1314.22 효과의 결정론적 성질과 보장

1. 결정론적 효과의 정의

PDDL의 고전적 플래닝 모델에서 액션의 효과는 결정론적(deterministic)이다. 이는 동일한 상태에서 동일한 액션을 실행하면, 항상 동일한 결과 상태가 산출됨을 의미한다. 형식적으로:

\forall s, a: \gamma(s, a) \text{는 유일하게 결정됨}

여기서 \gamma는 상태 전이 함수이다. 결정론적 효과 하에서 상태 전이 함수는 전함수(total function)로서, 주어진 상태-액션 쌍에 대해 정확히 하나의 결과 상태를 반환한다.

이 성질은 PDDL의 기본 설계 원리이며, STRIPS, ADL, PDDL 2.1의 모든 표준 기능에 적용된다. 확률적 효과(probabilistic effects)는 PPDDL이나 RDDL 등의 별도 확장에서만 지원되며, 표준 PDDL의 범위에는 포함되지 않는다.

2. 결정론적 효과가 제공하는 보장

2.1 계획의 정당성 보장

결정론적 효과 하에서, 정당한(valid) 계획은 실행 시 반드시 목표 상태에 도달한다:

\pi = \langle a_1, a_2, \ldots, a_n \rangle \text{이 정당하면}, \quad s_n = \gamma(\ldots\gamma(\gamma(s_0, a_1), a_2)\ldots, a_n) \models g

여기서 g는 목표 조건이다. 이 보장은 확률적 효과 모델에서는 성립하지 않는다. 확률적 모델에서는 계획의 성공 확률만을 추정할 수 있을 뿐, 확실한 목표 달성을 보장할 수 없다.

2.2 상태 전이의 예측 가능성

결정론적 효과는 플래너가 각 상태에서 가능한 후속 상태를 정확히 계산할 수 있게 한다. 이는 전방 탐색(forward search), 후방 탐색(backward search), 양방향 탐색(bidirectional search) 등 모든 탐색 전략의 기반이 된다.

s' = (s \setminus \text{eff}^-(a)) \cup \text{eff}^+(a)

이 계산은 집합 연산으로 정확히 수행되며, 불확실성이 개입하지 않는다.

2.3 계획 검증의 용이성

결정론적 효과 하에서 계획의 정당성 검증은 다항 시간(polynomial time)에 수행 가능하다. 초기 상태에서 계획의 각 액션을 순차적으로 적용하면서 전제 조건의 충족 여부와 최종 상태의 목표 달성 여부를 확인하면 된다. 이 과정의 시간 복잡도는 O(n \cdot (k_{\text{pre}} + k_{\text{eff}}))이다. 여기서 n은 계획의 길이, k_{\text{pre}}와 k_{\text{eff}}는 각각 전제 조건과 효과의 평균 크기이다.

3. 조건부 효과와 결정론

조건부 효과가 포함된 액션도 결정론적이다. 가드 조건의 평가는 현재 상태에 의해 유일하게 결정되므로, 활성화되는 조건부 효과의 집합도 유일하게 결정된다:

\text{eff}^+(a, s) = \text{eff}^+_{\text{unc}}(a) \cup \bigcup_{\{j \mid s \models c_j\}} \text{eff}^+_j(a)

동일한 상태 s에서는 동일한 가드 조건 집합이 활성화되므로, 결과 상태도 유일하다. 조건부 효과는 효과의 상태 의존성(state-dependence)을 도입하지만, 비결정성(non-determinism)을 도입하지는 않는다.

4. 결정론적 모델의 한계

실제 로봇 시스템은 본질적으로 비결정론적이다. 센서 잡음, 액추에이터의 불확실성, 환경의 동적 변화 등으로 인해 동일한 행동이 다른 결과를 산출할 수 있다. PDDL의 결정론적 모델은 이러한 현실을 추상화하며, 다음과 같은 한계를 내포한다.

4.1 실행 실패의 비표현성

