💻 computer science

Distributed Model Predictive Control with Connectivity-based Contracts

본 논문은 각 에이전트에게 이웃 간의 교환으로부터 도출된 국소적 '연결성 계약(connectivity contract)'을 할당함으로써, 전역적 연결성 가정 없이도 네트워크 응집성, 충돌 회피 및 제약 조건 만족을 보장하여 이동 로봇의 팀 연결성을 보장하는 확장 가능한 분산 모델 예측 제어(DMPC) 프레임워크를 제안한다.

원저자: Jorit Geurts, Danilo Saccani, Melanie N. Zeilinger, Andrea Carron

게시일 2026-09-18

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Jorit Geurts, Danilo Saccani, Melanie N. Zeilinger, Andrea Carron

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

무너진 건물 속에서 생존자를 수색하거나 재난 지역에 물자를 전달하는 등, 좁은 공간을 함께 이동하는 소형 자율 주행 차량 군집을 상상해 보십시오. 이 기계들이 하나의 팀으로 기능하기 위해서는 서로의 위치와 계획을 공유하며 충돌을 피하고 움직임을 조절하기 위해 끊임없이 대화해야 합니다. 만약 집단이 통신 능력을 상실하면 팀은 무너집니다. 정보가 흐르지 못하게 되고, 안전이 위협받으며, 임무는 실패합니다. 엔지니어들의 과제는 로봇들이 목표에 도달하기 위해 자유롭게 움직이면서도, 서로 너무 멀어져서 연락이 끊어지는 일이 없도록 능동적으로 보장하는 제어 시스템을 설계하는 것입니다. 이는 매우 어려운 균형 잡기인데, 왜냐하면 집단의 연결성을 보장하는 수학적 규칙들은 복잡하고 상호 의존적이어서, 중앙 컴퓨터가 모두에게 명령을 내리지 않고도 모든 로봇의 안전한 경로를 실시간으로 계산하기 어렵기 때문입니다.

연구자들은 '분산 모델 예측 제어(distributed model predictive control)'라는 방법을 사용하여 이 문제를 해결하려는 방법을 오랫동안 모색해 왔습니다. 이 방법은 각 로봇이 이웃으로부터 알고 있는 정보를 바탕으로 자신의 미래 경로를 계산하는 방식입니다. 그러나 기존의 대부분의 접근 방식은 네트워크가 연결된 상태를 유지한다고 단순히 가정할 뿐, 이를 능동적으로 강제하는 시스템을 구축하지는 않습니다. 연결성에 대한 수학적 조건을 직접 적용하면, 모든 로봇을 다른 모든 로봇과 연결하는 복잡한 제약 조건의 그물망이 만들어져, 경로를 빠르고 독립적으로 계산할 수 있는 능력을 파괴하게 됩니다. 이를 극복하기 위해 ETH 취리히와 EPFL의 엔지니어 팀은 복잡한 전역 규칙을 단순한 지역적 합의로 대체하는 새로운 프레임워크를 개발했습니다. 그들은 이 합의를 "계약(contracts)"이라고 부릅니다.

이 새로운 시스템에서는 각 로봇에게 짧은 시간 동안 이동할 수 있는 특정 안전 구역, 즉 공간의 국소적 영역이 할당됩니다. 이 구역은 임의로 정해진 것이 아닙니다. 이 구역들은 인접한 이웃과의 단 한 번의 정보 교환을 바탕으로 정교하게 계산됩니다. 핵심 통찰은 모든 로봇이 자신에게 할당된 구역 내에 머물기만 하면, 집단 전체의 연결성이 수학적으로 보장된다는 점입니다. 연구진은 통신 링크를 유지할 수 있을 만큼 구역들이 서로 겹치도록 설계하여, 네트워크가 끊어지는 것을 방지하는 안전망을 효과적으로 구축했습니다. 연구진은 전체 군집을 위한 거대하고 불가능한 방정식을 푸는 대신, 각 로봇이 자신의 움직이는 경계 안에서 목표에 도달하는 법이라는 단순하고 독립적인 문제만을 풀도록 설계했습니다.

