휴리스틱 기반 플래닝 기법 (Heuristic-Based Planning Techniques)

1. 개요

휴리스틱 기반 플래닝은 현재 상태에서 목표까지의 추정 비용(휴리스틱 함수 h(s))을 활용하여 탐색을 유도하는 계획 기법이다. 현대 최고 성능 계획기의 핵심 메커니즘이며, 플래닝 그래프로부터 도출되는 다양한 도메인 독립(domain-independent) 휴리스틱이 개발되어 있다.

2. 휴리스틱 함수의 역할

2.1 탐색 유도

f(s) = g(s) + h(s)

A* 탐색에서 f(s)는 초기 상태에서 s를 거쳐 목표에 도달하는 추정 총 비용이다. h(s)가 정확할수록 탐색이 목표 방향으로 효율적으로 유도된다.

허용 가능성 (Admissibility)

h(s) \leq h^*(s), \quad \forall s \in S

h^*(s)는 s에서 목표까지의 실제 최소 비용이다. 허용 가능한 휴리스틱을 사용하면 A*가 최적 계획을 보장한다.

3. 주요 도메인 독립 휴리스틱

3.1 h_{\max} 휴리스틱

각 목표 명제를 달성하는 데 필요한 최소 행동 수의 최대값이다.

h_{\max}(s) = \max_{g \in G} \text{cost}(s, g)

허용 가능하지만 정보가 약하여 실용적으로 잘 사용되지 않는다.

h_{\text{add}} 휴리스틱

각 목표 명제를 달성하는 최소 비용의 합이다.

h_{\text{add}}(s) = \sum_{g \in G} \text{cost}(s, g)

허용 가능하지 않으나(과추정), 정보가 풍부하여 탐색 효율이 높다. FF 계획기에서 변형된 형태로 활용된다.

3.2 h_{\text{FF}} 휴리스틱

삭제 효과를 무시한 완화된 문제(delete relaxation)의 해를 구하고, 그 길이를 휴리스틱으로 사용한다. FF 계획기의 핵심이다.

3.3 랜드마크 기반 휴리스틱 (h_{\text{LM}})

랜드마크(landmark)는 모든 유효한 계획에 반드시 달성되어야 하는 명제이다. 아직 달성되지 않은 랜드마크의 수를 휴리스틱으로 사용한다.

3.4 인과 그래프 휴리스틱

SAS+ 표현의 인과 그래프(causal graph)를 분석하여 변수 간 의존성에 기반한 비용을 추정한다. Fast Downward 계획기에서 활용된다.

4. 휴리스틱 비교

5. 다중 휴리스틱

Fast Downward와 LAMA는 복수의 휴리스틱을 동시에 사용하여, 각 휴리스틱의 장점을 결합한다.

6. 참고 문헌

• Hoffmann, J. (2001). “FF: The Fast-Forward Planning System.” AI Magazine, 22(3), 57-62.
• Helmert, M. (2006). “The Fast Downward Planning System.” JAIR, 26, 191-246.
• 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.