자율 계획의 이론적 기반 (Theoretical Foundations of Autonomous Planning)

1. 개요

자율 계획의 이론적 기반은 인공지능(AI) 분야의 자동화된 계획(automated planning)에 있다. 1960년대 STRIPS에서 시작하여, PDDL 표준화, 휴리스틱 탐색 기반 계획기, 계층적 태스크 네트워크(HTN) 등으로 발전하여 왔다. 본 절에서는 자율 계획의 핵심 이론적 토대를 다룬다.

2. 고전적 계획 (Classical Planning)

2.1 가정

고전적 계획은 다음 가정에 기반한다.

1. 유한 상태: 상태 공간이 유한하다.
2. 완전 관측 가능: 현재 상태를 완전히 관측할 수 있다.
3. 결정론적: 행동의 결과가 확정적이다.
4. 정적 환경: 행동 실행 중 환경이 변하지 않는다.
5. 목표 기반: 목표 조건의 달성 여부가 성공 기준이다.

2.2 상태 공간 탐색

고전적 계획은 상태 공간에서의 경로 탐색 문제로 환원된다.

• 순방향 탐색 (Forward Search): 초기 상태에서 시작하여 행동을 적용하며 목표에 도달하는 상태를 탐색한다.
• 역방향 탐색 (Backward Search): 목표 조건에서 시작하여 해당 조건을 달성할 수 있는 행동을 역으로 추적한다.

2.3 계산 복잡도

고전적 계획의 판정 문제(plan existence)는 PSPACE-complete이다. 최적 계획(optimal planning)은 NP-hard 이상이다.

3. 휴리스틱 탐색 (Heuristic Search)

현대 계획기의 핵심은 효율적인 휴리스틱 함수를 사용한 탐색이다.

3.1 완화된 문제 (Relaxed Problem)

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

h_{\text{FF}}(s) = \lvert \text{RelaxedPlan}(s, G) \rvert

A* 기반 계획기

f(s) = g(s) + h(s)를 비용 함수로 사용하여, 최적 또는 준최적 계획을 효율적으로 탐색한다.

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

HTN 플래닝은 추상적 태스크를 구체적 행동으로 분해(decomposition)하는 방식이다.

태스크 분해

배달(robot, box, dest)
  → [이동(robot, box_location), 집기(robot, box), 이동(robot, dest), 놓기(robot, box)]

HTN의 장점

• 도메인 지식 활용: 전문가의 태스크 분해 지식을 인코딩
• 탐색 공간 축소: 계층적 분해에 의해 탐색 공간이 감소
• 자연스러운 표현: 로봇 행동의 계층적 구조를 직관적으로 표현

STRIPS에서 PDDL까지

참고 문헌

• 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.
• Ghallab, M., Nau, D., & Traverso, P. (2016). Automated Planning and Acting. Cambridge University Press.
• Nau, D., et al. (2003). “SHOP2: An HTN Planning System.” JAIR, 20, 379-404.
• Hoffmann, J. (2001). “FF: The Fast-Forward Planning System.” AI Magazine, 22(3), 57-62.