🤖 AI

HiRAD: A Flexible Large-Scale AGV Routing System

본 논문은 연속 공간 표현, 분리된 제어 전략, 그리고 비동기 이벤트 기반 파이프라인을 채택함으로써 기존의 고전적 및 RL 기반 AGV 라우팅 시스템의 확장성 및 실시간성 한계를 극복하고 메이크스팬(makespan)과 추론 지연 시간을 유의미하게 단축하는 계층적 강화 학습 프레임워크인 HiRAD를 소개한다.

원저자: Yunjie Huang, Ruizhong Wu, Mengxuan Zhang, Frodo Kin Sun Chan, Yan Nei Law, Lei Li

게시일 2026-09-10

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Yunjie Huang, Ruizhong Wu, Mengxuan Zhang, Frodo Kin Sun Chan, Yan Nei Law, Lei Li

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

현대 이커머스를 뒷받침하는 거대하고 웅웅거리는 창고 안에서, 수천 대의 소형 자율 주행 차량들이 바닥을 가로지르며 보관 선반에서 포장 구역으로 패키지를 실어 나릅니다. 자동 가이드 차량(AGV)이라 불리는 이 기계들은 글로벌 물류의 조용한 일꾼으로서, 매일 수십억 개의 품목을 이동시킬 수 있는 능력을 갖추고 있습니다. 그러나 이들을 충돌 없이 함께 움직이게 만드는 것은 오랫동안 엔지니어들을 괴롭혀온 난제였습니다. 전통적인 방식은 창고 바닥을 차량이 격자 칸에서 칸으로 딱딱하고 즉각적으로 뛰어넘는 거대한 체스판처럼 취급합니다. 이러한 방식은 수학적 계산을 단순화해주기는 하지만, 물리적 실체를 간과합니다. 실제 차량은 즉각적으로 멈출 수 없으며, 제자리에서 바로 회전할 수도 없습니다. 차량에는 가속, 감속, 그리고 조향을 위한 공간이 필요합니다. 소프트웨어가 이러한 물리적 한계를 무시하면, 실제 환경에서 차량들이 서로 충돌하거나, 컴퓨터가 안전한 경로를 계산하는 데 너무 많은 시간을 허비하여 차량들이 지시를 기다리며 가동을 멈추게 됩니다. 이처럼 이상적인 디지털 지도와 실제 기계의 무질서하고 연속적인 움직임 사이의 간극은, 대규모 로봇 군단을 효율적으로 배치하는 것을 어렵게 만들었습니다.

연구진은 이제 'HiRAD'라고 불리는 새로운 시스템을 통해 이 간극을 메웠으며, 이 시스템은 복잡한 창고 내에서 대규모 차량 그룹을 실시간으로 안내하도록 설계되었습니다. 연구진은 로봇들에게 격자 칸 사이를 점프하는 것처럼 행동하라고 강요하는 대신, 움직임의 연속적인 흐름을 존중하는 모델을 구축했습니다. 그들은 수백 대의 차량이 동시에 움직이는 상황에서 충분히 빠르게 결정을 내리기 위해서는, 시스템이 한 번에 모든 미세한 세부 사항을 제어하려고 노력하는 것을 멈춰야 한다는 점을 깨달았습니다. 그들의 해결책은 운전 과업을 두 개의 뚜렷한 계층으로 나누는 것입니다. 첫 번째 계층은 고수준 내비게이터로서, 광범 l하고 단순화된 지도를 보고 차량이 어느 일반적인 방향으로 향해야 할지 결정합니다. 두 번째 계층은 실제 물리학을 다루는 국소 제어기로, 차량이 목표 방향에 부드럽게 도달할 수 있도록 가속, 순항, 제동을 관리합니다. 이처럼 '어디로 갈 것인가'와 '어떻게 움직일 것인가'를 분리함으로써, 시스템은 매 순간 수행해야 하는 계산량을 획기적으로 줄였습니다.

