1316.9 A* 알고리즘을 활용한 플래닝

1. A* 알고리즘의 정의

A* 알고리즘은 Hart, Nilsson, Raphael(1968)이 제안한 정보적 탐색(informed search) 알고리즘으로, 휴리스틱 함수를 활용하여 최적 해를 효율적으로 탐색한다. 플래닝에 적용하면, 초기 상태에서 목표 상태까지의 비용 최적 계획을 보장하면서 불필요한 탐색을 최소화할 수 있다.

2. 평가 함수

A*의 핵심은 각 노드(상태)에 대한 평가 함수 $f$ 이다:

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

여기서:

$g(s)$ : 초기 상태 $s_0$ 에서 상태 $s$ 까지의 실제 경로 비용
$h(s)$ : 상태 $s$ 에서 목표 상태까지의 추정 비용(휴리스틱)

탐색은 $f$ 값이 가장 작은 노드를 우선적으로 확장한다.

3. 알고리즘

A_STAR_PLANNING(s0, goal, h):
    open ← priority_queue({(s0, f=h(s0), g=0, plan=[])})
    closed ← ∅

    WHILE open ≠ ∅:
        (s, f_val, g_val, plan) ← EXTRACT_MIN(open)

        IF s ⊨ goal:
            RETURN plan

        IF s ∈ closed:
            CONTINUE
        closed ← closed ∪ {s}

        FOR EACH action a applicable in s:
            s' ← γ(s, a)
            g_new ← g_val + cost(a)
            f_new ← g_new + h(s')
            IF s' ∉ closed:
                INSERT(open, (s', f_new, g_new, plan + [a]))

    RETURN "No plan exists"

4. 허용 가능 휴리스틱과 최적성

A*가 비용 최적 계획을 보장하려면, 휴리스틱 $h$ 가 **허용 가능(admissible)**해야 한다:

$\forall s \in S: h(s) \leq h^*(s)$

여기서 $h^*(s)$ 는 $s$ 에서 목표까지의 실제 최소 비용이다. 허용 가능 휴리스틱은 절대 과대 추정하지 않으므로, A*가 최적 해를 보장한다.

추가로 **일관성(consistency)**을 만족하면 중복 검출이 보다 효율적으로 수행된다:

$h(s) \leq c(s, a, s') + h(s')$

5. 플래닝에서 사용되는 허용 가능 휴리스틱

휴리스틱	정의	허용 가능	특성
$h^{\max}$	목표 리터럴 중 최대 달성 비용	예	허용 가능하나 비정보적
$h^{\text{LM-cut}}$	랜드마크 기반 컷	예	정보적, 비용 최적 플래닝에 효과적
$h^{\text{M\&S}}$	합병-축소 추상화	예	높은 정보성
$h^{\text{PDB}}$	패턴 데이터베이스	예	사전 계산 필요

6. A*의 성능 특성

6.1 시간 복잡도

$O(b^{d \cdot (1 - \epsilon)}) \text{ (이상적 휴리스틱 시)}$

여기서 $\epsilon$ 은 휴리스틱의 정확도에 의존하는 인자이다. 완벽한 휴리스틱( $h = h^*$ )이면 $O(d)$ 이고, 무정보 휴리스틱( $h = 0$ )이면 $O(b^d)$ 이다.

6.2 공간 복잡도

$O(b^d)$

모든 생성된 노드를 open 또는 closed에 저장해야 하므로, BFS와 동일한 공간 소비가 발생한다. 이는 A*의 가장 큰 실용적 제약이다.

7. 가중 A* (Weighted A*)

최적성을 완화하여 탐색 속도를 높이는 변형이다:

$f(s) = g(s) + w \cdot h(s), \quad w > 1$

가중치 $w$ 가 클수록 휴리스틱의 영향이 커져 탐색이 빨라지지만, 최적 비용의 $w$ 배 이내인 계획만 보장한다(w-admissible). 실용적 로봇 플래닝에서는 $w = 2 \sim 5$ 의 가중 A*가 빈도 높게 사용된다.

8. 비용 최적 플래닝에서의 A* 활용

Fast Downward 플래너는 A* 탐색을 지원하며, $h^{\text{LM-cut}}$ , $h^{\text{M\&S}}$ 등의 허용 가능 휴리스틱과 결합하여 비용 최적 계획을 생성한다. IPC의 비용 최적 트랙에서 최고 수준의 성능을 보인다.

9. 로봇 도메인에서의 A* 적용 고려사항

메모리 제한: 대규모 로봇 도메인에서 A의 메모리 소비가 문제가 될 수 있다. IDA나 SMA*(Simplified Memory-Bounded A*)로 대체를 고려한다.
실시간 요구: A의 탐색 시간이 실시간 제약을 초과하면 가중 A나 만족 플래닝으로 전환한다.
휴리스틱 선택: 도메인의 특성에 따라 적합한 휴리스틱을 선택해야 한다.

10. 참고 문헌

Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). “A Formal Basis for the Heuristic Determination of Minimum Cost Paths.” IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107.
Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.
Bonet, B. & Geffner, H. (2001). “Planning as Heuristic Search.” Artificial Intelligence, 129(1–2), 5–33.
Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.