Fast Downward 플래너의 아키텍처 (Architecture of the Fast Downward Planner)

1. 개요

Fast Downward는 Helmert(2006)가 개발한 모듈식 계획기 프레임워크로, PDDL 입력을 SAS+(다치 변수) 표현으로 변환하고, 다양한 휴리스틱과 탐색 알고리즘을 플러그인 방식으로 조합하는 아키텍처를 제공한다. LAMA, Mercury 등 IPC 우승 계획기의 기반이다.

2. 단계 아키텍처

[PDDL 입력] → [변환기] → [SAS+ 표현] → [탐색 엔진] → [계획]

2.1 단계: 변환 (Translation)

PDDL을 SAS+ 표현으로 변환한다. 이 과정에서 상호 배타 그룹(mutex group)을 식별하여 다치 변수를 생성한다.

2.2 단계: 전처리 (Preprocessing)

인과 그래프(causal graph) 분석, 도메인 전이 그래프(domain transition graph) 생성 등의 전처리를 수행한다.

2.3 단계: 탐색 (Search)

다양한 탐색 알고리즘(A*, GBFS, WA*, EHC 등)과 휴리스틱(h_{\text{FF}}, h_{\text{CG}}, h_{\text{LM}}, PDB 등)을 조합하여 계획을 탐색한다.

3. SAS+ 표현

다치 변수를 사용하여 상태를 표현한다.

s = \{v_1 = d_1, v_2 = d_2, \ldots, v_n = d_n\}

상호 배타 조건이 자연스럽게 처리되어, 명제적 표현보다 효율적이다.

인과 그래프 (Causal Graph)

변수 간의 인과 관계를 방향 그래프로 표현한다. 변수 v_i의 값이 변수 v_j의 전이에 영향을 미치면 v_i \rightarrow v_j 간선이 존재한다. 인과 그래프 분석은 PDB 패턴 선택, 분해 전략 등에 활용된다.

모듈식 설계

참고 문헌

• Helmert, M. (2006). “The Fast Downward Planning System.” JAIR, 26, 191-246.
• Helmert, M. (2009). “Concise Finite-Domain Representations for PDDL Planning Tasks.” Artificial Intelligence, 173(5-6), 503-535.