⚡ electrical engineering

Motion planning for hundreds of floating robots

본 논문은 대규모 부유 로봇 군집의 충돌 회피를 병렬 상호작용 클러스터로 분해하여, 최대 500대의 로봇 시뮬레이션 및 실제 배포에서 검증된 충돌 없는 궤적을 신속하게 생성할 수 있는 확장 가능한 모션 플래닝 파이프라인을 제시한다.

원저자: Jan Kamm, Antonio Terpin, Raffaello D'Andrea, Aswin Ramachandran

게시일 2026-06-09

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Jan Kamm, Antonio Terpin, Raffaello D'Andrea, Aswin Ramachandran

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

당신이 거대한 호수 위에서 펼쳐지는 대규모 플로팅 댄스 쇼의 감독이라고 상상해 보세요. 당신에게는 수백 대의 작은 자율 주행 보트(로봇)들이 있고, 이들은 하트 모양에서 'Water'라는 글자 모양으로 형태를 바꾸는 것과 같이 한 대형에서 다른 대형으로 이동해야 합니다.

문제는 무엇일까요? 만약 500대의 보트 모두에게 어디로 가야 할지 한꺼번에 지시하려고 하면, 수학적 계산이 매우 복잡해진다는 점입니다. 모든 보트는 서로 충돌하지 않도록 피해야 합니다. 보트의 수가 늘어날수록, 피해야 하는 '회피 규칙'의 수는 폭발적으로 증가하며, 이로 인해 컴퓨터가 안전한 경로를 계산하는 데 너무 오랜 시간이 걸리게 됩니다.

이 논문은 이러한 댄스를 매우 빠르게 계획할 수 있는 새로운 방법을 제시합니다. 이를 통해 인간 디자이너가 움직임을 미세하게 조정하고 그 결과를 단 몇 초 만에 확인할 수 있도록 합니다. 규모가 큰 함대(fleet)를 대상으로도 말이죠.

그들이 어떻게 이 일을 해냈는지, 간단한 단계별로 설명해 드리겠습니다.

1. "교통 체증" 문제

보통 함대를 계획하는 것은 모든 조각이 서로 연결된 거대한 퍼즐을 푸는 것과 같습니다. 만약 500대의 로봇이 있다면, 컴퓨터는 수백만 개의 잠재적 충돌 가능성을 확인해야 합니다. 이는 마치 도시의 모든 자동차가 동시에 서로에게 말을 걸며 교통 상황을 조절해야 하는 상황과 같습니다. 너무 느려서 사람이 기다리기 힘든 수준이죠.

2. "그룹 채팅" 전략 (계층적 계획)

저자들의 시스템은 모든 사람에게 하나의 거대한 규칙 목록을 만드는 대신, 군중을 작은 그룹으로 나누는 스마트한 조직가처럼 행동합니다.

1단계: 러프한 스케치. 먼저, 컴퓨터는 모든 로봇을 위해 시작부터 끝까지 이어지는 빠르고 대략적인 선을 그립니다. 이 선에는 충돌이 포함될 수 있지만, 출발점을 제공합니다.
2단계: 클러스터 찾기. 컴퓨터는 이 러프한 스케치를 보고 "누가 실제로 서로 부딪히고 있는가?"를 묻습니다. 그리고 서로 가까이 있는 로봇들만을 보여주는 지도(그래프)를 구축합니다.
3단계: 분리하기. 이렇게 "부딪히는" 로봇들을 작은 클러스터(무리)로 묶습니다. 멀리 떨어져 있는 로봇들은 서로 대화할 필요가 없습니다.
4단계: 병렬 해결. 이제, 하나의 슈퍼컴퓨터가 호수 전체를 해결하는 대신, 시스템은 각 작은 그룹을 서로 다른 프로세서로 보내 각자의 미니 퍼즐을 동시에 풀게 합니다. 이는 한 사람이 교통 체증을 하나씩 해결하는 대신, 50명의 사람이 50개의 서로 다른 교통 체증을 동시에 해결하는 것과 같습니다.

3. "안전 버퍼"

때로는 한 그룹의 충돌을 해결하면, 실수로 인접한 다른 그룹에서 충돌을 유발할 수도 있습니다. 이를 처리하기 위해 시스템은 그룹 주변에 "안전 버퍼"(약간의 추가 시간과 공간)를 추가합니다. 만약 두 그룹이 너무 많이 겹치면, 시스템은 특정 순간 동안만 영리하게 두 그룹을 하나로 합치고, 더 큰 문제를 해결한 뒤 다시 분리합니다. 이는 시스템이 똑같은 실수를 고치느라 무한 루프에 빠지는 것을 방지합니다.

4. "스마트 수학" 기술

