1316.8 반복 심화 탐색 기반 플래닝

1. 반복 심화 탐색의 정의

반복 심화 탐색(Iterative Deepening Search, IDS)은 DFS의 메모리 효율성과 BFS의 완전성 및 최적성을 결합한 탐색 전략이다. 깊이 제한을 0부터 시작하여 점진적으로 증가시키면서 깊이 제한 DFS를 반복 수행한다(Korf, 1985).

2. 알고리즘

ITERATIVE_DEEPENING(s0, goal):
    FOR depth = 0, 1, 2, ...:
        result ← DEPTH_LIMITED_DFS(s0, goal, depth)
        IF result ≠ CUTOFF:
            RETURN result
    RETURN "No plan exists"

DEPTH_LIMITED_DFS(s, goal, limit):
    IF s ⊨ goal: RETURN []
    IF limit = 0: RETURN CUTOFF

    cutoff_occurred ← FALSE
    FOR EACH action a applicable in s:
        s' ← γ(s, a)
        result ← DEPTH_LIMITED_DFS(s', goal, limit - 1)
        IF result = CUTOFF:
            cutoff_occurred ← TRUE
        ELSE IF result ≠ FAILURE:
            RETURN [a] + result

    IF cutoff_occurred: RETURN CUTOFF
    ELSE: RETURN FAILURE

3. 특성 분석

3.1 시간 복잡도

$O(b^d)$

반복으로 인한 중복 탐색이 발생하지만, 시간 복잡도의 차수(order)는 BFS와 동일하다. 최종 반복에서의 탐색량이 이전 모든 반복의 합보다 크기 때문이다:

$\sum_{i=0}^{d} b^i = \frac{b^{d+1} - 1}{b - 1} \approx \frac{b}{b-1} \cdot b^d$

분기 요인 $b$ 가 클수록 중복 비율이 줄어든다. $b = 10$ 일 때 중복 비율은 약 11%에 불과하다.

3.2 공간 복잡도

$O(b \cdot d)$

DFS와 동일한 선형 공간 복잡도를 가진다. 이는 대규모 상태 공간에서의 핵심적 이점이다.

3.3 완전성과 최적성

단위 비용 하에서 IDS는 완전하고 최적(최단 계획 보장)이다. 이는 BFS의 수준별 탐색 순서를 재현하면서도 DFS의 메모리 효율성을 유지하는 결과이다.

4. IDA* (Iterative Deepening A*)

IDA는 IDS의 원리를 A 탐색에 적용한 것으로, 깊이 제한 대신 $f$ -값 제한을 사용한다(Korf, 1985):

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

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

    min_threshold ← ∞
    FOR EACH action a applicable in s:
        s' ← γ(s, a)
        cost ← action_cost(a)
        result, t ← BOUNDED_DFS(s', plan+[a], g+cost, goal, threshold, h)
        IF result ≠ CUTOFF: RETURN (result, t)
        min_threshold ← min(min_threshold, t)

    RETURN (CUTOFF, min_threshold)

허용 가능(admissible) 휴리스틱 $h$ 하에서 IDA*는 비용 최적 계획을 보장하면서 선형 공간 복잡도를 유지한다.

5. 플래닝에서의 실용적 의의

IDS와 IDA*는 다음의 상황에서 유용하다:

메모리 제한 환경: closed 집합을 유지할 수 없는 대규모 상태 공간
최적 계획 보장 필요: BFS/A*의 최적성을 메모리 효율적으로 달성
깊이 미지 시: 최적 계획의 깊이를 사전에 알 수 없는 경우

FF 플래너의 강제 산책(Enforced Hill-Climbing) 실패 시 대안 탐색으로 IDA* 변형이 사용되기도 한다.

6. 참고 문헌

Korf, R. E. (1985). “Depth-First Iterative-Deepening: An Optimal Admissible Tree Search.” Artificial Intelligence, 27(1), 97–109.
Russell, S. & Norvig, P. (2021). Artificial Intelligence: A Modern Approach. 4th Edition. Pearson.
Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.