1314.8 긍정적 전제 조건과 부정적 전제 조건

1. 긍정적 전제 조건

긍정적 전제 조건(positive precondition)은 특정 술어 인스턴스가 현재 상태에서 참일 것을 요구하는 조건이다. 이는 PDDL 전제 조건의 가장 기본적인 형태로서, :strips 요구사항만으로 사용이 가능하다.

:precondition (and
    (robot_at ?r ?from)        ;; 긍정적 전제 조건
    (connected ?from ?to)       ;; 긍정적 전제 조건
    (battery_sufficient ?r)     ;; 긍정적 전제 조건
)

형식적으로, 긍정적 전제 조건 리터럴 (p \ o_1 \ o_2 \ \ldots \ o_n)이 상태 s에서 만족되는 조건은 다음과 같다:

s \models (p \ o_1 \ o_2 \ \ldots \ o_n) \iff (p \ o_1 \ o_2 \ \ldots \ o_n) \in s

즉, 해당 술어 인스턴스가 상태 집합의 원소로 존재하면 조건이 충족된다. STRIPS 플래닝에서 긍정적 전제 조건의 집합적 만족 판정은 부분 집합(subset) 검사로 단순화된다:

s \models \text{pre}(a) \iff \text{pre}^+(a) \subseteq s

여기서 \text{pre}^+(a)는 액션 a의 긍정적 전제 조건 리터럴들의 집합이다.

2. 부정적 전제 조건

부정적 전제 조건(negative precondition)은 특정 술어 인스턴스가 현재 상태에서 거짓일 것을 요구하는 조건이다. not 연산자를 사용하여 표현하며, :negative-preconditions 요구사항의 활성화가 필요하다:

(:requirements :strips :typing :negative-preconditions)

(:action move
    :parameters (?r - robot ?from - waypoint ?to - waypoint)
    :precondition (and
        (robot_at ?r ?from)
        (connected ?from ?to)
        (not (blocked ?to))         ;; 부정적 전제 조건
        (not (robot_busy ?r))        ;; 부정적 전제 조건
    )
    :effect (...)
)

부정적 전제 조건의 의미론은 닫힌 세계 가정(Closed World Assumption, CWA)에 의존한다. CWA 하에서 상태 s에 명시적으로 포함되지 않은 술어 인스턴스는 거짓으로 간주된다:

s \models (\text{not} \ (p \ o_1 \ \ldots \ o_n)) \iff (p \ o_1 \ \ldots \ o_n) \notin s

3. 긍정적 전제 조건과 부정적 전제 조건의 비교

두 유형의 전제 조건은 다음과 같은 측면에서 차이를 보인다:

4. 부정적 전제 조건의 필요성

순수 STRIPS에서는 부정적 전제 조건 없이도 동등한 도메인을 구성할 수 있다. 술어 p의 부정을 나타내기 위해 보조 술어 \overline{p}(예: not_blocked)를 도입하고, 두 술어가 항상 상보적으로 유지되도록 모든 관련 액션의 효과를 수정하는 방식이다:

;; 부정적 전제 조건 사용 (간결)
(:action move
    :parameters (?r - robot ?from - waypoint ?to - waypoint)
    :precondition (and
        (robot_at ?r ?from)
        (connected ?from ?to)
        (not (blocked ?to))
    )
    :effect (and (not (robot_at ?r ?from)) (robot_at ?r ?to))
)

;; 보조 술어로 대체 (장황)
(:predicates (path_clear ?w - waypoint))  ;; blocked의 보수 술어

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

보조 술어 방식은 기능적으로 동등하지만, 다음의 단점이 있다:

1. 도메인 복잡성 증가: 모든 부정적 조건에 대해 보조 술어를 추가해야 하므로, 술어 수가 증가한다.
2. 초기 상태 확장: 보조 술어의 초기 값을 문제 파일에 명시해야 하므로, 초기 상태의 크기가 증가한다.
3. 효과의 일관성 유지 부담: 원래 술어와 보조 술어를 동시에 갱신해야 하므로, 도메인 설계 오류의 가능성이 높아진다.

따라서 부정적 전제 조건의 사용은 도메인 모델의 간결성과 유지 보수성을 향상시키는 실용적 이점을 제공한다.

5. 로봇 도메인에서의 부정적 전제 조건 활용

