🤖 AI

Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF

이 논문은 시차를 둔 서브셋 계획(staggered subset planning)과 윈도우 기반 경로 업데이트, 그리고 EPIBT에서 영감을 얻은 충돌 해결 방식을 결这种하여 일반적인 지도 상에서 수천 명의 에이전트를 대상으로 높은 처리량과 긴 호흡의 조율을 달성하는 확장 가능한 평생 다중 에이전트 경로 탐색(lifelong Multi-Agent Path Finding) 플래너인 PUSH를 소개한다.

원저자: Vaibhav Sanjay, Jiaoyang Li

게시일 2026-08-10

📖 5 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Vaibhav Sanjay, Jiaoyang Li

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

수백만 대의 작고 보이지 않는 자동차들이 서로 충돌하지 않고 A 지점에서 B 지점으로 이동하려고 질주하는 북적이는 도시를 상상해 보세요. 이것은 단순한 교통 체증이 아니라, 다중 에이전트 경로 탐색(Multi-Agent Path Finding, MAPF)이라 불리는 고도의 정밀한 춤입니다. 현실 세계에서 이는 로봇으로 가득 찬 창고, 분류 센터, 배송 함대를 움직이는 보이지 않는 두뇌입니다. 하지만 여기서 까다로운 점이 있습니다. 이 로봇들은 단순히 특정 지점에 도착해서 떠나는 것이 아닙니다. 그들은 종로히 물건을 싣거나 사람이 무언가를 할 때까지 기다려야 하는 경우가 많습니다. 이는 로봇들이 기존 작업을 마치는 즉시 새로운 작업을 계속 부여받는 "평생(lifelong)" 문제를 발생시킵니다.

과학자들의 큰 과제는 이 수천 대의 로봇을 동시에 어떻게 조율하느냐 하는 것입니다. 만약 모든 로봇의 전체 여정을 시작부터 끝까지 계획하려고 시도한다면, 컴퓨터는 과부하가 걸려 멈춰버릴 것입니다. 반대로, 앞을 내다보지 않고 단순히 "앞으로 가라"고만 지시하면, 다가올 문제를 인지하지 못해 교통 체증이나 막다른 길에 갇히게 됩니다. 이는 미래를 멀리 내다보며 문제를 피하는 것과, 계속 움직일 수 있도록 빠르게 반응하는 것 사이의 균형을 잡는 일입니다.

여기 이 이야기에 등장하는 새로운 영웅이 있습니다. 바로 PUSH라고 불리는 알고리즘입니다. PUSH는 10,000대의 로봇 군단을 정신을 잃지 않고 관리하는 방법을 마침내 알아낸 초스마트 교통 관제사라고 생각하면 됩니다.

기존 방식의 문제점

PUSH가 왜 특별한지 이해하기 위해, 기존에 로봇들을 관리하던 두 가지 주요 방식과 그 결함들을 살펴보겠습니다.

"모든 것을 보는" 접근 방식 (RHCR):
도시의 모든 자동차를 위해 향후 한 시간 동안의 경로를 한꺼번에 계획하는 교통 경찰을 상상해 보세요. 이것이 "롤링 호라이즌 충돌 해결(Rolling Horizon Collision Resolution, RHCR)"입니다. 이는 큰 그림을 보고 장기적인 교통 체증을 피하는 데는 탁월합니다. 하지만 매우 느립니다. 만약 10,000대의 로봇이 있다면, 컴퓨터는 경로를 계산하는 데 너무 많은 시간을 소비하여 로봇들에게 언제 움직여야 할지조차 알려주지 못하게 됩니다. 이는 마치 시계가 돌아가는 와중에 백만 개의 조각이 있는 퍼즐을 풀려고 하는 것과 같습니다. 결국 완성하기도 전에 시간이 다 되어버립니다.

"딱 한 걸음만 보는" 접근 방식 (PIBT/EPIBT):
이제 딱 한 걸음 앞만 내다보는 다른 교통 경찰을 상상해 보세요. "좋아, 앞으로 가. 벽에 부딪히면 멈춰." 이것이 "반응형(Reactive)" 접근 방식(PIBT 및 EPIBT와 같은 방식)입니다. 이는 번개처럼 빠르며 수천 대의 로봇도 쉽게 처리할 수 있습니다. 하지만 "시간적 근시안(temporal myopia)"이라는 문제가 있습니다. 이는 아주 짧은 앞날만 본다는 뜻의 멋진 표현입니다. 만약 로봇이 물건을 싣기 위해 20초 동안 기다려야 한다는 것을 알고 있더라도, 이 근시안적인 플래너는 그 기다림이 뒤쪽 복도 전체를 막을 것이라는 사실을 깨닫지 못합니다. 그저 "움직임"과 "정지"만을 보기 때문에, 불필요하고 거대한 교통 체증을 유발합니다.

