16891: Multi-Robot Planning and Coordination

Robotics Institute, Carnegie Mellon University, Spring 2024

Last update: 07-20-2024

More details can be found in course canvas.

Course Introduction

Overview:

The course provides a graduate-level introduction to the field of multi-robot planning and coordination from both AI and robotics perspectives. Topics for the course include multi-robot cooperative task planning, multi-robot path/motion planning, learning for coordination, coordinating robots under uncertainty, etc. The course will particularly focus on state-of-the-art Multi-Agent Path Finding algorithms that can coordinate hundreds of robots with rigorous theoretical guarantees. Current applications for these technologies will be highlighted, such as mobile robot coordination for warehouses and drone swarm control.

Textbook:

There is no assigned textbook for this class. Reference materials are provided in the course schedule as well as the lecture slides.

Course Description:

The course includes lectures, research paper presentations and discussions, and course projects. The majority of this course is a seminar-style survey of issues and approaches to planning and coordination in multi-robot systems. Although the subject area is multi-robot coordination, it is also an explicit goal of this course to advance students’ critical thinking and communication skills, which is achieved through discussions, presentations, and report writing.

Prerequisite knowledge:

There are no formal prerequisites for this class.
Informally, students should be familiar with algorithms and informed search (for example, A*). Students should also have basic knowledge of probability and physics (kinematics).

Course topics:

Each of the following 7 topics will be covered by 2-6 lectures:

• Basics of Multi-Agent Path Finding (MAPF)
• Combined (Multi-Robot) Task and Path Planning
• (Multi-Robot) Planning and Coordination under Uncertainty
• (Multi-Robot) Planning with Robot Dynamics
• Decentralized (Multi-Robot) Planning and Coordination
• Learning for (Multi-Robot) Planning and Coordination
• (Multi-Robot) Applications

Course Activities and Grading

Schedule

Reading List

1. Idle Time Optimization for Target Assignment and Path Finding in Sortation Centers (AAAI’20)
2. A New Approach for Multiagent Combinatorial Path Finding (T-RO’23)
3. Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree (MRS’23)
4. A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph (ICAPS’20 Workshop)
5. Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution (AAAI’24)
6. Offline Time-Independent Multiagent Path Planning (T-RO’23)
7. Adaptive Robot Coordination: A Subproblem-based Approach for Hybrid Multi-Robot Motion Planning (arXiv’23)
8. Scalable Multi-Robot Motion Planning for Congested Environments With Topological Guidance (RA-L’23)
9. Quick Multi-Robot Motion Planning by Combining Sampling and Search (IJCAI’23)
10. Walk, Stop, Count, and Swap: Decentralized Multi-Agent Path Finding With Theoretical Guarantees (RA-L’20)
11. Distributing Collaborative Multi-Robot Planning with Gaussian Belief Propagation (RA-L’23)
12. PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning (RA-L’19)
13. Mobile Robot Path Planning in Dynamic Environments through Globally Guided Reinforcement Learning (RA-L’20)
14. Multi-Agent Path Finding with Prioritized Communication Learning (ICRA’22)
15. Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding (AAAI’24)
16. Trajectory Planning for Quadrotor Swarms (T-RO’18)
17. Toward Efficient Physical and Algorithmic Design of Automated Garages (ICRA’23)
18. Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement in Large-Scale Warehouses (RA-L’23)

Student Projects

• Kinodynamically Feasible Multi-Agent Motion Planning by Rohan Chandrasekar and Burhanuddin Shirose

This work enhances Multi-Agent Path Finding (MAPF) by accommodating robots with complex, non-holonomic dynamics, addressing limitations of traditional methods that assume simpler holonomic robots. We developed a pipeline that constructs individual graphs for each agent, merging them to facilitate collision-free trajectory generation. Our approach utilizes space-time A* for path generation and Priority Planning to manage inter-agent conflicts. We also integrate these algorithms with ROS to test on RC cars in a simulated environment, demonstrating the practicality of our method for dynamic, real-world applications in advanced robotic systems.

• Improving RHCR with PIBT2 by Vineet Tambe

Multi-agent path finding (MAPF) is a challenging task that involves determining conflict-free paths for multiple agents within a given environment. The domain of MAPF has garnered significant attention due to its applicability in various real-world scenarios, ranging from robotics and transportation to video games and virtual simulations. This paper delves into the challenges posed by MAPF and explores state-of-the-art solutions aimed at enhancing efficiency and scalability. Specifically, this paper focuses on enhancing the Rolling-Horizon Collision Resolution (RHCR) algorithm, designed for life-long MAPF scenarios where agents continuously receive new goals. This project aims to augment RHCR by integrating the Priority Inheritance with Backtracking (PIBT) algorithm and a dummy path mechanism for prioritized planning purposes. The PIBT-based approach provides a comprehensive solution strategy for the one-shot MAPF problem, while achieving comparable or better solution quality in terms of service time and makespan. The report summarizes valuable learnings from the project.

• Improving Switchable TPG Optimization by He Jiang and Muhan Lin

