1314.28 동시 액션과 상호 배제 분석

1314.28 동시 액션과 상호 배제 분석

1. 동시 액션의 개념

고전적 PDDL 플래닝에서 계획은 액션의 순차적 시퀀스로 정의된다. 그러나 실제 로봇 시스템에서는 다중 로봇이 동시에 행동하거나, 단일 로봇이 여러 서브시스템을 병렬로 작동시키는 경우가 빈번하다. 동시 액션(concurrent actions)은 동일한 시간 단위에 여러 액션이 병렬로 실행되는 상황을 의미한다.

PDDL 2.1의 지속 액션(durative-action)은 시간적 중첩을 통해 동시 실행을 자연스럽게 모델링할 수 있다. 그러나 고전적 STRIPS/ADL 수준에서도 다중 로봇 도메인에서 동시 액션의 개념이 중요하며, 이 경우 상호 배제(mutual exclusion, mutex) 분석이 핵심이 된다.

2. 상호 배제의 정의

두 그라운드 액션 a_1과 a_2가 상호 배제 관계에 있다는 것은, 이 두 액션을 동시에 또는 임의의 순서로 적용했을 때 결과 상태가 일관되지 않거나, 하나의 액션이 다른 액션의 전제 조건을 위반하는 경우를 의미한다.

Blum과 Furst(1997)는 Graphplan 알고리즘에서 다음의 상호 배제 유형을 정의하였다:

2.1 간섭(Interference)

한 액션의 효과가 다른 액션의 전제 조건을 삭제하는 경우이다:

\text{eff}^-(a_1) \cap \text{pre}^+(a_2) \neq \emptyset \quad \text{또는} \quad \text{eff}^-(a_2) \cap \text{pre}^+(a_1) \neq \emptyset

예시:

;; 액션 1: 로봇이 wp1에서 wp2로 이동
(move r1 wp1 wp2)
;; 효과: (not (robot_at r1 wp1)), (robot_at r1 wp2)

;; 액션 2: 로봇이 wp1에서 물체를 집기
(pick_up r1 box1 wp1)
;; 전제 조건: (robot_at r1 wp1)

move의 삭제 효과 (not (robot_at r1 wp1))이 pick_up의 전제 조건 (robot_at r1 wp1)을 위반하므로, 두 액션은 간섭 관계에 있다.

2.2 경쟁적 요구(Competing Needs)

두 액션의 전제 조건이 상호 배타적 술어를 요구하는 경우이다:

\exists p: p \in \text{pre}(a_1) \wedge \neg p \in \text{pre}(a_2)

2.3 비일관적 효과(Inconsistent Effects)

한 액션의 추가 효과가 다른 액션의 삭제 효과와 충돌하는 경우이다:

\text{eff}^+(a_1) \cap \text{eff}^-(a_2) \neq \emptyset

3. Graphplan에서의 상호 배제 분석

Graphplan 알고리즘(Blum & Furst, 1997)은 플래닝 그래프(planning graph)의 각 액션 계층에서 상호 배제 쌍을 체계적으로 추론한다. 플래닝 그래프는 교대하는 명제 계층(proposition layer)과 액션 계층(action layer)으로 구성되며, 각 계층에서 상호 배제 관계가 전파된다.

액션 간 mutex 조건:

  1. 비일관적 효과: 한 액션이 다른 액션의 효과를 부정한다.
  2. 간섭: 한 액션이 다른 액션의 전제 조건을 삭제한다.
  3. 경쟁적 요구: 두 액션의 전제 조건이 이전 계층에서 상호 배제이다.

명제 간 mutex 조건:

두 명제가 상호 배제인 경우는, 한 명제를 달성하는 모든 액션이 다른 명제를 달성하는 모든 액션과 상호 배제일 때이다.

4. 다중 로봇 도메인에서의 상호 배제

다중 로봇 도메인에서 상호 배제 분석은 로봇 간의 충돌을 방지하는 데 핵심적인 역할을 한다:

4.1 공간적 상호 배제

두 로봇이 동일한 위치를 동시에 점유할 수 없는 경우:

;; 위치 점유의 상호 배제
(move r1 wp1 wp2) 와 (move r2 wp3 wp2) 는 mutex
;; 이유: 두 액션 모두 wp2에 대한 (occupied wp2)를 추가하므로 경쟁

4.2 자원 상호 배제

동일한 공유 자원을 동시에 사용할 수 없는 경우:

;; 충전 스테이션의 상호 배제
(dock_for_charging r1 station1) 와 (dock_for_charging r2 station1) 는 mutex
;; 이유: 두 액션 모두 (dock_available station1) 삭제를 요구

4.3 대상 물체 상호 배제

동일한 물체에 대해 두 로봇이 동시에 조작할 수 없는 경우:

;; 물체 조작의 상호 배제
(pick_up r1 box1 wp1) 와 (pick_up r2 box1 wp1) 는 mutex
;; 이유: 두 액션 모두 (object_at box1 wp1) 삭제를 요구

5. PDDL에서의 상호 배제 표현

고전적 PDDL에서는 상호 배제를 직접적으로 선언하는 구문이 존재하지 않는다. 상호 배제는 전제 조건과 효과의 구조로부터 간접적으로 추론된다. 도메인 설계자는 다음의 기법을 통해 상호 배제를 간접적으로 강제할 수 있다:

5.1 위치 점유 술어를 통한 공간 상호 배제

(:action move
    :parameters (?r - robot ?from - waypoint ?to - waypoint)
    :precondition (and
        (robot_at ?r ?from)
        (connected ?from ?to)
        (not (occupied ?to))     ;; 목적지가 비어 있어야 함
    )
    :effect (and
        (not (robot_at ?r ?from))
        (robot_at ?r ?to)
        (not (occupied ?from))
        (occupied ?to)
    )
)

5.2 잠금 술어를 통한 자원 상호 배제

(:action use_tool
    :parameters (?r - robot ?tool - shared_tool)
    :precondition (and
        (tool_available ?tool)    ;; 도구가 사용 가능해야 함
        (robot_at ?r tool_station)
    )
    :effect (and
        (not (tool_available ?tool))  ;; 도구 잠금
        (tool_in_use ?r ?tool)
    )
)

(:action release_tool
    :parameters (?r - robot ?tool - shared_tool)
    :precondition (tool_in_use ?r ?tool)
    :effect (and
        (tool_available ?tool)        ;; 도구 잠금 해제
        (not (tool_in_use ?r ?tool))
    )
)

6. PDDL 2.1의 시간적 상호 배제

PDDL 2.1의 지속 액션에서는 시간적 중첩이 허용되되, 동시 실행되는 액션 간의 상호 배제 조건이 명시적으로 정의된다:

  1. 두 지속 액션은 동일한 술어에 대해 하나는 추가, 다른 하나는 삭제를 시도하면 동시 실행이 불가능하다.
  2. 두 지속 액션은 동일한 수치 플루언트에 대해 동시에 변경을 시도하면 동시 실행이 불가능하다.

이러한 규칙은 시간 플래너(temporal planner)가 지속 액션의 병렬 실행 가능성을 판단하는 데 사용된다.

7. 참고 문헌

  • Blum, A. L. & Furst, M. L. (1997). “Fast Planning Through Planning Graph Analysis.” Artificial Intelligence, 90(1–2), 281–300.
  • Fox, M. & Long, D. (2003). “PDDL2.1: An Extension to PDDL for Expressing Temporal Planning Domains.” Journal of Artificial Intelligence Research, 20, 61–124.
  • Ghallab, M., Nau, D., & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
  • Haslum, P., Lipovetzky, N., Magazzeni, D., & Muise, C. (2019). An Introduction to the Planning Domain Definition Language. Morgan & Claypool Publishers.