LAMA 플래너의 동작 원리 (Operating Principles of the LAMA Planner)

1. 개요

LAMA(Landmarks, A* search and Multi-heuristic A*)는 Richter와 Westphal(2010)이 개발한 계획기로, 랜드마크 기반 휴리스틱과 h_{\text{FF}} 휴리스틱을 결합한 다중 휴리스틱 탐색을 수행한다. IPC 2008과 2011에서 최고 성능을 달성하였으며, Fast Downward 프레임워크를 기반으로 구현되었다.

2. LAMA의 핵심 전략

2.1 다중 휴리스틱 (Multi-Heuristic)

LAMA는 두 개의 휴리스틱을 동시에 사용한다.

2.2 다중 오픈 리스트 (Alternating Open Lists)

각 휴리스틱에 대해 별도의 오픈 리스트를 유지하고, 번갈아가며 노드를 확장한다. 이를 통해 두 휴리스틱의 장점을 모두 활용한다.

2.3 임의 시간 (Anytime) 전략

첫 번째 해를 빠르게 찾은 후, 남은 시간 동안 더 좋은 해를 탐색하여 품질을 점진적으로 개선한다.

2.4 선호 연산자 (Preferred Operators)

h_{\text{FF}}의 도움 행동과 랜드마크 기반 선호 연산자를 결합하여 탐색을 유도한다.

3. LAMA의 탐색 루프

1. h_LM과 h_FF에 대한 각각의 오픈 리스트 초기화
2. 번갈아가며 각 리스트에서 노드 확장
3. 해 발견 시 기록, 바운드 갱신
4. 개선된 해를 계속 탐색 (anytime)
5. 시간 제한 도달 시 최선의 해 반환

4. 성능

5. PlanSys2에서의 활용

LAMA는 Fast Downward의 설정 파일을 통해 PlanSys2의 플래너 플러그인으로 사용할 수 있다.

6. 참고 문헌

• Richter, S., & Westphal, M. (2010). “The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks.” JAIR, 39, 127-177.
• Helmert, M. (2006). “The Fast Downward Planning System.” JAIR, 26, 191-246.