1314.12 존재 양화 전제 조건과 exists 연산자

1. 존재 양화의 정의

존재 양화(existential quantification)는 특정 타입의 객체 중 적어도 하나가 주어진 조건을 만족할 것을 요구하는 논리적 구성이다. PDDL에서 존재 양화는 exists 연산자로 표현되며, :existential-preconditions 또는 :adl 요구사항의 활성화가 필요하다.

구문은 다음과 같다:

(exists (<typed-variable-list>) <formula>)

형식적 의미론:

s \models (\text{exists} \ (?x - T) \ \phi(?x)) \iff \exists o \in \text{objects}(T): s \models \phi[?x/o]

여기서 \text{objects}(T)는 타입 T에 속하는 모든 객체의 집합이고, \phi[?x/o]는 변수 ?x를 객체 o로 대입한 결과이다. 해당 타입의 객체 중 하나라도 조건을 만족하면 존재 양화 전체가 참으로 평가된다.

2. 전칭 양화와의 관계

존재 양화와 전칭 양화는 논리적 이중성(duality)의 관계에 있다:

(\text{exists} \ (?x - T) \ \phi(?x)) \equiv \neg(\text{forall} \ (?x - T) \ \neg\phi(?x))

(\text{forall} \ (?x - T) \ \phi(?x)) \equiv \neg(\text{exists} \ (?x - T) \ \neg\phi(?x))

즉, “조건을 만족하는 객체가 존재한다“는 “모든 객체가 조건을 만족하지 않는 것은 아니다“와 동치이며, 그 역도 성립한다. 이러한 이중성은 양화사 간의 변환이 필요할 때 유용하다.

3. 기본 활용 예시

3.1 가용 로봇의 존재 확인

(:action assign_task
    :parameters (?t - task ?loc - waypoint)
    :precondition (and
        (task_pending ?t)
        (task_location ?t ?loc)
        (exists (?r - robot)
            (and
                (robot_available ?r)
                (robot_at ?r ?loc)
            )
        )
    )
    :effect (task_assigned ?t)
)

이 전제 조건은 태스크 위치에 가용한 로봇이 적어도 하나 존재할 것을 요구한다. exists 내부의 변수 ?r은 지역 변수(local variable)로서, 조건을 만족하는 객체가 존재하는지 여부만 판단하며 액션의 매개변수로 노출되지 않는다.

3.2 연결 가능한 경로의 존재 확인

(:action plan_route
    :parameters (?r - robot ?from - waypoint ?to - waypoint)
    :precondition (and
        (robot_at ?r ?from)
        (exists (?mid - waypoint)
            (and
                (connected ?from ?mid)
                (connected ?mid ?to)
                (not (blocked ?mid))
            )
        )
    )
    :effect (route_planned ?r ?from ?to)
)

이 예시에서 exists는 출발지와 도착지를 연결하는 차단되지 않은 중간 웨이포인트가 존재하는지를 검사한다.

3.3 필요 자원의 존재 확인

(:action begin_repair
    :parameters (?r - robot ?target - equipment)
    :precondition (and
        (robot_at ?r (location_of ?target))
        (malfunction ?target)
        (exists (?tool - repair_tool)
            (and
                (holding ?r ?tool)
                (compatible ?tool ?target)
            )
        )
    )
    :effect (and
        (not (malfunction ?target))
        (repaired ?target)
    )
)

4. exists와 매개변수의 차이

exists 양화사의 변수와 액션 매개변수는 근본적으로 다른 역할을 수행한다. 이 차이를 정확히 이해하는 것이 도메인 설계에서 중요하다.

핵심적 차이는, exists 변수에 바인딩된 구체적 객체가 무엇인지는 플래너에 의해 결정되지만, 이 정보가 계획이나 실행 시스템에 전달되지 않는다는 것이다. 따라서 효과에서 참조해야 하는 객체는 반드시 매개변수로 선언해야 한다.

;; 잘못된 설계: exists 변수를 효과에서 참조
(:action pick_any_object
    :parameters (?r - robot ?loc - waypoint)
    :precondition (and
        (robot_at ?r ?loc)
        (gripper_free ?r)
        (exists (?obj - object) (object_at ?obj ?loc))
    )
    :effect (and
        (holding ?r ?obj)     ;; 오류: ?obj는 exists 변수이므로 여기서 참조 불가
        (not (gripper_free ?r))
    )
)

