우리나라 대기업 LG전자에서 MAPF를 연구한다면 어떨까요? - MAPF 제대로 연구하려면 로봇이랑 물류센터는 있어야 한다니깐요!

안녕하세요. 오늘은 무려 LG 전자에서 진행된 MAPF 연구를 공부해보려고 합니다.

• 신동철, et al. 다중에이전트 경로탐색 (MAPF) 기반의 실내배송로봇 군집제어 구현. 로봇학회 논문지, 2022, 17.4: 407-416.

로봇도 있고, 물류센터도 있으니 MAPF 연구를 진행하는데 필요한 핵심적인 것들이 전부 갖춰진 환경인 것 같더라고요...!
 
같이 한번 봐볼까요?

---

1. Introduction

1.1. 로봇의 실제 동작과 경로 계획 사이의 갭을 줄이기 위해 노력한 연구들

기존 MAPF 연구들은 이론상 충돌 없는 경로를 계획할 수는 있지만 실제 로봇이 이를 정확하게 실행할 수 없다는 문제가 있습니다.
이를 보완하기 위해 로봇의 동역학적인 모델을 도입하여 경로를 보다 정확하게 계획하는 연구들이 있었지만 이들 역시 데드락 발생 가능성이 남아 있습니다.

• W. Hönig, T. K. Kumar, L. Cohen, H. Ma, H. Xu, N. Ayanian, and S. Koenig, “Multi-agent path finding with kinematic constraints,” Twenty-Sixth International Conference on Automated Planning and Scheduling, vol. 26, 2016, DOI: 10.1609/icaps. v26i1.13796
• H. Ma, S. Koenig, N. Ayanian, L. Cohen, W. Hönig, T. K. S. Kumar, T. Uras, H. Xu, C. Tovey, and G. Sharon, “Overview: Generalizations of multi-agent path finding to real-world scenarios,” Artificial Intelligence, 2016, DOI: 10.48550/arXiv.1702.05515.

1.2. 그래프 생성 방법

기존 MAPF 연구들은 격자 지도를 사용하거나 토폴로지 형태의 그래프로 공간을 구성합니다.
 
격자 지도를 사용하는 경우에는 공간을 최대한 활용하면서 로봇들의 경로를 계획할 수 있지만 경로 계획에 시간이 오래 걸려서 경로 재계획이 잦은 lifelong MAPF 문제를 풀 때 어려움이 존재합니다.
토폴로지 형태의 그래프를 사용하면 경로 계획에 걸리는 시간은 줄어들지만 공간을 일부 낭비한다는 단점이 있습니다.
 
1.1과 1.2에서 설명되었던 기존 연구들의 한계점들을 해결하기 위해 논문에서는 프레임워크를 소개합니다.
그리고 실험이 진행되었던 물류센터에 적합한 그래프 작성 방법도 소개합니다.

2. 논문에서 제안한 방법

2.1. 프레임워크

논문에서 제안하는 프레임워크는 다음과 같습니다.

1. 로봇들의 목적지 선정
   • 이 부분은 제가 이해하지 못했습니다. 로봇들의 목적지가 바뀐다는 의미인 것인지, 경유지를 선정하는 것인지, 왜 필요한 것인지 이해하지 못했습니다.
2. AGENT & OBSTACLE 분류
   • 경로를 다시 계획해야 하는 로봇은 AGENT, 경로를 그대로 유지하거나 가만히 있어야 하는 로봇은 OBSTACLE로 분류합니다.
3. AGENT의 우선 순위 계산
   • Priority Based 경로 계획 알고리즘을 사용하기 때문에 우선 순위를 어떻게 부여하느냐가 문제 해결에 큰 영향을 끼칩니다.
   • 논문에서는 막다른 골목에서 빠져나오는 AGENT에 최우선 순위를 부여하였고, 그 다음으로는 현재 목적지까지의 거리가 가까운 순으로 우선 순위를 부여했습니다.
