💻 computer science

Adaptive-Horizon Conflict-Based Search for Closed-Loop Multi-Agent Path Finding

이 논문은 계획 지평을 동적으로 조정하고 제약 트리를 재사용함으로써, 온라인 장애에 대한 낮은 지연 시간과 강건성을 갖춘 다중 에이전트 경로 탐색을 위해 고품질의 점근적 최적해를 제공하는 새로운 알고리즘인 Anytime Closed-Loop Conflict-Based Search (ACCBS)를 소개한다.

원저자: Jiarui Li, Federico Pecora, Runyu Zhang, Gioele Zardini

게시일 2026-06-25

📖 4 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Jiarui Li, Federico Pecora, Runyu Zhang, Gioele Zardini

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

수백 대의 작은 로봇들이 서로 부딪히지 않고 상자를 A 지점에서 B 지점으로 옮기려고 애쓰는 거대하고 자동화된 창고를 상상해 보세요. 이것이 바로 다중 에이전트 경로 탐색(Multi-Agent Path Finding, MAPF) 문제입니다. 이는 마치 모두가 각기 다른 목적지를 가진 채 춤을 추는 안무를 조율하는 것과 같습니다. 만약 두 명의 무용수가 동시에 같은 자리를 차지하려고 한다면, 공연 전체가 멈춰버릴 것입니다.

오랫동안 로봇 플래너들은 다음과 같은 좌절스러운 "골디락스(Goldilocks)" 문제에 직면해 왔습니다:

"완벽한 계획" 방식: 이 알고리즘들은 로봇이 단 한 걸음도 움직이기 전에 모든 로봇의 전체 여정을 설계하려고 합니다. 이는 마치 지휘자가 첫 음을 연주하기 전에 3시간짜리 교향곡을 미리 다 써 내려가는 것과 같습니다. 문제는, 창고가 너무 크거나 붐비면 교향곡을 쓰는 데 시간이 너무 오래 걸려 로봇들이 그저 멍하니 기다리게 만든다는 점입니다.
"빠른 해결" 방식: 이 알고리즘들은 그저 바로 다음 단계만을 보고 결정을 내립니다. 이는 마치 바로 앞 차량의 범퍼만 보고 운전하는 운전자와 같습니다. 속도는 빠르지만, 코너 너머를 볼 수 없기 때문에 교통 체증에 갇히거나 장기적으로 좋지 않은 결정을 내리기 쉽습니다.

이 논문은 이 두 세계의 장점을 모두 취한 ACCBS(Anytime Closed-Loop Conflict-Based Search)라는 새로운 방법을 소개합니다. 이 방법이 어떻게 작동하는지 쉬운 비유를 통해 설명하겠습니다.

핵심 아이디어: "성장하는 망원경"

안개가 자욱한 도로를 운전하고 있다고 상상해 보세요.

기존 방식: 안개가 완전히 걷혀서 목적지까지의 전체 경로가 다 보일 때까지 기다렸다가 엔진을 켭니다. (너무 느립니다).
단순한 방식: 타이어 바로 앞의 도로만 살핍니다. (너무 위험합니다).
ACCBS 방식: 즉시 출발할 수 있도록 우선 몇 피트 앞만 먼저 봅니다. 하지만 여유 시간이 생기는 즉시, 망원경을 "줌 아웃"하여 조금 더 멀리 내다봅니다. 시간이 더 주어진다면, 다시 한번 줌 아웃을 합니다.

ACCBS도 정확히 이와 같이 작동합니다. 먼저 모든 로봇의 다음 단계만을 계획하여 즉시 움직일 수 있게 합니다. 그런 다음, 남은 컴퓨터 시간을 사용하여 "시야"(계획 지평선)를 2단계, 3단계, 4단계 등으로 확장하며 더 멀리 내다봅니다.

마법의 기술: "지도" 재사용하기

계속해서 줌 아웃을 하면, 매번 지도를 새로 그려야 해서 너무 느려지지 않을까 생각할 수 있습니다.

