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

Result code in 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>

Alternative codes found

RIV/68407700:21730/22:00364289

Result on the web

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

Result language

angličtina

Original language name

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

Original language description

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/)

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/EF15_003%2F0000470" target="_blank" >EF15_003/0000470: Robotics 4 Industry 4.0</a><br>

Continuities

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

Publication year

2022

Confidentiality

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

Article name in the collection

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

ISBN

—

ISSN

2405-8963

e-ISSN

2405-8963

Number of pages

6

Pages from-to

61-66

Publisher name

Elsevier BV

Place of publication

Linz

Event location

Matsumoto

Event date

Oct 17, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000925715900010