16891: Multi-Robot Planning and Coordination
Robotics Institute, Carnegie Mellon University, Spring 2025
Last update: 10-22-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-5 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) Task Allocation and Path Planning
- Learning for (Multi-Robot) Planning and Coordination
- (Multi-Robot) Applications
Course Activities and Grading
| Paper presentation | 15% |
| Paper reading | 17% |
| Coding assignment | 20% |
| Research project | 48% |
Summary of reading lists and research projects from previous years can be found here: spring 2024, spring 2023.
Tentative Schedule
| Date | Format | Topics |
|---|---|---|
| 01/13 | Lecture 0 | Overview |
| 01/15 | Lecture 1 | Basics of MAPF: A*-based Optimal Methods |
| 01/20 | Martin Luther King Day | No Class |
| 01/22 | Lecture 2 | Basics of MAPF: CBS-based Optimal Methods |
| 01/27 | Lecture 3 | Basics of MAPF: CBS-based Optimal Methods |
| 01/29 | Lecture 4 | Basics of MAPF: Bounded-suboptimal Methods |
| 02/03 | Lecture 5 | Basics of MAPF: Greedy Methods |
| 02/05 | Lecture 6 | Combined Task and Path Planning: Anonymous MAPF and TAPF |
| 02/10 | Paper Discussion 1 | Combined Task and Path Planning: Recent Progress (p1,p2,p3) |
| 02/12 | Lecture 7 | Planning and Coordination under Uncertainty: Robust MAPF with Robust Execution |
| 02/17 | Paper Discussion 2 | Planning and Coordination under Uncertainty: Recent Progress (p4,p5,p6) |
| 02/19 | Lecture 8 | Planning with Robot Dynamics: Overview |
| 02/24 | Paper Discussion 3 | Planning with Robot Dynamics: Recent Progress (p7,p8,p9) |
| 02/26 | Guest Lecture 1 | TBA |
| 03/03 | Spring Break | No Class |
| 03/05 | Spring Break | No Class |
| 03/10 | Lecture 9 | Decentralized Path Planning: ORCA and Shard System |
| 03/12 | Lecture 10 | Decentralized Path Planning: Distributed PP and Distributed CSP |
| 03/17 | Paper Discussion 4 | Decentralized Path Planning: Recent Progress (p10,p11,p12) |
| 03/19 | Lecture 11 | Decentralized Task Allocation: Auction-based methods |
| 03/24 | Paper Discussion 5 | Decentralized Task Allocation: Recent Progress (p13,p14,p15) |
| 03/26 | Lecture 12 | Lifelong and Online Planning: Task and Path Planning |
| 03/31 | Lecture 13 | Lifelong and Online Planning: Interleaving Planning and Execution |
| 04/02 | Lecture 14 | Learning for Planning and Coordination: Overview |
| 04/07 | Paper Discussion 6 | Learning for Planning and Coordination: Recent Progress (p16,p17,p18) |
| 04/09 | Guest Lecture 2 | TBA |
| 04/14 | Lecture 15 | Applications |
| 04/16 | Lecture 16 | Applications |
| 04/21 | Project Presentation 1 | |
| 04/23 | Project Presentation 2 |