결정론적 모델에서 액션의 전제 조건이 충족되면 효과는 반드시 발생한다. 그러나 실제로는 전제 조건이 충족되더라도 액션이 실패할 수 있다(예: 파지 실패, 내비게이션 오류). 이러한 실행 실패를 PDDL의 효과 모델에서 직접 표현할 수 없다.

4.2 부분 효과의 비표현성

결정론적 모델에서 효과는 전부 적용되거나 전혀 적용되지 않는다(all-or-nothing). 부분적으로만 성공하는 행동(예: 이동 중 중간 지점에서 정지)은 모델링하기 어렵다.

4.3 관측 불확실성의 비표현성

결정론적 모델에서 세계 상태는 완전히 알려져 있다(완전 관측 가능성). 센서의 한계로 인해 상태를 정확히 파악할 수 없는 상황은 모델에 반영되지 않는다.

5. 결정론적 모델에서의 불확실성 대응 전략

결정론적 PDDL 모델의 한계를 실행 수준에서 보완하는 전략들이 존재한다.

5.1 실행 모니터링과 재계획

계획 실행 중에 실제 상태를 모니터링하고, 예상과 다른 상태가 관측되면 현재 상태를 기반으로 재계획(replanning)을 수행한다. PlanSys2는 이러한 재계획 메커니즘을 지원한다:

실행 루프:
1. 현재 상태에서 계획 생성
2. 계획의 다음 액션 실행
3. 실행 결과 관측
4. 관측 결과가 예상과 일치하면 2로 이동
5. 불일치하면 현재 상태를 갱신하고 1로 이동

5.2 보수적 전제 조건 설계

불확실성이 존재하는 조건에 대해 더 엄격한 전제 조건을 설정하여, 실패 가능성이 높은 상황에서의 액션 실행을 방지한다:

;; 보수적 전제 조건: 충분한 여유 마진 확보
:precondition (and
    (robot_at ?r ?from)
    (connected ?from ?to)
    (battery_level_high ?r)      ;; sufficient 대신 high 요구
    (no_dynamic_obstacles ?from ?to)  ;; 동적 장애물 부재 확인
)

5.3 강건한 계획 설계

여러 대안적 경로를 포함하는 조건부 계획(contingency plan)을 사전에 준비하여, 일부 액션이 실패하더라도 대안 경로를 통해 목표를 달성할 수 있도록 한다.

6. 비결정론적 확장과의 비교

FOND(Fully Observable Non-Deterministic) 플래닝에서는 효과가 가능한 결과의 집합으로 정의되며, 각 결과에 확률이 부여되지 않는다. 강한 계획(strong plan)은 어떤 결과가 발생하든 목표를 달성하는 계획이고, 약한 계획(weak plan)은 일부 결과 하에서만 목표를 달성하는 계획이다.

7. 설계 지침

1. 결정론적 모델의 한계를 인지하고 설계하라. PDDL 도메인은 실행 불확실성을 추상화한 모델임을 명확히 인식하고, 실행 수준에서의 오류 처리 메커니즘과 함께 설계해야 한다.

2. 실행 실패에 대한 대비를 실행 계층에서 구현하라. PlanSys2의 액션 노드에서 실행 성공/실패를 판단하고, 실패 시 적절한 복구 행동을 수행하도록 구현한다.

3. 결정론적 모델에서도 강건한 도메인을 설계하라. 보수적 전제 조건, 안전 마진, 대안 경로의 확보를 통해 계획의 실제 실행 성공률을 높일 수 있다.

8. 참고 문헌

• Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
• Cimatti, A., Pistore, M., Roveri, M., & Traverso, P. (2003). “Weak, Strong, and Strong Cyclic Planning via Symbolic Model Checking.” Artificial Intelligence, 147(1–2), 35–84.
• Younes, H. L. S. & Littman, M. L. (2004). “PPDDL1.0: An Extension to PDDL for Expressing Planning Domains with Probabilistic Effects.” Technical Report CMU-CS-04-167, Carnegie Mellon University.
• Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.