Path and Action Planning in Non-uniform Environments for Multi-agent Pickup and Delivery Tasks

Tomoki Yamauchi*, Yuki Miyashita, Toshiharu Sugawara

*Corresponding author for this work

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

5 Citations (Scopus)


Although the multi-agent pickup and delivery (MAPD) problem, wherein multiple agents iteratively carry materials from some storage areas to the respective destinations without colliding, has received considerable attention, conventional MAPD algorithms use simplified, uniform models without considering constraints, by assuming specially designed environments. Thus, such conventional algorithms are not applicable to some realistic applications wherein agents have to move in a more complicated and restricted environment; for example, in a rescue or a construction site, their paths and orientations are strictly restricted owing to the path width, and the sizes of agents and materials they carry. Therefore, we first formulate an N-MAPD problem, which is an extension of the MAPD problem for a non-uniform environment. We then propose an N-MAPD algorithm, the path and action planning with orientation (PAPO), to effectively generate collision-free paths meeting the environmental constraints. The PAPO is an algorithm that considers not only the direction of movement but also the orientation of agents as well as the cost and timing of rotations in our N-MAPD formulation by considering the agent and material sizes, node sizes, and path widths. We experimentally evaluated the performance of the PAPO using our simulated environments and demonstrated that it could efficiently generate not optimal but acceptable paths for non-uniform environments.

Original languageEnglish
Title of host publicationMulti-Agent Systems - 18th European Conference, EUMAS 2021, Revised Selected Papers
EditorsAriel Rosenfeld, Nimrod Talmon
PublisherSpringer Science and Business Media Deutschland GmbH
Number of pages18
ISBN (Print)9783030822538
Publication statusPublished - 2021
Event18th European Conference on Multi-Agent Systems, EUMAS 2021 - Virtual, Online
Duration: 2021 Jun 282021 Jun 29

Publication series

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


Conference18th European Conference on Multi-Agent Systems, EUMAS 2021
CityVirtual, Online


  • Multi-agent path finding
  • Multi-agent pickup and delivery tasks
  • Non-uniform environments

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Path and Action Planning in Non-uniform Environments for Multi-agent Pickup and Delivery Tasks'. Together they form a unique fingerprint.

Cite this