397.41 동시성(Concurrency)을 고려한 멀티 액션 계획

전통적인 임무 계획 기법은 단일 에이전트가 행동을 순차적으로 실행하는 것을 전제로 한다. 그러나 실제 로봇 시스템에서는 다수의 로봇이 동시에 행동을 수행하거나, 단일 로봇이라 하더라도 이동과 센싱을 병행하는 등 **동시성(concurrency)**이 본질적으로 존재한다. 동시성을 고려한 멀티 액션 계획은 다수의 행동이 시간적으로 중첩되어 실행될 수 있는 상황에서 올바르고 효율적인 계획을 수립하기 위한 이론과 기법을 다룬다.

1. 순차 계획과 동시 계획의 구분

1.1 순차 계획(Sequential Planning)

순차 계획에서 계획 $\pi$ 는 행동의 선형 시퀀스로 정의된다.

$\pi = \langle a_1, a_2, \ldots, a_n \rangle$

각 행동 $a_i$ 는 이전 행동 $a_{i-1}$ 이 완전히 종료된 후에 시작되며, 상태 전이는 다음과 같이 순차적으로 적용된다.

$s_0 \xrightarrow{a_1} s_1 \xrightarrow{a_2} s_2 \xrightarrow{} \cdots \xrightarrow{a_n} s_n$

1.2 동시 계획(Concurrent Planning)

동시 계획에서는 동일한 시간 단계(time step)에 여러 행동이 동시에 실행될 수 있다. 계획은 **동시 행동 집합(concurrent action set)**의 시퀀스로 정의된다.

$\pi_c = \langle A_1, A_2, \ldots, A_m \rangle$

여기서 $A_i \subseteq \mathcal{A}$ 는 시간 단계 $i$ 에서 동시에 실행되는 행동들의 집합이며, $\mathcal{A}$ 는 전체 행동 공간이다. 동시 계획에서의 상태 전이는 동시 행동 집합의 **결합 효과(joint effect)**에 의해 결정된다.

$s_{i+1} = \gamma(s_i, A_i)$

이때, 동시에 실행되는 행동들 사이에 **상호작용(interaction)**이 존재할 수 있으며, 이 상호작용의 유형에 따라 동시 실행의 허용 여부와 결합 효과의 계산 방식이 달라진다.

2. 동시 행동 간의 상호작용 유형

동시에 실행되는 행동 $a_i$ 와 $a_j$ 사이의 상호작용은 다음과 같이 분류된다.

2.1 독립(Independence)

두 행동이 서로의 전제 조건이나 효과에 영향을 미치지 않는 경우, 이들은 **독립(independent)**이라 한다. 형식적으로, 행동 $a_i$ 와 $a_j$ 가 독립이 되려면 다음 조건을 모두 만족해야 한다.

$\text{eff}^+(a_i) \cap \text{pre}(a_j) = \emptyset \quad \wedge \quad \text{eff}^+(a_j) \cap \text{pre}(a_i) = \emptyset$
$\text{eff}^-(a_i) \cap \text{pre}(a_j) = \emptyset \quad \wedge \quad \text{eff}^-(a_j) \cap \text{pre}(a_i) = \emptyset$
$\text{eff}^+(a_i) \cap \text{eff}^-(a_j) = \emptyset \quad \wedge \quad \text{eff}^+(a_j) \cap \text{eff}^-(a_i) = \emptyset$

여기서 $\text{eff}^+$ 는 추가 효과, $\text{eff}^-$ 는 삭제 효과, $\text{pre}$ 는 전제 조건을 나타낸다. 독립인 행동들은 어떤 순서로 실행하든, 또는 동시에 실행하든 동일한 결과 상태를 생성한다.

2.2 간섭(Interference)

한 행동의 효과가 다른 행동의 전제 조건을 무효화하거나, 두 행동의 효과가 상충하는 경우, 이들은 간섭(interfering) 관계에 있다. 간섭하는 행동들의 동시 실행은 일반적으로 금지되거나, 특별한 충돌 해결 메커니즘이 필요하다.

$\text{간섭}(a_i, a_j) \iff \text{eff}^-(a_i) \cap \text{pre}(a_j) \neq \emptyset \quad \vee \quad \text{eff}^+(a_i) \cap \text{eff}^-(a_j) \neq \emptyset$

2.3 협력(Cooperation)

두 행동이 개별적으로는 달성할 수 없는 효과를 함께 실행할 때만 달성하는 경우, 이들은 협력(cooperative) 관계에 있다. 예를 들어, 두 로봇이 무거운 물체의 양쪽을 동시에 들어 올리는 행동은 개별적으로는 불가능하지만 동시에 수행하면 성공한다.

3. 동시 계획의 형식적 모델링

3.1 PDDL에서의 동시성 표현

PDDL(Planning Domain Definition Language)에서는 **지속적 행동(durative action)**을 통해 동시성을 모델링한다. 지속적 행동은 시작 시점, 종료 시점, 그리고 지속 기간 동안의 조건과 효과를 명시한다.

