1315.7 타입 시스템의 도메인 모델 간결화 효과

1. 간결화의 의미

도메인 모델의 간결화(simplification)는 동일한 의미론적 내용을 더 적은 구문적 요소로 표현하는 것을 의미한다. PDDL 타입 시스템은 단항 술어의 제거, 전제 조건의 축소, 초기 상태의 간소화 등 여러 측면에서 도메인 모델을 간결하게 만든다.

2. 단항 타입 술어의 제거

타입 시스템이 없는 도메인에서는 객체의 범주를 단항 술어(unary predicate)로 표현해야 한다. 타입 시스템은 이러한 단항 술어를 완전히 대체한다:

;; 타입 없이: 단항 술어 필요
(:predicates
    (is_robot ?x)
    (is_waypoint ?x)
    (is_object ?x)
    (is_ground_robot ?x)
    (is_aerial_robot ?x)
    (robot_at ?x ?y)
    (connected ?x ?y)
)

(:action move
    :parameters (?r ?from ?to)
    :precondition (and
        (is_robot ?r)
        (is_waypoint ?from)
        (is_waypoint ?to)
        (robot_at ?r ?from)
        (connected ?from ?to)
    )
    :effect (and (not (robot_at ?r ?from)) (robot_at ?r ?to))
)

;; 타입 사용: 단항 술어 불필요
(:types robot waypoint object - entity)

(:predicates
    (robot_at ?r - robot ?w - waypoint)
    (connected ?w1 - waypoint ?w2 - waypoint)
)

(:action move
    :parameters (?r - robot ?from - waypoint ?to - waypoint)
    :precondition (and
        (robot_at ?r ?from)
        (connected ?from ?to)
    )
    :effect (and (not (robot_at ?r ?from)) (robot_at ?r ?to))
)

타입 시스템 사용 시:

술어 수 감소: is_robot, is_waypoint, is_object 등 5개의 단항 술어가 제거됨
전제 조건 간결화: 각 액션에서 3개의 타입 검사 리터럴이 제거됨
가독성 향상: 매개변수의 의미가 타입으로 즉시 드러남

3. 전제 조건의 축소 효과

타입 시스템 도입으로 제거되는 전제 조건의 수를 정량적으로 분석한다.

$k$ 개의 매개변수를 가진 액션에서 타입 없이는 각 매개변수에 대해 하나의 단항 타입 술어가 전제 조건에 추가된다. $a$ 개의 액션이 있는 도메인에서 제거되는 전제 조건 리터럴의 총 수는:

$\text{제거 리터럴 수} = \sum_{i=1}^{a} k_i$

여기서 $k_i$ 는 $i$ 번째 액션의 매개변수 수이다. 5개의 액션이 각각 평균 3개의 매개변수를 가진다면, 15개의 전제 조건 리터럴이 제거된다.

4. 초기 상태의 간소화

타입 없이는 각 객체의 타입 정보를 초기 상태에 단항 술어로 명시해야 한다:

;; 타입 없이: 초기 상태에 타입 술어 나열 필요
(:init
    (is_robot robot1) (is_robot robot2)
    (is_ground_robot robot1) (is_aerial_robot robot2)
    (is_waypoint wp1) (is_waypoint wp2) (is_waypoint wp3)
    (is_object box1) (is_object box2)
    (robot_at robot1 wp1)
    (connected wp1 wp2) (connected wp2 wp3)
)

;; 타입 사용: 타입 정보는 :objects 절에서 처리
(:objects
    robot1 - ground_robot
    robot2 - aerial_robot
    wp1 wp2 wp3 - waypoint
    box1 box2 - object
)
(:init
    (robot_at robot1 wp1)
    (connected wp1 wp2) (connected wp2 wp3)
)

$n$ 개의 객체가 있고 타입 계층의 평균 깊이가 $d$ 이면, 제거되는 초기 상태 리터럴 수는 약 $n \times d$ 이다.

5. 상태 표현 크기의 축소

상태를 참인 술어 인스턴스의 집합으로 표현할 때, 타입 시스템에 의해 상태에 포함되어야 하는 단항 술어 인스턴스가 제거되므로 상태의 크기가 감소한다. 이는 다음의 연쇄적 효과를 야기한다:

메모리 사용량 감소: 각 상태의 표현에 필요한 메모리가 줄어든다.
상태 비교 비용 감소: 중복 상태 검출(duplicate state detection) 비용이 줄어든다.
해시 계산 효율 향상: 상태 해시 계산에 포함되는 리터럴 수가 줄어든다.

6. 도메인 유지 보수성 향상

타입 시스템은 도메인의 유지 보수성을 다음과 같이 향상시킨다:

새로운 객체 추가의 용이성: 새 객체를 추가할 때 :objects 절에 타입만 지정하면 되며, 단항 타입 술어를 초기 상태에 추가할 필요가 없다.
새로운 타입 추가의 용이성: 타입 계층에 새 타입을 추가하면, 기존 상위 타입의 액션이 새 타입에 자동으로 적용된다.
오류 검출의 용이성: 타입 불일치가 파서 수준에서 검출되므로, 실행 시점의 오류를 사전에 방지할 수 있다.

7. 플래닝 효율성에의 영향

타입 시스템의 간결화 효과는 플래닝 효율성에 다음과 같이 반영된다:

측면	타입 미사용	타입 사용	개선 효과
그라운딩 수	$O(n^k)$	$O(\prod n_i)$	지수적 감소
전제 조건 크기	크다 (타입 술어 포함)	작다	평가 비용 감소
상태 크기	크다 (타입 리터럴 포함)	작다	메모리 감소
휴리스틱 정보성	낮음 (잡음 포함)	높음	탐색 효율 향상

Helmert(2009)는 타입 정보의 활용이 Fast Downward 플래너의 전처리 효율을 크게 향상시킴을 보였다.

8. 참고 문헌

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.