4. Priority Based 경로 계획
5. 경로 분석
   • 계획된 경로를 분석하여 로봇이 수행할 수 있는 단위로 잘라서 전달합니다.
     • 예시) 계획된 경로에 유턴, N초 대기 등과 같은 로봇이 지원하지 않는 동작이 있다면 이전 경로까지 자릅니다.
   • 만약 전달할 경로가 너무 짧을 경우, 로봇에게 전달하지 않습니다.
6. 경로 전송
7. 이벤트 발생 시 다시 1 시작
   • 다시 1을 시작하는 이벤트들은 다음과 같습니다.
   • 로봇 간 충돌 예측, 특정 로봇의 현재 목적지 도착, 로봇 목적지의 추가, 경로 계획 시간 초과

 
정리된 내용을 보면 간단하지만 각 단계에서 정책이 정해지기까지 어떤 문제들이 있었고, 고민을 하셨을지...🙏
 

2.2. 한 줄 격자 형태의 그래프

논문에서는 격자 지도와 토폴로지 형태의 그래프의 장점을 가져가기 위해서 한 줄 격자 형태의 그래프를 제안합니다.
 
한 줄 격자 형태로 그래프를 구성하면 계산량도 줄일 수 있고, 로봇의 반경 혹은 로봇의 자율 주행으로 인한 충돌을 배제할 수 있다는 장점이 있습니다.
하지만 로봇이 많아질수록 양보하는데 시간이 오래 걸린다는 단점이 있지만 로봇이 짐을 옮기고 오랜 시간 대기해야 한다는 물류센터의 특징 때문에 운영에 문제가 없다고 합니다.

3. 실험

논문에서는 1) 시뮬레이션을 이용하여 제안된 프레임워크의 경로재계획이 있을 때와 없을 때의 성능을 비교했고, 2) 실제 AMR 로봇을 이용해서 실제 물류센터에서 피킹 작업 효율을 측정했습니다.

• 진짜 물류센터에서 실험을 진행할 수 있는 것이 LG 전자의 힘이 아닐까 싶습니다...!

실험 결과는 다음과 같습니다.
 

3.1. 시뮬레이션을 이용한 실험

10대의 가상 로봇들로 실험을 진행하였습니다.
실험에 사용된 태스크 셋은  다음과 같습니다. 순서 없이 가장 멀리 떨어져 있는 피킹 장소를 들렸다가 하역 장소를 들리는 것을 10번 반복하는 실험을 3번 진행했습니다.
 
경로재계획이 있을 때는 나중에 출발한 로봇이 경로를 양보하느라 주어진 작업을 다 못 끝내기도 했지만 전반적으로 경로재계획이 없을 때보다 성능이 좋았습니다.

신동철, et al. 다중에이전트 경로탐색 (MAPF) 기반의 실내배송로봇 군집제어 구현. 로봇학회 논문지, 2022, 17.4: 407-416. Table 2

3.2. 실제 AMR 로봇을 이용한 실험

이 논문에서는 작업 효율을 측정하기 위해서 실제 물류센터에서 각각의 로봇이 이동하는 거리, 소요된 시간, POI 이동 횟수를 측정했습니다.
 
결과로는 일일 누적 평균 44.8km를 이동했으며 전체 7시간 작업에서 1.85시간을 이동에 소요했고, 평균 290번 POI를 이동했습니다.
결과를 바탕으로 로봇 10대 운영을 통해서 일일 작업 시간의 25%에 해당하는 부분을 로봇으로 대체할 수 있다고 주장합니다.

신동철, et al. 다중에이전트 경로탐색 (MAPF) 기반의 실내배송로봇 군집제어 구현. 로봇학회 논문지, 2022, 17.4: 407-416. Fig 9

4. 리뷰

작업 효율에 대한 고찰

실험 결과에서 로봇 10대 운영을 통해서 일일 작업 시간의 25%에 해당하는 부분을 로봇으로 대체할 수 있다고 주장되었는데 로봇을 사용하기 전과 후의 작업량이 비교되었으면 더욱 좋았을 것 같습니다.
 
"로봇의 이동 시간"을 "감소한 작업자의 이동 시간" 해석할 수도 있지만 "비효율적으로 계획된 경로"라고 해석할 수도 있기 때문입니다.
계획된 경로가 효율적이었는지 비효율적이었는지를 판단하기 위해서는 결국 작업량이 중요합니다.
 
