🤖 AI

Complete, Scalable, and Robust Prioritized Planning for Multi-Robot Ordered Storage and Retrieval at Maximum Capacity

이 논문은 불확실한 출발 순서에 대한 강건성을 위해 무시할 수 있는 수준의 오버헤드를 유지하면서도, 데드락 없는 실행과 근선형적인 메이크스팬 개선을 보장하는, 최대 용량 퍼즐 기반 창고에서의 다중 로봇 순차 저장 및 인출을 위한 새롭고 완전하며 확장 가능한 우선순위 지정 계획 알고리즘을 제시한다.

원저자: William Zhang, Tzvika Geft, Jingjin Yu, Kostas Bekris

게시일 2026-08-11

📖 2 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: William Zhang, Tzvika Geft, Jingjin Yu, Kostas Bekris

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

모든 창고의 모든 평방 인치가 마치 테트리스 판이 빈틈없이 꽉 채워진 것처럼 빈틈없이 가득 찬 세상을 상상해 보십시오. 이것은 임대료를 아끼기 위해 저장 밀도를 극대화하려는 현대 물류의 꿈입니다. 하지만 여기에는 함정이 있습니다. 만약 지게차나 로봇이 지나갈 통로가 없을 정도로 방을 빽빽하게 채운다면, 어떻게 물건을 꺼낼 수 있을까요? 이것이 바로 "퍼즐 기반 저장(Puzzle-Based Storage)"의 난제입니다. 모든 아이템이 하나의 타일이고, 하나를 움직이기 위해서는 주변의 다른 것들을 재배치해야 하는 고전적인 15 퍼즐 게임과 같은 슬라이딩 타일 퍼즐을 떠올려 보십시오. 이제 한 사람이 타일을 움직이는 것이 아니라, 로봇 팀 전체가 동시에 작업한다고 상상해 보십시오. 문제는 혼란스러운 춤이 됩니다. 만약 로봇들이 완벽하게 조율되지 않는다면, 아무도 움직일 수 없는 상태인 '데드락(deadlock, 교착 상태)'이라 불리는 교통 체증에 빠질 수 있습니다. 온라인 쇼야가 폭발적으로 증가함에 따라 창고는 매우 빽빽하면서도 매우 빨라야 하므로, 이를 해결하는 것은 매우 중요합니다.

이 논문은 바로 그 혼란을 다룹니다. 러트거스 대학교 연구진인 저자들은 통로가 없는 꽉 찬 창고에서 로봇 군집을 조율하는 새로운 방법을 제안합니다. 이들은 두 가지 뚜렷한 단계를 처리하는 시스템을 도입합니다. 첫째는 들어오는 물품으로 창고를 절대적인 최대 용량까지 채우는 것이고, 둘째는 트럭이 도착하여 물건을 실어 갈 때 특정 순서에 따라 물건을 꺼내는 것입니다. 이들 솔루션의 핵심은 "우선순위 기반 계획(prioritized planning)" 알고리즘입니다. 모든 로봇의 경로를 동시에 계산하려고 시도하는 대신(이는 백만 조각짜리 퍼즐을 한꺼번에 풀려고 하는 것과 같으며 보통 컴퓨터를 다운시킵니다), 이들은 로봇들이 차례를 갖도록 합니다. 한 로봇이 작업을 마치면, 다음 가능한 작업을 가져와 경로를 설정하고, 다른 로봇들은 자신의 차례를 기다리거나 길을 비켜줍니다.

