397.20 고전적 계획 기법의 기본 원리

1. 개요

고전적 계획(Classical Planning)은 자율 로봇 시스템이 주어진 초기 상태에서 목표 상태로 전이하기 위한 행동 시퀀스를 자동으로 생성하는 인공지능의 핵심 기법이다. 이 기법은 결정론적(deterministic)이고 완전 관측 가능한(fully observable) 환경을 전제로 하며, 유한한 상태 공간과 이산적 행동 집합을 기반으로 동작한다. 고전적 계획 기법은 로봇 임무 계획 분야에서 가장 전통적이면서도 여전히 중요한 이론적 기반을 제공한다.

2. 고전적 계획 문제의 형식적 정의

고전적 계획 문제(Classical Planning Problem)는 다음의 4-튜플(quadruple)로 형식화할 수 있다.

$\mathcal{P} = \langle \mathcal{S}, \mathcal{A}, \gamma, s_0, S_g \rangle$

여기서 각 요소의 정의는 다음과 같다.

$\mathcal{S}$ : 유한한 상태 집합(finite set of states)으로, 시스템이 존재할 수 있는 모든 가능한 세계 상태를 나열한 것이다.
$\mathcal{A}$ : 유한한 행동 집합(finite set of actions)으로, 에이전트가 수행할 수 있는 모든 원자적(atomic) 행동을 포함한다.
$\gamma: \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{S}$ : 상태 전이 함수(state transition function)로, 현재 상태 $s \in \mathcal{S}$ 에서 행동 $a \in \mathcal{A}$ 를 실행하였을 때 도달하는 다음 상태를 결정론적으로 정의한다.
$s_0 \in \mathcal{S}$ : 초기 상태(initial state)로, 계획 수립 시점에서 에이전트가 인식하는 세계의 현재 상태이다.
$S_g \subseteq \mathcal{S}$ : 목표 상태 집합(goal states)으로, 에이전트가 도달하고자 하는 바람직한 상태들의 부분집합이다.

이 형식화에서 **계획(plan)**은 행동의 유한 시퀀스 $\pi = \langle a_1, a_2, \ldots, a_n \rangle$ 으로 정의되며, 초기 상태 $s_0$ 에서 시작하여 이 시퀀스를 순차적으로 실행하면 목표 상태 $s_n \in S_g$ 에 도달하여야 한다.

$\gamma(\gamma(\cdots\gamma(s_0, a_1), a_2), \ldots, a_n) \in S_g$

3. 고전적 계획의 기본 가정

고전적 계획 기법은 다음의 엄격한 가정(assumptions)들을 전제로 한다. 이러한 가정은 문제의 복잡도를 제어하고 해의 존재성과 정확성을 보장하기 위한 것이다.

3.1 결정론적 행동(Deterministic Actions)

모든 행동의 결과는 고유(unique)하다. 즉, 동일한 상태에서 동일한 행동을 실행하면 항상 동일한 후속 상태가 생성된다. 확률론적(stochastic) 결과나 불확실성은 고려하지 않는다.

$\forall s \in \mathcal{S}, \forall a \in \mathcal{A}: |\gamma(s, a)| = 1$

3.2 완전 관측성(Full Observability)

에이전트는 임의의 시점에서 현재 세계 상태를 완전하게 인식할 수 있다. 센서 노이즈, 부분 관측, 정보 부족 등의 문제가 존재하지 않는 것으로 가정한다.

3.3 정적 환경(Static Environment)

계획 실행 중에 에이전트의 행동 이외의 외부 요인에 의해 세계 상태가 변하지 않는다. 다른 에이전트의 간섭이나 환경 자체의 동적 변화가 없는 것으로 간주한다.

3.4 유한 상태 공간(Finite State Space)

상태 공간 $\mathcal{S}$ 와 행동 공간 $\mathcal{A}$ 는 모두 유한(finite)하다. 이 상태 집합이 매우 커질 수 있으나, 원칙적으로 열거 가능(enumerable)하여야 한다.

3.5 순차적 행동 실행(Sequential Action Execution)

행동은 한 번에 하나씩 순차적으로 실행된다. 동시성(concurrency)이나 병렬 행동 실행은 고전적 계획의 범위에 포함되지 않는다.

3.6 암묵적 시간(Implicit Time)

행동의 수행에 소요되는 시간이 명시적으로 모델링되지 않는다. 각 행동은 즉각적으로 완료되는 것으로 가정한다.

