1316.28 FF 플래너의 아키텍처와 알고리즘

1. FF 플래너의 개요

FF(Fast Forward)는 Hoffmann과 Nebel(2001)이 개발한 전방 휴리스틱 탐색 플래너로, IPC 2000에서 우승하며 휴리스틱 탐색 플래닝의 실용성을 입증하였다. FF는 삭제 완화 기반의 $h^{\text{FF}}$ 휴리스틱, 도움 행동(helpful actions) 가지치기, 강제 산책(Enforced Hill-Climbing) 탐색 전략의 세 가지 핵심 혁신을 결합한다.

2. 아키텍처

FF의 아키텍처는 다음의 구성 요소로 이루어진다:

[PDDL 입력] → [그라운딩/전처리] → [탐색 엔진]
                                       ├── 강제 산책 (EHC)
                                       └── 가중 A* (대안)
                                  [휴리스틱 계산기]
                                       └── h^FF 휴리스틱
                                  [도움 행동 추출기]

2.1 전처리 단계

PDDL 파싱
액션 스키마의 그라운딩
도달 불가능 액션의 제거
관련성 분석에 의한 불필요한 명제 제거

2.2 휴리스틱 계산

$h^{\text{FF}}$ 는 현재 상태에서 플래닝 그래프(삭제 무시)를 확장하고, 역방향 탐욕적 추출을 통해 완화된 계획을 생성한 후, 그 비용을 휴리스틱 값으로 사용한다:

H_FF(state, goal):
    1. 삭제 무시 플래닝 그래프 확장 (state에서 시작)
    2. 모든 goal 리터럴이 그래프에 포함되면 확장 중단
    3. 역방향 탐욕적 완화 계획 추출
    4. RETURN 완화 계획의 액션 수 (또는 비용 합)

3. 강제 산책(Enforced Hill-Climbing, EHC)

FF의 기본 탐색 전략은 강제 산책이다. 현재 상태에서 $h$ 값이 감소하는 이웃 상태를 찾을 때까지 BFS를 수행하고, 찾으면 즉시 이동하는 전략이다:

EHC(s0, goal, h):
    s ← s0
    WHILE s ⊭ goal:
        s' ← IMPROVE(s, h)     ;; h 값이 감소하는 이웃 찾기
        IF s' = FAILURE:
            RETURN FAILURE       ;; 지역 최소에 빠짐 → 대안 탐색으로 전환
        s ← s'
    RETURN plan

IMPROVE(s, h):
    ;; BFS로 h 값이 감소하는 첫 번째 상태를 찾음
    queue ← applicable_actions(s)  ;; 도움 행동 우선
    visited ← {s}
    WHILE queue ≠ ∅:
        (s', path) ← DEQUEUE(queue)
        IF h(s') < h(s):
            RETURN s'
        FOR EACH applicable action a in s':
            s'' ← γ(s', a)
            IF s'' ∉ visited:
                visited ← visited ∪ {s''}
                ENQUEUE(queue, (s'', path + [a]))
    RETURN FAILURE

EHC의 특성:

그리디 탐색보다 강건: BFS를 통해 수평 이동(plateau) 가능
완전하지 않음: 지역 최소(local minimum)에 빠질 수 있음
빠른 수렴: 대부분의 벤치마크 도메인에서 매우 빠른 해 발견

4. 도움 행동(Helpful Actions)

완화된 계획에서 현재 상태의 직접 후속 액션을 추출하여, 유망한 탐색 방향을 식별한다:

$\text{HA}(s) = \{a \in \text{applicable}(s) \mid a \in \text{first\_layer}(\text{relaxed\_plan}(s))\}$

도움 행동만을 탐색 후보로 사용하면 분기 요인이 크게 줄어들어 탐색 속도가 향상된다. 그러나 완전성이 보장되지 않으므로, 도움 행동으로 해를 찾지 못하면 모든 적용 가능 액션으로 탐색을 확장한다.

5. 대안 탐색 전략

EHC가 지역 최소에 빠지면, FF는 가중 A*(Weighted A*)로 전환하여 완전한 탐색을 수행한다:

$f(s) = g(s) + w \cdot h^{\text{FF}}(s), \quad w = 5$

이 대안 탐색은 완전성을 보장하지만, EHC보다 느리다.

6. FF의 성능 특성

특성	값
완전성	EHC: 비완전, A* 대안: 완전
최적성	비보장 (만족 플래너)
시간 효율	매우 높음 (대부분의 도메인)
공간 효율	EHC: 중간, A*: 높음
PDDL 지원	STRIPS, ADL, 수치 (Metric-FF)

7. Metric-FF

Hoffmann(2003)은 FF를 수치 플루언트를 지원하도록 확장한 Metric-FF를 개발하였다. Metric-FF는 삭제 완화를 수치 변수에 확장하여, 수치 전제 조건과 수치 효과를 포함하는 도메인을 처리할 수 있다.

8. 참고 문헌

Hoffmann, J. & Nebel, B. (2001). “The FF Planning System: Fast Plan Generation Through Heuristic Search.” Journal of Artificial Intelligence Research, 14, 253–302.
Hoffmann, J. (2003). “The Metric-FF Planning System: Translating ‘Ignoring Delete Lists’ to Numeric State Variables.” Journal of Artificial Intelligence Research, 20, 291–341.
Hoffmann, J. (2005). “Where ‘Ignoring Delete Lists’ Works: Local Search Topology in Planning Benchmarks.” Journal of Artificial Intelligence Research, 24, 685–758.