물류센터 환경에서 가장 좋은 MAPF 모델은 뭘까요? - 리서치 논문 리뷰에 약간의 고민들을 곁들여봤습니다.

안녕하세요. 오늘은 리서치 논문인 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.

 

평소에 MAPF 연구를 공부할 때 많이 봤었던 Jiaoyang Li 님의 블로그를 보다가 위의 논문을 찾을 수 있었는데요.

 

진짜 진짜 블로그 둘러보기만 하려고 했는데 MAPF Model, Best, Warehousing 3가지 키워드에 그만 넘기지 못하고 읽게 되었습니다.

 

나름대로 논문 내용을 간단하게 정리해보고, 리뷰를 남겨보겠습니다.

한번 봐보실래요?

 

P.S.

Jiaoyang Li 님의 블로그에는 다른 논문들도 많으니 MAPF 분야를 공부하고 있다면 꼭 블로그를 들러보세요!

• 블로그 링크: https://jiaoyangli.me/

진짜 진짜 연구에 진심이십니다 ㄷㄷ

---

1. Introduction

1.1. 물류센터 환경을 연구하는 이유

혹시 물류센터(Warehouse) 환경을 연구되는 이유에 대해서 생각해본 적이 있으실까요?

MAPF 알고리즘이 적용될 수 있는 분야는 Unmanned Aerial Vehicle Traffic(무인 항공기 교통 제어), Airport Surface Operation(공항 지상조업), railway planning(선로 계획) 등 다양합니다.

 

하지만 물류센터 환경에 집중되는 이유가 뭘까요?

바로 돈, 연구 투자 물류센터 환경이 MAPF 알고리즘들의 일반적인 전제 조건과 유사하기 때문입니다.

• MAPF 알고리즘들의 일반적인 전제 조건은 다음과 같습니다.

1. 모든 로봇은 상, 하, 좌, 우 4방향으로 움직인다.
2. 모든 로봇은 동일한 제어 방식을 가지고 있다.
3. 각각의 로봇은 계속해서 목적지를 할당 받으며, 충돌 없는 경로를 계획해야 한다.
4. 각각의 로봇은 중앙 서버로부터 명령을 받는다.

 

1.2. MAPF 선행 연구

그러면 이런 전제 조건들을 가지고 어떤 알고리즘들이 연구되었을까요?

크게 3가지 부류가 소개되었는데 정리하면 다음과 같습니다.

 

1. 경로 계획에 충실한 알고리즘들

• A* 기반 알고리즘
• CBS
  • Sharon, G.; Stern, R.; Felner, A.; and Sturtevant, N. R. 2012. Conflict-Based Search For Optimal Multi-Agent Path Finding. In AAAI, 563–569
• Prioritized 알고리즘
  • Silver, D. 2005. Cooperative Pathfinding. In AIIDE, 117–122.

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

• 로봇의 회전을 고려한 CBS with rotation
• 로봇이 계획된 경로를 시간 내에 완수하지 못할 것을 고려한 k-robustness CBS
  • Atzmon, D.; Stern, R.; Felner, A.; Wagner, G.; Bartak, R.; and ´ Zhou, N. 2020b. Robust Multi-Agent Path Finding and Executing. Journal of Artificial Intelligence Research, 67: 549–579.
• 유닛 타임 대신 continuous한 값을 고려한 Continuos CBS
  • Andreychuk, A.; Yakovlev, K.; Boyarski, E.; and Stern, R. 2021. Improving Continuous-Time Conflict Based Search. In AAAI, 11220–11227
• 로봇들의 경로 간 의존성을 고려한 Action Dependency Graph(ADG)
  • HÖNIG, Wolfgang, et al. Persistent and robust execution of MAPF schedules in warehouses. IEEE Robotics and Automation Letters, 2019, 4.2: 1125-1131.

3. lifelong MAPF 연구들

• Token 기반의 작업 배정
  • MA, Hang, et al. Lifelong multi-agent path finding for online pickup and delivery tasks. arXiv preprint arXiv:1705.10868, 2017.
• window 기반의 경로 계획인 RHCR
  • LI, Jiaoyang, et al. Lifelong multi-agent path finding in large-scale warehouses. In: Proceedings of the AAAI Conference on Artificial Intelligence. 2021. p. 11272-11281.

실제 로봇을 운용할 때에는 센서, 모터, 네트워크 환경 등의 불안정성 때문에 계획된 경로대로 움직이지 않는 경우가 대다수입니다.

그래서 1처럼 경로 계획에만 충실한 알고리즘들을 현장에 바로 적용할 수 없어 2, 3의 후속 연구들이 활발하게 진행되고 있습니다.

 

2. 논문에서 새롭게 제안된 개념

