16891: Multi-Robot Planning and Coordination

Robotics Institute, Carnegie Mellon University, Spring 2023

Last update: 5-30-2023

More details can be found in course canvas.

Course Introduction


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.


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 reading16%
Coding assignment15%
Research project49%


01/17Lecture 0Overview 
01/19Lecture 1Basics of MAPF: A*-based Optimal Methods 
01/24Lecture 2Basics of MAPF: CBS-based Optimal Methods 
01/26Lecture 3Basics of MAPF: CBS-based Optimal Methods 
01/31Lecture 4Basics of MAPF: CBS-based Bounded-suboptimal Methods 
02/02Lecture 5Basics of MAPF: Greedy Methods 
02/07Lecture 6Planning and Coordination under Uncertainty: Robust MAPF with Robust Execution 
02/09Guest Lecture 1A Glimpse of Integer Programming and Applications to MAPF by Edward Lam (Monash University) 
02/14Guest Lecture 2Learning-based Safe Control and Planning with Applications in Drones by Guanya Shi (CMU) 
02/16Paper Discussion 1Planning and Coordination under Uncertainty: Robust MAPF with Robust Execution (p1,p2) 
02/21Paper Discussion 2Decentralized Planning and Coordination (p3,p4) 
02/23Paper Discussion 3Decentralized Planning and Coordination (p5,p6) 
02/28Lecture 7Combined Task and Path Planning 
03/02Lecture 8Planning with Robot Dynamics: Overview 
03/07Spring BreakNo Class 
03/09Spring BreakNo Class 
03/14Paper Discussion 4Planning with Robot Dynamics: Combination with Sampling-based Methods (p7,p8) 
03/16Paper Discussion 5Learning for Planning and Coordination: Learning for Planning (p9,p10) 
03/21Paper Discussion 6Learning for Planning and Coordination: MARL (p11,p12) 
03/23Paper Discussion 7Learning for Planning and Coordination: MARL (p13,p14) 
03/28Lecture 9Applications: Warehouse Robots 
03/30Lecture 10Applications: Warehouse Robots 
04/04Paper Discussion 8Applications: Drones (p15,p16) 
04/06Lecture 11Applications: Multi-Arm Assembly 
04/11Lecture 12Applications: Flatland Challenge 
04/13Spring CarnivalNo Class 
04/18Project Presentation 1Groups 1, 2, 3, and 4 
04/20Project Presentation 2Groups 5, 6, 7, 8, and 9 
04/25Project Presentation 3Groups 10, 11, 12, 13, and 14 
04/27Project Presentation 4Groups 15, 16, 17, 18, and 19 

Student Projects

GroupTitleGroup members
1Improving MAPFAST: A Deep Algorithm Selector for Multi-Agent Path Finding using Shortest Path EmbeddingsHarshit Agrawal, Jigarkumar Patel, Manuj Trehan
2Multi-goal Task Assignment and Path Finding with Temporal ConstraintsKaushik Balasundar, Narendar Sriram
3Towards Online Planning for Drone Formations in Obstacle-Free EnvironmentsMatthew Booker, Sundaram Seivur
4Selective Communication for Cooperative Perception in End-to-End Autonomous DrivingHsu-Kuang Chiu
5Optimal Task Assignment Conflict-Based Search with Precedence and Temporal ConstraintsYu Quan Chong
6Enhancing Multi-Drone Coordination for Filming Group Behaviours in Dynamic EnvironmentsAditya Rauniyar
7Hierarchical Planning in Multi-Agent Collective ConstructionZejian Huang
8Evidence Accumulation Enables Robust Sparse Communication in MARL ApplicationsSeth Karten, Siva Kailas
9Multi-Agent Task Allocation for Temporally Located Tasks in a Dynamic, Distributed EnvironmentGialon Kasha
10Multi-Agent Multi-Objective Ergodic SearchAkshaya Kesarimangalam Srinivasan
11Multi-Agent Path Planning for Communication Coverage ApplicationsPrasanna Sriganesh
12Heterogeneous Multi-Agent Motion Planning in Continuous Space with Incremental Constraint Resolution (HICBS-MP)Anthony Kyu, Hardik Singh, Shivani Sivakumar
13Lifelong Multi-Agent Path Finding for Online Pickup and Delivery TasksAlexander Pletta, Benjamin Younes, David Russell
14Parallellized Intelligent Conflict Based SearchKwangkyun Kim, Sabrina Shen, Jaekyung Song
15Conflict Based Search using Theta* with Task SchedulingSankalp Chopkar, Dhanvi Sreenivasan
16Model Predictive Control for Scalable Multi-Robot Motion PlanningArdalan Tajbakhsh, Shruti Gangopadhyay, Charvi Gupta
17Propulsion-Free Cross-Track Control of a LEO Small-Satellite Constellation with Differential DragJacob B. Willis
18Arbitrarily Scalable Environment Generators via Neural Cellular AutomataYulun Zhang
19Hierarchical Planning for Multi-agent Collective ConstructionShambhavi Singh

Reading List

  1. A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph (ICAPS’20 workshop)
  2. Time-Independent Planning for Multiple Moving Agents (AAAI’21)
  3. Distributed Multi-agent Navigation Based on Reciprocal Collision Avoidance and Locally Confined MAPF (CASE’21)
  4. Complete Decentralized Method for On-Line Multi-Robot Trajectory Planning in Well-formed Infrastructures (ICAPS’15)
  5. Walk, Stop, Count, and Swap: Decentralized Multi-Agent Path Finding With Theoretical Guarantees (RA-L’20)
  6. Shard Systems: Scalable, Robust, and Persistent Multi-Agent Path Finding with Performance Guarantees (AAAI’22)
  7. Representation-Optimal Multi-Robot Motion Planning Using Conflict-Based Search (RA-L’21)
  8. Cooperative Multi-Robot Sampling-Based Motion Planning with Dynamics (ICAPS’17)
  9. Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Search (AAAI’21)
  10. CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces (AAMAS’22)
  11. PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning (RA-L’19)
  12. Mobile Robot Path Planning in Dynamic Environments through Globally Guided Reinforcement Learning (RA-L’20)
  13. Learning Selective Communication for Multi-Agent Path Finding (RA-L’22)
  14. MAPPER: Multi-Agent Path Planning with Evolutionary Reinforcement Learning in Mixed Dynamic Environments (IROS’20)
  15. Trajectory Planning for Quadrotor Swarms (TRO’18)
  16. Efficient Large-Scale Multi-Drone Delivery Using Transit Networks (ICRA’20)