1316.2 고전적 플래닝 가정과 제약 조건
1. 고전적 플래닝의 표준 가정
고전적 플래닝(classical planning)은 문제의 복잡성을 관리 가능한 수준���로 제한하기 위해 일련의 단순화 가정(simplifying assumptions)을 채택한다. 이 가정들은 이론적 분석과 효율적 알고리즘 설계의 기반이 되며, 실제 로봇 시스템에의 적용 시 한계와 보완 방안을 결정하는 핵심 요소이다(Ghallab, Nau, & Traverso, 2004).
2. 가정 1: 유한 상태 공간(Finite State Space)
세계 상태의 집합 S는 유한하다. 유한한 수의 명제(또는 술어 인스턴스)로 상태가 표현되며, 각 명제는 참 또는 거짓의 이진 값을 가진다. n개의 명제가 존재하면 가능한 상태의 수는 2^n이다.
로봇 시스템에서의 의미: 로봇의 상태를 이산적 명제로 추상화해야 한다. 연속적 위치, 관절 각도, 센서 값 등은 이산적 웨이포인트, 구성(configuration), 임계값 기반 이진 판정으로 변환되어야 한다.
3. 가정 2: 완전 관측 가능성(Full Observability)
에이전트는 현재 상태 s를 완전히 알고 있다. 초기 상태 s_0이 정확히 주어지며, 각 액션 적용 후의 결과 상태도 정확히 계산 가능하다.
로봇 시스템에서의 의미: 실제 로봇은 센서의 한계로 상태를 불완전하게 관측한다. 이 간극은 상태 추정(state estimation) 시스템과 재계획 메커니즘으로 보완한다.
4. 가정 3: 결정론적 효과(Deterministic Effects)
각 액션의 효과는 결정론적이다. 상태 s에서 액션 a를 적용하면 결과 상태 s' = \gamma(s, a)가 유일하게 결정된다.
\gamma: S \times A \rightarrow S \text{ (전함수)}
로봇 시스템에서의 의미: 파지 실패, 이동 오류, 센서 오류 등의 확률적 실패를 모델에 직접 포함할 수 없다. 실행 모니터링과 재계획으로 대응한다.
5. 가정 4: 정적 환경(Static Environment)
환경은 에이전트의 액션에 의해서만 변화한다. 외인성 이벤트(exogenous events), 다른 에이전트의 행동, 자연적 변화 등이 존재하지 않는다.
로봇 시스템에서의 의미: 사람의 이동, 문의 열림/닫힘, 기상 변화 등의 동적 ��경 변화를 모델에 포함할 수 없다. 주기적 상태 갱신과 재계획으로 보완한다.
6. 가정 5: 단일 에이전트(Single Agent)
하나의 에이전트만이 행동을 수행한다. 다중 에이전트의 동시 행동, 협력, 경쟁이 배제된다.
로봇 시스템에서의 의미: 다중 로봇 시스템에서는 모든 로봇을 단일 에이전트의 자원으로 모델링하거나, 중앙 집중식 플래너가 모든 로봇의 행동을 통합 계획하는 방식으로 대응한다.
7. 가정 6: 순간적 액션(Instantaneous Actions)
모든 액션은 시간이 소요되지 않고 즉시 완료된다. 시간의 개념이 없으며, 계획은 순차�� 시퀀스로만 표현된다.
로봇 시스템에서의 의미: 실제 로봇 행동에는 시간이 소요되므로, PDDL 2.1의 듀레이티브 액션과 시간 플래너(POPF 등)가 이 가정을 완화한다.
8. 가정의 완화와 비고전적 확장
| 가정 | 완화 방향 | PDDL 확장 | 대응 플래너 |
|---|---|---|---|
| 유한 상태 | 수치 변수 도입 | PDDL 2.1 :numeric-fluents | Metric-FF, POPF |
| 완전 관측 | 부분 관측 | PPDDL, 조건부 계획 | POND, CLG |
| 결정론적 | 확률적 효과 | PPDDL, RDDL | PROST, mGPT |
| 정적 환경 | 외인성 이벤트 | PDDL+ | SMTPlan |
| 단일 에이전트 | 다중 에이전트 | MA-PDDL | 분산 플래너 |
| 순간적 액션 | 지속 액션 | PDDL 2.1 :durative-actions | POPF, TFD |
9. 고전적 가정의 실용적 타당성
로봇 임무 계획 수준에서 고전적 가정이 ��리적인 이유:
- 추상화의 적절성: 임무 수준에서는 세밀한 물리적 불확실성이 추상화되어 결정론적 ���델이 유효하다.
- 재계획의 ��완: 실행 시 가정 위반이 발생하면 재계획으로 즉시 대응할 수 있다.
- 계산적 효율성: 고전적 가정 하에서 강력한 휴리스틱과 효율적 탐색 알고리즘을 사용할 수 있다.
- 실증적 성공: PlanSys2, ROSPlan 등의 시스템이 고전적 플래너를 활용하여 실제 로봇에서 성공적으로 임무를 수행하고 있다.
10. 참고 문헌
- 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.