논문에서는 1.2. MAPF 선행 연구에서 소개된 RHCR과 ADG를 합쳐서 RHCRE(Rolliing Horizon Collision Resolution and Execution)이라는 프레임워크를 제안합니다.

 

그리고 RHCRE를 이용하여 다음 MAPF 알고리즘들과 설정 별 성능을 비교하는 실험을 진행했습니다.

• 성능을 비교한 MAPF 알고리즘들
  • ECBS-TA
  • Prioritized Planning(PP)
  • Prioritized Planning with Continuous Time(Continuous PP)
• 성능을 비교한 설정들
  • window size
  • k-robustness
  • rotation 고려 여부

3. 실험

논문에서 실험을 진행한 환경은 다음과 같습니다.

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. Figure2

 

Persistent and robust execution of MAPF schedules in warehouses 논문에서 사용된 실험 환경을 똑같이 사용했더라고요.

• HÖNIG, Wolfgang, et al. Persistent and robust execution of MAPF schedules in warehouses. IEEE Robotics and Automation Letters, 2019, 4.2: 1125-1131.

 

결과는 다음과 같았습니다.

 

k = 0, k = 1로 구분되는 것이 k-robustness를 다르게 설정하여 실험을 진행한 것입니다.

with rot 붙어있는 결과들은 회전을 고려하여 경로를 계획한 것, 붙어있지 않은 것은 회전을 고려하지 않고 경로를 계획한 것입니다.

w는 window size를 뜻합니다.

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. Table 1, Table 2, Table 3

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. Table 4

결과에 대해서는 다음과 같은 의견을 남겼습니다.

1. windowing과 로봇의 회전 시간을 고려하는 것은 성능을 개선시키는데 도움을 준다.
2. k-robustness를 사용하면 특정 경우에 성능을 향상시킬 수 있다.
3. robot dynamic을 고려하여 액션의 실행 시간을 정확히 고려할수록 성능이 좋아진다.

 

4. 리뷰 + 고민거리

RHCRE 프레임워크

기존의 연구들을 합쳐서 새로운 실행 프레임워크를 제안해준 것이 정말 인상깊었습니다.

 

MAPF 알고리즘들을 공부하면서 유용하다고 느꼈던 연구들은 대체로 프레임워크인 경우가 많았습니다.

• CBS, MACBS, RHCR, ADG 등

프레임워크는 시스템의 구조는 그대로 유지하면서 환경에 적합한 연구들을 적용해볼 수 있다는 장점이 있는데요.

 

완전히 새로운 내용은 아니지만 lifelong MAPF에서 정책적인 부분을 잘 구분하여 프레임워크를 제안해준 것이 영감을 준다고 생각합니다.

 

실험 결과에 대한 해석 부분

이 부분은 많이 아쉬웠던 것 같습니다.

RHCRE 프레임워크를 제안한 것에서 힘을 다 쓰신 것인지 혹은 실험 단계에서 힘을 다 쓰신 것인지 결과 해석이 아쉽더라고요 ㅜ

 

조금 더 많은 시나리오들에 대해서 실험이 진행되었다면 조금 더 의미 있는 결과 해석이 나올 수 있지 않았을까 싶습니다.

 

레이어의 중요성

위의 RHCRE 프레임워크 부분과 연결되는데 lifelong MAPF 문제를 해결하기 위해서는 레이어를 잘 나누는 것이 정말 중요하다고 느꼈습니다.

 

연구 단계에서는 연구자들이 실험 환경을 구성하고, 실험을 진행하면 끝납니다.

하지만 이를 이용하여 제품을 개발하기 위해서는 알고리즘 연구에서 끝나는 것이 아니라 여러 공학적인 문제들도 해결해야 합니다.

 

예를 들어 MAPF 문제를 푸는 서비스의 무중단배포를 지원하기 위해서는 어떻게 해야 할까요?

그래프 크기, 로봇 수, 서버 성능 등에 따라서 stateless 한 방법, stateful 한 방법, 하이브리드 방법 등 여러 해결책이 존재할 수 있습니다.

 

이런 공학적인 문제와 연구를 병행하는 것은 제품을 개발하고 운영하는 측면에서 매우 리스크가 높다고 생각합니다.

연구와 개발을 적절히 나눌 수 있어야 장기적으로 훌륭한 알고리즘과 훌륭한 제품이 나올 수 있을 것입니다.

 

어떻게 나눠야 잘 나눈 걸까요? 이건 계속 고민해봐야 할 것 같습니다.

---

이번 논문은 어떠셨나요?

MAPF 알고리즘들을 공부하던 중에 리서치 논문을 보니 감회가 새롭네요!

아는만큼 보인다고들 하는데 더욱 열심히 공부해야 할 것 같습니다 ㅜ

 

설명이 부족한 부분이나 잘못된 부분 알려주시면 최대한 보완하도록 하겠습니다 :)