1316.27 가산 휴리스틱과 최대 휴리스틱

1. 삭제 완화에서의 두 집계 방법

삭제 완화 기반 휴리스틱에서 개별 목표 리터럴의 달성 비용을 집계(aggregate)하는 두 가지 대표적 방법이 가산 휴리스틱( $h^{\text{add}}$ )과 최대 휴리스틱( $h^{\text{max}}$ )이다. 두 휴리스틱은 동일한 개별 비용 계산을 공유하지만, 집계 함수에서 근본적으로 다르다(Bonet & Geffner, 2001).

2. 개별 리터럴 비용 계산

두 휴리스틱 모두 각 명제(리터럴) $p$ 의 달성 비용 $\text{cost}(p, s)$ 를 다음의 재귀적 정의로 계산한다:

$\text{cost}(p, s) = \begin{cases} 0 & \text{if } p \in s \\ \min_{a: p \in \text{eff}^+(a)} \left[ \text{cost}(\text{pre}(a), s) + c(a) \right] & \text{otherwise} \end{cases}$

차이는 전제 조건 집합의 비용 $\text{cost}(\text{pre}(a), s)$ 를 어떻게 집계하느냐에 있다.

3. 가산 휴리스틱( $h^{\text{add}}$ )

3.1 정의

전제 조건의 비용을 합산한다:

$\text{cost}^{\text{add}}(\{p_1, \ldots, p_n\}, s) = \sum_{i=1}^n \text{cost}^{\text{add}}(p_i, s)$

$h^{\text{add}}(s) = \text{cost}^{\text{add}}(\text{goal}, s) = \sum_{g \in \text{goal}} \text{cost}^{\text{add}}(g, s)$

3.2 특성

비허용 가능: 목표 리터럴 간의 양의 상호작용(한 액션이 여러 목표를 동시에 달성)을 무시하므로 과대 추정할 수 있다.
정보적: 비허용 가능하지만, 목표까지의 거리를 비교적 정확하게 추정하여 탐색을 효과적으로 유도한다.
빠른 계산: $O(\lvert\mathcal{A}\rvert \cdot \lvert\mathcal{F}\rvert)$ 의 고정점 계산으로 효율적으로 산출된다.

3.3 예시

목표: $\{A, B\}$ , 각 달성 비용: $\text{cost}(A) = 3$ , $\text{cost}(B) = 2$
$h^{\text{add}} = 3 + 2 = 5$

만약 단일 액션이 $A$ 와 $B$ 를 동시에 달성한다면, 실제 비용은 3이지만 $h^{\text{add}}$ 는 5로 과대 추정한다.

4. 최대 휴리스틱( $h^{\text{max}}$ )

4.1 정의

전제 조건의 비용 중 최대값을 선택한다:

$\text{cost}^{\max}(\{p_1, \ldots, p_n\}, s) = \max_{i \in \{1,\ldots,n\}} \text{cost}^{\max}(p_i, s)$

$h^{\max}(s) = \text{cost}^{\max}(\text{goal}, s) = \max_{g \in \text{goal}} \text{cost}^{\max}(g, s)$

4.2 특성

허용 가능(Admissible): 절대 과대 추정하지 않으므로, A*와 결합하면 비용 최적 계획을 보장한다.
비정보적: 가장 비용이 큰 단일 목표의 비용만 반영하므로, 다른 목표의 달성 비용이 무시된다.
빠른 계산: $h^{\text{add}}$ 와 동일한 복잡도.

4.3 예시

목표: $\{A, B\}$ , 각 달성 비용: $\text{cost}(A) = 3$ , $\text{cost}(B) = 2$
$h^{\max} = \max(3, 2) = 3$

실제 비용이 5(A와 B를 별도로 달성해야 하는 경우)라면 $h^{\max}$ 는 3으로 과소 추정한다.

5. 두 휴리스틱의 관계

항상 다음의 부등식이 성립한다:

$h^{\max}(s) \leq h^*(s) \leq h^{\text{add}}(s) \quad \text{(일반적으로는 아님)}$

정확히는:
$h^{\max}(s) \leq h^{+*}(s) \leq h^{\text{add}}(s)$

여기서 $h^{+*}(s)$ 는 삭제 완화 문제의 최적 비용이다. $h^{\max}$ 는 $h^{+*}$ 의 하한, $h^{\text{add}}$ 는 $h^{+*}$ 의 상한이다.

6. 비교 요약

특성	$h^{\text{add}}$	$h^{\text{max}}$
집계 함수	합(sum)	최대(max)
허용 가능	아니오	예
정보성	높음	낮음
과대/과소 추정	과대 경향	과소 경향
A* 최적성	비보장	보장
만족 플래닝	효과적	덜 효과적
비용 최적 플래닝	부적합	기본 선택

7. 실용적 선택 지침

만족 플래닝(빠른 해 찾기): $h^{\text{add}}$ 또는 $h^{\text{FF}}$ 사용. 비허용 가능하지만 정보적이어서 탐색을 효과적으로 유도.
비용 최적 플래닝: $h^{\text{max}}$ 또는 더 정보적인 허용 가능 휴리스틱( $h^{\text{LM-cut}}$ , $h^{\text{M\&S}}$ ) 사용.
하이브리드 접근: 만족 플래닝으로 초기 해를 빠르게 찾고, 비용 최적 플래닝으로 개선하는 반복적 접근(LAMA 등).

8. 참고 문헌

Bonet, B. & Geffner, H. (2001). “Planning as Heuristic Search.” Artificial Intelligence, 129(1–2), 5–33.
Hoffmann, J. & Nebel, B. (2001). “The FF Planning System.” Journal of Artificial Intelligence Research, 14, 253–302.
Haslum, P. & Geffner, H. (2000). “Admissible Heuristics for Optimal Planning.” Proceedings of AIPS, 140–149.