1314.21 조건부 효과와 양화사의 결합

1314.21 조건부 효과와 양화사의 결합

1. 결합의 개념

조건부 효과(when)와 양화사(forall)의 결합은 PDDL ADL 수준에서 가장 강력한 효과 표현 기법 중 하나이다. 이 결합을 통해 “특정 조건을 만족하는 모든 객체에 대해 동일한 효과를 적용“하는 패턴을 간결하게 표현할 수 있다.

표준적 결합 구문은 다음과 같다:

(forall (<typed-variable-list>)
    (when <guard-condition>
        <conditional-effect>
    )
)

형식적 의미론:

\forall o \in \text{objects}(T): \left( s \models c[?x/o] \Rightarrow e[?x/o] \text{가 적용됨} \right)

이 구문은 타입 T의 모든 객체에 대해 순회하면서, 각 객체에 대해 가드 조건을 평가하고, 참인 경우에만 해당 효과를 적용한다.

2. 기본 패턴: forall-when 구조

2.1 선택적 일괄 변경

(:action decontaminate_area
    :parameters (?r - cleaning_robot ?area - zone)
    :precondition (and
        (robot_at ?r ?area)
        (decontamination_ready ?r)
    )
    :effect (and
        (area_decontaminated ?area)
        (forall (?surface - surface)
            (when (surface_in_area ?surface ?area)
                (and
                    (surface_cleaned ?surface)
                    (not (contaminated ?surface))
                )
            )
        )
    )
)

이 액션은 구역 내의 모든 표면에 대해 오염 상태를 해제한다. forall이 모든 surface 객체를 순회하고, when이 해당 구역에 위치한 ���면에 대해서만 효과를 적용한다.

2.2 조건부 상태 전파

(:action power_off_station
    :parameters (?station - workstation)
    :precondition (station_active ?station)
    :effect (and
        (not (station_active ?station))
        (station_powered_off ?station)
        (forall (?dev - device)
            (when (connected_to ?dev ?station)
                (and
                    (not (device_active ?dev))
                    (device_standby ?dev)
                )
            )
        )
    )
)

3. 복합 가드 조건의 활용

가드 조건에 접합, 부정, 다른 양화사 등의 복합 논리식을 사용할 수 있다:

3.1 접합 가드

(forall (?item - cargo)
    (when (and
            (in_vehicle ?item ?v)
            (perishable ?item)
            (not (refrigerated ?item))
          )
        (spoiled ?item)
    )
)

이 효과는 차량��� 적재된 부패성 화물 중 냉장되지 않은 것에 대해 부패 상태를 설정한다. 세 가지 조건�� 모두 참인 화물에만 적용된다.

3.2 부정 가드

(forall (?r - robot)
    (when (not (in_safe_zone ?r))
        (at_risk ?r)
    )
)

3.3 존재 양화 가드

(forall (?loc - waypoint)
    (when (exists (?obs - obstacle) (obstacle_at ?obs ?loc))
        (not (path_clear ?loc))
    )
)

이 효과는 장애물이 존재하는 모든 웨이포인트에 대해 경�� 차단 상태를 설정한다.

4. 다중 변수 양화와 조건부 효과

forall에서 복수의 변수를 동시에 양화하고, 이들 간의 관계에 기반한 조건부 효과를 정의할 수 있다:

(:action update_visibility_map
    :parameters (?r - robot ?loc - waypoint)
    :precondition (and (robot_at ?r ?loc) (sensor_active ?r))
    :effect (and
        (map_updated ?r ?loc)
        (forall (?target - waypoint)
            (when (and
                    (not (= ?target ?loc))
                    (line_of_sight ?loc ?target)
                    (within_range ?loc ?target)
                  )
                (visible_from ?loc ?target)
            )
        )
    )
)

5. ��첩 양화 효과

이론적으로 forall 내부�� 또 다른 forall을 중첩할 수 있으나, 실용적으로는 권장되지 않는다:

