397.25 역방향 탐색(Backward Search) 기반 계획

1. 개요

역방향 탐색(backward search) 기반 계획은 목표 조건에서 출발하여, 해당 목표를 달성할 수 있는 행동을 역으로 추적하며 초기 상태에 도달하는 계획 기법이다. 이 접근 방식은 **회귀 계획(regression planning)**이라 불리며, 순방향 탐색이 초기 상태로부터 진행(progression)하는 것과 대조적으로 목표로부터 **후퇴(regression)**하는 방향으로 탐색을 수행한다. 역방향 탐색은 목표 지향적(goal-directed) 탐색의 본질적 속성으로 인해, 목표와 무관한 상태 공간의 탐색을 회피할 수 있다는 구조적 장점을 갖는다.

2. 역방향 탐색의 수학적 기초

2.1 부분 상태와 신뢰 집합

순방향 탐색에서 각 탐색 노드가 완전히 정의된 상태(fully specified state)를 나타내는 것과 달리, 역방향 탐색에서 각 탐색 노드는 부분 상태(partial state) 또는 **신뢰 집합(belief set)**을 나타낸다. 부분 상태는 명제 변수의 부분 집합에 대해서만 참/거짓을 명시하고, 나머지 변수는 미정(don’t-care)으로 남긴다.

고전적 계획 문제 \mathcal{P} = \langle \mathcal{F}, \mathcal{A}, s_0, G \rangle에서 부분 상태는 다음과 같이 정의된다.

\hat{s} = (P, N), \quad P \subseteq \mathcal{F}, \quad N \subseteq \mathcal{F}, \quad P \cap N = \emptyset

여기서 P는 참이어야 하는 명제의 집합(긍정 조건)이고, N은 거짓이어야 하는 명제의 집합(부정 조건)이다. \mathcal{F} \setminus (P \cup N)에 해당하는 명제의 값은 미정이다.

부분 상태 \hat{s} = (P, N)은 완전 상태(complete state)의 집합을 표현한다. 부분 상태에 의해 표현되는 완전 상태의 집합은 다음과 같다.

\llbracket \hat{s} \rrbracket = \{ s \subseteq \mathcal{F} \mid P \subseteq s \wedge N \cap s = \emptyset \}

목표 조건 G는 초기 부분 상태 \hat{s}_G = (G, \emptyset)로 표현된다. 탐색이 초기 상태 s_0를 포함하는 부분 상태에 도달하면, 즉 s_0 \in \llbracket \hat{s} \rrbracket을 만족하면 계획이 성공적으로 완성된다.

2.2 행동의 회귀(Regression of Actions)

역방향 탐색의 핵심 연산은 **행동 회귀(action regression)**이다. 주어진 부분 상태 \hat{s} = (P, N)에 대해 행동 a의 회귀를 수행하면, 행동 a를 적용하면 \hat{s}에 도달할 수 있는 선행 부분 상태(predecessor partial state)를 생성한다.

행동 a가 부분 상태 \hat{s} = (P, N)에 대해 관련 있는(relevant) 조건은 다음과 같다.

\text{add}(a) \cap P \neq \emptyset \quad \text{(행동이 목표 명제 중 하나 이상을 달성)}

행동 a가 부분 상태 \hat{s} = (P, N)에 대해 일관된(consistent) 조건은 다음과 같다.

\text{add}(a) \cap N = \emptyset \quad \wedge \quad \text{del}(a) \cap P \subseteq \text{add}(a)

즉, 행동이 부정 조건에 있는 명제를 추가하지 않고, 긍정 조건에 있는 명제를 삭제하면서 동시에 추가하지 않는(즉, 순수하게 삭제하지 않는) 경우이다.

행동 a가 관련 있고 일관된 경우, 부분 상태 \hat{s}에 대한 a의 회귀 결과는 다음과 같이 정의된다.

\text{regress}(\hat{s}, a) = (P', N')

여기서

P' = (P \setminus \text{add}(a)) \cup \text{pre}(a)

N' = (N \setminus \text{del}(a)) \cup (\text{del}(a) \setminus P)

직관적으로, 회귀 연산은 다음을 수행한다.

1. 행동 a에 의해 달성되는 목표 명제를 제거한다(P \setminus \text{add}(a)).
2. 행동 a의 전제 조건을 새로운 하위 목표로 추가한다(\cup \text{pre}(a)).
3. 행동 a에 의해 삭제되는 명제 중 부정 조건에서 제거되어야 할 것을 처리한다.

3. 역방향 탐색 알고리즘

3.1 기본 역방향 탐색 절차

역방향 탐색의 기본 절차는 다음과 같다.