논문은 이 접근 방식이 단순한 기교가 아니라 강력한 해결책임을 입증합니다. 저자들은 창고가 100% 가득 차 있는 상황에서도 로봇들이 결코 데드락에 빠지지 않음을 수학적으로 증명합니다. 시뮬레이션에서 이들은 최대 30대의 로봇이 투입된 30x30 셀 크기의 그리드를 테스트했습니다. 결과는 로봇을 더 많이 추가할수록 작업 완료 속도가 거의 선형적으로 빨라진다는 것을 보여주었습니다. 예를 들어, 20x20 그리드에서 20대의 로봇을 사용하는 것은 단 한 대의 로봇을 사용할 때보다 거의 20배 더 빨랐습니다. 아마도 가장 놀라운 점은, 불확실성에 대해 시스템을 "강건하게(robust)" 만드는 것, 즉 트럭의 순서가 마지막 순간에 약간 변경되더라도 창고가 이를 처리할 수 있게 만드는 것이 속도 면에서 거의 손해가 없다는 사실을 발견했다는 점입니다. 계획이 경직되어 있든 유연하든 로봇들은 똑같이 빠르게 움직입니다. 이들의 방법이 매우 복잡하고 느린 중앙 집중형 계획가에 비해 이론적으로 완벽하지는 않을지라도, 실시간으로 실행될 만큼 충분히 빠르며 매우 잘 확장됩니다. 이는 붐비고 정적인 퍼즐을 고속의 움직이는 기계로 바꾸는 실용적인 방법을 제시합니다.

기술 요약: 최대 용량에서의 다중 로봇 순차적 저장 및 인출을 위한 완전하고 확장 가능하며 견고한 우선순위 계획법

1. 문제 정의

본 논문은 고밀도 퍼즐 기반 저장(PBS) 시스템, 특히 "최대 용량에서의 순차적 저장 및 인출 문제"에서 여러 로봇을 조정하는 과제를 다룹다.

문맥 및 과제:

고밀도 제약 조건: 내부 통로를 사용하는 전통적인 자동 창고 시스템(AS/RS, 예: Kiva 방식)과 달리, PBS 아키텍처는 저장 밀도를 극대화하기 위해 내부 통로를 제거한다. 저장 그리드는 제한된 빈 셀을 사용하여 하중을 재배치하는 슬라이딩 타일 퍼즐처럼 작동한다.
운영 단계: 시스템은 두 가지 별개의 단계로 운영된다:
1. 저장: 하중이 특정 순서에 따라 컨베이어 벨트를 통해 도착하며, 그리드 용량의 최대 100%까지 저장되어야 한다.
2. 인출: 하중은 사전에 계획된 출발 순서에 따라 인출되어야 한다.
핵심 갈등: 선행 연구(StoRMR 및 R-StoRMR)는 순차적(단일 로봇) 재배치 불필요 배치가 기하학적으로 가능하다는 것을 입증했지만, 이를 다중 로봇을 사용하여 병렬로 실행하는 것은 여전히 미개척 분야로 남아 있다. 이러한 밀집된 통로 없는 환경에서 여러 로로봇을 조정하는 것은 데드락(교착 상태)의 높은 위험과 중앙 집중식 플래너의 차원의 저주로 인해 계산적으로 매우 어렵다.
불확실성: 시스템은 실제 인출 순서가 계획에서 약간 벗어날 수 있는 경우(k-유계 섭동으로 모델링됨)에도 불확실성을 처리해야 한다.

2. 방법론

저자들은 재배치 불필요 저장 배치(relocation-free storage arrangements)의 특정 기하학적 불변성을 활용하여 완전성을 보장하고 데드락을 방지하는 온라인, 우선순위 기반 다중 에이전트 경로 탐색(MAPF) 알고리즘을 제안한다.

시스템 모델

환경: 직사각형 그리드( $R \times C$ )와 그 아래의 I/O 행 및 컨베이어 벨트.
에이전트: 이동, 회전, 하중 픽업 및 드롭오프가 가능한 $m$ 개의 로봇 ( $m \le C$ ).
2단계 높이 모델: 로봇은 정지된 하중 아래를 주행할 수 있는 AMR 스타일로 이동하며, 동시에 동일한 셀을 점유하지 않는 한 하중 아래를 통과할 수 있다.
제약 조건: 위치 충돌(두 엔티티가 한 셀에 존재) 및 방향 충돌(교차 또는 직교 충돌)을 피하지만, "열차(train)" 형태의 움직임(동일한 방향을 따라가는 것)은 허용된다.

