1316.36 LAMA 플래너의 설계와 특성
1. LAMA의 개요
LAMA(Landmarks, Actions, and Adaptive search)는 Richter와 Westphal(2010)이 개발한 만족 플래너로, Fast Downward 프레임워크를 기반으로 랜드마크 휴리스틱과 FF 휴리스틱을 결합한다. LAMA는 IPC 2008 만족 트랙과 IPC 2011에서 우승하며, 현대 만족 플래닝의 표준으로 자리 잡았다.
2. 핵심 설계 요소
2.1 랜드마크 기반 휴리스틱
랜드마크(landmark)는 모든 유효한 계획에서 반드시 달성되어야 하는 사실이다. LAMA는 미달성 랜드마크의 수를 휴리스틱 값으로 사용한다:
h^{\text{LM}}(s) = \lvert\{l \in \mathcal{L} \mid l \text{ is not achieved in } s\}\rvert
2.2 FF 휴리스틱의 병용
LAMA는 랜드마크 휴리스틱과 FF 휴리스틱을 동시에 사용한다. 두 휴리스틱이 서로 다른 도메인 구조를 포착하므로, 결합 시 탐색 효율이 향상된다.
2.3 다중 큐 탐색
네 개의 큐를 라운드 로빈 방식으로 사용한다:
- h^{\text{LM}} 일반 큐
- h^{\text{FF}} 일반 큐
- h^{\text{LM}} 선호 큐 (랜드마크 기반 선호적 연산자)
- h^{\text{FF}} 선호 큐 (FF 기반 도움 행동)
2.4 반복적 비용 개선(Anytime)
첫 번째 해를 빠르게 찾은 후, 비용 제한을 설정하여 더 나은 해를 반복적으로 탐색한다:
1차: GBFS 탐색 → 비용 C1인 해 발견
2차: 가중 A* (w=5, bound=C1) → 비용 C2 < C1인 해 발견
3차: 가중 A* (w=3, bound=C2) → 비용 C3 < C2인 해 발견
...
시간 제한까지 반복, 가중치를 점진적으로 감소
3. LAMA의 탐색 전략 상세
3.1 단계: 빠른 첫 해 탐색
Greedy Best-First Search(GBFS)와 다중 큐를 사용하여 가능한 한 빨리 첫 번째 유효한 계획을 찾는다. 이 단계에서는 비용 최적성을 추구하지 않는다.
3.2 단계: 반복적 개선
첫 해의 비용을 상한으로 설정하고, 가중 A*로 더 나은 해를 탐색한다. 가중치를 5 → 3 → 2 → 1로 점진적으로 줄여, 초기에는 빠르게 개선하고 후반에는 최적에 가까운 해를 탐색한다.
4. LAMA의 성능 특성
| 특성 | 값 |
|---|---|
| 완전성 | 보장 (GBFS + 대안 탐색) |
| 최적성 | 비보장 (만족 플래너), 반복적 개선으로 근사 |
| 첫 해 발견 속도 | 매우 빠름 |
| 비용 개선 | 시간에 따라 점진적 개선 |
| PDDL ��원 | STRIPS, ADL, 수치 (제한적), 파생 술어 |
5. IPC 결과
| 대회 | 트랙 | 순위 |
|---|---|---|
| IPC 2008 | 만족 | 1위 |
| IPC 2011 | 만족 | 1위 |
| IPC 2014 | 만족 | 상위권 |
LAMA는 다양한 도메인에서 일관된 우수한 성능을 보이며, 특정 도메인에 특화되지 않은 범용 플래너(general-purpose planner)로 평가된다.
6. PlanSys2에���의 활용
Fast Downward를 플래너로 설정하고 LAMA 구성을 적용할 수 있다:
./fast-downward.py domain.pddl problem.pddl --alias lama-first
듀레이티브 액션이 필요하지 않은 로봇 도메인에서, LAMA는 빠른 계획 생성과 비용 개선의 균형을 제공하는 우수��� 선택이다.
7. 참고 문헌
- Richter, S. & Westphal, M. (2010). “The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks.” Journal of Artificial Intelligence Research, 39, 127–177.
- Richter, S., Helmert, M., & Westphal, M. (2008). “Landmarks Revisited.” Proceedings of AAAI, 975–982.
- Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.