1314.10 선언적 전제 조건과 or 연산자

1. 선언의 정의와 의미론

선언(disjunction)은 다수의 논리적 조건 중 적어도 하나가 참일 것을 요구하는 논리 연산이다. PDDL에서 선언은 or 연산자로 표현되며, 이 연산자의 사용에는 :disjunctive-preconditions 요구사항의 활성화가 필요하다.

or 연산자의 구문은 다음과 같다:

(or <formula_1> <formula_2> ... <formula_n>)

형식적 의미론은 다음과 같이 정의된다:

$s \models (\text{or} \ \phi_1 \ \phi_2 \ \ldots \ \phi_n) \iff \exists i \in \{1, \ldots, n\}: s \models \phi_i$

즉, 하위 공식 중 하나 이상이 상태 $s$ 에서 참이면 선언 전체가 참이다. 모든 하위 공식이 거짓일 때에만 선언이 거짓으로 평가된다.

2. 요구사항 선언

or 연산자를 전제 조건에서 사용하려면 도메인의 :requirements 절에 다음 중 하나를 선언해야 한다:

;; 방법 1: 선언적 전제 조건만 활성화
(:requirements :strips :typing :disjunctive-preconditions)

;; 방법 2: ADL 전체 활성화 (선언적 전제 조건 포함)
(:requirements :adl)

:adl 요구사항은 :disjunctive-preconditions를 포함하는 상위 기능 집합이므로, ADL 수준의 도메인에서는 별도 선언이 불필요하다.

3. 선언적 전제 조건의 활용 시나리오

3.1 대안적 실행 조건

로봇이 특정 행동을 수행하기 위해 여러 대안적 조건 중 하나를 충족하면 되는 경우에 선언적 전제 조건이 유용하다:

(:action open_door
    :parameters (?r - robot ?d - door)
    :precondition (and
        (robot_at ?r ?d)
        (or
            (has_key ?r ?d)
            (has_master_key ?r)
            (door_unlocked ?d)
        )
    )
    :effect (door_open ?d)
)

이 예시에서 로봇은 해당 문의 열쇠를 가지고 있거나, 마스터 키를 가지고 있거나, 문이 이미 잠겨 있지 않은 경우 중 하나를 만족하면 문을 열 수 있다.

3.2 다중 경로 선택

(:action reach_target
    :parameters (?r - robot ?target - waypoint)
    :precondition (and
        (or
            (connected (current_loc ?r) ?target)
            (exists (?mid - waypoint)
                (and (connected (current_loc ?r) ?mid) (connected ?mid ?target))
            )
        )
        (not (blocked ?target))
    )
    :effect (robot_at ?r ?target)
)

3.3 능력 대체 가능성

로봇이 동일한 작업을 서로 다른 도구나 방법으로 수행할 수 있는 경우:

(:action cut_material
    :parameters (?r - robot ?material - workpiece)
    :precondition (and
        (robot_at ?r cutting_station)
        (material_positioned ?material)
        (or
            (equipped_laser_cutter ?r)
            (equipped_plasma_cutter ?r)
            (equipped_waterjet ?r)
        )
    )
    :effect (material_cut ?material)
)

4. 선언과 접합의 결합

실제 도메인에서 or와 and는 중첩되어 복합 전제 조건을 형성한다. 이때 연산자의 중첩 구조에 따라 의미가 달라진다.

4.1 and 내부의 or

가장 일반적인 패턴으로, 전체 전제 조건이 접합적이되 일부 조건이 선언적인 경우이다:

:precondition (and
    (robot_at ?r ?loc)              ;; 필수 조건
    (or (tool_a ?r) (tool_b ?r))    ;; 대안적 조건
    (not (in_error ?r))             ;; 필수 조건
)

이는 다음의 논리식과 동치이다:

$(\text{robot\_at} \ r \ \text{loc}) \wedge ((\text{tool\_a} \ r) \vee (\text{tool\_b} \ r)) \wedge \neg(\text{in\_error} \ r)$

4.2 or 내부의 and

각 대안이 복합 조건인 경우이다:

:precondition (or
    (and (indoor_path ?from ?to) (not (door_locked ?from ?to)))
    (and (outdoor_path ?from ?to) (weather_clear))
)

이는 다음과 동치이다:

$((\text{indoor\_path}) \wedge \neg(\text{door\_locked})) \vee ((\text{outdoor\_path}) \wedge (\text{weather\_clear}))$

5. 선언적 전제 조건의 정규 형식 변환

플래너의 내부 처리를 위해 선언적 전제 조건은 정규 형식으로 변환될 수 있다.

5.1 선언 정규 형식(DNF)으로의 변환

선언 정규 형식(Disjunctive Normal Form, DNF)은 접합들의 선언으로 구성된다:

$(\phi_{11} \wedge \phi_{12} \wedge \cdots) \vee (\phi_{21} \wedge \phi_{22} \wedge \cdots) \vee \cdots$

