TY - GEN
T1 - Task Selection Algorithm for Multi-Agent Pickup and Delivery with Time Synchronization
AU - Yamauchi, Tomoki
AU - Miyashita, Yuki
AU - Sugawara, Toshiharu
N1 - Funding Information:
This work was partly supported by JSPS KAKENHI Grant Number 20H04245.
Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2023
Y1 - 2023
N2 - In this paper, we formulate the material transportation problem as a multi-agent pickup and delivery with time synchronization (MAPD-TS) problem, which is an extension of the well-known multi-agent pickup and delivery (MAPD) problem. In MAPD-TS, we consider the synchronization of the movement of transportation agents with that of external agents, such as trucks arriving and departing from time to time in a warehouse and elevators that transfer materials to and from different floors in a construction site. We then propose methods via which agents autonomously select the tasks for improving overall efficiency by reducing unnecessary waiting times. MAPD is an abstract formation of material transportation tasks, and a number of methods have been proposed only for efficiency and collision-free movement in closed systems. However, as warehouses and construction sites are not isolated closed systems, transportation agents must sometimes synchronize with external agents to achieve real efficiency, and our MAPD-TS is the abstract form of this situation. In our proposed methods for MAPD-TS, agents approximately estimate their arrival time at the carry-in/out port connected with external agents and autonomously select the task to perform next for improved synchronization. Thereafter, we evaluate the performance of our methods by comparing them with the baseline algorithms. We demonstrate that our proposed algorithms reduce the waiting times of both agents and external agents and thus could improve overall efficiency.
AB - In this paper, we formulate the material transportation problem as a multi-agent pickup and delivery with time synchronization (MAPD-TS) problem, which is an extension of the well-known multi-agent pickup and delivery (MAPD) problem. In MAPD-TS, we consider the synchronization of the movement of transportation agents with that of external agents, such as trucks arriving and departing from time to time in a warehouse and elevators that transfer materials to and from different floors in a construction site. We then propose methods via which agents autonomously select the tasks for improving overall efficiency by reducing unnecessary waiting times. MAPD is an abstract formation of material transportation tasks, and a number of methods have been proposed only for efficiency and collision-free movement in closed systems. However, as warehouses and construction sites are not isolated closed systems, transportation agents must sometimes synchronize with external agents to achieve real efficiency, and our MAPD-TS is the abstract form of this situation. In our proposed methods for MAPD-TS, agents approximately estimate their arrival time at the carry-in/out port connected with external agents and autonomously select the task to perform next for improved synchronization. Thereafter, we evaluate the performance of our methods by comparing them with the baseline algorithms. We demonstrate that our proposed algorithms reduce the waiting times of both agents and external agents and thus could improve overall efficiency.
KW - Decentralized robot path planning
KW - Multi-agent path finding
KW - Multi-agent pickup and delivery tasks
KW - Multi-agent task selection
UR - http://www.scopus.com/inward/record.url?scp=85142671225&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85142671225&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-21203-1_27
DO - 10.1007/978-3-031-21203-1_27
M3 - Conference contribution
AN - SCOPUS:85142671225
SN - 9783031212024
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 458
EP - 474
BT - PRIMA 2022
A2 - Aydoğan, Reyhan
A2 - Criado, Natalia
A2 - Sanchez-Anguix, Victor
A2 - Lang, Jérôme
A2 - Serramia, Marc
PB - Springer Science and Business Media Deutschland GmbH
T2 - 24th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2020
Y2 - 16 November 2022 through 18 November 2022
ER -