1316.50 고전적 플래너 알고리즘의 향후 발전 방향

1316.50 고전적 플래너 알고리즘의 향후 발전 방향

1. 현재 수준의 한계

현대 고전적 플래너는 IPC 벤치마크에서 수백 개의 변수와 수천 개의 연산자를 가진 문제를 합리적 시간 내에 해결할 수 있으나, 실제 로봇 시스템의 요구사항에는 여전히 간극이 존재한다. 주요 한계는 계산 시간의 비예측성, 대규모 도메인에서의 확장성 부족, 불확실성 처리의 부재, 연속 변수의 제한적 처리 등이다.

2. 발전 방향 1: 기계 학습과 플래닝의 융합

2.1 학습된 휴리스틱

신경망을 사용하여 도메인 특화 휴리스틱을 학습하는 연구가 활발하다. 기존 벤치마크의 계획 데이터로 신경망을 훈련하여, 해당 도메인에 최적화된 휴리스틱을 자동으로 생성한다(Ferber et al., 2022).

2.2 정책 학습 기반 플래닝

강화 학습이나 모방 학습으로 플래닝 정책을 학습하여, 탐색 없이 직접 액션을 선택하는 접근이 연구되고 있다. 이는 실시간 제약에서의 계획 생성 속도를 극적으로 향상시킬 수 있다.

2.3 LLM 기반 도메인 생성

대규모 언어 모델(LLM)을 활용하여 자연어 기술로부터 PDDL 도메인을 자동 생성하는 연구가 진행되고 있다(Silver et al., 2024). 이는 도메인 전문가가 아닌 사용자도 플래닝 시스템을 구성할 수 있게 한다.

3. 발전 방향 2: 확장성 향상

3.1 리프팅된 플래닝

그라운딩 없이 리프팅된(매개변수화된) 표현에서 직접 탐색을 수행하는 플래너가 발전하고 있다. 이는 대규모 객체 집합을 가진 도메인에서 그라운딩의 조합적 폭발을 회피한다(Corrêa et al., 2020).

3.2 지연 평가와 증분적 탐색

필요한 시점까지 휴리스틱 평가를 지연하거나, 이전 탐색의 결과를 증분적으로 갱신하여 재계획의 효율을 향상시키는 기법이 연구되고 있다.

4. 발전 방향 3: 고전적 가정의 완화

4.1 확률적 요소의 통합

결정론적 고전 플래너의 효율성을 유지하면서 확률적 요소를 부분적으로 통합하는 하이브리드 접근이 연구되고 있다.

4.2 부분 관측 환경

완전 관측 가정을 완화하여, 센서 불확실성 하에서도 강건한 계획을 생성하는 조건부 플래닝(contingent planning)의 발전이 기대된다.

4.3 연속 변수의 확장된 지원

PDDL+의 프로세스와 이벤트, 하이브리드 오토마타 기반의 플래닝 등 연속 물리 시스템을 더 정밀하게 모델링하는 플래너의 발전이 진행되고 있다.

5. 발전 방향 4: 로봇 시스템 특화

5.1 온라인 플래닝과 실행의 통합

계획 생성과 실행을 분리하지 않고, 실행하면서 동시에 다음 단계를 계획하는 인터리빙(interleaving) 접근의 발전이 기대된다.

5.2 다중 로봇 분산 플래닝

중앙 집중식 플래닝의 확장성 한계를 극복하기 위해, 각 로봇이 독립적으로 계획하면서 협조하는 분산 플래닝 기법이 발전하고 있다.

5.3 안전 보장 플래닝

형식 검증(formal verification) 기법과 플래닝을 결합하여, 생성된 계획이 안전 속성을 반드시 만족함을 보장하는 접근이 연구되고 있다.

6. 발전 방향 5: 도구와 생태계

6.1 통합 플래닝 플랫폼

PlanSys2와 같은 ROS2 기반 플래닝 플랫폼의 발전으로, 다양한 플래너를 표준화된 인터페이스로 교체 사용할 수 있는 생태계가 확장되고 있다.

6.2 자동 도메인 분석 도구

도메인의 구조적 특성을 자동으로 분석하여 최적 플래너를 추천하거나, 도메인 모델의 오류를 검출하는 도구의 발전이 기대된다.

7. 전망

고전적 플래너 알고리즘은 60년 이상의 연구 역사를 가지며, 이론적 기반과 실용적 도구 모두에서 지속적으로 발전하고 있다. 기계 학습과의 융합, 확장성 향상, 로봇 특화 기법의 발전에 의해, 향후 더욱 복잡한 로봇 임무를 효율적으로 계획할 수 있을 것으로 전망된다.

8. 참고 문헌

  • Corrêa, A. B., Pommerening, F., Helmert, M., & Francès, G. (2020). “Lifted Successor Generation Using Query Decomposition.” Proceedings of ICAPS, 30, 65–73.
  • Ferber, P., Helmert, M., & Hoffmann, J. (2022). “Neural Network Heuristics for Classical Planning.” Proceedings of ICAPS.
  • Silver, T., Hariprasad, V., Lian, R. S., et al. (2024). “PDDL Planning with Pretrained Large Language Models.” NeurIPS 2023 Workshop on Foundation Models for Decision Making.
  • Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
  • Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.