3 분 소요

이전 내용에서 greedy한 휴리스틱은 optimal하지도, complete하지도 않다는 것을 보았다. 그렇다면 어떤 휴리스틱이 있어야 Informed Search가 optimal, 그리고 complete해질까? 이번 시간에는 A* search를 토대로 admissible한 heuristics가 무엇인지 다뤄본다.

A* Search(에이스타 탐색)

좋은 ‘탐색 휴리스틱’은 현재 상태 X가 목표 G에 얼마나 가까지 있는지를 나타낸다. 팩맨의 경우 맨하튼 거리나 유클리드 거리 등이 있었다. 그런데 이 휴리스틱들의 성능은 어떻게 비교할 수 있을까? 그리고 어떤 휴리스틱이 더 좋은 휴리스틱일까?

앞선 Arad-Bucharest 예제를 보며 우리는 거리 휴리스틱 h(x)뿐만 아니라 각 경로에서의 cost도 고려해야함을 몸소 느꼈다. 이제부터 다룰 A* Search는 실제 비용(actual cost)과 휴리스틱 비용(heuristic cost)의 총합 f(n)을 우선순위 큐에 할당한다.

실제 경로의 비용 g(n)은 이동할 수록 쌓여가는 cumulative한 성질이 있다. 얼마나 우리가 소모했는지(how much have we spent?)에 대한 기준으로서, backward cost라고도 불린다.

반면 떨어진 거리에 대한 휴리스틱 비용 h(n)은 정확하지는 않은 추정치(estimated)이며 이동할 수록 작아지게 된다. 또한 우리가 얼마나 소비할지(how much will we spend?)를 고려하므로 forward cost라고도 불린다.

따라서 이 둘의 합 \(f(n):=g(n)+h(n)\)을 새로운 기준으로 사용하는 A* Search는 half-estimated하다고 할 수 있다. Arad-Bucharest 예제를 보면 A* Search가 f(n)이 최소인 곳부터 탐색하면서 가장 최적의 코스(s-a-d-G)를 바로 찾아내는 것을 확인할 수 있다. 그런데 문제는, 이게 항상 most efficient한(가장 효율적인) 방법일까?

13페이지의 예제에서는 실제 비용이 가장 적은 경로는 S-A-G의 4임에도, f(n)이 더 작은 값을 가지는 S-A로 이동하게 된다. 이 때문에 4로 갈 수 있는 경로를 7로 가버리는 상황이 발생했다. 따라서 우리는 A* Search에서 \(f(n):=g(n)+h(n)\)보다 더 적절한 휴리스틱을 찾아야 한다.

Admissible한 휴리스틱을 찾아서

admit

motivation은 다음과 같다. 각 스텝 N_i와 N_j에서의 누적된 실제 cost값이 검정색의 g(n) 그래프를 따른다고 하자. 이때 optimal한 경로의 실제 cost가 G*라고 한다면, G 스타에서 g(n)까지의 gap 사이보다 더 작은 값의 휴리스틱은 결국 optimal한 경로가 될 것이다.

반대로 나쁜 휴리스틱이라면 해당 gap보다 더 큰 값을 가져서, 13페이지의 단순한 예제처럼 optimal하지 않은 경로로 Agent를 이끌게 된다. 따라서 실제 cost보다 더 작거나 같은 휴리스틱 cost를 가지는 휴리스틱을 채택하여야 한다.

바꿔 말하자면 경로 상의 cost를 절대 과대평가하면 안된다(never over-estimates). 최적의 goal까지의 남은 실제 cost를 h*(n)이라 하면, 올바른 휴리스틱 값 h(n)은

\[0\le h(n)\le h^*(n)\]

이어야 한다. 이러한 휴리스틱을 Admissible하다고 표현한다! admissible한 휴리스틱을 찾으면, A* search를 통해 optimal한 solution을 찾을 수 있다!

