397.22 PDDL(Planning Domain Definition Language)의 구조

1. 개요

PDDL(Planning Domain Definition Language)은 자동 계획(automated planning) 문제를 기술하기 위한 표준화된 형식 언어이다. 1998년 Drew McDermott 등이 국제 인공지능 계획 경진대회(International Planning Competition, IPC)를 위해 개발한 이 언어는 계획 문제를 **도메인 정의(domain definition)**와 **문제 정의(problem definition)**로 분리하여 기술하는 구조를 갖는다. PDDL은 STRIPS와 ADL의 표현력을 통합·확장하였으며, 로봇 임무 계획 분야에서 도메인 독립적(domain-independent) 계획기와의 표준 인터페이스로 널리 활용되고 있다.

2. PDDL의 설계 원칙

PDDL의 설계는 다음의 핵심 원칙에 기반한다.

도메인과 문제의 분리: 도메인 정의는 행동의 일반적 구조(연산자 스키마)와 술어(predicates)를 기술하고, 문제 정의는 특정 인스턴스의 초기 상태와 목표를 기술한다. 이 분리를 통해 동일한 도메인에 대해 다양한 문제 인스턴스를 독립적으로 정의할 수 있다.

점진적 표현력 확장: PDDL은 :requirements 절을 통해 계획기가 지원해야 하는 표현 기능을 명시적으로 선언한다. 이를 통해 계획기의 능력에 따라 필요한 기능만 선택적으로 사용할 수 있다.

리스프(Lisp) 유사 문법: PDDL은 리스프(Lisp) 프로그래밍 언어의 S-표현식(S-expression) 문법을 채택하여, 괄호 기반의 중첩 구조로 모든 정의를 기술한다.

3. PDDL 도메인 정의의 구조

PDDL 도메인 파일은 계획 도메인의 일반적 특성을 기술한다. 기본적인 도메인 정의의 구조는 다음과 같다.

(define (domain <도메인-이름>)
  (:requirements <요구사항-목록>)
  (:types <타입-계층>)
  (:constants <상수-목록>)
  (:predicates <술어-목록>)
  (:functions <함수-목록>)
  (:action <행동-이름>
    :parameters (<매개변수-목록>)
    :precondition (<전제-조건>)
    :effect (<효과>))
  ...
)

3.1 도메인 이름(Domain Name)

(domain <이름>) 절은 도메인의 고유 이름을 선언한다. 이 이름은 문제 정의에서 해당 도메인을 참조할 때 사용된다.

3.2 요구사항 선언(:requirements)

:requirements 절은 도메인이 사용하는 PDDL 기능을 명시적으로 선언한다. 주요 요구사항 플래그는 다음과 같다.

3.3 타입 선언(:types)

:types 절은 객체의 타입 계층(type hierarchy)을 정의한다. 타입 시스템은 연산자 매개변수의 도메인을 제한하여 기저화(grounding) 수를 줄이고, 계획기의 탐색 효율을 향상시킨다.

(:types
  robot location - object
  warehouse office - location
)

위 예시에서 robot과 location은 object의 하위 타입이며, warehouse와 office는 location의 하위 타입이다.

3.4 술어 선언(:predicates)

:predicates 절은 도메인에서 사용되는 관계형 술어(predicate)를 선언한다. 각 술어는 이름과 타입이 지정된 매개변수를 갖는다.

(:predicates
  (at ?r - robot ?l - location)
  (connected ?l1 - location ?l2 - location)
  (holding ?r - robot ?obj - object)
  (gripper-empty ?r - robot)
)

3.5 함수 선언(:functions)

:functions 절은 수치적 상태 변수(numeric state variable), 즉 유창어(fluent)를 선언한다. 이 기능은 PDDL 2.1에서 도입되었으며, :fluents 요구사항이 필요하다.

(:functions
  (battery-level ?r - robot)
  (distance ?l1 - location ?l2 - location)
  (total-cost)
)

3.6 행동 정의(:action)

:action 절은 에이전트가 수행할 수 있는 행동(연산자 스키마)을 정의한다. 각 행동은 매개변수, 전제 조건, 효과로 구성된다.

