[인공지능] 3. Solving problems by searching - 3

5. Heuristic Search 

  * Best-First Search

     : Best-first search는 일반적인 TreeSearch나 GraphSearch algorithm의 instance이다. 이 때 node는 evaluation function인 f(n)에 기초해 expansion된다. Evaluation function은 cost estimate와 같은 것으로 이해할 수 있으며, 그래서 가장 작은 evaluation을 가진 node가 가장 먼저 expand된다.

    즉, Best-First Search는 대부분의 TreeSearch나 GraphSearch 알고리즘에서 쓰이고, node를 확장해 나갈 때 어떠한 evaluation function을 기준으로 한다. 이 때 이 Evaluation function은 경로를 지나는데 드는 cost를 반환하는 등의 함수가 있으며, 이 evaluation이 가장 작은 node부터 추가해나간다. 

 

   - best-first graph search의 수행은 uniform-cost search에서 g(priority queue)의 사용이 f로 변했다는 것만 제외하면 동일하다.

   - search strategy는 f를 무엇을 사용하느냐에 따라 결정된다.

   - 대부분의 best-first search 알고리즘에서는 f를 heuristic function h(n)으로 가지고 있다. 

     heuristic function은 시작 state인 node n에서부터 goal state까지의 가장 적은 path cost를 측정하는 것을 말한다.

   - 따라서 n이 goal node이면 h(n) = 0 이다.

 

 1) Greedy Best-First Search

    : Greedy Best-First Search는 가장 goal에 가까운 node를 expand한다. 그러므로 휴리스틱 함수를 이용해 node를 evaluate 한다. (f(n) = h(n))

    greedy best-first graph search는 uniform-cost search에서 priority queue의 순서였던 g 대신, h가 쓰인다는 점을 제외하고는 모두 동일하다. 

 

  (h : 현재 노드에서 goal까지 거리가 가장 짧은 것)

 

Uniform Cost search

goal까지의 직선거리

  (b)에서는 sibiu의 h값이 가장 작으므로 그것 먼저 expand.

  (c)에서는 Fagaras Expand. 그러고 나면 goal인 bucharest를 찾을 수 있다. 

 

  - greedy best-first tree search는 dfs처럼 finite state space에서조차 incomplete하다. Greedy best-first graph search에서는 finite state space일 때는 complete하지만 역시나 infinite할 때엔 complete하지 않다. 

  - tree와 graph 모두 optimal하지 않다. (heuristic도 정확하지가 않다)

 

  -Time complexity : O(b^m)

  -Space complexity : O(b^m)

 

 

 

 

 

 

 2) A* search

   : A* search 는 evaluate function으로 현재 node까지의 cost를 구하는 g(n)과 현재 노드에서 goal 까지의 cost를 구하는 h(n) 두개를 합친 f(n) = g(n) + h(n) 을 사용한다. g(n)은 실제 측정값이니까 주어지고, h(n)은 cost의 최솟값을 추정한 값이다. 즉, 얘도 uniform-cost search와 다른 것은 g 대신에 g+h를 사용한다는 것. 

 

(a) initial state에서 가장 첫 노드 expand (f = 366)

(b) f값이 가장 작은 sibiu expand ( 140 + 253 )

(c) 이하동문

(d) rimnicu vilcea의 자식 노드를 살펴봤더니 f값이 fagaras보다 더 크므로 일단 fagaras를 expand

(e) bucharest goal이 있긴 하지만, 이 때의 f 값이 앞서 expand 해뒀던 pitesti보다 크므로 pitesti를 expand

