[AI] 2. Informed Search (Heuristics, Greedy, A*)

 Informed Search 라는 것은 현재 State에서 Goal state로 가기 위한 정보(Heuristics)가 주어진 문제를 말한다. 즉, 지금 상태에서 다음으로는 어느 state로 가야 Goal에 더 빠르게 근접할 수 있는지에 대한 Hint가 주어진 문제라고 할 수 있다.

Heuristics

Heuristic은 Goal에 얼마나 가까워 질 수 있는지에 '대략적으로 추정할 수 있는' 정보 혹은 함수이다. 물론 Heuristic 값이 실제 값에 가까울 수록 더 좋지만 대략적인 정보가 주어진 것 만으로도 Goal state를 찾아가는데 큰 도움을 받을 수 있다. 아래 두가지 예제를 보자.

Packman이 도달해야할 Goal state를 그림속 흰 점이라고 가정하자. Packman이 실제로 Goal state로 가기위해서는 미로를 해쳐나가야 하지만 빨간선과 같이 Goal state가 좌측 하단에 있다는 정보를 알고 있다면 Packman은 가급적 좌측 하단으로 이동하려고 할 것이다. 

(위 예제에서는 11.2 혹은 15가 Heuristic 값이 된다. 참고로 10+15와 같은 거리를 Manhattan distance, 11.2와 같은 직선 거리를 Airline distance라 부르며 대표적인 Heuristic 값으로 쓰인다.)

 

또 다른 예로 Goal State가 Bucharest 인 길찾기 문제를 들 수 있다.

예를 들어 Arad에서 Bucharest로 가는 최단 경로를 찾고 싶다면, Bucharest와 가장 가까운 선택지를 골라서 이동하면 Global solution은 아닐지라도 어느정도 빠른 길을 찾을 수 있다. (본 예제에서 우측 Heuristics를 이용한다면 Arad - Sibiu - Fagaras - Bucharest 순으로 이동하게 된다.)

Greedy Algorithm

Greedy 알고리즘을 직역하면 '욕심쟁이' 혹은 '탐욕' 알고리즘으로, 먼 미래를 고민하는 것이 아니라 당장 눈 앞의 문제를 해결하기 위해 최적의 선택을 하려는 알고리즘이다. Greedy 알고리즘이 최적의 선택을 하기 위한 기준에 Heuristics이 주로 활용하면 앞서 설명하였든 Global solution은 아닐지라도 대략 쓸만한 결과를 도출할 수 있다.

UCS vs. Greedy 

UCS는 Start state에서 Next state까지의 cost를 기준으로 가장 작은 cost를 선택한다.

반면 Greedy는 현재 state에서 goal state까지의 heuristic 값이 작은 state를 선택한다.

위 특징을 따르면, UCS는 시간은 오래 걸리더라도 Global solution을 찾을 수 있고,

Greedy 알고리즘은 그럭저럭 쓸만한 solution을 빠르게 찾을 수 있는 장점이 있다.

A* Search

A* search는 Greedy 알고리즘의 장점과 UCS의 장점을 모두 취한 알고리즘이다.

말로 풀면, 지나온 길도 고려하면서 Goal과의 거리도 함께 고려한다고 표현할 수 있다.

아래 예제를 보면 더욱 직관적으로 이해할 수 있다.

 1) Greedy search

   : Greedy search는 heuristic 값이 가장 적은 것을 선택한다. 따라서 (a)state 다음에 (G)와 가장 가까운 (e) state를 선택하게 되는데 이 경로는 최적의 경로는 아니다.

 2) Uniform Cost Search

   : 반면 UCS search은 이전의 경로까지 고려해서 next state까지의 거리가 가장 짧은 루트를 선택한다. 따라서 (a) state 다음에는 (b), (c)state를 선택했다가 (d)를 선택하며 이 역시도 최적의 경로는 아니다

 3) A* Search

   : A* 알고리즘은 UCS의 cost와 (위 그림에서는 g) Heuristics (위 그림에서는 h)의 합을 기준으로 g+h가 가장 낮은 것을 택하여 next state를 결정한다. 위 예제에서는 (a) state 다음에 g+h 가 6으로 가장 큰 (d)노드를 선택함으로써 빠르게 Global solution을 찾을 수 있게 된다.

