Collision-Free Multi-Agent Path Finding for 2D/3D Robots

Collision-Free Multi-Agent Path Finding for 2D/3D Robots

Given the rapid development of affordable robots with embedded sensing and computation capabilities, we are quickly approaching a point at which manufacturing applications will involve the deployment of hundreds, if not thousands, of robots. To support these applications, significant research effort has been devoted to multi-agent path finding (MAPF), to support deployments in distribution centers, potential use for airplane taxiing and test applications to multi-agent search and rescue. However, as the number of agents in the system grows, so does the combinatorial complexity of coordinating them. Current state-of-the-art optimal planners can plan for up to several hundreds of agents, and the community is now settling for suboptimal planners as a potential solution for even larger multi-agent systems. Another common approach is to rely on reactive planners, which do not plan joint paths for all agents before execution, but rather correct individual paths online to avoid collisions. However, such planners often prove inefficient in cluttered factory environments, and can result in dead- and livelocks.

As a new direction for research in MAPF for large numbers of robots, this project builds upon recent results in distributed reinforcement learning (RL) as well as imitation learning (IL) to train agents to plan paths in complex, cluttered environments based on individual decisions toward a common goal (distributed intelligence). This project will seek to extend recent results in 2D path planning (PRIMAL, see our recently published paper) to 3D teams of agents (e.g., drones). There, the complexity of the problem increases with the dimensionality of the space, and the assumption that the robot have simple kinematics might not hold. This work will seek new ways to let teams of 3D robots plan individual collision-free paths, for applications and/or added safety in a wide range of multi-UAVs applications, such as collective search, mapping, or inspection.

Project reports from previous years:

Related prior projects:

People

Guillaume SARTORETTI
Assistant Professor
Chengyang HE
Chengyang HE
Mehul DAMANI (NTU)
Mehul DAMANI (NTU)
Yutong WANG
Yutong WANG
Xinwei GAO
Xinwei GAO