4. 상태 공간 표현

4.1 명제적 상태 표현(Propositional State Representation)

고전적 계획에서 상태는 흔히 명제(proposition)의 집합으로 표현한다. 유한한 명제 변수 $P = \{p_1, p_2, \ldots, p_k\}$ 가 주어졌을 때, 상태 $s \subseteq P$ 는 참(true)인 명제들의 부분집합으로 정의된다. 이를 **닫힌 세계 가정(Closed-World Assumption, CWA)**이라 하며, 상태에 포함되지 않은 명제는 거짓(false)으로 간주한다.

예를 들어, 로봇의 위치와 물체의 위치를 다음과 같이 명제로 표현할 수 있다.

$s = \{ \text{at}(\text{robot}, \text{room1}),\ \text{on}(\text{box}, \text{table}),\ \text{gripper\_empty} \}$

이 상태에서 로봇은 room1에 있고, 상자는 테이블 위에 있으며, 그리퍼는 비어 있다고 해석한다.

4.2 상태 공간의 크기

$k$ 개의 명제 변수가 있을 때 가능한 상태의 수는 $2^k$ 이다. 실제 로봇 임무 계획 문제에서 명제 변수의 수가 수십에서 수백에 이를 수 있으므로, 상태 공간의 크기는 지수적(exponential)으로 증가한다. 이를 상태 공간 폭발(state space explosion) 현상이라 하며, 고전적 계획의 주요 연산 도전 과제이다.

5. 행동 모델

5.1 전제 조건과 효과(Preconditions and Effects)

고전적 계획에서 행동 $a \in \mathcal{A}$ 는 **전제 조건(preconditions)**과 **효과(effects)**의 쌍으로 정의한다.

$a = \langle \text{Pre}(a), \text{Eff}^+(a), \text{Eff}^-(a) \rangle$

$\text{Pre}(a) \subseteq P$ : 행동 $a$ 를 실행하기 위해 현재 상태에서 반드시 참이어야 하는 명제들의 집합이다.
$\text{Eff}^+(a) \subseteq P$ : 행동 $a$ 를 실행한 후 참이 되는 명제들의 집합(추가 목록, add list)이다.
$\text{Eff}^-(a) \subseteq P$ : 행동 $a$ 를 실행한 후 거짓이 되는 명제들의 집합(삭제 목록, delete list)이다.

행동 $a$ 가 상태 $s$ 에서 적용 가능(applicable)하기 위한 조건은 다음과 같다.

$\text{Pre}(a) \subseteq s$

행동 $a$ 를 상태 $s$ 에 적용한 결과 상태 $s'$ 는 다음과 같이 계산한다.

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

즉, 현재 상태에서 삭제 효과에 해당하는 명제를 제거하고, 추가 효과에 해당하는 명제를 추가하여 새로운 상태를 생성한다.

5.2 행동 모델의 예시

로봇이 물체를 집는 행동 $\text{pick\_up}(x)$ 을 다음과 같이 정의할 수 있다.

$\text{pick\_up}(x) = \langle \{ \text{on}(x, \text{table}), \text{gripper\_empty} \},\ \{ \text{holding}(x) \},\ \{ \text{on}(x, \text{table}), \text{gripper\_empty} \} \rangle$

이 행동은 물체 $x$ 가 테이블 위에 있고 그리퍼가 비어 있는 경우에만 실행할 수 있으며, 실행 후 로봇은 물체 $x$ 를 잡고 있는 상태가 되고, 물체의 테이블 위 존재와 그리퍼의 비어 있음 상태가 동시에 해제된다.

6. 계획 기법의 탐색 패러다임

고전적 계획 문제를 해결하기 위한 탐색(search) 패러다임은 크게 **상태 공간 탐색(state-space search)**과 **계획 공간 탐색(plan-space search)**으로 분류할 수 있다.

6.1 상태 공간 탐색(State-Space Search)

상태 공간 탐색은 상태를 노드로, 행동을 간선으로 하는 그래프에서 초기 상태로부터 목표 상태까지의 경로를 찾는 문제로 변환한다.

**순방향 탐색(Forward Search, Progression)**은 초기 상태 $s_0$ 에서 시작하여 적용 가능한 행동을 순차적으로 적용함으로써 목표 상태에 도달하는 경로를 탐색한다. 이 방식은 직관적이며 구현이 비교적 간단하나, 분기 계수(branching factor)가 클 경우 탐색 공간이 급격히 증가하는 단점이 있다.