전제 조건을 DNF로 변환하면, 각 선언 항(disjunct)을 별도의 STRIPS 스타일 전제 조건으로 처리할 수 있다. 이는 or를 지원하지 않는 플래너에서 선언적 전제 조건을 처리하는 표준적 방법이다.

5.2 액션 분할에 의한 선언 제거

선언적 전제 조건을 가진 액션은 각 선언 항에 대응하는 별도의 액션으로 분할할 수 있다:

;; 원래 액션 (선언적 전제 조건)
(:action open_door
    :parameters (?r - robot ?d - door)
    :precondition (and
        (robot_at ?r ?d)
        (or (has_key ?r ?d) (door_unlocked ?d))
    )
    :effect (door_open ?d)
)

;; 분할된 액션 1
(:action open_door_with_key
    :parameters (?r - robot ?d - door)
    :precondition (and
        (robot_at ?r ?d)
        (has_key ?r ?d)
    )
    :effect (door_open ?d)
)

;; 분할된 액션 2
(:action open_unlocked_door
    :parameters (?r - robot ?d - door)
    :precondition (and
        (robot_at ?r ?d)
        (door_unlocked ?d)
    )
    :effect (door_open ?d)
)

이 변환은 의미론적으로 동등하며, 분할된 각 액션은 순수 STRIPS 전제 조건만을 사용한다. 그러나 액션의 수가 증가하고, 효과가 중복 정의되어야 하는 단점이 있다.

6. 선언적 전제 조건과 플래닝 복잡도

선언적 전제 조건의 도입은 플래닝의 계산 복잡도에 영향을 미친다.

6.1 적용 가능성 판정의 복잡도

순수 접합적 전제 조건의 적용 가능성 판정은 다항 시간(polynomial time)에 수행 가능하지만, 선언적 전제 조건이 포함되면 일반적인 경우 NP-완전(NP-complete)에 해당할 수 있다. 그러나 실제 PDDL 도메인에서 선언의 크기는 제한적이므로, 실용적인 성능 저하는 통상 미미하다.

6.2 휴리스틱에의 영향

선언적 전제 조건은 휴리스틱 추정에도 영향을 미친다. 가산 휴리스틱( $h^{\text{add}}$ )에서 선언 조건의 비용은 각 대안의 최소 비용으로 추정된다:

$h^{\text{add}}(\text{or} \ \phi_1 \ \ldots \ \phi_n) = \min_{i \in \{1,\ldots,n\}} h^{\text{add}}(\phi_i)$

이는 선언적 전제 조건이 접합적 전제 조건에 비해 더 낮은 휴리스틱 비용을 가지게 되어, 플래너가 해당 액션을 우선적으로 탐색하도록 유도할 수 있음을 의미한다.

7. 플래너 호환성

모든 PDDL 플래너가 선언적 전제 조건을 지원하는 것은 아니다. 특히 STRIPS 전용 플래너들은 or 연산자를 처리할 수 없다. 주요 플래너의 지원 현황은 다음과 같다:

플래너	선언적 전제 조건 지원
FF	지원 (DNF 변환을 통해)
Fast Downward	지원 (전처리 단계에서 변환)
POPF	제한적 지원
LAMA	지원
Madagascar	미지원 (SAT 기반 플래너)

선언적 전제 조건의 사용을 결정할 때는 대상 플래너의 지원 여부를 사전에 확인해야 한다. 최대 호환성을 확보하려면 액션 분할을 통해 or를 제거하는 방식이 안전하다.

8. 설계 시 고려사항

선언의 남용을 피하라. 지나치게 많은 대안을 하나의 or에 포함하면 도메인의 가독성이 저하되고 플래닝 효율이 감소할 수 있다. 대안의 수가 많은 경우, 도메인의 술어 구조를 재설계하여 대안을 줄이는 것이 바람직하다.
선언과 접합의 상호 변환을 고려하라. 분배 법칙에 의해 접합과 선언은 상호 변환이 가능하지만, 변환 과정에서 공식의 크기가 지수적으로 증가할 수 있다. 원래 형태가 더 간결한 경우에는 변환하지 않는 것이 좋다.
PlanSys2 환경에서의 호환성을 확인하라. PlanSys2가 사용하는 플래너(예: POPF)의 ADL 지원 범위에 따라 선언적 전제 조건의 사용 가능 여부가 결정된다. 호환성 문제가 발생하면 액션 분할 기법으로 대응할 수 있다.

9. 참고 문헌

Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
Pednault, E. P. D. (1989). “ADL: Exploring the Middle Ground Between STRIPS and the Situation Calculus.” Proceedings of the 1st International Conference on Principles of Knowledge Representation and Reasoning (KR), 324–332.
Helmert, M. (2006). “The Fast Downward Planning System.” Journal of Artificial Intelligence Research, 26, 191–246.
Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.