16891: Multi-Robot Planning and Coordination
Robotics Institute, Carnegie Mellon University, Spring 2025
Last update: 12-19-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 optimization.
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 | 14% |
| Coding assignments | 30% |
| Research project | 41% |
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 Bounded-suboptimal Methods |
| 01/29 | Lecture 4 | Basics of MAPF: Greedy Search-based Methods |
| 02/03 | Lecture 5 | Basics of MAPF: Greedy Rule-based Methods |
| 02/05 | Lecture 6 | Task Planning: Multi-Robot Task Allocation |
| 02/10 | Lecture 7 | Task Planning: Combined Task and Path Planning |
| 02/12 | Paper Discussion 1 | Task Planning: Recent Progress (p1,p2,p3) |
| 02/17 | Lecture 8 | Motion Planning: Planning and Coordination under Uncertainty |
| 02/19 | Lecture 9 | Motion Planning: Planning with Robot Dynamics |
| 02/24 | Paper Discussion 2 | Planning and Coordination under Uncertainty: Recent Progress (p4,p5,p6) |
| 02/26 | Project Discussion | |
| 03/03 | Spring Break | No Class |
| 03/05 | Spring Break | No Class |
| 03/10 | Lecture 10 | Decentralized Planning: ORCA |
| 03/12 | Lecture 11 | Decentralized Planning: Distributed PP and Distributed CSP |
| 03/17 | Paper Discussion 3 | Decentralized Planning: Recent Progress (p7,p8,p9) |
| 03/19 | Lecture 12 | Lifelong and Online Planning: Task and Path Planning |
| 03/24 | Lecture 13 | Lifelong and Online Planning: Interleaving Planning and Execution |
| 03/26 | Guest Lecture 1 | TBA |
| 03/31 | Paper Discussion 4 | Other Multi-Robot Planning Problems: (p10,p11,p12) |
| 04/02 | Lecture 14 | Learning for Planning and Coordination: Overview |
| 04/07 | Paper Discussion 5 | Learning for Planning and Coordination: Recent Progress (p13,p14,p15) |
| 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 |