인공지능개론 | Informed Search

⚠ Before reading the post ⚠

본 포스팅은 컴퓨터 공학 계열 전공자 대학교 4학년에서 대학원생 기준으로 작성하였습니다.
기본적인 자료구조나 알고리즘 내용은 생략하였습니다.

Informed Search | 정보가 있는 검색 전략 - Heuristic Search

지난 시간에 다룬 Uninformed Search는 아래 실세계 문제를 풀기에 한계점을 지니고 있다.
간단히 설명하면 8puzzle 문제는 각 숫자 블록을 오로지 상하좌우로 움직임으로써 오름차순으로 숫자를 정렬하는 것이 목표인 문제다. 이 때 제한 조건(constraint)은 블록이 순간이동하거나 후퇴를 하지 않아야한다는 것.

Branch factor(b): 2~4 → state 별 움직일 수 있는 가지수, 평균은 3
least solution depth(d): 22 steps

이 문제를 지난 포스팅에서 다뤘던 IDS(Iterative Depth Search)로 탐색하게 되면, 상태를 저장하게 될 메모리 공간은 $O(b^d) = 3^{22}$ 가 된다. Exponential하다는 단점이 있다보니 8-puzzle이 아닌 24-puzzle인 경우 훨씬 많은 공간들을 저장해야해서 매우 치명적이다.

전 포스팅에서 다룬 알고리즘과 다르게 이번에는 Agent에 네비게이션을 달아주는 검색 전략이다. 즉, 상태에 대한 전도유망함을 heuristic function을 통해서 최적의 경로를 찾게 된다.

정보가 있는 검색 전략은 크게 두 가지로 나뉘게 된다.

Heuristic Search
Local Search

두 가지의 차이점은 Fringe의 유무인데, Local Search는 현 상태에서 이익을 포커스로 두고 있기 때문에 해가 최소 경로를 통해 도달한 것이 아닐 수 있다. (Local Search는 다음 포스팅에서!)

Best First Search | 최선 우선 검색

가장 일반적인 방법이며 평가함수 $f(n) = min(node)$ 을 토대로 goal node를 찾아가게 된다.
비슷한 방법으로는 아래와 같다.

Uniform Cost Search: $g(n)$ → 우선순위가 큰 것부터 적용, 탐색 공간 확장하는 순간 정확한 node 값을 알 수 있다.
Greedy Best-First Search: $h(n)$ → 아래에서 다루게 될 텐데, heuristic function 즉, 전도유망한지 여부로 상태를 평가하게 된다.

Greedy Best First Search | 탐욕적 최우선 검색

들어가기 앞서, Heuristic function에 대해 짚고 넘어가자!

Heuristic function

정답에 근사하기 위해 유용한 정보(goal state까지의 optimal cost 예측 정보)를 제공하는 함수이다. 공식적인 함수가 아니므로 항상 정확하다고 보장할 수 없다. 위에서 다룬 문제를 Best First Search로 푼다고 가정했을 때 heursitic funciton 아래와 같이 정의될 수 있다. 장애물이 없을 때 가정하면 실제로 움직이는 횟수보다 작거나 같다.

$h_1 = n(misplaced)$ : 원 위치가 아닌 타일들
$h_2 = sum(current.pos - goal.pos)$ → manhattan distance

Notion of Dominance

그렇다면 위 8-puzzle에서 $h_2(n)>h_1(n)$ 이라면 $h_2(n)$ 가 우위에 있다고 볼 수 있으며 평균적으로 depth에 따라서 성능이 더 좋은 것이 더 두드러진다.

Greedy best first search에서 다룰 heuristic function은 목표에 근사한 노드들을 확장하기 하며, 현 상태에서 눈앞에 보이는 이득을 먼저 취하기 때문에 장기적으로는 좋지 않은 결과를 낳을 수 있다. 아래 예제와 함께 보자.

후보 노드들을 저장하는 fringe는 min heap*, Arad 부터 Bucharest까지 도착하는 문제인데, 도착시 직선 거리(Straight Line Distance)가 heurstic을 결정한다고 했을 때, function value(goal state까지 남은 거리)가 0인 것, $h(n) = 0$ 일 때 goal node에 도착했음을 확인할 수 있다.

Completeness & Optimality: NO

당장의 이익만 보고 노드를 확장시키므로, 방문 정보를 받지 않게 되면 무한 루프에 빠질 수가 있다.
이미지에서 볼 수 있듯, 빨간색으로 표시된 경로 또한 최소 경로가 아니므로 d도 보장이 되지 않는 solution이다.

Time and Space Complexity
- Time Complexity: $O(b^m)$
- Space Complexity: $O(b^m)$ or $O(bm)$

A* Search | A* 검색

위 평가 함수였던 $h(n)$ 을 확장시켜서 uniform cost function에서 사용되었던 $g(n)$ , 현재까지의 거리를 저장하는 함수를 합하여 아래와 같이 evaluation function을 세울 수 있다.

$f(n)=g(n)+h(n)$

한마디로 UFS + GBFS 가 합쳐진 형태로 보면 이해하기 쉽다.
아래 예제와 함께 보자.

Time and Space complexity: exponential
Completeness & Optimality: YES

현재까지 거리를 고려하여 least solution을 보장(d 존재)하므로 complete하고 optimal하다고 볼 수 있다.
여기서 왜 complete할까! 라고 궁금증이 생길 수 있는데, 아래 Heurstic 특성 때문이다.

Admissible heurstics (허용 가능 발견적 함수)

$h(n) \leq h^*(n)$

모든 경우 확장시, 모든 n에서 실제 goal 까지의 거리인 $h^\ast(n)$ 보다 작아야 하므로 optimality가 보장된다고 할 수 있다. 이를 반영하면 $h_{SLD}(n)$ 는 overestimate하지 않으므로 adimissible 하다. (Goal state에서 최소 거리는 직선거리이므로).
다시 결론을 짓자면, Heurstic function이 허용가능(adimissible)하면 A* 탐색은 optimal 하다.

Consistency (일관성)

일관성 보장은 수업에서 다루지는 않았지만 현재 heurstic value는 현상태에서 자식 위치와 자식 위치에서 goal 까지의 거리의 합보다 항상 작다는 일관성을 지니고 있다.
자세한 내용은 아래 걸어둔 링크에서 확인하면 좋을 것 같다.

Relaxed problem

다시 8-puzzle로 돌아와서 constraint를 완화함으로써 더 많은 상태 공간에서 노드들을 확장할 수 있다. 각각 $h_1(n)$ , $h_2(n)$ 를 완화하면 아래와 같이 나타날 수 있다.

$h_1(n)$ : 아무 곳이나 순간 이동이 가능하며 least solution이다.
$h_2(n)$ : tile과 겹칠 수 있으며 least solution이다.

제약 조건이 완화되었음에도 더 나은 해를 간혹 발견할 수 있는데, 이 때 relaxed problem에서 optimal value를 찾는 heuristic funciton은 곧 원래 문제에 대한 adimissible heurstic function이다.

Wrap up & Conclusion

이번 수업에서 조금 모호한 부분들이 있어서 서적이랑 인터넷을 많이 뒤져본 것 같다.
해당 내용 관련 글을 더 보고 싶다면, 컴공계에서 스타분이신 동빈님의 블로그글을 매우 유용하게 보아서 아래 링크 남기고 마무리한다!

안경잡이개발자 Naver Blog: Informed Search