1316.25 휴리스틱 탐색 플래너의 발전

1. ��리스틱 탐색 플래닝의 등장

휴리스틱 탐색 플래닝(heuristic search planning)은 1990년대 후반에 등장하여 현대 고전적 플래닝의 지배적 패러다임이 된 접근법이다. 핵심 아이디어는 전방 상태 공간 탐색에 도메인 독립적(domain-independent) 휴리스틱을 결합하여, 목표를 향한 유망한 방향으로 탐색을 유도하는 것이다.

2. 역사적 발전 과정

2.1 단계: HSP (1998)

HSP(Heuristic Search Planner)는 Bonet과 Geffner(1998, 2001)가 제안한 최초의 본격적 휴리스틱 탐색 플래너이다. 삭제 완화(delete relaxation)에 기반한 가산 휴리스틱( $h^{\text{add}}$ )과 최대 휴리스틱( $h^{\text{max}}$ )을 도입하였다. HSP는 전방 최선 우선 탐색(greedy best-first search)을 사용하여 당시의 최고 수준 성능을 달성하였다.

2.2 단계: FF (2001)

FF(Fast Forward) 플래너는 Hoffmann과 Nebel(2001)이 개발하였으며, 플래닝 그래프에서 완화된 계획(relaxed plan)을 추출하여 $h^{\text{FF}}$ 휴리스틱을 계산한다. FF의 핵심 혁신:

$h^{\text{FF}}$ 휴리스틱: 삭제 효과를 무시한 완화 문제의 계획 비용을 추정
도움 행동(Helpful Actions): 완화된 계획에 포함된 액션만을 탐색 후보로 제한
강제 산책(Enforced Hill-Climbing): 그리디 탐색과 BFS의 결합

FF는 IPC 2000에서 우승하며 휴리스틱 탐색 플래닝의 실용성을 입증하였다.

2.3 단계: Fast Downward (2004, 2006)

Helmert(2006)가 개발한 Fast Downward는 PDDL에서 SAS+(유한 도메인 변수) 표현으로의 번역(translation), 인과 그래프(causal graph) 기반 분석, 다양한 휴리스틱(인과 그래프, 합병-축소, 랜드마크 컷)을 지원하는 모듈화된 플래닝 시스템이다. Fast Downward의 핵심 혁신:

SAS+ 표현: 다치 변수(multi-valued variable) 기반의 간결한 상태 표현
다중 휴리스틱 지원: 여러 휴리스틱을 조합하여 탐색을 유도
모듈화된 아키텍처: 번역기, 전처리기, 탐색기의 분리된 모듈

2.4 단계: LAMA (2008, 2010)

Richter와 Westphal(2010)이 개발한 LAMA는 Fast Downward를 기반으로 랜드마크 휴리스틱과 FF 휴리스틱을 결합한 플래너이다. LAMA의 핵심 혁신:

랜드마크 기반 휴리스틱: 계획에서 반드시 달성해야 하는 중간 사실(랜드마크)을 활용
선호도 기반 탐색: 여러 큐를 사용하여 다양한 탐색 방향을 균형
반복적 개선(Anytime): 초기 계획 생성 후 비용을 점진적으로 개선

LAMA는 IPC 2008과 2011에서 우승하였다.

2.5 단계: 현대 발전 (2010년대 이후)

Scorpion: 합병-축소 휴리스틱의 최적화
Delfi: 기계 학습 기반 포트폴리오 플래너
GBFS with Novelty: 참신성(novelty) 기반 탐색 전략

3. 휴리스틱 탐색 플래너의 공통 구조

현대 휴리스틱 탐색 플래너의 일반적 구조:

HEURISTIC_SEARCH_PLANNER(problem):
    1. 전처리: PDDL → 내부 표현 변환, 도달 가능성 분석
    2. 휴리스틱 계산기 초기화
    3. 탐색:
        open ← {(s0, h(s0))}
        closed ← ∅
        WHILE open ≠ ∅:
            s ← SELECT(open)  ;; 휴리스틱 값 기반 선택
            IF s ⊨ goal: RETURN plan
            closed ← closed ∪ {s}
            FOR EACH applicable action a:
                s' ← γ(s, a)
                IF s' ∉ closed:
                    h_val ← h(s')
                    open ← INSERT(open, (s', h_val))
    4. 후처리: 내부 계획 → PDDL 계획 변환

4. 주요 휴리스틱의 비교

휴리스틱	계산 비용	정보성	허용 가능	대표 플래��
$h^{\text{add}}$	낮음	중간	아니오	HSP
$h^{\text{max}}$	낮음	낮음	예	비용 최적 플래너
$h^{\text{FF}}$	중간	높음	아니오	FF, LAMA
$h^{\text{LM-cut}}$	높음	매우 높음	예	Fast Downward (최적)
$h^{\text{M\&S}}$	높음 (사전 계산)	매우 높음	예	Scorpion
$h^{\text{LM-count}}$	중간	높음	아니오	LAMA

5. 참고 문헌

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.
Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.
Richter, S. & Westphal, M. (2010). “The LAMA Planner.” Journal of Artificial Intelligence Research, 39, 127–177.