1316.26 완화 문제 기반 휴리스틱 설계

1. 완화의 개념

완화(relaxation)는 원래 플래닝 문제의 일부 제약을 무시하여 단순화한 문제를 생성하고, 이 단순화된 문제의 해를 원래 문제의 휴리스틱으로 사용하는 기법이다. 완화 문제의 최적 비용은 원래 문제의 최적 비용보다 작거나 같으므로, 허용 가능(admissible) 또는 비허용 가능 휴리스틱의 기초가 된다.

2. 삭제 완화(Delete Relaxation)

가장 널리 사용되는 완화 기법으로, 모든 액션의 삭제 효과(negative effects)를 무시한다(Hoffmann & Nebel, 2001):

$a^+ = \langle \text{pre}(a), \text{eff}^+(a), \emptyset \rangle$

삭제 완화 문제에서는 한번 참이 된 명제가 이후에도 영원히 참으로 유지되므로, 상태가 단조적으로 확장된다. 이에 따라:

상태 공간이 단조적이어서 탐색이 단순화된다
최적 완화 계획의 비용 계산이 효율적이다
완화 비용이 원래 비용의 하한을 제공한다

2.1 삭제 완화의 한계

삭제 효과를 무시함으로써 원래 문제의 핵심 구조가 손실될 수 있다:

위치 변경 시 이전 위치의 삭제가 무시되어, 로봇이 모든 위치에 동시에 있는 것으로 간주
자원 소모가 무시되어, 무한한 자원이 있는 것으로 간주

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

각 목표 리터럴의 달성 비용을 독립적으로 계산하고 합산한다:

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

여기서 $\text{cost}^+(g, s)$ 는 상태 $s$ 에서 리터럴 $g$ 를 삭제 완화 문제에서 달성하는 최소 비용이다. 이 비용은 고정점 계산으로 효율적으로 산출된다.

$h^{\text{add}}$ 는 비허용 가능하다(과대 추정 가능). 목표 리터럴 간의 양의 상호작용(한 액션이 여러 목표를 동시에 달성)을 무시하기 때문이다.

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

목표 리터럴 중 달성 비용이 가장 큰 것을 선택한다:

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

$h^{\text{max}}$ 는 허용 가능하다. 그러나 목표 리터럴 간의 독립적 달성을 가정하므로 정보성이 낮다(과소 추정 경향).

5. FF 휴리스틱( $h^{\text{FF}}$ )

Hoffmann과 Nebel(2001)이 제안한 $h^{\text{FF}}$ 는 삭제 완화 문제의 최적 비용이 아닌, 플래닝 그래프에서 탐욕적으로 추출한 완화 계획의 비용을 사용한다:

현재 상태에서 플래닝 그래프(삭제 무시)를 확장한다
목표 계층에서 역방향으로 탐욕적 완화 계획을 추출한다
추출된 계획의 액션 수(또는 비용 합)가 $h^{\text{FF}}$ 이다

$h^{\text{FF}}$ 는 비허용 가능하지만, $h^{\text{add}}$ 보다 정확한 추정을 제공하는 경우가 많다.

6. 비용 계산의 고정점 알고리즘

COMPUTE_HEURISTIC(state, goal):
    ;; 각 리터럴의 달성 비용을 초기화
    FOR EACH literal p:
        IF p ∈ state: cost[p] ← 0
        ELSE: cost[p] ← ∞

    ;; 고정점까지 반복
    REPEAT:
        changed ← FALSE
        FOR EACH action a:
            ;; 전제 조건 비용 계산
            pre_cost ← aggregate(cost[p] for p ∈ pre(a))
            ;; aggregate: h_add는 SUM, h_max는 MAX
            IF pre_cost < ∞:
                FOR EACH p ∈ eff+(a):
                    new_cost ← pre_cost + action_cost(a)
                    IF new_cost < cost[p]:
                        cost[p] ← new_cost
                        changed ← TRUE
    UNTIL NOT changed

    ;; 목표 비용 집계
    RETURN aggregate(cost[g] for g ∈ goal)

7. 완화 휴리스틱의 비교

특성	$h^{\text{add}}$	$h^{\text{max}}$	$h^{\text{FF}}$
계산 비용	$O(\lvert\mathcal{A}\rvert \cdot \lvert\mathcal{F}\rvert)$	$O(\lvert\mathcal{A}\rvert \cdot \lvert\mathcal{F}\rvert)$	$O(\lvert\mathcal{A}\rvert \cdot \lvert\mathcal{F}\rvert \cdot \lvert g\rvert)$
정보성	중간~높음	낮음	높음
허용 가능	아니오	예	아니오
과대/과소 추정	과대 경향	과소 경향	균형적
주요 용도	만족 플래닝	비용 최적 플래닝	만족 플래닝

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: Fast Plan Generation Through Heuristic Search.” Journal of Artificial Intelligence Research, 14, 253–302.
Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.