16891: Multi-Robot Planning and Coordination
Robotics Institute, Carnegie Mellon University, Spring 2024
Last update: 11-04-2023
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
- Decentralized (Multi-Robot) Planning and Coordination
- (Multi-Robot) Planning with Robot Dynamics
- Learning for (Multi-Robot) Planning and Coordination
- (Multi-Robot) Applications
Course Activities and Grading
| Paper presentation | 20% |
| Paper reading | 14% |
| Coding assignment | 16% |
| Research project | 50% |
Tentative Schedule
| Date | Format | Topics |
|---|---|---|
| 01/17 | Lecture 0 | Overview |
| 01/22 | Lecture 1 | Basics of MAPF: A*-based Optimal Methods |
| 01/24 | Lecture 2 | Basics of MAPF: CBS-based Optimal Methods |
| 01/29 | Lecture 3 | Basics of MAPF: Optimization-based Optimal Methods |
| 01/31 | Lecture 4 | Basics of MAPF: CBS-based Bounded-suboptimal Methods |
| 02/05 | Lecture 5 | Basics of MAPF: Greedy Methods (PP, LNS, etc) |
| 02/07 | Guest Lecture 1 | Pathfinding for 10k Agents By Keisuke Okumura (University of Cambridge) |
| 02/12 | Lecture 6 | Planning and Coordination under Uncertainty: Robust Planning and Robust Execution |
| 02/14 | Paper Discussion 1 | Planning and Coordination under Uncertainty |
| 02/19 | Lecture 7 | Combined Task and Path Planning: Anonymous MAPF |
| 02/21 | Lecture 8 | Combined Task and Path Planning: TAPF |
| 02/26 | Lecture 9 | Decentralized Planning and Coordination |
| 02/28 | Paper Discussion 2 | Decentralized Planning and Coordination |
| 03/04 | Spring Break - No Class | |
| 03/06 | Spring Break - No Class | |
| 03/11 | Lecture 10 | Planning with Robot Dynamics |
| 03/13 | Paper Discussion 3 | Planning with Robot Dynamics: Combination with Sampling-based Methods |
| 03/18 | Project Discussion | |
| 03/20 | Lecture 11 | Learning for Planning and Coordination: Speeding Up Search with Learning Techniques |
| 03/25 | Paper Discussion 4 | Learning for Planning and Coordination: MARL |
| 03/27 | Lecture 12 | Applications: Warehouse Robots Part 1 |
| 04/01 | Lecture 13 | Applications: Warehouse Robots Part 2 |
| 04/03 | Guest Lecture 2 | Guest Lecture by Jingkai Chen (Symbotic) |
| 04/08 | Paper Discussion 5 | Applications: Drones |
| 04/10 | Lecture 14 | Applications: Multi-Arm Assembly |
| 04/15 | Lecture 15 | Applications: Flatland Challenge |
| 04/17 | Project Presentation 1 | |
| 04/22 | Project Presentation 2 | |
| 04/24 | Project Presentation 3 |