새로운 솔루션: PUSH

이 논문의 저자인 바이바브 산제이(Vaibhav Sanjay)와 지양 리(Jiaoyang Li)는 PUSH(Staggered Horizons를 통한 경로 업데이트, Path Updates over Staggered Horizons)를 만들어 두 방식의 장점을 모두 취하고자 했습니다. 그들은 느린 플래너들처럼 멀리 내다보면서도, 반응형 플래너들처럼 빠르게 움직일 수 있는 시스템을 원했습니다.

PUSH가 어떻게 작동하는지 간단한 비유를 통해 설명하겠습니다.

1. 교차된 이동 (부분 집합 계획 - Subset Planning)
10,000명의 사람들이 탈출해야 하는 거대한 경기장을 상상해 보세요. 모든 사람에게 정확히 같은 순간에 어디로 갈지 지시하는 대신(이는 혼란을 야기합니다), PUSH는 소수의 그룹에게 먼저 움직이라고 지시합니다. 그러고 나서 몇 초 후, 다음 그룹에게 지시합니다. 즉, 업데이트를 "교차(staggered)"시키는 것입니다.
논문에서 이는 컴퓨터가 매 순간 로봇의 작은 부분 집합만을 계획한다는 것을 의미합니다. 이는 반응형 플래너들처럼 계산을 쉽고 빠르게 유지해 줍니다.

2. 긴 안목 (윈도우 계획 - Windowed Planning)
하지만 반전이 있습니다. 비록 한 번에 몇 대의 로봇만을 계획하지만, 그들에 대해서는 멀리 내다보며 계획합니다. 단순히 "한 걸음 움직여"라고 말하는 대신, "다음 10단계 동안의 경로는 이렇다"라고 말합니다. 이것이 "윈도우(windowed)" 방식입니다. 이를 통해 로봇은 코너 너머를 볼 수 있고, 앞의 로봇이 물건을 싣기 위해 멈춰 서 있을 것이라는 것을 미리 알아차려, 그곳에 도착하기 전에 속도를 줄일 수 있습니다.

3. 재귀적 밀기 (우선순위 상속 - Recursive Push)
만약 두 로봇이 여전히 같은 지점으로 가고 싶어 한다면 어떻게 될까요? 기존의 반응형 시스템에서는 서로 부딪히거나 어색하게 기다릴 수 있습니다. PUSH는 "재귀적 우선순위 상속(recursive priority inheritance)"이라는 영리한 기술을 사용합니다.
사람들이 문을 통과하려고 줄을 서 있는 상황을 상해 보세요. 만약 높은 우선순위를 가진 사람(오랫동안 기다려온 사람)이 움직여야 한다면, 그 사람은 낮은 우선순위의 사람을 옆으로 "밀어낼(push)" 수 있습니다. 하지만 여기서 마법 같은 일이 일어납니다. 그 낮은 우선순위의 사람은 그냥 멈춰 서는 것이 아니라, 즉시 새로운 자리를 찾아내고, 어쩌면 또 다른 사람을 밀어낼 수도 있습니다. 이것은 군중 사이로 퍼져나가는 예의 바른 '밀치기'의 연쇄 반응이며, 모든 사람이 자리를 찾을 때까지 이어집니다. 이를 통해 시스템은 복잡한 교통 체증을 즉각적으로 해결할 수 있습니다.

연구 결과

연구진은 두 가지 매우 다른 환경에서 PUSH를 테스트했습니다:

"하역장(Loading Dock)" 환경: 로봇이 작업을 수행하기 위해 20초 동안 멈춰서 기다려야 하는 지도입니다. 이곳은 짧은 시야를 가진 플래너들이 보통 실패하는 곳인데, 왜냐하면 차단될 상황을 예측하지 못하기 때문입니다.
"좁은 복도(Narrow Hallway)" 환경: 로봇이 자신을 가두지 않도록 매우 주의해야 하는 길고 좁은 통로와 막다른 길이 있는 지도입니다.