알고리즘: 비동기 우선순위 계획

이 접근 방식은 모든 에이전트를 동시에 해결하는 대신, 유휴 로봇에게 동적으로 작업을 할당함으로써 계획 프로세스를 분리한다.

작업 할당:
- 저장: 로봇이 유휴 상태가 되면, 도착 순서에서 아직 할당되지 않은 다음 하중이 할당된다. 픽업 지점에 가장 가까운 로봇이 탐욕적(greedy)으로 선택된다.
- 인출: 로봇은 출발 순서에서 아직 할당되지 않은 다음 하중을 점유한다. 로봇은 유효한 경로가 성공적으로 계산된 경우에만 하중을 점유한다.
경로 계획:
- 플래너는 로봇의 현재 위치에서 픽업/드롭오프 지점까지 시간 최소화 A* 탐색을 사용하여 시간-최소 궤적을 생성한다.
- 글로벌 예약 테이블: 충돌을 방지하기 위해, 시스템은 위치 $p$ , 타임스텝 $t$ , 금지된 진입 방향 $d$ 를 추적하는 시공간 제약 $(p, t, d)$ 를 기록하는 예약 테이블을 유지한다. 이는 명시적으로 방향성 추종 충돌을 방방지한다.
- 장애물 관리: 저장된 하중은 정적 장애물로 취급된다. 로봇이 하중을 픽업하기 위해 계획할 때 장애물 테이블에서 제거되고, 하중을 드롭오프할 때 다시 추가되는 방식으로 동적으로 업데이트된다.
인출 복잡성 처리:
- 인출 시 로봇이 하중을 드롭오프한 후 어디에서 대기해야 하는지를 결정하는 것이 핵심적인 과제이다.
- 전략: 알고리즘은 다음 미할당 하중 아래에 로봇을 위치시키려고 시도한다. 만약 접근이 불가능하다면, 가장 가까이 접근 가능한 미할당 하중 아래에서 대기하는 것으로 대체한다. 만약 접근 가능한 하중이 없다면, 로봇은 뒷줄의 보장된 비방해 셀로 이동한다.
- 순서 준수: 출발 순서를 보장하기 위해, 로봇은 $j-1$ 번째 하중이 I/O 행으로 가는 경로가 큐에 쌓인 후에만 $j$ 번째 하중을 위한 경로를 계획한다.

이론적 보장

저자들은 저장 및 인출 단계 모두에 대해 완전성(알고리즘이 솔루션이 존재한다면 항상 찾아냄)을 증명한다.

근거: 이 증명은 재배치 불필요 배치(선행 StoRMR/R-StoRMR 연구에서 확립됨)의 특성에 의존한다. 이러한 배치는 다른 하중들이 움직이지 않는 한, 순서 내의 모든 하중에 대해 I/O 행까지의 충돌 없는 경로가 존재함을 보장한다.
귀납법: 저자들은 첫 $k-1$ 개의 하중이 성공적으로 저장/인출되면, 배치의 기하학적 특성이 $k$ 번째 하중 또한 적어도 하나의 유휴 로봇에 의해 접근 가능함을 보장하여, 100% 밀도에서도 데드락을 방지한다는 것을 귀납법을 통해 보여준다.

3. 주요 기여

