[인공지능] No observation searching

No observation searching

percept 가 없음

이러한 문제를 Sensorless 또는 conformant 문제라고 함

Sensorless vacuum cleaner

현재 청소기가 어느 방에 있는지, 방이 깨끗한지 더러운지 알 수 없음

 

initial state : {1,2,3,4,5,6,7,8} → 이 모든 state 가 belief state

After “Right” : {2,4,6,8}

After “Suck” : {4, 8}

Solution : { Right, Suck, Left, Suck }

 

현재 state 는 알 수 없지만 Action 으로서 belief state 의 수를 줄여나가는 것이 핵심

 

Fully observable problem 에서 Sensorless problem 으로 변환하여 문제를 풀어나감

 

문제 정의

• State, Initial state

• Physical state : 원래의 state → Physical state 의 수 = N

• 새롭게 정의되는 state(P) 는 physical state 들의 모든 조합 →  Belief state = 2N

• 새롭게 정의되는 Initial state 는 모든 physical state 를 가진 state

• Action

• P 의 각 원소(state)가 취할 수 있는 모든 action 의 set

• Transition model (d)

• Deterministic : d = {s’ : s’ = RESULT(s, a), s ∈ b}   (b = belief state, s = physical state)
  각 state 마다 action 을 취해서 나오는 모든 successor 를 말함

• Nondeterministic : d = {s’ : s’ ∈ RESULT(s, a), s ∈ b}   (b = belief state, s = physical state)

• Goal-test : belief state 의 모든 원소 state 가 goal test 를 통과해야 goal

• Step-cost : action 의 cost 가 모두 같다고 가정

Belief state 도식

이론적으로 belief state 는 28 으로 256개이지만 실질적으로 도달 불가능한 state 를 빼면 12개 뿐임

Belief state 에서의 Graph search

Tree search 보다는 graph search 가 더 효율적임

b` 이 b의 부분집합이라고 하자

b 를 거쳐서 goal state 로 갈 수 있다면 b`을 거쳐서도 goal 로 갈 수 있다.

대우 : b` 을 거쳐서 goal 로 갈 수 없다면 b 또한 갈 수 없다.

 

Graph search 에서는 frontier 에 이미 들어갔던 노드에 대해서는 중복 검색하지 않음

만약 b`이 있다면 b 는 frontier 에 넣지 않을 수 있기 때문에 Tree search 보다 효율적임

b 가 frontier 에 들어가야하는 조건은 b`은 goal에 도달할 수 없으나 b는 도달할 수 있는 경우이며, 이 경우는 대우명제에의해 모순임