• 다음 내용은 [CS-188] Introduction to Aritificial Intelligence, UC Berkeley, Fall 2018의 Readings-Note1을 정리하였음을 밝힙니다.
• 스스로 이해하기에 영문 용어가 이해하기 직관적이면 그대로 사용했습니다.

functions

휴리스틱 비용을 계산할 때 사용하는 세 가지 함수는 다음과 같다.
1. $g(n)$: UCS에서 사용되는 backward 비용
2. $h(n)$: Greedy 탐색에서 사용되는 휴리스틱 비용
3. $f(n)$: A* 탐색에서 사용되는 총 비용. 즉 $g(n)+h(n)$

Admissibility

admissible하다면, A* 트리 탐색을 할 때 optimal한 solution을 찾을 수 있다. 이때 휴리스틱 비용 $h(n)$은 0 이상 true optimal 휴리스틱 비용 이하라는 조건을 만족해야 한다. 직관적인 내용만 설명하자면 다음과 같다.

• 0 이상: 0보다 $h(n)$ 값이 작다면 올바른 "방향"으로 유도될 수 없다.
• $h(n)^*$ 이하: 목적지로 가는 "가장 올바른 방향"을 유도하는 최적의 휴리스틱 비용이다.

$h(n)^*$보다 크다면 잘못된 방향으로 유도되는 까닭에 $h(n)$은 이 값을 최대한 근사해야 한다. 가까울 수록 Greedy 탐색의 경우와 같이 탐색 속도가 빨라지겠지만, 조절을 잘 하지 못한다면 오히려 optmial한 경로를 찾지 못할 수도 있다.

Consistency

consistent하다면, A* 그래프 탐색을 할 때 optimal한 solution을 찾을 수 있다. 대개 consistent한 조건이 admissbile보다 더 강력한 제약 조건이다. adimissible이 휴리스틱 비용 #h(n)#에 주목했다면 consistent는 그 노드로 가는 비용 역시 주목하기 때문이다. 연결된 두 노드가 있을 때 각 노드에 대한 휴리스틱 비용의 차가 실제 비용보다 작거나 같아야 한다. 즉 두 노드를 건너는 실제 비용보다 추정한 휴리스틱 값의 차이가 '작아서는' 올바른 방향을 유도될 수 없다는 뜻이다.

• ${\forall}A,C\,\,\,\,h(A)-h(C)\leq cost(A,C)$

이 특징을 통해 노드 $n$과 그 successor 노드 $n'$의 비용을 비교해볼 수 있다.
$f(n')=g(n')+h(n')=g(n)+cost(n,n')+h(n')\geq g(n)+h(n)= f(n)$

admissible하다면 A '트리'에서, consistent하다면 A '그래프' 탐색에서 optimal한 경로를 찾을 수 있다.

Dominance

A* 탐색 알고리즘은 곧 $h(n)$과 $g(n)$을 계산하는 것이다. 그렇기 때문에 과연 지금 사용하고 있는 휴리스틱 비용 함수가 admissible한지, consistent한지 확인하는 게 관건이다. 이를 위해 dominance라는 판단 기준이 있다.

• 모든 상태 공간의 노드에서 휴리스틱 a가 휴리스틱 b보다 추정된 목표와의 거리가 더 크다면 휴리스틱 a가 dominant하다.

이 dominant하다는 뜻은 그렇기 때문에 "어떤 휴리스틱이 더 좋은지" 판단하는 간단한 근거가 된다. 물론 비교되는 휴리스틱 $h(n)$는 admissible한 조건인 $h(n)^*$ 이하라는 제약 조건을 지키고 있어야 한다. 이를 가정할 때 더 큰 max 값을 통해 dominant한 휴리스틱 비용을 찾는다면, "가장 빠르게" 주어진 조건에서 optimal한 경로를 계산할 수 있다.