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
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 | 20% |
| Paper reading | 16% |
| Coding assignment | 15% |
| Research project | 49% |
Schedule
| Date | Format | Topics | |
|---|---|---|---|
| 01/17 | Lecture 0 | Overview | |
| 01/19 | Lecture 1 | Basics of MAPF: A*-based Optimal Methods | |
| 01/24 | Lecture 2 | Basics of MAPF: CBS-based Optimal Methods | |
| 01/26 | Lecture 3 | Basics of MAPF: CBS-based Optimal Methods | |
| 01/31 | Lecture 4 | Basics of MAPF: CBS-based Bounded-suboptimal Methods | |
| 02/02 | Lecture 5 | Basics of MAPF: Greedy Methods | |
| 02/07 | Lecture 6 | Planning and Coordination under Uncertainty: Robust MAPF with Robust Execution | |
| 02/09 | Guest Lecture 1 | A Glimpse of Integer Programming and Applications to MAPF by Edward Lam (Monash University) | |
| 02/14 | Guest Lecture 2 | Learning-based Safe Control and Planning with Applications in Drones by Guanya Shi (CMU) | |
| 02/16 | Paper Discussion 1 | Planning and Coordination under Uncertainty: Robust MAPF with Robust Execution (p1,p2) | |
| 02/21 | Paper Discussion 2 | Decentralized Planning and Coordination (p3,p4) | |
| 02/23 | Paper Discussion 3 | Decentralized Planning and Coordination (p5,p6) | |
| 02/28 | Lecture 7 | Combined Task and Path Planning | |
| 03/02 | Lecture 8 | Planning with Robot Dynamics: Overview | |
| 03/07 | Spring Break | No Class | |
| 03/09 | Spring Break | No Class | |
| 03/14 | Paper Discussion 4 | Planning with Robot Dynamics: Combination with Sampling-based Methods (p7,p8) | |
| 03/16 | Paper Discussion 5 | Learning for Planning and Coordination: Learning for Planning (p9,p10) | |
| 03/21 | Paper Discussion 6 | Learning for Planning and Coordination: MARL (p11,p12) | |
| 03/23 | Paper Discussion 7 | Learning for Planning and Coordination: MARL (p13,p14) | |
| 03/28 | Lecture 9 | Applications: Warehouse Robots | |
| 03/30 | Lecture 10 | Applications: Warehouse Robots | |
| 04/04 | Paper Discussion 8 | Applications: Drones (p15,p16) | |
| 04/06 | Lecture 11 | Applications: Multi-Arm Assembly | |
| 04/11 | Lecture 12 | Applications: Flatland Challenge | |
| 04/13 | Spring Carnival | No Class | |
| 04/18 | Project Presentation 1 | Groups 1, 2, 3, and 4 | |
| 04/20 | Project Presentation 2 | Groups 5, 6, 7, 8, and 9 | |
| 04/25 | Project Presentation 3 | Groups 10, 11, 12, 13, and 14 | |
| 04/27 | Project Presentation 4 | Groups 15, 16, 17, 18, and 19 |
Student Projects
| Group | Title | Group members |
|---|---|---|
| 1 | Improving MAPFAST: A Deep Algorithm Selector for Multi-Agent Path Finding using Shortest Path Embeddings | Harshit Agrawal, Jigarkumar Patel, Manuj Trehan |
| 2 | Multi-goal Task Assignment and Path Finding with Temporal Constraints | Kaushik Balasundar, Narendar Sriram |
| 3 | Towards Online Planning for Drone Formations in Obstacle-Free Environments | Matthew Booker, Sundaram Seivur |
| 4 | Selective Communication for Cooperative Perception in End-to-End Autonomous Driving | Hsu-Kuang Chiu |
| 5 | Optimal Task Assignment Conflict-Based Search with Precedence and Temporal Constraints | Yu Quan Chong |
| 6 | Enhancing Multi-Drone Coordination for Filming Group Behaviours in Dynamic Environments | Aditya Rauniyar |
| 7 | Hierarchical Planning in Multi-Agent Collective Construction | Zejian Huang |
| 8 | Evidence Accumulation Enables Robust Sparse Communication in MARL Applications | Seth Karten, Siva Kailas |
| 9 | Multi-Agent Task Allocation for Temporally Located Tasks in a Dynamic, Distributed Environment | Gialon Kasha |
| 10 | Multi-Agent Multi-Objective Ergodic Search | Akshaya Kesarimangalam Srinivasan |
| 11 | Multi-Agent Path Planning for Communication Coverage Applications | Prasanna Sriganesh |
| 12 | Heterogeneous Multi-Agent Motion Planning in Continuous Space with Incremental Constraint Resolution (HICBS-MP) | Anthony Kyu, Hardik Singh, Shivani Sivakumar |
| 13 | Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks | Alexander Pletta, Benjamin Younes, David Russell |
| 14 | Parallellized Intelligent Conflict Based Search | Kwangkyun Kim, Sabrina Shen, Jaekyung Song |
| 15 | Conflict Based Search using Theta* with Task Scheduling | Sankalp Chopkar, Dhanvi Sreenivasan |
| 16 | Model Predictive Control for Scalable Multi-Robot Motion Planning | Ardalan Tajbakhsh, Shruti Gangopadhyay, Charvi Gupta |
| 17 | Propulsion-Free Cross-Track Control of a LEO Small-Satellite Constellation with Differential Drag | Jacob B. Willis |
| 18 | Arbitrarily Scalable Environment Generators via Neural Cellular Automata | Yulun Zhang |
| 19 | Hierarchical Planning for Multi-agent Collective Construction | Shambhavi Singh |
Reading List
- A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph (ICAPS’20 workshop)
- Time-Independent Planning for Multiple Moving Agents (AAAI’21)
- Distributed Multi-agent Navigation Based on Reciprocal Collision Avoidance and Locally Confined MAPF (CASE’21)
- Complete Decentralized Method for On-Line Multi-Robot Trajectory Planning in Well-formed Infrastructures (ICAPS’15)
- Walk, Stop, Count, and Swap: Decentralized Multi-Agent Path Finding With Theoretical Guarantees (RA-L’20)
- Shard Systems: Scalable, Robust, and Persistent Multi-Agent Path Finding with Performance Guarantees (AAAI’22)
- Representation-Optimal Multi-Robot Motion Planning Using Conflict-Based Search (RA-L’21)
- Cooperative Multi-Robot Sampling-Based Motion Planning with Dynamics (ICAPS’17)
- Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Search (AAAI’21)
- CTRMs: Learning to Construct Cooperative Timed Roadmaps for Multi-agent Path Planning in Continuous Spaces (AAMAS’22)
- 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)
- Learning Selective Communication for Multi-Agent Path Finding (RA-L’22)
- MAPPER: Multi-Agent Path Planning with Evolutionary Reinforcement Learning in Mixed Dynamic Environments (IROS’20)
- Trajectory Planning for Quadrotor Swarms (TRO’18)
- Efficient Large-Scale Multi-Drone Delivery Using Transit Networks (ICRA’20)