Conflict-Based Search with Optimal Task Assignment - 작업 배정과 경로 계획을 동시에 한다면?

안녕하세요. 오늘은 작업 배정과 다중 에이전트 경로 계획을 합쳐서 효율성을 높인 방법을 제안한 Conflict-Based Search with Optimal Task Assignment 논문을 공부해보도록 하겠습니다.

• HÖNIG, Wolfgang, et al. Conflict-based search with optimal task assignment. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems. 2018.

 
일반적으로 작업 배정과 다중 에이전트 경로 계획은 다른 단계에서 이뤄졌는데요.
이렇게 문제를 분해한 결과, Lifelong MAPF 문제를 빠르게 풀 수 있지만 어쩌면 있을지도 모르는 최적의 작업 배정을 놓칠 수도 있습니다.
 
이 논문은 이 점을 해소하기 위해서 작업 배정과 경로 계획을 동시에 진행했는데요.
어떻게 한 것인지 같이 공부해볼까요?

---

1. Introduction

기존에 진행되던 MAPF 연구들은 주로 Labeled MAPF였습니다.

• agent들이 해결해야 할 task가 이미 정해져 있는 MAPF 문제를 Labeled MAPF 문제라고 합니다.

 
Labeled MAPF 문제는 CBS, M*, ECBS 등 다양한 방법으로 문제를 해결할 수 있습니다.

• Sharon, Guni, et al. "Conflict-based search for optimal multi-agent pathfinding." Artificial Intelligence 219 (2015): 40-66.
• WAGNER, Glenn; CHOSET, Howie. M*: A complete multirobot path planning algorithm with performance bounds. In: 2011 IEEE/RSJ international conference on intelligent robots and systems. IEEE, 2011. p. 3260-3267.
• BARER, Max, et al. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem. In: Proceedings of the International Symposium on Combinatorial Search. 2014. p. 19-27.

 
그러면 agent들이 해결해야 할 task가 정해져 있지 않은 경우는 어떻게 해야 할까요? 이러한 문제를 Target Assignment and Path Finding(TAPF)문제라고 하는데 TAPF 문제는 주어진 agent들에게 주어진 task들을 적절히 나누는 문제입니다.
 
TAPF 문제를 해결하는 통상적인 방법은 task assignment + path finding 2단계로 나눠서 해결하는 것입니다.

• auction, token 기반의 decentralized 해결 방안들과 M* 알고리즘 등이 있습니다.

하지만 논문에서는 강하게 결합되어 있는 두 단계를 한번에 해결함으로써 보다 많은 agent들을 처리하면서 효율적인 경로를 계획하는 방법을 제안합니다.

• MA, Hang, et al. Lifelong multi-agent path finding for online pickup and delivery tasks. arXiv preprint arXiv:1705.10868, 2017.

 

2. 논문에서 제안한 방법

논문에서는 CBS-TA라고 명명한 이 알고리즘은 CBS 프레임워크에 작업 배정 로직 실행 부분을 추가한 것이며, ECBS로 확장할 수 있어서 보다 많은 agent들을 처리하면서 효율적인 경로를 계획할 수 있다고 주장했습니다.
 
CBS 프레임워크에 작업 배정 로직을 추가한 방식은 다음과 같습니다.

1. 맨 처음 root node를 생성할 때, 선택한 작업 배정 알고리즘을 이용하여 agent들에게 작업을 배정합니다.
2. high level 노드들의 탐색을 진행할 때에는 부모 노드의 작업 배정을 그대로 가져간다.
3. OPEN 리스트에서 선택된 노드가 root node일 경우, 작업 배정이 다른 root node를 추가하여 OPEN 리스트에 넣습니다.

위의 설명을 보시면 굵은 글씨로 작성된 키워드들이 무슨 의미인지 궁금하셨을 것 같은데 부연 설명드리겠습니다.
 
1. 선택한 작업 배정 알고리즘
CBS-TA는 작업 배정 알고리즘을 강제하지 않습니다.
CBS라는 프레임워크에 작업 배정 로직 실행 부분을 추가한 것이기 때문에 사용하고 싶은 작업 배정 알고리즘을 사용할 수 있습니다.

• 논문에서 헝가리안 알고리즘을 예시로 든 것으로 보아 헝가리안 알고리즘을 사용한 것 같습니다!

 
2. 작업 배정이 다른
작업 배정이 다르다고 했는데 같은 작업 배정 알고리즘을 사용했다면 같은 값이 나와야 하지 않을까요? 어떻게 다른 결과를 만들 수 있었을까요?
 
CBS-TA에서는 agent와 작업 간의 배정 가능 여부를 임의로 설정하는 방식으로 다른 결과가 도출될 수 있도록 하였습니다.
예를 들어서, 원래 배정된 작업이 [(로봇1, 작업1), (로봇2, 작업2)] 이었다면 "로봇1은 작업1에 배정될 수 없어" 라는 조건을 추가하여 다시 작업 배정 알고리즘을 실행하는 것이죠.
 

