1316.11 후방 상태 공간 탐색의 동작 원리

1. 후방 탐색의 정의

후방 상태 공간 탐색(backward state-space search)은 목표 조건에서 출발하여 초기 상태로 역방향으로 탐색하는 전략이다. 전방 탐색이 초기 상태에서 액션을 적용하여 후속 상태를 생성하는 것과 반대로, 후방 탐색은 목표 조건에서 액션을 역방향으로 적용(회귀, regression)하여 선행 조건을 도출한다(Ghallab, Nau, & Traverso, 2004).

2. 회귀 연산

후방 탐색의 핵심 연산은 회귀(regression)이다. 목표 조건 집합 $g$ 에 대해 액션 $a$ 의 회귀는, $a$ 를 적용하면 $g$ 가 달성되는 선행 상태의 조건을 계산한다:

$\text{regress}(g, a) = (\text{pre}(a) \cup (g \setminus \text{eff}^+(a))) \setminus \text{eff}^-(a)$

회귀가 유효하려면 다음 조건을 만족해야 한다:

관련성(Relevance): 액션 $a$ 의 추가 효과가 $g$ 의 일부 리터럴을 달성해야 한다: $\text{eff}^+(a) \cap g \neq \emptyset$
일관성(Consistency): 액션 $a$ 의 삭제 효과가 $g$ 의 리터럴을 파괴하지 않아야 한다: $\text{eff}^-(a) \cap g = \emptyset$

3. 알고리즘

BACKWARD_SEARCH(s0, goal):
    open ← {goal}
    closed ← ∅

    WHILE open ≠ ∅:
        g ← SELECT(open)

        IF g ⊆ s0:                     ;; 초기 상태가 조건을 만족
            RETURN plan

        closed ← closed ∪ {g}

        FOR EACH action a IN domain:
            IF relevant(a, g) AND consistent(a, g):
                g' ← regress(g, a)
                IF g' ∉ closed:
                    open ← INSERT(open, g')

    RETURN "No plan exists"

4. 전방 탐색과의 비교

특성	전방 탐색	후방 탐색
탐색 시작점	초기 상태 $s_0$	목표 조건 $g$
탐색 방향	$s_0 \rightarrow g$	$g \rightarrow s_0$
노드의 성격	완전한 상태	부분 상태 (조건 집합)
적용 연산	상태 전이 $\gamma(s, a)$	회귀 $\text{regress}(g, a)$
분기 요인	적용 가능 액션 수	관련 액션 수
중복 검출	상태 비교 (정확)	조건 집합 비교 (복잡)
목표 지향성	낮음 (휴리스틱 의존)	높음 (목표에서 출발)

5. 후방 탐색의 장점

목표 지향적 탐색: 목표 조건에서 출발하므로, 목표와 무관한 액션이 자연스럽게 배제된다. 관련성(relevance) 조건에 의해 목표에 기여하지 않는 액션이 탐색 대상에서 제외된다.
부분 상태를 통한 추상화: 후방 탐색의 각 노드는 완전한 상태가 아닌 부분적 조건 집합이다. 이는 목표 달성에 필요한 조건만을 추적하므로, 무관한 상태 요소가 자동으로 배제된다.

6. 후방 탐색의 단점

부분 상태의 비결정성: 각 노드가 완전한 상태가 아니므로, 전제 조건의 정확한 평가가 어려울 수 있다. 부정적 전제 조건(not)의 처리가 특히 복잡하다.
중복 검출의 어려움: 부분 상태(조건 집합) 간의 동치성 판단이 완전한 상태 비교보다 복잡하다. 집합 포함 관계의 검사가 필요하다.
휴리스틱 설계의 어려움: 부분 상태에 대한 효과적인 휴리스틱을 설계하기 어렵다. 전방 탐색에 비해 정보적 휴리스틱의 발전이 제한적이다.

7. 현대 플래닝에서의 위치

현대의 주류 고전적 플래너(FF, Fast Downward, LAMA)는 전방 탐색을 채택하고 있으며, 순수 후방 탐색 기반 플래너는 드물다. 그 이유는 전방 탐색에 적합한 강력한 휴리스틱(삭제 완화, 랜드마크 등)이 개발된 반면, 후방 탐색용 휴리스틱의 발전이 상대적으로 더딘 데 있다.

그러나 후방 탐색의 원리는 다음에서 간접적으로 활용된다:

회귀 기반 휴리스틱: 목표에서 후방으로 관련 액션을 추적하여 휴리스틱 정보를 도출
랜드마크 추출: 목표 달성에 반드시 거쳐야 하는 중간 상태(랜드마크)를 후방 분석으로 식별
양방향 탐색: 전방과 후방을 동시에 진행하여 중간에서 만나는 탐색 전략

8. 참고 문헌

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.
Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.