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

Tomoki Yamauchi*, Yuki Miyashita, Toshiharu Sugawara


研究成果: Conference contribution

5 被引用数 (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.

ホスト出版物のタイトルMulti-Agent Systems - 18th European Conference, EUMAS 2021, Revised Selected Papers
編集者Ariel Rosenfeld, Nimrod Talmon
出版社Springer Science and Business Media Deutschland GmbH
出版ステータスPublished - 2021
イベント18th European Conference on Multi-Agent Systems, EUMAS 2021 - Virtual, Online
継続期間: 2021 6月 282021 6月 29


名前Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
12802 LNAI


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

ASJC Scopus subject areas

  • 理論的コンピュータサイエンス
  • コンピュータサイエンス一般


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