3. 실험

실험은 크게 unlabeled MAPF, TAPF 2가지로 진행되었습니다.
 

3.1. unlabeled MAPF

실험은 작은 환경(8x8 격자 지도, 장애물 20%, agent 수: 5, 9, 19), 큰 환경(32x32 격자 지도, 장애물 20% agent 수: 40, 70, 100)에서 진행되었습니다.
TA + ECBS, ECBS-TA(CBS-TA 스타일), ECBS-TA(CBS Min Root) 들의 실행 시간과 SICs를 비교했습니다.
 
결과를 보면 알 수 있지만 작은 환경에서는 ECBS-TA가 성능이 좋지만 큰 환경에서는 ECBS-TA의 성능이 안 좋은 것을 볼 수 있습니다. agent 수가 많아지면서 가능한 작업 배정의 경우의 수가 많아져서 시간이 오래 걸리게 되는 것입니다.
 
큰 환경에서는 ECBS-TA(MinRoot)를 사용하거나, TA + ECBS를 사용하는 것이 효율적이라는 결과입니다.

HÖNIG, Wolfgang, et al. Conflict-based search with optimal task assignment. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems. 2018. Table1

 

3.2. TAPF

실험은 작은 환경(8x8 격자 지도, 장애물 20%), 큰 환경(32x32 격자 지도, 장애물 20%)에서 진행되었습니다.
agent 수를 늘려보면서, group size를 늘려가면서 CBM과 ECBS-TA의 작업 배정의 성능 차이를 비교했습니다.
 
두 환경 모두 ECBS-TA가 CBM보다 실행 시간이 빠르고, SICs가 더 낮은 결과가 나왔습니다.

HÖNIG, Wolfgang, et al. Conflict-based search with optimal task assignment. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems. 2018. Figure5

 

HÖNIG, Wolfgang, et al. Conflict-based search with optimal task assignment. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems. 2018. Figure6

4. 리뷰

Labeled MAPF

Labeled MAPF는 single shot MAPF와 똑같이 현실 세계에서 적용하기 어렵다는 문제가 있는 것 같습니다.
중소 규모의 물류센터의 경우, Warehouse Management System(WMS)를 직접 만들지 않고 외부 업체의 솔루션을 이용하는 경우가 많습니다.
 
자동화 시스템의 성숙도가 높지 않다면 WMS와 로봇 관제 시스템이 데이터를 충분히 잘 주고 받지 못하여 TAPF 문제를 해결해야 할 것 입니다.
반대로 자동화 시스템의 성숙도가 높아서 Labeled MAPF 문제로 바꿀 수 있다면 훨씬 문제를 쉽게 만들 수 있을 것 입니다.
알고리즘의 성능도 중요하지만 시스템이 이를 뒷받침 할 수 있는지도 고려해야 합니다.
 

CBS 프레임워크를 사용하여 작업 배정을 할 수 있다는 장점

CBS-TA는 CBS 프레임워크를 사용하기 때문에 조금 더 특수한 상황에 특화된 CBS variant들을 적용할 수 있다는 장점이 있습니다.
그리고 배정된 작업들은 Sum of Individual path Costs(SICs)라는 비용 함수가 고려되었다는 장점이 있습니다.
 
작업 배정과 경로 계획을 따로 진행하면 경로가 비효율적으로 계획될 수 있는데 이 점이 보완될 수 있다고 생각합니다.
 

규모에 따른 알고리즘 선택

실험 결과를 보면 CBS-TA는 작은 규모의 환경에 적합합니다.
제가 중소 규모의 물류센터를 많이 언급하는데 이런 환경에서는 CBS-TA가 효율적일 수 있다는 것이 흥미롭습니다.
 
시스템을 어떻게 설계해야 상황에 따라서 CBS-TA, TA+CBS 중 원하는 알고리즘을 선택할 수 있을까요?
TA + CBS-TA 같은 구조로 만들어야 할까요? ㄷㄷ
 

Token Passing 알고리즘과 비교했다면 어땠을까?

decentralized 알고리즘인 Token Passing과 성능을 비교했다면 어땠을까 싶습니다.
Token Passing 알고리즘의 실험 결과를 보면 작업 배정에 걸리는 시간도 짧아서 큰 환경에서 같이 비교하면 좋았을 것 같습니다.

MA, Hang, et al. Lifelong multi-agent path finding for online pickup and delivery tasks.  arXiv preprint arXiv:1705.10868 , 2017. Table 1

---

CBS-TA는 어떠셨나요?
저는 항상 작업 배정과 경로 계획을 따로 풀려고만 했었기에
CBS 내부적으로 작업 배정을 녹이는 방법은 생각해보지 못했습니다.
 
Target Assignment Path Finding(TAPF), Lifelong MAPF 등 해결해야 할 문제가 많습니다...ㅎㅎ
하나씩 하나씩 공부해봐야겠습니다!