[인공지능] 10. Planning

1. Planning Problem Representation

 

 1) Planning Domain Definition Language (PDDL)

 : search problem을 정의하는데 필요한 4가지 요소를 설명한다.

  -> initial state, actions, result, goal test

 

   ① States

    : 각각의 state는 "ground하고 functionless하고 atoms한" conjunction of fluents로 표현된다. 

     즉 variable이 없어야 해요

   Database semantic이 사용되는데 

     - closed-world assumption : 어떤 fluents도 false로 언급되지 않고

     - unique names assumption : 서로 다른 constants는 구별되어야 한다

    ex) At(P1, SFO) ∧ Plane(P1) ∧ Airport(SFO) ∧ Airport(JFK)

  

   ② Action Schema

    : Action들은 actions schemas의 set를 통해 표현된다.

     action schemas는 action name과 precondition, effect에서 사용된 variables의 list로 이루어진다.

    이 때 precondition과 effect는 literal들의 conjunction들로 이루어져 있다. (positive, negated atomic sentence 둘 다 됨) precondition은 action이 수행될 수 있는 조건이고, effect는 action이 수행되고 난 뒤의 결과이다. 언급 안된건 그대로다. 

 

   variables은 기본적으로 universally quantified라고 가정한다. 우리는 변수를 instantiate 하고 싶을 때, 값을 자유롭게 선택할 수 있다. 

 p라는 변수에 P1, from엔 SFO, to에는 JFK를 넣었다.

 

  s가 action a의 precondition을 entail 할 때 action a는 state s 에서 수행될 수 있다. 

   " 𝑎 ∈ 𝐴𝑐𝑡𝑖𝑜𝑛𝑠 (𝑠) ⇔ 𝑠 ⊨ Precond (𝑎) "

  precondition이 s에 의해 만족이 된다면, action a가 state s에서 applicable하다고 말한다. 

  q의 모든 positive literal이 s에도 있고, q의 모든 negated literal이 s에 없을 때, s가 q를 entail한다고 말한다.

( 즉, 만족해야하는 조건은 s가 가지고 있고, 없어야 하는 조건은 s가 가지고 있지 않을 때 s가 q를 entail한다.)

이러한 action schemas 의 set은 planning domain의 definition로 역할한다.

 

 

  action a의 result는 state s'로 정의되는데, s'는 s state에다가, action effect에 있는 negative literal은 없애고 positive literal은 더해준다. 즉 Result(s, a) = (s - Del(a)) ∪ Add(a)

안 어렵다 걍 원래 state에서 action 적용한 결과가 result이다. effect에서 negation이 붙어있던 literal은 state에서 없애주고, positive literal은 기존 state에 추가해준다.

 

  effect 안에 있는 모든 variable이 precondition에 언급되어야 한다는 것이 action schemas의 요구 사항이다. 그래야지 precondition과 state s 이 일치할 때 모든 variable이 result에 반영되게 된다. 그 결과 result(s,a)는 오직 ground atoms만 갖게 될 것이다.

 

 

  ③ Initial State와 Goal Test

 - Initial State는 ground atoms의 conjunction으로 이루어진다.

 - Goal 은 precondition 처럼 literal들의 conjunction으로 나타내진다.  (이 때 vaiable도 포함될 수 있다.) 

   variable들은 "existentially" quantified 되었다고 여긴다.

   만약 우리가 어떤 state에서 goal을 entail하는 sequence of actions을 찾으면 problem이 풀렸다고 한다.