**역방향 탐색(Backward Search, Regression)**은 목표 상태 $S_g$ 에서 시작하여 어떤 행동이 해당 상태로 이끌 수 있는지 역추적하는 방식이다. 이 기법은 목표 관련 행동만을 고려하므로 탐색 공간을 효과적으로 줄일 수 있으나, 부분 상태(partial state)의 표현과 회귀(regression) 연산의 복잡성이 증가하는 문제가 있다.

6.2 계획 공간 탐색(Plan-Space Search)

계획 공간 탐색은 부분 순서 계획(Partial-Order Planning, POP)의 기초를 이룬다. 이 방식에서는 완전한 상태가 아닌 **부분 계획(partial plan)**의 공간에서 탐색을 수행한다. 부분 계획은 행동의 집합, 행동 간의 순서 제약(ordering constraints), 인과 링크(causal links)로 구성된다.

인과 링크(causal link) $a_i \xrightarrow{p} a_j$ 는 행동 $a_i$ 의 효과 $p$ 가 행동 $a_j$ 의 전제 조건 $p$ 를 충족시키는 관계를 나타낸다. 계획 공간 탐색은 이러한 인과 관계를 점진적으로 구축하면서, 미해결 전제 조건(open precondition)과 위협(threat)을 해소하는 방향으로 진행한다.

**위협(threat)**은 인과 링크 $a_i \xrightarrow{p} a_j$ 사이에 명제 $p$ 를 삭제하는 행동 $a_k$ 가 삽입될 가능성이 있는 상황이다. 위협을 해소하기 위해 순서 제약을 추가하여 $a_k$ 를 $a_i$ 이전이나 $a_j$ 이후로 배치한다.

7. 휴리스틱 탐색 기반 고전적 계획

현대 고전적 계획기(planner)의 성능은 효과적인 휴리스틱 함수(heuristic function) $h(s)$ 의 설계에 크게 좌우된다. 휴리스틱 함수는 현재 상태 $s$ 에서 목표 상태까지의 예상 비용을 추정하는 함수로, 탐색 방향을 안내하는 역할을 한다.

7.1 삭제 완화 휴리스틱(Delete Relaxation Heuristic)

삭제 완화(delete relaxation)는 고전적 계획에서 가장 널리 사용되는 휴리스틱 도출 기법 중 하나이다. 이 기법은 행동의 삭제 효과 $\text{Eff}^-(a)$ 를 모두 무시하여 완화된 문제(relaxed problem) $\mathcal{P}^+$ 를 생성한다. 완화된 문제에서의 최적 비용 $h^+(s)$ 는 원래 문제의 허용적(admissible) 또는 비허용적(inadmissible) 추정치를 제공한다.

$\mathcal{P}^+ = \langle \mathcal{S}, \mathcal{A}^+, \gamma^+, s_0, S_g \rangle$

여기서 $\mathcal{A}^+$ 는 삭제 효과가 제거된 행동 집합이다.

** $h^{\text{add}}$ 휴리스틱(Additive Heuristic)**은 목표 상태의 각 명제를 독립적으로 달성하는 데 필요한 비용을 합산한 추정치를 제공한다.

$h^{\text{add}}(s) = \sum_{p \in S_g} h^{\text{add}}_p(s)$

여기서 $h^{\text{add}}_p(s)$ 는 현재 상태 $s$ 에서 명제 $p$ 를 달성하기 위한 최소 비용이다. 이 휴리스틱은 허용적이지 않으나, 정보량이 풍부하여 탐색 효율을 크게 향상시킬 수 있다.

** $h^{\text{max}}$ 휴리스틱(Max Heuristic)**은 목표 상태의 각 명제를 달성하는 비용 중 최댓값을 사용한다.

$h^{\text{max}}(s) = \max_{p \in S_g} h^{\text{max}}_p(s)$

이 휴리스틱은 허용적이므로 A* 탐색과 결합하면 최적 해를 보장할 수 있으나, 정보량이 적어 탐색 효율이 상대적으로 낮은 경우가 있다.

7.2 추상화 기반 휴리스틱(Abstraction-Based Heuristic)

패턴 데이터베이스(Pattern Database, PDB) 휴리스틱은 상태 공간의 투영(projection)을 통해 축소된 추상 문제에서의 정확한 비용을 사전 계산하여 사용한다. 원래 문제의 명제 변수 일부를 무시함으로써 추상 상태 공간을 생성하고, 이 추상 공간에서의 최적 비용을 원래 문제의 하한(lower bound)으로 활용한다.

