상태 공간 탐색 기반 플래닝 (State-Space Search-Based Planning)

1. 개요

상태 공간 탐색(state-space search) 기반 플래닝은 계획 문제를 그래프 탐색 문제로 환원하여, 초기 상태에서 목표 상��에 이르는 경로를 탐색하는 방식이다. 이는 현대 AI 플래닝의 지배적 패러다임이며, FF, Fast Downward, LAMA 등 최고 성능 계획기의 기반이다.

2. 상태 공간 그래프

계획 문제의 상태 공간은 방향 그래프(directed graph)로 표현된다.

• 노드: 가능한 상태 s \in S
• 간선: 상태 s에서 행동 a를 적용하여 상태 s' = \gamma(s, a)로 전이하는 간선 (s, a, s')

계획 탐색은 이 그래프에서 s_0에서 s_g \in G까지의 경로를 찾는 문제이다.

3. 탐색 방향

3.1 순방향 탐색 (Forward Search)

초기 상태 s_0에서 시작���여 적용 가능한 행동을 확장하며 목표에 도달하는 상태를 탐색한다.

frontier = {s0}
while frontier is not empty:
    s = select(frontier)
    if s ∈ G: return plan
    for each applicable action a in s:
        s' = γ(s, a)
        frontier = frontier ∪ {s'}

장점: 적용 가능한 행동만 고려하므로 유효하지 않은 행동이 자동으로 ���제됨
단점: 목표와 무관한 방향으로의 탐색이 발생할 수 있음

3.2 역방향 탐색 (Backward Search)

목표 상태 G에서 시작하여 해당 조건을 달성할 수 있는 행동을 역방향으로 ��적한다.

장점: 목표 관련(goal-relevant) 행동에 집중하여 탐색 공간 축소
단점: 부분 상태(partial state) 표현이 필요하여 구현이 복잡

3.3 양방향 탐색 (Bidirectional Search)

순방향과 역방향을 동시에 수행하여, 두 탐색이 만나는 지점에서 계획을 구성한다.

4. 탐색 알고리즘

여기서 b는 분기 계수(branching factor), d는 최적 해의 깊이, m은 최대 깊이이다.

5. 휴리스틱의 역할

순방향 탐색에서 휴리스틱 함수 h(s)는 상태 s에서 목표까지의 추정 비용을 제공하여, 유망한 방향으로의 탐색을 유도한다.

f(s) = g(s) + h(s)

• g(s): s_0에서 s까지의 실제 비용
• h(s): s에서 G까지의 추정 비용

참고 문헌

• Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.
• Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach. 4th ed. Pearson.