결과:

속도: PUSH는 최대 **10,000대의 에이전트(로봇)**를 1초 미만 안에 처리했습니다. 이는 가장 빠른 반응형 플래너들과 동일한 규모입니다.
처리량(Throughput): "하역장" 테스트에서 PUSH는 다른 어떤 방식보다 더 많은 로봇을 목표 지점까지 이동시켰습니다. 한 테스트(random-32-32-20 맵)에서는 이전의 최고 방식인 EPIBT-LNS보다 처리량을 300% 개선했습니다. 또 다른 테스트(warehouse-large)에서는 **25%**를 개선했습니다.
강건성(Robustness): 연구진이 로봇의 대기 시간을 늘렸을 때(작업 시간 증가), 기존의 근시안적인 플래너들은 무너졌지만, PUSH는 계속해서 원활하게 작동했습니다.
"라이트(Lite)" 버전: 저자들은 "재귀적 밀기" 기술을 사용하지 않은 "PUSH-lite" 버전도 테스트했습니다. 이 버전은 적은 수의 로봇 그룹에서는 잘 작동했지만, 로봇 수가 너무 많아지자 무너졌습니다. 이는 "밀기(pushing)" 메커니즘이 군중을 처리하는 데 필수적임을 입증했습니다.

이것이 중요한 이유

이 논문은 빠르면서도 똑똑할 필요는 없다는 것을 보여줍니다. 일부 로봇만을 계획하는 아이디어(부분 집합 계획)와 멀리 내다보는 능력(윈도우 계획), 그리고 충돌을 해결하는 스마트한 방법(재귀적 밀기)을 결합함으로써, PUSH는 수년간 병목 현상이 되었던 문제를 해결했습니다.

이는 단순히 이론적인 승리가 아닙니다. 저자들은 실제 대회와 산업계에서 사용되는 실제 지도 레이아웃에서 이 시뮬레이션을 실행했습니다. 그들은 다른 방식들이 수백 대의 로봇에게는 작동할지 몰라도, 실제 바쁜 창고에서 필요한 수천 대 규모로 확장될 때는 처참하게 실패한다는 것을 발견했습니다. PUSH는 로봇이 멈춰서 작업해야 할 때 발생하는 교통 체증을 피하면서도, 그토록 많은 수의 로봇을 성공적으로 조율하는 첫 번째 방법입니다.

요약하자면, PUSH는 교통 관제사에게 수정 구슬과 확성기를 쥐여준 것과 같습니다. 이를 통해 도로가 좁고 운전자들이 커피를 마시러 멈춰 서야 하는 상황에서도 10,000대의 로봇 도시를 매끄럽게 안내할 수 있게 해줍니다.

기술 요약: Lifelong MAPF를 위한 순차적 업데이트 기반의 확장 가능한 장기 지평 계획 (Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF)

문제 정의

본 논문은 에이전트가 현재 목표에 도달할 때마다 새로운 목표를 지속적으로 부여받는 표준 MAPF(Multi-Agent Path Finding)의 변형인 Lifelong MAPF (LMAPF) 문제를 다룹니다. 핵심 과제는 엄격한 실시간 제약 조건 하에서 대규모 함대(수천 명의 에이전트)를 위해 충돌 없는 경로를 생성하면서도, **시간적 근시안(temporal myopia)**을 피하는 것입니다.

기존 방식들은 확장성과 장기 지평 추론 사이에서 트레이드오프를 겪습니다:

반응형 플래너 (예: PIBT, EPIBT): 규칙 기반의 단계별 조율을 사용하여 수천 명의 에이전트까지 손쉽게 확장 가능하지만, 심각한 시간적 근시안 문제를 겪으며, 미래의 혼잡(예: 좁은 복도 또는 작업 실행 지연)을 예측해야 하는 시나리오에서 실패합니다.
윈도우 기반 플래너 (예: RHCR): 다단계 지평에 대해 계획을 세워 선견지명을 높이지만, 전체 함대를 동시에 재계획할 때 상당한 계산 오버헤드가 발생하여 확장성을 저해합니다.
서브셋 플래너 (예: Token Passing - TP): 에이전트의 일부만을 재계획함으로써 확장성을 확보하지만, 고도로 구조화된 "잘 형성된(well-formed)" 지도에 국한되며 일반적인 토폴로지를 처리할 수 없습니다.

