1315.1 PDDL 타입 시스템의 개요와 필요성

1315.1 PDDL 타입 시스템의 개요와 필요성

1. PDDL 타입 시스템의 정의

PDDL 타입 시스템(type system)은 도메인 내의 객체를 의미론적 범주로 분류하는 메커니즘이다. :typing 요구사항의 활성화를 통해 사용되며, 도메인의 :types 절에서 타입을 선언하고, 술어의 매개변수와 액션의 매개변수에 타입 제약을 부여한다.

(:requirements :strips :typing)

(:types
    robot waypoint object - entity
    ground_robot aerial_robot - robot
    package tool - object
)

이 선언에서 robot, waypoint, object는 entity의 하위 타입이며, ground_robot과 aerial_robot은 robot의 하위 타입이다. 모든 타입의 최상위(root)는 암묵적으로 object(PDDL의 기본 타입)이다.

2. 타입 시스템의 필요성

2.1 그라운딩 공간의 축소

타입이 없는 도메인에서 k개의 매개변수를 가진 액션의 그라운딩 수는 전체 객체 수 n에 대해 O(n^k)이다. 타입을 사용하면 각 매개변수가 해당 타입의 객체에만 바인딩되므로 그라운딩 수가 \prod_{i=1}^k n_i (n_i: 각 타입의 객체 수)로 감소한다.

예를 들어, 도메인에 로봇 3대, 웨이포인트 20개, 물체 10개가 있고 move 액션이 3개의 매개변수(로봇, 출발지, 도착지)를 가지는 경우:

\text{타입 미사용}: 33^3 = 35{,}937

\text{타입 사용}: 3 \times 20 \times 20 = 1{,}200

그라운딩 수가 약 30배 감소한다. 이 차이는 도메인 규모가 커질수록 더욱 극적으로 나타난다.

2.2 의미론적 오류 방지

타입 제약은 의미론적으로 부적절한 객체 바인딩을 구조적으로 차단한다:

;; 타입 없이: 웨이포인트 자리에 로봇이 바인딩될 수 있음
(:action move :parameters (?r ?from ?to) ...)
;; 가능한 바인딩: (move wp1 robot1 wp2) → 의미 없음

;; 타입 사용: 타입에 의해 부적절한 바인딩 차단
(:action move :parameters (?r - robot ?from - waypoint ?to - waypoint) ...)
;; (move wp1 robot1 wp2)는 타입 불일치로 자동 차단

2.3 도메인 가독성 향상

타입 정보는 각 매개변수의 의미를 명시적으로 전달하여, 도메인을 처음 접하는 개발자의 이해를 돕는다. 타입이 없는 도메인에서는 변수의 역할을 전제 조건의 술어 구조에서 간접적으로 추론해야 한다.

2.4 플래너 효율성 향상

플래너는 타입 정보를 활용하여 탐색 과정에서 무효한 바인딩을 사전에 제거한다. 이는 적용 가능 액션의 열거, 휴리스틱 계산, 상태 공간 탐색의 모든 단계에서 효율성을 향상시킨다(Helmert, 2009).

3. 타입 시스템의 역사적 배경

PDDL 1.2(McDermott et al., 1998)에서 :typing 요구사항으로 처음 도입되었으며, 이후 모든 PDDL 버전에서 계승되었다. 타입 시스템은 프로그래밍 언어의 정적 타입 시스템에서 영감을 받았으며, 1차 논리의 정렬 체계(sorted logic)와 유사한 역할을 수행한다.

4. STRIPS와의 비교

원래의 STRIPS 형식에는 타입 개념이 없으며, 모든 객체가 단일 유니버설 타입에 속한다. 타입의 효과를 단항 술어(unary predicate)로 모방할 수 있다:

;; 타입 시스템 사용
(:types robot waypoint - object)
(:action move :parameters (?r - robot ?from - waypoint ?to - waypoint) ...)

;; 단항 술어로 대체 (타입 없이)
(:predicates (is_robot ?x) (is_waypoint ?x))
(:action move :parameters (?r ?from ?to)
    :precondition (and (is_robot ?r) (is_waypoint ?from) (is_waypoint ?to) ...)
)

단항 술어 방식은 기능적으로 동등하지만, 전제 조건이 장황해지고, 플래너가 타입 정보를 최적화에 활용하기 어렵다. 따라서 :typing 요구사항을 사용하는 것이 실무적으로 권장된다.

5. 로봇 도메인에서의 타입 시스템 활용

로봇 도메인의 전형적인 타입 계층 구조:

(:types
    ;; 에이전트 계층
    entity - object
    robot human - entity
    ground_robot aerial_robot underwater_robot - robot

    ;; 위치 계층
    location - object
    waypoint docking_station charging_station - location
    airspace - location

    ;; 물체 계층
    item - object
    package tool sensor_unit - item

    ;; 기능 계층
    gripper - object
    parallel_gripper suction_gripper - gripper
)

이 계층 구조를 통해:

  • robot 타입의 매개변수에 ground_robot, aerial_robot, underwater_robot 모두 바인딩 가능
  • 특정 로봇 유형에만 적용되는 액션은 하위 타입으로 매개변수를 제한
  • 위치 유형에 따라 이동 가능 범위를 자연스럽게 구분

6. 참고 문헌

  • McDermott, D., Ghallab, M., Howe, A., Knoblock, C., Ram, A., Veloso, M., Weld, D., & Wilkins, D. (1998). “PDDL—The Planning Domain Definition Language.” Technical Report CVC TR-98-003, Yale Center for Computational Vision and Control.
  • Helmert, M. (2009). “Concise Finite-Domain Representations for PDDL Planning Tasks.” Artificial Intelligence, 173(5–6), 503–535.
  • Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.
  • Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.