16891: Multi-Robot Planning and Coordination

Robotics Institute, Carnegie Mellon University, Spring 2024

Last update: 12-29-2023

More details can be found in course canvas.

Course Introduction


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.


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%

Tentative Schedule

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)