16891: Multi-Robot Planning and Coordination

Robotics Institute, Carnegie Mellon University, Spring 2026

Last update: 8-15-2026

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 optimization.

Course topics:

Each of the following 8 topics will be covered by 2-5 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
• (Multi-Robot) Lifelong and Online Planning
• Learning for (Multi-Robot) Planning and Coordination
• (Multi-Robot) Applications

Course Activities and Grading

Summary of reading lists and research projects from previous years can be found here: spring 2025, spring 2024, and spring 2023.

Schedule

Reading List

1. Conflict-Based Steiner Search for Multi-Agent Combinatorial Path Finding (RSS’18)
2. Multi-Robot Task and Motion Planning With Subtask Dependencies (RAL’20)
3. pc-dbCBS: Kinodynamic Motion Planning of Physically-Coupled Robot Teams (RAL’25)
4. Space-Time Graphs of Convex Sets for Multi-Robot Motion Planning (IROS’25)
5. GCBF+: A Neural Graph Control Barrier Function Framework for Distributed Safe Multiagent Control (TRO’25)
6. Distributing Collaborative Multi-Robot Planning with Gaussian Belief Propagation (RAL’23)
7. Local Guidance for Configuration-Based Multi-Agent Pathfinding (AAAI’26)
8. SOCIALMAPF: Optimal and Efficient Multi-Agent Path Finding With Strategic Agents for Social Navigation (RAL’23)
9. Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning (AAAI Workshop’26)
10. RoboBallet: Planning for multirobot reaching with graph neural networks and reinforcement learning (ScienceRobotics’25)
11. Multi-agent Path Finding for Mixed Autonomy Traffic Coordination (IROS’24)
12. Trajectory Planning for Heterogeneous Robot Teams (IROS’18)

Student Projects

• Solving TAPF via Poisson Potential Fields and Heuristic Word Reduction in Permutation Groups by Boxiang (William) Fu

We present a new formulation of target allocation and path finding (TAPF) as a constrained word problem in a permutation group generated by graph-edge transpositions. Building on this view, we propose a two-level solver combining global Poisson potential-field guidance with local greedy word reduction. The high-level planner dynamically allocates goals without fixed assignments, while the low-level planner constructs feasible local moves through pebble-motion steps, blocker displacement, and backtracking. Experiments show strong performance on large benchmarks with up to 200 agents, low runtime, and support for delay handling without full replanning.

• Learning-Guided Conflict Selection for Optimal Multi-Agent Path Finding by Zihan Qu

This project studies learning-guided conflict selection for optimal Conflict-Based Search in grid-based multi-agent path finding. Starting from a standard CBS solver with space-time A*, I collect rollout-labeled conflict-tree traces and train a lightweight MLP to rank candidate conflicts. The learned selector preserves optimality because it changes only conflict ordering. On held-out MovingAI instances, it reduces search effort on congested maze cases, cutting average CT expansions from 58.7 to 48.0 and runtime from 4.84 s to 3.99 s, while showing mixed performance on easier open maps.

• Multi-Agent Task Allocation for Coordinated Multi-Robot Exploration by Po-Ting Ko, Ya-Ting Hsu, and Tzu-Cheng Tsai

Multi-robot exploration must balance efficiency against coordination cost. Greedy frontier allocation deadlocks, while full Multi-Agent Path Finding (MAPF) is too slow for online replanning. We ask how much coordination is actually needed when a modern navigation stack already handles local collisions. On the same scenario, we compare three allocators: a distance-greedy baseline, a Priority-Based Search (PBS) MAPF evaluator that re-plans the greedy assignment with space-time A*, and a Multi-Agent Task Allocation (MATA) scheme that refines frontiers and matches robots via the Hungarian algorithm. PBS cuts mission time by 45.4% over greedy; MATA cuts it a further 71.5% with the most balanced workload, suggesting frontier-selection coordination outperforms post-hoc path-conflict resolution.

• Scalable Multi-Agent Reinforcement Learning for Partially Observable Competitive Games by Alex DeWeese and Stephen Oduh

Previously we developed a theoretical framework called the Locally Interdependent Multi-Agent MDP, that admits scalable near optimal solutions and naturally handles partial observability for a large class of "navigation style" environments. We extend the results to the two-team zero sum setting where local groups of agents will be taking actions according to a local Nash equilibria (with time varying groups depending on the position). We show that taking a local Nash equilibria policy is exponentially close to the centralized policy which computes the Nash equilibria for all the agents together. Then we empirically observe this in the Pommerman game.

