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

Tomoki Yamauchi*, Yuki Miyashita, Toshiharu Sugawara


研究成果: Article査読


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.

ジャーナルSN Computer Science
出版ステータスPublished - 2023 1月

ASJC Scopus subject areas

  • 計算理論と計算数学
  • コンピュータ ネットワークおよび通信
  • コンピュータ サイエンスの応用
  • コンピュータ グラフィックスおよびコンピュータ支援設計
  • コンピュータサイエンス一般
  • 人工知能


「Efficient Path and Action Planning Method for Multi-Agent Pickup and Delivery Tasks under Environmental Constraints」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。