알고리즘/Assignment Problem

Multi-Goal Multi-Agent Pickup and Delivery - Pickup and Delivery 일반화 해봐야죠!

Jㅐ둥이 2023. 11. 9. 08:00
반응형

안녕하세요. 오늘은 MAPD 문제를 연구한 Multi-Goal Multi-Agent Pickup and Delivery 논문을 공부하려고 합니다.

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

이전에 Task and Path Planning For Multi Agent Pickup and Delivery 논문을 공부했을 때,
Multiple Pickup and Delivery 문제를 어떻게 해결할 수 있을지 궁금했는데 다행히도 관련 연구를 쉽게 찾을 수 있었죠!
 
과연 Multi-Goal Multi-Agent Pickup and Delivery 논문에서는
Multiple Pickup and Delivery 문제를 어떻게 정의했고, 어떻게 해결했는지 알아보도록 하겠습니다!

1. Introduction

기존의 MAPD 알고리즘들의 한계

대다수의 MAPD 알고리즘들이 Task Assignment와 Path Finding 문제를 분리해서 풀고 있습니다.
이러한 MAPD 알고리즘들을 decoupled MAPD 알고리즘이라고 하는데요.
 
decoupled MAPD 알고리즘은 아래 3가지 유형으로 분류할 수 있습니다.

  1. agent들에게 한 번에 하나의 작업만 배정. 한 개의 목적지까지만 경로를 계획하는 유형
  2. agent들에게 한 번에 하나의 작업만 배정. 작업에 포함된 모든 목적지에 대해서 경로를 계획하는 유형
  3. agnet 들에게 한 번에 여러 개의 작업을 배정. 한 개의 목적지까지만 경로를 계획하는 유형

각 유형 별 연구들

더보기

1.

  • H. Ma, J. Li, T. K. S. Kumar, and S. Koenig, “Lifelong multi-agent path finding for online pickup and delivery tasks,” in International Conference on Autonomous Agents and Multiagent Systems, 2017, pp. 837–845.

2.

  • F. Grenouilleau, W.-J. v. Hoeve, and J. N. Hooker, “A multi-label A* algorithm for multi-agent pathfinding,” in International Conference on Automated Planning and Scheduling, 2021, pp. 181–185.

3.

  • M. Liu, H. Ma, J. Li, and S. Koenig, “Task and path planning for multi-agent pickup and delivery,” in International Conference on Autonomous Agents and Multiagent Systems, 2019, pp. 2253–2255.
  • Z. Chen, J. Alonso-Mora, X. Bai, D. D. Harabor, and P. J. Stuckey, “Integrated task assignment and path planning for capacitated multiagent pickup and delivery,” IEEE Robotics and Automation Letters, vol. 6, no. 3, pp. 5816–5823, 2021.

 
아쉽게도!
 
한 번에 하나의 작업만 배정하는 경우에는 최적의 작업 배정을 놓치는 문제가 발생할 수 있고,
배정 받은 작업에 대해서 한 개의 목적지까지만 경로를 계획하면 장기적으로 봤을 때 비효율적인 경로가 계획되는 문제가 발생할 수 있습니다.
 
논문에서는 이를 개선하기 위해 한 번에 여러 개의 작업을 배정하면서 모든 목적지에 대한 경로를 계획하는 decoupled MAPD 알고리즘 LNS-PBS와 LNS-wPBS를 제안합니다.
 

2. 논문에서 제안한 방법

논문에서 제안한 LNS-PBS와 LNS-wPBS는 기존 연구들과는 무엇이 다르길래 한 번에 여러 개의 작업을 배정하면서 모든 목적지에 대한 경로를 계획할 수 있는 것일까요?
 
일반적으로 한 번에 여러 개의 작업을 배정하면서 모든 목적지에 대한 경로를 계획하는 것은 매우 어려운 문제입니다.
Task Assignment 문제와 MAPF 문제를 여러 번 해결해야 하기 때문이지요...!
 
앞선 논문 리뷰들을 보시면 아시겠지만 MAPF, MAPD 알고리즘은 효율도 높아야 하지만 이에 못지 않게 알고리즘 실행 시간도 굉장히 빨라야 합니다.
 
LNS-PBS와 LNS-wPBS는 Priority Based Search(PBS)로 MAPF 문제를 해결하고, Large Neighborhood Search(LNS)로 작업 배정을 해결하는 방식으로 알고리즘의 효율과 실행 시간을 챙겼습니다.

  • PBS: H. Ma, D. D. Harabor, P. J. Stuckey, J. Li, and S. Koenig, “Searching with consistent prioritization for multi-agent path finding,” in AAAI Conference on Artificial Intelligence, 2019, pp. 7643–7650.
  • LNS: P. Shaw, “A new local search algorithm providing high quality solutions to vehicle routing problems,” APES Group, Dept of Computer Science, University of Strathclyde, 1997. 


PBS와 LNS를 어떻게 적용한 것인지, 어떤 디테일이 숨겨져 있는지 궁금하시겠지만!
그 전에 논문에서 Multiple Pickup and Delivery 문제를 어떻게 정의했는지부터 알아보겠습니다.
 

