이 장면을 상상해 보십시오. 40대의 자율이동로봇이 하나의 창고 바닥을 공유합니다. 교차로에서 만나 서로 양보하고, 좁은 통로를 흠집 하나 없이 지나갑니다. 솔직히 말해서, 러시아워의 인간 운전자보다 훨씬 규율이 잡혀 있습니다. 애리조나의 한 물류센터에서 메자닌 층에서 이 광경을 처음 내려다봤을 때, 저는 머리 속에 하나의 질문을 품은 채 한참을 서 있었습니다. "이 오케스트라를 지휘하는 건 누구지?" 그날 오후 그들의 엔지니어들과 함께 시간을 보낸 뒤, 답을 알게 되었습니다. 모든 움직임을 지시하는 단일 '슈퍼 브레인' 같은 것은 없습니다. 멀티에이전트 스케줄링이라는 시스템이 있었습니다. 이 글에서는 그것을 세 조각으로 나눕니다. 일을 어떻게 배분하는지, 로봇이 길을 어떻게 찾는지, 그리고 두 대가 같은 바닥을 원할 때 무슨 일이 벌어지는지. 그리고 마지막으로, 어느 정도 규모가 되어야 그 수고를 들일 가치가 있는지 이야기합니다.
규모를 잡기 위한 숫자 두 개. 2012년, Amazon은 Kiva Systems를 775,000,000달러에 인수하면서 선반 운반 로봇을 자사 풀필먼트센터에 들였습니다. 2023년까지 Amazon은 창고 전체에 750,000대 이상의 로봇을 배치했다고 발표했습니다. 10여 년 만에 이동 로봇은 파일럿 프로젝트에서 대형 시설의 표준 장비가 되었습니다. 그리고 750,000대라는 숫자 뒤에서, 어려웠던 건 절대 '로봇 한 대를 달리게 만드는 것'이 아니었습니다. 수십 대, 수백 대의 로봇이 충돌도, 데드록도, 절반의 유휴도 없이 하나의 지붕 아래를 공유하게 만드는 것이었습니다. 바로 그 문제를 풀기 위해 멀티에이전트 스케줄링이 존재합니다.
누가 일을 맡을까
스케줄러의 첫 번째 임무는 작업 배분입니다. "A 랙에서 토트를 픽업해 B 패킹 스테이션으로 배달하라" 같은 일을 적절한 로봇에게 넘기는 일. 설명은 간단하지만, 실무에서는 트레이드오프의 연속입니다.
주류 학파는 두 가지입니다. 하나는 경매 기반입니다. 일이 생길 때마다, 대기 중인 모든 로봇이 랙까지의 거리, 남은 배터리, 근처에 다른 볼일이 있는지를 기준으로 '입찰'합니다. 최저 입찰가가 승리합니다. 다른 하나는 중앙집중형 최적화입니다. 중앙 서버가 모든 일과 모든 로봇의 상태를 모아 한 번에 전체 최적 배분을 계산합니다.
경매는 빠르고 단일 장애점에도 강합니다. 한 대가 오프라인이 되어도 나머지 로봇이 일을 계속 가져가는 것을 막지 못합니다. 대가는 국소 최적입니다. 전체 플릿의 주행 거리는 이론적 최적값보다 높게 나옵니다. 중앙집중형 최적화는 아름다운 계획을 내놓지만, 수십 대의 로봇과 초당 수백 건의 신규 작업에서는 솔버가 실시간 속도를 따라가지 못하고, 서버가 기침하면 바닥 전체가 함께 기침합니다.
제 의견은 직설적입니다. 50대 미만의 플릿이라면, 경매에 몇 가지 단순한 규칙을 더하는 것으로 충분합니다. 첫날부터 전체 최적을 쫓지 마십시오. 절약하는 주행 거리는 그 복잡성과 디버깅 시간의 비용을 메우지 못합니다. 한 번은 30,000평방피트 규모의 전자상거래 창고에서 12대의 로봇이 전체 최적화 풀 스케줄러로 돌아가는 것을 본 적이 있습니다. 엔지니어들이 석 달을 조정했지만, 피크 시즌을 구한 것은 태블릿으로 수동 배분을 두드리는 사람이었습니다. 알고리즘 선택에서 '충분히 좋은'이 황금보다 값집니다.
어떻게 길을 찾을까
일이 배분되면 로봇은 경로가 필요합니다. AMR은 사람처럼 표지판을 읽지 않습니다. 지도를 읽습니다.
창고 바닥은 보이지 않는 격자로 나뉩니다. 각 셀은 주행 가능하거나 장애물입니다. 스케줄러는 A* 계열의 경로 탐색 알고리즘을 실행해 각 로봇의 출발점에서 도착점까지의 경로를 계산합니다. 스마트폰 내비게이션처럼 들리지만, 창고 버전은 교통 법규 한 층이 더해집니다. 주 통로는 일방통행 거리가 되고, 교차로에는 양보 지점이 생기며, 충전 구역과 수작업 구역은 서행 구역이 되고, 적재 로봇과 공차 로봇은 서로 다른 가상 차선을 달립니다.
제가 직접 밟은 함정을 공유합니다. 여러분은 밟지 않도록. 한 모퉁이에서 로봇이 계속 비상정지했고, 로그는 장애물 알림으로 가득했습니다. 라이다를 교체하고, 파라미터를 세 번이나 다시 조정했지만 아무 소용이 없었습니다. 알고 보니 그 모퉁이 위에 신설된 고출력 액세스 포인트가 전파 버스트를 쏘면서 몇 밀리초씩 자기위치 추정 패킷을 날려버리고 있었습니다. 로봇은 자기 위치를 잃었다고 생각해 브레이크를 밟고 지시를 기다렸던 것입니다. 교훈: 경로 계획이 이상하게 굴 때는 알고리즘을 탓하기 전에 Wi-Fi 커버리지와 바닥 평탄도를 먼저 확인하십시오. 알고리즘은 물리적 환경을 고칠 수 없습니다. 이 문장은 한 번 더 나옵니다.
교차로에서는 무슨 일이 벌어질까
수십 대의 로봇이 하나의 도로망을 공유하니 교차로에서의 만남은 일상입니다. 충돌 해결이 정하는 것은 누가 먼저 갈지, 누가 양보할지, 그리고 무엇보다, 한 대 너비밖에 안 되는 통로에서 두 대가 정면으로 마주해 둘 다 물러나려 하지 않는 사태를 어떻게 하면 절대 막을 수 있는지입니다.
주력 기법은 예약 테이블입니다. 각 로봇은 자기 경로만 계획하는 것이 아니라, 앞으로 몇 초간 점유할 도로 구간을 '예약'합니다. 시간과 공간 모두에서 자리를 확보하는 것입니다. 다음 로봇이 경로를 계획하다가 특정 시간대에 그 구간이 이미 예약된 것을 보면, 우회하거나 잠시 기다립니다. 우선 규칙은 보통 선착순, 적재 로봇이 공차보다 우선, 그리고 충전을 서두르는 로봇이 모든 것을 이깁니다. 로봇 한 대가 죽는 것이 교통 체증보다 비용이 크기 때문입니다.
데드록은 악몽의 시나리오입니다. 두 대의 로봇이 좁은 통로에서 정면으로 만나고, 양쪽의 예약 테이블이 "내게 우선권이 있다"고 말합니다. 정지. 데드록은 길가에서의 흥정으로 막지 못합니다. 도로망 설계로 막습니다. 주 통로는 루프 형태로, 좁은 통로는 엄격하게 일방통행으로 하면 정면 충돌은 구조적으로 불가능해집니다. 제가 스케줄링 시스템을 평가할 때 데드록 건수는 필수 지표입니다. 일주일 내내 돌려 보십시오. 데드록이 두 자릿수가 나오면 도로망 설계가 잘못된 것입니다. "드문 엣지 케이스"라며 달래는 말은 듣지 마십시오.
언제 도입할 가치가 있을까
마지막으로, 가장 자주 받는 질문입니다. 저희 규모에서 멀티에이전트 스케줄링이 필요합니까?
제 분기점은 이렇습니다. 10대 미만이면 중앙집중형 스케줄링은 신경 쓰지 마십시오. 로봇 개체의 지능과 고정 교통 규칙, 수동 개입용 태블릿으로 충분합니다. 그 규모에서의 중앙집중형 스케줄링은 못 하나 박는 데 대형 해머를 드는 격이고, 게다가 다루기 불편한 해머입니다. 20대에서 50대 사이라면, 중앙집중형 작업 배분과 도로망 교통 규칙이 확실히 본전을 뽑기 시작합니다. 여기가 멀티에이전트 스케줄링의 스위트스팟입니다. 100대를 넘기면 존과 계층이 필요합니다. 중앙 시스템은 존 간 작업 흐름만 다루고 각 존은 자율 운영합니다. 그렇지 않으면 중앙 서버의 연산력과 통신 지연이 먼저 항복합니다.
제가 "건드리지 마십시오"라고 말할 두 가지 시나리오가 있습니다. 첫째, 바닥이 울퉁불퉁하고 랙 간격이 불규칙한 오래된 창고에서 자기위치 추정이 하루 종일 표류하는 경우입니다. 그런 물리적 환경에서는 스케줄링 알고리즘이 화재 진압에만 쫓깁니다. 둘째, 수요의 조석이 극심한 창고입니다. 예를 들어 피크 시즌 물량이 평상의 10배라 한산한 날은 20대로 충분하지만 12월에는 80대가 필요한 경우입니다. 스케줄링이 푸는 건 '어떻게 돌릴 것인가'입니다. '로봇이 모자라다'는 풀지 못합니다. 먼저 탄력적인 용량을 확보한 뒤에 지능 이야기를 하십시오.
내일부터 실행할 수 있는 세 가지 권장 사항입니다.
첫째, AMR을 한 대도 사기 전에 WMS에서 일주일치 작업 데이터를 뽑아 일이 어디에, 언제 몰리는지 히트맵을 만드십시오. 그리고 플릿 규모와 스케줄링 방식을 선택하십시오. 자신의 작업량이 어떤 모습인지 모르면 알고리즘을 선택할 준비가 안 된 것입니다.
둘째, 도로망을 먼저 설계하십시오. 일방통행 통로, 루프, 충전 구역 배치. 종이에 그려 최악의 경우를 통과시켜 보십시오. 가장 좁은 통로에서 만재한 두 대가 정면으로 만나는 경우, 피크 시간에 다섯 대가 동시에 충전을 필요로 하는 경우. 종이 위에서 돌아가지 않으면 바닥에서도 돌아가지 않습니다.
셋째, "로봇이 움직이고 있다"를 성공으로 인정하지 마십시오. 세 가지 숫자를 보십시오. 평균 작업 대기 시간, 주간 데드록 건수, 충전 대기 시간. 이 세 가지가 건강해 보이면 스케줄링 시스템이 진정으로 건강한 것입니다.
영어판 번역본입니다. 내용이 다를 경우 영어판을 우선합니다.
