[인공지능] 4. Beyond Classical Search - 2

2. Local Search In Continuous Space

 : 지금까지는 현재 내가 어떤 state에 있는지, action을 취하면 어떻게 되는지, 이산적, 그리고 이 게임의 규칙이 뭔지 아는 경우였다! 즉 fully observable, deterministic, discrete, and known environment! 

 

discrete와 continuous한 환경의 구분은 시간이 다뤄지는 방법과 agent의 action과 percept에 따라 이루어진다.

지금까지 설명했던 알고리즘으로는 continuous state와 action space를 다룰 수가 없다. (단, first-choice hill climbing과 simulated annealing 제외) 왜냐면 연속적인 경우 branching factor가 무한히 많아 가능한 경우의 수가 너무너무 많기 때문이다. 이걸 다 일일히 탐색할 수는 없으니...

 

 

 1) Gradient Ascent/ Descent Search

 

이러한 continuous problem을 피하기 위해서는 각 state의 neighborhood를 discretize 하는 방법이 있다. 즉, 연속적인 state를 discrete state로 바꿔주는 것이다. 

 

이산적인 값으로 바꿔주고 나면 우리는 gradient를 구할 수 있다. objective funtion의 gradient값은 가장 가파른 구간의 방향과 정도를 알려주는 vector ∇f(x)이다. 즉 f(x)를 미분한 값, 기울기가 gradient 값이다. steepest-ascent hill climbing는 현재 state를 x<- x+ a∇f로 업데이트 하면서 수행할 수 있다. 이 때 a는 step size라고 불리는 작은 상수값이다. 

이게 뭔 소리인가 하면, 그라디언트 값, 즉 f(x)의 미분값을 따라서 x값을 a 만큼씩 이동시켜 나간다는 얘기다. 만약 최댓값을 구하고 싶으면, 기울기가 양수인 그래프를 따라 이동해야할 것이고, 최솟값을 구하고 싶으면 음수인 구간을 따라 이동하게 되겠지? 

 

이 object function은 미분 불가능한 상황에서는 사용할 수 없을 수도 있는데, 이럴 경우 우리는 x값이 조금 변함에 따라 증가하는 양 또는 감소하는 양을 알아내는 empirical gradient를 이용하여 그래프의 기울기를 추정할 수 있다. empirical gradient search는 이산적인 상황에서 steepest-ascent hill climbing과 같다. 

 

적절한 a값을 구하는 것도 미션이다. a가 너무 작으면 step이 너무 많이 필요하고, a가 너무 크면 search가 maximum이 있는 구간을 뛰어 넘어버릴 것이다.

 

* line search는 이러한 a의 값을 적절히 구하는 방법이다. a의 값을 doubling 시켜가면서 f가 변화하는 추이를 잘 지켜보다가, 어느순간 확 감소해버리는 지점을 찾는다. 만약 어떤 point에서 감소하기 시작하면 그 직전 point를 new current state로 추가한다.

a->2a->4a 로 이동하다가 4a에서 값이 갑자기 감소해버렸으니까 2a로 돌아가 state을 추가한다. 

 

 

  2) Newton-Raphson Method

 

Newton-Raphson Method는 function의 근(g(x) = 0 이 되는 지점)을 찾는 가장 일반적인 방법이다. g(x)에서 근은 x값 대신 x = x - g(x)/g'(x)로 근사해가며 구할 수 있다. 

 

f의 maximum 또는 minimum 값을 구하기 위해서는 gradient값이 (기울기가) 0이 되는 지점을 찾아야 한다.

 

 

그래서 newton's formula 에서 g(x) = ∇f(x)로 두고 근을 찾는 것이다. 이걸 공식으로 풀면, 결국 x = x 0 Hf^(-1)∇f(x) 가 된다. 어우 헷갈려 그래서 이 Hf^(-1)이 뭔데?? Hf = (∇f(x))'=(f(x))''즉, f(x)의 이계도함수이다. 사실 그래서 그냥 앞의 식 x = x - g(x) / g'(x) 에서 g(x)에 f'(x)를 대입한 것과 같다. 즉 f'(x) = 0이 되는 x의 값을 x = x - f'(x) / f''(x)로 근사해가며 푸는 것이다. 

 