연구팀은 컴퓨터 시뮬레이션과 실제 하드웨어 실험 모두에서 소형 자동차 형태의 로봇을 사용하여 이 접근 방식을 테스트했습니다. 시뮬레이션에서는 장애물이 가득한 복잡한 환경에 7대의 로봇을 배치하고 특정 목표 지점으로 항해하도록 했습니다. 그들은 이 새로운 방법과, 연결성을 무시하거나 혹은 모든 로봇이 밀접하게 결합되어야 하는 무겁고 복잡한 계산을 통해 연결성을 강제하려 했던 기존 기술들을 비교했습니다. 결과는 명확했습니다. 기존 방식들은 집단의 연결성을 유지하는 데 실패하거나, 실시간 제어를 할 수 없을 정도로 많은 컴퓨팅 파워를 요구했습니다. 반면, 새로운 계약 기반 시스템은 모든 실험에서 네트워크 연결을 유지했으며, 로봇들이 충돌을 피하면서 목적지에 효율적으로 도달하게 했습니다. 로봇들은 단 몇 밀리초 만에 개별 경로 계획 문제를 해결했으며, 이 속도는 소형 저전력 컴퓨터에서도 실시간 제어가 가능함을 보여줍니다.

연구진이 Wi-Fi와 모션 캡처 센서를 갖춘 실제 로봇을 사용하여 시스템을 물리적 하드웨어로 옮겼을 때도 결과는 동일했습니다. 로봇들은 복잡한 환경을 성공적으로 항해하며 여정 내내 연결된 통신 네트워크를 유지했습니다. 새로운 계약이 없다면 로봇들은 서로 멀어져 네트워크가 끊어지고, 연결성의 대수적 척도가 0으로 떨어지게 됩니다. 하지만 계약이 적용되면 네트워크는 견고하게 유지되며, 로봇들은 장애물을 피하면서 통신 범위 내에 안전하게 머물렀습니다. 이 시스템은 단순한 지역적 규칙을 통해 복잡한 집단 행동을 강제할 수 있음을 입증했으며, 중앙의 '두뇌'나 지속적이고 무거운 연산 없이도 군집이 하나의 응집된 단위로서 작동할 수 있게 했습니다. 이 연구는 로봇들이 어디로 갈 수 있는지에 대한 합의 방식을 재고함으로써, 엔지니어들이 안전하고 확장 가능하며, 무질서하고 예측 불가능한 현실 세계에서도 작동할 수 있는 자율 팀을 만들 수 있음을 보여줍니다.

기술 요약: 연결성 기반 계약을 이용한 분산 모델 예측 제어(Distributed Model Predictive Control)

문제 정의
수색 및 구조, 협동 운송과 같은 작업을 수행하는 다중 에이전트 로봇 시스템(예: 모바일 로봇 군집)은 조정을 위해 지속적인 통신에 의존한다. 분산 모델 예측 제어(DMPC)는 상태/입력 제약 조건을 처리하고 작업 의존적 목적 함수를 최별화하기 위한 매력적인 프레임워크이지만, 기존의 대부분의 방식은 통신 네트워크가 연결성을 능동적으로 강제하기보다는 연결된 상태로 유지된다고 가정한다. 만약 연결성이 상실되면 정보 전파가 실패하여 안전과 성능이 저해된다.

연결성을 DMPC 내에 강제하는 것은 수학적으로 까다롭다. 그래프 라플라시안(Graph Laplacian)의 피들러 고유값( $\lambda_2$ )의 양수성이라는 표준 조건은 본질적으로 비볼록(nonconvex)하며, 모든 에이전트를 서로 결합시킨다. 이러한 전역적 결합은 확장 가능한 분산형 실시간 제어기에 연결성 제약을 삽입하는 것을 어렵게 만든다. 기존 방법들은 보수적인 포텐셜 필드(potential fields)를 사용하거나, 최적 제어와 통합되지 않는 독립적인 연결성 제어기를 사용하거나, 계산량이 많은 결합된 최적화 문제를 야기하는 비볼록 고유값 제약을 직접 삽입하는 방식을 취한다.

방법론
저자들은 전역적이고 비볼록한 연결성 제약을 일-홉(one-hop) 이웃 정보로부터 유도된 국소적이고 볼록한 제약으로 대체하는 계약 기반 DMPC 프레임워크를 제안한다.

