Efficient Path and Action Planning Method for Multi-Agent Pickup and Delivery Tasks under Environmental Constraints

Tomoki Yamauchi*, Yuki Miyashita, Toshiharu Sugawara

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review


We propose a method called path and action planning with orientation (PAPO) that efficiently generates collision-free paths to satisfy environmental constraints, such as restricted path width and node size, for the multi-agent pickup and delivery in non-uniform environment (N-MAPD) problem. The MAPD problem, wherein multiple agents repeatedly pick up and carry materials without collisions, has attracted considerable attention; however, conventional MAPD algorithms assume a specially designed environment and thus use simple, uniform models with few environmental constraints. Such conventional algorithms cannot be applied to realistic applications where agents need to move in more complex and restricted environments. For example, the actions and orientations of agents are strictly restricted by the sizes of agents and carrying materials and the width of the passages at a construction site and a disaster area. In our N-MAPD formulation, which is an extension of the MAPD problem to apply to non-uniform environments with constraints, PAPO considers not only the path to the destination but also the agents’ direction, orientation, and timing of rotation. It is costly to consider all these factors, especially when the number of nodes is large. Our method can efficiently generate acceptable plans by exploring the search space via path planning, action planning, and conflict resolution in a phased manner. We experimentally evaluated the performance of PAPO by comparing it with our previous method, which is the preliminary version of PAPO, the baseline method in a centralized approach, and fundamental meta-heuristic algorithms. Finally, we demonstrate that PAPO can efficiently generate sub-optimal paths for N-MAPD instances.

Original languageEnglish
Article number83
JournalSN Computer Science
Issue number1
Publication statusPublished - 2023 Jan


  • Environmental constraints
  • Multi-agent path finding
  • Multi-agent pickup and delivery problem
  • Multi-agent planning
  • Robot planning

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Networks and Communications
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • General Computer Science
  • Artificial Intelligence


Dive into the research topics of 'Efficient Path and Action Planning Method for Multi-Agent Pickup and Delivery Tasks under Environmental Constraints'. Together they form a unique fingerprint.

Cite this