Chapter 1312. AI 플래닝 이론 기초 (Foundations of AI Planning Theory)

1. 개요

AI 플래닝(Artificial Intelligence Planning)은 지능적 에이전트가 주어진 목표를 달성하기 위한 행동 시퀀스를 자동으로 생성하는 인공지능의 핵심 분야이다. 1960년대 STRIPS(Stanford Research Institute Problem Solver)에서 시작하여, 반세기에 걸친 이론적 발전을 통해 현대의 효율적 계획 알고리즘과 표준화된 계획 언어(PDDL)로 결실을 맺었다. 본 장에서는 AI 플래닝의 이론적 기초를 체계적으로 다루며, 로봇 공학에서의 자율 임무 계획에 필요한 핵심 개념과 형식적 프레��워크를 제시한다.

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

2.1 상태 전이 시스템

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

• S: 유한한 상태(state)의 집합
• A: 유한한 행동(action)의 집합
• \gamma : S \times A \rightarrow S: 상태 전이 함수

2.2 계획 문제

계획 문제는 상태 전이 시스템에 초기 상태와 목표 조건을 추가한 튜플 \mathcal{P} = (S, A, \gamma, s_0, G)로 ���의된다.

s_0 \in S: \text{초기 상태}, \quad G \subseteq S: \text{���표 상태의 ��합}

해 (Solution)

계획 문제의 해는 행동 시퀀스 \pi = \langle a_1, a_2, \ldots, a_n \rangle으로, 순차 적용의 결과가 목표 상태에 도달한다.

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

3. 계획의 가정과 분류

3.1 고전적 계획의 가정

3.2 계획 문제의 확장

4. 명제적 표현

4.1 STRIPS 표현

STRIPS(Fikes & Nilsson, 1971)는 최초의 형식적 계획 언어로, 상태를 명제(proposition)의 집합으로, 행동을 전제 조건(precondition)과 효과(effect)로 표현한다.

행동 a의 정의:

• \text{pre}(a): 전제 조건 (참이어야 하는 명제 집합)
• \text{add}(a): 추가 리스트 (참이 되는 명제)
• \text{del}(a): 삭제 리스트 (거짓이 되는 명제)

상태 전이:
\gamma(s, a) = (s \setminus \text{del}(a)) \cup \text{add}(a) \quad \text{if } \text{pre}(a) \subseteq s

ADL (Action Description Language)

STRIPS를 확장하여 조건부 효과(conditional effects), 부정 전제 조건(negative preconditions), 양화사(quantifiers)를 지��한다.

탐색 기반 계획

순방향 탐색 (Forward Search)

초기 상태 s_0에서 시작하여 적용 가능한 행동을 확장하며 목표에 도달하는 상태를 탐색한다.

• 너비 우선 탐색 (BFS): 최단 계획 보장, 메모리 소모 큼
• 깊이 우선 탐�� (DFS): 메모리 효율적, 최적성 미보장
• A* 탐색: 휴리스틱 기반 최적 탐색

역방향 탐색 (Backward Search)

목표 상태 G에서 시작하여 해당 조건을 달성할 수 있는 행동을 역방향으로 추적한다. 목표 관련 행동만 고려하므로 탐색 공간이 축소될 수 있다.

휴리스틱 기반 계획

완화된 문제 (Relaxed Problem)

삭제 효과를 무시한 완화된 문제(delete relaxation)의 해 길이를 휴리스틱으로 사용한다.

h^+(s) = \text{완화된 문제의 최적 해 길이}

h^+는 허용 가능(admissible)하나 계산이 NP-hard이므로, 다항 시간 근사를 ��용한다.

4.2 주요 휴리스틱

5. 계획 그래프 (Planning Graph)

Blum과 Furst(1997)가 제안한 계획 그래프는 도달 가능한 명제와 행동을 계층적으로 확장하는 데이터 구조이다. Graphplan 알고리즘의 기반이며, 효율적 휴리스틱 계산에도 활용된다.

6. 부분 순서 계획 (Partial-Order Planning)

행동 간의 순서를 필요한 만큼만 지정하는 부분 순서 계획(POP)은, 완전 순서 계획보다 더 유연한 계획 구조를 제공한다. 시간적 계획에서 병렬 실행 가능한 행동을 식별하는 데 유용하다.

7. 계층적 태스크 네트워크 (HTN)

HTN 플래닝은 추상적 태스크를 구체적 행동으로 분해(decomposition)하는 계층적 접근이다. 도메인 전문가의 분해 지식을 활용하여 탐색 공간을 축소하며, 로봇 공학에서 특히 효과적이다.

7.1 HTN의 형식적 정의

• 원시 태스크(primitive task): 직접 실행 가능한 행동
• 복합 태스크(compound task): 하위 태스크로 분해되는 추상 태스크
• 메서드(method): 복합 태스크를 하위 태스크 집합으로 분해하는 규칙

8. 계산 복잡도

9. 국제 계획 경진 대회 (IPC)

International Planning Competition(IPC)은 1998년부터 격년으로 개최되어, 계획 알고리즘의 발전을 촉진하고 표준 벤치마크를 제공한다. PDDL은 IPC의 표준 입력 언어이다.

10. 로봇 공학에서의 의의

AI 플래닝 이론은 로봇의 자율 임무 계획의 이론적 토대를 제공한다. 특히 PDDL을 통한 도메인 기술, 휴리스틱 탐색을 통한 효율적 계획 생성, HTN을 통한 계층적 태스크 분해는 ROS2 기반 PlanSys2의 핵심 메커니즘에 직접 적용된다.

11. 참고 문헌

• Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.
• Fikes, R., & Nilsson, N. (1971). “STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving.” Artificial Intelligence, 2(3-4), 189-208.
• Blum, A., & Furst, M. (1997). “Fast Planning Through Planning Graph Analysis.” Artificial Intelligence, 90(1-2), 281-300.
• Hoffmann, J. (2001). “FF: The Fast-Forward Planning System.” AI Magazine, 22(3), 57-62.
• Helmert, M. (2006). “The Fast Downward Planning System.” JAIR, 26, 191-246.
• Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach. 4th ed. Pearson.
• Nau, D., et al. (2003). “SHOP2: An HTN Planning System.” JAIR, 20, 379-404.