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:

Course Activities and Grading

  
Paper presentation15%
Paper reading17%
Coding assignment20%
Research project48%

Schedule

DateFormatTopics
01/17Lecture 0Overview
01/22Lecture 1Basics of MAPF: A*-based Optimal Methods
01/24Lecture 2Basics of MAPF: CBS-based Optimal Methods
01/29Lecture 3Basics of MAPF: CBS-based Optimal Methods
01/31Lecture 4Basics of MAPF: CBS-based Bounded-suboptimal Methods
02/05Lecture 5Basics of MAPF: Greedy Methods
02/07Guest Lecture 1Basics of MAPF: Breaking Tradeoffs: Extremely Scalable MAPF Algorithms By Keisuke Okumura (University of Cambridge)
02/12Lecture 6Combined Task and Path Planning: Anonymous MAPF and TAPF
02/14Paper Discussion 1Combined Task and Path Planning: Recent Progress (p1,p2,p3)
02/19Lecture 7Planning and Coordination under Uncertainty: Robust MAPF with Robust Execution
02/21Paper Discussion 2Planning and Coordination under Uncertainty: Recent Progress (p4,p5,p6)
02/26Lecture 8Planning with Robot Dynamics: Overview
02/28Paper Discussion 3Planning with Robot Dynamics: Recent Progress (p7,p8,p9)
03/04Spring BreakNo Class
03/06Spring BreakNo Class
03/11Lecture 9Decentralized Planning and Coordination: ORCA and Shard System
03/13Lecture 10Decentralized Planning and Coordination: Distributed PP and Distributed CSP
03/18Paper Discussion 4Decentralized Planning and Coordination: Recent Progress (p10,p11,p12)
03/20Lecture 11Lifelong and Online Planning: Task and Path Planning
03/25Lecture 12Lifelong and Online Planning: Interleaving Planning and Execution
03/27Lecture 13Learning for Planning and Coordination: Overview
04/01Paper Discussion 5Learning for Planning and Coordination: Recent Progress (p13,p14,p15)
04/03Lecture 14Applications: Multi-Arm Assembly
04/08Paper Discussion 6Applications: Recent Progress (p16,p17,p18)
04/10Guest Lecture 2Applications: Guest Lecture by Liron Cohen (Mujin)
04/15Guest Lecture 3Applications: Guest Lecture by Jingkai Chen (Symbotic)
04/17Lecture 15Applications: MAPF Competitions
04/22Project Presentation 1 
04/24Project Presentation 2 

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

Group 1

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.


Group 2

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.


Group 3

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.


Group 4

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.


Group 5

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.


Group 6

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.


Group 7

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.


Group 8

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.


Group 9

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.


Group 10

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.