\begin{aligned} &\textbf{Algorithm: Backward-Search}(\mathcal{P}) \\ &\quad \hat{s}_0 \leftarrow (G, \emptyset) \\ &\quad \text{Open} \leftarrow \{\hat{s}_0\} \\ &\quad \text{Closed} \leftarrow \emptyset \\ &\quad \textbf{while } \text{Open} \neq \emptyset \textbf{ do} \\ &\quad\quad \hat{s} \leftarrow \text{Select}(\text{Open}) \\ &\quad\quad \textbf{if } s_0 \in \llbracket \hat{s} \rrbracket \textbf{ then return } \text{ExtractPlan}(\hat{s}) \\ &\quad\quad \text{Closed} \leftarrow \text{Closed} \cup \{\hat{s}\} \\ &\quad\quad \textbf{for each } a \in \mathcal{A} \text{ relevant and consistent w.r.t. } \hat{s} \textbf{ do} \\ &\quad\quad\quad \hat{s}' \leftarrow \text{regress}(\hat{s}, a) \\ &\quad\quad\quad \textbf{if } \hat{s}' \text{ is consistent and } \hat{s}' \notin \text{Closed} \cup \text{Open} \textbf{ then} \\ &\quad\quad\quad\quad \text{Open} \leftarrow \text{Open} \cup \{\hat{s}'\} \\ &\quad \textbf{return } \text{FAIL} \end{aligned}

3.2 부분 상태의 일관성 검사

회귀 과정에서 생성된 부분 상태 \hat{s}' = (P', N')의 **일관성(consistency)**을 검사하여야 한다. 부분 상태가 일관적이려면 다음 조건을 만족하여야 한다.

P' \cap N' = \emptyset

즉, 동일한 명제가 동시에 참이어야 하고 거짓이어야 하는 모순이 없어야 한다. 모순된 부분 상태는 실현 불가능(unrealizable)하므로, 탐색 과정에서 즉시 가지치기(pruning)된다.

3.3 초기 상태 도달 검사

역방향 탐색의 종료 조건은 현재 부분 상태 \hat{s} = (P, N)이 초기 상태 s_0를 포함하는지 확인하는 것이다.

s_0 \in \llbracket \hat{s} \rrbracket \iff P \subseteq s_0 \wedge N \cap s_0 = \emptyset

이 검사는 O(|\mathcal{F}|) 시간에 수행 가능하다.

4. 역방향 탐색의 휴리스틱

4.1 순방향 휴리스틱의 적응

역방향 탐색에서 휴리스틱 함수 h(\hat{s})는 부분 상태 \hat{s}에서 초기 상태 s_0에 도달하기 위한 추정 비용을 제공한다. 순방향 탐색에서 개발된 휴리스틱을 역방향 탐색에 적용하기 위해서는 다음과 같은 변환이 필요하다.

부분 상태 \hat{s} = (P, N)의 긍정 조건 P를 순방향 탐색의 “목표“로, 초기 상태 s_0를 “초기 상태“로 간주하여 역방향 도달 가능성을 추정한다. 이 방식은 순방향 탐색의 삭제 완화 휴리스틱을 역방향 설정에 적용할 수 있게 한다.

h^{\text{back}}(\hat{s}) \approx h^{\text{fwd}}(s_0, P)

여기서 h^{\text{fwd}}(s_0, P)는 초기 상태 s_0에서 조건 P를 달성하기 위한 순방향 휴리스틱 추정치이다.

4.2 목표 카운팅 휴리스틱(Goal Counting Heuristic)

가장 단순한 역방향 휴리스틱은 현재 부분 상태에서 초기 상태에 의해 충족되지 않는 조건의 수를 세는 것이다.

h^{\text{gc}}(\hat{s}) = |\{p \in P \mid p \notin s_0\}| + |\{p \in N \mid p \in s_0\}|

이 휴리스틱은 계산이 매우 빠르지만 정보량이 적으므로, 소규모 문제에서만 효과적이다.

4.3 역방향 도달 가능성 그래프 휴리스틱

역방향 탐색에 특화된 휴리스틱으로, **역방향 계획 그래프(backward planning graph)**를 구성하여 현재 부분 상태에서 초기 상태까지의 거리를 추정할 수 있다. 역방향 계획 그래프는 목표 조건에서 출발하여, 각 계층에서 관련 행동을 역방향으로 적용함으로써 확장된다.

역방향 계획 그래프의 계층 수(level)는 목표에서 초기 상태까지의 하한(lower bound)을 제공하며, 이를 휴리스틱으로 활용할 수 있다.