(:action move
  :parameters (?r - robot ?from - location ?to - location)
  :precondition (and
    (at ?r ?from)
    (connected ?from ?to)
    (>= (battery-level ?r) (distance ?from ?to))
  )
  :effect (and
    (at ?r ?to)
    (not (at ?r ?from))
    (decrease (battery-level ?r) (distance ?from ?to))
  )
)

이 행동 정의에서 전제 조건은 논리곱(and)으로 결합된 명제적 조건과 수치적 조건을 포함하며, 효과는 명제의 추가((at ?r ?to)), 삭제((not (at ?r ?from))), 수치 변수의 감소(decrease)를 포함한다.

4. PDDL 문제 정의의 구조

PDDL 문제 파일은 특정 계획 문제 인스턴스를 기술한다. 기본적인 문제 정의의 구조는 다음과 같다.

(define (problem <문제-이름>)
  (:domain <도메인-이름>)
  (:objects <객체-목록>)
  (:init <초기-상태>)
  (:goal <목표-조건>)
  (:metric <최적화-기준>)
)

4.1 도메인 참조(:domain)

:domain 절은 이 문제가 사용하는 도메인 정의의 이름을 지정한다. 계획기는 이 참조를 통해 해당 도메인의 술어, 타입, 행동 정의를 로드한다.

4.2 객체 선언(:objects)

:objects 절은 문제 인스턴스에 존재하는 구체적 객체들을 타입과 함께 선언한다.

(:objects
  robot1 - robot
  roomA roomB roomC - location
  box1 box2 - object
)

4.3 초기 상태 정의(:init)

:init 절은 계획 수립 시점에서 참인 모든 기저 원자(ground atom)와 수치 함수의 초기값을 나열한다. 닫힌 세계 가정에 의해 명시되지 않은 모든 명제는 거짓으로 간주한다.

(:init
  (at robot1 roomA)
  (at box1 roomA)
  (at box2 roomB)
  (connected roomA roomB)
  (connected roomB roomC)
  (connected roomB roomA)
  (connected roomC roomB)
  (gripper-empty robot1)
  (= (battery-level robot1) 100)
  (= (distance roomA roomB) 10)
  (= (distance roomB roomC) 15)
  (= (total-cost) 0)
)

4.4 목표 조건 정의(:goal)

:goal 절은 계획이 달성해야 하는 목표 조건을 논리식으로 정의한다.

(:goal (and
  (at box1 roomC)
  (at box2 roomC)
))

4.5 최적화 기준(:metric)

:metric 절은 계획의 최적화 기준을 정의한다. 계획기는 이 기준에 따라 최소 비용 또는 최대 이익을 갖는 계획을 탐색한다.

(:metric minimize (total-cost))

5. PDDL의 버전 진화

PDDL은 IPC의 요구에 따라 지속적으로 확장되어 왔다. 주요 버전의 진화 과정은 다음과 같다.

5.1 PDDL 1.2 (1998)

McDermott(1998)에 의해 제안된 초기 버전으로, STRIPS와 ADL의 표현력을 통합하였다. 명제적 전제 조건, 조건부 효과, 양화를 지원한다.

5.2 PDDL 2.1 (2003)

Fox와 Long(2003)이 제안한 이 버전은 두 가지 핵심 확장을 도입하였다.

수치 유창어(Numeric Fluents): 정수 및 실수 값을 갖는 상태 변수를 지원한다. assign, increase, decrease, scale-up, scale-down 연산자를 통해 수치 변수를 조작할 수 있다.

지속 행동(Durative Actions): 행동에 시간적 지속 기간(duration)을 부여하고, 행동의 시작(at start), 종료(at end), 전체 구간(over all) 시점에서의 전제 조건과 효과를 구분하여 정의할 수 있다.

(:durative-action move-with-duration
  :parameters (?r - robot ?from - location ?to - location)
  :duration (= ?duration (distance ?from ?to))
  :condition (and
    (at start (at ?r ?from))
    (at start (connected ?from ?to))
    (over all (>= (battery-level ?r) 0))
  )
  :effect (and
    (at start (not (at ?r ?from)))
    (at end (at ?r ?to))
    (at end (decrease (battery-level ?r) (distance ?from ?to)))
  )
)

5.3 PDDL 2.2 (2004)