Multi-Goal MAPD 문제

논문에서는 Multiple Pickup and Delivery 문제를 Multi-Goal MAPD 문제라고 명명했습니다.
 
일반적으로 k개의 에이전트가 있는 MAPD 문제 <G, s, T>는 다음과 같이 표현할 수 있습니다.

  • G는 노드들의 집합 V와 엣지들의 집합 E의 쌍으로 표현할 수 있습니다. => G = (V, E)
  • s는 k개의 에이전트와 각 에이전트의 초기 위치를 나타내는 관계입니다. => s : [1, 2, ..., k] -> V
  • T는 해결해야 할 작업들의 집합으로 작업은 pickup location과 delivery location 그리고 release time을 나타냅니다. => T = {t | t = (Vp, Vd, r), Vp ∈ V, Vd ∈ V , r  ∈ N}

 
Multi-Goal MAPD problem도 MAPD 문제와 유사하지만 작업에 대한 정의가 조금 다릅니다.

  • G는 노드들의 집합 V와 엣지들의 집합 E의 쌍으로 표현할 수 있습니다. => G = (V, E)
  • s는 k개의 에이전트와 각 에이전트의 초기 위치를 나타내는 관계입니다. => s : [1, 2, ..., k] -> V
  • T는 해결해야 할 작업들의 집합으로 작업은 goal location의 순열과 release time을 나타냅니다. => T = {t | t=({v | v ∈ V}, r), r  ∈ N}

MAPD 문제에서는 작업이 pickup location과 delivery location으로 구성되어 있지만 MG-MAPD 문제에서는 작업이 goal location의 순열로 구성되어 있습니다.
 
혹시 Task and Path Planning For Multi Agent Pickup and Delivery 리뷰에서 다뤘던 well-formed infrastructure를 기억하시나요?

 
마지막으로 본 논문에서는 well-formed MG-MAPD 문제에 대해서만 다뤘습니다. MG-MAPD 문제라고 해서 well-formed의 조건이 다르지는 않더라고요 ㅎㅎ
 
P.S.
논문에서 well-formed MG-MAPD 문제만 다룬 이유가 무엇일까요?
해답은 뒤에 솔루션 설명에서 다뤄지니 궁금하시면 읽어주세요 :)
 

LNS-PBS

LNS-PBS는 이름 그대로 Large Neighborhood Search(LNS)와 Prioriby Based Search(PBS)를 사용하여
작업 배정과 경로 계획에 걸리는 시간, 그리고 makespan을 최소화 하는 솔루션입니다.

  • MA, Hang, et al. Searching with consistent prioritization for multi-agent path finding. In: Proceedings of the AAAI conference on artificial intelligence. 2019. p. 7643-7650.
  1. 새로운 작업이 생성되었거나, 종료되었다면 LNS를 이용해서 agent에게 작업을 배정합니다.
  2. agent들에게 dummy endpoint를 배정합니다.
  3. PBS를 이용해서 agent들의 경로를 계획합니다.
  4. 계획된 경로대로 agent들을 이동시킵니다.
  5. 1로 돌아갑니다.


PBS는 MAPF 알고리즘들을 공부하면서 한번씩 들어보셨을 수도 있지만 LNS는 많이 낯설 거에요.
 
LNS를 간단하게 설명드리면 "최적의 답은 아니더라도 일단 답을 찾은 다음에 개선해 나가는 것"이라고 할 수 있습니다.
그러면 LNS-PBS에서는 어떤 방식으로 1) 일단 답을 찾고, 2) 개선해나가는지 알아보도록 하겠습니다.
 
LNS TMI ㅎㅎ...

더보기

Neighborhood Search를 보시고 유전 알고리즘을 떠오르신 분들이 있었을 것 같습니다.

조금 더 나아가서 Neighborhood Search에 왜 Large가 붙었는지 궁금하신 분도 있었을까요?

 

일반적으로 Neighborhood Search라고 하면 초기에 찾은 솔루션에서 작은 수정을 가하여 다른 솔루션을 찾는 탐색 반식을 뜻합니다.

 

이렇게 되면 초기에 찾은 솔루션의 성능과 크게 달라지지 않는다는 단점이 있습니다.

 

그래서 큰(Large) 수정을 가하는 방식들이 연구되었는데 이것이 LNS였습니다.

 

저는 탐색해야 할 노드가 너무 많아서 Large를 붙인 줄 알았는데 완전 잘못 짚었더라고요 ㅋㅋㅋ

 

이제 각 과정을 조금 더 자세하게 설명드리겠습니다.

 

헝가리안 알고리즘을 사용한 초기 작업 배정

LNS-PBS에서는 초기 작업 배정을 위해서  헝가리안 알고리즘을 사용했습니다.
 
헝가리안 알고리즘은 agent와 각 agent들이 목적지로 가기까지 걸리는 비용 행렬이 있을 때, 최적의 (agent - 목적지) 조합을 찾는 알고리즘입니다.
 
하지만 주어진 비용 행렬에서 한번의 목적지 배정만 이뤄지기 때문에 agent들이 여러 개의 목적지를 들려야 하는 상황이라면 최적의 답을 찾지 못할 수 있습니다.
 