그럼 A* 알고리즘은 언제 종료되어야 하는가? UCS의 경우 가장 먼저 Goal state가 pop(dequeue)되면 종료되었지만 아래 예제를 보면 A* search는 그렇지 않다.

실제로 위 상황에서 Start state 다음에는 g+h가 3인 B가 선택될 것이다. 하지만 이는 Global solution이 아니기 때문에 (G)를 pop 하고 끝내면 안된다. 사실 (G) state를 Goal이 아니라 하나의 state로 본다면 g(5)+h(0)는 5의 값을 갖는다. 반면 (A) state는 g(2) + h(2)로 4의 값을 갖기 때문에 (A) state를 expend 하고 난 뒤에 (G) state나 assign되어야 global solution으로 자리잡게 된다. 

다시 말해 UCS처럼 Goal state가 expend 됐다고 멈추는 것이 아니라 남아 있는 fringe의 g+h값을 살펴보고 더이상 expend 할 state가 없을 때 종료하게 된다.

Admissibility

그런데 A* Search는 항상 Optimal solution을 낼 수 있을까? 

위 예제에서 A* Search는 g+h가 7인 (A)를 선택하지 않고 (G)를 선택할 것이다. 하지만 (S→G)는 Optimal solution이 아니다. 원인은 h=6으로 estimate된 Heuristic 값에 있다. 실제로 (A→G)의 거리는 3이지만 Heuristic은 6으로, 즉 매우 비관적으로 설정되었기 때문에 Optimal solution을 찾지 못한 것이다.

따라서 Estimate(Heuristic)은 Actual cost와 최소한 작아야 한다는 가정 충족되어야 Optimal solution을 도출할 수 있고 이러한 성질을 Admissibility라 한다.

Graph Search

지금까지 학습한 Search 알고리즘 (DFS, BFS, UCS, Iterative Deeping, Greedy, A* 등)은 State space를 Tree로 두고 문제를 해결했다. 하지만 Graph search 알고리즘을 활용하면 불필요한 연산을 줄일 수 있다.

위 Tree는 어느 Graph를 Tree로 표현한 것이다. 위 그림을 보면 같은 노드를 여러번 생성하고 있음을 알 수 있다. 한번 나온 노드를 다시 연산하지 않으면 더 효율적이다는 Idea에서 나온 것이 Graph Search 이다. 

Graph Search의 원리는 크게 어렵지 않다. 기존의 Tree Search 알고리즘의 Rule을 따르되, 이미 방문한 node를 기억해 뒀다가 (closed-set) 방문한 node라면 expend 하지 않으면서 Tree search를 수행하는 것이다.

그런데 A* Graph Search는 Admissible 한 Heuristic이 보장된다 하더라도 Optimal 하지 않을 수 있다.

Consistency

위 예제를 보면, Heuristic 값은 모두 Admissible 하다. 

Search tree의 경우 처음에는 S - B - C - G로 갔지만 바로 종료되지 않고 A를 expend했다가 결국은 solution을 찾을 것이다.

하지만 좌측의 Graph의 경우, 마찬가지로 S - B - C - G로 이동할텐데, 4개 state가 closed-set에 저장되었기 때문에 다시 돌아가지 못하고 강제 종료하게 된다. 이 문제의 원인은 Heuristic value에 있다.

초기에는 A의 Heuristic 값이 4였는데, 이 값이 지나치게 크게 잡혀있었기 때문에 문제해결이 어려웠고, Graph search가 성공하기 위해서는 Admissibility 보다 엄격한 조건이 필요하다. 그 조건이 바로 Consistency이다.

다시 말하면, Heuristic 값은 현재 state에서 다음 state까지 가는 cost와 다음 state의 Heuristic 값의 합보다 작아야 Graph search가 동작할 수 있고 이 조건을 Consistency라 한다.