연구진은 최대 2,000대의 차량이 다양한 창고 레이아웃을 가로지르는 시뮬레이션을 통해 이 접근 방식을 테스트했습니다. 그 결과, 이 시스템은 이전 방식들보다 작업을 훨씬 더 빠르게 완료할 수 있었으며, 일부 시나리오에서는 주문 배치를 완료하는 데 필요한 총 시간을 거의 절반 가까이 단축했습니다. 결정적으로, 이 시스템은 속도를 희생하지 않으면서도 안전성을 유지했습니다. 차량들이 고속으로 이동하며 좁은 공간을 통과할 때도 충돌을 방지했습니다. 단 한 대의 차량이 지연을 겪을 때마다 모든 것을 멈추고 재계산하던 기존 시스템과 달리, 이 새로운 프레임워크는 충돌에 연루된 특정 차량들만을 조정함으로써 나머지 군단이 계속 움직일 수 있도록 합니다. 이러한 유연성 덕분에 시스템은 차량이 속도를 줄이거나 일시적인 장애물이 생기는 것과 같은 예상치 못한 돌발 상황이 발생해도 전체 운영을 중단시키지 않고 대응할 수 있습니다.

시스템이 실제 환경에서 빠르게 작동할 수 있도록 하기 위해, 연구진은 비동기식 의사결정 방식을 도입했습니다. 전통적인 설정에서는 모든 차량이 움직이기 전 컴퓨터가 다른 모든 차량과의 경로를 대조할 때까지 기다려야 하며, 이는 차량 규모가 커질수록 불가능할 정도로 느려지는 과정입니다. 새로운 시스템은 이미 부드럽게 움직이고 있는 차량들에 대해서는 이러한 검사를 건너뛰고, 차량이 멈추거나 방향을 바꿔야 할 때만 복잡한 결정을 내립니다. 이러한 최적화는 계산 부하를 매우 효과적으로 줄여서, 결정을 내리는 데 걸리는 시간이 차량이 실제로 이동하는 데 걸리는 시간보다 짧아지게 만들었습니다. 그 결과, 이 시스템은 대규모 군단도 소규모 군단만큼 쉽게 관리할 수 있음을 입증했으며, 인공지능의 적응력과 실제 기계를 지배하는 엄격한 물리 법칙을 결합하는 것이 가능하다는 것을 보여주었습니다.

또한 연구는 고수준 내비게이션을 구동하는 인공지능을 어떻게 학습시킬 것인가를 탐구했습니다. 연구진은 단순히 비어 있는 단순한 지도로 시스템을 가르치는 것만으로는 부족하며, AI가 잘 일반화되기 위해서는 장애물이 있고 난이도가 다양한 지도로 학습해야 한다는 것을 발견했습니다. 학습 환경의 복잡성을 점진적으로 높임으로써, 시스템은 붐비고 혼란스러운 창고에서도 효율적인 경로를 찾아내는 법을 배웠습니다. 다른 선도적인 방법들과 비교했을 때, 이 새로운 접근 방식은 속도와 신뢰성 모두에서 지속적으로 우수한 성능을 보였습니다. 다른 시스템들이 수백 대 이상의 차량을 처리하는 데 어려움을 겪거나 환경 변화에 적응하지 못할 때, 이 프레임워크는 수천 명의 에이전트에게도 원활하게 확장되었습니다. 이 연구 결과는 창고 자동화의 미래가 경직되고 미리 계획된 경로가 아니라, 실제 움직임에 따라 반응할 수 있는 유연하고 연속적인 시스템에 있다는 것을 시사합니다.

기술 요약: HiRAD: 유연한 대규모 AGV 라우팅 시스템

1. 문제 정의

본 논문은 실제 창고 환경에서 대규모 자동 가이드 차량(AGV) 함대를 라우팅하는 과제를 다룹니다. AGV는 현대 물류에 있어 필수적이지만, 기존의 라우팅 솔루션들은 유연성(동적 변화 및 고장에 대한 적응력)과 운동학적 제약(연속 공간에서의 물리적 운동 법칙 준수) 사이에서 근본적인 트레이드오프(trade-off) 문제에 직면해 있습니다.

고전적 다중 에이전트 경로 탐색 (MAPF): CBS 또는 ODrM*와 같은 솔버들은 조합 폭발적인 복잡도와 초이차(super-quadratic) 실행 시간 문제로 인해 어려움을 겪습니다. 이들은 종종 이상적인 그리드 또는 조각별 선형(piecewise-linear) 운동 모델에 의존하는데, 이는 실제 운동학을 포착하지 못해 연속적인 환경에서 충돌을 유발할 수 있습니다.
강화 학습 (RL) 접근 방식: 최근의 분산형 RL 솔루션들은 유연성을 제공하지만 확장성과 현실성 측면에서 어려움을 겪습니다. 이들은 일반적으로 이산화된 시공간 표현에 의존하며, 수백만 번의 훈련 에피소드가 필요하고, 매 단계마다 전체 맵 관찰로 인해 높은 추론 지연 시간이 발생합니다. 이는 실시간 산업 제어 제약을 위반하는 경우가 많습니다.
핵심 격차: 안전성과 효율성을 희생하지 않으면서 대규모 함대를 지원하고, 연속적인 운동학적 제약을 준수하며, 실시간 의사결정을 동시에 수행할 수 있는 시스템이 부족합니다.