증명: Admissible한 휴리스틱이 적용된 A*는 정말 optimal한가?

가정이 좀 많이 필요하다. A스타 트리의 노드 중 가장 optimal한 골을 A, suboptimal한 골을 B라 하고, admissible한 휴리스틱 h를 채택했다고 하자. A의 조상(ancestor)인 노드 n과 suboptimal한 노드 B가 현재 fringe에 있고, 아직 A는 fringe에 포함되지 않았다고 하자. 노드 n이 노드 B보다 먼저 탐색된다고 가정하면, 다음 3가지를 입증하여 A*의 optimal함을 증명한다.

첫째: \(f(n)<=f(A)\)를 입증한다. 이건 노드 A가 optimal하기에 h(A)=0으로 계산되고, h는 admissible한 휴리스틱이므로 그 정의에 따라 h(n)<=(actual cost from n to A)이므로 쉽게 입증된다. 자세한 건 필기본 참조

둘째: \(f(A)<=f(B)\)를 입증한다. 노드 A와 B는 각각 optimal, suboptimal하고 휴리스틱은 절대 overestimate하지 않으므로, h(A)=h(B)=0이 된다. 따라서 g(A)와 g(B)를 비교하면 되는데 B는 suboptimal하기에 g(A)<g(B)에서 입증이 된다.

셋째: \(f(N)<=f(A)<=f(B)\)를 입증한다. 삼단논법에 따라서 자명하게 입증된다. 이 뜻은 우선순위 큐에서 노드 n -> 노드 A -> 노드 B 순으로 탐색이 될 것이라는 것이다.

따라서 A보다도 f값이 작은 A의 모든 조상 노드들은 A보다 먼저 탐색될 것이고, 그 다음에 A가 탐색될 것이다. 따라서 B보다 A가 먼저 탐색되므로, 우리는 모든 suboptimal한 goal들을 제쳐두고 항상 optimal한 goal을 먼저 찾을 수 있다!

A*의 특성

Uninformed Search에서 가장 나았던 UCS는 오직 actual cost만 사용하고, Informed Search의 일종인 Greedy한 Heuristic Search는 오직 heuristic cost만을 사용했다. 에이스타 탐색은 이 둘을 모두 사용해 \(f=g+h\)라는 새로운 휴리스틱을 발견했다는 점이 특징이다.

이러한 A* Search는 탐색 범위를 좁혀나가려고 한다는 특성이 있다. admissible한 휴리스틱 덕분에 모든 노드를 탐색하는 UCS나 탐색할 뻔한 Greedy heuristic과는 달리, optimal함을 보증할 수 있다.

시간, 공간 복잡도는 지수형(exponential)이지만, 완전하고(complete) 최적이다(optimal). 모든 방향을 균일하게 도는 UCS와 달리, 점점 올바른 경로로 guided된다는 특성 또한 있다(자세한 그림은 필기본 참조)

Admissible한 휴리스틱은 어디에?

근데 그래서 결론적으로 admissible한 휴리스틱을 어떻게 찾을것인가?에 대한 해답을 찾지 못했다. 아니 admissible한 휴리스틱이면 optimal하다는 것도 알겠고, 그 휴리스틱을 고안해내는 것이 탐색 문제의 핵심이자 가장 시간이 오래 걸리는 작업이라는 것도 알겠는데, 그래서 그게 어디있다는 건데?

해답은 조건을 유연하게 바꿔서 휴리스틱을 찾는 것이다. 이를 relaxed problem이라 표현한다. 자세한 예제는 필기본의 Andrew Moore’s 8 Puzzle을 참고하자.

핵심은 덜 유한 조건(less relaxed problem)에서의 admissible한 휴리스틱이 더 정확하고, 탐색하는 노드의 수도 줄어들지만, 더 많은 계산량이 필요하여 시간이 더 걸리게 된다는 것이다.

출처: 인공지능(COSE361) ㅇㅅㅅ 교수님

참고