[인공지능] And-Or Tree

Partially observable, Nondeterminitic world

Partially observable : state 의 정보가 전부 다 주어지지 않는 문제

주어지는 percept 를 통해서 가능한 state 의 경우의 수를 줄이는데 큰 도움을 줌

 

Nondeterministic : state 가 action 을 취했을 때 다음 state 가 확정적이지 않음 (확률적으로 결정)

percept 를 통해 다음 state 가 무엇인지 알려줌

 

Contingency plan : state 가 확률적으로 정해질 때 상황에 따라 대응이 달라지는 것 (if-else)

 : agent 가 만나는 percept 에 따라 action 이 바뀜

Erratic Vacuum World

더러운 방을 suck 하면 현재 방은 물론 옆 방도 깨끗해질 수 있음 (확률적임. 옆 방은 안깨끗해질수도 있음)

깨끗한 방을 suck 하면 현재 방이 다시 더러워질 수도 있음

initial state : 1

Goal state : 7 and 8

Solution : [Suck, if state = 5 then [Right, Suck] else []]

And-Or search tree

기존의 tree 와는 달리 action 또한 하나의 노드로 나타냄

Action : And node

State : Or node

 

특징

• 모든 leaf 는 goal node 여야함

• Or 노드는 1개의 action 만을 선택

• And 노드는 모든 state 를 표함해야함

Slippery vacuum world

청소기 로봇이 미끄러져서 left/right 가 수행되지 않을 수도 있는 문제 ( cycle 이 존재 )

1번 상태에서 Right 했을 때 현재 상태 : 1 or 2

Cycle 이 있는 문제의 경우에는 무한 Loop 할 수 있는 solution 을 내주어야함

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