동일한 적치 전략을 사용한다는 가정하에 로봇을 사용하기 전의 작업량이 baseline으로, 로봇을 사용했을 때의 작업량이 얼마나 개선되었는지 혹은 필요한 작업자의 수가 얼마나 줄었는지 등의 비교가 이뤄졌다면 어땠을까 싶습니다.
 

액션 간 의존성 분석이 없는 점

논문에서 제안된 프레임워크는 로봇 간의 충돌이 예측될 때 경로를 재계획합니다.
이것이 의미하는 바는 collision free 경로를 계획했지만 이를 실행할 때 의존성을 분석하지 않고 로봇에게 경로를 전달한다는 것입니다.
 
만약 네트워크 통신이 불안정한 구간이 있거나 로봇의 네트워크 모듈에 문제가 생긴다면 경로가 재계획 되더라도 로봇 간의 충돌을 막을 수 없는 상황이 발생할 수 있습니다.
아마 예외 상황들을 처리하면서 안정성을 보장하기 위해서 액션 간 의존성을 분석하셨을 것 같은데 어떤 디테일이 숨겨져 있을지 궁금하네요.
 

환경에 따른 그래프 작성 방법

논문에서는 한 줄 격자 형태의 그래프 형태를 제안했는데요.

• 한 줄 격자와 격자 지도를 같이 활용하는 방안을 제시했던 논문 참고: MA, Hang, et al. Overview: Generalizations of multi-agent path finding to real-world scenarios. arXiv preprint arXiv:1702.05515, 2017.

애매하게 좁은 랙 사이 공간에 로봇 2대가 들어가는 것을 허용하지 않고, 한 줄 격자 형태로 만들고 랙 밖에서 대기하도록 만든 것과, 양방향 교차가 가능하도록 T자 형태로 피해줄 수 있는 공간도 추가한 것은 프레임워크의 방향성과 부합하는 해결책이었다고 생각합니다.
 
논문과는 별개로 환경에 맞는 그래프를 작성하는 것은 정말 어려운 작업인 것 같습니다. 그래프가 어떻게 작성되었는지에 따라서 경로 계획에 걸리는 시간, 계획된 경로의 길이가 달라지는데요.
 
문제는 현재 작성된 그래프가 최적인지 알 수 없다는 점에 있습니다. 최적의 그래프를 찾는 방법이 없기에 현장에서 테스트 하는 것 밖에 방법이 없는데요... 그래프 작성에 관한 연구는 어디 없는지 궁금하네요 ㅜ
 

작업 배정 알고리즘이 적용되면 어떨까요?

논문에서 제안된 프레임워크에는 작업 배정 부분이 없는 것 같습니다. 실험에서도 관리자가 직접 로봇별로 POI를 선정했었는데요.
아무래도 LG전자가 물류센터를 운영하고 있기 때문에 WMS를 직접 운영하고 있을 것으로 예상됩니다.
만약 그렇다면 로봇 관제 시스템과 WMS와의 연동이 비교적 수월할 것이기 때문에 작업 배정 알고리즘 적용도 적극적으로 고민할 수 있을 것 같습니다.
 
작업 배정 알고리즘까지 적용되면 효율이 얼마나 좋아질지 궁금하네요 ㅎㅎ

---

이번 논문은 어떠셨나요?
 
저는 영어로 작성된 논문만 보다가 한글로 작성된 것을 보니 이렇게 반가울 수가 없더라고요 ㅎㅎ
그리고 반가운 것과는 별개로 어떤 디테일들이 숨어있을까 상상하면서 읽으니 정말 재밌더라고요!
논문에서 제안되었던 방식의 영감을 얻었던 논문들도 공부할 수 있어서 정말 좋았습니다.
 
물류센터, 라스트 마일 딜리버리 등 국내에서도 로봇을 활용하여 자동화 시스템을 구성하는 사업들이 활발히 진행되고 있습니다.
이에 발맞춰 TAPF, MAPF 연구들도 필요할텐데 더 많은 연구들이 나오면 좋을 것 같습니다 :)