1314.5 매개변수와 객체 바인딩 메커니즘

1. 객체 바인딩의 개념

PDDL에서 객체 바인딩(object binding)은 액션 스키마의 매개변수 변수에 도메인 내의 구체적 객체를 대입하는 과정이다. 이 과정을 통해 추상적인 액션 스키마가 특정 객체들에 대해 실행 가능한 구체적 액션 인스턴스, 즉 그라운드 액션(ground action)으로 변환된다.

형식적으로, 바인딩은 대입 함수(substitution function) $\sigma$ 로 표현된다:

$\sigma: \text{Vars}(\mathcal{A}) \rightarrow \mathcal{O}$

여기서 $\text{Vars}(\mathcal{A})$ 는 액션 스키마 $\mathcal{A}$ 의 매개변수 변수 집합이고, $\mathcal{O}$ 는 문제 인스턴스에 선언된 객체 집합이다. 유효한 바인딩은 각 변수의 타입 제약을 만족해야 한다:

$\forall v_i \in \text{Vars}(\mathcal{A}): \text{type}(\sigma(v_i)) \preceq \text{decltype}(v_i)$

여기서 $\text{decltype}(v_i)$ 는 변수 $v_i$ 에 선언된 타입이고, $\preceq$ 는 타입 계층의 하위 타입 관계이다.

2. 그라운딩 과정

그라운딩(grounding)은 액션 스키마의 모든 유효한 바인딩을 열거하여 그라운드 액션 집합을 생성하는 과정이다. 이 과정은 플래닝의 전처리(preprocessing) 단계에서 수행되거나, 플래너의 탐색 과정에서 필요 시 동적으로 수행된다.

다음의 예시를 통해 그라운딩 과정을 설명한다:

;; 도메인 정의
(:types robot waypoint - object)
(: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))
)

;; 문제 정의
(:objects
    robot1 - robot
    wp1 wp2 wp3 - waypoint
)

이 도메인에서 move 액션의 가능한 바인딩은 다음과 같다:

바인딩	`?r`	`?from`	`?to`	그라운드 액션
$\sigma_1$	robot1	wp1	wp2	`(move robot1 wp1 wp2)`
$\sigma_2$	robot1	wp1	wp3	`(move robot1 wp1 wp3)`
$\sigma_3$	robot1	wp2	wp1	`(move robot1 wp2 wp1)`
$\sigma_4$	robot1	wp2	wp3	`(move robot1 wp2 wp3)`
$\sigma_5$	robot1	wp3	wp1	`(move robot1 wp3 wp1)`
$\sigma_6$	robot1	wp3	wp2	`(move robot1 wp3 wp2)`

?from과 ?to에 동일한 객체가 바인딩되는 경우(예: (move robot1 wp1 wp1))도 구문적으로는 유효한 바인딩이다. 이러한 자기 참조적 바인딩을 제외하려면 전제 조건에 별도의 불동 조건(inequality condition)을 명시해야 한다. :equality 요구사항이 활성화된 도메인에서는 다음과 같이 처리한다:

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

3. 바인딩의 적용 가능성 필터링

모든 타입 호환 바인딩이 실제로 유효한 액션을 생성하는 것은 아니다. 그라운드 액션이 특정 상태에서 적용 가능하려면, 바인딩된 전제 조건이 해당 상태에서 참이어야 한다. 따라서 실제 플래닝 과정에서는 두 단계의 필터링이 적용된다:

1단계: 타입 기반 필터링: 타입 제약을 만족하는 바인딩만을 후보로 생성한다.

2단계: 전제 조건 기반 필터링: 현재 상태에서 전제 조건이 참인 그라운드 액션만을 적용 가능한 액션으로 선택한다.

현재 상태가 다음과 같다고 가정한다:

$s = \{(\text{robot\_at} \ \text{robot1} \ \text{wp1}), (\text{connected} \ \text{wp1} \ \text{wp2}), (\text{connected} \ \text{wp2} \ \text{wp3})\}$

이 상태에서 적용 가능한 그라운드 move 액션은 (move robot1 wp1 wp2)뿐이다. ?from이 wp1에 바인딩되어야 robot_at 전제 조건이 충족되고, ?to는 wp1과 연결된 wp2에만 바인딩될 수 있기 때문이다.

4. 양화사와 바인딩의 상호 작용

전제 조건이나 효과에 양화사(forall, exists)가 포함된 경우, 양화사 내부의 변수에 대한 바인딩은 매개변수 바인딩과는 독립적으로 처리된다.

4.1 전칭 양화와 바인딩

forall 양화사 내부의 변수는 해당 타입의 모든 객체에 대해 순회한다:

(:action secure_area
    :parameters (?r - robot ?area - zone)
    :precondition (and
        (robot_at ?r ?area)
        (forall (?d - door)
            (imply (door_in ?d ?area) (door_locked ?d))
        )
    )
    :effect (secured ?area)
)