5. 역방향 탐색의 구현

5.1 부분 상태 기반 역방향 탐색기

다음은 부분 상태를 탐색 노드로 사용하는 역방향 탐색 계획기의 구현 예시이다.

from dataclasses import dataclass, field
from typing import Set, FrozenSet, Optional, List, Tuple
import heapq

@dataclass(frozen=True)
class PartialState:
    """부분 상태를 나타내는 불변 클래스"""
    positive: FrozenSet[str]  # 참이어야 하는 명제
    negative: FrozenSet[str]  # 거짓이어야 하는 명제
    
    def is_consistent(self) -> bool:
        """부분 상태의 일관성을 검사한다."""
        return len(self.positive & self.negative) == 0
    
    def is_satisfied_by(self, state: FrozenSet[str]) -> bool:
        """완전 상태가 이 부분 상태를 만족하는지 검사한다."""
        return (self.positive.issubset(state) and
                len(self.negative & state) == 0)

@dataclass
class Action:
    """STRIPS 행동을 나타내는 클래스"""
    name: str
    params: List[str]
    preconditions: FrozenSet[str]
    add_effects: FrozenSet[str]
    del_effects: FrozenSet[str]
    cost: float = 1.0

class BackwardSearchPlanner:
    """역방향 탐색 기반 계획기"""
    
    def __init__(self, actions: List[Action]):
        self.actions = actions
    
    def is_relevant(self, action: Action,
                    pstate: PartialState) -> bool:
        """행동이 부분 상태에 대해 관련 있는지 검사한다."""
        return len(action.add_effects & 
                   pstate.positive) > 0
    
    def is_consistent(self, action: Action,
                      pstate: PartialState) -> bool:
        """행동이 부분 상태에 대해 일관된지 검사한다."""
        # 행동이 부정 조건의 명제를 추가하지 않는가
        if len(action.add_effects & pstate.negative) > 0:
            return False
        # 행동이 긍정 조건의 명제를 순수 삭제하지 않는가
        pure_del = (action.del_effects & pstate.positive
                   ) - action.add_effects
        if len(pure_del) > 0:
            return False
        return True
    
    def regress(self, pstate: PartialState,
                action: Action) -> Optional[PartialState]:
        """부분 상태에 대한 행동 회귀를 수행한다."""
        if not (self.is_relevant(action, pstate) and
                self.is_consistent(action, pstate)):
            return None
        
        # 새로운 긍정 조건 계산
        new_positive = (
            (pstate.positive - action.add_effects) |
            action.preconditions
        )
        
        # 새로운 부정 조건 계산
        new_negative = (
            (pstate.negative - action.del_effects) |
            (action.del_effects - pstate.positive)
        )
        
        result = PartialState(
            positive=frozenset(new_positive),
            negative=frozenset(new_negative)
        )
        
        if not result.is_consistent():
            return None
        
        return result
    
    def solve(self, initial_state: FrozenSet[str],
              goal: FrozenSet[str],
              heuristic=None) -> Optional[List[Action]]:
        """
        역방향 탐색을 수행하여 계획을 생성한다.
        
        Args:
            initial_state: 초기 상태 (완전 상태)
            goal: 목표 조건 (명제 집합)
            heuristic: 휴리스틱 함수
        
        Returns:
            plan: 행동의 순서열 또는 None
        """
        start_pstate = PartialState(
            positive=frozenset(goal),
            negative=frozenset()
        )
        
        if start_pstate.is_satisfied_by(initial_state):
            return []  # 목표가 이미 만족됨
        
        # 기본 휴리스틱: 목표 카운팅
        if heuristic is None:
            def heuristic(ps):
                return len(
                    ps.positive - initial_state
                ) + len(ps.negative & initial_state)
        
        open_list = []
        counter = 0
        g_values = {start_pstate: 0}
        parent = {start_pstate: (None, None)}
        closed = set()
        
        h = heuristic(start_pstate)
        heapq.heappush(
            open_list, (h, counter, start_pstate)
        )
        counter += 1
        
        while open_list:
            f, _, pstate = heapq.heappop(open_list)
            
            if pstate in closed:
                continue
            
            if pstate.is_satisfied_by(initial_state):
                return self._extract_plan(
                    parent, pstate
                )
            
            closed.add(pstate)
            g = g_values[pstate]
            
            for action in self.actions:
                successor = self.regress(pstate, action)
                if successor is None:
                    continue
                if successor in closed:
                    continue
                
                new_g = g + action.cost
                if (successor not in g_values or
                    new_g < g_values[successor]):
                    g_values[successor] = new_g
                    parent[successor] = (pstate, action)
                    h = heuristic(successor)
                    heapq.heappush(
                        open_list,
                        (new_g + h, counter, successor)
                    )
                    counter += 1
        
        return None
    
    def _extract_plan(self, parent, pstate):
        """역추적으로 계획을 추출한다."""
        plan = []
        while parent[pstate][0] is not None:
            prev_pstate, action = parent[pstate]
            plan.append(action)
            pstate = prev_pstate
        # 역방향이므로 반전하지 않음
        # (목표→초기 순서가 실행 순서)
        return plan

