Quality Analysis of Multi-Agent Multi-Item Pickup and Delivery Solutions Using a Decoupled Approach

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F22%3A00364289" target="_blank" >RIV/68407700:21230/22:00364289 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21730/22:00364289

Výsledek na webu

<a href="https://doi.org/10.1016/j.ifacol.2023.01.134" target="_blank" >https://doi.org/10.1016/j.ifacol.2023.01.134</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ifacol.2023.01.134" target="_blank" >10.1016/j.ifacol.2023.01.134</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Quality Analysis of Multi-Agent Multi-Item Pickup and Delivery Solutions Using a Decoupled Approach

Popis výsledku v původním jazyce

In this article, we study the Multi-agent Multi-item Pickup and Delivery (MAMPD), which stands for a problem of finding collision-free trajectories for a fleet of mobile agents transporting a set of items from their initial positions to the specified goal locations. Each agent can carry multiple items up to a given capacity at the same moment. This requires solving two orthogonal problems concurrently: assigning a sequence of items to pick for every agent and finding a set of collision-free trajectories under this assignment. We decouple the problem into two subproblems: the task assignment (TA) and Multi-Agent Pathfinding (MAPF), to determine the lower and upper bounds of the MAMPD. First, a lower bound is estimated by formulating and solving the TA as a Vehicle Routing Problem (VRP). The collisions, which are not considered during the TA, are consequently resolved using a MAPF solver on the VRP solution. The cost of the MAPF solution forms an upper bound of the MAMPD. We show that on a large class of setups, the gap between the lower and upper bounds is small. This signifies that the decoupled MAMPD solver obtained near-optimal solutions. However, we show that on certain setups, intentionally designed to be difficult, the decoupled solver is unable to find a solution with a small gap even when using a bounded suboptimal MAPF solver. By computing the gap, we can determine whether the solution obtained by the decoupled approach is near-optimal or whether it is beneficial to use a more advanced MAMPD solver. Copyright (c) 2022 The Authors. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0/)

Název v anglickém jazyce

Quality Analysis of Multi-Agent Multi-Item Pickup and Delivery Solutions Using a Decoupled Approach

Popis výsledku anglicky

In this article, we study the Multi-agent Multi-item Pickup and Delivery (MAMPD), which stands for a problem of finding collision-free trajectories for a fleet of mobile agents transporting a set of items from their initial positions to the specified goal locations. Each agent can carry multiple items up to a given capacity at the same moment. This requires solving two orthogonal problems concurrently: assigning a sequence of items to pick for every agent and finding a set of collision-free trajectories under this assignment. We decouple the problem into two subproblems: the task assignment (TA) and Multi-Agent Pathfinding (MAPF), to determine the lower and upper bounds of the MAMPD. First, a lower bound is estimated by formulating and solving the TA as a Vehicle Routing Problem (VRP). The collisions, which are not considered during the TA, are consequently resolved using a MAPF solver on the VRP solution. The cost of the MAPF solution forms an upper bound of the MAMPD. We show that on a large class of setups, the gap between the lower and upper bounds is small. This signifies that the decoupled MAMPD solver obtained near-optimal solutions. However, we show that on certain setups, intentionally designed to be difficult, the decoupled solver is unable to find a solution with a small gap even when using a bounded suboptimal MAPF solver. By computing the gap, we can determine whether the solution obtained by the decoupled approach is near-optimal or whether it is beneficial to use a more advanced MAMPD solver. Copyright (c) 2022 The Authors. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0/)

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/EF15_003%2F0000470" target="_blank" >EF15_003/0000470: Robotika pro Průmysl 4.0</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

IFAC-PapersOnLine 13th IFAC Symposium on Robot Control SYROCO 2022

ISBN

—

ISSN

2405-8963

e-ISSN

2405-8963

Počet stran výsledku

6

Strana od-do

61-66

Název nakladatele

Elsevier BV

Místo vydání

Linz

Místo konání akce

Matsumoto

Datum konání akce

17. 10. 2022

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000925715900010