(:durative-action 이동
  :parameters (?robot - robot ?from - location ?to - location)
  :duration (= ?duration (/ (distance ?from ?to) (speed ?robot)))
  :condition (and
    (at start (at ?robot ?from))
    (over all (path-clear ?from ?to))
  )
  :effect (and
    (at start (not (at ?robot ?from)))
    (at end (at ?robot ?to))
  )
)

이 표현에서:

at start: 행동 시작 시점에 적용
at end: 행동 종료 시점에 적용
over all: 행동의 전체 지속 기간 동안 유지되어야 하는 조건

3.2 시간축 기반 계획(Temporal Planning)

동시성을 본격적으로 다루기 위해서는 시간축 기반 계획(temporal planning) 프레임워크가 필요하다. 시간축 기반 계획에서 각 행동 $a$ 는 시작 시점 $\text{start}(a)$ 와 종료 시점 $\text{end}(a)$ 를, 그리고 지속 시간 $\text{dur}(a) = \text{end}(a) - \text{start}(a)$ 를 가진다.

시간축 기반 계획 $\pi_t$ 는 (행동, 시작 시점) 쌍의 집합으로 정의된다.

$\pi_t = \{(a_1, t_1), (a_2, t_2), \ldots, (a_n, t_n)\}$

여기서 $t_i = \text{start}(a_i)$ 이다. 두 행동 $a_i$ 와 $a_j$ 가 동시에 실행되고 있는 시간 구간은 다음과 같이 정의된다.

$\text{overlap}(a_i, a_j) = [\max(t_i, t_j),\ \min(t_i + \text{dur}(a_i),\ t_j + \text{dur}(a_j))]$

이 구간이 빈 구간이 아니면 두 행동은 시간적으로 중첩된다.

4. 동시 계획 알고리즘

4.1 GraphPlan의 동시성 활용

GraphPlan 알고리즘은 본질적으로 동시 계획을 지원한다. 계획 그래프(planning graph)의 각 레벨에서 상호 배타(mutex) 관계에 있지 않은 행동들은 동시에 실행 가능한 것으로 간주된다. 두 행동 $a_i$ 와 $a_j$ 가 상호 배타가 되는 조건은 다음과 같다.

효과 불일치(Inconsistent Effects): $\text{eff}^+(a_i) \cap \text{eff}^-(a_j) \neq \emptyset$ 또는 $\text{eff}^+(a_j) \cap \text{eff}^-(a_i) \neq \emptyset$
간섭(Interference): $\text{eff}^-(a_i) \cap \text{pre}(a_j) \neq \emptyset$ 또는 $\text{eff}^-(a_j) \cap \text{pre}(a_i) \neq \emptyset$
경쟁 전제 조건(Competing Needs): $a_i$ 와 $a_j$ 의 전제 조건 중 상호 배타인 명제 쌍이 존재

4.2 시간축 기반 계획기

4.2.1 TFD (Temporal Fast Downward)

TFD는 Fast Downward 계획기를 시간축 기반 계획으로 확장한 시스템으로, PDDL 2.1 수준의 지속적 행동을 지원한다. TFD는 의사 결정점(decision epoch) 기반의 탐색을 수행하며, 각 의사 결정점에서 새로운 행동의 시작 또는 진행 중인 행동의 종료를 선택한다.

TFD에서의 상태는 다음과 같은 확장된 형태를 가진다.

$\sigma = (s, Q, t)$

여기서 $s$ 는 현재 명제 상태, $Q$ 는 진행 중인 행동들의 대기열(queue), $t$ 는 현재 시간이다. 탐색은 이 확장된 상태 공간 위에서 수행되며, $Q$ 가 비어 있고 목표 조건이 $s$ 에서 만족될 때 계획이 완성된다.

4.2.2 POPF (Partial Order Planning Forward)

Coles 등(2010)이 개발한 POPF는 전방 탐색과 부분순서 계획을 결합하여 시간축 기반 계획을 수행한다. POPF는 진행 중인 행동의 over all 조건을 효율적으로 추적하며, 필요 순서 제약(necessary ordering constraint)만을 도입하여 불필요한 순서 결정을 회피한다.

4.3 다중 에이전트 동시 계획

다중 로봇 시스템에서의 동시 계획은 각 로봇의 개별 계획을 생성하되, 로봇 간의 상호작용(물리적 충돌, 자원 경쟁, 통신 동기화)을 적절히 관리해야 한다.

4.3.1 결합 상태 공간 계획(Joint State-Space Planning)

가장 직접적인 접근은 모든 로봇의 상태를 결합한 **결합 상태 공간(joint state space)**에서 계획을 수행하는 것이다. $n$ 개의 로봇이 각각 상태 공간 $S_i$ 를 가질 때, 결합 상태 공간은 다음과 같다.

$S_{\text{joint}} = S_1 \times S_2 \times \cdots \times S_n$

결합 상태 공간의 크기는 $\prod_{i=1}^n |S_i|$ 로 지수적으로 증가하므로, 로봇 수가 많을 경우 직접적인 적용이 비실용적이다.

4.3.2 느슨 결합 분해(Loosely-Coupled Decomposition)

