1316.35 합산 추상화 휴리스틱

1. 합산의 동기

단일 추상화 휴리스틱은 원래 문제의 일부 변수만을 고려하므로 정보성에 한계가 있다. 여러 추상화의 휴리스틱 값을 합산(additive combination)하면 더 정보적인 ��리스틱을 구성할 수 있다. 그러나 무분별한 합산은 과대 추정을 야기하여 허용 가능성을 위반할 수 있으므로, 정확한 합산 조건을 충족해야 한다.

2. 허용 가능한 합산 조건

여러 추상화 휴리스틱 $h^{\alpha_1}, h^{\alpha_2}, \ldots, h^{\alpha_m}$ 의 합산이 허용 가능하려면:

$\sum_{i=1}^{m} h^{\alpha_i}(s) \leq h^*(s) \quad \forall s \in S$

이 조건을 충족하는 주요 방법은 **비용 분할(cost partitioning)**이다.

3. 비용 분할(Cost Partitioning)

각 연산자 $o$ 의 비용 $c(o)$ 를 $m$ 개의 추상화에 분배하여, 각 추상화가 할당된 비용만으로 PDB를 계산한다:

$c(o) = \sum_{i=1}^{m} c_i(o), \quad c_i(o) \geq 0$

각 추상화 $\alpha_i$ 는 비용 함수 $c_i$ 를 사용하여 PDB를 계산하므로:

$\sum_{i=1}^{m} h^{\alpha_i}_{c_i}(s) \leq h^*(s)$

3.1 균등 비용 분할

가장 단순한 형태로, 각 연산자의 비용을 추상화 수로 균등 분할한다:

$c_i(o) = \frac{c(o)}{m}$

3.2 최적 비용 분할

선형 프로그래밍(LP)을 사용하여 합산 휴리스틱 값을 최대화하는 비용 분할을 찾는다(Pommerening et al., 2015):

$\max \sum_{i=1}^{m} h^{\alpha_i}_{c_i}(s) \quad \text{s.t.} \quad \sum_{i=1}^{m} c_i(o) \leq c(o), \quad c_i(o) \geq 0$

3.3 포화 비용 분할(Saturated Cost Partitioning)

Seipp et al.(2020)이 제안한 기법으로, 각 추상화에 “필요한 만큼만” 비용을 할당하고 나머지를 다음 추상화에 전달하는 탐욕적 방법이다:

FOR i = 1 TO m:
    saturated_cost_i ← min cost needed for h^α_i
    c_i ← saturated_cost_i
    remaining_cost ← remaining_cost - c_i

4. 합병-축소 휴리스틱(Merge-and-Shrink)

합병-축소(Helmert et al., 2007)는 변수를 합병하고 추상 상태 공간이 커지면 축소하여, 단일 추상화로 높은 정보성을 달성하는 기법이다:

MERGE_AND_SHRINK(variables):
    abstractions ← {atomic abstraction for each v ∈ variables}
    WHILE |abstractions| > 1:
        (α_1, α_2) ← SELECT_PAIR(abstractions)
        α_merged ← MERGE(α_1, α_2)
        IF |α_merged| > SIZE_LIMIT:
            α_merged ← SHRINK(α_merged, SIZE_LIMIT)
        abstractions ← (abstractions \ {α_1, α_2}) ∪ {α_merged}
    RETURN abstractions[0]

합병-축소는 PDB의 일반화로 볼 수 있으며, 축소 과정에서의 정보 손실을 최소화하는 것이 핵심이다.

5. 실용적 합산 전략

전략	허용 가능	정보성	계산 비용
단일 PDB	예	낮음~중간	낮음
가산 PDB (균등 분할)	예	중간	낮음
가산 PDB (최적 분할)	예	높음	LP 풀이 비용
포화 비용 분할	예	높음	중간
합병-축소	예	매우 높음	사전 계산 높음

6. IPC에서의 성능

합산 추상화 휴리스틱은 IPC의 비용 최적 트랙에서 최고 수준의 성능을 보인다. 특히 Scorpion 플래너(합병-축소 기반)와 Delfi 플래너(포트폴리오 기반)가 우수한 결과를 보였다.

7. 참고 문헌

Helmert, M., Haslum, P., & Hoffmann, J. (2007). “Flexible Abstraction Heuristics for Optimal Sequential Planning.” Proceedings of ICAPS, 176–183.
Pommerening, F., Röger, G., Helmert, M., & Bonet, B. (2015). “LP-Based Heuristics for Cost-Optimal Planning.” Proceedings of ICAPS, 226–234.
Seipp, J., Keller, T., & Helmert, M. (2020). “Saturated Cost Partitioning for Optimal Classical Planning.” Journal of Artificial Intelligence Research, 67, 129–167.