로봇 공학 도메인에서 부정적 전제 조건은 다음과 같은 시나리오에서 특히 유용하다.

5.1 충돌 회피

(:action move
    :parameters (?r - robot ?from - waypoint ?to - waypoint)
    :precondition (and
        (robot_at ?r ?from)
        (connected ?from ?to)
        (not (occupied ?to))         ;; 목적지에 다른 로봇이 없어야 함
    )
    :effect (and
        (not (robot_at ?r ?from))
        (not (occupied ?from))
        (robot_at ?r ?to)
        (occupied ?to)
    )
)

이 패턴은 다중 로봇 환경에서 두 로봇이 동일한 위치를 점유하는 것을 방지한다.

5.2 자원 상태 확인

(:action execute_task
    :parameters (?r - robot ?t - task ?loc - waypoint)
    :precondition (and
        (robot_at ?r ?loc)
        (task_at ?t ?loc)
        (not (task_completed ?t))     ;; 이미 완료된 태스크가 아니어야 함
        (not (battery_low ?r))        ;; 배터리 부족 상태가 아니어야 함
        (not (robot_in_error ?r))     ;; 오류 상태가 아니어야 함
    )
    :effect (task_completed ?t)
)

5.3 순서 제약 표현

(:action assemble_part_b
    :parameters (?r - robot ?product - assembly)
    :precondition (and
        (robot_at ?r assembly_station)
        (part_a_installed ?product)    ;; Part A가 먼저 설치되어야 함
        (not (part_b_installed ?product))  ;; Part B가 아직 설치되지 않아야 함
        (holding ?r part_b)
    )
    :effect (and
        (part_b_installed ?product)
        (not (holding ?r part_b))
        (gripper_free ?r)
    )
)

이 패턴은 조립 공정에서 부품의 설치 순서 제약을 표현한다. 긍정적 전제 조건(part_a_installed)은 선행 단계의 완료를 확인하고, 부정적 전제 조건(not part_b_installed)은 현재 단계가 아직 수행되지 않았음을 확인한다.

6. 부정적 전제 조건과 휴리스틱의 상호 작용

삭제 완화 휴리스틱(delete relaxation heuristic)에서 부정적 전제 조건은 특수하게 처리된다. 삭제 완화 문제에서는 효과의 삭제 부분이 제거되므로, 한번 참이 된 술어는 이후 항상 참으로 유지된다. 이 경우 부정적 전제 조건 (not (p))는 초기 상태에서 p가 거짓인 경우에만 달성 가능하며, 초기 상태에서 p가 참이면 삭제 완화 문제에서 영원히 만족시킬 수 없게 된다.

이러한 특성은 부정적 전제 조건이 포함된 액션에 대해 휴리스틱이 무한대의 비용을 추정할 수 있음을 의미하며, 이는 실제로는 달성 가능한 상태임에도 플래너가 탐색을 기피하는 결과를 초래할 수 있다. 이 문제에 대응하기 위해 일부 플래너들은 부정적 전제 조건의 특수 처리 기법을 도입한다(Hoffmann & Nebel, 2001).

7. 긍정적 전제 조건과 부정적 전제 조건의 설계 지침

1. 가능하면 긍정적 전제 조건을 우선 사용하라. 긍정적 전제 조건은 모든 PDDL 플래너에서 지원되며, 휴리스틱 추정의 정확도가 높다.

2. 부정적 전제 조건은 부재(absence) 조건에 사용하라. “특정 상태가 아직 달성되지 않았음”, “장애물이 없음”, “오류가 발생하지 않았음” 등 부재를 확인하는 조건에 부정적 전제 조건이 자연스럽다.

3. 보조 술어와 부정적 전제 조건 중 택일할 때는 도메인의 전체적 복잡성을 고려하라. 부정적 조건이 소수인 경우에는 보조 술어가 불필요한 복잡성을 추가할 수 있으며, 부정적 조건이 다수인 경우에는 보조 술어가 도메인의 일관성 유지를 어렵게 만들 수 있다.

8. 참고 문헌

• Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
• Hoffmann, J. & Nebel, B. (2001). “The FF Planning System: Fast Plan Generation Through Heuristic Search.” Journal of Artificial Intelligence Research, 14, 253–302.
• 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.
• Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.