Brafman과 Domshlak(2008)이 제안한 MA-STRIPS 형식론에서는 다중 에이전트 계획 문제를 개별 에이전트의 국소 문제와 에이전트 간 상호작용으로 분해한다. 각 에이전트 $i$ 의 국소 문제는 자신의 상태 변수에만 영향을 미치는 행동들로 구성되며, 다른 에이전트의 상태 변수에 영향을 미치는 행동은 **공개 행동(public action)**으로 분류되어 조율 대상이 된다.

5. 로봇 임무에서의 동시 계획 사례

5.1 다관절 로봇의 양팔 작업 계획

양팔(dual-arm) 매니퓰레이터 로봇에서는 좌우 양팔이 동시에 독립적인 행동을 수행하거나, 협력적으로 하나의 물체를 다루는 상황이 발생한다. 동시 계획을 통해 양팔의 행동을 최적으로 병렬화하면, 순차 계획에 비해 작업 완료 시간(makespan)을 대폭 단축할 수 있다.

예를 들어, 부품 조립 임무에서 좌측 팔이 부품 A를 파지하는 동안 우측 팔이 부품 B의 위치를 정렬하는 행동은 독립적이므로 동시 실행이 가능하다. 반면, 두 팔이 함께 큰 패널을 들어 올리는 행동은 협력적 동시 행동에 해당하며, 양팔의 시작 시점과 힘 제어가 동기화되어야 한다.

5.2 다중 AGV(Automated Guided Vehicle)의 물류 계획

물류 환경에서 다수의 AGV가 동시에 물품을 운반할 때, 각 AGV의 이동 경로가 교차하는 지점에서 충돌이 발생할 수 있다. 동시 계획에서는 시간축 상에서 각 AGV의 경로를 병렬로 계획하되, 교차 지점에서의 시간적 간섭을 방지하는 순서 제약을 추가한다.

5.3 이종 로봇 팀의 협력 감시

공중 로봇(UAV)과 지상 로봇(UGV)이 협력하여 감시 임무를 수행할 때, UAV의 항공 정찰과 UGV의 지상 순찰이 동시에 진행된다. 동시 계획에서는 UAV가 이상 징후를 탐지하면 인접한 UGV에 확인 명령을 전달하는 동기화 지점(synchronization point)을 계획에 포함한다.

6. 동시 계획의 최적성 지표

동시 계획의 품질을 평가하기 위한 주요 지표는 다음과 같다.

6.1 작업 완료 시간(Makespan)

작업 완료 시간은 계획의 첫 행동 시작부터 마지막 행동 종료까지의 총 소요 시간이다.

$\text{makespan}(\pi_t) = \max_{(a, t) \in \pi_t} (t + \text{dur}(a)) - \min_{(a, t) \in \pi_t} t$

순차 계획에서의 makespan은 $\sum_{i=1}^n \text{dur}(a_i)$ 이지만, 동시 계획에서는 행동의 병렬 실행에 의해 이보다 작은 값을 달성할 수 있다.

6.2 병렬화 비율(Parallelism Ratio)

병렬화 비율은 동시 계획이 순차 계획 대비 얼마나 효과적으로 병렬화되었는지를 나타내는 지표이다.

$\rho = \frac{\sum_{i=1}^n \text{dur}(a_i)}{\text{makespan}(\pi_t)}$

$\rho = 1$ 이면 완전 순차 실행, $\rho > 1$ 이면 병렬 실행의 이득이 존재함을 의미한다.

7. 요약

동시성을 고려한 멀티 액션 계획은 다수의 행동이 시간적으로 중첩되어 실행되는 상황을 체계적으로 모델링하고 최적화하는 프레임워크이다. 행동 간의 독립, 간섭, 협력 관계를 형식적으로 분류하고, PDDL의 지속적 행동이나 시간축 기반 계획 모델을 통해 동시성을 표현한다. TFD, POPF 등의 시간축 기반 계획기는 동시 행동의 효율적 탐색과 충돌 방지를 구현하며, 다중 에이전트 시스템에서는 결합 상태 공간 또는 느슨 결합 분해를 통해 확장성을 확보한다. 로봇 임무 계획에서 동시 계획의 적용은 makespan 단축과 자원 활용 효율 향상에 핵심적으로 기여한다.

8. 참고 문헌

Blum, A. L., & Furst, M. L. (1997). “Fast planning through planning graph analysis.” Artificial Intelligence, 90(1–2), pp. 281–300.
Fox, M., & Long, D. (2003). “PDDL2.1: An extension to PDDL for expressing temporal planning domains.” Journal of Artificial Intelligence Research, 20, pp. 61–124.
Eyerich, P., Mattmüller, R., & Röger, G. (2009). “Using the context-enhanced additive heuristic for temporal and numeric planning.” Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pp. 130–137.
Coles, A. J., Coles, A. I., Fox, M., & Long, D. (2010). “Forward-chaining partial-order planning.” Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pp. 42–49.
Brafman, R. I., & Domshlak, C. (2008). “From one to many: Planning for loosely coupled multi-agent systems.” Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS), pp. 28–35.

v1.0 | 로봇공학 서적 – Volume 9, Part 53, Chapter 397, Section 41