Scholarlink

We propose an efficient method for determining subsequent movements in the multi-agent pickup and delivery (MAPD) problem, where multiple agents (e.g., carrier robots) continuously perform transportation tasks in environments with obstacles while avoiding collisions. Our method extends the decentralized path-finding algorithm, priority inheritance with backtracking (PIBT), proving effective in environments with narrow one-way paths and detours. This approach, PIBT with provisional booking (PIBT-PB), not only secures the next node as in PIBT but also provisionally books nodes in advance to detect potential conflicts earlier. This reduces unnecessary “turning back” and “waiting” actions. Experiments demonstrate that PIBT-PB outperforms the baselines, PIBT and windowed PIBT.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Path Finding with Flexible Provisional Booking in Multi-agent Pickup and Delivery Problems

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Daiki Shimada,
  • Yuki Miyashita,
  • Toshiharu Sugawara

摘要

We propose an efficient method for determining subsequent movements in the multi-agent pickup and delivery (MAPD) problem, where multiple agents (e.g., carrier robots) continuously perform transportation tasks in environments with obstacles while avoiding collisions. Our method extends the decentralized path-finding algorithm, priority inheritance with backtracking (PIBT), proving effective in environments with narrow one-way paths and detours. This approach, PIBT with provisional booking (PIBT-PB), not only secures the next node as in PIBT but also provisionally books nodes in advance to detect potential conflicts earlier. This reduces unnecessary “turning back” and “waiting” actions. Experiments demonstrate that PIBT-PB outperforms the baselines, PIBT and windowed PIBT.