1316.6 너비 우선 탐색 기반 플래닝

1. 너비 우선 탐색의 정의

너비 우선 탐색(Breadth-First Search, BFS)은 탐색 트리의 각 수준(depth level)을 순차적으로 확장하는 무정보(uninformed) 탐색 전략이다. 플래닝에 적용하면, 초기 상태에서 깊이 1의 모든 후속 상태를 먼저 생성하고, 이어서 깊이 2의 모든 후속 상태를 생성하는 방식으로 목표 상태를 찾는다.

2. 알고리즘

BFS_PLANNING(s0, goal):
    queue ← [(s0, [])]          // FIFO 큐
    closed ← {s0}

    WHILE queue ≠ ∅:
        (s, plan) ← DEQUEUE(queue)

        FOR EACH action a applicable in s:
            s' ← γ(s, a)
            IF s' ⊨ goal:
                RETURN plan + [a]
            IF s' ∉ closed:
                closed ← closed ∪ {s'}
                ENQUEUE(queue, (s', plan + [a]))

    RETURN "No plan exists"

3. 특성 분석

3.1 완전성(Completeness)

BFS는 완전하다. 유한한 분기 요인과 유한한 상태 공간에서 해가 존재하면 반드시 찾는다.

3.2 최적성(Optimality)

모든 액션의 비용이 균일한 경우(단위 비용), BFS는 최단 계획(최소 액션 수 계획)을 보장한다. 이는 BFS가 깊이 순서로 탐색하므로, 처음 발견되는 목표 상태까지의 경로가 최단 경로이기 때문이다.

비균일 비용에서는 최적성이 보장되지 않으며, 이 경우 균일 비용 탐색(Uniform-Cost Search) 또는 A*를 사용해야 한다.

3.3 시간 복잡도

$O(b^d)$

여기서 $b$ 는 분기 요인(각 상태에서 적용 가능한 평균 액션 수), $d$ 는 최단 계획의 깊이이다.

3.4 공간 복잡도

$O(b^d)$

BFS는 현재 수준과 이전 수준의 모든 노드를 메모리에 유지해야 하므로, 공간 소비가 크다. 이는 BFS의 가장 큰 실용적 제약이다.

4. 플래닝에서의 BFS 적용

4.1 장점

최단 계획 보장: 최소 액션 수 계획을 찾는 가장 단순한 방법
구현 용이: 큐 자료 구조만으로 구현 가능
완전성 보장: 해가 존재하면 반드시 발견

4.2 단점

메모리 폭발: 분기 요인이 큰 도메인에서 메모리가 빠르게 소진
비효율적 탐색: 목표와 무관한 방향으로도 동일하게 탐색
실용적 한계: 대규모 로봇 도메인에서 실용적이지 않음

5. BFS와 다른 탐색 전략의 비교

전략	시간	공간	최적성	완전성
BFS	$O(b^d)$	$O(b^d)$	보장 (단위 비용)	보장
DFS	$O(b^m)$	$O(bm)$	미보장	미보장 (깊이 제한 없이)
IDA*	$O(b^d)$	$O(bd)$	보장	보장
A*	$O(b^d)$	$O(b^d)$	보장 (허용 가능 $h$ )	보장

여기서 $m$ 은 최대 탐색 깊이이다.

6. 실용적 의의

BFS는 현대 플래닝에서 단독으로 사용되기보다는, 휴리스틱 탐색의 기준선(baseline)으로 활용되거나, 소규모 도메인에서의 최적 계획 검증에 사용된다. 대규모 로봇 도메인에서는 A* 또는 가중 A*(Weighted A*)와 같은 정보적 탐색이 필수적이다.

7. 참고 문헌

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.