Searching with Partial Observations
- agent 의 percept 는 현재 위치한 state 를 정확히 알지 못한다. 가능한 state 가 둘 이상 존재할 수 있다.
- Belief states : 내가 어떤 state 에 있는지 정확히 알 순 없지만 가능한 state 에 있을 것이라고 생각 (후보군)
Searching with No Observation
- percept 가 없는 경우이다.
- sensor 가 없고 그에 순응하는 문제들이다. (sensor 의 비용이 크기 때문에)
- 예) 컨테이너 벨트에서 물품의 방향을 고치기 위해 카메라가 존재할 수 있다. 카메라로 방향을 파악하는데, 카메라가 비싸니깐 몇번의 action 으로 고정된 방향을 가리치도록 대체할 수 있다.
A Sensorless Vacuum Cleaner Agent
- 만약 위치 센서가 있고, 먼지 센서가 있더라도 partially observable 하다. [A,dirt] 의 정보를 센서를 통해 알게되더라도 현재 나의 state 가 8개 state 중 어디에 있는지 모르기 때문이다.
- 위 문제에서 agent 는 위치 센서, 먼지 센서를 모두 가지고 있지 않다. 그러나 world 가 deterministic 하다는 지도를 알고 있다.
- 따라서 Initial states 는 {1,2,3,4,5,6,7,8} 로 belief state 가 될 수 있다. (후보군)
- 이곳에서 Right action 을 취하면 {2,4,6,8} 로 belief state 가 줄어들게 된다.
- 여기서 Suck 을 취하면 {4,8} 로 belief state 가 더 줄어들게 된다.
- 따라서 solution 은 {Right, Suck, Left, Suck} 이 될 수 있다.
Solving Sensorless Problems
- belieft state 상에서 search 를 하면 된다. 이때, belieft state 상에서의 search 문제는 fully observable 하다. 왜냐하면 agent 가 자신의 belieft state 를 확실히 알고 있기 때문이다. 이때 solution 은 sequence of action 이 된다.
- 원래의 문제 P 로부터 belieft-state 상에서의 문제로 변환할 수 있다.
– States and initial state
– ACTIONS P
– Transition model: RESULTP
– GOAL-TEST P
– STEP-COST P
Sensorless Problems
- Belieft states : 모든 physical states 의 가능한 집합들 (전체 state 의 부분집합) -> 2^N
- Initial state : 전체집합 (P 의 모든 states)
- Actions : belief state 를 구성하는 모든 state 들의 action 의 합집합 (무의미한 action 이 아무런 영향을 끼치지 않는다는 조건하에)
- Transition model :
nondeterministic 한 경우, 특정한 aciton 을 취하더라도 결과가 여러개가 될 수 있기 때문에 '=' 로 표현되지 않는다.
The Belief-State Search Problem
(a) 는 deterministic, (b) 는 non deterministic 이다.
Goal test 는 현재 belief state 에 들어있는 모든 physical state 들이 goal test 를 만족해야만 GOAL-TESTp가 된다.
ex) {7,8} 이 belief state 일때
Path cost : 모든 action 의 비용이 같다.
Reachable Belief States for the Sensorless Vacuum World
2^8=256 개의 belief state 가 이론상 가능하지만, 실제는 12개의 state 가 존재한다.
belief state 상의 search 는 이전에 배운 BFS,DFS... 등 을 사용할 수 있다.
Graph Search in a Belief-State Search Problem
이전에 방문했던 state 와 똑같지 않더라도, 부분집합이나 Superset 의 개념을 이용해서 그런 노드를 방문하지 않을 수 있다. 따라서 search 를 조금 더 효율적으로 진행할 수 있다.
- belief state b 를 통해서 solution 이 만들어 질 수 있다면, b의 부분집합에 대해서도 똑같은 solution 이 만들어질 수 있다.
ex)
b 가 {1,3,5,7} 일때 initial state 에서 b를 통과해서 goal 로 갈 수 있다고 가정하자. 그렇다면 {1,3,5,7} 중 어느 state 를 거치더라도 goal 에 도달할 수 있음을 말한다.
따라서 b' 이 {5,7} 이라면 initial state 에서 b' 을 통과해서 goal 로 갈 수 있음은 당연해진다.
명제 : {1,3,5,7} yes -> {5,7} yes
대우 : {5,7} no -> {1,3,5,7} no
-> frontier 에 {5,7} 이라는 belief state 가 이미 존재할 때, {1,3,5,7} 이라는 belief state 가 새로 들어와야하는 경우, 명제의 대우에 의해 이는 삽입되지 않을 수 있다. 따라서 frontier 에 들어가지 않는 state 들이 많아지므로, 더 많은 state 들을 search 하지 않을 수 있어 효율적이다.
댓글