Task and Path Planning For Multi Agent Pickup and Delivery - 작업 배정, 경로 계획을 분리한다면 이렇게!

안녕하세요. 오늘은 Offline MAPD 문제에 대해서 연구한 Task and Path Planning For Multi Agent Pickup and Delivery 논문을 공부해보도록 하겠습니다.

• LIU, Minghua, et al. Task and path planning for multi-agent pickup and delivery. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2019.

MAPF에 관한 연구만 찾아봤어서 MAPD가 무엇인지 생소하실텐데요. Offline MAPD에 대해서 간단하게 알아보겠습니다!
 
MAPD란 Multi Agent Pickup and Delivery의 약자로 다중 에이전트들을 상대로 최적의 작업 배정을 찾는 문제입니다.
다만, 하나의 task가 하나의 goal만 있는 것이 아니라 pickup location, delivery location 2개의 goal을 가진다는 차이점이 있습니다.
 
앞에 Offline이 붙어 있으면 배정해야 할 task들의 모든 정보를 전부 알고 있는 상태에서 문제를 푸는 것이고,
반대로 Online이 붙어 있으면 task들의 모든 정보를 알지 못한 상태에서 문제를 푸는 것입니다.
 
즉, Offline MAPD라고 하면 배정해야 할 task들의 모든 정보를 알고 있는 상태에서 최적의 작업 배정을 찾는 문제입니다.
 
이제 논문에서 어떻게 Offline MAPD 문제를 해결했는지 같이 공부해볼까요?

---

1. Introduction

Offline MAPD의 수요

논문에서는 Offline MAPD 문제가 단순히 이론적인 접근이 아닌 현실 세상에서도 수요가 많다는 점을 보여줍니다.

• 물류 센터 혹은 공장에서는 물건의 포장 작업 시각이 미리 계획되어 있음
• 공항에서 비행기의 이륙, 착륙 시간을 미리 알고 있는 상태에서 활주로를 정리함

MAPD 관련 연구들

MAPD 문제는 작업 배정, 경로 계획 두 부분으로 나눠서 문제를 바라볼 수 있는데요.

• 혹시 작업 배정, 경로 계획 두 부분을 한번에 푸는 방법이 궁금하시다면 Conflict-Based Search with Optimal Task Assignment 이 도움이 될 것 같습니다!

작업 배정 쪽으로 연관 있는 것은 Traveling Salesman Problem(TSP), Vehicle Routing Problem(VRP) 문제들이 있습니다만 MAPD의 작업 배정과 100% 일치하지는 않습니다.
관련 연구 링크

• T. Bektas. 2006. The Multiple Traveling Salesman Problem: an Overview of Formulations and Solution Procedures. Omega 34, 3 (2006), 209–219.
• E. Osaba, F. Diaz, E. Onieva, P. López-García, R. Carballedo, and A. Perallos. 2015. A Parallel Meta-Heuristic for Solving a Multiple Asymmetric Traveling Salesman Problem with Simulateneous Pickup and Delivery Modeling Demand Responsive Transport Problems. In International Conference on Hybrid Artificial Intelligence Systems. Springer, 557–567.
• A. Stentz, M B. Dias, R. M. Zlot, and N. Kalra. 2004. Market-Based Approaches for Coordination of Multi-Robot Teams at Different Granularities of Interaction. In International Conference on Robotics and Remote Systems for Hazardous Environments
• S. Yoon and J. Kim. 2017. Efficient Multi-Agent Task Allocation for Collaborative Route Planning with Multiple Unmanned Vehicles. IFAC-PapersOnLine 50, 1 (2017), 3580–3585.

경로 계획 쪽으로는 연관 있는 것은 MAPF, Anonymous MAPF(AMAPF) 문제들이 있습니다.
관련 연구 링크