• MATTER: Multi-Agent Task Planning for Triage and Exploration by Tom Gao, Joshua Pen, and Ranai Srivastav

We present MATTER, a framework for multi-agent task allocation and path planning in partially unknown environments with heterogeneous robots. Inspired by the DARPA Triage Challenge, our system integrates auction-based task allocation with Conflict-Based Search (CBS) for collision-free multi-agent path finding. We compare three variants of our algorithm, the Availability-Constrained Sequential Single-Item Auction (SSIA) with variants of reward-shaped bidding against a greedy baseline on procedurally generated maps containing obstacles, buildings, and triage objectives. Experimental results demonstrate that SSIA-Collateral achieves the lowest average completion time (avg. ~39.7 steps) among our baselines.

• Dynamic DAG Generation and Solving for Multi-Robot Abstract Task Execution by Arnav Shah and Sachet Korada

Enabling robots to execute high-level natural language tasks remains a central challenge in robotics. Large language models (LLMs) demonstrate strong reasoning capabilities, but they struggle with long-horizon planning, feasibility, and coordination, particularly in multi-agent settings. We propose a structured planning framework in which an LLM emits a directed acyclic graph (DAG) of action primitives that is consumed by a multi-agent execution pipeline combining Hungarian task allocation, a four-tier motion planner (Prioritized Planning, with Conflict-Based Search, Priority-Based Search, and BFS with a collision guard as bounded fall- backs), and an online recovery mechanism for failed placements. We evaluate the system on nine LLM-generated DAGs spanning five AI2-THOR scenes and five household tasks, sweeping from one to four agents (36 trials total). Across the matrix we observe per-task makespan speedups of 1.50–2.34×, near-perfect task completion (100% lenient completion on 34 of 36 trials, 83.8% strict completion on average), and a planner-tier hit-rate showing that just Prioritized Planning is sufficient for 80% of all plan calls (over 92% excluding two outlier trials), with the bounded fallbacks engaged only under high-density coordination.

• Online Rolling-Horizon Multi-Robot Arm Planning with Vector-Accelerated Incremental Shortcutting by Mehul Menon

Offline multi-robot arm planners idle every robot for tens of seconds while building a full activity-dependency graph. We present an online rolling-horizon framework that begins execution from a partial ADG and incrementally appends new windows while the robots are already moving. A sweep-based algorithm discovers inter-robot collision dependencies in O((N/k)^2) instead of O(N^2), and time-budgeted incremental shortcutting recovers offline plan quality. On Kinova GP4 LEGO assembly with 2-4 arms, the system cuts time-to-first-move by 5.9-22.2x and on the larger Vessel task beats offline makespan by 5.9-7.6%.

• Scalable Real World Imitation Learning (SRAW-IL) by Chenxi Xu, CheHsuan Lee, Hongyi Sam Dong, and Pin-Wen Wang

Scalable Real-World Aware Imitation Learning (SRAW-IL) bridges the gap between grid-based Lifelong Multi-Agent Path Finding and realistic robot execution. We integrate ExecTimeNet, a neural surrogate for physics-based execution cost, into the windowed Large Neighborhood Search refinement loop to favor plans that are not only collision-free but also physically efficient. Evaluated in Lifelong SMART, our method improves throughput by 3.36% over a strong heuristic baseline. The project introduces a novel execution-aware MAPF planner and highlights key challenges in aligning planning objectives with real-world dynamics.

• Robust Multi-Robot Motion Planning Under Disturbance Uncertainty by Chengyang Zhao and Zongtai Li

Multi-robot motion planning in continuous space is sensitive to execution uncertainty, which can make nominally safe plans unsafe. We study robust MRMP under bounded time- and space-dependent disturbances. Building on ST-GCS, we introduce disturbance-aware trajectory reservation using pairwise safety radii that capture robot size and uncertainty. This modifies the space-time decomposition and conflict checking. Experiments show that nominal methods are unsafe under disturbance, while sampling-based baselines are slower and lower quality. Our method maintains ST-GCS efficiency while improving robustness.

• An Exploration of MAPF for Tethered Robots in 3D Space by Emily Newman

