플래닝 문제의 형식적 정의 (Formal Definition of the Planning Problem)

1. 개요

플래닝 문제(planning problem)는 인공지능에서 가장 기본적인 문제 유형 중 하나로, 초기 상태에서 목표 상태에 도달하기 위한 행동 시퀀스를 탐색하는 문제이다. 본 절에서는 고전적 계획 문제의 형식적 정의와 주요 구성 요소를 다룬다.

2. 형식적 정의

2.1 상태 전이 시스템

플래닝의 기반은 상태 전이 시스템 \Sigma = (S, A, \gamma)이다.

2.2 계획 문제

계획 문제는 상태 전이 시스템에 초기 상태와 목표를 추가한 5-튜플이다.

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

• s_0 \in S: 초기 상태 (세계의 현재 상태)
• G \subseteq S: 목표 상태의 집합 (달성하여야 할 조건을 충족��는 상태들)

해 (Solution)

계획 문제 \mathcal{P}의 해는 행동 시퀀스 \pi = \langle a_1, a_2, \ldots, a_n \rangle으로, 다음을 만족한다.

s_n = \gamma(\ldots\gamma(\gamma(s_0, a_1), a_2)\ldots, a_n) \in G

즉, 초기 상태에서 행동 시퀀스��� 순차 적용한 결과 상태가 목표 집합에 포함되어야 한다.

2.3 적용 가능성 (Applicability)

행동 a가 상태 s에서 적용 가능하려면, a의 전제 조건이 s에서 충족되어야 한다.

a \text{ is applicable in } s \iff \text{pre}(a) \subseteq s

적용 불가능한 행동을 포함하는 시퀀스는 유효한 해가 아니다.

명제적 표현

상태의 명제적 표현

상태 s는 참인 명제(ground atom)의 집합으로 표현된다.

s = \{p_1, p_2, \ldots, p_k\} \subseteq \mathcal{F}

여기서 \mathcal{F}��� 모든 가능한 명제(fluent)의 집합이다. s에 포함된 명제는 참, 포함되지 않은 명제는 거짓이�� (폐쇄 세계 가정, Closed World Assumption).

2.4 행동의 명제적 표현

행동 a는 세 구성 요소로 정의된다.

a = \langle \text{pre}(a), \text{eff}^+(a), \text{eff}^-(a) \rangle

• \text{pre}(a): 전제 조건 (참이어야 하는 명제의 집합)
• \text{eff}^+(a): 추가 효과 (참이 되는 명제)
• \text{eff}^-(a): 삭제 효과 (거짓이 되는 명제)

상태 전이

\gamma(s, a) = (s \setminus \text{eff}^-(a)) \cup \text{eff}^+(a) \quad \text{if } \text{pre}(a) \subseteq s

3. 목표의 표현

목표 G는 참이어야 하는 명제의 집합(목표 조건)으로 표현된다.

G = \{g_1, g_2, \ldots, g_m\}

상태 s가 목표를 충족하려면 G \subseteq s이어야 한다.

계획의 유형

참고 문헌

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