$h^{\text{PDB}}(s) = \max_i h^{\text{PDB}}_i(\alpha_i(s))$

여기서 $\alpha_i$ 는 $i$ 번째 투영 함수이다.

7.3 랜드마크 기반 휴리스틱(Landmark-Based Heuristic)

**랜드마크(landmark)**는 임의의 유효한 계획에서 반드시 달성되어야 하는 명제 또는 행동을 의미한다. 랜드마크 기반 휴리스틱은 아직 달성되지 않은 랜드마크의 수 또는 이들을 달성하기 위한 비용을 추정하여 휴리스틱 값으로 사용한다.

$h^{\text{LM}}(s) = \sum_{L \in \mathcal{L}_{\text{unacc}}} \text{cost}(L)$

여기서 $\mathcal{L}_{\text{unacc}}$ 는 현재 경로에서 아직 달성되지 않은 랜드마크의 집합이다.

8. 고전적 계획의 계산 복잡도

고전적 계획 문제의 판정 문제(decision problem), 즉 “주어진 계획 문제에 해가 존재하는가?“는 **PSPACE-완전(PSPACE-complete)**임이 증명되어 있다(Bylander, 1994). 이는 최악의 경우 계획 수립에 다항 공간(polynomial space)이 필요하며, 시간 복잡도 측면에서 지수 시간(exponential time)이 소요될 수 있음을 의미한다.

그러나 실제 응용 문제에서는 도메인 구조를 활용한 휴리스틱과 탐색 기법의 발전으로, 수천 개의 명제 변수를 포함하는 문제도 합리적인 시간 내에 해결할 수 있는 경우가 많다. 현대 계획기인 Fast Downward(Helmert, 2006)나 LAMA(Richter & Westphal, 2010) 등은 이러한 효율적 기법들을 통합하여 높은 성능을 달성하고 있다.

9. 고전적 계획의 확장

고전적 계획의 기본 가정은 실제 로봇 시스템의 복잡한 환경을 완전히 반영하지 못한다. 따라서 다음과 같은 확장이 연구되어 왔다.

확장 방향	완화되는 가정	대응 기법
비결정론적 계획	결정론적 행동	조건부 계획(Contingent Planning)
부분 관측 계획	완전 관측성	신뢰 상태 기반 탐색
시간 계획	암묵적 시간	시간 요소 포함 PDDL 2.1
연속 계획	이산 상태	혼합 이산-연속 계획
다중 에이전트 계획	단일 에이전트	분산 계획, 합동 행동 공간
확률적 계획	결정론적 전이	MDP, POMDP 기반 기법

이러한 확장들은 고전적 계획의 형식적 기반 위에 추가적인 복잡성을 도입하면서도, 그 핵심 원리인 상태-행동-전이의 형식화와 탐색 기반 해법을 공유한다.

10. 로봇 임무 계획에서의 활용

고전적 계획 기법은 로봇 임무 계획에서 다음과 같은 방식으로 활용된다.

임무의 행동 시퀀스 생성: 로봇이 수행해야 할 고수준 작업(예: 물체 이동, 검사, 조립 등)을 행동으로 모델링하고, 이들의 전제 조건과 효과를 명세하여 자동으로 실행 가능한 행동 시퀀스를 생성한다.

PDDL 기반 도메인 모델링: 로봇의 행동 능력과 환경의 특성을 PDDL(Planning Domain Definition Language)로 형식화하여 도메인 독립적(domain-independent) 계획기에 전달함으로써, 특정 도메인에 종속되지 않는 범용적 임무 계획을 수립할 수 있다.

계층적 통합: 고전적 계획기의 출력을 하위 수준의 경로 계획기(path planner)나 모션 플래너(motion planner)의 입력으로 연결함으로써 계층적 임무 수행 아키텍처를 구성할 수 있다.

11. 참고 문헌

Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
Bylander, T. (1994). “The Computational Complexity of Propositional STRIPS Planning.” Artificial Intelligence, 69(1-2), 165–204.
Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.
Richter, S., & Westphal, M. (2010). “The LAMA Planner: Guiding Cost-Based Anytime Planning with Landmarks.” Journal of Artificial Intelligence Research, 39, 127–177.
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.

v0.1.0