• M. Goldenberg, A. Felner, R. Stern, G. Sharon, N. R. Sturtevant, R. C. Holte, and J. Schaeffer. 2014. Enhanced Partial Expansion A*. Journal of Artificial Intelligence Research 50 (2014), 141–187.
• R. Luna and K. E. Bekris. 2011. Push and Swap: Fast Cooperative Path-Finding with Completeness Guarantees. In IJCAI. 294–300.
• G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant. 2015. Conflict-Based Search for Optimal Multi-Agent Pathfinding. Artificial Intelligence 219 (2015), 40–66.
• T. S. Standley. 2010. Finding Optimal Solutions to Cooperative Pathfinding Problems. In AAAI. 173–178
• N. R. Sturtevant and M. Buro. 2006. Improving Collaborative Pathfinding Using Map Abstraction. In AIIDE. 80–85.
• G. Wagner and H. Choset. 2015. Subdimensional Expansion for Multirobot Path Planning. Artificial Intelligence 219 (2015), 1–24.
• K. Wang and A. Botea. 2011. MAPP: A Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees. Journal of Artificial Intelligence Research 42 (2011), 55–90

• AMAPF는 Conflict-Based Search with Optimal Task Assignment 에서 설명되었던 Labeled MAPF의 반대 의미로 task를 수행할 agent들이 정해지지 않은 MAPF 문제입니다.

솔루션 부분에서 자세히 설명되지만 논문에서는 MAPD 문제를 MAPF 문제와 AMAPF 문제로 분해하여 해결합니다.

이제 논문에서 제안하는 방법들을 자세히 살펴보도록 하겠습니다!

 

2. 논문에서 제안한 방법

논문에서는 TA-Prioritized, TA-Hybrid 2가지 방법을 제안합니다.

2가지 방법 모두 TSP solver를 이용해서 최적의 작업 시퀀스를 찾는다는 공통점이 있지만 작업을 수행하면서 어떻게 경로 계획을 하는지 차이점이 있습니다.

 

TA-Prioritized

TA-Prioritized는 Prioritzed Planning을 이용해서 경로를 계획합니다.

Prioritized Planning이라면 우선 순위를 정해야 하는데 어떻게 정할까요? TA-Prioritized에서는 각 agent들의 남은 작업 수행 시간이 큰 순서대로 우선 순위를 정합니다.

 

만약 다음과 같이 작업이 배정된 경우라면 다음 표와 같이 경로가 계획될 것 입니다.

• 작업을 배정 받지 못한 agent들이 모두 작업을 배정 받을 때까지 진행합니다.
•  

{
    a1 : [(t1, p1, 10, d1, 10), (t2, p2, 9, d2, 9)],
    a2 : [(t3, p3, 10, d3, 9), (t4, p4, 9, d4, 8)],
    a3 : [(t5, p5, 10, d5, 8), (t6, p6, 9, d6, 7)]
}

	a1	a2	a3	경로 계획 결과
남은 작업 수행 시간 1	38	36	34	a1의 p1 경로 계획
남은 작업 수행 시간 2	28	36	34	a2의 p3 경로 계획
남은 작업 수행 시간 3	28	26	34	a3의 p5 경로 계획

 

이렇게 경로가 잘 계획되면 문제가 없지만 만약에 a1과 a2가 a3의 길을 막아서 경로를 계획하지 못하면 어떻게 해야 할까요?

 

논문에서는 reserving dummy path라는 테크닉을 이용해서 문제를 해소합니다.

a2의 p3까지의 경로를 계획할 때, a1이 p1에 멈춰 있는 것이 아니라 a1의 parking location(=a1을 위한 대기 장소)로 움직인다고 가정하고 경로를 계획합니다.

a3의 p5까지의 경로를 계획할 때에도 a1, a2가 p1, p3에 멈춰 있는 것이 아니라 각각의 parking location으로 움직인다고 가정하고 경로를 계획합니다.

 

agent들이 실제로 움직이는 것은 아니고 그렇게 움직일 것을 가정하고 경로를 계획하는 것입니다. agent들이 계속해서 작업을 수행할 수 있는 환경이기 때문에 가능한 접근법이죠.