이 논문의 영리한 혁신은 바로 **제약 트리 재사용(Constraint Tree Reuse)**입니다.
계획 과정을 "만약 ~라면"이라는 시나리오를 구축하는 트리(Tree)라고 생각해 보세요.

ACCBS가 1단계 앞을 내다볼 때, 작은 트리를 하나 만듭니다.
그다음 2단계 앞을 내다보기로 결정했을 때, 기존의 트리를 버리지 않습니다. 대신 기존 트리의 윗부분에 새로운 가지를 추가합니다.
수학적으로 특정 방식("비용 불변성", Cost Invariance)으로 작동하기 때문에, 새로운 가지를 추가하더라도 기존 가지의 가치는 변하지 않습니다.

이는 블록으로 탑을 쌓는 것과 같습니다. 탑을 더 높게 만들기 위해 기존의 탑을 허물지 않고, 그 위에 계속해서 새 블록을 쌓아 올리는 것입니다. 덕분에 컴퓨터는 이미 계산해낸 것을 다시 계산하느라 시간을 낭비하지 않습니다.

"Anytime"이 중요한 이유

"Anytime(언제든 가능한)"이라는 용어는 매우 중요합니다. 이는 이 알고리즘이 중단 가능하다는 것을 의미합니다.

만약 컴퓨터가 0.5초 안에 결정을 내려야 한다면, 그 0.5초 동안 찾을 수 있는 최선의 계획(보통은 바로 다음의 안전한 단계)을 제공합니다.
만약 5초의 시간이 주어진다면, 훨씬 더 멀리 내다보는 더 나은 계획을 제공합니다.
만약 로봇이 예상치 못한 상황(예: 상자가 떨어지거나 로봇이 예상보다 느리게 움직이는 경우)에 직면하더라도, ACCBS는 당황하지 않습니다. 단순히 현재의 계획을 멈추고, 새로운 현실을 살핀 뒤, 현재 위치에서부터 다시 "줌 아웃" 과정을 시작하면 됩니다.

결과

저자들은 빈 방부터 수백 대의 로봇이 있는 붐비는 창고까지 다양한 지도에서 이를 테스트했습니다.

속도: 한 번에 전체 여정을 계획하는 것보다 훨씬 빠릅니다.
품질: 시간을 더 많이 줄수록, 찾아내는 경로는 완벽한 해답에 더 가까워지며 더 좋아집니다.
신뢰성: 상황이 복잡해지면 멈추거나 시간이 초과될 수 있는 다른 방법들과 달리, ACCBS는 항상 단순하고 안전한 첫 단계를 가지고 있기 때문에 언제나 무언가 답을 내놓을 수 있습니다.

요 요약

ACCBS는 완벽하고 장기적인 스케줄이 나올 때까지 기다리는 똑똑한 교통 관제사와 같습니다. 대신, 짧은 단기 계획을 통해 즉시 차량들을 움직이게 하고, 더 많은 정보와 시간이 생김에 따라 계획을 지속적으로 정교하게 다듬어 나갑니다. 이 과정에서 처음부터 다시 시작하는 일은 없습니다. 이는 속도의 필요성과 좋은 해결책을 찾는 필요성 사이에서 균형을 맞추며, 바쁜 실제 로봇 군단에 이상적인 방식입니다.

기술 요약: 폐쇄 루프 다중 에이전트 경로 탐색을 위한 적응형 호라이즌 기반 충돌 기반 탐색 (Adaptive-Horizon Conflict-Based Search)

문제 정의

다중 에이전트 경로 탐색(MAPF)은 자동화된 창고 및 물류 시스템의 대규모 로봇 군집을 위한 근본적인 조정 문제로, 에이전트가 그래프 상에서 충돌 없이 시작 정점에서 목표 정점으로 이동하는 것을 요구합니다.

