🤖 AI

A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning

이 논문은 평생 지속되는 다중 에이전트 경로 탐색(Lifelong Multi-Agent Path Finding)에 대한 롤링 호라이즌 충돌 해결(Rolling-Horizon Collision Resolution, RHCR) 프레임워크의 근사 최적성을 이론적으로 증명하고, 이러한 통찰을 활용하여 근사 최적성 보장을 유지하면서도 계산 비용을 현저히 낮추어 높은 처리량과 확장성을 달성하기 위해 에이전트를 분할하는 병렬 계획 방식인 그룹 분산형 RHCR(Group Decentralized RHCR, GD-RHCR)을 제안한다.

원저자: Alex DeWeese, Jiaoyang Li, Guannan Qu

게시일 2026-08-19

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Alex DeWeese, Jiaoyang Li, Guannan Qu

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

현대 물류의 분주하고 자동화된 세계에서, 디지털 지도 위에서는 매 초마다 조용한 도전이 펼쳐지고 있습니다. 수백 대의 작은 로봇들이 선반, 벽, 그리고 서로를 피해 끊임없이 항해하며 한 지점에서 다른 지점으로 패키지를 옮겨야 하는 창고 바닥을 상상해 보십시오. 이것은 다중 에이전트 경로 탐색(multi-agent pathfinding)의 영역으로, 많은 움직이는 물체들이 충돌 없이 시작점에서 도착점까지 도달하는 방법을 찾아내는 데 전념하는 분야입니다. 이 로봇들이 단 한 번의 여정만을 수행할 때는 문제가 어렵긴 해도 관리 가능한 수준입니다. 하지만 실제 창고에서는 작업이 멈추지 않습니다. 로봇이 패키지를 내려놓자마자 즉시 새로운 패키지를 배정받기 때문입니다. 이 연속적인 순환을 '평생 경로 탐색(lifelong pathfinding)'이라고 합니다. 목표는 간단합니다. 로봇들을 최대한 빠르게 움직이게 하여 패키지 배송량을 극대화하는 것입니다. 어려움은 수학에 있습니다. 바닥에 더 많은 로봇이 추가될수록, 그들이 충돌할 수 있는 가능한 경우의 수가 너무 빠르게 증가하여 경로를 계획하려는 컴퓨터가 과부하되어 전체 운영을 중단시킬 수 있습니다.

연구자들은 오랫동안 속도와 안전 사이의 균형을 모색해 왔습니다. '롤링 호라이즌 충돌 해결(rolling-horizon collision resolution)'이라 불리는 한 가지 인기 있는 방법은, 미래의 짧은 거리까지 내다보며 모든 로봇의 안전한 경로를 동시에 계획하는 방식입니다. 이 접근법은 교통 흐름을 원활하게 유지하고 정체를 피하는 데 탁-월하지만, 무거운 대가를 치러야 합니다. 컴퓨터는 몇 초마다 모든 로봇의 경로를 동시에 계산하기 위해 엄청난 양의 작업을 수행해야 합니다. 또 다른 방법은 매우 빠르지만, 종종 근시안적이고 탐욕적인 결정을 내려 로봇들이 서로를 기다리며 멈춰 서는 교착 상태(deadlock)를 초래할 수 있습니다. 카네기 멜런 대학교 연구진의 핵심 질문은, 신중하고 느린 방식의 높은 성능을 유지하면서도 컴퓨터가 다운되지 않고 수백 대의 로봇을 처리할 수 있을 만큼 충분히 빠르게 만들 수 있느냐는 것이었습니다.

