Task Selection Algorithm for Multi-Agent Pickup and Delivery with Time Synchronization

Tomoki Yamauchi*, Yuki Miyashita, Toshiharu Sugawara

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish
Title of host publicationPRIMA 2022
Subtitle of host publicationPrinciples and Practice of Multi-Agent Systems - 24th International Conference, Proceedings
EditorsReyhan Aydoğan, Natalia Criado, Victor Sanchez-Anguix, Jérôme Lang, Marc Serramia
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages17
ISBN (Print)9783031212024
Publication statusPublished - 2023
Event24th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2020 - Valencia , Spain
Duration: 2022 Nov 162022 Nov 18

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13753 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference24th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2020


  • Decentralized robot path planning
  • Multi-agent path finding
  • Multi-agent pickup and delivery tasks
  • Multi-agent task selection

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Task Selection Algorithm for Multi-Agent Pickup and Delivery with Time Synchronization'. Together they form a unique fingerprint.

Cite this