보면 x값에서 g(x)/g'(x) 값을 빼주다 보면 x값이 근에 근사하게 된다. 왜냐면 x=근 일 때, g(x)가 0이 되니까! 계속 조금씩 조금씩 빼주다보면 언젠간 근에 가까워 지겠쥬

 

 

 

3. Searching with Nondeterministic Action 

 

만약 agent에 의해 action이 수행되었을 때  다음 state가 현재 state에 의해 완벽히 결정될 경우, 즉 다음 state를 예상할 수 있다면 이 환경을 deterministic하다고 부른다. 그렇지 않으면 stochastic하다. (stochastic은 확률적인거)

 

nondeterministic environment에서 각 action들은 action을 취했을 때 가능한 outcome들의 후보를 알수는 있지만, 그 중 뭐가 다음 state가 될지는 알 수 없다. 그 각각의 state에는 확률조차 존재하지 않는다.  즉, 뭐가 나올지 아예 모르는거다.

 

그래서 우리는 not fully observable 하거나 not deterministic 하면 environment가 uncertain 하다고 부른다. 

 

만약 environment가 nondeterministic하다면, 센서를 통해 인식을 해서, action이 수행되었을 때 가능한 outcome들 중에서 어떤 outcome이 실제로 일어났는지를 agent에게 알려준다. 

 

예로 고장난 로봇청소기가 있다고 치자. 쓰레기를 빨아 들일수도, 그렇지 않을 수도,옆 칸까지 다 빨아들일수도 있다. 그래서 방에 쓰레기가 있어도 얘를 흡수할지 안할지를 모르는 것이다. 그래서 이 vacuum world에는 총 8가지의 가능성이 있을 수 있다. 이 중 7과 8이 goal state이다. 

 

 

* Contingency Plans

: environment가 nondeterministic할 때, 미래의 percept은 결정되어질 수 없으며 agent의 미래의 action은 이러한 미래 percept에 의존한다. 그래서 problem의 solution은 어떠한 sequence가 아니라 모든 경우를 다 생각하는 contingency plan(=strategy)의 형태로 나타나진다. 왜냐면 각 percept마다 수행할 수 있는 action이 다 다른데, 미래에 어떤 percept가 될 지 모르니까! 

 

그래서 nondeterministic problems의 solution은 "if-then-else statements"를 포함한다. 즉 sequence가 아니라 tree의 꼴로 나타난다는 것이다. 수행하는 동안 일어날 수 있는 모든 경우의 수를 기반으로 action을 선택할 수 있게 한다. 

 

ex) [if percept then action-1 else action-2]

 

 1) AND-OR Search Trees

 deterministic environment에서는 각 agent의 choice에 따라 branch가 오직 하나였다. 따라서 뭐 이 action을 하든 저 action을 하든 선택할 수 있었고 state들 끼리는 or로 묶여 있었다. 그래서 이 node들을 OR node라고 부른다. 

 반면 nondeterministic environment에서는 각 action에 대한 outcome이 두 개 이상일 수 있고, action에 대한 모든 outcome이 goal로 갈 수 있어야 action이 solution이 될 수 있으므로 AND node가 된다. 

  이 두 가지 node를 이용해 만든게 바로 AND-OR tree이다.  

 

 

이 때 LOOP는 위에 이미 나와있던 state로, 이 node는 더이상 탐색해보지 않아도 된다. (=failure 를 리턴한다) 이 node에 솔루션이 없다는 것이 아니라, 어차피 위에 있었으니까 solution이 있다면 거기서 이미 나올 거니까! 이 노드는 더이상 보지 않겠다는 의미이다. 

 

