397.43 협력 임무 스케줄링(Cooperative Mission Scheduling)

다중 로봇 시스템에서는 개별 로봇이 독립적으로 임무를 수행하는 것이 아니라, 여러 로봇이 **협력(cooperation)**하여 공동의 목표를 달성해야 하는 상황이 빈번하게 발생한다. **협력 임무 스케줄링(Cooperative Mission Scheduling)**은 다수의 로봇에게 과업을 할당하고, 각 과업의 실행 시점과 순서를 결정하며, 로봇 간의 동기화와 자원 공유를 관리하는 통합적 계획 프레임워크이다.

1. 협력 임무 스케줄링의 정의

1.1 문제의 형식적 정의

협력 임무 스케줄링 문제는 다음과 같은 튜플로 정의된다.

\mathcal{S} = (\mathcal{R},\ \mathcal{T},\ \mathcal{C},\ \mathcal{F},\ f_{\text{obj}})

각 구성 요소의 의미는 다음과 같다.

• \mathcal{R} = \{r_1, r_2, \ldots, r_n\}: 가용 로봇의 집합으로, 각 로봇 r_i는 능력 벡터(capability vector) \mathbf{cap}(r_i)와 현재 상태 \mathbf{state}(r_i)를 가진다.
• \mathcal{T} = \{t_1, t_2, \ldots, t_m\}: 수행해야 할 과업의 집합으로, 각 과업 t_j는 요구 능력 \mathbf{req}(t_j), 예상 소요 시간 \text{dur}(t_j), 마감 시한 d_j 등의 속성을 보유한다.
• \mathcal{C}: 과업 간 제약 조건의 집합으로, 선행 제약(precedence constraints), 동기화 제약(synchronization constraints), 자원 제약(resource constraints) 등을 포함한다.
• \mathcal{F}: \mathcal{T} \rightarrow 2^{\mathcal{R}}: 과업-로봇 할당 함수로, 각 과업에 하나 이상의 로봇을 할당한다.
• f_{\text{obj}}: 최적화 목적 함수

1.2 독립 과업과 협력 과업의 구분

과업은 필요한 로봇 수에 따라 다음과 같이 구분된다.

독립 과업(Independent Task): 단일 로봇이 독자적으로 수행할 수 있는 과업이다. 이 경우 할당 함수 \mathcal{F}(t_j) = \{r_i\}는 단일 로봇 원소를 반환한다.

협력 과업(Cooperative Task): 둘 이상의 로봇이 동시에 참여해야 수행 가능한 과업이다. |\mathcal{F}(t_j)| \geq 2이며, 참여 로봇 간의 시간적 동기화가 필수적이다. 예를 들어, 대형 물체의 협력 운반, 다중 센서 동시 측정 등이 해당한다.

2. 과업 할당 문제(Task Allocation Problem)

2.1 단일 과업 할당

가장 기본적인 형태의 과업 할당은 각 과업을 하나의 로봇에 할당하는 문제이다. 이는 **할당 문제(assignment problem)**의 표준 형태로, 다음과 같이 정식화된다.

\min \sum_{i=1}^n \sum_{j=1}^m c_{ij} x_{ij}

\text{s.t.} \quad \sum_{i=1}^n x_{ij} = 1\ \forall j, \quad \sum_{j=1}^m x_{ij} \leq k_i\ \forall i, \quad x_{ij} \in \{0, 1\}

여기서 c_{ij}는 로봇 r_i가 과업 t_j를 수행하는 비용, x_{ij}는 할당 여부를 나타내는 이진 결정 변수, k_i는 로봇 r_i가 동시에 수행할 수 있는 최대 과업 수이다. 이 문제는 **헝가리안 알고리즘(Hungarian Algorithm)**에 의해 O(n^3) 시간에 최적으로 해결된다.

2.2 다중 로봇 과업 할당(MRTA) 분류 체계

Gerkey와 Matarić(2004)는 다중 로봇 과업 할당 문제를 다음 세 가지 축으로 분류하는 체계를 제안하였다.

이 분류에 따르면, 가장 단순한 형태는 ST-SR-IA (단일 과업-단일 로봇-즉시 할당)이고, 가장 복잡한 형태는 MT-MR-TA (다중 과업-다중 로봇-시간 확장 할당)이다.

3. 협력 스케줄링 알고리즘

3.1 경매 기반 할당(Auction-Based Allocation)

경매 기반 할당은 시장 경제의 경매 메커니즘에서 영감을 받은 분산적 과업 할당 방법이다.

단일 항목 경매(Single-Item Auction): 각 과업에 대해 독립적으로 경매를 진행한다. 각 로봇은 해당 과업의 수행 비용(또는 가치)에 기반하여 **입찰(bid)**을 제출하고, 경매인(auctioneer)이 최적의 입찰을 선택하여 과업을 할당한다.

r^* = \arg\min_{r_i \in \mathcal{R}} \text{bid}(r_i, t_j)

