1314.31 at start, at end, over all 조건의 의미

1. 시간 주석의 형식적 의미론

PDDL 2.1에서 듀레이티브 액션의 시간 주석(temporal annotation) at start, at end, over all은 액션의 시간적 생명 주기에서 조건이 평가되거나 효과가 적용되는 시점을 결정한다. Fox와 Long(2003)은 이들의 형식적 의미론을 다음과 같이 정의하였다.

듀레이티브 액션 $da$ 가 시작 시점 $t_s$ 에서 시작하여 종료 시점 $t_e = t_s + \text{dur}(da)$ 에 완료될 때:

$\text{at start } \phi: \quad s(t_s) \models \phi$

$\text{at end } \phi: \quad s(t_e) \models \phi$

$\text{over all } \phi: \quad \forall t \in [t_s, t_e]: s(t) \models \phi$

여기서 $s(t)$ 는 시점 $t$ 에서의 세계 상태를 나타낸다.

2. at start의 의미

at start 주석은 액션 시작의 순간에만 유효한 시간적 범위를 지정한다.

조건에서의 의미: 액션이 시작되기 직전의 상태에서 조건이 참이어야 한다. at start 조건이 거짓이면 액션은 해당 시점에 시작될 수 없다.

효과에서의 의미: 액션이 시작되는 순간에 즉시 상태가 변경된다. 이 변경은 다른 병렬 실행 중인 액션의 over all 조건이나 후속 액션의 at start 조건에 영향을 미칠 수 있다.

;; at start 조건과 효과의 시간적 관계
:condition (at start (robot_at ?r ?from))
:effect (at start (not (robot_at ?r ?from)))
;; 시점 t_s에서: 먼저 조건 확인 → 참이면 효과 적용

핵심적으로, at start 조건의 확인과 at start 효과의 적용은 동일한 시점에서 원자적으로 발생한다. 조건 확인이 효과 적용에 선행한다.

3. at end의 의미

at end 주석은 액션 종료의 순간에만 유효한 시간적 범위를 지정한다.

조건에서의 의미: 액션 종료 시점의 상태에서 조건이 참이어야 한다. at end 조건이 종료 시점에 거짓이면 액션은 정상적으로 완료될 수 없다. 이 조건은 액션 시작 시에는 평가되지 않으므로, 시작 시점에 거짓이더라도 실행 중에 다른 액션의 효과에 의해 참이 될 수 있다.

효과에서의 의미: 액션이 종료되는 순간에 상태가 변경된다.

;; at end 조건: 종료 시 도착지가 비어 있어야 함
:condition (at end (not (occupied ?to)))
;; 다른 로봇이 이동 중 ?to를 비워주면 조건이 종료 시 만족될 수 있음

at end 조건의 중요한 특성은 지연된 평가(deferred evaluation)이다. 플래너는 액션 시작 시점에 at end 조건이 아직 거짓이더라도, 종료 시점까지 다른 액션의 효과에 의해 참이 될 것으로 예측되면 액션을 시작할 수 있다. 이는 시간 플래너의 핵심적인 추론 능력이다.

4. over all의 의미

over all 주석은 액션의 전체 실행 구간에 걸쳐 유효한 시간적 범위를 지정한다.

조건에서의 의미: 액션의 시작부터 종료까지 모든 시점에서 조건이 참이어야 한다. 실행 구간 내의 어떤 시점에서든 조건이 위반되면 액션은 유효하지 않다.

:condition (over all (battery_sufficient ?r))
;; 이동 전 구간 동안 배터리가 충분해야 함
;; 다른 액션이 배터리 술어를 삭제하면 위반

효과에서의 사용: over all은 효과에서는 사용되지 않는다. 효과는 항상 특정 시점(at start 또는 at end)에 적용되며, 구간에 걸쳐 지속적으로 적용되는 효과는 PDDL 2.1에서 정의되지 않는다(연속 효과는 PDDL+에서 다룬다).

5. 시간 주석의 조합 패턴

5.1 보호 패턴

at start 효과로 자원을 잠그고, over all 조건으로 보호하며, at end 효과로 해제하는 패턴이다:

:condition (and
    (at start (tool_available ?tool))
    (over all (tool_reserved ?r ?tool))
)
:effect (and
    (at start (not (tool_available ?tool)))
    (at start (tool_reserved ?r ?tool))
    (at end (tool_available ?tool))
    (at end (not (tool_reserved ?r ?tool)))
)

5.2 점진적 진행 패턴

시작과 종료에서 서로 다른 상태를 표현하는 패턴이다:

:condition (and
    (at start (robot_at ?r ?from))
    (over all (path_safe ?from ?to))
    (at end (not (blocked ?to)))
)
:effect (and
    (at start (not (robot_at ?r ?from)))
    (at start (in_transit ?r ?from ?to))
    (at end (robot_at ?r ?to))
    (at end (not (in_transit ?r ?from ?to)))
)

5.3 동기화 패턴

at end 조건을 활용하여 병렬 액션 간의 동기화를 표현하는 패턴이다:

;; 액션 1: 물체를 전달 위치로 운반
(:durative-action deliver_to_handover
    :effect (at end (object_ready_for_handover ?obj ?loc))
)

;; 액션 2: 물체를 수령 (at end 조건으로 동기화)
(:durative-action receive_object
    :condition (at end (object_ready_for_handover ?obj ?loc))
    :effect (at end (holding ?r2 ?obj))
)

6. over all 조건의 실용적 처리

over all 조건의 연속적 유지를 정확히 검증하는 것은 계산적으로 어렵다. 연속적인 시간 구간의 모든 시점을 검사하는 것은 불가능하므로, 실제 플래너는 다음의 근사적 방법을 사용한다:

이산 시점 검사: 다른 액션의 시작/종료 시점에서만 over all 조건을 검사한다. 이 시점들이 상태 변경이 발생하는 유일한 시점이므로, 이산 검사가 대부분의 경우 정확하다.
엡실론 분리: Fox와 Long(2003)은 at start/at end 효과와 over all 조건 사이에 무한소 시간 간격 $\epsilon$ 을 도입하여, at start 효과가 적용된 직후부터 over all 조건이 유지되도록 하는 의미론을 정의하였다.

7. 참고 문헌

Fox, M. & Long, D. (2003). “PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains.” Journal of Artificial Intelligence Research, 20, 61–124.
Coles, A. J., Coles, A. I., Fox, M., & Long, D. (2010). “Forward-Chaining Partial-Order Planning.” Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 42–49.
Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.