1314.24 프레임 문제와 PDDL의 대응

1314.24 프레임 문제와 PDDL의 대응

1. 프레임 문제의 정의

프레임 문제(frame problem)는 McCarthy와 Hayes(1969)가 제기한 AI의 근본적 문제로서, “액션이 세계 상태의 어떤 측면을 변경하지 않는지를 어떻게 형식적으로 명시할 것인가?“에 관한 문제이다.

직관적으로, 로봇이 방 A에서 방 B로 이동할 때, 로봇의 위치는 변경되지만 방 안에 있는 물체의 위치, 문의 열림 상태, 배터리 충전 상태 등 나머지 상태 요소는 변하지 않는다. 인간은 이러한 “변하지 않는 것“을 암묵적으로 이해하지만, 형식적 논리 체계에서는 이를 명시적으로 기술해야 한다.

상황 논법(situation calculus)에서 이 문제를 프레임 공리(frame axiom)로 해결하려 하면, 각 액션과 각 술어의 조합에 대해 “이 액션은 이 술어를 변경하지 않는다“는 공리를 일일이 기술해야 한다. n개의 액션과 m개의 술어가 있으면 O(n \times m)개의 프레임 공리가 필요하며, 이는 도메인이 커질수록 관리가 불가능해진다.

2. 대표 문제와 자격 문제

프레임 문제는 두 가지 관련 문제와 함께 논의된다.

2.1 대표 문제(Representational Frame Problem)

세계 상태의 불변 측면을 형식적으로 표현하는 문제이다. 상황 논법에서의 프레임 공리 폭발이 이 문제의 핵심이다.

2.2 추론적 프레임 문제(Inferential Frame Problem)

불변 사실을 효율적으로 추론하는 문제이다. 모든 프레임 공리를 명시적으로 나열하더라도, 이로부터 “특정 상태 요소가 변하지 않았다“는 결론을 도출하는 추론 비용이 문제가 된다.

2.3 자격 문제(Qualification Problem)

액션의 실행에 필요한 모든 전제 조건을 완전히 열거하는 것이 불가능하다는 문제이다. “로봇이 이동하려면 바퀴가 있어야 하고, 바닥이 존재해야 하고, 중력이 작용해야 하고…” 등 무한히 많은 조건이 존재할 수 있다.

3. STRIPS의 프레임 문제 해결

STRIPS(Fikes & Nilsson, 1971)는 프레임 문제에 대해 다음과 같은 실용적 해법을 제시하였다:

STRIPS 가정: 액션의 효과에 명시적으로 포함되지 않은 상태 요소는 해당 액션에 의해 변경되지 않는다.

형식적으로, 상태 s에서 액션 a를 적용한 결과 상태 s'을 계산할 때:

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

이 정의에서 \text{eff}^-(a)에 포함되지 않은 술어 인스턴스는 삭제되지 않고, \text{eff}^+(a)에 포함되지 않은 술어 인스턴스도 추가되지 않는다. 따라서 효과에 언급되지 않은 모든 상태 요소는 자동으로 보존된다:

p \notin \text{eff}^+(a) \cup \text{eff}^-(a) \Rightarrow (p \in s \iff p \in s')

이 가정은 대표 문제와 추론적 프레임 문제를 동시에 해결한다. 프레임 공리를 명시적으로 기술할 필요가 없으며(대표 문제 해결), 불변 사실의 추론이 집합 연산으로 단순화된다(추론적 문제 해결).

4. PDDL에서의 프레임 가정

PDDL은 STRIPS의 프레임 가정을 그대로 계승한다. PDDL의 모든 버전(1.2, 2.1, 3.0, 3.1)에서 이 가정이 적용되며, ADL 확장의 조건부 효과와 양화 효과에도 동일하게 적용된다.

이 가정의 실용적 의미는 다음과 같다:

  1. 효과 명세의 간결성: 도메인 설계자는 변경되는 상태만 효과에 기술하면 된다. 변경되지 않는 상태에 대한 명시적 기술이 불필요하다.

  2. 상태 표현의 효율성: 전체 상태를 다시 기술하지 않고, 효과에 의한 차분(delta)만으로 상태 전이를 계산할 수 있다.

  3. 도메인 확장의 용이성: 새로운 술어나 액션을 추가해도, 기존 액션의 효과에 새 술어가 포함되지 않으면 기존 액션의 행동이 변하지 않는다.

5. 프레임 가정의 적용 예시

다음의 도메인에서 프레임 가정의 작용을 추적한다:

(:predicates
    (robot_at ?r - robot ?w - waypoint)
    (object_at ?o - object ?w - waypoint)
    (holding ?r - robot ?o - object)
    (gripper_free ?r - robot)
    (door_open ?d - door)
)

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

초기 상태:

s_0 = \{(\text{robot\_at} \ r1 \ wp1), (\text{object\_at} \ box1 \ wp2), (\text{gripper\_free} \ r1), (\text{door\_open} \ d1)\}

(move r1 wp1 wp2) 적용 후:

s_1 = \{(\text{robot\_at} \ r1 \ wp2), (\text{object\_at} \ box1 \ wp2), (\text{gripper\_free} \ r1), (\text{door\_open} \ d1)\}

프레임 가정에 의해 (object_at box1 wp2), (gripper_free r1), (door_open d1)은 move 액션의 효과에 언급되지 않았으므로 변경 없이 보존된다.

6. 프레임 가정의 한계

6.1 간접 효과의 비표현

프레임 가정은 액션의 직접적 효과만을 고려한다. 물리적 세계에서 발생하는 간접 효과(indirect effects) 또는 파급 효과(ramification)는 자동으로 포착되지 않는다:

;; 테이블을 이동하면 테이블 위의 물체도 함께 이동해야 하나,
;; 프레임 가정에 의해 명시적으로 기술하지 않으면 물체는 원래 위치에 유지됨
(:action move_table
    :parameters (?t - table ?from ?to - waypoint)
    :precondition (table_at ?t ?from)
    :effect (and (not (table_at ?t ?from)) (table_at ?t ?to))
    ;; 문제: 테이블 위 물체의 위치가 갱신되지 않음
)

이 문제를 해결하려면 조건부 효과를 사용하여 간접 효과를 명시적으로 기술해야 한다:

:effect (and
    (not (table_at ?t ?from))
    (table_at ?t ?to)
    (forall (?obj - object)
        (when (on_table ?obj ?t)
            (and (not (object_at ?obj ?from)) (object_at ?obj ?to))
        )
    )
)

6.2 연속 프로세스의 비표현

프레임 가정은 이산적 상태 변화에 적합하지만, 시간에 따라 연속적으로 변하는 상태(예: 배터리 잔량의 점진적 감소)를 자연스럽게 표현하기 어렵다. PDDL 2.1의 지속 액션(durative-action)과 PDDL+의 프로세스(process)는 이러한 한계를 부분적으로 해소한다.

7. 참고 문헌

  • McCarthy, J. & Hayes, P. J. (1969). “Some Philosophical Problems from the Standpoint of Artificial Intelligence.” Machine Intelligence, 4, 463–502.
  • 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.
  • Reiter, R. (1991). “The Frame Problem in the Situation Calculus: A Simple Solution (Sometimes) and a Completeness Result for Goal Regression.” Artificial Intelligence and Mathematical Theory of Computation, 359–380.
  • Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
  • Shanahan, M. (1997). Solving the Frame Problem: A Mathematical Investigation of the Common Sense Law of Inertia. MIT Press.