오픈 루프 플래너(예: 표준 Conflict-Based Search, CBS)는 실행 전 전체 궤적을 계산합니다. 이는 최적성 보장을 제공하지만, 높은 계획 지연 시간(planning latency)과 밀도가 높고 긴 호라이즌을 가진 인스턴스에서의 낮은 확장성 문제를 겪으며, 이는 동작 실행을 지연시킵니다.
폐쇄 루프 휴리스틱(Closed-loop heuristics)은 현재 상태로부터 재계획(replanning)함으로써 지연 시간을 줄이지만, 신뢰할 수 있는 성능 보장이 부족한 경우가 많아 안전이 중요한 배포 환경에서의 활용에 한계가 있습니다.
유한 호라이즌 접근 방식(예: Windowed CBS/RHCR)은 이 간극을 메우려 시도하지만 "호라이즌 선택 딜레마"에 직면합니다. 즉, 고정된 계획 호라이즌을 사전에 결정해야 합니다. 작은 호라이즌은 효율적이지만 근시안적이며, 큰 호라이즌은 솔루션 품질을 개선하지만 지수적인 탐색 증가를 초래합니다. 또한, 고정 윈도우 방식은 표준 CBS의 완결성(completeness) 및 점근적 최적성(asymptotic optimality) 보장을 상실하는 경우가 많습니다.

방법론: 애니타임 폐쇄 루프 충돌 기반 탐색 (ACCBS)

본 논문은 모델 예측 제어(MPC)에서 영감을 얻은 동적 호라이즌 메커니즘을 결과적으로 결합한 폐쇄 루프 MAPF 알고리즘인 ACCBS를 제안합니다.

핵심 메커니즘

유한 호라이즌 폐쇄 루프 CBS:
- 전체 궤적을 해결하는 대신, 알고리즘은 유한한 전방 주시 호라이즌 $H$ 에 대해 계획을 세웁니다.
- 이는 실행 비용(목표에 도달하기 위해 소요된 단계)과 터미널 비용(남은 거리를 추정하는 허용 가능한 휴리스틱)으로 구성된 비용 함수를 최적화합니다.
- 각 타임스텝 $t$ 에서 알고리즘은 전방 주시 윈도우 내의 충돌만을 해결하고, 첫 번째 움직임을 실행한 후, 새로운 상태로부터 재계획합니다.
반복 심화(Iterative Deepening)를 통한 적응형 호라이즌:
- ACCBS는 호라이즌 $H$ 를 미리 고정하지 않습니다. 대신, 계산 시간 예산이 허용하는 한 1에서 시작하여 $H_{max}$ 까지 점진적으로 증가하는 실행 중 호라이즌 $h_r$ 을 유지합니다.
- 이를 통해 알고리즘은 즉각적으로 실행 가능한 저지연 솔루션을 반환할 수 있고( $h_r=1$ ), 시간이 남을 경우 더 긴 전방 주시를 통해 이를 정교화함으로써 애니타임(anytime) 동작을 보여줍니다.
활성 접두사(Active Prefix) 및 제약 트리 재사용:
- 호라이즌이 증가할 때마다 발생하는 과도한 비용을 피하기 위해, ACCBS는 활성 접두사 개념을 도입합니다. 충돌은 현재 활성 접두사의 길이 $h_r$ 내에서만 해결되며, 이 접두사를 넘어선 충돌은 일시적으로 무시됩니다.
- 비용 불변성 (Lemma III.1): 본 논문은 특정 저수준 플래너 가정(접미사가 최단 경로를 따름) 하에서, 호라이즌이 확장될 때 노드의 비용이 불변함을 증명합니다.
- 제약 트리 재사용 (Proposition III.1): 비용과 부모-자식 관계가 보존되기 때문에, 작은 호라이즌 $h$ 에 대해 구축된 제약 트리는 $h+1$ 에 대해서도 유효한 서브트리가 됩니다. 이를 통해 ACCBS는 탐색을 재시작하지 않고도 호라이즌을 매끄럽게 확장할 수 있으며, 누적 계산 노력을 최대 호라이즌에서의 단일 실행과 유사한 수준으로 만듭니다.