5.2 중복 상태 관리

역방향 탐색에서 부분 상태의 중복 검사는 순방향 탐색보다 복잡하다. 두 부분 상태 \hat{s}_1 = (P_1, N_1)과 \hat{s}_2 = (P_2, N_2)가 동일한 경우는 P_1 = P_2 \wedge N_1 = N_2이다. 그러나 **포함 관계(subsumption)**를 고려하면, \llbracket \hat{s}_1 \rrbracket \subseteq \llbracket \hat{s}_2 \rrbracket인 경우 \hat{s}_1은 \hat{s}_2에 의해 포함되므로, 이미 \hat{s}_2가 탐색 대상에 포함되어 있다면 \hat{s}_1을 추가할 필요가 없다.

\llbracket \hat{s}_1 \rrbracket \subseteq \llbracket \hat{s}_2 \rrbracket \iff P_2 \subseteq P_1 \wedge N_2 \subseteq N_1

포함 검사는 계산 비용이 높으므로, 실용적으로는 정확한 등가 검사만 수행하거나, 부분 상태의 긍정 조건에 대한 해시 값을 이용하여 근사적 중복 검사를 수행한다.

6. 순방향 탐색과 역방향 탐색의 비교

6.1 구조적 차이

순방향 탐색과 역방향 탐색의 핵심적 차이는 탐색 노드의 성격에 있다.

6.2 탐색 공간의 비교

순방향 탐색에서 각 상태는 |\mathcal{F}|개의 이진 변수로 완전히 결정되므로, 가능한 상태의 수는 최대 2^{|\mathcal{F}|}이다. 역방향 탐색에서 각 부분 상태의 각 명제는 참(P), 거짓(N), 미정(don’t-care)의 세 가지 값을 가질 수 있으므로, 가능한 부분 상태의 수는 최대 3^{|\mathcal{F}|}이다. 이는 역방향 탐색의 잠재적 탐색 공간이 순방향 탐색보다 지수적으로 클 수 있음을 의미한다.

그러나 실제로 역방향 탐색은 목표와 관련 있는 행동만 탐색하므로, 효과적인 가지치기가 이루어진다. 특히 목표가 소수의 명제로 구성되고 행동의 효과가 제한적인 경우, 역방향 탐색의 실질적 탐색 공간은 순방향 탐색보다 작을 수 있다.

6.3 양방향 탐색(Bidirectional Search)

순방향 탐색과 역방향 탐색의 상보적 장점을 활용하기 위해, 두 방향의 탐색을 동시에 수행하는 **양방향 탐색(bidirectional search)**이 제안되었다. 양방향 탐색은 초기 상태에서 순방향으로, 목표에서 역방향으로 동시에 탐색을 진행하며, 두 탐색의 프론티어(frontier)가 만나면 해를 구성한다.

양방향 탐색의 이론적 시간 복잡도는 O(b^{d/2})로, 단방향 탐색의 O(b^d)에 비해 크게 감소한다. 그러나 실제 계획 문제에서 양방향 탐색의 효과적 구현은 두 방향의 탐색 프론티어 간의 **교차 검사(meet-in-the-middle check)**의 효율적 구현과, 양 방향에서의 상태 표현 불일치(순방향: 완전 상태, 역방향: 부분 상태)를 해결하여야 하는 기술적 과제를 수반한다.

7. 역방향 탐색의 역사적 의의와 현대적 위치

7.1 STRIPS에서의 역방향 탐색

최초의 자동 계획 시스템인 STRIPS(Fikes & Nilsson, 1971)는 역방향 탐색(목표 회귀)에 기반한 수단-목표 분석(means-ends analysis) 전략을 채택하였다. STRIPS는 현재 달성되지 않은 목표 명제를 선택하고, 해당 명제를 효과로 갖는 행동을 찾아 적용함으로써 새로운 하위 목표를 생성하는 방식으로 동작한다.

STRIPS의 수단-목표 분석은 목표 지향적 탐색의 효율성을 보여주었으나, **서스만 이상(Sussman anomaly)**과 같은 상호 종속 목표(interacting subgoals) 문제에서 최적 해를 찾지 못하는 한계가 있었다.