본 논문은 기존 알고리즘에 공백이 있음을 식별합니다: 즉, 일반적인 지도 상에서 혼잡한 환경과 **작업 완료 시간(Task Completion Time, TCT)**을 처리하면서 장기 지평 계획을 달ai할 수 있는 기존 알고리즘이 존재하지 않습니다.

방법론: 순차적 지평 기반 경로 업데이트 (Path Updates over Staggered Horizons - PUSH)

저자들은 TP, RHCR, EPIBT의 강점을 결합한 플래너인 PUSH를 제안합니다. PUSH는 순차적인 윈도우를 통해 장기 지평 추론을 유지하면서 각 타임스텝마다 에이전트의 일부만을 계획함으로써 확장성을 달성합니다.

핵심 메커니즘

순차적 서브셋 계획 (Staggered Subset Planning):
- 전체 함대를 동시에 재계획하는 RHCR와 달리, PUSH는 각 타임스텝마다 에이전트의 일부( $Q$ )만을 재계획합니다.
- 에이전트에게는 time2Replan 카운터가 할당됩니다. 에이전트의 카운터가 0에 도달하거나 현재 경로가 대기를 강제하는 경우, 해당 에이전트는 재계획 큐에 진입합니다.
- 이러한 순차적 접근 방식은 전체 함대 단위의 동시 재계획과 관련된 계산 폭발을 방지합니다.
폴백(Fallback) 기능이 포함된 윈도우 경로 계획:
- PUSH는 모든 에이전트를 위한 안전하고 충돌 없는 폴백 경로 집합( $\Pi$ )을 전역적으로 유지합니다.
- TP처럼 목표까지의 전체 경로를 계획하는 대신, 에이전트는 $W$ -스텝 윈도우 경로를 계획합니다.
- 새로운 계획을 찾을 수 없는 경우, 에이전트는 기존의 폴백 경로를 기본값으로 사용하며, 이를 통해 항상 충돌 없는 실행을 보장합니다.
재귀적 우선순위 상속 및 푸싱 (Recursive Priority Inheritance and Pushing):
- 혼잡을 처리하고 경로 품질을 개선하기 위해, PUSH는 EPIBT에서 영감을 받은 우선순위 상속을 통합합니다.
- 에이전트들에게 전역 우선순위가 할당됩니다. 높은 우선순위의 에이전트가 계획한 경로가 낮은 우선순위 에이전트와 충돌하는 경우, 낮은 우선순위의 에이전트는 "푸시(pushed)"됩니다.
- 밀려난 에이전트는 일시적으로 높은 우선순위를 상속받아 경로를 재귀적으로 재계획합니다. 이 과정은 충돌 없는 솔루션이 발견되거나 재귀 제한( $M$ )에 도달할 때까지 계속됩니다.
- 1단계 또는 단기 지평의 푸싱에 국한된 EPIBT와 달리, PUSH는 수정된 윈도우 공간-시간 A*를 사용하여 최대 하나의 낮은 우선순위 에이전트와만 충돌하는 최적의 $W$ -스텝 경로를 찾습니다.
Anytime 최적화 (LNS):
- 기본 계획 주기가 끝난 후, PUSH는 남은 시간을 활용하여 **대규모 이웃 탐색(Large Neighborhood Search - LNS)**을 실행합니다.
- 무작위로 에이전트를 선택하고, 그들의 경로를 제거한 뒤, 전역 목적 함수(목표까지의 거리 최소화)를 개선하기 위해 더 높은 우선순위로 재계한을 시도합니다.
- 솔루션은 목표까지의 총 거리가 개선되는 경우에만 수락됩니다.

이론적 보장

완전성 (Completeness): PUSH는 유한한 시간 내에 모든 에이전트에 대해 충돌 없는 경로를 반환함을 보장합니다.
데드락 프리 (Deadlock-Freedom): 특정 조건(이연결 그래프, TCT 0, 그리고 "더 긴 경과 시간" 우선순위 지정) 하에서, PUSH는 모든 에이전트가 유한한 타임스텝 내에 목표에 도달함을 보장하며, 이는 EPIBT의 보장과 일치합니다.

주요 기여

