1314.29 듀레이티브 액션의 구조와 정의

1. 듀레이티브 액션의 개념

듀레이티브 액션(durative-action)은 PDDL 2.1에서 도입된 확장으로서, 실행에 시간이 소요되는 행동을 모델링한다(Fox & Long, 2003). 고전적 PDDL의 순간적 액션(instantaneous action)과 달리, 듀레이티브 액션은 시작 시점, 진행 구간, 종료 시점을 구분하여 각 시점에 서로 다른 조건과 효과를 지정할 수 있다.

이 확장은 :durative-actions 요구사항의 활성화를 필요로 한다:

(:requirements :strips :typing :durative-actions)

2. 구문 구조

듀레이티브 액션의 기본 구문은 다음과 같다:

(:durative-action <action-name>
    :parameters (<typed-variable-list>)
    :duration (= ?duration <duration-expression>)
    :condition (and
        <timed-conditions>
    )
    :effect (and
        <timed-effects>
    )
)

고전적 액션과의 주요 구문적 차이는 다음과 같다:

3. 지속 시간의 정의

:duration 절은 액션의 지속 시간을 명시한다. 가장 기본적인 형태는 고정 지속 시간이다:

:duration (= ?duration 10)

지속 시간은 수치 표현식으로 정의될 수 있으며, 매개변수에 의존하는 동적 지속 시간도 가능하다:

;; 거리에 따른 동적 지속 시간
:duration (= ?duration (distance ?from ?to))

;; 지속 시간 범위 제약
:duration (and (>= ?duration 5) (<= ?duration 20))

지속 시간 변수 ?duration은 시스템이 자동으로 제공하는 예약 변수이며, 명시적으로 선언할 필요가 없다.

4. 시간 조건

듀레이티브 액션의 조건은 시간 주석(temporal annotation)에 따라 세 가지 유형으로 분류된다:

4.1 at start 조건

액션 시작 시점에만 평가되는 조건이다:

(at start (robot_at ?r ?from))

4.2 at end 조건

액션 종료 시점에만 평가되는 조건이다:

(at end (path_clear ?to))

4.3 over all 조건

액션의 전체 실행 구간 동안 지속적으로 유지되어야 하는 불변 조건(invariant condition)이다:

(over all (battery_sufficient ?r))

5. 시간 효과

효과도 시간 주석에 따라 분류된다:

5.1 at start 효과

액션 시작 시점에 즉시 적용되는 효과이다:

(at start (not (robot_at ?r ?from)))
(at start (moving ?r))

5.2 at end 효과

액션 종료 시점에 적용되는 효과이다:

(at end (robot_at ?r ?to))
(at end (not (moving ?r)))

6. 완전한 듀레이티브 액션 예시

6.1 로봇 이동 액션

(:durative-action move
    :parameters (?r - robot ?from - waypoint ?to - waypoint)
    :duration (= ?duration (travel_time ?from ?to))
    :condition (and
        (at start (robot_at ?r ?from))
        (at start (connected ?from ?to))
        (over all (battery_sufficient ?r))
        (at end (not (blocked ?to)))
    )
    :effect (and
        (at start (not (robot_at ?r ?from)))
        (at start (moving ?r))
        (at start (not (location_free ?to)))
        (at end (robot_at ?r ?to))
        (at end (not (moving ?r)))
        (at end (location_free ?from))
    )
)

이 정의에서:

• 시작 시 로봇이 출발지에 있어야 하고, 출발지를 떠난다.
• 이동 중 배터리가 충분해야 한다(불변 조건).
• 종료 시 도착지가 차단되지 않아야 하고, 로봇이 도착한다.

6.2 물체 파지 액션

(:durative-action pick_up
    :parameters (?r - robot ?obj - object ?loc - waypoint)
    :duration (= ?duration 5)
    :condition (and
        (at start (robot_at ?r ?loc))
        (at start (object_at ?obj ?loc))
        (at start (gripper_free ?r))
        (over all (robot_at ?r ?loc))
    )
    :effect (and
        (at start (not (gripper_free ?r)))
        (at end (holding ?r ?obj))
        (at end (not (object_at ?obj ?loc)))
    )
)

7. 듀레이티브 액션의 의미론

듀레이티브 액션 da는 형식적으로 시작 시점 t_s에서 시작하여 종료 시점 t_e = t_s + \text{dur}(da)에 완료되는 행동으로 정의된다:

1. 시작 시점 t_s: at start 조건이 평가되고, at start 효과가 적용된다.
2. 실행 구간 [t_s, t_e]: over all 조건이 전 구간에 걸쳐 유지되어야 한다.
3. 종료 시점 t_e: at end 조건이 평가되고, at end 효과가 적용된다.

8. 병렬 실행과 시간적 유연성

듀레이티브 액션의 핵심적 이점은 시간적으로 중첩 가능한 액션의 병렬 실행을 표현할 수 있다는 것이다. 두 듀레이티브 액션이 상호 간섭하지 않으면, 시간적으로 중첩하여 실행할 수 있다:

시간축:
로봇1 이동: [====move(r1, wp1, wp2)====]
로봇2 이동:       [====move(r2, wp3, wp4)====]
                                      [==pick_up(r2, box1, wp4)==]

이러한 병렬 실행은 다중 로봇 시스템에서 전체 임무 수행 시간을 단축하는 데 필수적이다. PlanSys2는 시간 플래너(예: POPF)를 통해 이러한 병렬 계획을 생성하고, Executor 노드를 통해 병렬로 실행한다.

9. 순간적 액션으로의 변환

듀레이티브 액션은 개념적으로 두 개의 순간적 액션(시작 액션과 종료 액션)과 하나의 불변 조건으로 분해될 수 있다:

• 시작 액션: at start 조건을 전제 조건으로, at start 효과를 효과로 갖는 순간적 액션
• 종료 액션: at end 조건을 전제 조건으로, at end 효과를 효과로 갖는 순간적 액션
• 불변 조건: over all 조건이 두 액션 사이의 모든 시점에서 유지

이 분해는 일부 플래너의 내부 처리 방식에 해당하지만, 불변 조건의 연속적 유지를 보장하는 것은 비자명한 문제이다.

10. 참고 문헌

• Fox, M. & Long, D. (2003). “PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains.” Journal of Artificial Intelligence Research, 20, 61–124.
• Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
• 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.