Tethered robots are useful for extreme environments and situations where it is beneficial to have guaranteed power and communications. However, multiple tethered robots performing complex actions present the problem of tether tangles restricting further motion. This work explores applications of MAPF for multi-tethered-robot path planning. We design a conflict-based search algorithm using topological 2-braids as a representation of a tangle and present initial findings. We also explore a prioritized planning method and a CBS-based no-path-overlap approach, and compare to standard CBS without consideration for tangles. The work concludes with ideas for future exploration based on initial results.

• Pressure-Aware Priority-Based Search for Lifelong Multi-Agent Path Finding with Workstations by Ayush Varshney

Warehouse robots crowd workstations when departure and arrival overlap with service. We study this setting in lifelong multi-agent path finding using Rolling-Horizon Collision Resolution with Priority-Based Search (RHCR+PBS). Pressure-Aware PBS acts when a queue becomes crowded. It preserves service and departure, keeps one arriving robot moving toward service, and softly discourages other robots from entering the queue zone during replanning. Across corridor-dense and open layouts, this method improves throughput and queue delay over standard PBS and a conflict-ordering baseline. These results show how selectively regulating workstation crowding can improve efficiency across congestion patterns.

• MAPF Framework for Optimal Finger Planning on Dexterous Hands by Joshua Tsang and Nimalan Suresh

Dexterous robotic manipulation in cluttered workspaces is bottlenecked by the high dimensionality of multi-fingered hands and the lack of deterministic guarantees in current planners. We present a hierarchical framework that decouples a 7-DoF arm from a 16-DoF Allegro Hand by formulating finger pre-grasp planning as a multi-agent pathfinding problem. A sampling-based RRT* generates a collision-free wrist trajectory, which then serves as a moving coordinate frame for four independent space-time A* searches, one per finger. A Conflict-Based Search layer detects inter-finger collisions in the integrated trajectory and injects vertex constraints back into the low-level searches until the joint plan is conflict-free.

• Scaling Multi-Robot Diffusion Planning with RRT Warm-Start and Lossless Skip-Replan by Tzu-Yi Yang

Multi-Robot Motion Planning with Diffusion (MMD) couples a learned diffusion sampler with Conflict-Based Search (CBS), but repeated diffusion calls dominate planning time and cap scalability. We propose two accelerations. RRT warm-start seeds each agent's sampler with an RRT-Connect skeleton and reduces denoising from 25 steps to 3. BatchHit is a lossless skip-replan that reuses parent-batch trajectories already satisfying new CBS hard constraints. Across 100 trials in two environments and up to 25 agents, our method has the fastest planning time in every cell. At 25 agents, only our method solves the cluttered environment.

• Lifelong Multi-Agent Pathfinding in Unknown Environments with Limited Communication by Srikar Gouru, Krrish Jain, and Nilay Marathe

This work studies decentralized coordination among a set of agents operating in a constrained 2D environment with dynamically environment changes, such as obstacles being picked up or placed down. Agents complete either one-shot or lifelong MAPF tasks while simultaneously exploring the environment and have limited communication. The objective is to efficiently complete all targets without centralized control while minimizing travel time and maximizing throughput. We utilize single-agent planning techniques for real-time and incremental heuristic planning, as well as multi-agent decentralized collision shielding methods and auction-based task allocation. Our methods provide a fast but suboptimal method for completing all tasks.

• Typed Lifelong MAPF with TP-Inspired Assignment and ITA-CBS Replanning by Aravind Gnanasekaran

This paper studies typed lifelong multi-agent path finding for heterogeneous robot fleets with homogeneous robots per robot type, where online pickup and delivery tasks must be assigned only to compatible robot types. The proposed hybrid planner combines TP-inspired online task assignment with ITA- CBS fixed-target joint replanning. TP handles lifelong task gener- ation, compatibility filtering, and pickup/delivery target updates, while ITA-CBS repairs the current robot paths for collision-free execution. Experiments show that the hybrid improves conflict- aware coordination in smaller typed settings, but repeated centralized replanning becomes computationally expensive as the number of robot types increases.

• Multi-agent UAV Exploration and Agile Navigation Through Tree Canopy by Nicole Chan

This literature review proposes a lightweight multi-agent UAV system for agile navigation through tree canopies, prioritizing gap detection over high-fidelity mapping to reduce computational overhead. By analyzing centralized planning (MUI-TARE) and decentralized approaches (RACER), the work selects optimal strategies for efficient map representation and task assignment in unknown, cluttered environments. It further examines perception-driven methods that directly identify traversable openings, enabling rapid decision-making without exhaustive reconstruction.