During the execution of a MAPF plan, agents may suffer from unexpected delays. The execution framework TPG overly restricts the order in which agents visit a specific location, which typically leads to unnecessary waits in such scenarios. Switchable TPG provides a framework to optimize the visiting orders depending on the delays. However, current solutions based on mixed integer linear programming or naive-version graph-based search are not fast enough to be applied in real-time large-scale settings. This project aims to speed up the baseline graph-based search algorithm with multiple techniques, such as dependency grouping, stronger heuristics, incremental implementation, and focal search.

• ML-EECBS - Learning a better cost-to-go heauristic for EECBS by Arvind Car and Amey Sheth

EECBS is arguably the most advanced suboptimal variant of CBS. One of the salient features of EECBS is that it uses online learning to obtain an inadmissible heuristic that estimates the cost of the solution below each high-level node in order to guide the high-level search. In this paper, we investigate further runtime reduction for EECBS by calculating a more accurate inadmissible cost-to-go heuristic. We propose a support vector-based lightweight machine learning model that is trained to observe the features of the high-level search and use them to more accurately predict the cost-to-go values while generating nodes.

• MAPF-Based Multi-Robot Autonomous Exploration with Task Assignment in Unknown Space by Xiaoyang Zhan, Akshay Raman and Christopher Suzuki

In multi-robot exploration, we revolutionize planning with MAPF algorithms, optimizing path allocation to reduce sensor overlap. Robots navigate grid-based subspaces, orchestrating targets and paths via TAPF. MAPF guides agents to ensure collision-free navigation, while local planners adapt within subspaces. Centralized data integration offers a comprehensive view while the decentralized local planner allows for dynamic path generation and subregion decision making. Our approach pioneers a distinct global planning strategy, bridging dense map exploration with 3D space intricacies. The dynamic interplay between global and local planner optimizes performance, offering a cutting-edge solution to autonomous exploration challenges.

• Multi-Agent Path Finding for Collaborative Robot Fleets in Dynamic Environments by Dhruv Tyagi, Kshitij Kabeer and Hariharan Ravichandran

Existing Multi-Agent Path Finding algorithms and implementations assume that the agents themselves do not bring about many changes to their environments. Although, there are applications ranging from autonomous construction, agriculture to re-configurable warehouses, where different types of agents can make changes to the environment they are operating in. Some agents can clear obstacles while others can even make obstacles. This project explores 3 approaches to solve the scenarios that have agents which can move temporary obstacles to allow for other agents to reach their goal. The approaches are derived from conventional centralized algorithms, namely Prioritized Planning and Conflict-based Search.

• Multi-Agent Motion Planning with Diffusion Models by Yorai Shaoul

An exciting frontier in robotics is the coordinated use of multiple robots to solve complex tasks. Even though single-agent skills have been significantly improved by data-driven methods, multi-agent coordination remains challenging. Training a multi-agent system requires exponentially more data compared to single-agent learning, and retraining is necessary for each new team configuration. In this project, we propose a method for coordinating multiple agents while only requiring learning single-agent models. We leverage advancements in encoding motion planning as inference in a diffusion model, and propose an approach to yield valid multi-agent solutions by combining single-agent models in a search-based framework.

• Improving Safe Execution Policies for Multi-Arm Motion Planning by Philip Huang, Sandhya Vidyashankar and Haoyue Liu

In this work, we focus on multi-robot arm manipulation to advance dexterous industrial assembly. We aim to develop a collision-free, efficient multi-arm motion planning policy that can account for execution uncertainties such as delays and enable real robot execution. We build upon the standard multi-agent path finding (MAPF) execution policy to the more general case in continuous space and also incorporate random path shortcutting to further improve policy execution performance. Our findings reveal that this technique significantly improves the overall makespan, with our TPG framework outperforming standard baselines in various multi-robot manipulation scenarios.

• TAPF Approaches for Collaborative Multi-Arm Motion Planning by Jiaying Wei

This project looks into TAPF Approaches for multi-robot motion planning in the context of Architectural Engineering Construction application, specifically with Modular integrated mass-customization. It explores scalability, planning strategies, and efficiencies in MRS under a collaboration scenario where robot groups must plan and operate upon work objects with mutual constraints instead of explicit target information. The result of this project proposed a pipeline solution for parallel modular processing with multi-manipulator systems. It defines the specific application for this cellular setup in modular, mass-customized manufacturing. In addition, it provides detailed solutions to key problems of composite-goal finding, iterative re-assignment of robot groups, and adaptation to de-coupled MAPF algorithms in state-of-the-art.

• Muti-Agent Path Finding with Topological Guidance for UAVs by Brandon Rishi

Multi-agent path finding (MAPF) serves to generate collision free paths for a set of agents. Issues arise when tasked to solve in a complicated continuous space. For single agent problems, sampling based approaches have demonstrated success. When coupled with topoloigical methods, performance improves in these constricted environments. Topolgical guided MAPF approaches have further shown to improve planning in these difficult environments. In this work we extend existing topology-guided MAPF work to a three dimensional space. We demonstrate our approach's capacity to navigate complex environments and quickly find solutions. Furthermore, we showcase how topology provides an edge over non-topology-guided equivalents.