그렇지만 이 단계에서는 agent들간의 충돌과 장기적으로 발생할 수 있는 비효율을 고려하지 않고 일단 답을 찾습니다.
 
 
P.S.
헝가리안 알고리즘에 대해서 공부하고 싶으시면 아래 블로그 글을 참고해주세요.
정말 자세하게 설명해주셔서 공부하는데 많은 도움이 될 거에요!

 

Shaw removal and regret-based  re-insertion 작업 배정 개선

이제 위에서 나온 결과를 개선해야 합니다.
도대체 어떤 방법으로 개선할 수 있을까요?
 
놀랍게도 어떤 작업들을 빼야 좋은지 휴리스틱한 방법을 연구한 논문이 있더라고요!

  • S. Ropke and D. Pisinger, “An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows,” Transportation Science, pp. 455–472, 2006

위의 논문을 참고하여 작업 배정을 개선하는 방식은 다음과 같습니다.

  • Shaw removal과 regret-based re-insertion에 대한 자세한 설명은 생략하도록 하겠습니다!

 
1. 배정된 작업 중에서 임의로 하나의 작업을 고릅니다.
2. 1에서 고른 작업과 공간적, 시간적으로 가까운 작업들을 N-1 개 고른 다음에 배정을 해제합니다(Shaw removal).
3. 해제한 N-1개의 작업들을 따로 정의한 regret 연산값이 가장 큰 순서대로 다시 배정합니다(regret-based re-insertion).

 

Dummy Endpoint

혹시 Dummy Endpoint라는 용어가 익숙하신가요?

Task and Path Planning For Multi Agent Pickup and Delivery 에서 공부한 적이 있죠!

하지만 이 논문에서 Dummy Endpoint는 조금 다릅니다.

 

모든 agent들의 dummy endpoint는 달라야 하며,

1. agent의 경로를 재계획 할 때, agent에 배정된 마지막 목적지와 가장 가까운 스테이션(task endpoint)를 dummy endpoint로 설정합니다.
2. 이 때, 남아 있는 task endpoint가 없다면, agent의 초기 위치를 dummy endpoint로 설정합니다.

 

이전 논문에서는 agent 별 dummy endpoint를 고정하여 알고리즘의 완전성을 지켰다면 LNS-PBS는 다른 endpoint도 활용한 것입니다.

 

PBS

PBS는 Prioritized Planning의 CBS 버전입니다.

원래 Prioritized Planning(PP)은 agent들 간의 우선순위를 경로 계획 초기에 임의로 정하고 계획합니다.

하지만 PBS는 CBS와 비슷하게 처음에는 agent 간 우선 순위 없이 경로를 계획하고,
충돌이 발생할 때마다 충돌이 발생한 agent들간의 우선 순위를 설정합니다.

이렇게 되면 PBS는 agent들간의 partial order를 생성하게 됩니다.
PP가 total order만을 사용하여 생기는 단점을 해소하기 위해 착안된 알고리즘으로 알고 있는데
구체적으로는 나중에 공부해보도록 하겠습니다!

 

 

LNS-wPBS

LNS-PBS에 대해서 살펴봤으니 LNS-wPBS에 대해서 살펴봐야겠죠.

 

사실 LNS-wPBS는 LNS-PBS와 굉장히 유사합니다.

 

  1. 새로운 작업이 생성되었거나, 종료되었다면
    1. LNS를 이용해서 agent에게 작업을 배정합니다.
    2. agent들에게 dummy endpoint를 배정합니다.
    3. wPBS를 이용해서 agent들의 경로를 계획합니다.
    4. 5로 돌아갑니다.
  2. agent가 사용자가 정의한 timestep만큼 움직였다면
    1. agent들에게 dummy endpoint를 배정합니다.
    2. wPBS를 이용해서 agent들의 경로를 계획합니다
  3. 계획된 경로대로 agent들을 이동시킵니다.
  4. 1로 돌아갑니다.

Multi-Goal Multi-Agent Pickup and Delivery 논문은 어떠셨나요?

 

저는 알고리즘의 효율과 속도 중 한가지를 선택해야 할 때, 어떤 기준을 잡을지, 휴리스틱 함수를 어떻게 정의할 것인지 막막하던데

이렇게 유의미한 결과가 나오는 휴리스틱 함수는 어떻게 찾는지 다들 대단한 것 같습니다!
 


Task and Path Planning For Multi Agent Pickup and Delivery 논문을 리뷰하고,

빠르게 Multi-Goal Multi-Agent Pickup and Delivery 논문을 리뷰하려고 했지만

결혼 준비, 알고리즘 공부, 명절 연휴 등 할 일이 많더라구요.

 

그러다보니 이번 논문 공부가 너무 늘어지는 것 같아서 실험 파트와 리뷰 파트까지는 작성하지 않았습니다

그래도 꾸준히 공부를 이어가고 있다는 것에 의의를 두려고 합니다 ㅎㅎ

 

여러분도 하시는 일 모두 건승하기를 바랍니다!

 

피드백은 언제나 환영입니다 :)

반응형
저작자표시 비영리 변경금지 (새창열림)