연결성 계약(Connectivity Contracts): 전역적인 그래프 상태를 최적화하는 대신, 각 에이전트는 예측 수평선(prediction horizon) 동안 "연결성 계약"을 할당받는다. 계약은 에이전트의 예측 위치가 존재할 수 있는 국소 영역(집합)을 규정한다.
- 구성: 계약은 인접한 이웃 간에 공유되는 "제안된 궤적(proposed trajectory)"을 중심으로 구축된다. 유지되는 스패닝 서브그래프(spanning subgraph) $T_t$ 의 모든 에지 $(i, j)$ 에 대해, 두 에이전트는 제안된 위치의 중점을 중심으로 하는 반지름 $r_{com}/2$ 의 공유 쌍별 구(pairwise ball) $B_{ij,k|t}$ 내에 머물기로 합의한다.
- 에이전트 계약: 에이전트의 특정 계약 $C_{i,k|t}$ 는 $T_t$ 에 속한 인접 에지들과 관련된 모든 쌍별 구들의 교집합이다.
- 보장: 모든 에이전트가 할당된 계약 내에 머문다면, 연결된 에이전트 쌍 사이의 거리는 통신 범위 $r_{com}$ 이내로 유지됨이 보장되며, 이를 통해 $T_t$ 의 연결성이 보존된다.
국소 최적화 (FHOCP): 계약이 계산되면, 각 에이전트는 완전히 분리된 유한 수평 최적 제어 문제(FHOCP)를 해결한다. 중앙 집중식 문제의 결합된 충돌 회피 및 연결성 제약은 집합 멤버십 제약(에이전트의 위치가 자신의 충돌 및 연결성 계약 내에 있어야 함)으로 대체된다. 이는 에이전트 간의 최적화 단계에서의 결합을 제거한다.
재귀적 가능성(Recursive Feasibility): 이 프레임워크는 시스템이 $t=0$ 에서 실행 가능하다면 모든 $t$ 에 대해 실행 가능함을 보장한다. 이는 다음을 통해 달성된다:
- 로컬 제약, 충돌 계약 및 연결성 그래프 $T_t$ 를 만족하는 "호환 가능한 제안 궤적"을 사용한다.
- 이전 단계에서 이동된(shifted) 최적 궤적을 사용하여 매 단계마다 계약을 업데이트한다.
- 전체 수평선 동안 연결된 스패닝 서브그래프 $T_t$ 를 유지한다(이는 정적이거나 분산 스패닝 트리 알고리즘을 통해 업데이트될 수 있다).

주요 기여
본 논문의 세 가지 주요 기여는 다음과 같다:

연결성 계약: 비볼록 피들러 고유값 제약을 대체하는 볼록하고 시변적인 국소 집합을 도입하였다. 이 계약들은 에이전트들이 반복적인 조정 없이도 완전히 분리된 최적화 문제를 해결할 수 있도록 하면서 연결된 스패닝 서브그래프를 보존한다.
이론적 보장: 저자들은 계약의 유효성 조건을 제공하며, 폐루프 시스템이 재귀적 가능성을 유지하고, 충돌을 회피하며, 로컬 상태/입력 제약 및 연결성 요구 사항을 만족함을 증명한다.
실험적 검증: 소형 자율 자동차 로봇을 이용한 시뮬레이션과 하드웨어 실험을 통해 제안된 방식을 검증하였다.

결과

시뮬레이션: 복잡한 환경에서의 7개 에이전트 실험을 통해 제안된 방식과 충돌 전용 계약 DMPC, 그리고 고유값 제약 MPC(순차 이차 계획법 사용)를 비교하였다.
- 충돌 전용 DMPC는 31회의 실행 중 31회 모두 연결성 위반이 발생했다.
- 고유값 제약 MPC는 수렴할 때까지 반복 수행했을 때만 연결성을 유지했으며, 막대한 계산 비용을 초래했다(중앙값 계산 시간 약 219ms vs. 제안된 방식의 약 2ms). 제안된 방식의 속도에 맞춰 단일 실시간 반복으로 제한했을 때, 고유값 방식은 4회에서 네트워크 단절(연결 실패)이 발생했고, 6회에서 안전 거리 위반이 발생했다.
- 제안된 방식은 31회 실행 모두에서 연결성을 유지하였으며, 중앙값 계산 시간은 2.02ms였다.
하드웨어: Wi-Fi 통신을 사용하는 1/28 스케일 자동차형 로봇에 대한 실험을 통해 시뮬레이션 결과를 확인하였다. 연결성 계약이 없을 경우 대수적 연결성 $\lambda_2$ 가 0으로 떨어졌으나(네트워크 단절), 제안된 계약을 사용할 경우 $\lambda_2$ 가 엄격하게 양수를 유지하며 시스템이 참조 궤적을 추종하면서 동시에 장애물을 회피하는 데 성공하였다.

의의
본 논문은 이 프레임워크가 확장 가능한 분산 제어와 엄격한 연결성 강제 사이의 간극을 성공적으로 메웠다고 주장한다. 로컬 계약을 통해 최적화 문제를 분리함으로써, 이 방법은 결합된 비볼록 문제를 푸는 계산적 부담을 피하면서도 네트워크 연결성, 충돌 회피 및 제약 조건 만족에 대한 공식적인 보장을 제공한다. 이 접근 방식은 통신 신뢰성이 중요한 실시간 다중 에이전트 조정을 위한 실용적인 솔루션으로 제시된다. 향후 연구 과제로 이질적인 통신 반경, 비동기 업데이트 및 적응형 계약 그래프 선택 등이 언급되었다.

유사한 논문