후방 탐색 플래닝 알고리즘 (Backward Search Planning Algorithms)

1. 개요

후방 탐색(backward search) 플래닝은 목표 상태 G에서 시작하여, 해당 조건을 달성할 수 있는 행동을 역방향으로 추적하며 초기 상태에 도달하는 경로를 탐색하는 알고리즘이다. 목표 관련(goal-relevant) 행동에 집중하여 탐색 공간을 축소할 수 있다.

2. 기본 원리

2.1 회귀 (Regression)

목표 조건 G에서 행동 a를 역적용하여 선행 상태(predecessor state)를 도출한다.

\text{regress}(G, a) = (G \setminus \text{Add}(a)) \cup \text{Pre}(a)

이는 “목표 G를 달성하기 위해 행동 a를 마지막으로 실행한다면, 직전에 충족되어야 하는 조건은 무엇인가?“에 대한 답이다.

적용 가능 조건

행동 a가 목표 G에 대해 역적용 가능하려면:

1. \text{Add}(a) \cap G \neq \emptyset: 행동의 추가 효과가 목표의 일부를 달성
2. \text{Del}(a) \cap G = \emptyset: 행동의 삭제 효과가 목표를 파괴하지 않음

알고리즘

function BackwardSearch(P = ⟨S, A, γ, s₀, G⟩):
    Open = {G}
    while Open ≠ ∅:
        g = selectAndRemove(Open)
        if g ⊆ s₀:
            return reconstructPlan(g)
        for each action a relevant to g:
            g' = regress(g, a)
            Open = Open ∪ {g'}
    return FAILURE

전방 탐색과의 비교

장점과 한계

장점

• 목표 관련 행동에 집중하여 탐색 공간 축소
• 큰 초기 상태에서 작은 목표 조건으로의 탐색에 효율적

한계

• 부분 상태 표현의 복잡성
• 상호 배타(mutex) 관계 처리의 어려움
• 효율적 휴리스틱 설계의 어려움
• 대부분의 현대 계획기는 전방 탐색을 선호

참고 문헌

• 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.