랜드마크 기반 휴리스틱 (Landmark-Based Heuristics)

1. 개요

랜드마크(landmark)는 모든 유효한 계획에서 반드시 달성되어야 하는 명제 또는 행동이다. 아직 달성되지 않은 랜드마크의 수를 기반으로 목표까지의 비용을 추정하는 것이 랜드마크 기반 휴리스틱이며, LAMA 계획기의 핵심 메커니즘이다.

2. 랜드마크의 정의

명제 p가 계획 문제 \mathcal{P}의 랜드마크이려면, 모든 유효한 계획 \pi에서 p가 어느 시점에서 참이어야 한다.

\forall \pi \in \text{solutions}(\mathcal{P}), \exists i : p \in \gamma(s_0, \pi[1:i])

랜드마크의 유형

랜드마크 휴리스틱

기본 형태

h_{\text{LM}}(s) = \lvert \{L \in \mathcal{L} : L \text{ not yet achieved}\} \rvert

아직 달성되지 않은 랜드마크의 수를 휴리스틱으로 사용한다.

2.1 허용 가능한 변형

최적 비용 분할(cost partitioning)을 적용하면 허용 가능한 랜드마크 휴리스틱을 구성할 수 있다.

3. 랜드마크의 추출

플래닝 그래프, 역방향 도달 가능성 분석, 이유 그래프(justification graph) 등의 기법으로 랜드마크를 자동 추출한다.

4. LAMA 계획기에서의 활용

LAMA(Richter & Westphal, 2010)는 랜드마크 기반 휴리스틱과 h_{\text{FF}} 휴리스틱을 결합하여, IPC 2008에서 최고 성능을 달성하였다.

4.1 LAMA의 전략

1. 랜드마크 카운팅으로 빠른 초기 해 발견
2. h_{\text{FF}}로 해 품질 개선
3. 다중 큐(open-list)를 통한 탐색 균형

5. 참고 문헌

• Richter, S., Helmert, M., & Westphal, M. (2008). “Landmarks Revisited.” AAAI 2008.
• Richter, S., & Westphal, M. (2010). “The LAMA Planner.” JAIR, 39, 127-177.
• Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.