1316.30 Fast Downward 플래너의 아키텍처
1. Fast Downward의 개요
Fast Downward는 Helmert(2006)가 개발한 모듈화된 플래닝 시스템으로, PDDL을 SAS+(유한 도메인 변수) 표현으로 변환한 후 다양한 휴리스틱과 탐색 알고리즘을 조합하여 계획을 생성한다. Fast Downward는 IPC에서 지속적으로 최고 수준의 성능을 보이며, LAMA, Scorpion 등 다수의 후속 플래너의 기반이 되는 프레임워크이다.
2. 단계 파이프라인 아키텍처
Fast Downward는 세 가지 독립된 모듈로 구성된 파��프라인 아키텍처를 채택한다:
[PDDL 입력] → [번역기(Translator)] → [전처리기(Preprocessor)] → [탐색기(Search)]
↓ ↓ ↓
SAS+ 출력 최적화된 SAS+ 계획 출력
2.1 단계: 번역기(Translator)
Python으로 구현된 번역기가 PDDL 도메인과 문제를 SAS+(유한 도메인 변수) 표현으로 변환한다:
- 명제 → 다치 변수: 관련된 명제 집합을 하나의 다치 변수(multi-valued variable)로 합친다. 예:
(robot_at r1 wp1),(robot_at r1 wp2),(robot_at r1 wp3)→ 변수V_robot_at_r1∈ {wp1, wp2, wp3} - 불변량(invariant) 분석: 상태에서 항상 유지되는 불변 조건을 식별하여 변수 인코딩에 활용
- 인과 그래프(causal graph) 구성: 변수 간의 인과적 의존 관계를 방향 그래프로 표현
2.2 단계: 전처리기(Preprocessor)
SAS+ 표현을 최적화하고 추가 분석을 수행한다:
- 도달 불가능 변수 값의 제거
- 전이 시스템의 축소
- 도메인 전이 그래프(Domain Transition Graph, DTG) 구성
2.3 단계: 탐색기(Search)
C++로 구현된 탐색 엔진�� SAS+ 표현에서 계획을 탐색한다. 다양한 탐색 알고리즘과 휴리스틱을 플러그인 방식으로 조합할 수 있다.
3. SAS+ 표현
SAS+ 표현은 유한 도메인 변수(finite-domain variable) 기반의 플래닝 형식이다:
- 변수 V = \{v_1, \ldots, v_n\}: 각 변수 v_i의 도메인 D_i는 유한 집합
- 상태: 각 변수에 값을 할당하는 완전 할당 s: V \rightarrow \bigcup D_i
- 연산자: 부분 할당 기반의 전제 조건과 효과
PDDL의 이진 명제에 비해 SAS+의 다치 변수는 더 간결한 상태 표현과 효율적인 휴리스틱 계산을 가능하게 한다(Helmert, 2009).
4. 지원 휴리스틱
Fast Downward는 플러그인 방식으로 다양한 휴리스틱을 지원한다:
| 휴리스틱 | 유형 | 허용 가능 | 특성 |
|---|---|---|---|
| h^{\text{FF}} | 삭제 완화 | 아니오 | 빠르고 정보적 |
| h^{\text{add}} | 삭제 완화 | 아니오 | 빠른 계산 |
| h^{\text{CG}} | 인과 그래프 | 아니오 | CG 구조 활용 |
| h^{\text{LM-cut}} | 랜드마크 컷 | 예 | 비용 최적에 효과적 |
| h^{\text{M\&S}} | 합병-축소 | 예 | 높은 정보성 |
| h^{\text{iPDB}} | 패턴 DB | 예 | 사전 계산 기반 |
| h^{\text{LM-count}} | 랜드마크 수 | 아니오 | LAMA의 기반 |
5. 지원 탐색 알고리즘
| 알고리즘 | 최적성 | 특성 |
|---|---|---|
| A* | 보장 (허용 가능 h 시) | 비용 최적 플래닝 |
| 가중 A* | 비보장 | 빠른 만족 플래닝 |
| Greedy best-first | 비보장 | 가장 빠른 만족 플래닝 |
| Eager/Lazy GBFS | 비보장 | 중복 검출 시점 차이 |
| 다중 큐 | 비보장 | LAMA의 기반 |
6. 커맨드라인 인터페이스
Fast Downward는 유연한 커맨드라인 인터페이스를 통해 탐색 구성을 지정한다:
# A* + LM-cut 휴리스틱 (비용 최적)
./fast-downward.py domain.pddl problem.pddl --search "astar(lmcut())"
# Greedy best-first + FF 휴리스틱 (만족 플래닝)
./fast-downward.py domain.pddl problem.pddl --search "eager_greedy([ff()])"
# LAMA 구성
./fast-downward.py domain.pddl problem.pddl --alias lama-first
7. PlanSys2에서의 활용
PlanSys2는 Fast Downward를 외부 플래너로 설정할 수 있다. 듀레이티브 액션이 필요 없는 도메인에서, Fast Downward는 POPF보다 고전적 플래닝 문제에서 우수한 성능을 보일 수 있다.
8. 참고 문헌
- Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.
- Helmert, M. (2009). “Concise Finite-Domain Representations for PDDL Planning Tasks.” Artificial Intelligence, 173(5–6), 503–535.
- Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.