7.2 부분 순서 계획과의 관계

역방향 탐색의 개념적 확장인 **부분 순서 계획(partial-order planning)**은 행동의 순서를 부분적으로만 결정하면서 계획을 구성하며, 개방 조건(open conditions)의 해결과 위협(threat)의 해결을 통해 계획을 정제(refine)한다. UCPOP(Penberthy & Weld, 1992) 등의 부분 순서 계획기는 역방향 탐색의 아이디어를 일반화한 시스템이다.

7.3 현대 계획에서의 위치

현대의 고성능 계획기는 대부분 순방향 탐색에 기반하고 있으며, 순수한 역방향 탐색을 주 알고리즘으로 사용하는 계획기는 상대적으로 드물다. 그 주된 이유는 다음과 같다.

1. 휴리스틱의 발전: 삭제 완화, 추상화, 랜드마크 등 순방향 탐색에 특화된 강력한 휴리스틱이 개발되어, 순방향 탐색의 맹목적 탐색 문제가 크게 완화되었다.
2. 부분 상태 관리의 복잡성: 역방향 탐색에서 부분 상태의 포함 관계 검사, 일관성 유지 등의 추가적 연산 부담이 발생한다.
3. SAS+ 표현의 이점: 현대 계획기가 채택하는 SAS+ 표현은 순방향 탐색에 최적화되어 있다.

그러나 역방향 탐색의 핵심 원리인 목표 회귀 분석은 현대 계획 기법에서도 중요한 역할을 수행한다. 랜드마크 추출(landmark extraction), 관련 행동 분석(relevant action analysis), 목표 순서 분석(goal ordering analysis) 등에서 역방향 분석 기법이 활용된다. 또한 계획 인식(plan recognition) 분야에서는 관측된 행동에서 역방향으로 목표를 추론하는 데 회귀 분석이 핵심적으로 사용된다.

8. 로봇 임무 계획에서의 역방향 탐색 활용

8.1 목표 분해와 하위 목표 생성

로봇 임무 계획에서 역방향 탐색의 원리는 복잡한 임무 목표를 하위 목표로 분해하는 데 활용된다. 예를 들어, “물체 A를 위치 B에 배달하라“는 임무 목표에 대해 역방향 분석을 수행하면 다음과 같은 하위 목표 체인이 생성된다.

\text{object-at}(A, B) \xleftarrow{\text{put-down}} \text{holding}(R, A) \wedge \text{at}(R, B) \xleftarrow{\text{move}} \text{at}(R, L_A) \wedge \text{holding}(R, A) \xleftarrow{\text{pick-up}} \text{at}(R, L_A) \wedge \text{object-at}(A, L_A)

이러한 하위 목표 체인은 임무의 구조적 이해와 실행 가능성 평가에 유용한 정보를 제공한다.

8.2 실행 불가능 조건의 조기 탐지

역방향 분석은 임무의 실행 가능성을 조기에 판단하는 데 활용될 수 있다. 목표에서 역방향으로 분석하여, 초기 상태에서 도달 불가능한 전제 조건이 발견되면 해당 임무가 실현 불가능함을 빠르게 판단할 수 있다. 이는 계획 수립 시간을 절약하고, 사용자에게 임무 불가능에 대한 조기 피드백을 제공하는 데 기여한다.

8.3 혼합 탐색 전략

실용적 로봇 임무 계획 시스템에서는 순방향 탐색과 역방향 분석을 결합한 혼합 전략이 효과적일 수 있다. 예를 들어, 역방향 분석을 통해 목표와 관련된 행동과 변수를 식별한 후, 이 정보를 순방향 탐색의 휴리스틱에 반영하여 탐색을 안내하는 방식이 가능하다. 이를 **목표 인식 휴리스틱(goal-aware heuristic)**이라 하며, 순방향 탐색의 실질적 효율을 크게 향상시킬 수 있다.

9. 참고 문헌

• Fikes, R. E., & Nilsson, N. J. (1971). “STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving.” Artificial Intelligence, 2(3–4), 189–208.
• Penberthy, J. S., & Weld, D. S. (1992). “UCPOP: A Sound, Complete, Partial Order Planner for ADL.” Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning (KR 1992), 103–114.
• 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.
• Russell, S. J., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th ed.). Pearson.
• Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.
• Weld, D. S. (1994). “An Introduction to Least Commitment Planning.” AI Magazine, 15(4), 27–61.
• Sussman, G. J. (1975). A Computer Model of Skill Acquisition. Elsevier.

v0.2.0