순차 단일 항목 경매(Sequential Single-Item Auction, SSI Auction): 과업을 하나씩 순차적으로 경매하되, 이전 할당 결과가 후속 입찰에 반영된다. 각 로봇은 이미 할당받은 과업을 고려하여 추가 과업의 **한계 비용(marginal cost)**을 입찰한다.

\text{bid}(r_i, t_j) = C(P_i \cup \{t_j\}) - C(P_i)

여기서 P_i는 로봇 r_i에 현재 할당된 과업 집합, C(\cdot)는 과업 집합의 총 수행 비용 함수이다.

합의 기반 번들 알고리즘(Consensus-Based Bundle Algorithm, CBBA): Choi 등(2009)이 제안한 CBBA는 분산 환경에서 경매 기반 할당을 수행하는 알고리즘이다. 각 로봇은 **번들 구성 단계(bundle construction phase)**에서 탐욕적으로 과업을 추가하고, **합의 단계(consensus phase)**에서 이웃 로봇과 정보를 교환하여 할당 충돌을 해결한다.

CBBA의 수렴성과 최적성에 대해 다음이 알려져 있다.

정리 (Choi et al., 2009): 점수 함수(scoring function)가 감소 한계 이득(Diminishing Marginal Gain, DMG) 조건을 만족하는 경우, CBBA는 유한 시간 내에 충돌 없는 할당으로 수렴하며, 최적 해 대비 \frac{1}{2}의 근사 보장을 제공한다.

3.2 최적화 기반 스케줄링

과업 할당과 스케줄링을 동시에 수행하는 통합적 접근에서는 혼합 정수 선형 프로그래밍(MILP) 또는 **제약 프로그래밍(Constraint Programming, CP)**이 활용된다.

MILP 정식화의 일반적 형태는 다음과 같다.

\min f_{\text{obj}}(\mathbf{x}, \mathbf{s})

\text{s.t.} \quad s_j + \text{dur}(t_j) \leq s_k \quad \forall (t_j, t_k) \in \text{prec}
x_{ij} = 1 \Rightarrow s_j + \text{dur}(t_j) \leq d_j \quad \forall i, j
\sum_i x_{ij} = |\mathcal{F}(t_j)| \quad \forall j
x_{ij} \in \{0, 1\}, \quad s_j \geq 0

여기서 \mathbf{x}는 할당 결정 변수, \mathbf{s}는 각 과업의 시작 시점 변수, \text{prec}는 선행 제약 집합이다.

3.3 메타 휴리스틱 기반 스케줄링

대규모 문제에서 정확한 해법의 적용이 비실용적일 때, 메타 휴리스틱(meta-heuristic) 기법이 활용된다.

유전 알고리즘(Genetic Algorithm, GA): 스케줄을 염색체로 부호화하고, 교차(crossover)와 돌연변이(mutation) 연산을 통해 해 공간을 탐색한다. 염색체의 표현은 과업-로봇 할당과 과업 실행 순서를 동시에 부호화하는 2계층 표현(two-layer representation)이 일반적이다.

개미 군집 최적화(Ant Colony Optimization, ACO): 과업-로봇 할당 그래프 위에서 개미 에이전트가 페로몬을 기반으로 최적 할당을 탐색한다.

입자 군집 최적화(Particle Swarm Optimization, PSO): 연속 공간에서의 최적화를 이산적 할당 문제에 적용하여, 입자들이 협력적으로 최적 스케줄을 탐색한다.

4. 동기화 제약의 처리

4.1 랑데뷰 제약(Rendezvous Constraint)

협력 과업에서는 참여 로봇들이 특정 시점과 장소에서 **합류(rendezvous)**해야 하는 제약이 존재한다. 랑데뷰 제약은 다음과 같이 정의된다.

\forall r_i, r_j \in \mathcal{F}(t_k): |s(r_i, t_k) - s(r_j, t_k)| \leq \epsilon_t

여기서 s(r_i, t_k)는 로봇 r_i가 과업 t_k의 실행을 시작하는 시점이며, \epsilon_t는 허용되는 최대 시간 편차이다.

4.2 동시 실행 제약(Simultaneous Execution Constraint)

일부 협력 과업에서는 참여 로봇들의 행동이 정확히 동시에 수행되어야 한다. 예를 들어, 두 로봇이 대형 패널의 양쪽을 동시에 들어 올리는 과업에서는 행동의 시작과 종료가 동기화되어야 한다.

s(r_i, t_k) = s(r_j, t_k) \quad \wedge \quad \text{end}(r_i, t_k) = \text{end}(r_j, t_k)

4.3 핸드오프 제약(Handoff Constraint)

하나의 과업이 여러 로봇에 의해 순차적으로 수행되는 릴레이(relay) 방식의 임무에서는, 선행 로봇과 후속 로봇 사이의 핸드오프(handoff) 시점이 정확하게 조율되어야 한다.

\text{end}(r_i, t_k^{\text{phase1}}) = s(r_j, t_k^{\text{phase2}}) \quad \wedge \quad \text{pos}(r_i, \text{end}) = \text{pos}(r_j, \text{start})

5. 분산 협력 스케줄링

5.1 분산 제약 최적화(DCOP)