• agent가 배정 받은 모든 작업을 수행했을 때에는 parking location으로 복귀하는 정책이더라고요.

하지만 이 방법도 모든 경우에 대해서 deadlock을 막지는 못합니다 ㅜ

 

P.S.
만약 well-formed infrastructure라면 deadlock이 발생하지 않는다고 말할 수 있습니다.
well-formed infrastructure란 스테이션에 위치한 로봇들이 다른 로봇의 경로를 완전히 막는 경우가 없는 것을 의미합니다.

• 참고: Complete Decentralized Method for On-Line Multi-Robot Trajectory Planning in Valid Infrastructure

well-formed infrastructure의 조건은 다음과 같습니다.

• 태스크의 수가 유한할 것
• 로봇의 대기 스테이션이 피킹, 패킹 작업이 이뤄지는 노드와 구분될 것
• 정차 가능한 노드 사이를 이어주는 경로 중에서 정차 가능한 노드를 포함하지 않는 경로가 있어야 함

 

로봇을 운용하는 환경이 well-formed라면 로봇A가 이미 정차하고 있는 노드로 로봇B가 움직여야 하는 데드락 같은 상황에서도

 

로봇A가 대기 스테이션으로 자리를 피해줄 수 있다는 것을 가정할 수 있기 때문에 문제를 풀기가 훨씬 쉬워집니다

 

TA-Hybrid

TA-Hybrid는 MAPD 문제를 MAPF 문제와 AMAPF 문제로 분해하여 해결합니다.

 

로봇이 pickup location에 도착해서 물품을 실었으면 정해진 delivery location으로 가야합니다. 이렇게 정해진 목적지를 바꾸지 못하는 경우는 MAPF 문제라고 볼 수 있습니다.

하지만 delivery location에서 다음 pickup location으로 가야하는 로봇이라면 다른 로봇들과 작업을 바꿀 수 있습니다. 정해진 목적지가 바뀔 수 있는 것이죠. 이런 경우는 AMAPF 문제라고 볼 수 있습니다.

 

TA-Hybrid는 MAPF, AMAPF 순서대로 문제를 해결합니다.

1. MAPF 문제

1. pickup location에서 작업을 완료하고 delivery location으로 가야하는 agent들의 집합을 A1라고 하고, 그 외 agent들을 A`이라고 합니다.
2. A1의 agent들에 대한 경로를 ICBS 알고리즘으로 계획합니다. 이 때, A`의 agent들의 경로를 constraint로 이용합니다.

2. AMAPF 문제

1. delivery location에서 작업을 완료하고, 새로운 작업을 수행해야 하는 agent들의 집합을 A2라고 합니다.
2. A2에 포함되어 있는 agent들을 pickup location이 중복되지 않도록 다시 한번 subgroup으로 나눕니다.
   • 만약 A2가 { a1: [(t1, p1, d1)], a2: [(t2, p1, d1)] } 라면 a1과 a2의 pickup location이 중복되므로 { a1: [(t1, p1, d1)] }{ a2: [(t2, p1, d1)] } 이렇게 subgroup으로 나워져야 합니다.
3. 각각의 subgroup을 A2`이라고 한다면 min cost max flow 알고리즘을 이용해서 A2`의 agent들간의 작업을 교환합니다.
   • min cost max flow 알고리즘을 이용해서 작업을 교환할 때에도 다른 agent들의 경로를 고려하는데 여기서는
4. A2`의 agent들에 대한 경로를 Prioritized Planning 알고리즘으로 계획합니다. 이 때, A2`의 agent들의 경로를 constraint로 이용합니다.

 

TA-Hybrid도 TA-Prioritized와 똑같이 reserving dummy path를 이용해서 데드락이 발생하는 것을 해소합니다.

 

3. 실험

논문에서는 Table1의 알고리즘들의 성능을 Figure 4의 small warehouse, large warehouse 환경에서 agent 수와 작업이 release 되는 속도를 조절하면서 비교했습니다.