각 작은 그룹 내부에서 컴퓨터는 경로를 매끄럽게 만들기 위해 특정 유형의 수학(순차적 볼록 최적화, Sequential Convex Programming)을 사용합니다. 저자들은 방정식을 쓰는 방식을 변경함으로써 이 수학을 개선했습니다. 이는 마치 지저분한 손글씨 노트를 깔끔하고 정리된 스프레드시트로 바꾸는 것과 같습니다. 이 변화는 컴퓨터가 수학 문제를 훨씬 더 빠르고 안정적으로 풀 수 있게 하며, 특히 로봇들이 빽빽하게 모여 있을 때 더욱 효과적입니다.

실제 세계에서의 증명

팀은 단순히 컴퓨터 시뮬레이션에 그치지 않고, 실제로 현장에서 테스트했습니다.

취리히 호수: 24대의 플로팅 로봇이 공연을 수행하도록 성공적으로 연출했습니다.
베니스 비엔날레 (2025): 8대의 로봇을 활용한 예술 설치 작품에 이 기술을 사용했습니다.
시뮬레이션: 컴퓨터 시뮬레이션을 통해 최대 500대의 로봇까지 작동함을 입증했습니다.

핵심 요약

주요 성과는 속도와 신뢰성입니다. 이전에는 수백 대의 로봇을 위한 계획을 세우는 데 몇 시간이 걸리거나 아예 실패할 수도 있었습니다. 하지만 이 새로운 파이프라인을 사용하면, 디자이너가 몇 개의 "키프레임"(춤의 시작과 끝 위치)을 움직이는 것만으로도 몇 초 만에 안전하고 충돌 없는 계획을 얻을 수 있습니다. 이는 인간이 컴퓨터의 응답을 기다릴 필요 없이, 현장에서 즉석으로 안무를 수정하며 복잡하고 상호작용적인 로봇 쇼를 만들 수 있게 해줍니다.

기술 요약: 수백 대의 부유 로봇을 위한 모션 플래닝

문제 정의
본 논문은 평면 매니폴드 상에서 작동하는 대규모 함대 규모의 전방향 부유 로봇(수상 로봇)을 위한 충돌 없는 동적 실행 가능한 궤적을 계획하는 과제를 다룹다. 수직 기동을 통해 밀집된 전환 구간을 회피할 수 있는 항공 드론과 달리, 수상 로봇은 2D로 제한되어 있어 조정 및 충돌 회피가 본질적으로 더 어렵다. 플래닝의 맥락은 인터랙티브 쇼 디자인으로, 디자이너는 희소한 키프레임(시작 및 종료 구성)을 지정하고, 수 분에 걸쳐 수천 개의 타임 스텝을 아우르는 궤적을 생성하기 위해 즉각적인 피드백(수 초 이내)을 요구한다.

핵심적인 어려움은 충돌 회피의 확장성(scalability)에 있다. 함대 규모( $N$ )가 증가함에 따라 에이전트 간 결합(inter-agent coupling)이 급격히 증가하며(종종 이차 함수적으로 증가), 이는 쌍별 충돌 제약 조건의 수를 $\binom{N}{2}K$ ( $K$ 는 타임 스텝 수)로 늘린다. 큰 $N$ (예: 500)과 $K$ (예: 1000)의 경우, 표준 순차적 볼록 계획법(Sequential Convex Programming, SCP) 정식화는 수억 개의 비제로(non-zero) 항목을 가진 이차 계획법(Quadratic Program, QP)을 생성하여 반복적인 디자인 루프를 수행하기에 계산적으로 불가능하게 만든다.

방법론
저자들은 전역적으로 결합된 문제를 더 작고 독립적인 하위 문제들로 분해하는 확장 가능한 계층적 플래닝 파이프라인을 제안한다. 이 파이프라인은 네 가지 주요 단계로 구성된다:

초기화 및 할당 (Initialization and Allocation):
- 프로세스는 로봇을 목표 위치에 매칭하는 최소 비용 할당 문제로 시작된다. "레이블링된(labelled)" 로봇(사용자가 정의한 고정 타겟을 가진 로봇)의 경우, 특정 매칭을 강제하기 위해 비용은 0 또는 무한대로 설정된다. "레이블링되지 않은(unlabelled)" 로봇의 경우, 불필요한 교체를 줄이기 위해 유클리드 거리를 비용으로 사용하여 총 변위를 최소화한다.
- 초기 궤적은 시작 위치와 종료 위치 사이의 선형 보간을 통해 생성된다. 이 초기화 단계는 일반적으로 충돌이 없는 상태가 아니다.
충돌 그래프 구축 (Collision Graph Construction):
- 노드가 로봇-시간 쌍을 나타내는 시공간 그래프를 구축한다.
- **공간 엣지(Spatial edges)**는 동일한 타임스텝에서 안전 반경 $R$ 내에 있는 로봇들을 연결한다.
- **시간 엣지(Temporal edges)**는 연속된 타임스텝에 걸쳐 로봇 자신과 충돌이 발생하는 경우 로봇을 연결한다.
- 이 그래프의 연결 성분(connected components)은 "충돌 클러스터"를 정의한다. 저자들은 효율적인 쌍별 위반 탐지를 위해 KD-트리 데이터 구조를 활용하며, 이를 통해 단순한 쌍별 체크 방식보다 거의 2000배 빠른 속도를 달성했다.
클러스터링 및 분해 (Clustering and Decomposition):
- 옵티마이저가 우회 경로를 계획할 수 있는 자유도를 제공하기 위해, 각 클러스터의 시간 윈도우를 하이퍼파라미터 $B$ (3초로 설정)만큼 확장(버퍼링)한다.
- 겹치는 버퍼링된 클러스터들은 유니온-파인드(union-find) 절차를 사용하여 병합된다. 하위 문제가 너무 커져서 병렬 처리의 이점이 사라지는 것을 방지하기 위해 복잡도 캡(complexity cap)이 적용된다. 만약 병합이 QP 행렬의 비제로 항목 임계값을 초과하면, 결과로 발생하는 하위 문제들의 최대 복잡도를 최소화하는 스코어링 메커니즘을 사용하여 그룹을 분할한다.
하위 문제 해결 및 병합 (Subproblem Solving and Merging):
- 각 클러스터는 SCP 프레임워크를 사용하여 독립적으로, 그리고 병렬적으로 해결된다.
- 정식화 개선: 본 논문은 결정 벡터에 위치와 속도( $\chi = [p, v]$ )를 모두 포함하는 "직접 전사(direct transcription)" 정식화를 도입한다. 이는 역학을 로컬 등가 제약 조건으로 변환하며, 기존 연구에서 사용된 "직접 슈팅(direct shooting)" 정식화와 비교했을 때 제약 행렬의 희소성을 크게 개선한다(복잡도를 $O(N^2K^2)$ 에서 $O(N^2K)$ 로 감소시킴).
- 강건성(Robustness): 대칭적 구성에 대한 초기값 섭동(perturbation), 해를 찾지 못할 경우의 적응형 이산화 조밀도 축소(coarsening), 그리고 경량화된 폴리싱(polishing) 단계 등의 메커니즘이 포함된다.
- 사이클 탐지: 클러스터 병합이 진동하는 충돌 패턴을 유발하는 순환 의존성을 감지한다. 사이클이 감지되면, 충돌하는 하위 문제들은 다음 반복을 위해 하나의 공동 하위 문제로 묶인다.
- 마지막으로, 로컬 솔루션들이 글로벌 궤적으로 병합되며, 충돌 없는 솔루션이 발견될 때까지 루프가 반복된다.

주요 기여

확장 가능한 계층적 파이프라인: 충돌 그래프를 구축하고, 상호작용 클러스터로 문제를 분해하며, 이를 병렬로 해결함으로써 수백 대의 로봇에 대해 수 초 내에 플래닝을 가능하게 하는 방법론을 제시한다.
강건한 분해 메커니즘: 빠른 그래프 업데이트, 버퍼링 전략, 하위 문제 폭발을 방지하기 위한 복잡도 캡, 그리고 진동을 방지하기 위한 사이클 탐지를 포함한 일반적인 병목 현상 처리 기술을 제공한다.
최적화 재정식화: 클러스터 수준의 궤적 최적화를 위해 직접 전사 정식화로 전환함으로써, 특히 레이블링된 로봇의 비율이 높은 구성에서 QP 희소성과 솔버의 강건성을 향상시킨다.

결과 및 검증
시스템은 시뮬레이션과 두 차례의 실세계 배포를 통해 검증되었다:

시뮬레이션: 파이프라인은 최대 500대의 로봇과 1000개의 타임 스텝에 대해 충돌 없는 궤적을 성공적으로 생성했다. 500대 로봇 케이스 스터디에서, 솔버는 레이블링된 로봇이 30%일 때까지 100%의 수렴율을 보였고, 그 이상의 비율에서도 99%를 기록했으며, 계산 시간은 통상 수 초 미만이었다.
실세계 배포 1 (취리히 호수): 24대의 로봇 함대가 1~2분에 걸친 전환(400개 이상의 타임 스텝)을 위해 안무되었다. 디자이너는 키프레임을 반복적으로 조정하고 수 초 내에 궤적을 재생성할 수 있었다.
실세계 배포 2 (베네치아 비엔날레 2025): 8대의 로봇 함대가 2000개 이상의 타임 스텝에 걸친 전환을 수행했다. 2491단계의 궤적이 1.23초 만에 계산되었다.

의의
본 논문은 공학 중심의 이 파이프라인이 표면 환경에서의 다중 로봇 모션 플래닝의 핵심적인 확장성 병목 현상을 해결한다고 주장한다. 문제를 분해하고 솔버 정식화를 최적화함으로써, 이 접근 방식은 전통적인 단일 구조(monolithic) SCP 파이프라인보다 수십 배 더 빠르다. 이러한 속도는 디자이너가 희소한 키프레임을 반복적으로 조정하고, 충돌 없는 동적 실행 가능한 궤적에 대해 즉각적인 피드백을 받을 수 있게 함으로써, 기존의 계산적 제약으로 인해 어려웠던 인터랙티브한 안무 디자인 경험을 가능하게 한다.