최초의 일반 지도 서브셋 플래너: PUSH는 서브셋 계획(확장성을 위함)과 장기 지평 윈도우 계획을 결합한 최초의 알고리즘이며, Token Passing의 토폴로지적 제한 없이 일반적인 지도 구조에 적용 가능합니다.
확장 가능한 장기 지평 추론: PUSH는 수천 명의 에이전트 규모에서도 $W=10$ 의 다단계 계획 지평을 사용하여 성공적으로 협업합니다. 이는 이전에는 일반적인 지도에서 달성하기 어려웠던 능력입니다.
혼잡 및 지연에 대한 견고성: 재귀적 우선순위 푸싱과 순차적 업데이트를 통합함으로써, PUSH는 반응형 플래너가 실패하는 좁은 복도, 깊은 막다른 길, 그리고 확률적인 작업 완료 시간(TCT) 상황을 효과적으로 처리합니다.

실험 결과

저자들은 두 가지 유형의 시나리오에서 PUSH를 베이스라인(RHCR-PBS, EPIBT-LNS, PIBT, 그리고 ablation 모델인 PUSH-lite)과 비교 평가했습니다.

TCT 맵 (작업 지연):
- 설정: 에이전트들이 목표에서 $T=20$ 타임스텝 동안 대기합니다.
- 결과: PUSH 및 PUSH-LNS가 모든 맵 크기(최대 10,000명)에서 가장 높은 처리량(throughput)을 달성했습니다.
- 비교: EPIBT-LNS는 개방된 맵에서는 매끄러운 확장을 유지했으나, 좁은 복도와 밀집된 장애물에서는 성능이 크게 저하되었습니다. RHCR은 혼잡도가 증가함에 따라 계획 예산을 모두 소진했습니다. PUSH-LNS는 warehouse-large에서 EPIBT-LNS보다 25%, random-32-32-20에서 300% 향상된 처리량을 보여주었습니다.
복잡한 맵 (구조적 제약):
- 설정: 긴 복도와 막다른 길이 있는 (Symbotic, Delivery) 맵 ( $T=0$ ).
- 결과: PUSH-LNS가 가장 높은 처리량(예: Symbotic에서 3.8)을 달성했습니다.
- 실패 모드: EPIBT-LNS는 깊은 복도의 높은 밀도에서 고전했으며, RHCR은 빈번하게 타임아웃이 발생했습니다. 재귀적 푸싱이 없는 PUSH-lite ablation 모델은 대규모 함대에서 파괴적인 성능 붕괴를 겪었으며, 이는 재귀적 우선순위 치환의 필요성을 입증합니다.
Ablation 연구:
- TCT 민감도: PUSH-LNS는 비제로(non-zero) TCT 상황에서도 높은 처리량을 유지한 반면, 근시안적인 플래너(EPIBT-LNS)는 성능이 크게 저하되었습니다.
- 윈도우 크기 ( $W$ ): $W$ 를 늘리면 PUSH-LNS의 성능이 향상되어 계산적 붕괴 없이 장기 지평 계획을 활용할 수 있었습니다. 반면, EPIBT-LNS는 가능한 연산의 지수적 폭발로 인해 $W=7$ 에서 성능이 붕마했고, RHCR은 더 큰 윈도우에서 근시안적 계획으로 회귀했습니다.

의의 및 주장

본 논문은 PUSH가 극단적인 확장성을 가진 반응형 플래너와 통찰력을 가진 장기 지평 플래너 사이의 결정적인 간극을 메운다고 주장합니다. PUSH는 다음과 같은 능력을 갖춘 최초의 LMAPF 알고리즘으로 제시됩니다:

10,000명의 에이전트를 장기 지평 계획으로 조율.
제한적인 토폴로지 가정 없이 일반적인 지도 구조에서 작동.
반응형 플래너를 실패하게 만드는 혼잡한 시나리오와 작업 실행 지연을 효과적으로 관리.

저자들은 PUSH를 로봇 분류 센터와 같이 대규모 함대의 동시 조율과 장기적 예측이 동시에 요구되는 실제 산업적 과제를 해결하기 위한 기초적인 단계로 포지셔닝합니다. 이는 이전에는 일반적인 지도에서 다루기 불가능하다고 여겨졌던 조합입니다. 향후 연구 방향으로는 키네다이내믹(kinodynamic) 제약 조건 및 동적 윈도우 크기 조절로의 확장이 제안되었습니다.