이 예시에서 ?r과 ?area는 매개변수 바인딩의 대상이지만, ?d는 forall 양화사에 의해 도메인 내의 모든 door 타입 객체에 대해 내부 조건이 평가된다. 매개변수 바인딩 $\sigma = \{?r \mapsto \text{robot1}, ?area \mapsto \text{zone1}\}$ 이 주어지면, 전제 조건의 평가는 다음과 같이 진행된다:

$s \models (\text{robot\_at} \ \text{robot1} \ \text{zone1}) \wedge \bigwedge_{d \in \text{objects}(\text{door})} \left( (\text{door\_in} \ d \ \text{zone1}) \Rightarrow (\text{door\_locked} \ d) \right)$

4.2 존재 양화와 바인딩

exists 양화사는 해당 타입의 객체 중 적어도 하나가 내부 조건을 만족하는지를 검사한다:

(:action request_assistance
    :parameters (?r - robot ?loc - waypoint)
    :precondition (and
        (robot_at ?r ?loc)
        (robot_stuck ?r)
        (exists (?helper - robot)
            (and
                (not (= ?helper ?r))
                (robot_available ?helper)
            )
        )
    )
    :effect (assistance_requested ?r)
)

여기서 ?helper는 exists 양화사 내부의 지역 변수(local variable)로서, 매개변수 ?r과는 별개의 바인딩 공간을 가진다. ?helper에 대한 바인딩은 조건을 만족하는 객체가 존재하는지 여부만 판단하는 데 사용되며, 액션 인스턴스의 인수로 노출되지 않는다.

5. 상수와 바인딩

도메인 수준에서 선언된 상수(constants)는 그라운딩 과정에서 특수하게 처리된다. 상수는 모든 문제 인스턴스에서 자동으로 존재하는 객체로서, 매개변수에 바인딩될 수 있다:

(:constants
    base_station - waypoint
    emergency - priority_level
)

상수 base_station은 waypoint 타입의 매개변수에 바인딩 가능하며, 문제 파일에서 별도로 선언할 필요가 없다. 이는 도메인 전반에 걸쳐 공통적으로 참조되는 고정 객체를 효율적으로 관리하는 데 유용하다.

6. 플래너의 바인딩 최적화 기법

현대의 플래너들은 그라운딩의 조합적 폭발을 완화하기 위해 다양한 최적화 기법을 사용한다.

6.1 도달 가능성 분석

도달 가능성 분석(reachability analysis)은 초기 상태에서 도달 가능한 술어 인스턴스만을 기반으로 유효한 바인딩의 범위를 축소한다. 초기 상태에서 어떤 술어가 성립할 수 없다면, 해당 술어를 전제 조건으로 요구하는 바인딩은 사전에 제거된다(Helmert, 2009).

6.2 리프팅된 플래닝

일부 플래너는 그라운딩을 완전히 수행하지 않고, 리프팅된(lifted) 표현에서 직접 탐색을 수행한다. 이 접근에서는 바인딩이 탐색 중에 점진적으로 결정되며, 불필요한 그라운드 액션의 생성을 회피한다(Corrêa et al., 2020).

6.3 대칭성 제거

동일한 타입의 매개변수 간에 순서가 무관한 경우(예: 두 웨이포인트가 교환 가능한 경우), 대칭적 바인딩을 제거하여 탐색 공간을 축소할 수 있다. 이는 자동 대칭성 탐지(automatic symmetry detection) 기법을 통해 수행된다(Fox & Long, 1999).

7. PlanSys2에서의 바인딩 처리

PlanSys2에서 플래너가 생성한 계획의 각 액션은 이미 그라운딩된 형태로 제공된다. Executor 노드는 계획에서 각 그라운드 액션의 이름과 바인딩된 인수를 추출하여, 해당 액션 노드에 전달한다:

// PlanSys2 액션 노드에서 바인딩된 인수 접근
void do_work() override
{
    auto args = get_arguments();
    // args[0]: 첫 번째 매개변수에 바인딩된 객체 이름
    // args[1]: 두 번째 매개변수에 바인딩된 객체 이름
    // ...
}

인수의 순서는 PDDL 도메인에서 액션 스키마의 :parameters 절에 선언된 순서와 동일하다. 따라서 매개변수의 선언 순서가 변경되면 액션 노드의 인수 처리 코드도 함께 수정해야 한다.

8. 참고 문헌

Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
Helmert, M. (2009). “Concise Finite-Domain Representations for PDDL Planning Tasks.” Artificial Intelligence, 173(5–6), 503–535.
Corrêa, A. B., Pommerening, F., Helmert, M., & Francès, G. (2020). “Lifted Successor Generation Using Query Decomposition.” Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), 30, 65–73.
Fox, M. & Long, D. (1999). “The Detection and Exploitation of Symmetry in Planning Problems.” Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI), 956–961.
Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.