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
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
- (Multi-Robot) Planning with Robot Dynamics
- Decentralized (Multi-Robot) Planning and Coordination
- 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% |
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: CBS-based Optimal Methods |
| 01/31 | Lecture 4 | Basics of MAPF: CBS-based Bounded-suboptimal Methods |
| 02/05 | Lecture 5 | Basics of MAPF: Greedy Methods |
| 02/07 | Guest Lecture 1 | Basics of MAPF: Breaking Tradeoffs: Extremely Scalable MAPF Algorithms By Keisuke Okumura (University of Cambridge) |
| 02/12 | Lecture 6 | Combined Task and Path Planning: Anonymous MAPF and TAPF |
| 02/14 | Paper Discussion 1 | Combined Task and Path Planning: Recent Progress (p1,p2,p3) |
| 02/19 | Lecture 7 | Planning and Coordination under Uncertainty: Robust MAPF with Robust Execution |
| 02/21 | Paper Discussion 2 | Planning and Coordination under Uncertainty: Recent Progress (p4,p5,p6) |
| 02/26 | Lecture 8 | Planning with Robot Dynamics: Overview |
| 02/28 | Paper Discussion 3 | Planning with Robot Dynamics: Recent Progress (p7,p8,p9) |
| 03/04 | Spring Break | No Class |
| 03/06 | Spring Break | No Class |
| 03/11 | Lecture 9 | Decentralized Planning and Coordination: ORCA and Shard System |
| 03/13 | Lecture 10 | Decentralized Planning and Coordination: Distributed PP and Distributed CSP |
| 03/18 | Paper Discussion 4 | Decentralized Planning and Coordination: Recent Progress (p10,p11,p12) |
| 03/20 | Lecture 11 | Lifelong and Online Planning: Task and Path Planning |
| 03/25 | Lecture 12 | Lifelong and Online Planning: Interleaving Planning and Execution |
| 03/27 | Lecture 13 | Learning for Planning and Coordination: Overview |
| 04/01 | Paper Discussion 5 | Learning for Planning and Coordination: Recent Progress (p13,p14,p15) |
| 04/03 | Lecture 14 | Applications: Multi-Arm Assembly |
| 04/08 | Paper Discussion 6 | Applications: Recent Progress (p16,p17,p18) |
| 04/10 | Guest Lecture 2 | Applications: Guest Lecture by Liron Cohen (Mujin) |
| 04/15 | Guest Lecture 3 | Applications: Guest Lecture by Jingkai Chen (Symbotic) |
| 04/17 | Lecture 15 | Applications: MAPF Competitions |
| 04/22 | Project Presentation 1 | |
| 04/24 | Project Presentation 2 |
Reading List
- Idle Time Optimization for Target Assignment and Path Finding in Sortation Centers (AAAI’20)
- A New Approach for Multiagent Combinatorial Path Finding (T-RO’23)
- Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree (MRS’23)
- A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph (ICAPS’20 Workshop)
- Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution (AAAI’24)
- Offline Time-Independent Multiagent Path Planning (T-RO’23)
- Adaptive Robot Coordination: A Subproblem-based Approach for Hybrid Multi-Robot Motion Planning (arXiv’23)
- Scalable Multi-Robot Motion Planning for Congested Environments With Topological Guidance (RA-L’23)
- Quick Multi-Robot Motion Planning by Combining Sampling and Search (IJCAI’23)
- Walk, Stop, Count, and Swap: Decentralized Multi-Agent Path Finding With Theoretical Guarantees (RA-L’20)
- Distributing Collaborative Multi-Robot Planning with Gaussian Belief Propagation (RA-L’23)
- PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning (RA-L’19)
- Mobile Robot Path Planning in Dynamic Environments through Globally Guided Reinforcement Learning (RA-L’20)
- Multi-Agent Path Finding with Prioritized Communication Learning (ICRA’22)
- Decentralized Monte Carlo Tree Search for Partially Observable Multi-agent Pathfinding (AAAI’24)
- Trajectory Planning for Quadrotor Swarms (T-RO’18)
- Toward Efficient Physical and Algorithmic Design of Automated Garages (ICRA’23)
- Double-Deck Multi-Agent Pickup and Delivery: Multi-Robot Rearrangement in Large-Scale Warehouses (RA-L’23)