1314.7 전제 조건의 논리적 구성 방법

1314.7 전제 조건의 논리적 구성 방법

1. 전제 조건의 논리적 기반

PDDL 액션의 전제 조건은 1차 논리(first-order logic)에 기반한 논리식으로 구성된다. 전제 조건의 표현력은 도메인의 :requirements 선언에 의해 결정되며, 기본적인 STRIPS 수준의 접합식(conjunction)에서부터 완전한 ADL 수준의 복합 논리식까지 다양한 구성이 가능하다.

전제 조건을 구성하는 기본 요소는 다음의 세 가지이다:

  1. 원자 술어(atomic predicate): 가장 기본적인 구성 단위로서, 도메인에 선언된 술어의 인스턴스이다.
  2. 논리 연산자(logical connective): and, or, not, imply 등으로 원자 술어를 결합한다.
  3. 양화사(quantifier): forall, exists로 변수의 범위를 지정한다.

2. 원자 술어를 이용한 기본 전제 조건

가장 단순한 전제 조건은 단일 원자 술어로 구성된다:

:precondition (robot_at ?r ?loc)

이 전제 조건은 로봇 ?r이 위치 ?loc에 있을 때 참으로 평가된다. 단일 술어 전제 조건은 구문적으로 간결하지만, 실제 로봇 도메인에서는 여러 조건이 동시에 충족되어야 하므로 복합적 구성이 일반적이다.

3. 접합적 구성: and 연산자

and 연산자는 다수의 조건이 모두 참일 것을 요구하는 접합(conjunction)을 형성한다. 이는 PDDL에서 가장 빈번하게 사용되는 전제 조건 구성 방법이다:

:precondition (and
    (robot_at ?r ?from)
    (connected ?from ?to)
    (not (blocked ?to))
    (battery_sufficient ?r)
)

형식적으로, (\text{and} \ \phi_1 \ \phi_2 \ \ldots \ \phi_n)은 다음과 동치이다:

\phi_1 \wedge \phi_2 \wedge \cdots \wedge \phi_n

and 연산자 내부의 하위 조건은 순서에 무관하게 평가된다. 즉, 조건의 나열 순서는 의미론적으로 영향을 미치지 않는다. 그러나 가독성을 위해 관련된 조건을 의미적 그룹으로 묶어 배치하는 것이 권장된다.

and 연산자는 중첩이 가능하며, 중첩된 and는 평탄화(flattening)하여 단일 수준의 접합으로 변환할 수 있다:

;; 중첩된 and (허용되지만 불필요)
:precondition (and
    (and (robot_at ?r ?from) (connected ?from ?to))
    (and (not (blocked ?to)) (battery_sufficient ?r))
)

;; 동치인 평탄화된 형태
:precondition (and
    (robot_at ?r ?from)
    (connected ?from ?to)
    (not (blocked ?to))
    (battery_sufficient ?r)
)

4. 선언적 구성: or 연산자

or 연산자는 하위 조건 중 적어도 하나가 참일 것을 요구하는 선언(disjunction)을 형성한다. 이 연산자의 사용에는 :disjunctive-preconditions 요구사항이 필요하다:

(:requirements :strips :typing :disjunctive-preconditions)

(:action access_location
    :parameters (?r - robot ?loc - waypoint)
    :precondition (and
        (or
            (has_key ?r ?loc)
            (door_open ?loc)
            (is_public ?loc)
        )
        (adjacent ?r ?loc)
    )
    :effect (robot_at ?r ?loc)
)

형식적으로, (\text{or} \ \phi_1 \ \phi_2 \ \ldots \ \phi_n)은 다음과 동치이다:

\phi_1 \vee \phi_2 \vee \cdots \vee \phi_n

or 연산자의 사용은 플래닝의 계산 복잡도를 증가시킬 수 있다. STRIPS 플래너들은 선언적 전제 조건을 처리하기 위해 내부적으로 액션을 분할(action splitting)하거나, 선언적 조건을 접합 정규 형식(Conjunctive Normal Form, CNF) 또는 선언 정규 형식(Disjunctive Normal Form, DNF)으로 변환하는 전처리를 수행한다.

5. 부정적 구성: not 연산자

not 연산자는 조건의 논리적 부정을 표현한다. 이 연산자의 사용에는 :negative-preconditions 요구사항이 필요하다:

:precondition (and
    (robot_at ?r ?loc)
    (not (obstacle_at ?loc))
    (not (robot_busy ?r))
)

