Which MAPF Model Works Best for Automated Warehousing?
라는 이름의 논문이 있어서 읽어봤습니다.
제조물류 환경에서 로봇을 운용하는 업무를 하고있기때문에, 제목을 보자마자 읽고싶은 생각이 났죠.
VARAMBALLY, Sumanth; LI, Jiaoyang; KOENIG, Sven. Which MAPF Model Works Best for Automated Warehousing?. In: Proceedings of the International Symposium on Combinatorial Search. 2022. p. 190-198.
Abstract
MAPF의 대부분의 연구는 로봇 동역학을 단순화시킨 후 최적&최고의 품질의 경로를 찾는것을 목적으로 합니다.
그래서 현실에서 바로 사용하는데 한계가 있는데, 이는 로봇이 계획된 경로를 정확하게 따를 수 없기 때문입니다.
하지만....시뮬레이션처럼 로봇이 계획된 경로를 따라간다면 얼마나 좋을까요
제가 출장갔던 공장만 하더라도 로봇 옆에 사람이 슥 지나가기만 해도 감속 알고리즘에 의해 로봇 속도가 확 낮아지고, 로봇 경로에 근무자가 잠시 서있어서 로봇이 정지하고..... 뭐하나 계획대로 로봇이 가는일이 없죠.
위와 같은 현실적인 계획오류 문제를 해결하기 위해서 ADG(Action Dependency Graph)프레임워크가 제안되었습니다.
Persistent and Robust Execution of MAPF Schedules in Warehouses (읽어보세요! 좋은논문입니다.)
하지만 ADG만으로는 완벽하게 해결되기 힘들기때문에 RHCE까지 합쳐서 새로운 프레임워크를 제안하는게 본 논문의 핵심입니다.(RHCR이나 ADG에 대한 설명은 좀 길기때문에 아래 섹션에서 다루겠습니다.)
본 논문의 Contribution을 정리해보면...
1. ADG와 RHCR를 통합하여 Online MAPF 문제를 해결할수있는 프레임워크 제안
2. 향상된 통합 프레임워크를 다양한 기존모델과 비교
3. 물류센터 환경을 시뮬레이션할수있는 시뮬레이터(Gazebo)를 활용하여 처리량 향상에 미치는 영향 분석
Introduction
MAPF는 다수의 로봇에게 충돌없는 개별 경로를 계획하는 알고리즘입니다.
초기에는 수십대 단위에서 지금은 수천대 단위까지도 계획이 가능합니다. (물론 최적성과의 Trade-off 결과...)
이렇게 수천대의 로봇까지 제어할수있게된 결과 다양한 시스템에도 활용할 수 있게 되었는데요.
UAV교통관리나 철도, 공항 등 다양한 업계에서 사용되게 되었습니다.
그중에서도 가장 큰 주목을 받는 분야는 바로 자동화된 창고에서 대규모 모바일로봇을 운용하는 것이죠.
아무래도 니즈가 크기 때문이겠죠?
지금까지 개발된 모델들은 로봇 동역학과 불확실성에 대해서 너무 단순화된 가정을 사용하기때문에 실제 세계에서 적용되기가 힘듭니다. 그래서 비단위 이동시간이나 운동학적 제약, 시간 불확실성 등 더 복잡하지만 현실에 가까운 연구들이 진행되고있죠.
예시를 들어 쉽게 풀어쓰면, MAPF의 대부분 알고리즘은 그리드 기반으로, 로봇은 한칸씩 움직인다고 가정합니다. 타임스텝 한칸마다 로봇도 한칸씩 슉 순간이동하죠. 이런것들은 현실 초분시 단위의 realtime과도 호환이 힘들고, 로봇의 운동학적 제약 (가속도, 속도 등)도 없을 뿐더러 현실에서는 반드시 발생하는 오차들도 없잖아요. 이런것들이 문제가된다~ 이런 내용입니다.
그래서 이 논문에서는 ADG와 RHCR 프레임워크를 통합한 RHCRE 프레임워크를 제안합니다.
RHCRE을 통해서 시간과 품질을 trade-off한 다양한 모델들을 비교하고 연구했습니다.
Modeling and Solving MAPF
우선 현실과 시뮬레이션의 간극을 해결하기 위해서는 기존 MAPF알고리즘들과 로봇 모델에 대해서 알아야겠죠.
이 섹션에서는 3가지 MAPF알고리즘과 4가지 에이전트 종류를 소개합니다.
MAPF Algorithms
- Astar-based
- CBS-based
- Prioritized Algorithms
- Prioritized planning (Erdmannand Lozano-Perez 1987) 얘는 어딜가도 항상 비교대상으로 나오는..
Agent Models
- Standard-MAPF
- 에이전트는 xy위치와 시간값을 가집니다.
- (본 논문에서는 ECBS와 PP로 해결)
- MAPF with Rotation
- 에이전트는 xy위치와 각도, 시간값을 가집니다.
- 회전 또한 이동과 마찬가지로 1개의 타임스텝을 가져갑니다.
- MAPF with Time Uncertainty
- 기존 에이전트 정보에 지연값이 추가됩니다.
- 노드와 에지의 점유 유무를 파악할 때, 지연값을 포함하여 계산합니다.
- Continuous-Time MAPF
- 시간값이 이산에서 연속성으로 변경됩니다
위와 같은 에이전트 모델이나 MAPF가 사용되고있다~ 이런 느낌으로 정리
From MAPF to Automated Warehousing
본 논문의 목적은 현실에서 MAPF의 운용을 높이는것이였죠. 저자는 위에서 소개한 다양한 MAPF방식과 에이전트 뿐만 아니라, 기존의 MAPF 명령 방식도 현실과 괴리가 있다고 지적합니다. 기존의 MAPF는 오프라인 문제로, 모든 로봇이 멈춰있는 상태에서 목적지가 할당되고, 경로계획이 끝나면 로봇이 출발합니다. 다른 논문에서는 One-Shot방식이라고도 불리더군요. 하지만 현실에서는 이렇게 다 멈춰있다가 요이땅 하고 시작하진 않죠... 운용중에 새로운 명령이 생기고, 로봇이 들어오고나가고....
1. Standard MAPF를 어떻게 LifeLong MAPF로 변환할것인가?
2. 실시간 로봇 운용을 위해서는 어떻게 MAPF의 계산을 극복할것인가?
그래서 저자는 위 두 질문에 대답하기 위해서 RHCR과 ADG를 결합한 RHCRE프레임워크를 제안합니다.
RHCRE프레임워크는 두 프레임워크의 장점을 이어받아 실시간으로 lifelong MAPF문제를 효율적으로 해결합니다.
그러면.. 이제 ADG와 RHCR를 설명해야겠죠.
ADG는 로봇의 행동을 전수조사한 후, 로봇의 행동간에 의존성을 추가하여 계획했던 순서를 지킬수있도록 명령을 내려주는 기법입니다. 로봇들의 행동 사이에서 의존성이 추가가되면, 로봇이 계획대로 정확하게 움직이지 않더라도 명령은 의존성 그래프의 순서대로 로봇에게 전달되서 명령순서 문제가 해결됩니다.
말그대로 싱크 맞춰주는거라고 생각하시면 될것같아요. 멀티쓰레드에서 먼저끝났다고 바로 다음꺼 안하고, 의존성 걸려있는 다른 쓰레드 기다려주듯이..
RHCR은 윈도잉 기법을 통해 일정 반경내의 충돌만 검사하는 방법론입니다. 즉, 기존 CBS와같은 알고리즘들은 최적성을 위해 로봇의 전 경로에 대해서 충돌을 감지하는데, RHCR은 현재 로봇 주변에서만 검사하고 나머진 그냥 휴리스틱으로 경로계획해버립니다. 그러니까 연산량이 급격하게 감소해서, 실시간으로 MAPF를 수행할 수 있게됩니다.
위 두가지 프레임워크의 장점이 어떻게 합쳐질지 짐작이 가시나요?
ADG -> 오차 발생해도 명령 안꼬이게 해줌
RHCR -> 연산량을 감소시켜서 실시간으로 lifelong MAPF해결 가능
요렇게 합쳐집니다.
ADG는 서술한대로 로봇의 행동을 전수조사하기때문에 O(n^2)의 시간복잡도를 가져서 대규모로 적용시키기가 힘든데.. RHCR의 윈도우 개념을 가져와서 로봇 일정반경 이내에서만 수행하게 한거죠.
이제부터 아래는 실험 잘했고, 결과 좋았고~ 내용입니다.
절대 귀찮아서 더 안쓰는건 아니고...
참고로 RHCRE는 스탠다드와 회전 에이전트 모델만을 지원합니다.즉, 이산화된 시간간격을 가지며, 시간불확실성은 가지지 않죠. 최소한의 수정으로 바꿀수있다곤 하긴하는데... 해당 논문에서 실험되지 않은것이 살짝 아쉬운 부분이네요. 기존 모델과 프레임워크가 현실과 괴리가 있는 부분을 해결하는 논문인데, 에이전트와 시간이 현실과 거리가 있는 모델을 사용했습니다.