1314.2 액션 스키마의 형식적 정의

1. 액션 스키마의 수학적 정의

액션 스키마(action schema)는 매개변수화된 행동 템플릿으로서, PDDL 도메인에서 에이전트가 수행할 수 있는 행동 유형을 일반적 형태로 정의한다. 형식적으로, 액션 스키마 $\mathcal{A}$ 는 다음의 사중 쌍(quadruple)으로 정의된다:

$\mathcal{A} = \langle \text{name}, \text{params}, \text{pre}, \text{eff} \rangle$

여기서 각 구성 요소는 다음을 의미한다:

$\text{name}$ : 액션의 고유 식별자로서, 도메인 내에서 유일해야 한다.
$\text{params} = \{(v_1, \tau_1), (v_2, \tau_2), \ldots, (v_k, \tau_k)\}$ : 매개변수 변수 $v_i$ 와 그에 대응하는 타입 $\tau_i$ 의 순서쌍 집합이다.
$\text{pre}$ : 전제 조건으로서, 매개변수 변수를 포함하는 1차 논리식(first-order logic formula)이다.
$\text{eff}$ : 효과로서, 액션 실행 후 상태에 가해지는 변경을 명시하는 논리식이다.

액션 스키마는 리프팅된(lifted) 표현으로서, 구체적인 객체에 대한 바인딩이 이루어지기 전의 추상적 형태이다. 이는 1차 논리에서 자유 변수(free variable)를 포함하는 공식에 해당하며, 매개변수에 도메인 객체를 대입(substitution)함으로써 그라운드 액션(ground action)으로 변환된다(Ghallab, Nau, & Traverso, 2004).

2. PDDL 구문에서의 액션 스키마 구조

PDDL에서 액션 스키마는 (:action ...) 구문으로 정의된다. 일반적인 구조는 다음과 같다:

(:action <action-name>
    :parameters (<typed-variable-list>)
    :precondition <logical-formula>
    :effect <effect-formula>
)

각 구문 요소의 역할을 상세히 분석한다.

2.1 액션 이름

:action 키워드 다음에 오는 식별자는 액션 스키마의 이름이다. 액션 이름은 도메인 내에서 고유해야 하며, PDDL 구문 규칙에 따라 알파벳, 숫자, 하이픈(-), 밑줄(_) 문자를 사용할 수 있다. 액션 이름은 대소문자를 구분하지 않는다.

2.2 매개변수 목록

:parameters 절은 액션의 매개변수 변수를 선언한다. 각 변수는 물음표(?)로 시작하며, 선택적으로 타입이 지정된다:

:parameters (?r - robot ?from ?to - waypoint)

위 예시에서 ?r은 robot 타입, ?from과 ?to는 waypoint 타입으로 선언된다. :typing 요구사항이 활성화되지 않은 도메인에서는 모든 변수가 기본 타입 object로 처리된다.

2.3 전제 조건

:precondition 절은 액션이 적용 가능한 상태 조건을 논리식으로 명시한다. 전제 조건이 없는 액션은 모든 상태에서 적용 가능하다. 전제 조건은 도메인의 :requirements에 따라 다양한 논리적 구성이 허용된다:

요구사항	허용되는 전제 조건 구성
`:strips`	긍정적 리터럴의 접합
`:negative-preconditions`	부정 리터럴 포함
`:disjunctive-preconditions`	`or` 연산자 사용
`:universal-preconditions`	`forall` 양화사 사용
`:existential-preconditions`	`exists` 양화사 사용
`:adl`	위의 모든 구성 허용

2.4 효과

:effect 절은 액션 실행 후 세계 상태에 발생하는 변경을 명시한다. 기본적으로 효과는 긍정적 리터럴(술어 추가)과 부정적 리터럴(술어 삭제)의 접합으로 표현된다. :conditional-effects 요구사항이 활성화된 경우, when 구문을 사용한 조건부 효과가 허용된다.

3. 액션 스키마의 형식적 의미론

액션 스키마의 의미론은 대입(substitution)과 적용(application)의 두 단계로 정의된다.

3.1 대입과 그라운딩

대입 $\sigma$ 는 매개변수 변수에서 도메인 객체로의 사상(mapping)이다:

$\sigma: \{v_1, v_2, \ldots, v_k\} \rightarrow \mathcal{O}$

여기서 $\mathcal{O}$ 는 도메인의 객체 집합이다. 대입 $\sigma$ 는 각 변수 $v_i$ 를 대응하는 타입 $\tau_i$ 에 속하는 객체에만 사상할 수 있다:

$\sigma(v_i) \in \text{objects}(\tau_i) \quad \forall i \in \{1, \ldots, k\}$

여기서 $\text{objects}(\tau_i)$ 는 타입 $\tau_i$ 에 속하는 모든 객체의 집합이다. 타입 계층 구조가 존재하는 경우, 하위 타입의 객체도 상위 타입에 대입할 수 있다.

그라운드 액션 $a = \sigma(\mathcal{A})$ 는 액션 스키마 $\mathcal{A}$ 에 대입 $\sigma$ 를 적용한 결과이다:

$a = \langle \text{name}, \sigma(\text{pre}), \sigma(\text{eff}) \rangle$

3.2 적용 가능성

그라운드 액션 $a$ 가 상태 $s$ 에서 적용 가능(applicable)하려면, 전제 조건이 해당 상태에서 참이어야 한다:

$s \models \sigma(\text{pre})$

여기서 $\models$ 는 논리적 만족(satisfaction) 관계를 나타낸다. STRIPS 의미론에서는 전제 조건이 긍정적 리터럴의 접합으로 제한되므로, 적용 가능성은 전제 조건의 모든 리터럴이 상태에 포함되는지의 집합 포함(subset) 관계로 단순화된다:

$\text{pre}^+(a) \subseteq s$

여기서 $\text{pre}^+(a)$ 는 전제 조건의 긍정적 리터럴 집합이다. ADL 확장에서는 부정, 선언, 양화 등의 논리적 구성이 허용되므로, 적용 가능성 판단이 더 복잡해진다.

3.3 상태 전이

적용 가능한 그라운드 액션 $a$ 를 상태 $s$ 에 적용한 결과 상태 $s'$ 은 다음과 같이 계산된다:

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

여기서 $\gamma$ 는 상태 전이 함수, $\text{eff}^-(a)$ 는 삭제 효과(delete effects)의 집합, $\text{eff}^+(a)$ 는 추가 효과(add effects)의 집합이다. 삭제가 추가보다 먼저 적용되므로, 동일 술어가 삭제와 추가 효과에 동시에 나타나는 경우 해당 술어는 결과 상태에 존재하게 된다.

4. 그라운딩의 조합적 폭발

액션 스키마의 그라운딩 과정에서 발생하는 조합적 폭발(combinatorial explosion)은 플래닝 복잡도에 직접적인 영향을 미친다. $k$ 개의 매개변수를 가지는 액션 스키마에서 각 매개변수 타입에 $n_i$ 개의 객체가 존재하면, 가능한 그라운드 액션의 수는 다음과 같다:

$\prod_{i=1}^{k} n_i$

실제로는 타입 제약과 전제 조건에 의해 유효한 그라운드 액션의 수가 크게 줄어들지만, 매개변수 수가 증가할수록 그라운딩 비용이 급격히 증가한다. 이는 액션 스키마 설계 시 매개변수의 수를 최소화해야 하는 실용적 이유를 제공한다.

현대의 플래너들은 이 문제를 완화하기 위해 리프팅된 표현에서 직접 플래닝을 수행하거나, 도달 가능성 분석(reachability analysis)을 통해 불필요한 그라운드 액션을 사전에 제거하는 기법을 사용한다(Helmert, 2009).

5. 로봇 도메인에서의 액션 스키마 설계 예시

로봇 공학의 물체 조작 도메인에서 액션 스키마 설계의 예시를 살펴본다:

(define (domain manipulation)
    (:requirements :strips :typing)
    (:types robot object location gripper)
    (:predicates
        (robot_at ?r - robot ?l - location)
        (object_at ?o - object ?l - location)
        (holding ?r - robot ?o - object ?g - gripper)
        (gripper_free ?r - robot ?g - gripper)
        (reachable ?r - robot ?l - location)
    )

    (:action pick
        :parameters (?r - robot ?o - object ?l - location ?g - gripper)
        :precondition (and
            (robot_at ?r ?l)
            (object_at ?o ?l)
            (gripper_free ?r ?g)
            (reachable ?r ?l)
        )
        :effect (and
            (holding ?r ?o ?g)
            (not (object_at ?o ?l))
            (not (gripper_free ?r ?g))
        )
    )

    (:action place
        :parameters (?r - robot ?o - object ?l - location ?g - gripper)
        :precondition (and
            (robot_at ?r ?l)
            (holding ?r ?o ?g)
        )
        :effect (and
            (object_at ?o ?l)
            (gripper_free ?r ?g)
            (not (holding ?r ?o ?g))
        )
    )
)

이 예시에서 pick 액션 스키마는 4개의 매개변수를 가지며, 전제 조건으로 로봇의 위치, 물체의 위치, 그리퍼의 가용성, 도달 가능성을 요구한다. 효과로는 물체를 들고 있는 상태의 추가, 물체의 원래 위치 삭제, 그리퍼 가용성 삭제가 정의된다.

이러한 형식적 정의를 통해 플래너는 도메인 내의 모든 가능한 물체 조작 행동을 체계적으로 열거하고, 목표 상태에 도달하는 최적의 액션 시퀀스를 탐색할 수 있다.

6. 참고 문헌

Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
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.
Helmert, M. (2009). “Concise Finite-Domain Representations for PDDL Planning Tasks.” Artificial Intelligence, 173(5–6), 503–535.
Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.
McDermott, D., Ghallab, M., Howe, A., Knoblock, C., Ram, A., Veloso, M., Weld, D., & Wilkins, D. (1998). “PDDL—The Planning Domain Definition Language.” Technical Report CVC TR-98-003, Yale Center for Computational Vision and Control.