;; 2중 forall 중첩 (비권장: 계산 비용 높음)
(forall (?r1 - robot)
    (forall (?r2 - robot)
        (when (and
                (not (= ?r1 ?r2))
                (same_zone ?r1 ?r2)
                (comm_enabled ?r1)
                (comm_enabled ?r2)
              )
            (comm_established ?r1 ?r2)
        )
    )
)

n개의 로봇에 대해 n^2개의 조건부 효과가 생성되므로, 객체 수가 증가하면 급격�� 성능 저하가 발생한다. 이 경우 다중 변수 단일 forall로 재작성하는 것이 동등하며 더 명확하다:

(forall (?r1 ?r2 - robot)
    (when (and
            (not (= ?r1 ?r2))
            (same_zone ?r1 ?r2)
            (comm_enabled ?r1)
            (comm_enabled ?r2)
          )
        (comm_established ?r1 ?r2)
    )
)

6. 전개 과정의 상세 분석

도메인에 ���봇 {r1, r2, r3}과 웨이포인트 {wp1, wp2, wp3, wp4}가 존재하는 상황에서 다음 효과의 전개를 분석한다:

(forall (?r - robot)
    (when (robot_in_zone ?r ?zone)
        (robot_alerted ?r)
    )
)

이 효과는 다음의 3개 조건부 효과로 전개된다:

(when (robot_in_zone r1 ?zone) (robot_alerted r1))
(when (robot_in_zone r2 ?zone) (robot_alerted r2))
(when (robot_in_zone r3 ?zone) (robot_alerted r3))

현재 상태에서 r1과 r3만 해당 구역에 있다면, (robot_alerted r1)과 (robot_alerted r3)만 결과 상태에 추가된다.

7. 휴리스틱에의 영향

조건부 양화 효과는 플래너의 휴리스틱 분석에 복잡성을 추가한다. 삭제 완화 휴리스틱에서 이러한 효과는 다음과 같이 처리된다:

  1. 가드 조건이 달성 가능한 것으로 추정되면, 해당 조건부 효과의 긍정적 부분이 달성 가능한 것으로 표시된다.
  2. 삭제 효과가 무시되므로, 가드 조건이 한번 달성되면 이후에도 ��속 유효한 것으로 간주된다.
  3. forall에 의해 전개된 각 조건부 효과는 개별적으로 분석된다.

이러한 처리는 양화 조건부 효과를 가진 액션의 유용성을 과대 평가할 수 있으며, 이는 휴리스틱의 비정보적(uninformative) 추정으로 이어질 수 있다.

8. 설계 지침

  1. 가드 조건의 선택성(selectivity)을 높게 유지하라. 가드 조건이 대부분의 객체에 대해 거짓이면 실제 적용되는 효과가 적어 효율적이다.

  2. 양화 범위를 가능한 한 좁게 지정하라. 구체적인 하위 타입을 사용하여 순회 대상 객체 수를 최소화하라.

  3. 중첩 양화를 피하라. 2중 이상의 양화 중첩은 O(m^k) (여기서 k는 중첩 깊이)개의 조건부 효과를 생성한다.

  4. 대안적 모델링을 고려하라. 양화 조건부 효과를 사용하는 대신, 각 객체에 대해 별도의 액션을 정의하고 플래너가 필요한 만큼 반복 적용하도록 하는 것이 STRIPS 호환성과 플래닝 효율 면에서 유리할 수 있다.

  5. 전개된 효과의 규모를 사전에 추정하라. 도메인의 객체 수를 기준으로 전개되는 조건부 효과의 수를 계산하고, 이것이 플래너의 처리 능력 범위 내인지 확인하라.

9. 참고 문헌

  • 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.
  • Nebel, B. (2000). “On the Compilability and Expressive Power of Propositional Planning Formalisms.” Journal of Artificial Intelligence Research, 12, 271–315.
  • Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.