부정 연산의 평가는 닫힌 세계 가정(Closed World Assumption, CWA)에 의존한다. CWA 하에서 상태 s에 포함되지 않은 술어 인스턴스는 거짓으로 간주된다. 따라서:

s \models (\text{not} \ (p \ o_1 \ \ldots \ o_n)) \iff (p \ o_1 \ \ldots \ o_n) \notin s

not 연산자는 원자 술어에만 적용되는 것이 아니라, 복합 논리식에도 적용될 수 있다:

;; 복합식에 대한 부정 (ADL 요구)
:precondition (not (and (holding ?r ?obj1) (holding ?r ?obj2)))

그러나 복합식에 대한 부정은 플래너의 처리 복잡도를 크게 증가시킬 수 있으므로, 가능하면 원자 수준의 부정으로 분해하여 표현하는 것이 권장된다.

6. 함축적 구성: imply 연산자

imply 연산자는 논리적 함축(material implication)을 표현한다:

:precondition (and
    (robot_at ?r ?loc)
    (imply (carrying_hazmat ?r) (hazmat_zone ?loc))
)

형식적으로, (\text{imply} \ \phi \ \psi)는 다음과 동치이다:

\phi \Rightarrow \psi \equiv \neg\phi \vee \psi

이 예시에서 로봇이 위험 물질을 운반하고 있으면 현재 위치가 위험 물질 구역이어야 하며, 위험 물질을 운반하고 있지 않으면 조건은 자동으로 참이 된다.

imply 연산자는 forall 양화사와 결합하여 조건부 전칭 제약을 표현하는 데 특히 유용하다:

:precondition (forall (?d - door)
    (imply (door_in_path ?from ?to ?d) (door_open ?d))
)

이 전제 조건은 경로상의 모든 문이 열려 있을 것을 요구하되, 경로상에 없는 문의 상태에는 무관하다.

7. 복합 전제 조건의 구성 패턴

실제 로봇 도메인에서 전제 조건은 위의 기본 구성 요소들을 조합하여 복합적으로 구성된다. 다음은 빈번히 사용되는 구성 패턴이다.

7.1 자원 가용성 패턴

:precondition (and
    (robot_at ?r ?loc)
    (gripper_free ?r)
    (not (battery_low ?r))
    (not (robot_in_error ?r))
)

이 패턴은 로봇의 위치 조건, 도구 가용성, 에너지 상태, 오류 상태를 종합적으로 검사한다.

7.2 환경 조건 패턴

:precondition (and
    (robot_at ?r ?from)
    (connected ?from ?to)
    (not (blocked ?to))
    (or
        (clear_weather)
        (indoor_path ?from ?to)
    )
)

이 패턴은 환경 조건에 따른 대안적 실행 경로를 표현한다.

7.3 다중 객체 관계 패턴

:precondition (and
    (robot_at ?r ?loc)
    (object_at ?obj ?loc)
    (compatible_gripper ?r ?obj)
    (forall (?other - object)
        (imply (object_at ?other ?loc)
            (not (fragile_near ?other ?obj))
        )
    )
)

이 패턴은 특정 객체를 조작할 때 주변의 다른 객체와의 관계를 고려하는 제약을 표현한다.

8. 전제 조건 구성 시 주의사항

8.1 요구사항 선언의 일관성

사용하는 논리적 구성에 대응하는 :requirements가 반드시 선언되어야 한다. or 연산자를 사용하면서 :disjunctive-preconditions를 선언하지 않으면, 엄격한 파서에서 오류가 발생한다. :adl 요구사항은 대부분의 ADL 기능을 포괄적으로 활성화하므로, 복합 전제 조건을 사용하는 도메인에서는 :adl을 선언하는 것이 편리하다.

8.2 플래너 호환성

모든 플래너가 ADL의 전체 기능을 지원하는 것은 아니다. 특히 or, exists, imply 등의 사용은 일부 플래너에서 지원되지 않거나 비효율적으로 처리될 수 있다. 도메인 설계 시 대상 플래너의 PDDL 지원 범위를 사전에 확인하고, 가능하면 STRIPS 수준의 전제 조건으로 표현하는 것이 최대 호환성을 보장한다.

8.3 연산 복잡도

양화사와 선언적 구성이 중첩되면 전제 조건의 평가 비용이 급증할 수 있다. 특히 forall 양화사 내부에 exists가 중첩되면 평가 복잡도가 다항식 수준 이상으로 증가한다. 실용적인 도메인에서는 양화사의 중첩 깊이를 최소화하는 것이 권장된다.

9. 참고 문헌

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