1314.9 접합적 전제 조건과 and 연산자

1314.9 접합적 전제 조건과 and 연산자

1. 접합의 정의와 의미론

접합(conjunction)은 다수의 논리적 조건이 모두 동시에 참일 것을 요구하는 논리 연산이다. PDDL에서 접합은 and 연산자로 표현되며, 이는 PDDL 전제 조건에서 가장 기본적이고 빈번하게 사용되는 구성 방식이다.

and 연산자의 구문은 다음과 같다:

(and <formula_1> <formula_2> ... <formula_n>)

형식적 의미론은 다음과 같이 정의된다. 상태 s에서 접합 공식의 평가:

s \models (\text{and} \ \phi_1 \ \phi_2 \ \ldots \ \phi_n) \iff \forall i \in \{1, \ldots, n\}: s \models \phi_i

즉, 모든 하위 공식 \phi_i가 상태 s에서 참일 때에만 접합 공식 전체가 참이다. 하위 공식 중 하나라도 거짓이면 접합 전체가 거짓으로 평가된다.

2. STRIPS에서의 접합적 전제 조건

STRIPS 의미론에서 전제 조건은 긍정적 리터럴의 접합으로 제한된다. 이는 전제 조건이 다음의 형태만 취할 수 있음을 의미한다:

:precondition (and
    (p1 ?x1 ?y1)
    (p2 ?x2)
    (p3 ?x3 ?y3 ?z3)
)

이 경우, 전제 조건의 만족 여부는 집합 포함(subset) 검사로 단순화된다:

s \models \text{pre}(a) \iff \{(p_1 \ o_1 \ o_1'), (p_2 \ o_2), (p_3 \ o_3 \ o_3' \ o_3'')\} \subseteq s

이러한 단순화는 STRIPS 플래너의 효율적 구현을 가능하게 하며, 상태에서의 적용 가능한 액션 열거가 해시 테이블 기반의 상수 시간 조회로 수행될 수 있다.

3. and 연산자의 구문적 특성

3.1 하위 공식의 순서 무관성

and 연산자 내부의 하위 공식은 순서에 무관하게 평가된다. 다음의 두 전제 조건은 의미론적으로 동치이다:

;; 순서 1
:precondition (and
    (robot_at ?r ?from)
    (connected ?from ?to)
    (gripper_free ?r)
)

;; 순서 2 (동치)
:precondition (and
    (gripper_free ?r)
    (robot_at ?r ?from)
    (connected ?from ?to)
)

그러나 가독성을 위해 논리적으로 관련된 조건을 그룹화하여 배치하는 것이 권장된다. 일반적인 관례는 에이전트 상태 조건, 대상 객체 조건, 환경 조건의 순서로 나열하는 것이다.

3.2 단일 조건의 처리

전제 조건이 단일 리터럴로 구성되는 경우, and 연산자를 생략할 수 있다:

;; 단일 리터럴: and 생략 가능
:precondition (robot_at ?r ?loc)

;; 동치: and로 감싸도 무방
:precondition (and (robot_at ?r ?loc))

3.3 빈 접합

(and)와 같이 하위 공식이 없는 빈 접합은 논리적으로 항진식(tautology)으로 간주되어, 모든 상태에서 참으로 평가된다. 이는 전제 조건이 없는 액션(무조건 적용 가능한 액션)을 표현하는 데 사용할 수 있으나, 실제 도메인에서는 :precondition 절 자체를 생략하는 것이 더 명확하다.

3.4 중첩된 and의 평탄화

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

(\text{and} \ (\text{and} \ \phi_1 \ \phi_2) \ (\text{and} \ \phi_3 \ \phi_4)) \equiv (\text{and} \ \phi_1 \ \phi_2 \ \phi_3 \ \phi_4)

이는 접합 연산의 결합 법칙(associativity)에 의한 것이다. 대부분의 PDDL 파서와 플래너는 내부적으로 이 평탄화를 자동 수행한다.

4. 접합적 전제 조건의 구성 패턴

로봇 도메인에서 접합적 전제 조건의 주요 구성 패턴을 분석한다.

4.1 위치-행동 패턴

로봇이 특정 위치에서 특정 행동을 수행하기 위한 기본 패턴이다:

(:action inspect_object
    :parameters (?r - robot ?obj - object ?loc - waypoint)
    :precondition (and
        (robot_at ?r ?loc)           ;; 위치 조건
        (object_at ?obj ?loc)         ;; 대상 조건
        (sensor_active ?r)            ;; 능력 조건
        (not (already_inspected ?obj)) ;; 상태 조건
    )
    :effect (already_inspected ?obj)
)

4.2 자원-행동 패턴

행동 수행에 필요한 다중 자원의 가용성을 접합적으로 확인하는 패턴이다:

(:action weld_joint
    :parameters (?r - robot ?joint - weld_point ?part - component)
    :precondition (and
        (robot_at ?r welding_station)
        (part_positioned ?part ?joint)
        (welder_equipped ?r)
        (gas_available)
        (power_on)
        (not (weld_complete ?joint))
    )
    :effect (and
        (weld_complete ?joint)
        (not (gas_available))   ;; 자원 소모 반영
    )
)

4.3 순서 의존성 패턴

여러 단계로 구성된 공정에서 선행 단계의 완료를 접합적으로 확인하는 패턴이다:

(:action final_assembly
    :parameters (?product - assembly)
    :precondition (and
        (frame_assembled ?product)
        (electronics_installed ?product)
        (software_loaded ?product)
        (quality_check_passed ?product)
        (not (final_assembly_done ?product))
    )
    :effect (final_assembly_done ?product)
)

이 패턴에서 네 가지 긍정적 전제 조건은 각각 선행 공정의 완료를 나타내며, 이들이 모두 참이어야 최종 조립이 수행된다.

5. 접합적 전제 조건과 플래닝 복잡도

접합적 전제 조건의 리터럴 수는 플래닝의 효율성에 직접적으로 영향을 미친다.

5.1 적용 가능성 검사 비용

접합에 포함된 리터럴 수를 k라 하면, 하나의 그라운드 액션의 적용 가능성 검사 비용은 O(k)이다(해시 기반 상태 표현 가정). 리터럴 수가 증가할수록 개별 액션의 검사 비용이 증가하지만, 동시에 적용 가능한 액션의 수는 감소하여 탐색의 분기 요인이 줄어든다.

5.2 휴리스틱 추정에의 영향

접합적 전제 조건의 리터럴은 플래너의 휴리스틱에서 개별 하위 목표(subgoal)로 분석된다. 가산 휴리스틱(h^{\text{add}})에서 접합 전제 조건의 비용은 각 리터럴의 달성 비용의 합으로 추정된다:

h^{\text{add}}(\text{and} \ \phi_1 \ \ldots \ \phi_n) = \sum_{i=1}^{n} h^{\text{add}}(\phi_i)

최대 휴리스틱(h^{\text{max}})에서는 가장 비용이 높은 리터럴의 달성 비용으로 추정된다:

h^{\text{max}}(\text{and} \ \phi_1 \ \ldots \ \phi_n) = \max_{i \in \{1,\ldots,n\}} h^{\text{max}}(\phi_i)

접합의 리터럴 수가 많을수록 가산 휴리스틱의 과대 추정(overestimation) 정도가 커지는 경향이 있으며, 이는 최적 계획 탐색에는 부적합하지만 만족 계획(satisficing plan) 탐색에서는 효과적인 가이드를 제공할 수 있다(Bonet & Geffner, 2001).

6. 접합적 전제 조건 설계의 실용적 지침

  1. 필수적인 조건만 포함하라. 액션의 정확한 적용 가능성을 규정하는 데 필수적인 조건만을 전제 조건에 포함해야 한다. 암묵적으로 보장되는 조건이나 다른 전제 조건에 의해 논리적으로 함의되는 조건은 중복이므로 제외한다.

  2. 접합의 크기를 관리하라. 지나치게 많은 리터럴을 하나의 접합에 포함하면 도메인의 가독성이 저하되고, 플래닝 효율이 떨어질 수 있다. 전제 조건이 과도하게 복잡해지는 경우, 도메인의 술어 구조나 액션 분해를 재검토하는 것이 바람직하다.

  3. 독립적 조건 그룹을 식별하라. 접합 내의 조건들이 논리적으로 독립적인 그룹으로 분리될 수 있다면, 이를 시각적으로 구분하여 배치함으로써 도메인 리뷰와 디버깅을 용이하게 한다.

7. 참고 문헌

  • Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
  • Bonet, B. & Geffner, H. (2001). “Planning as Heuristic Search.” Artificial Intelligence, 129(1–2), 5–33.
  • Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.