알렉스 드위스(Alex DeWeese), 조양 리(Jiaoyang Li), 관난 퀴(Guannan Qu)가 이끄는 팀은 로봇들이 어떻게 통신하고 계획하는지를 재고함으로써 이 문제에 접근했습니다. 그들은 먼저 이론적인 지점을 증명하며 시작했습니다. 신중하고 느린 방식이 효과적인 이유는 너무 멀리 떨어진 시간대의 상호작용을 무시하기 때문이라는 점입니다. 만약 로봇이 향후 20단계의 경로를 계획하고 있다면, 50단계 후에 발생할 수도 있는 충돌을 걱정할 필요가 없습니다. 이러한 통찰력을 바탕으로, 그들은 '그룹 분산형 롤링 호리즌 충돌 해결(Group Decentralized Rolling-Horizon Collision Resolution)'이라는 새로운 프레임워크를 제안했습니다. 창고 전체를 한꺼번에 해결해야 할 하나의 거대한 문제로 취급하는 대신, 이 새로운 시스템은 로봇들을 서로 얼마나 가까이 있는지에 따라 작고 독립적인 그룹으로 나눕니다. 서로 멀리 떨어져 있는 로봇들은 서로 다른 그룹에 배치되며, 계획이 진행되는 동안 서로를 무시하고 병렬적으로 경로를 계획할 수 있습니다.

이러한 분할은 임의적인 것이 아닙니다. 이는 특정 거리 임계값을 기준으로 합니다. 두 로봇이 특정 범위 내에 있으면 동일한 그룹의 일부로 간주되어 서로 충돌하지 않도록 조정해야 합니다. 만약 그 범위를 벗어나면, 시스템은 그들이 계획 창(planning window) 내에서 충 collision할 가능성이 없다고 가정하고 별도로 계획을 세울 수 있습니다. 연구진은 이러한 분리가 솔루션의 품질을 크게 해치지 않는다는 것을 수학적으로 증명했습니다. 실제로 그들은 이 새로운 그룹 기반 방식의 성능이 원래의 느린 방식처럼 최적의 솔루션에 매우 가깝게 유지된다는 것을 보여주었습니다. 핵심적인 차이점은 문제를 더 작은 덩어리로 나눔으로써 컴퓨터가 각 덩어리를 훨씬 더 빠르게 해결할 수 있다는 것입니다. 또한, 이 시스템은 필요한 경우에만 그룹을 대상으로 재계획을 수행할 만큼 영리합니다. 만약 로봇 그룹이 미리 계산된 경로를 따라 원활하게 움직이고 있다면, 컴퓨터는 새로운 로봇이 해당 구역에 진입하는 등의 변화가 생기기 전까지는 시간을 낭비하여 경로를 다시 계산하지 않습니다.

아이디어를 테스트하기 위해 연구진은 단순한 개방형 바닥부터 장애물이 많은 복잡한 창고 설계에 이르기까지 다양한 지도 레이아웃에서 광범위한 시뮬레이션을 실행했습니다. 그들은 이 새로운 방식을 표준적인 신중한 방식 및 빠른 탐욕적 방식과 비교했습니다. 결과는 놀라웠습니다. 많은 시나리오에서 새로운 방식은 신중하고 느린 방식과 거의 동일한 높은 처리량(시간당 거의 동일한 양의 패키지 배송)을 달-성하면서도, 훨씬 적은 컴퓨팅 파워로 이를 수행했습니다. 일부 테스트에서는 단일 계획을 계산하는 데 걸리는 시간이 거의 25배나 단축되었습니다. 더 중요한 것은, 로봇 수가 증가해도 새로운 방식이 무너지지 않았다는 점입니다. 표준적인 신중한 방식은 로봇 수가 늘어남에 따라 결국 유용하지 않을 정도로 느려지겠지만, 그룹 기반 방식은 수백 대의 에이전트를 처리하면서도 여전히 잘 작동했습니다.