AND-OR search problem의 solution은 다음과 같은 특징을 갖는 subtree이다.

  - 모든 leaf가 하나하나 goal node이다.

  - 각각의 OR nodes에서는 한 번에 하나의 action만이 수행된다.

  - 각각의 AND nodes에 모든 가능한 outcome branch가 포함된다.

 

 

먼저 AND-OR-GRAPH-SEARCH가 시작되면 initial state를 or search 하기 시작한다.

 

OR-SEARCH에서는 만약 현재 state가 goal이라면 empty plan을 리턴해준다. (이미 plan에 차곡차곡 쌓여있음)

만약 state가 이미 지나온 path에 있었더라면 loop(cycle)이므로 failure을 리턴해준다.

그리고 나서 state에서 취할 수 있는 모든 action을 검사해볼 것이다.

plan이라는 변수에 and-search의 결과를 집어 넣고, 이 결과가 failure가 아니라면 기존 solution에 해당하는 plan 즉 action을 추가해준다. and-search를 보낼 때에는 현재 state에서 특정한 action을 취했을 때 나올 수 있는 future state과, 기존 path에 현재 state을 추가해서 보내준다.

모든 action을 검사해준 다음에는 더이상 볼 것이 없으므로 그냥 failure 리턴해준다.

 

AND-SEARCH에서는 or search에서 날아온, action에서 가능한 모든 state의 경우를 검사해볼 것이다.

각 state마다 or-search를 다시 보내서 하나라도 failure가 되면 and search의 값도 failure가 될 것이다. 

만약 모두 failure가 아니었다면, 존재하는 state들에 대한 plan을 전부 return해준다. 그러면 이 아이를 다시 or search가 받아서 plan에 넣을거고, 그렇게 solution에 해당 plan이 추가되게 된다. 

 

* Cyclic Solutions

 

그렇다면 만약 청소기 바퀴가 고장나서 오른쪽으로 가라는 명령에 오른쪽으로 갈 수도, 가만히 있을 수도 있다고 가정해보자. 이 경우 cycle이 생기게 되는데, 그렇다고 해서 이 경우 solution이 없는게 아니다. 근데 이 경우를 loop라고 처리해버리면 solution을 영영 찾지 못하는 경우가 발생할 수 있다. 그러면 이러한 cyclic한 solution은 어떻게 표현을 할 수 있을까?

 

이 경우 plan의 일부에 label을 붙여서 계속 반복하게 만들 수 있다. 계속계속 try해서 state가 넘어가 solution으로 넘어갈 때까지 반복하는 것이다. 쉽게 코드로 쓰면 while(state==5) do action(right); 정도가 되겠지? 근데 우리는 labeling을 통한거니까 while 보다는 goto 문이라고 생각하면 쉽다. state==5면 goto label1 요정도?

 

ex) [label-1 :, action -1 ,... , if percept then label-1 else action-2] : action-1(label-1)을 했을 때 어떤 특정 percept가 나왔으면 다시 action-1(=label-1), 아니면 action-2를 수행해라.

 

 

 

4. Searching with Partial Observation

  

  * Sensorless Problem ( = conformant problem) 

   : 센서가 고장나서 현재 percept에 대한 정보를 받지 못하는 상황의 문제

  

  -> 현재 내 상태가 어디에 있는지 모르지만, 일단은 오른쪽으로 이동하기, 먼지빨아들이기, 왼쪽으로 이동하기, 먼지빨아들이기를 다 수행하고 나면 무조건 solution에 도착할 수는 있다.  

 

 * Belief State

 

  agent가 여러가지 가능한 state중 하나에 있다고 할 때, 하나의 action은 또 여러가지 가능성 중에 하나를 만들어 낼 것이다. (deterministic 할 때) 이렇게 partially observable한 문제를 풀기 위한 키가 바로 Belief State이다. 

  Belief state 란 어떤 percept과 action의 sequence가 주어진 경우, 현재 state일 수 있는 모든 physical state들을 말한다. 이 sensorless problem을 해결하기 위해서는 physical state가 아니라 belief state의 space를 search해야한다. 기존 탐색 문제에서 physical state를 belief state로 바꿔치기 했다고 보면 된다. 

  belief-state space에서는 problem이 fully obserbable한데, agent가 자신의 belief state를 항상 알기 때문이다. 더 나아가 solution은 항상 action들의 sequence로 나타나게 될 것이다. 즉, belief state 레벨에서는 observable 문제로 바뀌게 된다. 

 

 

