Multi-Robot Motion Planning
Related Projects:  Robot Task and Motion Planning    Multi-Agent Systems    Group Behaviors    Navigation & Localization    Parallel Hierarchical Planning Algorithms    Hybrid Planning  

Multi-robot systems (MRS) have grown more prevalent in warehouse management, manufacturing, and surveillance applications. MRS can improve productivity while reducing time and operation costs. Multi-robot Motion Planning (MRMP) is the problem of finding a feasibe set of collision-free paths of a given multi-robot system. Our group has developed several contributions to solve this problem.

Parallel Hierarchical Planning Algorithms

Parallel hierarchical planning algorithms are used to efficiently solve multi-robot motion planning and multi-robot task and motion planning problems.

Hybrid Planning

We investigate hybrid algorithms to solve challenging multi-robot motion planning problems with many robots requiring precise coordination.

Related Publications

Scalable Multi-robot Motion Planning for Congested Environments With Topological Guidance, Courtney McBeth, James Motes, Diane Uwacu, Marco Morales, Nancy M. Amato, In IEEE Robotics and Automation Letters, Aug 2023. DOI: 10.1109/LRA.2023.3312980
Keywords: Motion Planning, Multi-Agent, Workspace Topology
Links : [Published] [ArXiv] [Video]


author={McBeth, Courtney and Motes, James and Uwacu, Diane and Morales, Marco and Amato, Nancy M.},
journal={IEEE Robotics and Automation Letters},
title={Scalable Multi-robot Motion Planning for Congested Environments With Topological Guidance},


Multi-robot motion planning (MRMP) is the problem of finding collision-free paths for a set of robots in a continuous state space. The difficulty of MRMP increases with the number of robots and is exacerbated in environments with narrow passages that robots must pass through, like warehouse aisles where coordination between robots is required. In single-robot settings, topology-guided motion planning methods have shown improved performance in these constricted environments. In this work, we extend an existing topology-guided single-robot motion planning method to the multi-robot domain to leverage the improved efficiency provided by topological guidance. We demonstrate our method's ability to efficiently plan paths in complex environments with many narrow passages, scaling to robot teams of size up to 25 times larger than existing methods in this class of problems. By leveraging knowledge of the topology of the environment, we also find higher-quality solutions than other methods.

Parallel Hierarchical Composition Conflict-Based Search, Hannah Lee, James Motes, Marco Morales, Nancy M. Amato, IEEE/RSJ International Conference on Intelligent Robots and Systems, Vol: 6, Issue: 4, pp. 7001-7008, Prague, Czech Republic, Jul 2021. DOI: 10.1109/LRA.2021.3096476.
Keywords: Multi-Agent, Parallel Planning, Path Planning
Links : [Published]


title={Parallel Hierarchical Composition Conflict-Based Search for Optimal Multi-Agent Pathfinding},
author={Lee, Hannah and Motes, James and Morales, Marco and Amato, Nancy M},
journal={IEEE Robotics and Automation Letters},


In this letter, we present the following optimal multi-agent pathfinding (MAPF) algorithms: Hierarchical Composition Conflict-Based Search, Parallel Hierarchical Composition Conflict-Based Search, and Dynamic Parallel Hierarchical Composition Conflict-Based Search. MAPF is the task of finding an optimal set of valid path plans for a set of agents such that no agents collide with present obstacles or each other. The presented algorithms are an extension of Conflict-Based Search (CBS), where the MAPF problem is solved by composing and merging smaller, more easily manageable subproblems. Using the information from these subproblems, the presented algorithms can more efficiently find an optimal solution. Our three presented algorithms demonstrate improved performance for optimally solving MAPF problems consisting of many agents in crowded areas while examining fewer states when compared with CBS and its variant Improved Conflict-Based Search.

Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search, Irving Solis, James Motes, Read Sandström, Nancy M. Amato, IEEE Robotics and Automation Letters, Mar 2021. DOI:
Keywords: Industrial Applications, Motion Planning, Multi-Agent
Links : [Published] [Manuscript]


title={Representation-optimal multi-robot motion planning using conflict-based search},
author={Solis, Irving and Sandstr{\"o}m, Read and Motes, James and Amato, Nancy M},
journal={arXiv preprint arXiv:1909.13352},


Multi-Agent Motion Planning (MAMP) is the problem of computing feasible paths for a set of agents each with individual start and goal states within a continuous state space. Existing approaches can be split into coupled methods which provide optimal solutions but struggle with scalability or decoupled methods which provide scalable solutions but offer no optimality guarantees. Recent work has explored hybrid approaches that leverage the advantages of both coupled and decoupled approaches in an easier discrete subproblem, Multi-Agent Pathfinding (MAPF). In this work, we adapt recent developments in hybrid MAPF to the continuous domain of MAMP. We demonstrate the scalability of our method to manage groups of up to 32 agents, demonstrate the ability to handle up to 8 high-DOF manipulators, and plan for heterogeneous teams. In all scenarios, our approach plans significantly faster while providing higher quality solutions.