또한 이 연구는 환경의 물리적 레이아웃이 방식의 성공에 어떤 영향을 미치는지 밝혀냈습니다. 장애물이 많고 좁은 통로가 있는 지도에서는 로봇들이 자연스럽게 작고 뚜렷한 그룹을 형성하는데, 이는 장벽 때문에 서로를 볼 수 없거나 도달할 수 없기 때문입니다. 이러한 토폴로지는 새로운 방식이 더 잘 작동하게 만듭니다. 그룹이 더 작고 독립적으로 유지되기 때문입니다. 반면, 장애물이 거의 없는 매우 개방된 지도에서는 로봇들이 더 큰 그룹을 형성하여 더 많은 조정이 필요하지만, 시스템은 여전히 탐욕적인 대안들보다 우수한 성능을 보여주었습니다. 연구진은 또한 시스템이 혼잡도에 따라 특정 그룹이 너무 붐빌 경우 더 빠르고 단순한 계획 알고리즘으로 전환할 수 있음을 발견했으며, 이를 통해 가장 어려운 조건에서도 전체 시스템이 계속 움직일 수 있도록 보장했습니다.

이 연구는 로봇이 얼마나 앞을 내다봐야 하는지에 대한 이론적 한계를 이해함으로써, 엔지니어들이 안전하면서도 확장 가능한 시스템을 설계할 수 있음을 보여줍니다. 이 새로운 프레임워크는 슈퍼컴퓨터 없이도 자동화된 창고를 최고 효율로 운영할 수 있는 방법을 제공합니다. 이는 대규모 로보틱스의 미래가 모든 기계의 모든 움직임을 계산하는 단일한 거대한 뇌에 의존하는 것이 아니라, 병렬로 작동하는 작고 조정된 마음들의 네트워크에 달려 있을 수 있음을 시사합니다. 연구진은 신중한 계획의 안전함과 부드러움, 그리고 실제 응용에 필요한 속도와 확장성을 결합하여 두 마리 토끼를 모두 잡을 수 있음을 보여주었습니다. 자동화된 시스템이 배송 드론부터 공장 바닥에 이르기까지 우리 일상생활에서 점점 더 흔해짐에 따라, 이러한 방식은 기계들이 원활하게 협력하여 분주한 창고의 복잡한 혼돈을 유동적이고 효율적인 흐름으로 바꾸는 데 필수적일 것입니다.

기술 요약: 그룹 분산 계획을 이용한 병렬 평생 MAPF를 위한 이론적 프레임워크

1. 문제 정의

본 논문은 에이전트들이 장애물 및 에이전트 간 충돌을 피하면서 한 목적지에서 다른 목적지로 지속적으로 이동해야 하는 평생 다중 에이전트 경로 탐색(Lifelong Multi-Agent Path Finding, L-MAPF) 문제를 다룹다. 주요 목표는 처리량(예: 단위 시간당 달성된 목표 수)을 극대화하는 것이다.

롤링 호라이즌 충돌 해결(Rolling-Horizon Collision Resolution, RHCR) 프레임워크는 L-MAPF를 위한 고성능 솔루션으로 널리 인정받고 있지만, 심각한 계산적 병목 현상을 겪는다. RHCR은 짧은 간격으로 일회성(one-shot) MAPF 솔버(예: Priority Based Search 또는 Conflict Based Search)를 반복적으로 호출한다. 에이전트 수가 증가함에 따라 이러한 솔버의 계산 비용은 기하급수적으로 증가하며, 이는 RHCR의 적용 범위를 적은 수의 에이전트로 제한한다. 반면, **PIBT(Priority Inheritance with Backtracking)**와 같은 더 빠른 탐욕적(greedy) 방법은 확장성은 뛰어나지만, 이론적인 최적성 보장이 부족하고 데드락(deadlock)이 발생할 수 있다.

핵심 과제는 임의의 휴리스틱에 의존하지 않으면서도, 높은 처리량과 이론적 성능 보장을 유지하면서 계산 비용을 획기적으로 줄이는 병렬화된 RHCR 버전을 개발하는 것이다.

2. 방법론

이론적 기초: LI-MDP