1) Searching with Unobservable States : 내가 어떤 state인지 전혀 알 수 없을 때

 

  physical problem P가 있다고 가정해보자. 이 때 우리는 Actionsp, Resultp, GoalTestp, StepCostp를 정의할 수 있다. 

 

  - Belief states: physical state의 모든 가능한 set을 포함하는 belief-state space. 즉 physical state를 원소로 가지는 모든 가능한 부분 집합. n개의 state가 있다면 belief state는 2^n개

 

  - Initial state : 모든 Physical state를 포함하고 있는 전체 집합. 

 

  - Actions 

         불가능한 action을 취했을 때 아무런 변화가 없다면, 각 state에서 가능한 action들을 전부 합집합 해줘도 됨

         불가능한 action을 취했을 때 failure가 된다면 합집합을 하면 안된다. 교집합을 해야 한다. 

 

  - Transition model : 어떤 action을 수행한 후 새로운 belief state가 생성되는 과정을 prediction step이라고 부른다. 

                             b'(새로운 belief state) = Result(b, a) (state b 에서 action a 수행) == Predict(b, a)

 deterministic action이라면, Result(b,a)는 b의 값보다 커질 수 없다. 왜냐? 당연하게도 state b에서 action을 취하면 각각 하나의 new state b'가 생성되니까!  

      Result(b,a) = {s' | s' = Resultp(s, a) ∧ s ∈ b}  // s가 belief state의 원소일 때 s'는 resultp(s, a)이다. 

nondeterminism일 때 Result(b, a)는 b의 값보다 클 수도 있다.

      Result(b,a) = {s' | s' ∈ Resultp(s, a) ∧ s∈b } = Us∈b Resultp(s, a) // s'는 resultp(s,a)에서 나올 수 있는 모든 경우의 수이다. 

 

  - goal test : beilef state 안에 있는 모든 physical state가 goal을 만족하는가. 

 

  - path cost : 모든 state에서 action의 cost는 다 동일하다고 가정한다. 만약 같은 action이 다른 state에서 서로 다른 cost를 갖는다면, 각 belief state에 따라 action을 수행하는데 드는 cost가 여러가지 value 중 하나가 되어 버린다. 이것은 또다른 문제를 야기할 수 있다. 그래서 다 동일하다고 가정하는거임.

 

       

이렇게 모든 가능한 state를 포함하고 있는 initial state으로 부터 탐색 알고리즘을 사용하면 된다.

 