분산 환경에서의 협력 스케줄링은 **분산 제약 최적화 문제(Distributed Constraint Optimization Problem, DCOP)**로 모델링할 수 있다. DCOP에서 각 로봇은 자신의 결정 변수(과업 할당 및 스케줄)를 관리하며, 이웃 로봇과의 제약만을 고려하여 국소적으로 최적화를 수행한다.

DCOP의 대표적 해법으로 Max-Sum 알고리즘이 있으며, 이는 인수 그래프(factor graph) 위에서의 메시지 전달(message passing)을 통해 근사 최적 해를 탐색한다.

5.2 계약망 프로토콜(Contract Net Protocol, CNP)

Smith(1980)가 제안한 **계약망 프로토콜(Contract Net Protocol)**은 분산 과업 할당의 고전적 프레임워크이다. CNP에서의 과업 할당 과정은 다음과 같다.

1. 발주(Announcement): 관리자(manager) 로봇이 미할당 과업을 공고한다.
2. 입찰(Bidding): 계약자(contractor) 로봇들이 자신의 능력과 현재 부하를 고려하여 입찰을 제출한다.
3. 낙찰(Awarding): 관리자가 최적 입찰을 선택하여 과업을 할당한다.
4. 수행 보고(Reporting): 계약자가 과업 수행 결과를 관리자에게 보고한다.

CNP는 구현이 단순하고 통신 부하가 적으나, 전역 최적성을 보장하지 못하며 동적 환경에서의 재할당 지원이 제한적이라는 한계가 있다.

6. 시간 창(Time Window) 기반 스케줄링

과업에 시간 창(time window)이 부여될 때, 각 과업 t_j는 가장 이른 시작 시점 e_j와 가장 늦은 종료 시점 l_j를 가진다. 유효한 스케줄은 다음 조건을 만족해야 한다.

e_j \leq s_j \quad \wedge \quad s_j + \text{dur}(t_j) \leq l_j \quad \forall j

시간 창 기반 스케줄링은 **차량 경로 문제(Vehicle Routing Problem with Time Windows, VRPTW)**의 변형으로 모델링될 수 있으며, 이는 물류 로봇의 배달 임무 스케줄링에서 핵심적으로 활용된다.

7. 로봇 협력 스케줄링 사례

7.1 물류 창고의 다중 AGV 스케줄링

물류 창고에서 다수의 자동 유도 차량(AGV)이 물품 적재, 운반, 하역 임무를 협력적으로 수행할 때, 스케줄링 시스템은 주문 우선순위, AGV 간 경로 충돌, 충전 스테이션 가용성, 적하 지점의 혼잡도 등을 동시에 고려해야 한다.

7.2 건설 현장의 다중 로봇 협력

건설 로봇 시스템에서는 자재 운반 로봇, 용접 로봇, 검사 로봇 등이 공정 순서에 따라 협력하며, 선행 공정이 완료되어야 후속 공정이 시작될 수 있는 엄격한 선행 제약이 존재한다.

7.3 농업 로봇의 수확 스케줄링

농업 환경에서 다수의 수확 로봇이 넓은 농지를 분할하여 수확할 때, 작물의 성숙도에 따른 시간 창, 기상 조건에 의한 작업 가능 시간, 수확물 운반 트럭과의 동기화 등이 스케줄링의 핵심 제약이 된다.

8. 요약

협력 임무 스케줄링은 다중 로봇 시스템에서 과업 할당, 실행 순서 결정, 로봇 간 동기화를 통합적으로 관리하는 프레임워크이다. 경매 기반 할당(SSI Auction, CBBA), 최적화 기반 접근(MILP, CP), 메타 휴리스틱(GA, ACO, PSO), 분산 기법(DCOP, CNP) 등 다양한 알고리즘이 활용되며, 랑데뷰, 동시 실행, 핸드오프 등의 동기화 제약을 체계적으로 처리한다. 물류, 건설, 농업 등 다양한 응용 영역에서 협력 스케줄링의 효과적 적용은 다중 로봇 시스템의 성능을 결정하는 핵심 요인이다.

9. 참고 문헌

• Gerkey, B. P., & Matarić, M. J. (2004). “A formal analysis and taxonomy of task allocation in multi-robot systems.” International Journal of Robotics Research, 23(9), pp. 939–954.
• Choi, H. L., Brunet, L., & How, J. P. (2009). “Consensus-based decentralized auctions for robust task allocation.” IEEE Transactions on Robotics, 25(4), pp. 912–926.
• Korsah, G. A., Stentz, A., & Dias, M. B. (2013). “A comprehensive taxonomy for multi-robot task allocation.” International Journal of Robotics Research, 32(12), pp. 1495–1512.
• Smith, R. G. (1980). “The Contract Net Protocol: High-level communication and control in a distributed problem solver.” IEEE Transactions on Computers, 29(12), pp. 1104–1113.
• Nunes, E., Manner, M., Mitiche, H., & Gini, M. (2017). “A taxonomy for task allocation problems with temporal and ordering constraints.” Robotics and Autonomous Systems, 90, pp. 55–70.

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