2. 방법론: HiRAD 프레임워크

저자들은 이산 RL 알고리즘과 연속적인 물리적 실행 사이의 간극을 메우기 위해 설계된 계층적 RL 프레임워크인 HiRAD(High-Resolution and Hierarchical Routing with Asynchronous Decision Framework)를 제안합니다. 이 프레임워크는 세 가지 핵심 구성 요소로 이루어져 있습니다.

A. 고해상도 시공간 (HRS) 모델링

RL의 단계 기반 특성과 연속적 운동을 조화시키기 위해, HiRAD는 고해상도 모델링 방식을 도입합니다.

HR-Map: 공간 그리드를 더 작은 셀(예: $c \times c$ )로 세분화하여 더 미세한 공간 해상도를 생성합니다.
HR-Step: 시간 간격을 더 작은 단계( $\Delta t$ )로 나누어 AGV가 더 높은 시간 해상도에서 의사결정을 내릴 수 있도록 합니다.
속도 통합: 에이전트가 한 단계당 한 그리드를 이동하는 표준 MAPF와 달리, HRS는 각 단계에 스칼라 속도를 할당합니다. 이를 통해 가속, 정속, 감속을 모델링할 수 있어, 이산적인 RL 프레임워크 내에서 연속적인 역학을 효과적으로 시뮬레이션할 수 있습니다.

B. 계층적 교대 의사결정-속도 제어 (Alt-DVC)

확장된 행동 공간의 복잡성을 관리하기 위해, HiRAD는 내비게이션을 두 개의 층으로 분리합니다.

매크로-RL-라우팅 층 (Macro-RL-Routing Layer): 거친(coarse) 그리드 맵에서 작동합니다. 훈련된 단일 에이전트 정책(함대 전체에 재사용됨)을 사용하여 충돌 없는 방향을 출력합니다. 이 층은 다른 AGV를 정의된 "배제 구역"(AGV 주변의 5-그리드 영역) 내의 동적 장애물로 취급하여 충돌을 선제적으로 방지합니다.
마이크로 속도 제어 층 (Micro Velocity-Control Layer): 미세한 HR-Map에서 작동합니다. 매크로 방향을 사전 정의된 속도 모드(예: 다음 그리드로 이동, 연속 순항, 정지를 위한 감속)로 매핑하여 안전하고 연속적인 운동을 실행합니다. 이 모드들은 가속 $\to$ (최대) 속도 $\to$ 감속의 3단계 프로파일을 따르며, AGV가 그리드 중심에 정확히 멈추도록 보장합니다.

충돌 해결: 시스템은 속도와 장애물 밀도에 기반한 우선순위 스케줄링을 채택합니다. 높은 우선순위의 AGV는 진행하고, 낮은 우선순위의 AGV는 높은 우선순위 에이전트의 배제 구역을 장애물로 취급하여 진입 전 멈춥니다.

C. 비동기 의사결정-속도 제어 (Asy-DVC)

의사결정 시간이 물리적 실행 시간을 초과하는 지연 병목 현상을 해결하기 위해, HiRAD는 비동기 최적화를 도입합니다.

관측 프루닝 (Observation Pruning): 운동학적 제약으로 인해 즉각적인 헤딩 변경이 불가능하므로, 시스템은 이미 움직이고 있는 AGV에 대해 매크로 정책 추론을 건너뜁니다. 추론은 AGV가 정지 상태( $v=0$ )이고 방향 재설정이 필요할 때만 트리거됩니다. 이는 관측 복잡도를 $O(n)$ 에서 약 $O(n/4)$ 로 줄여줍니다.
맵 지향 우선순위 (Map-Oriented Priority): 모든 AGV 간의 쌍별(pairwise) 충돌 체크( $O(n^2)$ )를 수행하는 대신, 시스템은 거친 맵 상의 그리드 인덱스 우선순위 구조를 사용합니다. AGV는 목적지 그리드에 있는 최상위 우선순위 에이전트만을 확인하므로, 우선순위 처리 복잡도가 $O(n^2)$ 에서 $O(n)$ 으로 감소합니다.
결과: 이 최적화는 전체 추론 복잡도를 $O(n^2)$ 에서 $O(n)$ 으로 낮추어, 단계당 지연 시간을 최대 71%까지 절감합니다.