;; 올바른 설계: 매개변수로 선언
(:action pick_object
    :parameters (?r - robot ?obj - object ?loc - waypoint)
    :precondition (and
        (robot_at ?r ?loc)
        (object_at ?obj ?loc)
        (gripper_free ?r)
    )
    :effect (and
        (holding ?r ?obj)
        (not (object_at ?obj ?loc))
        (not (gripper_free ?r))
    )
)

5. 존재 양화의 그라운딩

플래너 내부에서 exists 양화사는 선언(disjunction)으로 전개될 수 있다. 타입 T에 속하는 객체가 \{o_1, o_2, \ldots, o_m\}이면:

(\text{exists} \ (?x - T) \ \phi(?x)) \equiv (\text{or} \ \phi[?x/o_1] \ \phi[?x/o_2] \ \ldots \ \phi[?x/o_m])

이 전개는 exists를 or로 변환하는 것이므로, 결과적으로 선언적 전제 조건의 처리 문제로 환원된다. or를 지원하지 않는 플래너에서는 추가적인 변환이 필요하다.

6. 다중 변수 존재 양화

exists 연산자는 동시에 여러 변수를 양화할 수 있다:

(:action request_transport
    :parameters (?package - cargo ?dest - location)
    :precondition (and
        (transport_requested ?package ?dest)
        (exists (?r - robot ?v - vehicle)
            (and
                (robot_available ?r)
                (vehicle_available ?v)
                (can_operate ?r ?v)
                (cargo_capacity ?v ?package)
            )
        )
    )
    :effect (transport_assigned ?package ?dest)
)

다중 변수 존재 양화의 전개는 변수들의 데카르트 곱에 대한 선언으로 확장된다:

(\text{exists} \ (?x - T_1) \ (?y - T_2) \ \phi(?x, ?y)) \equiv \bigvee_{o_1 \in T_1, o_2 \in T_2} \phi[?x/o_1, ?y/o_2]

전개되는 선언 항의 수가 \lvert T_1 \rvert \times \lvert T_2 \rvert이므로, 다중 변수의 사용은 계산 비용을 급격히 증가시킨다.

7. exists와 forall의 결합

exists와 forall의 결합은 복잡한 다중 객체 관계를 표현할 수 있다:

;; 모든 환자에게 적어도 하나의 돌봄 로봇이 배정됨을 확인
(:action verify_coverage
    :parameters (?ward - hospital_ward)
    :precondition (and
        (ward_active ?ward)
        (forall (?p - patient)
            (imply (in_ward ?p ?ward)
                (exists (?r - care_robot)
                    (assigned_to ?r ?p)
                )
            )
        )
    )
    :effect (coverage_verified ?ward)
)

이 전제 조건은 “해당 병동의 모든 환자에 대해, 적어도 하나의 돌봄 로봇이 배정되어 있어야 한다“는 조건을 표현한다. forall 내부에 exists가 중첩되므로, 전개 시 각 환자에 대해 모든 로봇을 순회하는 이중 루프가 발생한다.

8. 휴리스틱에의 영향

가산 휴리스틱(h^{\text{add}})에서 존재 양화 전제 조건의 비용은 선언으로의 전개 후 최소 비용 항으로 추정된다:

h^{\text{add}}(\text{exists} \ (?x - T) \ \phi(?x)) = \min_{o \in \text{objects}(T)} h^{\text{add}}(\phi[?x/o])

이는 존재 양화가 “가장 쉽게 달성 가능한 대안“의 비용으로 평가됨을 의미하며, 접합적 전제 조건에 비해 낙관적인 추정을 생성하는 경향이 있다.

9. 설계 지침

1. exists는 실행에 필요한 구체적 객체를 식별할 필요가 없을 때에만 사용하라. 실행 시 해당 객체의 정체가 필요하면 매개변수로 선언해야 한다.

2. 다중 변수 존재 양화를 최소화하라. 변수 수의 증가는 전개되는 선언 항의 수를 기하급수적으로 증가시킨다.

3. exists를 매개변수로 대체할 수 있는지 우선 검토하라. 많은 경우, exists 양화사의 사용은 매개변수의 추가로 대체할 수 있으며, 이 방식이 플래너에 더 효율적으로 처리된다.

4. 플래너의 존재 양화 처리 방식을 확인하라. 일부 플래너는 exists를 내부적으로 or로 전개한 후 액션 분할을 수행하며, 이 과정에서 성능 저하가 발생할 수 있다.

10. 참고 문헌

• 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. (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.