1314.1 PDDL 액션의 개념과 역할

1. 액션의 정의

PDDL(Planning Domain Definition Language)에서 액션(action)은 에이전트가 세계 상태를 변경하기 위해 수행할 수 있는 단위 행동의 형식적 명세이다. 자동화된 플래닝에서 액션은 상태 공간(state space)에서의 전이 함수(transition function)를 정의하는 핵심 구성 요소로서, 플래너가 초기 상태에서 목표 상태에 도달하는 경로를 탐색하는 데 사용하는 기본 연산 단위이다.

형식적으로, 액션 $a$ 는 다음의 삼중 쌍(triple)으로 정의된다:

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

여기서 $\text{params}(a)$ 는 액션의 매개변수 집합, $\text{pre}(a)$ 는 전제 조건(precondition)으로서 액션이 적용 가능한 상태를 규정하는 논리식, $\text{eff}(a)$ 는 효과(effect)로서 액션 실행 후 상태에 가해지는 변경을 명시하는 논리식이다(Ghallab, Nau, & Traverso, 2004).

2. 액션 스키마와 인스턴스화

PDDL의 액션 정의는 액션 스키마(action schema)의 형태를 취한다. 액션 스키마는 매개변수화된 행동 템플릿으로서, 구체적인 객체(object)가 매개변수에 대입되기 전의 일반화된 표현이다. 하나의 액션 스키마로부터 매개변수에 도메인 내 객체들을 바인딩함으로써 다수의 구체적 액션 인스턴스(ground action)를 생성할 수 있다.

예를 들어, 로봇 이동 액션의 스키마는 다음과 같이 정의된다:

(: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)
    )
)

이 스키마에서 ?r, ?from, ?to는 매개변수 변수이며, 각각 robot, waypoint 타입으로 제약된다. 도메인에 로봇 robot1과 웨이포인트 wp1, wp2가 존재하면, (move robot1 wp1 wp2)라는 구체적 액션 인스턴스가 생성된다. 이 과정을 그라운딩(grounding)이라 한다.

그라운딩된 액션의 수는 각 매개변수 타입에 해당하는 객체 수의 곱에 비례한다. 도메인에 $n_r$ 개의 로봇과 $n_w$ 개의 웨이포인트가 존재하면, move 액션의 그라운딩된 인스턴스 수는 $n_r \times n_w \times (n_w - 1)$ 에 달할 수 있다. 이는 플래닝의 계산 복잡도에 직접적인 영향을 미치므로, 액션 스키마의 매개변수 설계가 플래닝 성능에 중요한 역할을 한다.

3. 플래닝에서 액션의 역할

자동화된 플래닝 문제는 일반적으로 다음과 같이 정의된다:

$\mathcal{P} = \langle \mathcal{D}, s_0, g \rangle$

여기서 $\mathcal{D}$ 는 도메인(타입, 술어, 액션 스키마의 집합), $s_0$ 는 초기 상태, $g$ 는 목표 조건이다. 플래너의 과제는 초기 상태 $s_0$ 에서 시작하여 목표 조건 $g$ 를 만족하는 상태에 도달하는 액션 시퀀스 $\pi = \langle a_1, a_2, \ldots, a_n \rangle$ 을 찾는 것이다.

이 과정에서 액션은 다음의 역할을 수행한다:

상태 전이 정의: 각 액션은 현재 상태에서 후속 상태로의 전이를 결정론적으로 정의한다. 상태 $s$ 에서 액션 $a$ 를 적용한 결과 상태 $s'$ 은 다음과 같이 계산된다:

$s' = (s \setminus \text{del}(a)) \cup \text{add}(a)$

여기서 $\text{del}(a)$ 는 효과에 의해 삭제되는 술어 집합, $\text{add}(a)$ 는 추가되는 술어 집합이다.

탐색 공간 구성: 플래너가 탐색하는 상태 공간은 액션에 의해 연결된 상태들의 유향 그래프로 표현된다. 각 상태에서 적용 가능한 액션의 집합이 탐색의 분기 요인(branching factor)을 결정한다.
계획 비용 산정: 최적 플래닝에서 각 액션에는 비용이 부여될 수 있으며, 계획의 총 비용은 구성 액션들의 비용 합으로 계산된다. PDDL 2.1에서는 메트릭(metric) 구문을 통해 최적화 기준을 명시할 수 있다.

4. STRIPS 모델과 PDDL 액션의 관계

PDDL 액션의 의미론은 STRIPS(Stanford Research Institute Problem Solver) 모델에 근원을 둔다(Fikes & Nilsson, 1971). STRIPS에서 연산자(operator)는 추가 목록(add list)과 삭제 목록(delete list)으로 효과를 표현하며, 전제 조건은 긍정적 리터럴의 접합(conjunction)으로 제한된다.

PDDL은 STRIPS 모델을 확장하여 다음의 표현력을 추가하였다:

특성	STRIPS	PDDL
전제 조건의 부정	미지원	`:negative-preconditions`
전제 조건의 선언	미지원	`:disjunctive-preconditions`
양화 전제 조건	미지원	`:universal-preconditions`, `:existential-preconditions`
조건부 효과	미지원	`:conditional-effects`
타입 시스템	미지원	`:typing`
수치 효과	미지원	`:numeric-fluents`
시간적 액션	미지원	`:durative-actions`

PDDL 도메인에서 :requirements 절을 통해 사용할 기능을 명시함으로써, 플래너가 해당 도메인을 처리할 수 있는지 사전에 확인할 수 있다.

5. 로봇 공학에서 PDDL 액션의 의의

로봇 공학에서 PDDL 액션은 로봇이 수행할 수 있는 물리적 행동의 추상 모델로 기능한다. 실제 로봇 시스템에서 액션은 다음과 같은 계층적 구조로 매핑된다:

PDDL 수준: 추상적 행동 모델. 전제 조건과 효과가 논리적 술어로 표현된다.
태스크 실행 수준: PlanSys2 등의 프레임워크에서 액션 노드가 실제 로봇 행동을 조율한다.
모션 수준: 네비게이션 스택, 조작 플래너 등이 저수준 운동 명령을 생성한다.
하드웨어 수준: 액추에이터가 물리적 운동을 수행한다.

PDDL 액션이 이 계층 구조에서 최상위의 추상 계층을 담당함으로써, 임무 계획 수준에서는 저수준의 실행 세부사항으로부터 분리된 상태에서 전략적 의사 결정이 가능해진다. 이러한 추상화는 도메인 독립적(domain-independent) 플래닝의 핵심 원리이며, 동일한 플래너가 다양한 로봇 도메인에 적용될 수 있는 이유이기도 하다.

그러나 추상화 수준의 선택은 신중해야 한다. 지나치게 추상적인 액션은 실행 시 예상치 못한 실패를 초래할 수 있으며, 지나치게 구체적인 액션은 플래닝의 탐색 공간을 불필요하게 확장한다. 로봇 도메인에서의 적절한 액션 추상화 수준 결정은 도메인 모델링의 핵심 과제 중 하나이다.

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.
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.
Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.