3. 주요 기여

본 논문은 다음과 같은 기여를 주장합니다.

HiRAD 프레임워크: 실시간 보장을 제공하면서 운동학적 제약이 있는 환경에서 대규모, 충돌 없는 AGV 라우팅을 가능하게 하는 새로운 시스템.
고해상도 시공간 모델: 미세한 공간 셀과 속도 상태를 통합하여 단계 기반 RL을 연속적 환경에 적응시킨 모델.
계층적 제어 (Alt-DVC): 방향과 속도 결정을 분리하여 탐색 공간을 줄이고, 배제 구역 및 우선순위 스케줄링을 통해 충돌 회피를 강제하는 분리 전략.
비동기 최적화 (Asy-DVC): 관측 프루닝과 맵 지향 우선순위를 활용하여 의사결정 복잡도를 이차(quadratic)에서 선형(linear)으로 줄여 실시간 배포를 가능하게 함.
실증적 검증: 최첨단 솔루션 대비 우수한 성능을 입증하는 광범위한 실험.

4. 실험 결과

저자들은 무작위 그래프와 두 가지 실제 창고 레이아웃(Layout-A 및 Layout-B)에서 64대에서 2,048대의 함대 규모를 대상으로 HiRAD를 평가했습니다.

확장성: 고전적 방법(ICBS, ODrM*)은 64대를 초과하는 함대에 대해 결과를 제공하지 못했습니다. PRIMAL(대규모 RL 베이스라인)은 2,048대까지 처리할 수 있었으나, 높은 지연 시간과 밀집된 시나리오에서의 낮은 성공률을 보였습니다. HiRAD는 2,048대까지 성공적으로 확장되었습니다.
효율성 (Makespan): HiRAD는 베이스라인 대비 메이크스팬(마지막 에이전트가 목표에 도달하는 시간)을 45%~63% 단축했습니다. 크기 40의 맵에서 HiRAD는 PRIMAL보다 3~4배 빨랐으며, 크기 160에서는 약 2배 더 빨랐습니다.
실행 시간: HiRAD는 고전적 방법 및 다른 RL 기반 방법들과 비교하여 현저히 낮은 엔드 투 엔드(end-to-end) 실행 시간을 달왔으며, 실시간 제약을 충족했습니다.
유연성: 동적 장애(예: 10%의 AGV가 문제를 겪음)가 포함된 "라이프롱(lifelong)" 작업 시뮬레이션에서, HiRAD는 시스템 전체의 재계획 없이 성능을 유지했습니다. 반면, OHSMD와 같은 중앙 집중식 플래너는 전체 함대를 중단하고 재계획해야 했기에 상당한 지연이 발생했습니다.
훈련: 커리큘럼 학습(작고 장애물이 없는 맵에서 시작하여 점진적으로 난이도를 높임)과 무효 행동 마스킹(Invalid Action Masking, IAM)의 사용은 대규모 복잡한 맵에서의 수렴 속도와 성공률을 크게 향 향상시켰습니다.

5. 의의 및 주장

본 논문은 HiRAD를 이론적 RL 기반 라우팅과 실제 산업 적용 사이의 가교로 포지셔닝합니다. 저자들의 주장은 다음과 같습니다.

기존 솔루션들은 이산적 가정(운동학적 제약 위반)을 하거나 중앙 집중식 계획(유연성 부족)을 한다는 점에서 실용성이 떨어졌습니다.
HiRAD는 운동학적 제약을 엄격히 준수하고 연속 공간에서 충돌 없는 운행을 보장하면서 대규모 함대(최대 2,048대)를 지원하는 최초의 RL 기반 솔루션입니다.
비동기 최적화(Asy-DVC)는 의사결정 지연 시간이 물리적 실행 시간보다 짧게 유지되도록 하여 실시간 적용에 결정적입니다.
이 시스템은 효율성과 확장성 모두에서 최첨단 방법들을 능가하며, 동적인 창고 환경을 위한 견고하고 적응 가능한 솔루션을 제공합니다.