1316.4 상태 공간 탐색과 계획 공간 탐색의 비교
1. 두 탐색 패러다임의 개요
고전적 플래닝 문제를 해결하는 두 가지 근본적으로 다른 탐색 패러다임이 존재한다: 상태 공간 탐색(state-space search)과 계획 공간 탐색(plan-space search)이다. 각 패러다임은 “무엇을 탐색 노드로 정의하는가“에서 근본적으로 구별된다(Ghallab, Nau, & Traverso, 2004).
2. 상태 공간 탐색
2.1 정의
상태 공간 탐색에서 각 탐색 노드는 세계 상태(world state)에 해당한다. 탐색은 초기 상태에서 시작하여 액션을 적용하면서 새로운 상태를 생성하고, 목표 조건을 만족하는 상태에 도달할 때까지 진행된다.
2.2 탐색 공간 구조
- 노드: 세계 상태 s \subseteq \mathcal{F}
- 간선: 상태 전이 (s, a, s') 여기서 s' = \gamma(s, a)
- 초기 노드: s_0
- 목표 노드: s \models g인 상태
2.3 전방 탐색(Forward Search)
초기 상태에서 시작하여 적용 가능한 액션을 적용하면서 전방으로 탐색한다. 현대의 대부분의 고전적 플래너(FF, Fast Downward, LAMA 등)가 이 방식을 채택한다.
2.4 후방 탐색(Backward Search)
목표 상태에서 시작하여 어떤 액션이 목표를 달성할 수 있는지를 역방향으로 탐색한다. 회귀(regression) 계산을 통해 목표 달성에 필요한 선행 상태를 도출한다.
3. 계획 공간 탐색
3.1 정의
계획 공간 탐색에서 각 탐색 노드는 부분 계획(partial plan)에 해당한다. 탐색은 빈 계획(또는 초기-목표만 포함하는 최소 계획)에서 시작하여, 부분 계획에 액션을 추가하고 제약을 부여하면서 완전한 계획으로 발전시킨다.
3.2 탐색 공간 구조
- 노드: 부분 계획 \pi = \langle A, O, L, C \rangle (액션, 순서, 인과 링크, 제약)
- 간선: 계획 개선(refinement) 연산
- 초기 노드: 최소 부분 계획 (시작/종료 액션만 포함)
- 목표 노드: 모든 열린 조건(open condition)이 해소되고 위협이 없는 계획
3.3 POCL(Partial-Order Causal Link) 플래너
대표적인 계획 공간 플래너로, 부분 순서 계획(partial-order plan)을 생성한다. 액션 간의 필요한 순서 관계만을 명시하고, 불필요한 순서는 미결정 상태로 유지한다.
4. 두 패러다임의 체계적 비교
| 특성 | 상태 공간 탐색 | 계획 공간 탐색 |
|---|---|---|
| 탐색 노드 | 세계 상태 | 부분 계획 |
| 탐색 방향 | 전방/후방 | 계획 개선 |
| 탐색 공간 크기 | O(2^n) 상태 | 가변적 (계획의 수) |
| 결과 계획 형태 | 전순서(total order) | 부분 순서(partial order) |
| 휴리스틱 설계 | 상태 기반 (정보적) | 미해결 결함 기반 |
| 중복 검출 | 상태 비교로 용이 | 계획 비교로 어려움 |
| 구현 복잡도 | 상대적으로 단순 | 복잡 |
| 현대 플래너 | FF, FD, LAMA | VHPOP, UCPOP |
| 성능 | 일반적으로 우수 | 상대적으로 열세 |
5. 역사적 발전
1970년대~1990년대 초에는 계획 공간 탐색(STRIPS, NOAH, UCPOP 등)이 주류였다. 그러나 1990년대 중반 이후 Graphplan(1995)과 HSP(1998)의 등장으로 상태 공간 탐색 기반의 플래너가 급격히 발전하면서, 현대의 주류 플래너는 대부분 상태 공간 탐색을 채택하고 있다.
이 전환의 핵심 요인은 삭제 완화 휴리스틱(delete relaxation heuristic) 등 효과적인 상태 기반 휴리스틱의 발견이다(Bonet & Geffner, 2001; Hoffmann & Nebel, 2001). 이러한 휴리스틱이 상태 공간 탐색의 분기 요인을 크게 줄여 실용적 성능을 달성하게 하였다.
6. 로봇 도메인에서의 선택
PlanSys2에서 사용되는 플래너(POPF, Fast Downward 등)는 모두 상태 공간 탐색 기반이다. 로봇 도메인에서의 실용적 선택 기준:
- 성능 우선: 상태 공간 탐색 기반 플래너가 일반적으로 더 빠르다.
- 병렬 계획 필요: 부분 순서 계획이 필요하면 POPF(시간 플래너)를 사용하여 시간적 병렬성을 활용한다.
- 최적성 요구: A* 기반 상태 공간 탐색이 비용 최적 계획을 보장한다.
7. 참고 문헌
- Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
- Bonet, B. & Geffner, H. (2001). “Planning as Heuristic Search.” Artificial Intelligence, 129(1–2), 5–33.
- Hoffmann, J. & Nebel, B. (2001). “The FF Planning System: Fast Plan Generation Through Heuristic Search.” Journal of Artificial Intelligence Research, 14, 253–302.
- Weld, D. S. (1994). “An Introduction to Least Commitment Planning.” AI Magazine, 15(4), 27–61.