A study conducted by Hiroya Makino and Seigo Ito has been accepted for presentation at the 2026 IEEE International Conference on Robotics and Automation (ICRA).

 

Multi-Agent Path Finding (MAPF) involves planning efficient paths for multiple agents to move simultaneously while avoiding collisions, and it has been widely applied in areas such as transport robots in automated warehouses. Conventional warehouses often rely on static aisles that allow agents to move without interfering with one another. However, to utilize warehouse space more efficiently, there is a growing demand for effective MAPF under high-density environments. In high-density MAPF scenarios, Integer Linear Programming (ILP) has traditionally been employed. While ILP can derive optimal paths, it performs computations over all agents simultaneously, which results in a significant increase in computational time and poses a major challenge.

 

In this study, we successfully achieved a significant reduction in computation time by decomposing the path planning process into multiple stages and repeatedly performing lightweight computations that swap agents with empty spaces. While the computation time of ILP increases exponentially with respect to factors such as environment size, the proposed method operates within polynomial time. For example, in comparative experiments conducted in a simulation environment, the computation time was reduced from 180 seconds to 0.04 seconds. This method is expected to improve the efficiency of path planning not only in automated warehouses but also in other applications such as factories and automated parking systems.

 

This research was published in IEEE Robotics & Automation Magazine prior to its presentation at ICRA (https://doi.org/10.1109/MRA.2025.3642762).

 

【Related Article】

Path Planning for High-Density Conveyance Areas in Warehouses / Factories

 

Title: MAPF-HD: Multi-Agent Path Finding in High-Density Environments

Authors: Makino, H., Ito, S.

Appears in: IEEE International Conference of Robotics & Automation

Present: June 2, 2026