LIU, Minghua, et al. Task and path planning for multi-agent pickup and delivery. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2019. Table 1

LIU, Minghua, et al. Task and path planning for multi-agent pickup and delivery. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2019. Figure 4

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

 

makespan

결과 표를 보면 TA 알고리즘들이 다른 MAPD 알고리즘들보다 작은 makespan을 보여줍니다. 이는 더 좋은 작업 배정 방식(TSP solver)로 인한 것인데요.

 

TA-ICBS가 makespan이 가장 작지만 agent 수가 많아지고 작업이 release 되는 속도가 빨라지면 timeout이 발생합니다.

반면에 TA-Hybrid는 large warehouse에서도 안정적으로 작은 makespan을 보여줍니다.

• large warehouse  결과에 CENTRAL과 TA-ICBS가 없는 이유는 모든 경우에 대해서 timeout이 발생했기 때문입니다.

 

runtime

알고리즘 실행 시간은 GREEDY 알고리즘들이 빠른 양상을 보여줍니다. 비교적 간단한 작업 배정 방식과 경로 계획 방식 때문인데요.

 

TA 알고리즘들은 더 복잡한 작업 배정 방식과 경로 계획 방식으로 인해서 알고리즘 실행 시간이 비교적 큽니다.

• 비교적 크다고 설명했지만 large warehouse 결과 표를 보면 GREEDY2와 TA-Hybrid의 makespan은 6~8% 정도 차이나지만 runtime은 4배까지도 차이가 납니다ㄷㄷ

 

하지만 논문에서는 Offline 문제인만큼 실행시간이 너무 긴 것이(설정한 limit을 넘겨서 timeout이 발생하는) 아닌 이상 충분히 감내할만하다고 설명합니다.

• 실제로 물류센터에서 물류 작업을 시작하기 전에 전부 계획할 수 있는 정도이므로 큰 영향을 주지 않을 것 같습니다.

LIU, Minghua, et al. Task and path planning for multi-agent pickup and delivery. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2019. Table 2

LIU, Minghua, et al. Task and path planning for multi-agent pickup and delivery. In: Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS). 2019. Table 3

4. 리뷰

Offline MAPD 문제의 수요를 알려준 점

가끔씩 너무 이론적으로만 문제를 바라보다가 "왜" 문제를 해결하려고 했는지 잊어버리고는 합니다.
물론 문제를 해결하는 것 자체에도 의미는 있겠지만... 우리는 더 많은 가치를 창출하기 위해서 문제를 해결하려고 노력합니다.
문제를 해결했을 때 가치를 창출할 수 없다면 다른 문제에 집중하는 것이 비용 효율적일 것입니다.
 
솔루션을 찾을 때에도 마찬가지입니다. 내가 해결하려는 문제 영역에 적용할 수 있는 솔루션인지부터 생각해야 합니다.
최근에는 잊고 있었는데 Introduction을 보면서 다시 한번 떠올리게 되어 좋았습니다.
 

Reserving Dummy Path을 개선할 수 있을까?

처음 MAPF 문제를 공부할 때, 궁금했던 것이 2가지 있습니다.

1. 사람, 지게차와 같은 동적인 장애물 혹은 네트워크 불안정성 때문에 로봇이 계획된 경로대로 움직이지 못하면 어떡하지?
2. 한 로봇이 작업을 배정 받지 못해서 목적지에 계속 가만히 있는 상황에서 다른 로봇들이 해당 목적지로 가야 한다면 어떻게 경로를 계획해야 하지?

1에 대한 답은 Persistent and Robust Execution of MAPF Schedules in Warehouses에서 얻을 수 있었는데 2에 대한 답을 이 논문에서 나왔더라고요.
 
좋은 답을 얻었다고 생각하는 와중에 같이 공부하는 분이 이런 질문을 했습니다.

