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:

Course Activities and Grading

  
Paper presentation20%
Paper reading14%
Coding assignment16%
Research project50%

Tentative Schedule

DateFormatTopics
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: Optimization-based Optimal Methods
01/31Lecture 4Basics of MAPF: CBS-based Bounded-suboptimal Methods
02/05Lecture 5Basics of MAPF: Greedy Methods (PP, LNS, etc)
02/07Guest Lecture 1Pathfinding for 10k Agents By Keisuke Okumura (University of Cambridge)
02/12Lecture 6Planning and Coordination under Uncertainty: Robust Planning and Robust Execution
02/14Paper Discussion 1Planning and Coordination under Uncertainty
02/19Lecture 7Combined Task and Path Planning: Anonymous MAPF
02/21Lecture 8Combined Task and Path Planning: TAPF
02/26Lecture 9Decentralized Planning and Coordination
02/28Paper Discussion 2Decentralized Planning and Coordination
03/04Spring Break - No Class 
03/06Spring Break - No Class 
03/11Lecture 10Planning with Robot Dynamics
03/13Paper Discussion 3Planning with Robot Dynamics: Combination with Sampling-based Methods
03/18Project Discussion 
03/20Lecture 11Learning for Planning and Coordination: Speeding Up Search with Learning Techniques
03/25Paper Discussion 4Learning for Planning and Coordination: MARL
03/27Lecture 12Applications: Warehouse Robots Part 1
04/01Lecture 13Applications: Warehouse Robots Part 2
04/03Guest Lecture 2Guest Lecture by Jingkai Chen (Symbotic)
04/08Paper Discussion 5Applications: Drones
04/10Lecture 14Applications: Multi-Arm Assembly
04/15Lecture 15Applications: Flatland Challenge
04/17Project Presentation 1 
04/22Project Presentation 2 
04/24Project Presentation 3