Chapter 1316. 고전적 플래너 알고리즘 (Classical Planner Algorithms)

Chapter 1316. 고전적 플래너 알고리즘 (Classical Planner Algorithms)

1. 개요

고전적 플래너(classical planner)는 결정론적, 완전 관측 가능, 유한 상태 공간의 플래닝 문제를 해결하는 알고리즘이다. PDDL 도메인과 문제 정의를 입력으로 받아, 초기 상태에서 목표 상태에 도달하는 액션 시퀀스(계획)를 탐색한다. 고전적 플래너는 자동화된 플래닝 연구의 핵심이며, PlanSys2를 통해 ��제 로봇 시스템에서 임무 계획을 생성하는 데 직접 활용된다.

본 장에서는 고전적 플래너 알고리즘의 이론적 기초부터 실제 로봇 시스템에서의 적용에 이��기까지 체계적으��� 다룬다.

2. 본 장의 구성

본 장은 크게 다음의 여덟 가지 주제 영역으로 구성된다.

첫째, 고전적 플래닝의 기초이다. 고전적 플래닝의 정의, 가정, 상태 공간 탐색과 계획 공간 탐색의 비교, 전방 및 후방 탐색의 원리를 다룬다.

둘째, 비제약 탐색 기반 플래너이다. ���비 우선 탐색, 깊이 우선 탐색, 반복 심화 탐색 등 기본 탐색 알고리즘의 플래닝 적용을 분석한다.

셋째, GraphPlan 알고리즘이다. 플래닝 그래프의 확장, 뮤텍스 관계의 추출, 솔루션 추출을 위한 역방향 탐색을 상세히 다룬다(Blum & Furst, 1997).

넷째, SAT 기반 플래닝이다. SATPLAN의 원리, 플래닝 문제의 명제 논리 부호화, SAT 솔버를 활용한 계획 추출을 다룬다(Kautz & Selman, 1992).

다섯째, 부분 순서 플래너이다. POCL(Partial-Order Causal Link) 알고리즘, 인과 링크, 위협 해소 메커니즘을 다룬다.

여섯째, 휴리스틱 탐색 플래너이다. 완화 문제 기반 휴리스틱, 가산 및 최대 휴리스틱, FF 플래너, Fast Downward 플래너, LAMA 플래너의 아키텍처와 알고리즘을 상세히 분석한다(Hoffmann & Nebel, 2001; Helmert, 2006; Richter & Westphal, 2010).

일곱째, 시간 및 수치 플래너이다. POPF, OPTIC 등의 시간 플래너와 수치 플래닝 지원 플래너를 다룬다.

여덟째, 플래너의 실용적 적용이다. 플래너 포트폴리���, IPC 결과 분석, 로봇 도메인에서의 성능 비교, 실시간 제약에서의 적용, ROS2와의 통합 전략을 다룬다.

3. 학습 목��

본 장을 학습한 후 다음을 수행할 수 있어야 한다:

  1. 고전적 플래닝의 이론적 기초와 주요 가정을 이해한다.
  2. 주요 플래너 알고리즘(GraphPlan, SATPLAN, POCL, FF, Fast Downward, LAMA)의 동작 원리를 설명할 수 있다.
  3. 휴리스틱 설계의 원리와 주요 휴리스틱(가산, 최대, 랜드마크, 추상화)을 이해한다.
  4. 로봇 도메인의 특성에 적합한 플래너를 선택할 수 있다.
  5. PlanSys2를 통해 고전적 플래너를 로봇 시스템에 통합할 수 있다.

4. 선행 지식

본 장의 내용을 이해하기 위해서는 PDDL의 도메인과 문제 정의, 액션의 전제 조건과 효과, 상태 전이의 개념에 대한 이해가 필요하다. 그래프 ���론, 탐색 알고리즘(BFS, DFS, A*), 명제 논리의 기초 지식이 도움이 된다.

5. 참고 문헌

  • Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
  • Blum, A. L. & Furst, M. L. (1997). “Fast Planning Through Planning Graph Analysis.” Artificial Intelligence, 90(1–2), 281–300.
  • Kautz, H. & Selman, B. (1992). “Planning as Satisfiability.” Proceedings of the 10th European Conference on Artificial Intelligence (ECAI), 359–363.
  • Hoffmann, J. & Nebel, B. (2001). “The FF Planning System: Fast Plan Generation Through Heuristic Search.” Journal of Artificial Intelligence Research, 14, 253–302.
  • 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.
  • Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.