1316.5 전방 상태 공간 탐색의 동작 원리

1. 전방 탐색의 정의

전방 상태 공간 탐색(forward state-space search)은 초기 상태 $s_0$ 에서 출발하여, 적용 가능한 액션을 순차적으로 적용하면서 후속 상태(successor state)를 생성하고, 목표 조건 $g$ 를 만족하는 상태에 도달할 때까지 탐색하는 방식이다. 이는 현대 고전적 플래너의 지배적 패러다임이다.

2. 알고리즘의 기본 구조

FORWARD_SEARCH(s0, goal, domain):
    open ← {(s0, [])}           // (상태, 경로) 쌍
    closed ← ∅

    WHILE open ≠ ∅:
        (s, path) ← SELECT(open)

        IF s ⊨ goal:
            RETURN path          // 계획 반환

        closed ← closed ∪ {s}

        FOR EACH action a IN domain:
            IF s ⊨ pre(a):      // 적용 가능성 검사
                s' ← γ(s, a)    // 상태 전이
                IF s' ∉ closed:
                    open ← INSERT(open, (s', path + [a]))

    RETURN "No plan exists"

3. 핵심 연산

3.1 적용 가능 액션의 열거

현재 상태 $s$ 에서 전제 조건이 충족되는 모든 그라운드 액션을 열거한다:

$\text{applicable}(s) = \{a \in \mathcal{A}_{\text{ground}} \mid s \models \text{pre}(a)\}$

이 연산의 효율성이 전체 탐색 성능에 직접적인 영향을 미친다. 술어 인덱싱, 타입 기반 필터링 등의 최적화가 적용된다.

3.2 상태 전이 계산

적용 가능한 액션 $a$ 를 상태 $s$ 에 적용하여 후속 상태 $s'$ 을 계산한다:

$s' = (s \setminus \text{eff}^-(a)) \cup \text{eff}^+(a)$

3.3 목표 검사

현재 상태가 목표 조건의 모든 리터럴을 포함하는지 확인한다:

$s \models g \iff g \subseteq s$

3.4 중복 상태 검출

closed 집합에서 현재 생성된 상태가 이미 방문되었는지 확인한다. 해시 기반 자료 구조를 사용하여 $O(1)$ 평균 시간에 수행한다.

4. 전방 탐색의 장단점

4.1 장점

직관적 구현: 초기 상태에서 전방으로 진행하는 자연스러운 흐름
완전한 상태 정보: 각 노드가 완전한 세계 상태를 포함하므로 전제 조건 평가가 정확
효과적 휴리스틱: 완전한 상태 정보를 기반으로 정보적 휴리스틱 계산 가능
효율적 중복 검출: 완전한 상태를 해시하여 빠른 중복 검출

4.2 단점

큰 분기 요인: 각 상태에서 적용 가능한 액션이 많으면 탐색 트리가 급격히 확장
목표 비관련 탐색: 목표와 무관한 액션도 탐색 대상에 포함
메모리 소비: 모든 생성된 상태를 저장해야 함

5. 전방 탐색과 휴리스틱

순수 전방 탐색(무정보 탐색)은 분기 요인이 높아 실용적이지 않다. 현대 플래너는 휴리스틱을 사용하여 유망한 방향으로 탐색을 유도한다:

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

여기서 $g(s)$ 는 초기 상태에서 $s$ 까지의 실제 비용, $h(s)$ 는 $s$ 에서 목표까지의 추정 비용이다. 대표적 휴리스틱으로 삭제 완화 휴리스틱( $h^{\text{add}}$ , $h^{\text{max}}$ , $h^{\text{FF}}$ ), 랜드마크 휴리스틱, 추상화 휴리스틱 등이 있다.

6. 현대 플래너에서의 전방 탐색

FF, Fast Downward, LAMA 등 현대의 주요 고전적 플래너는 모두 전방 상태 공간 탐색을 기반으로 한다. 이들은 탐색 전략, 휴리스틱, 전처리 기법에서 차이를 보이지만, 기본적인 전방 탐색 프레임워크를 공유한다.

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.