스티그메틱 그래프 메모리(SGM)라는 새로운 메모리 계층이 최근 실행 패턴을 학습하여 창고 로봇 군집의 교통 체증을 방지해 준다. 다섯 가지 창고 레이아웃에 대한 벤치마크 테스트에서 SGM은 기존 최고의 다대다 작업 할당 방식 대비 작업 완료율을 20.5%~36.7% 향상시켰다.
목차
연구진이 만든 것
메릴랜드 대학교와 조지 메이슨 대학교의 연구진은 다중 에이전트 창고 시스템에서 작업 할당과 경로 계획 사이에 위치하는 경량 메모리 시스템인 스티그메틱 그래프 메모리(SGM)를 구축했다. SGM은 창고 그래프의 노드(보관 장소, 교차점)와 방향성 엣지(통로 구간) 모두에 감쇠 메모리 채널을 유지한다. 각 채널은 노드 혼잡, 대기 이벤트, 차단 압력, 작업 성공, 방향별 트래픽 흐름, 통행 지연 등 다양한 유형의 최근 정보를 저장한다.
SGM은 단일 '혼잡 점수' 대신 이러한 신호를 분리하여 엔드포인트 조향과 경로 안내라는 두 가지 제어 인터페이스에 매핑한다. 엔드포인트 조향은 노드 메모리를 활용하여 에이전트에 할당할 픽업 또는 배송 위치의 순위를 매기고, 경로 안내는 엣지 메모리를 사용하여 재계획 시 경로 비용에 영향을 준다. 이러한 분할 설계는 에이전트가 움직이기 시작하기 전에 문제가 될 수 있는 영역을 회피할 수 있게 한다.
SGM은 M2M 다대다 MAPD 프레임워크(Schneider et al., 2026) 위에 플러그인 계층으로 작동한다. 기본 경로 계획기나 충돌 회피 시스템을 변경할 필요가 없다. 연구진은 혼잡 증거가 강할 때만 메모리 기반 결정을 활성화하여 처리량 일부를 희생하는 대신 계산 오버헤드를 낮추는 적응형 변형 ASGM도 구축했다.
주요 결과
다섯 가지 창고 레이아웃과 세 가지 군집 크기(28, 56, 84대 에이전트로 각각 주차 용량의 30%, 60%, 90%에 해당)에 걸친 쌍체 벤치마크에서 SGM은 모든 조건(15개 지도-군집 조합 전체)에서 기본 M2M 방식과 SKU 인식 변형(M2M-wSKU)보다 뛰어난 성능을 보였다. 처리량 향상 폭은 20.5%~36.7%였으며, Holm 보정 Wilcoxon 부호 순위 검정에서 모두 통계적으로 유의미했다.
| 조건 | SGM 처리량(완료된 작업) | M2M-wSKU 처리량 | SGM 향상률 |
|---|---|---|---|
| 창고 A, 84대 에이전트 | ~7100 | ~5700 | +24.6% |
| 창고 B, 84대 에이전트 | ~6800 | ~5400 | +25.9% |
| 미로 X, 84대 에이전트 | ~6500 | ~5000 | +30.0% |
| 미로 Y, 84대 에이전트 | ~6200 | ~4500 | +37.8% |
| 전체 15개 조건 평균 | — | — | +20.5%~+36.7% |
구성 요소 제거 실험 결과 엔드포인트 조향만으로도 전체 SGM 처리량의 99.3~100.5%를 달성하여, 핵심 통찰은 경로를 어떻게 지정할지가 아니라 어떤 출발지와 목적지를 할당할지 선택하는 것임이 입증되었다. 경로 안내를 추가하면 대부분의 조건에서 계획기 실행 시간, 대기 시간, 차단으로 인한 재계획 횟수를 줄이면서 처리량을 유지했다.
중간 규모 이전 연구(더 큰 창고, 200대 이상 에이전트)에서도 SGM이 완료된 작업을 개선하여, 접근 방식이 기본 벤치마크를 넘어 확장 가능함을 보여주었다.
작동 원리
SGM은 다대다 픽업 및 배송 문제를 2단계 의사 결정 프로세스로 처리한다. 첫째, 에이전트가 사용 가능해지면 엔드포인트 조향이 메모리 값을 사용하여 모든 가능한 픽업 및 배송 위치의 점수를 매긴다. 둘째, 경로 안내가 계획 중에 방향성 엣지 메모리를 사용하여 경로 비용을 수정한다.
메모리 진화 공식: 각 그래프 요소(노드 또는 방향성 엣지)와 각 메모리 채널에 대해 저장된 값은 시간이 지남에 따라 지수적으로 감쇠한다. 감쇠 상수는 오래된 정보가 얼마나 빨리 사라지는지를 정의한다. 새로운 이벤트는 채널 값에 추가된다. 공식은 다음과 같다.
M(t+1) = M(t) * decay + event_value
감쇠율과 이벤트 주입 논리는 채널별로 조정된다. 예를 들어, 노드의 '차단 압력' 채널은 예측된 정점 충돌로 인해 에이전트가 제자리에 갇혀 있을 때 증가하는 반면, '성공적 완료' 채널은 에이전트가 해당 위치에서 작업을 완료할 때 증가한다.
엔드포인트 조향: 에이전트가 새 목표(픽업 또는 배송)가 필요할 때 SGM은 각 가능한 엔드포인트에 대한 복합 점수를 계산한다. 이 점수는 해당 노드와 관련된 메모리 채널(트래픽 강도, 대기 이벤트, 차단 압력, 완료율)의 가중 합이다. 대기 또는 차단 압력이 높으면 점수가 낮아지고, 완료율이 높으면 점수가 높아진다. 가중 합은 M2M 할당 목표와 결합되어 에이전트가 핫스팟을 피하면서도 작업을 계속 진행할 수 있게 한다.
경로 안내: 경로 계획 중에 엣지 메모리 값이 이동 비용에 기여한다. 차단, 지연 또는 혼잡이 많은 엣지는 페널티를 받는다. 계획기(RHCR/PBS 백엔드)는 여전히 충돌 없는 계획을 보장하며, 메모리 비용은 단순히 로봇을 덜 혼잡한 경로로 유도한다.
컨트롤러 변형: SGM은 엔드포인트 조향과 경로 안내 모두에 메모리를 사용하며, 경로 재수리 시 대기 중인 작업을 유지한다. ASGM은 혼잡 메트릭이 낮을 때 M2M-wSKU 기준선 동작으로 대체되는 적응형 버전으로, 대기, 백로그 또는 차단이 임계값을 초과할 때만 메모리를 활성화한다. 이는 계산량을 절약하지만 최대 처리량은 감소시킨다.
로봇 공학에서의 중요성
중고 산업용 로봇 또는 창고 로봇을 운영하는 창고 업체는 로봇 속도가 아니라 혼잡(교차로에서 대기, 좁은 통로에서 서로 차단, 인기 있는 픽업 스테이션에서 줄 서기)으로 인한 처리량 병목 현상을 자주 경험한다. 기존의 다중 에이전트 계획은 혼잡에 반응적으로 대처한다. 즉, 혼잡 지역이 발생한 후에 우회 경로를 설정한다. SGM은 다대다 작업 할당이 더 높은 레버리지를 가진 제어 지점을 제공한다는 것을 보여준다. 즉, 처음부터 로봇을 혼잡한 통로에 할당하지 않으면 우회 경로를 설정할 필요가 없다.
동적 환경에 배치되는 중고 협동 로봇의 경우 SGM과 같은 메모리 계층을 트래픽 패턴이 예측 불가능하게 변화하는 인간-로봇 협업 환경에 이식할 수 있다. 핵심 원칙인 다양한 혼잡 신호에 대한 별도 메모리를 할당 시점에 사용하는 것은 도메인에 구애받지 않는다.
적응형 ASGM 변형은 계산 능력이 제한된 엣지 배포에 특히 적합하다. 혼잡이 실제 문제가 될 때만 메모리 오버헤드를 지불하기 때문이다. 군집 운영자는 기본 계획기나 충돌 회피 시스템을 변경하지 않고도 감쇠 상수를 창고 트래픽 리듬에 맞게 조정할 수 있다.
한계와 과제
SGM은 시뮬레이션에서만 평가되었으며 실제 로봇 배치는 이루어지지 않았다. 센서 노이즈, 통신 지연, 하드웨어 오류와 같은 실제 환경 효과는 메모리 신호의 동작을 변화시킬 수 있다. 메모리 채널과 가중치는 수동으로 설계되었으며, 논문에서는 학습되거나 적응형 채널 튜닝을 탐구하지 않았다. 또한 엔드포인트 조향의 이점이 너무 커서 경로 안내 구성 요소가 덜 중요할 수 있으며, 향후 연구에서는 아키텍처를 단순화할 수 있다.
연구는 고정된 창고 레이아웃 세트를 사용했다. 비정적 환경(예: 계절별 재고 이동, 재구성 가능한 보관)에서는 메모리 감쇠율이 조정되지 않으면 SGM 성능이 저하될 수 있다. 마지막으로, SGM은 M2M 다대다 작업 모델을 가정하므로 일대일 MAPD 또는 재고 유연성이 없는 작업 할당에는 직접 적용되지 않는다.
자주 묻는 질문
다대다 다중 에이전트 픽업 및 배송이란 무엇인가? 다대다 MAPD에서 각 작업(예: 'A 품목을 보관소에서 출하장으로 이동')은 여러 가능한 픽업 위치에서 처리되고 여러 목적지로 배송될 수 있어, 디스패처가 혼잡을 피할 수 있는 유연성을 제공한다.
스티그메틱 그래프 메모리는 표준 혼잡 회피와 어떻게 다른가? 표준 혼잡 회피는 반응적이다. 즉, 혼잡을 감지한 후 로봇의 경로를 변경한다. SGM은 사전 예방적이다. 즉, 최근 메모리를 사용하여 엔드포인트 선택 순위를 매겨 로봇이 덜 혼잡한 영역에 할당되도록 하여 사전에 혼잡을 방지한다.
SGM은 어떤 종류의 메모리 신호를 추적하는가? SGM은 노드 혼잡, 대기, 차단 압력, 작업 완료, 엣지 통행 횟수, 지연 통행, 방향별 흐름에 대한 별도의 감쇠 신호를 추적한다. 이들은 단일 혼잡 점수로 병합되지 않고 별도로 유지된다.
SGM은 기존 창고 제어 시스템과 함께 작동할 수 있는가? 그렇다. 작업 할당과 경로 계획 사이에 위치하는 경량 메모리 계층으로 설계되었으며, 표준 RHCR/PBS 계획기 위에서 평가되었다. 충돌 회피나 로봇 펌웨어 변경이 필요하지 않다.
결론
SGM은 간단하면서도 강력한 아이디어를 도입한다. 즉, 최근 트래픽 이벤트에 대한 감쇠 메모리를 유지하고 이 메모리를 사용하여 어떤 작업을 어떤 엔드포인트에 할당할지 선택함으로써 창고 로봇 군집이 처음부터 혼잡을 만들지 않도록 할 수 있다. 다양한 레이아웃에서 20~36%의 처리량 향상은 모든 다대다 창고 디스패치 시스템에 스티그메틱 메모리를 추가해야 할 강력한 이유를 제공한다. 향후 연구에서는 이 접근 방식을 실제 로봇에서 테스트하고 변화하는 창고 레이아웃에 적응시킬 예정이다.