1314.20 전칭 양화 효과와 forall 연산자

1314.20 전칭 양화 효과와 forall 연산자

1. 효과에서의 전칭 양화

PDDL의 효과 절에서 forall 연산자는 특정 타입의 모든 객체에 대해 효과를 적용하는 구문이다. 이는 전제 조건에서의 forall과 구문적으로 유사하지만, 조건의 검증이 아닌 상태 변경의 적용이라는 점에서 역할이 다르다. 효과에서의 forall 사용에는 :conditional-effects 요구사항이 필요하다.

효과에서 forall의 기본 구문은 다음과 같다:

(forall (<typed-variable-list>) <effect>)

이 구문은 지정된 타입의 모든 객체에 대해 내부 효과를 반복 적용한다. 형식적으로:

(\text{forall} \ (?x - T) \ e(?x)) \equiv \bigwedge_{o \in \text{objects}(T)} e[?x/o]

즉, 타입 T에 속하는 모든 객체 o에 대해 효과 e를 인스턴스화한 결과의 접합으로 전개된다.

2. forall과 when의 결합

효과에서 forall은 거의 항상 when과 결합하여 사용된다. forall만 단독으로 사용하면 해당 타입의 모든 객체에 대해 무조건적으로 효과가 적용되는데, 이는 대부분의 경우 의도한 바가 아니다.

;; forall + when 결합 (일반적 패턴)
(forall (?obj - object)
    (when (in_container ?obj ?container)
        (not (in_container ?obj ?container))
    )
)

;; forall 단독 사용 (모든 객체에 무조건 적용)
(forall (?obj - object)
    (marked ?obj)
)

첫 번째 예시는 컨테이너에 포함된 객체에 대해서만 in_container를 삭제하는 반면, 두 번째 예시는 모든 object 타입 객체에 대해 marked를 추가한다.

3. 실용적 활용 예시

3.1 구역 정리 액션

특정 구역 내의 모든 물체를 일괄적으로 처리하는 액션이다:

(:action clear_zone
    :parameters (?r - robot ?zone - zone)
    :precondition (and
        (robot_at ?r ?zone)
        (authorized ?r ?zone)
    )
    :effect (and
        (zone_cleared ?zone)
        (forall (?obj - movable_object)
            (when (object_in_zone ?obj ?zone)
                (and
                    (not (object_in_zone ?obj ?zone))
                    (object_in_storage ?obj)
                )
            )
        )
    )
)

이 액션은 해당 구역 내의 모든 이동 가능한 물체를 보관소로 이동시킨다. forall이 모든 movable_object에 대해 순회하고, when이 해당 구역에 실제로 존재하는 물체에 대해서만 효과를 적용한다.

3.2 방송 통신 액션

로봇이 메시지를 방송하여 통신 범위 내의 모든 로봇에 정보를 전달하는 액션이다:

(:action broadcast_message
    :parameters (?sender - robot ?msg - message ?loc - waypoint)
    :precondition (and
        (robot_at ?sender ?loc)
        (has_message ?sender ?msg)
        (comm_enabled ?sender)
    )
    :effect (and
        (message_sent ?msg)
        (forall (?receiver - robot)
            (when (and
                    (not (= ?receiver ?sender))
                    (in_comm_range ?sender ?receiver)
                    (comm_enabled ?receiver)
                  )
                (received_message ?receiver ?msg)
            )
        )
    )
)

3.3 비상 정지 액션

비상 상황에서 모든 활성 로봇을 정지시키는 액션이다:

(:action emergency_stop_all
    :parameters (?zone - zone)
    :precondition (emergency_detected ?zone)
    :effect (and
        (zone_locked ?zone)
        (forall (?r - robot)
            (when (robot_in_zone ?r ?zone)
                (and
                    (not (robot_active ?r))
                    (robot_stopped ?r)
                    (not (robot_moving ?r))
                )
            )
        )
    )
)

3.4 센서 데이터 일괄 갱신

(:action update_map
    :parameters (?r - robot ?loc - waypoint)
    :precondition (and
        (robot_at ?r ?loc)
        (mapping_mode ?r)
    )
    :effect (and
        (map_updated ?loc)
        (forall (?adj - waypoint)
            (when (adjacent ?loc ?adj)
                (area_scanned ?adj)
            )
        )
    )
)

이 액션은 로봇의 현재 위치와 인접한 모든 웨이포인트에 대해 스캔 완료 표시를 설정한다.

4. 전개와 계산 복잡도

효과에서의 forall은 그라운딩 과정에서 개별 효과로 전개된다. 타입 T에 m개의 객체가 존재하면, forall (?x - T) (when ...) 구문은 m개의 개별 조건부 효과로 변환된다:

(\text{forall} \ (?x - T) \ (\text{when} \ c(?x) \ e(?x))) \longrightarrow \begin{cases} (\text{when} \ c[?x/o_1] \ e[?x/o_1]) \\ (\text{when} \ c[?x/o_2] \ e[?x/o_2]) \\ \vdots \\ (\text{when} \ c[?x/o_m] \ e[?x/o_m]) \end{cases}

각 조건부 효과의 가드 조건이 개별적으로 평가되므로, 하나의 액션 적용에서의 효과 평가 비용은 O(m \cdot k)이다. 여기서 k는 각 가드 조건의 평가 비용이다.

다중 변수 양화의 경우 비용은 객체 수의 곱에 비례한다:

;; 2중 양화: O(m1 * m2) 개의 조건부 효과로 전개
(forall (?x - type1 ?y - type2)
    (when (relation ?x ?y) (updated ?x ?y))
)

5. 다중 변수 양화 효과

forall에서 여러 변수를 동시에 양화할 수 있다:

(:action reset_all_assignments
    :parameters (?manager - robot)
    :precondition (authorized_manager ?manager)
    :effect (and
        (assignments_reset)
        (forall (?r - worker_robot ?t - task)
            (when (assigned ?r ?t)
                (not (assigned ?r ?t))
            )
        )
    )
)

이 액션은 모든 작업 로봇-태스크 할당 관계를 해제한다. 전개 시 worker_robot 수 \times task 수만큼의 조건부 효과가 생성된다.

6. 설계 지침

  1. forall은 반드시 when과 함께 사용하는 것을 기본으로 하라. 무조건적 forall 효과는 해당 타입의 모든 객체에 대해 효과가 적용되므로, 의도하지 않은 상태 변경을 초래할 수 있다.

  2. 양화 변수의 타입을 가능한 한 구체적으로 지정하라. 넓은 타입을 사용하면 전개되는 조건부 효과의 수가 불필요하게 증가한다.

  3. 다중 변수 양화를 최소화하라. 변수 수의 증가는 전개되는 효과의 수를 기하급수적으로 증가시킨다.

  4. 가드 조건의 선택성이 높도록 설계하라. 가드 조건이 대부분의 객체에 대해 거짓으로 평가되면 실제로 적용되는 효과의 수가 줄어들어 상태 전이 계산이 효율적이다.

  5. 대안으로 액션 반복 패턴을 고려하라. forall 효과 대신, 각 객체에 대해 별도의 액션을 정의하고 플래너가 필요한 만큼 반복 적용하도록 하는 설계도 가능하다. 이 방식은 계획이 길어지지만, STRIPS 호환성을 확보한다.

7. 참고 문헌

  • 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.
  • Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
  • Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.
  • Helmert, M. (2009). “Concise Finite-Domain Representations for PDDL Planning Tasks.” Artificial Intelligence, 173(5–6), 503–535.