1316.7 깊이 우선 탐색 기반 플래닝

1. 깊이 우선 탐색의 정의

깊이 우선 탐색(Depth-First Search, DFS)은 탐색 트리의 한 경로를 최대 깊이까지 우선적으로 확장한 후, 역추적(backtracking)하여 다른 경로를 탐색하는 전략이다. 스택(LIFO) 자료 구조를 사용하거나 재귀적으로 구현된다.

2. 알고리즘

DFS_PLANNING(s0, goal, depth_limit):
    RETURN DFS_RECURSIVE(s0, [], goal, depth_limit, ∅)

DFS_RECURSIVE(s, plan, goal, limit, path):
    IF s ⊨ goal: RETURN plan
    IF len(plan) >= limit: RETURN FAILURE
    IF s ∈ path: RETURN FAILURE    // 순환 방지

    path ← path ∪ {s}
    FOR EACH action a applicable in s:
        s' ← γ(s, a)
        result ← DFS_RECURSIVE(s', plan + [a], goal, limit, path)
        IF result ≠ FAILURE: RETURN result

    RETURN FAILURE

3. 특성 분석

3.1 공간 복잡도

$O(b \cdot m)$

여기서 $b$ 는 분기 요인, $m$ 은 최대 탐색 깊이이다. 이는 BFS의 $O(b^d)$ 에 비해 크게 우수하며, DFS의 핵심 장점이다.

3.2 시간 복잡도

$O(b^m)$

최악의 경우 전체 탐색 트리를 순회해야 하므로 BFS와 유사하나, 깊이 제한이 적절히 설정되면 실질적 탐색량을 줄일 수 있다.

3.3 완전성

깊이 제한 없는 DFS는 무한 경로에 빠질 수 있어 완전하지 않다. 깊이 제한(depth limit)을 설정하면 해당 깊이 이내의 해를 찾을 수 있지만, 적절한 깊이 제한의 설정이 어렵다.

3.4 최적성

DFS는 최적 계획을 보장하지 않는다. 처음 발견되는 해가 최단 해가 아닐 수 있다.

4. 플래닝에서의 DFS 적용

4.1 장점

메모리 효율성: 현재 경로만 메모리에 유지하므로 대규모 상태 공간에서도 실행 가능
빠른 첫 해 발견: 깊이 방향으로 빠르게 진행하여 해에 도달할 수 있음
역추적의 용이성: 스택 기반 구현으로 자연스러운 역추적

4.2 단점

비최적 해: 발견되는 첫 계획이 최단 또는 최저 비용이 아닐 수 있음
순환 위험: 상태 공간에 순환이 있으면 무한 루프에 빠질 수 있음
깊이 제한 설정의 어려움: 최적 깊이를 사전에 알기 어려움

5. 순환 방지 기법

DFS에서 순환을 방지하기 위한 기법:

경로 검사: 현재 탐색 경로에 포함된 상태의 재방문을 차단한다. 공간 비용이 $O(m)$ 으로 효율적이다.
깊이 제한: 최대 탐색 깊이를 설정하여 무한 경로를 차단한다.
closed 집합 사용: BFS와 유사하게 모든 방문 상태를 기록하지만, 공간 복잡도가 증가한다.

6. 깊이 제한 탐색(Depth-Limited Search)

깊이 제한 $l$ 을 설정하여 해당 깊이까지만 탐색하는 변형이다. 해가 깊이 $l$ 이내에 존재하면 발견하지만, 그렇지 않으면 실패한다. 이 한계는 반복 심화 탐색(Iterative Deepening Search)으로 해결된다.

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

순수 DFS는 현대 플래닝에서 단독으로 사용되지 않는다. 그러나 DFS의 원리는 다음의 고급 탐색 전략의 기반이 된다:

반복 심화 A(IDA)**: DFS의 메모리 효율성과 A*의 최적성을 결합
깊이 제한 휴리스틱 탐색: 휴리스틱으로 유도된 DFS
강제 산책(Enforced Hill-Climbing): FF 플래너의 핵심 탐색 기법

8. 참고 문헌

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.