dummy path를 만들기 위해서 로봇 별 대기 장소를 꼭 준비해야 하나요?
동적으로 효율적인 dummy path를 만들 수는 없을까요?

 dummy path로 인해 불필요한 conflict가 많이 발생하여 경로 계획에 시간이 오래 걸리는 문제가 발생할 수 있는데 이를 보완하는 방법이 궁금하셨던 것이죠.
 
간단하게 생각했을 때에는 배정된 task가 모두 끝난 로봇들에 대해서 가장 낮은 우선 순위를 부여하여 Prioritized Planning을 방법이 있을 것 같습니다.
Prioritized Planning의 목적은 로봇을 goal location으로 이동시키는 것이 아니라 conflict를 해소하는 것입니다.
 
하지만 Prioritized Planning의 한계상 완전성을 보장할 수 없다는 단점이 있으므로 이를 보완하기 위해서 로봇의 상황에 따라 부여하는 우선 순위를 조절할 수  있어야 할 것 같습니다.
예를 들어서, corridor 같은 환경에서는 가장 낮은 우선 순위를 부여해서 문제를 해결할 수 없습니다.

• 아래와 같이 B, C 노드에 배정된 task가 모두 끝난 로봇 1, 2가 있고 E에서 A로 향하는 로봇 3이 있다면 로봇 1, 2의 우선 순위가 최소한 로봇 3보다 크거나 같은 상태에서 대기 장소로 dummy path를 만들어야 문제를 해결할 수 있습니다.
• A - B(1) - C(2) - D - E(3) ... 

조금 더 구체적으로 방법을 고민해봐야겠습니다 ㅎㅎ

Priority 기반(?)의 deadlock 회피

 TA-Hybrid에서 phase를 나눠서 다른 phase의 경로를 방해하지 않는 경로 계획 방법은 꽤나 참신했습니다.

정확히 어느 phase의 우선 순위가 높다고 명시된 것은 아니지만 TA-Hybrid의 작업 배정 부분을 보면 delivery location으로 가는 작업을 먼저 할당한 후에 pick up location으로 가는 작업을 배정합니다.

이미 수행 중인 작업 > pickup location으로 가는 작업 > delivery location으로 가는 작업 순으로 우선 순위가 정해진다고 볼 수 있을 것 같습니다.

LG연구에서는 좁은 통로에서 빠져나오는 작업의 우선 순위를 높였던 것과 같이 생각해보면 현장에 따라서 정말 다양한 요구사항들이 있는 것 같습니다... MAPD 문제를 고객이 만족할만한 수준으로 해결하기 위해서는 현장 별로 작업의 우선 순위를 설정할 수 있는 확장성 좋은 방법이 필요한 것 같습니다!

• 사실 이 부분은 확장성 측면에서 생각하는 것이 좋았겠지만 논문의 conclusion에도 설명되어 있어서 다른 관점으로 살펴봤습니다...!

Pickup and Delivery가 아니라 Multiple Pickup and Delivery라면?

제가 해결하고 싶어 하는 중소 규모의 물류센터에서 해결해야 하는 MAPD 문제는 여러 pickup location을 들린 후에 delivery location으로 가는 경우가 많습니다.

 

이런 문제들은 어떻게 풀어야 할까요? 다행히 관련 연구들이 있더라고요!

다음에는 이 연구들을 공부해보도록 하겠습니다 :)

• XU, Qinghong, et al. Multi-goal multi-agent pickup and delivery. In: 2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2022. p. 9964-9971.

---

이번 논문은 어떠셨나요?
저는 assignment problem들을 찾아보면서 조합 최적화 알고리즘들을 조금 공부해 봤는데 세상에나 너무 어렵더라고요 ㅜ
"알고리즘 수업 들을 때 집중했어야 했는데..." 하면서 후회가 막심하더라고요 ㅋㅋㅋ
 
지금부터라도 열심히 공부해 봐야죠!

 

정리된 내용에서 제가 잘못 이해한 부분이 있다면 피드백 부탁드립니다 :)