Edelkamp와 Hoffmann(2004)이 도입한 확장으로, 다음의 기능을 추가하였다.

파생 술어(Derived Predicates): 다른 술어로부터 논리적으로 유도되는 술어를 정의할 수 있다. 이는 데이터로그(Datalog) 규칙과 유사하며, 상태의 추상적 속성을 선언적으로 기술하는 데 유용하다.

(:derived (reachable ?l1 - location ?l2 - location)
  (or
    (connected ?l1 ?l2)
    (exists (?l3 - location)
      (and (connected ?l1 ?l3) (reachable ?l3 ?l2)))
  )
)

시간 초기 리터럴(Timed Initial Literals): 초기 상태에서 특정 시점에 자동으로 참이 되거나 거짓이 되는 명제를 정의할 수 있다. 이는 외부 이벤트나 시간 의존적 환경 변화를 모델링하는 데 활용된다.

(:init
  (at 10 (door-open d1))
  (at 20 (not (door-open d1)))
)

5.4 PDDL 3.0 (2006)

Gerevini와 Long(2006)이 제안한 이 버전은 선호도(preferences) 와 **상태 궤적 제약(state trajectory constraints)**을 도입하였다.

선호도: 반드시 만족시키지 않아도 되지만, 만족시키면 계획의 품질이 향상되는 소프트 제약(soft constraint)을 기술한다.

(:goal (and
  (at box1 roomC)
  (preference p1 (at robot1 roomA))
))
(:metric minimize (+ (total-cost) (* 10 (is-violated p1))))

상태 궤적 제약: 계획 실행 중 상태 시퀀스가 만족해야 하는 시간적 속성을 LTL 유사 연산자(always, sometime, at-most-once, sometime-before, sometime-after)로 표현한다.

(:constraints (and
  (always (gripper-empty robot1))
  (sometime (at robot1 roomC))
))

5.5 PDDL 3.1 (2008)

PDDL 3.1은 **객체 유창어(object fluent)**를 도입하여, 함수의 반환값이 수치뿐만 아니라 객체 타입일 수 있도록 확장하였다.

(:functions
  (current-location ?r - robot) - location
)

6. PDDL의 전체 구조 요약

PDDL의 도메인 파일과 문제 파일의 관계를 다음과 같이 요약할 수 있다.

7. 로봇 임무 계획에서의 PDDL 활용

PDDL은 로봇 임무 계획 시스템에서 다음과 같은 방식으로 활용된다.

도메인 독립적 계획: 로봇의 행동 능력(이동, 조작, 감지 등)과 환경의 특성(위치 연결성, 물체 속성 등)을 PDDL 도메인 파일로 기술하면, Fast Downward, LAMA, POPF 등의 범용 계획기에 전달하여 자동으로 임무 계획을 생성할 수 있다.

ROS2 PlanSys2 통합: ROS2(Robot Operating System 2) 환경에서 PlanSys2 프레임워크는 PDDL을 기반으로 한 임무 계획 인터페이스를 제공한다. 로봇 개발자는 PDDL 도메인 파일을 작성하고, PlanSys2가 내장된 계획기(POPF 등)를 호출하여 임무 계획을 자동으로 수립하고 실행한다.

멀티 로봇 임무 계획: 다수의 로봇 객체를 PDDL 문제 파일에 선언하고, 로봇 간 자원 공유 및 작업 할당을 행동의 전제 조건과 효과로 모델링함으로써 멀티 로봇 환경의 임무 계획을 수립할 수 있다.

8. 참고 문헌

• McDermott, D. (1998). “PDDL—The Planning Domain Definition Language.” Technical Report CVC TR-98-003, Yale Center for Computational Vision and Control.
• Fox, M., & Long, D. (2003). “PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains.” Journal of Artificial Intelligence Research, 20, 61–124.
• Edelkamp, S., & Hoffmann, J. (2004). “PDDL2.2: The Language for the Classical Part of the 4th International Planning Competition.” Technical Report No. 195, Institute for Computer Science, University of Freiburg.
• Gerevini, A., & Long, D. (2006). “Preferences and Soft Constraints in PDDL3.” Proceedings of the ICAPS-2006 Workshop on Preferences and Soft Constraints in Planning, 46–53.
• Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
• Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.

v0.1.0