다중 로봇 정식화: 최대 용량에서의 순차적 저장 및 인출을 위한 새로운 정식화를 도입하여, 기하학적 가능성(순차적)과 실행 효율성(병렬적) 사이의 간극을 메운다.
우선순위 계획 알고리즘: 밀집된 환경에서 완전성과 데드락 방지를 보장하기 위해 재배치 불료 배치의 불변성을 활용하는 비동기 온라인 알고리즘을 제안하며, 이는 우선순위 기반 MAPF 방법론에서 드문 성과이다.
확장성 및 효율성: 제안된 방식이 로봇 수가 증가함에 따라(최대 $m = C$ 까지) 메이크스팬(총 소요 시간)에서 거의 선형적인 개선을 달라는 것을 입증한다.
미미한 오버헤드를 가진 견고성: 출발 순서의 불확실성(R-StoRMR)을 처리하는 것이 비견고한 베이스라인과 비교했을 때 실행 속도에 유의미한 페널티를 주지 않음을 보여준다.
낮은 부적정성: 이론적으로 최적이지만 확장성이 낮은 중앙 집중식 결합 플래너와 비교했을 때, 낮은 메이크스팬 부적정성(비율 1.09 ~ 의 1.21)을 보인다.

4. 실험 결과

실험은 최대 $30 \times 30$ 그리드와 다양한 로봇 수(1 ~ $C$ )를 대상으로 수행되었다.

확장성: 시스템은 로봇 수가 증가함에 따라 메이크스팬 감소에서 거의 선형적인 속도 향상을 달}{성한다. $20 \times 20$ 그리드의 경우, 개선 비율은 20대의 로봇까지 이상적인 선형 벤치마크를 밀접하게 따른다.
실행 시간: 그리드 크기와 로봇 수가 증가하더라도 하중당 계획 시간은 1초 미만으로 유지되어, 실시간 온라인 운영에 적합함을 보여준다.
견고성 페널티: 표준 배치( $k=0$ )와 견고한 배치( $k=0.4C$ )를 비교했을 때, 실행 페널티는 무시할 수 있는 수준인 것으로 나타났다. 메이크스팬과 총 이동 거리는 거의 동일했다.
조정 오버헤드: 충돌 회피 기동으로 인해 로봇이 많아질수록 총 이동 거리는 약간 증가하지만, 그 증가 폭은 완만하다(20대 로봇의 경우 단일 로봇 대비 5% 미만).
최적성: 결합 A* 솔버(계산 복잡성으로 인해 작은 배치로 제한됨)와 비교했을 때, 우선순위 플래너는 1.09에서 1.21 사이의 부적정성 비율을 보인다. 저자들은 이 격차의 일부를 결합 플래너가 순서를 약간 재조정하여 컨베이어 모델을 활용할 수 있는 능력 때문이며, 우선순위 방식은 엄격한 순서 보장을 위해 이를 피한다는 점에 기인한다고 설명한다.

5. 의의 및 주장

본 논문은 자동 물류의 근본적인 트레이드오프, 즉 저장 밀도를 극대화하면서 높은 인출 처리량을 유지하는 문제를 해결한다고 주장한다. 우선순위 계획이 특정 기하학적 불변성에 의해 유도될 때 100% 밀도 환경에서도 완전하고 데드락이 없을 수 있음을 증명함으로써, 본 연구는 퍼즐 기반 저장 시스템에서 다중 로봇 시스템의 실질적인 배치를 가능하게 한다.

저자들은 제안된 방식이 "차원의 저주"를 수반하는 중앙 집중식 플래너를 필요로 하지 않는다는 점을 강조한다. 대신, 저장 레이아웃의 구조적 특성을 활용하여 확장 가능한 병렬 실행을 가능하게 한다. 결정적으로, 본 연구는 불확실성에 대한 견고성(가변적인 출발 순서 처리)이 시스템의 속도나 효율성을 희생하지 않고도 통합될 수 있음을 보여주며, 이는 도착 및 출발 시간이 변할 수 있는 실제 물류 환경에 대한 실행 가능한 솔루션이 된다.

결론적으로, 결합 탐색에 비해 약간의 최적성 격차가 존재하지만, 제안된 방법의 확장성과 견고성은 대규모 실시간 애플리케이션에서 더 우수하다. 향후 연구로는 최적성 격차를 좁히기 위한 다른 MAPF 기법(예: PIBT)의 탐색과 다중 로봇 협업에 특화된 배리에이션에 대한 조사가 제안되었다.