1314.15 효과의 정의와 역할

1. 효과의 형식적 정의

PDDL 액션 스키마에서 효과(effect)는 액션이 실행된 후 세계 상태에 발생하는 변경을 형식적으로 명시하는 구성 요소이다. 전제 조건이 “언제 액션을 수행할 수 있는가“를 규정한다면, 효과는 “액션을 수행하면 무엇이 바뀌는가“를 규정한다.

형식적으로, 액션 $a$ 의 효과 $\text{eff}(a)$ 는 두 가지 요소로 구성된다:

$\text{eff}(a) = \langle \text{eff}^+(a), \text{eff}^-(a) \rangle$

여기서 $\text{eff}^+(a)$ 는 추가 효과(add effects)로서 액션 실행 후 상태에 새로 추가되는 술어 인스턴스의 집합이고, $\text{eff}^-(a)$ 는 삭제 효과(delete effects)로서 상태에서 제거되는 술어 인스턴스의 집합이다(Fikes & Nilsson, 1971).

PDDL 구문에서 효과는 :effect 절을 통해 명시된다:

(:action move
    :parameters (?r - robot ?from - waypoint ?to - waypoint)
    :precondition (...)
    :effect (and
        (robot_at ?r ?to)            ;; 추가 효과
        (not (robot_at ?r ?from))    ;; 삭제 효과
    )
)

2. 효과의 역할

효과는 자동화된 플래닝 시스템에서 다음의 핵심적 역할을 수행한다.

2.1 상태 전이 함수의 정의

효과는 상태 공간에서의 전이 함수(transition function) $\gamma$ 를 결정한다. 상태 $s$ 에서 액션 $a$ 를 적용한 결과 상태 $s'$ 은 다음과 같이 계산된다:

$s' = \gamma(s, a) = (s \setminus \text{eff}^-(a)) \cup \text{eff}^+(a)$

이 정의에서 중요한 점은 삭제가 추가보다 먼저 적용된다는 것이다. 따라서 동일한 술어 인스턴스가 삭제 효과와 추가 효과에 동시에 포함되는 경우, 해당 술어는 결과 상태에 존재하게 된다.

2.2 전방 탐색에서의 후속 상태 생성

전방 상태 공간 탐색(forward state-space search)에서 플래너는 현재 상태에서 적용 가능한 각 액션의 효과를 적용하여 후속 상태(successor state)를 생성한다. 효과의 정의가 상태 전이의 정확성을 결정하므로, 효과의 올바른 명세는 계획의 정당성을 보장하는 핵심 요소이다.

2.3 후방 탐색에서의 회귀 계산

후방 탐색(backward search) 또는 회귀 플래닝(regression planning)에서는 목표 상태로부터 역방향으로 탐색하며, 각 액션의 효과를 역으로 적용하여 목표 달성에 필요한 선행 상태를 계산한다. 효과의 추가 부분은 목표에서 제거되고, 전제 조건이 새로운 하위 목표로 추가된다(Ghallab, Nau, & Traverso, 2004).

2.4 휴리스틱 정보의 원천

현대 플래너의 휴리스틱은 효과 정보를 분석하여 목표까지의 거리를 추정한다. 삭제 완화 휴리스틱은 효과의 삭제 부분을 무시한 완화 문제에서 목표 달성 비용을 추정하며, 이 과정에서 효과의 추가 부분이 어떤 술어를 달성할 수 있는지가 핵심 정보로 활용된다(Hoffmann & Nebel, 2001).

3. 효과의 유형

PDDL에서 지원하는 효과의 유형을 체계적으로 분류한다.

3.1 추가 효과

추가 효과(add effect)는 술어 인스턴스를 상태에 추가한다:

:effect (robot_at ?r ?to)

이는 “액션 실행 후 로봇 ?r이 위치 ?to에 있게 된다“를 의미한다. 형식적으로:

$(p \ o_1 \ \ldots \ o_n) \in s' \text{ (추가)}$

3.2 삭제 효과

삭제 효과(delete effect)는 술어 인스턴스를 상태에서 제거한다. not 연산자로 표현된다:

:effect (not (robot_at ?r ?from))

이는 “액션 실행 후 로봇 ?r이 더 이상 위치 ?from에 있지 않게 된다“를 의미한다. 형식적으로:

$(p \ o_1 \ \ldots \ o_n) \notin s' \text{ (삭제)}$

3.3 접합적 효과

다수의 추가 및 삭제 효과를 and 연산자로 결합한다:

:effect (and
    (robot_at ?r ?to)
    (not (robot_at ?r ?from))
    (visited ?to)
)

접합적 효과의 모든 구성 요소는 동시에 적용되는 것으로 간주된다. 효과 내부의 나열 순서는 의미론적으로 무관하다.

3.4 조건부 효과

조건부 효과(conditional effect)는 특정 조건이 성립할 때에만 적용되는 효과이다. when 구문으로 표현하며, :conditional-effects 요구사항이 필요하다:

:effect (and
    (not (robot_at ?r ?from))
    (robot_at ?r ?to)
    (when (carrying ?r ?obj)
        (and
            (not (object_at ?obj ?from))
            (object_at ?obj ?to)
        )
    )
)

3.5 전칭 양화 효과

forall 양화사를 사용하여 특정 타입의 모든 객체에 대해 효과를 적용한다:

:effect (and
    (area_cleared ?zone)
    (forall (?obj - debris)
        (when (in_zone ?obj ?zone)
            (not (in_zone ?obj ?zone))
        )
    )
)

3.6 수치적 효과

PDDL 2.1에서 도입된 수치적 효과는 수치 플루언트(numeric fluent)의 값을 변경한다:

:effect (and
    (robot_at ?r ?to)
    (not (robot_at ?r ?from))
    (decrease (battery_level ?r) (travel_cost ?from ?to))
    (increase (distance_traveled ?r) (path_length ?from ?to))
)

4. 효과와 프레임 문제

프레임 문제(frame problem)는 “액션의 효과로 명시되지 않은 상태 요소는 어떻게 되는가?“라는 문제이다(McCarthy & Hayes, 1969). PDDL은 STRIPS 의미론의 프레임 공리(frame axiom)를 암묵적으로 채택하여 이 문제를 해결한다:

프레임 가정: 액션의 효과에 명시적으로 포함되지 않은 술어 인스턴스는 액션 실행 전후로 변경되지 않는다.

$(p \ o_1 \ \ldots \ o_n) \notin \text{eff}^+(a) \cup \text{eff}^-(a) \Rightarrow \left[(p \ o_1 \ \ldots \ o_n) \in s \iff (p \ o_1 \ \ldots \ o_n) \in s'\right]$

이 가정 덕분에 도메인 설계자는 변경되는 술어만 효과에 명시하면 되며, 변경되지 않는 수많은 술어에 대해 “변하지 않는다“는 프레임 공리를 일일이 기술할 필요가 없다.

5. 로봇 도메인에서 효과 설계의 실용적 고려사항

5.1 상태 일관성 유지

효과를 설계할 때 상태의 일관성(consistency)이 유지되도록 해야 한다. 예를 들어, 로봇의 위치를 변경하는 액션에서 이전 위치의 삭제 효과를 누락하면, 로봇이 동시에 두 위치에 존재하는 비일관적 상태가 발생한다:

;; 비일관적 효과: 이전 위치 삭제 누락
:effect (robot_at ?r ?to)
;; 결과: robot_at ?r ?from과 robot_at ?r ?to가 동시에 참

;; 일관적 효과
:effect (and
    (not (robot_at ?r ?from))
    (robot_at ?r ?to)
)

5.2 부수 효과의 완전한 반영

물리적 행동의 모든 관련 부수 효과를 PDDL 효과에 반영해야 한다. 물체를 집는 행동은 그리퍼 상태, 물체 위치, 적재 상태 등 다수의 상태 요소를 동시에 변경한다:

(:action pick_up
    :parameters (?r - robot ?obj - object ?loc - waypoint)
    :precondition (...)
    :effect (and
        (holding ?r ?obj)            ;; 파지 상태 추가
        (not (object_at ?obj ?loc))  ;; 물체의 원래 위치 삭제
        (not (gripper_free ?r))      ;; 그리퍼 가용성 삭제
    )
)

누락된 부수 효과는 후속 액션의 전제 조건과의 불일치를 초래하여 유효하지 않은 계획이 생성될 수 있다.

6. 참고 문헌

Fikes, R. E. & Nilsson, N. J. (1971). “STRIPS: A New Approach to the Application of Theorem Proving to Problem Solving.” Artificial Intelligence, 2(3–4), 189–208.
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.
McCarthy, J. & Hayes, P. J. (1969). “Some Philosophical Problems from the Standpoint of Artificial Intelligence.” Machine Intelligence, 4, 463–502.
Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.