1316.1 고전적 플래너의 정의와 범위

1. 고전적 플래너의 정의

고전적 플래너(classical planner)는 고전적 플래닝 문제(classical planning problem)를 해결하는 자동화된 알고리즘이다. 고전적 플래닝 문제는 다음의 삼중 쌍으로 형식적으로 정의된다(Ghallab, Nau, & Traverso, 2004):

\mathcal{P} = \langle \mathcal{D}, s_0, g \rangle

여기서:

• \mathcal{D} = \langle \mathcal{F}, \mathcal{A} \rangle: 도메인. \mathcal{F}는 명제(또는 술어 인스턴스)의 유한 집합, \mathcal{A}는 액션의 유한 집합이다.
• s_0 \subseteq \mathcal{F}: 초기 상태. 참인 명제의 집합이다.
• g \subseteq \mathcal{F}: 목표 조건. 달성되어야 하는 명제의 집합이다.

플래너의 출력은 계획(plan) \pi = \langle a_1, a_2, \ldots, a_n \rangle으로, 초기 상태에서 순차적으로 적용하면 목표 조건을 만족하는 상태에 도달하는 액션 시퀀스이다.

2. 고전적 플래닝의 기본 가정

고전적 플래닝은 다음의 제한적 가정(restrictive assumptions) 하에서 정의된다:

2.1 유한 상태 공간

상태 공간 S는 유한하다. 명제의 수가 n이면 가능한 상태의 수는 2^n 이하이다.

2.2 완전 관측 가능성

에이전트는 현재 상태를 완전히 관측할 수 있다. 센서의 불확실성이나 부분 관측의 문제가 배제된다.

2.3 결정론적 효과

각 액션의 효과는 결정론적이다. 동일한 상태에서 동일한 액션을 적용하면 항상 동일한 결과 상태가 산출된다.

2.4 정적 환경

환경은 에이전트의 액션에 의해서만 변화한다. 외인성 이벤트(exogenous events)가 존재하지 않는다.

2.5 단일 에이전트

단일 에이전트가 행동을 수행한다. 다중 에이전트의 동시 행동이나 적대적 행동이 배제된다.

2.6 순간적 액션

모든 액션은 즉시 완료된다. 시간의 개념이 없으며, 액션 간 병렬 실행이 존재하지 않는다.

3. 고전적 플래닝의 계산 복잡도

고전적 플래닝 문제의 계산 복잡도는 도메인의 특성에 따라 다르다:

PSPACE-완전이라는 복잡도는 최악의 경우 해결이 매우 어려움을 의미하지만, 실제 도메인에서는 휴리스틱을 활용하여 합리적인 시간 내에 해를 찾을 수 있다.

4. 고전적 플래너의 범위

4.1 포함 범위

• STRIPS 플래닝: 기본 술어, 액션, 전제 조건, 효과
• ADL 플래닝: 부정, 선언, 양화사, 조건부 효과
• 수치 플래닝: 수치 함수, 비교 연산, 수치 효과
• 비용 최적 플래닝: 메트릭 기반 비용 최적화

4.2 제외 범위 (비고전적 확장)

• 시간적 플래닝: 듀레이티브 액션, 병렬 실행 → POPF, TFD 등의 시간 플래너
• 확률적 플래닝: 불확실한 효과 → PPDDL, RDDL 플래너
• 부분 관측 플래닝: 불완전 관측 → 조건부 플래닝
• 다중 에이전트 플래닝: 복수 에이전트의 동시 행동 → MA-STRIPS 플래너

5. 고전적 플래너와 로봇 시스템

로봇 시스템에서 고전적 플래너는 임무 수준(task level)의 계획 생성에 주로 활용된다. 실제 로봇 환경은 고전적 가정(결정론적, 완전 관측)을 엄격히 만족하지 않지만, 추상적 임무 계획 수준에서는 고전적 플래너가 실용적으로 유효하다. 실행 수준의 불확실성은 재계획(replanning)과 모니터링으로 보완한다.

PlanSys2는 POPF(시간 플래너)를 기본으로 사용하지만, Fast Downward, LAMA 등의 고전적 플래너로 교체할 수 있으며, 듀레이티브 액션이 필요하지 않은 도메인에서는 고전적 플래너가 더 효율적일 수 있다.

6. 참고 문헌

• Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
• Bylander, T. (1994). “The Computational Complexity of Propositional STRIPS Planning.” Artificial Intelligence, 69(1–2), 165–204.
• Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.