• Resilient Multi-Agent Task Scheduling via Reassignment Flexibility by Esme Rubinstein

Robust task scheduling in multi-agent systems must account for the possibility of unexpected agent failures. Existing approaches either typically add temporal protection to activity durations or reactively reassign tasks after failures occur. We propose a proactive scheduling approach that maximizes reassignment flexibility by preserving feasible futures across multiple agents. Our method seeks an initial assignment maximizing a flexibility objective combining temporal slack with feasible reassignment options, formalized through direct reassignment measures. An incremental heuristic search selects assignments that maximize aggregate flexibility across the schedule. We evaluate against three baselines, minimum makespan, maximum completion time margin, and maximum slack, using randomized agent unavailability simulations. Across 900 generated scenarios, our approach results in 21% fewer dropped tasks than minimum makespan as scenario density increases, and outperforms all baselines in total agent failure scenarios where reassignment to a new agent is critical.

• RESCUE – Reasoning over Earth Scenes for Coordinated UAS–UGS Exploration by Swastik Mahapatra

Project RESCUE presents a heterogeneous multi-agent planning framework for search-and-rescue exploration in unknown outdoor environments. Using satellite data and drone imagery simulation, the system builds traversability and cost maps that encode robot-specific capabilities and environmental constraints. Heuristic priority rules assign regions to UAVs and UGVs based on distance from the launch zone and mobility limits, enabling coordinated coverage with A*-based planning. The approach improves mission efficiency by distributing exploration across complementary robot platforms while preserving geospatial accuracy and supporting real-world GPS waypoint execution.

• MotionToken-MAPF: Coordination in Mixed Autonomy via Language-Based Motion Prediction by Emanuel Munoz

The coexistence of Connected and Automated Vehicles (CAVs) and Human-Driven Vehicles (HDVs) presents a significant challenge for autonomous systems, as CAVs must plan safe multi-agent trajectories while accounting for the unpredictability of human behavior. This work proposes a hierarchical framework to address this challenge in two stages: behavior forecasting of HDVs followed by constrained multi-agent pathfinding. Our approach leverages MotionLM as a motion predictor for modeling interactions through discrete tokens. The forecasted trajectories are then used to generate collision-free paths for CAVs along with a Multi-phase A* low level controller. The framework is evaluated in a rampway-merge scenario in simulation.

• Local Socially Aware Planning for Multi-Agent Path Finding by Vaibhav Sanjay

Autonomous robotic fleets often employ variations of multi-agent path finding (MAPF) planners for trajectory planning in warehouses. Although highly scalable, these planners are not designed to account for planning in human-shared environments. Diffusion-based methods are capable of generating "humanlike" trajectories for multi-robot systems in human-shared environments. However, these planners typically do not take advantage of modern grid-based MAPF planning techniques, limiting their scalability. We develop a hybrid algorithm that incorporates scalable MAPF planning to generate optimized plans when possible, and diffusion-based human-aware plans only when needed. This idea leads to better performance compared to MAPF or diffusion alone.

• Real-Time Lazy Constraint Addition Search for Heterogeneous Multi-Agent Path Finding with Mixed Footprints and Speeds by Guadalupe Bernal

Traditional MAPF assumes identical point agents that move one cell per timestep. As robot collaboration increases in popularity, extensions of traditional methods have attempted to bridge the gap between theory and real applications. MC-CBS supports variable agent sizes and CCBS supports variable agent speeds in continuous time. HetPIBT is a recent approach that handles both size and speed heterogeneity, but is a greedy local method that lacks completeness guarantees. We present both a full-horizon and real-time extension to LaCAM that supports agents of varying square footprint sizes and different integer movement periods.

• Learning-Augmented Congestion Pricing for Lifelong Multi-Agent Path Finding in Warehouses by Pranav Kumara

Robots in warehouse fleets independently compute shortest paths that converge on the same corridors, creating congestion that stalls throughput. We present a rolling-horizon reservation planner that embeds online congestion pricing inside the time-extended A* cost function, adapting prices to observed traffic without any offline precomputation. An ablation study across fleet sizes up to 200 robots shows that pricing alone improves throughput by 25% and reduces mean task latency by 9% over the unpriced backbone. Adding an online-learned congestion potential degrades performance due to per-expansion computational overhead, identifying caching and label quality as the key gaps to close.