1316.10 IDA* 알고리즘의 적용

1. IDA*의 정의와 원리

IDA*(Iterative Deepening A*)는 Korf(1985)가 제안한 알고리즘으로, A의 비용 최적성과 깊이 우선 탐색(DFS)의 선형 공간 복잡도를 결합한 탐색 전략이다. IDA는 A*의 평가 함수 $f(s) = g(s) + h(s)$ 를 사용하되, $f$ -값의 상한(threshold)을 점진적으로 증가시키면서 깊이 제한 DFS를 반복 수행한다.

2. 알고리즘 구조

IDA_STAR(s0, goal, h):
    threshold ← h(s0)
    LOOP:
        (result, min_f) ← BOUNDED_DFS(s0, 0, threshold, goal, h, [])
        IF result = SUCCESS:
            RETURN plan
        IF min_f = ∞:
            RETURN "No plan exists"
        threshold ← min_f

BOUNDED_DFS(s, g, threshold, goal, h, plan):
    f ← g + h(s)
    IF f > threshold:
        RETURN (CUTOFF, f)
    IF s ⊨ goal:
        RETURN (SUCCESS, plan)

    min_exceeded ← ∞
    FOR EACH action a applicable in s:
        s' ← γ(s, a)
        g' ← g + cost(a)
        (result, exceeded) ← BOUNDED_DFS(s', g', threshold, goal, h, plan + [a])
        IF result = SUCCESS:
            RETURN (SUCCESS, plan + [a])
        min_exceeded ← min(min_exceeded, exceeded)

    RETURN (CUTOFF, min_exceeded)

각 반복에서 threshold를 초과하는 최소 $f$ -값이 다음 반복의 threshold가 된다. 이에 따라 탐색 경계가 점진적으로 확장되며, 최적 해의 $f$ -값에 도달하면 해가 발견된다.

3. 핵심 특성

3.1 최적성 보장

허용 가능(admissible) 휴리스틱 $h$ 하에서 IDA*는 비용 최적 계획을 보장한다. 이는 $f$ -값의 하한에서 상한으로 점진적으로 탐색하므로, 최소 $f$ -값을 가진 해가 먼저 발견되기 때문이다.

3.2 공간 복잡도

$O(b \cdot d)$

여기서 $b$ 는 분기 요인, $d$ 는 최적 해의 깊이이다. DFS를 기반으로 하므로 현재 탐색 경로만 메모리에 유지하면 된다. 이는 A*의 $O(b^d)$ 에 비해 극적으로 우수하다.

3.3 시간 복잡도

$O(b^d)$

반복으로 인한 중복 탐색이 발생하지만, 비용이 정수인 경우 반복 횟수가 $O(C^*)$ ( $C^*$ : 최적 비용)에 비례한다. 비용이 실수인 경우 반복 횟수가 매우 커질 수 있어 성능이 저하될 수 있다.

4. A*와의 비교

특성	A*	IDA*
공간 복잡도	$O(b^d)$	$O(bd)$
시간 복잡도	$O(b^d)$	$O(b^d)$ (중복 포함)
최적성	보장	보장
완전성	보장	보장
중복 상태 검출	가능 (`closed` 집합)	제한적 (경로 검사만)
대규모 상태 공간	메모리 한계	적합

5. 플래닝에서의 IDA* 적용

5.1 적합한 시나리오

메모리 제약 환경: 임베디드 로봇 시스템 등 메모리가 제한된 환경에서 비용 최적 계획이 필요할 때
대규모 상태 공간: A*의 open/closed 집합이 메모리를 초과하는 도메인
단위 비용 도메인: 모든 액션의 비용이 동일하면 반복 횟수가 최적 깊이에 비례하여 효율적

5.2 부적합한 시나리오

실수 비용 도메인: 비용이 다양한 실수 값이면 $f$ -값 threshold의 증분이 매우 작아져 반복 횟수가 폭발적으로 증가
대량 중복 상태: closed 집합 없이 동일 상태를 반복 방문하여 비효율적
비단조적 휴리스틱: 일관성(consistency)이 보장되지 않으면 성능이 저하

5.3 중복 상태 문제의 완화

IDA*에서 중복 상태 방문을 줄이기 위한 기법:

;; 경로 기반 순환 검사
BOUNDED_DFS(s, g, threshold, goal, h, plan, path):
    IF s ∈ path: RETURN (CUTOFF, ∞)  ;; 현재 경로의 순환 방지
    ...

이 기법은 현재 경로상의 상태만 검사하므로 공간 비용이 $O(d)$ 에 불과하다. 그러나 서로 다른 경로를 통해 도달하는 동일 상태의 중복 방문은 차단하지 못한다.

5.4 전이 테이블(Transposition Table)

제한된 크기의 해시 테이블을 사용하여 최근 방문한 상태를 캐싱하는 기법이다. 전체 closed 집합보다 메모리 효율적이면서 중복 방문을 부분적으로 줄일 수 있다.

6. 플래닝 시스템에서의 IDA* 활용 사례

6.1 FF 플래너의 대안 탐색

FF 플래너(Hoffmann & Nebel, 2001)는 기본적으로 강제 산책(Enforced Hill-Climbing, EHC) 전략을 사용하지만, EHC가 실패하면(지역 최소에 빠지면) 가중 A* 또는 IDA* 변형으로 전환하여 완전한 탐색을 수행한다.

6.2 Fast Downward에서의 활용

Fast Downward(Helmert, 2006)는 기본적으로 A* 탐색을 사용하지만, 메모리 제한 설정 시 IDA*로 전환하는 옵션을 제공한다.

7. 로봇 도메인에서의 고려사항

로봇 도메인의 비용 구조: 이동 거리, 에너지 소모 등 실수 비용이 일반적이므로, IDA*의 반복 횟수가 증가할 수 있다. 비용을 정수로 이산화하거나 $\epsilon$ -그리딩(epsilon-gridding)을 적용하여 완화한다.
PlanSys2에서의 간접 활용: PlanSys2는 IDA를 직접 내장하지 않지만, Fast Downward를 플래너로 설정하면 IDA 기반 탐색을 사용할 수 있다.
실시간 제약: IDA의 반복 특성으로 인해 첫 해 발견까지 시간이 길어질 수 있으므로, 실시간 요구가 강한 로봇 시스템에서는 가중 A나 만족 플래닝이 더 적합할 수 있다.

8. 참고 문헌

Korf, R. E. (1985). “Depth-First Iterative-Deepening: An Optimal Admissible Tree Search.” Artificial Intelligence, 27(1), 97–109.
Hoffmann, J. & Nebel, B. (2001). “The FF Planning System: Fast Plan Generation Through Heuristic Search.” Journal of Artificial Intelligence Research, 14, 253–302.
Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.
Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.