(f) 더 f값이 작은 goal state 발견!  expand 완료! goal 찾음

 

 * Admissible  : goal까지 도달하는데 드는 cost를 예상한 값은 실제 cost를 절대 넘지 않는다.

                               이 조건이 바로 optimality 하기 위한 첫 번째 조건임

   만약 g(n)이 n까지 도달하는데 드는 실제 cost이고 f(n)이 g(n)+h(n)이라면, 결과적으로 f(n)은 실제로 n을 거쳐goal까지 드는 cost를 넘지 않게 된다. 즉, h(n) <= c(n~goal). h(n)의 정의가 애초에 직선거리로 최저 cost를 예상하는 것이므로 실제 cost보다 더 크게 예측하면 안된다. 

 

 * Consistency(=monotonicity) : 모든 node n과 n의 모든 자손 노드 n'가 있을 때, n에서부터 goal까지의 예상되는 cost는 (n에서 n'까지 가는 cost + n'에서부터 goal까지의 cost)보다 크지 않은 경우를 말한다. 즉, h(n) <= c(n,a,n') + h(n')

 

h(n) <= h(n') + c(n~n') 

이 때 h(n') <= c'(n'~goal) 이므로

h(n) <= c(n~n') + c(n'~goal) (실제 cost)

-> 모든 consistent heuristic은 admissible하다. 

-> 최소한 consistent 해야 optimal 할 수 있음

 

 

 * Optimality 

  - h(n)이 consistent하면, f(n)의 값은 어떤 path에서든 nondecreasing한다. 앞선 node보다 cost가 작아질 수 없음.

    f(n') = g(n') + h(n') = g(n) + c(n~n') + h(n') >= g(n) + h(n) = f(n)

 

  - A*가 어떤 노드를 선택할 때마다, 그 때까지의 경로가 그 노드의 optimal path이다. 만약 그렇지 않다면 다른 frontier node n'에 더 optimal한 path가 있어야 하는데, f는 nondecreasing하므로 n보다 더 낮은 node에 lower f-cost가 있을 수는 없다. 만약 더 cost가 작은 것이 있었더라면, 그게 먼저 select 됐을거다. 

 

  - 즉, (나중에 찾은 solution의 true cost) > (처음에 찾은 solution의 true cost) 가 항상 만족한다. 

  - 그러므로 만약 A* 에 의해 node들이 expand된다면, f(n)은 nondecreasing 할 것이다. 따라서 첫번째로 찾은 first goal node는 반드시 optimal solution이다. 

 

 

 * Contours :  A* search 시 f-cost가 증가하는 같은 영역의 노드를 추가하며 선을 그려 나가면, 등고선처럼 이 선은 시작 state를 중심으로 확장되어 나간다. 더 정확한 heuristic을 사용하면 할 수록, 이 band는 goal state를 향해 더 직선으로 쭉쭉 뻗을 것이며, optimal path를 중심으로 좁아질 것이다. 

 * pruning(가지치기) : 볼 필요가 없는 것은 고려 대상에서 삭제해버리는 것. (AI에서 중요함!) 

 

 * Completeness

  만약 C*이 optimal solution path의 cost라고 하면 우리는 다음과 같이 말할 수 있다.

   - A*는 f(n) < C*인 모든 노드를 expand 한다

   - A*는 그런 다음 goal node를 선택하기 이전에, goal contour(f(n) = C*)에 놓인 노드들의 일부를 expand 했을 것이다. 

   - Completeness는 C*과 같거나 작은 cost를 가진 node들이 유한한 경우 가능하다. (단 모든 step의 cost는 유한한 값 ε을 넘어야 하고, b는 유한해야 한다) 

 

 

* Optimally Efficient 

 : A*는 어떤 heuristic을 줘도 항상 optimally efficient하다. 또한 A*보다 더 적은 node를 expand하면서 optimal한 알고리즘은 없다. 그래서 f(n) < C*인 모든 노드를 expand하지는 않는 알고리즘은 모두 optimal한 solution을 놓칠 위험을 안고 실행된다. 

 

 * Complexity

  - 가장 흔한 문제는 search space의 states의 개수가 여전히 exponential한 경우이다. 즉 시간 공간 복잡도가 exponential한 경우가 생긴다.

 

  - 만약 state space가 많은 goal states를, 특히나 optimal goal state에 가까운 states를 많이 가졌다고 하면, search process는 최적의 경로와는 다른 잘못된 길로 유도될 수 있고, 이 때 추가적인 cost가 발생한다. 아무리 오차가 상수에 의해 제한된다고 하더라도, f(n) < C*인 states가 exponential 하게 많을 수 있다.

 

  - 이렇게 생성된 모든 node가 memory에 저장되기 때문에 A*는 시간 초과가 뜨기 이전에 runs out of space가 뜨는 경우가 많다.

 

 

*정리*

heuristic이 consistent하지 않으면 optimal하지 않음

                                            complete는 search space가 finite하면 complete

                                                                               infinite하면 incomplete

 

 

 3) Iterative- Deepening A* Search (IDA*)

  : memory requirements를 줄이기 위해 나온 아이디어로, standard iterative deepening과 다른 점은 cutoff used를 depth가 아니라 f-cost로 한다는 점이다. 매 iteration마다 cutoff value는 이전 iteration에서 cutoff됐던 node 중 가장 작은 f-cost값으로 설정된다. 

위 경우, (d)에서 cutoff된 값이 526/ 417/ 553이므로 fagaras를 탐색할 때의 cutoff값은 417이다. 이 때 bucharest와 sibiu 모두 cutoff값보다 크므로 바로 보지도 않고 return해버린다. 

 

- IDA*는 많은 문제에서 유용하지만, iterative version of uniform-cost search와 마찬가지로 실제 valued costs와 다르다는 문제가 있다. 

 

 

 4) Recursive Best-First Search(RBFS)

 : 오직 linear space만 사용하면서도 standard best-first search의 operation을 모방하려는 시도를 한 단순한 recursive algorithm이다. 

  - 이 structures은 recursive depth-first search와 유사하지만, f limit variable을 사용해서 현재 노드에서 가능한 가장 best alternative path의 f-value를 트래킹한다. 

  - RBFS는 subtree는 잊어버려도 subtree 중 best leaf의 f-value는 기억하고 있다. 그래서 시간이 지나고 subtree를 다시 expanding할 가치가 있는지 없는지를 결정할 수 있다.

 

 

 

(a) Arad의 f-limit = inf

    sibiu가 best가 되고 timisoara가 alternative로 f_limit(447)이 됨

    sibiu 시점에서 rimnicu vilcea가 best, fagaras가 alternative. 447>415이므로 f_limit = 415

   rimnicu vilcea 시점에서 pitesti가 best였는데 415<417이므로 그냥 return됨. 이 때 rimnicu vilcea의 f_cost값이 417이 됨. 

(b) rimnicu vilcea가 417이 되었으므로 Sibiu 기준으로 f_limit은 417, best는 fagaras

   fagaras 기준으로 best가 bucharest(450)이므로 return (450>417). fagaras의 f-cost는 450으로 업데이트

(c) sibiu 관점에서 best는 다시 rimnicu vilcea. 447 < 450이므로 f_limit = 447

   pitesti가 best, alternative는 craiova이지만 526>447이므로 패스 (여전히 f_limit = 447)

   pitesti 기준으로 best는 bucharest. goal 찾음

 

 

- best path가 extend될 때 마다 f 값이 증가할 가능성이 높기 때문에, 일반적으로 goal에 더 가까운 노드에 대해 h는 optimistic하지 않다. 이 경우 두번째로 best한 path가 최적의 path로 찾아질 수 있어서, backtrack를 이용해 follow it 할 필요가 있음. 

- A* tree search처럼 RBFS는 heuristic function h(n)이 admissible할 때 optimal algorithm이다.

- space complixity : linear

 

 

 5) Simplified Memory-Bounded A* Search (SMA*)

   : IDA* 과 RBFS는 메모리 사용을 너무 적게 하려고만 함. 사용가능한 메모리는 다 쓰는게 좀 더 sensible하지 않겠어?

 그래서 Simplified Memory bounded A*는 A*처럼 메모리가 찰 때 까지는 best leaf를 expanding한다. 이 때, 예전 노드를 없애지 않고 새로운 노드를 추가하는 것은 불가능 하다. SMA*는 언제나 가장 worst한, f-value가 가장 큰 leaf node를 삭제하면서 새 노드를 추가해 나간다. (단 이 때 기억을 해둔다) 만약 그 삭제한 노드의 ancestor의 subtree에서 best path가 나온 다는 사실을 알게 되었을 때, SMA*는 이미 둘러본 path들이 삭제한 path보다 안좋다는 것을 확인한 후 삭제한 subtree를 regenerates해낸다. 

 

 - 만약 reachable solution이 존재하면 complete하다. (가장 얕은 곳에 있는 goal node의 깊이가 메모리 사이즈보다 작을 경우)

- optimal solution이 reachable하면 optimal하다. 그렇지 않으면 다른 best reachable solution을 return 한다.

- 실용적인 면에서, SMA*는 최적의 solution을 찾기 위한 상당히 좋은 선택이다. 특히 state space가 graph이거나, step costs가 uniform하지 않거나, node generation할 때 드는 비용이 frontier와 explored set을 유지하는데 드는 비용보다 클 때 좋다.