Partially Observable and/or Nondeterministic Worlds, AND-OR Search Trees, The Slippery Vaccum World

Partially Observable and/or Nondeterministic Worlds

- fully observable, deterministic 한 문제들에서 percept 은 새로운 정보를 제공하지 않았다.

- partially observable 하다면, 가능한 state 들 중 agent 가 어떤 state 에 있는지 percept 가 좁혀줄 수 있다.

- nondeterministic 하다면, 가능한 결과가 실제로 일어난 것을 percept 가 알려준다.

-> percept 들이 미리 정해져있지 않다.

따라서 어떤 percept 가 들어오냐에 따라 agent 가 action 을 다르게 해야 한다.

solution 은 action sequence 가 아니라 contingency plan 이 된다. (어떤 일이 일어나냐에 따라 계획을 다르게 해야함)

 

 

The Vacuum Cleaner Agent

initial state 1번에서 suck 을 취하면 5번 state, 5번 state 에서 right 을 취하면 5번 state, 5번 state에서 suck 을 취하면 8번 state 로 가므로, 3번의 action 으로 goal 다다르는 것이 optimal solution 이 된다.

이 경우는 deterministic 한 environment 이다.

 

 

The Erratic Vaccum World

- 'Suck' action 에 nondeterministic 을 취한 문제이다.

- 이 경우엔, suck 을 취한다면 현재 방만 청소할 수도 있고, 또는 다른 방의 먼지까지 모두 청소할 수도 있다.

- 만약 방이 깨끗할때 suck 을 취한다면, 때로는 방이 다시 더러워질 수도 있다.

 

- Solution 

1번에서 suck 을 취한다면 5또는 7 state 로 갈 수 있다.

5번 state 의 경우 right, suck 을 취해야 하고, 7번 state 의 경우 아무 action 을 취할 필요가 없다.

따라서 [ Suck, if State = 5 then [Right, Suck] else [] ] 이 solution 이 된다.

-> Contingency plan 

 

 

 

AND-OR Search Trees

initial state 인 root node 에서 Suck 또는 Right action 을 취할 수 있다.

이때 Suck 을 취하게 되면 state 가 하나로 고정되는 것이 아니라, 5번 또는 7번 state 로 나뉠 수 있다.

5번 state 에서 suck 또는 right 을 actinon 을 취할 수 있다.

이때 네모난 node 는 OR노드로 solution 을 정하기 위해 어떤 action 을 취할지 정해줘야 하고,

동그란 node 는 AND노드로 모든 branch 에 대해 어떤 action 을 취할지를 정해야 solution 이다.

 

이때 AND-OR tree 의 subtree 는 다음과 같은 조건을 만족한다면 solution 이 될 수 있다.

- 모든 leaf node 는 goal node 이다.

- OR node 에서는 하나의 action 을 선택해야 한다.

- AND node 에서는 모든 branch 에 대해 action 이 포함되어 있어야 한다.

-> [Suck, if State = 5 then [Right, Suck] else []]

 

 

 

An AND-OR Search Algorithm

depth-first recursive 알고리즘이다.

OR-SEARCH(problem.INITIAL-STATE, problem, []) 에서 []는 지금까지 찾은 경로인데, 이는 중간에 만났던 state 를 다시 만날 경우 더 search 하지 않고 건너뛰기 위한 경로이다.

 

OR-SERACH

- 현재 state 가 goal 인지 확인하고, 맞다면 plan 을 리턴한다.

- 만약 지금까지의 경로에 현재 state 가 포함되어 있다면 loop 이기 때문에, failure 을 리턴한다.

- 현재 state 에서 가능한 모든 action 에 대해서 , AND-SERACH 를 진행하고 결과로 plan 을 얻는다.

- 만약 plan 이 failure 가 아니라면, solution 이 있는 것이므로 현재 [action | plan] 을 리턴한다. 이때 plan 은 이 action 다음에 실행될 수 있는 action 들을 AND-SEARCH 에서 받아온 것이다.

 

AND-SEARCH

- 인자로 받은 states는 두개 이상이 올 수 있다.

- OR-SERACH 를 실행한 결과인 plan 이 failure 가 아니라면 solution 을 리턴해준다.

 

 

 

The Slippery Vaccum World

- cycle 이 없는 solution 는 존재하지 않는 문제이다.

- 가끔 action 을 취했을 때 실패할 수도 있기 때문이다.

 

 

 

Part of the Serach Tree for the Slippery Vaccum World

- 이전의 알고리즘으로 진행한다면 loop 가 발생하므로 failure 을 리턴할 것이다.

- 그러나 cyclic solution 은 존재한다.

– [Suck, L1: Right, if State=5 then L1 else Suck]

- cycle 이 있는 경우 계속해서 goal 을 찾지 못할 수도 있다. (로봇의 바퀴가 고장나서 right 를 할 수 없는 경우)