- 다음 내용은 [CS-188] Introduction to Aritificial Intelligence, UC Berkeley, Fall 2018의 Readings-Note1을 정리하였음을 밝힙니다.
- 스스로 이해하기에 영문 용어가 이해하기 직관적이면 그대로 사용했습니다.
Informed Search
UCS는 complete하고 optimal하지만 시작 상태에서 목표 상태까지 '모든' 방향으로 expand하기 때문에 속도가 느리다. 이 방향을 '목표 상태'가 있는 방향으로 설정한다면 속도를 높일 수 있다. 즉, 목표 상태라는 '정보가 주어진=informed' 탐색이 가능하다.
Heuristics
"목표 상태까지 거리가 어느 정도인가?" 휴리스틱 비용 함수는 현재 상태를 input으로, 목표 상태에 대한 추정 거리를 output으로 반환한다.
이때 휴리스틱 함수는 목표 상태에 대한 거리에 대해 lower bound(즉 )하는 등 relaxed problems을 해결할 수 있다.
팩맨 문제에서 사용 가능한 대표적인 휴리스틱 비용 함수는 L1, 맨해튼 거리로 두 좌표값 사이의 절대값을 반환한다.
미로찾기 문제에서 팩맨은 동서남북으로 이동하기 때문에 현재 좌표 → 목표 상태까지의 실제 거리보다 맨해튼 거리가 무조건적으로 작기 때문에 lower bound하며, '그럴 듯한' 목표 상태에 대한 추정치를 반환하기 때문이다. 이때 맨해튼 거리 계산은 현재 상태와 목표 상태까지의 '벽' 등 팩맨 문제의 기타 요소를 제거하기 때문에 relaxed problems로 기존 문제를 설정하였다.
휴리스틱 비용 함수를 통해 agent가 '어떤 방향'으로 expand할지 수학적으로 선호도를 계산할 수 있다. 휴리스틱 비용 함수를 사용하는 대표적인 탐색 알고리즘은 다음과 같다.
L2 유클리드 거리는 팩맨 문제의 동서남북 이동 상황에서 적절하지 않은데, 대각선 이동이 가능하다면 고려할 수 있다.
1. Greedy Search
그리디 탐색은 휴리스틱 비용 함수를 통해 볼 때 "목표 상태에 가장 가까운" 방향을 택한다. 따라서 "휴리스틱 비용 함수"가 제대로 주어진다면, 속도가 매우 빠르다.
- Fringe representation: UCS와 마찬가지로 (min) 우선순위 큐를 통해 구현된다. 하지만 휴리스틱 비용 함수가 반환하는 값을 estimated forward cost로 곧바로 우선순위 큐에 넣기 때문에, 지금까지 주어진 경로 상의 총 비용을 기준으로 삼는 UCS와 계산 기준이 다르다.
- Completeness: 휴리스틱 비용 함수가 잘못되었을 경우 목표 상태에 도달할 수 없다.
- Optimality: 휴리스틱 비용 함수가 잘못되었을 경우 (답을 찾아도) optimal하지 않을 수 있다.
2. A* Search
A* 탐색 알고리즘은 UCS와 Greedy 탐색을 결합한 탐색 알고리즘으로, fringe node에서 (Greedy와 마찬가지로) lowest estimated total cost를 뽑고, 이 total cost는 (UCS에서와 마찬가지로) 현재 주어진 '그' state까지 드는 총 비용이다.
- Fringe representation: UCS, Greedy 탐색과 마찬가지로 우선순위 큐를 사용해 fringe를 구현한다. 현재 주어진 우선순위 큐의 fringe에는 UCS에서와 마찬가지로 그 '노드'까지의 총 비용이 저장되어 있고, 지금 agent는 greedy에서와 마찬가지로 그 '노드'를 택할 때의 휴리스티 비용을 가져와 더한다. 그리고 주어진 fringe 중 최저 비용인 선택을 통해 goal까지 반복한다.
- Completeness: UCS에서와 마찬가지로 complete할 수 있다.
- Optimality: UCS에서와 마찬가지로 optimal할 수 있다. 이때 Greedy 탐색처럼 빠른 속도로 경로를 반환하기 때문에 성능 역시 뛰어나다.
A 알고리즘의 completeness와 optimality는 휴리스틱 비용 함수가 어떻게 설계되었는지와 직결된다. 그 요소는 "휴리스틱 비용이 0 이상 참 비용 이하"(admissible)일 때, 그리고 "tail의 휴리스틱에서 head의 휴리스틱을 뺀 값이 실제 비용 이하"(consistent)인 경우이다. 이 두 가지 요소를 통해 A 탐색 알고리즘을 통해 얻은 solution이 optimal한지 확인할 수 있다.