저자들은 국소적 상호 의존 다중 에이전트 MDP(Locally Interdependent Multi-Agent MDP, LI-MDP) 프레임워크(DeWeese와 Qu 2024, 2025)에 기반하여 접근한다. 이들은 L-MAPF 문제를 가시성 반경(visibility radius)에 의해 정의된 국소적 상호작용을 가진 할인된(discounted) MDP로 모델링한다.

RHCR 분석: 본 논문은 먼저 바닐라 RHCR이 이 할인된 설정에서 근사 최적(near-optimal)임을 증명한다. 구체적으로, RHCR과 최적 정책 사이의 부최적성 격차(suboptimality gap)는 계획 호라이즌( $H$ )이 증가함에 따라 지수적으로 감소한다. 결정적으로, 이 보장은 재계획 창(replanning window, $\alpha$ )과는 독립적이므로, 효율성을 높이기 위해 더 짧은 재계획 창을 사용하는 것에 대한 이론적 정당성을 제공한다.
그룹 분산(Group Decentralization): LI-MDP 문헌은 가시성 거리 $V$ 내에서의 연결성을 기준으로 에이전트를 그룹으로 분할해도 근사 최적성을 희생하지 않고 수행할 수 있음을 시사한다. 서로 다른 그룹에 속한 에이전트들은 일정 단계( $\lfloor V/2 \rfloor$ ) 내에서 충돌할 수 없으므로 병렬로 계획을 세울 수 있다.

제안된 알고리즘: GD-RHCR (Group Decentralized RHCR)

시간 기반 제한(RHCR)과 공간 기반 분할(GD-RHCR) 사이의 이론적 이중성을 바탕으로, 저자들은 GD-RHCR을 제안한다. 알고리즘은 다음과 같이 작동한다:

그룹 분할: 각 타임스텝에서 에이전트들은 가시성 반경 $V$ (최단 경로 거리 사용) 내의 연결 성분을 기준으로 그룹으로 분할된다.
지연 평가(Deferred Evaluation): 모든 그룹을 매 단계마다 재계획하는 대신, 시스템은 "지연" 전략을 채택한다. 그룹 내 에이전트들이 현재 계획에 대해 의견이 불일치하거나 계획이 소진된 경우에만 그룹이 계획을 다시 계산한다. 이는 서로 다른 에이전트 집합에 대해 유효한 재계획 창을 동적으로 조정한다.
소프트 제약(Soft Constraints): 특정 그룹을 계획할 때, 알고те즘은 이전 타임스텝의 다른 그룹 에이전트들의 계획된 궤적을 기반으로 한 "소프트 제약"을 포함한다. 이를 통해 다른 그룹을 하드 장애물로 취급하여 계산 비용을 높이는 대신, 잠재적인 미래 충돌을 고려하면서 계획을 세울 수 있다.
이종 솔버 및 폴백(Heterogeneous Solvers & Fallback): 이 프레임워크는 서로 다른 에이전트 그룹에 서로 다른 솔버를 할당하는 것을 지원한다.
- 작은 그룹은 고품질의, 잠재적으로 더 느린 솔버(예: PBS)를 사용하여 해결한다.
- 혼잡도가 높은 대규모 그룹(임계값 $K_{threshold}$ 초과)은 즉시 빠르고 확장 가능한 솔버(예: PIBT)로 넘겨진다.
- 타임아웃에 의해 트리거되는 "실패" 모드로서의 폴백을 사용하는 RHCR과 달리, GD-RHCR은 대규모 그룹에 대해 더 빠른 솔버를 사용하는 것을 알고리즘의 필수적인 부분으로 취급하여 혼잡도가 증가함에 따라 시스템 속도를 높인다.

3. 주요 기여

