양방향 탐색 플래닝 기법 (Bidirectional Search Planning Techniques)

1. 개요

양방향 탐색(bidirectional search) 플래닝은 전방 탐색과 후방 탐색을 동시에 수행하여, 두 탐색이 만나는 지점에서 계획을 구성하는 기법이다. 이론적으로 단방향 탐색보다 탐색 공간을 축소할 수 있으나, 구현의 복잡성과 두 탐색 간의 매칭 문제가 도전 과제이다.

2. 기본 원리

2.1 탐색 전략

Forward frontier: s₀ → expand → ...
Backward frontier: G → regress → ...

두 frontier가 교차하는 상태를 발견하면 계획 완성

2.2 이론적 이점

단방향 탐색의 시간 복잡도가 O(b^d)인 경우, 양방향 탐색은 이론적으로 O(b^{d/2})로 축소될 수 있다. 이는 분기 계수 b가 클 때 큰 이점이다.

3. AI 플래닝에서의 적용

3.1 기술적 도전

1. 부분 상태 매칭: 후방 탐색의 부분 상태와 전방 탐색의 완전 상태를 매칭하는 것이 어렵다.
2. 탐색 균형: 두 방향의 탐색 속도를 균형 있게 조절하여야 한다.
3. 휴리스틱 설계: 양방향 모두에 효과적인 휴리스틱 함수 설계가 어렵다.

3.2 실무에서의 채택

현대 계획기에서 양방향 탐색은 주류로 채택되지 않으며, 대부분 순방향 탐색에 강력한 휴리스틱을 결합하는 방식이 지배적이다.

4. 참고 문헌

• Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.