이론적 보장

완결성 및 최적성: Theorem III.1은 시간 예산이 무한하고 $H_{max}$ 가 최적 솔루션의 메이크스팬(makespan)보다 크다면, ACCBS가 완결성을 가지며 전역 최적 솔루션(Sum of Costs, SOC)을 반환함을 입증합니다.
애니타임 속성: 실행 시간이 증가함에 따라, 발견된 최적 솔루션의 비용은 단조 증가하며(최적 비용에 의해 제한됨) 최적값으로 수렴합니다.
단일 단계 실행 가능성: 알고리즘은 구조적으로 매 타임스텝마다 충돌 없는 활성 접두사(여기서 $h_r \ge 1$ )를 가진 노드의 첫 번째 단계를 실행함으로써 충돌 없는 단일 단계 명령을 보장합니다.

실험 결과

저자들은 원샷(one-shot), 라이프롱(lifelong), 확률적 실행 설정에서 PIBT, EECBS, MAPF-LNS2, LaCAM2/3, RHCR를 포함한 베이스라인들과 ACCBS를 비교 평가했습니다.

원샷 MAPF: ACCBS는 계산 효율성과 솔루션 품질 사이에서 유리한 균형을 달取得합니다. 스텝당 시간 예산이 증가함에 따라, ACCBS는 SOC를 낮추며 최적성에 도달하며, PIBT와 같은 빠른 휴리스틱보다 우수한 성능을 보이고 밀집된 맵에서 full-trajectory 솔버인 EECBS의 타임아웃 실패를 방지합니다.
라이프롱 MAPF: 목표가 변하는 시나리오에서 ACCBS는 경쟁력 있는 처리량을 보여줍니다. 적응형 호라이즌 덕분에 ACCBS는 고정 윈도우 방식(RHCR)이 타임아웃되는 더 큰 규모의 플릿(fleet)으로 확장할 수 있습니다.
확률적 불확실성: 실행 지연 및 에이전트 도착이 있는 시뮬레이션에서 ACCBS는 오픈 루프 베이스라인보다 뛰어난 성능을 보입니다. 오픈 루프 방식은 장애 발생 시 전체 궤적을 재계획해야 하는 병목 현상을 겪는 반면, ACCBS는 현재 상태로부터 재계획함으로써 자연스럽게 장애를 흡수합니다.
절제 연구(Ablation Study): 본 논문은 ACCBS에 우선순위 충돌(prioritized-conflict, PC) 선택을 추가하는 것이 고정된 예산 하에서는 솔루션 품질을 때때로 저하시킬 수 있다고 언급합니다. 이는 충돌 분류의 오버헤드가 트리 확장의 이점보다 크기 때문입니다.

의의 및 주장

본 논문은 ACCBS가 다중 에이전트 시스템에서 계획 지연 시간과 솔루션 품질 사이의 임계적인 트레이드오프를 해결한다고 주장합니다. 주요 기여는 다음과 같습니다:

취약한 설계 선택의 제거: 호라이즌을 온라인으로 적응시킴으로써, ACCBS는 특정 인스턴스 특성과 시간 예산에 의존하는 고정 호라이즌을 수동으로 튜닝할 필요를 없앱니다.
효율적인 호라이즌 확장: 비용 불변성과 제약 트리 재사용을 통해, 알고리즘은 탐색을 재시작하는 데 따르는 계산적 페널티 없이 반복 심화의 이점을 달성합니다.
보장의 복구: 고정 윈도우 폐쇄 루프 방식과 달리, ACCBS는 표준 CBS의 점근적 최적성 및 완결성 보장을 회복합니다.
강건성: 폐쇄 루프 정식화는 전체 궤적 재계획 없이도 온라인 장애(지연, 새로운 에이전트)를 자연스럽게 수용합니다.

저자들은 ACCBS를 실행의 유연성과 성능 보장이 모두 요구되는 안전 중심의 대규모 배포를 위한 실질적인 솔루션으로 포지셔닝합니다.