RHCR의 근사 최적성에 대한 이론적 증명: 본 논문은 할인된 MDP 공식화된 L-MAPF에서 RHCR이 계획 호라이즌에 따라 최적해로 지수적으로 수렴함을 입증한다.
이론적 이중성: RHCR의 시간 기반 제한과 GD-RHCR의 공간 기반 분할 사이의 이론적 이중성을 입증하며, GD-RHCR이 유사한 근사 최적성 보장(상수 계수 범위 내)을 만족함을 증명한다.
GD-RHCR 프레임워크: 에이전트를 그룹으로 분할하고, 지연 평가를 활용하며, 소프트 제약을 통합하는 새롭고 이론적으로 원칙 있는 병렬 계획 프레임워크를 도입한다.
확장성 및 효율성: 서로 다른 에이전트 그룹에 서로 다른 솔버를 동적으로 할당함으로써 솔루션 품질과 계산 효율성의 균형을 맞춘다. 이는 기존 RHCR에 비해 단위 계획당 계산 비용을 크게 줄인다.

4. 실험 결과

저자들은 다양한 맵(창고, 분류, 무작위 내비게이션 환경)과 에이전트 수에 대해 GD-RHCR을 RHCR(PIBT 폴백 포함) 및 PIBT 단독 모델과 비교하여 평가했다.

RHCR 대비 성능: RHCR이 실행 가능한 에이전트 수 범위에서, GD-RHCR은 유사한 처리량(테스트된 시나리오에서 약 2% 이내)을 달면서도 평균 계획 시간을 24.9배 단축했다.
확장성: GD-RH월 GD-RHCR은 RHCR의 실행 가능한 범위를 훨씬 더 높은 에이전트 수까지 확장한다. 800명의 에이전트가 있는 밀집된 창고 시나리오에서, GD-RHCR은 붕괴된(collapsed) RHCR/PIBT 대비 57.7% 향상된 처리량을 달면서도 낮은 계획 비용을 유지했다.
위상적 영향: 이 방법은 최단 경로가 맨해튼 거리와 크게 달라져 자연스럽게 작고 독립적인 그룹을 형성하는, 장애물이 밀집되고 복잡한 위상을 가진 맵(예: 창고)에서 가장 잘 작동한다. 단순하거나 작은 맵에서는 그룹이 커짐에 따라 이점이 줄어들지만, 여전히 계산적으로 효율적이다.
강건성 및 한계: GD-RHCR의 성능은 맵의 위상에 민데한 영향을 받는다. 이분 연결(biconnected)되지 않은 맵(예: random-32-32-20 및 room-32-32-var1)에서는 PIBT가 데드락을 겪을 수 있다. GD-RHCR은 이러한 환경에서 PIBT에 의존하게 될 경우, RHCR이 붕괴되기 전에 PIBT를 사용하게 되어 성능이 저하될 수 있다. 그러나 그룹이 작고 분리되어 있는 밀집된 맵에서는 GD-RHCR이 높은 처리량을 유지하며 이러한 데드락 문제를 피한다.

5. 의의 및 주장

본 논문은 GD-RHCR이 RHCR의 계산적 한계에 대한 이론적으로 근거 있는 해결책을 제공한다고 주장한다. LI-MDP 프레임워크를 활용함으로써, 저자들은 단순한 휴리스틱 기반의 병렬화를 넘어 다음과 같은 방법을 제시한다:

RHCR의 높은 처리량 이점을 유지한다.
적절한 위상 구조에서 PIBT와 같은 탐욕적이고 부최적인 방법으로만 관리 가능했던 높은 에이전트 수까지 확장 가능하다.
그룹 크기와 혼잡도에 따라 서로 다른 계획 알고리즘을 동적으로 할당할 수 있는 모듈형 프레임워크를 제공한다.

저자들은 이 연구가 그룹 분산(group decentralization)을 다른 MAPF 방법론 및 학습 기반 접근 방식에 통합하는 새로운 연구 방향을 열어주며, 이론적 보장과 계산적 확장성 사이의 균형을 맞추는 새로운 패러다임을 구축한다고 강조한다.