1315.40 선호도와 제약을 위한 PDDL 3.0 기능

1. PDDL 3.0의 도입 배경

PDDL 3.0은 Gerevini와 Long(2005)이 IPC 2006을 위해 제안한 확장으로, 계획의 품질을 정량적으로 평가하기 위한 선호도(preference)와 제약(constraint) 기능을 도입하였다. 이전 PDDL 버전에서는 목표 조건이 모두 달성되기만 하면 유효한 계획이었으나, PDDL 3.0에서는 선호적 목표와 경성/연성 제약을 구분하여 계획의 품질을 다차원적으로 평가할 수 있다.

:preferences와 :constraints 요구사항의 활성화가 필요하다.

2. 선호도(Preference)

2.1 정의

선호도는 “가능하면 충족하는 것이 바람직하지만, 충족되지 않더라도 계획이 무효화되지 않는” 연성 조건(soft constraint)이다:

(:goal (and
    ;; 경성 목표: 반드시 달성
    (delivered pkg1 customer1)
    (delivered pkg2 customer2)

    ;; 선호 목표: 달성하면 바람직
    (preference p1 (robot_at robot1 base))
    (preference p2 (battery_level_high robot1))
))

2.2 구문

(preference <preference-name> <goal-formula>)

선호도에 이름(p1, p2 등)을 부여하여 메트릭에서 참조할 수 있다.

2.3 선호도와 메트릭의 결합

선호도의 충족 여부를 메트릭 표현식에 반영하여, 선호도를 많이 충족하는 계획이 높은 점수를 받도록 한다:

(:metric minimize (+
    (total_cost)
    (* 10 (is-violated p1))
    (* 5 (is-violated p2))
))

(is-violated <pref-name>)은 해당 선호도가 충족되지 않으면 1, 충족되면 0을 반환하는 특수 함수이다.

3. 경로 제약(Trajectory Constraints)

3.1 정의

경로 제약은 계획의 실행 경로(trajectory) 전체에 걸쳐 충족되어야 하는 조건이다. 이는 목표 상태뿐만 아니라 중간 상태에도 적용된다.

3.2 주요 시간 양상(Temporal Modality) 연산자

(:constraints (and
    ;; always: 모든 상태에서 참이어야 함
    (always (not (collision_occurred)))

    ;; sometime: 경로의 적어도 하나의 상태에서 참
    (sometime (robot_at robot1 checkpoint))

    ;; at-most-once: 최대 한 번만 참이 됨
    (at-most-once (emergency_mode))

    ;; sometime-after: p가 참이 된 후 언젠가 q가 참이 됨
    (sometime-after (task_started ?t) (task_completed ?t))

    ;; sometime-before: q가 참이 되기 전에 p가 참이어야 함
    (sometime-before (enter_zone ?z) (zone_cleared ?z))
))

3.3 경로 제약의 유형

연산자	의미	로봇 도메인 활용
`always`	전 경로에서 참	안전 불변 조건
`sometime`	경로 중 한 번 이상 참	체크포인트 방문
`at-most-once`	최대 한 번 참	일회성 행동 제약
`sometime-after`	p 후에 q 발생	순서 제약
`sometime-before`	q 전에 p 발생	사전 조건 제약
`always-within`	p가 참이 된 후 t 시간 내에 q	시간 제한 대응

4. 로봇 도메인에서의 활용

4.1 안전 제약

(:constraints (and
    ;; 충돌이 절대 발생하지 않아야 함
    (always (forall (?r - robot) (not (collision ?r))))

    ;; 배터리가 절대 0 이하로 떨어지지 않아야 함
    (always (forall (?r - robot) (> (battery_level ?r) 0)))
))

4.2 임무 순서 제약

(:constraints (and
    ;; 구역 진입 전 반드시 스캔 수행
    (forall (?z - restricted_zone)
        (sometime-before (robot_in_zone ?r ?z) (zone_scanned ?z)))

    ;; 배송 후 반드시 확인 수행
    (forall (?pkg - package)
        (sometime-after (delivered ?pkg) (delivery_confirmed ?pkg)))
))

4.3 선호적 행동 패턴

(:goal (and
    (all_tasks_completed)
    ;; 선호: 로봇이 기지로 복귀
    (preference return_to_base (robot_at robot1 base_station))
    ;; 선호: 배터리 잔량 50% 이상
    (preference battery_margin (>= (battery_level robot1) 50))
))

(:metric minimize (+
    (total_cost)
    (* 20 (is-violated return_to_base))
    (* 10 (is-violated battery_margin))
))

5. 플래너 지원 현황

PDDL 3.0의 선호도와 제약은 IPC 2006 및 이후 대회에서 사용되었으나, 모든 플래너가 완전히 지원하는 것은 아니다:

기능	SGPlan	LPRPG	Fast Downward
선호도	지원	부분 지원	제한적
always 제약	지원	지원	제한적
sometime 제약	지원	부분 지원	제한적
시간 양상 제약	부분 지원	제한적	제한적

6. 참고 문헌

Gerevini, A. & Long, D. (2005). “Plan Constraints and Preferences in PDDL3.” Technical Report, Department of Electronics for Automation, University of Brescia.
Gerevini, A. & Long, D. (2006). “Preferences and Soft Constraints in PDDL3.” Proceedings of the ICAPS Workshop on Planning with Preferences and Soft Constraints.
Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.