* Pruning : 가지치기

 : 어떤 belief state b에 대해서 한 action sequence가 solution이라면, b의 subset 역시 solution이다. 그러므로 우리는 만약 이미 superset의 subset이 생성되었다면, 다른 level에서 이 superset으로 가는 path들은 가지치기 해서 더이상 볼 필요가 없다. 이러한 pruning은 sensorless problem을 푸는데 아주 좋은 효율성 개선 효과를 보여준다. 

  -> 애초에 [1, 2]에서 action b를 하면 바로 goal이 나올 수 있는데 굳이 action a 를 걸쳐서 goal로 갈 필요가 없음.

 

 * 가장 큰 문제는, 각 belief state들의 크기이다. 예를 들어 initial belief state가 10x10이라고 하면, vacuum world는 100x2^100이 된다. 이건.. states들의 리스트를 atomic represetation으로 나타내기엔 너무도 많다.... 

   -> 하나의 솔루션은 belief state를 보다 압축적인 설명으로 나타내는 것이다. (ex. 100개 다 깨끗)

   -> belief state에서 state 일부를 먼저 꺼내서 search하고, 다음 state도 또 search하고. ..  develop incremental belief-state search algorithm을 쓴다. 나온 답이 같으면 계속 search를 해 나가고. 하나라도 solution이 나오지 않으면 failure.

 

 

    2)  Search with Partially Observable States : 일부만 observable한 경우

  

 이 경우 action, step cost, goaltest는 앞서 했던 sensorless problem과 같다. 단, transition model에만 조금 차이가 있다. 다음 belief state를 만들기 전에 어떤 state가 가능할지 예측하고 또, 가능한 percept를 측정해야 한다.

   

  ① prediction stage : 예측 단계 (sensorless problem과 동일) : belief state b에서 action a를 수행했을 때 가능한 state                                b' = Predict(b, a)

  ② observation prediction stage : 관측 예측 단계 : predicted belief state에서 관측할 수 있는 percept를 예측한다. 

                             PossiblePercepts(b') = { o | o = Percept(s)  ∧ s ∈ b' }

  ③ update stage : 각 percept들이 가능할 수 있는 state들끼리 모아서 새로운 belief state로 만들어준다.  

                             b0 = Update(b', o) = {s | o = Percept(s)  ∧ s ∈ b' }

 

이 세 단계를 합쳐서 표현하면 다음과 같다.

 Result(b, a) = { b0 | b0 = Update(Predict(b,a), o)  ∧ o ∈PossiblPercepts(Predict(b,a))}

//가능한 모든 belief state에서 가능한 percept 중 하나를 골라, 이 percept가 나오도록 하는 belief state들의 집합을 b0에 update 시킨다.

 

(a) 를 보면 청소기가 있는 방에는 먼지가 있는지 없는지를 알지만 다른 방에는 먼지가 있는지 없는지를 모른다고 하자.  이 때 두가지의 belief state가 존재한다. 이 때 청소기를 오른쪽으로 이동시키면 두가지의 state가 가능하다.(prediction) 이 때 가능한 percept는 오른쪽 방에 먼지가 있거나/ 없거나. 즉 이 사실을 바탕으로 prediction belief state를 분리하여 각각 update 시켜준다.

 

(b)의 경우는 바퀴가 고장난 경우이다. 오른쪽으로 가라는 action을 명령했을 때 가능한 belief state는 총 4가지 이다. 여기서 가능한 percept는 [청소기가 오른쪽에 있고 방이 더럽다], [청소기가 왼쪽에 있고 방이 더럽다], [청소기가 오른쪽에 있고 방이 깨끗하다] 라는 세 가지 경우로 나눌 수 있다. 그리고 각각의 percept가 나올 수 있는 belief state를 update 해준다. 

 

이렇게 partially observable한 문제에서는 action을 취한 다음에 정확히 어떤 percept가 올 수 있는지 예상하는 것이 불가능하다. 따라서 nondeterminism 하다. 이러한 상황에서는 우리가 AND - OR search tree를 그릴 수 있다. 

 

 * AND-OR search for Partial observability

 : solution은 belief state에 대한 conditional plan으로 나타나게 된다. 

  agent는 action을 수행하고 percept를 받는 동안에 belief state를 유지해야 한다. 이 function은 여러가지 이름으로 불리는데 monitoring, filtering, state estimation이 있다.

 new belief state b' = Update(Predict(b, a), o)

 

 - 현재 state에의 subset 또는 supersets이 전에 생성된적이 있는지 확인함으로써 imporve할 수 있다

 - 또한 incremental search algorithms을 통해 black-box approach에 비해 더 빠른 속도를 보여줄 수 있다. 

 (둘 다 sensorless problem과 같다)

percept를 통해 지도의 어느 위치가 가능한지 선택지를 줄여 나가는 모습