One robot cannot build a bridge in a week, but a coordinated team of humanoids, quadrupeds, and construction robots could. My thesis is motivated by a future full of multi-agent systems: robots running warehouses, humanoids constructing buildings, aerial and ground robots delivering packages in urban environments, and autonomous rovers collaborating on the moon. One core problem in these multi-robot teams is effective multi-agent motion planning; robots in the teams need to be able to efficiently find collision-free paths in order to complete their tasks. Multi-agent motion planning is challenging as the number of possible solutions grows exponentially with the number of agents.

Multi-Agent Path Finding (MAPF) is a subset of multi-agent motion planning that typically focuses on simple planar robots but can be generalized to other robot systems. The majority of modern MAPF methods compute complete start-goal (global) paths, however computing partial (local) paths offers several advantages including faster planning, adaptability to changes, and compatibility with decentralized systems. Additionally, local planning makes it easier to incorporate machine learning as it makes the prediction problems more tractable and reduces data collection requirements. Despite these benefits, local planning is challenging as it is likely to get stuck in livelock or deadlock. Thus, the main objective of my thesis is to effectively solve global multi-agent motion planning leveraging local policies, learned or planned, while avoiding the typical pitfalls of local reasoning.

This thesis has three significant contributions.
The first main contribution is showing how augmenting local machine learning (ML) policies with heuristic search for MAPF can dramatically improve scalability compared to just ML policies by themselves.
The second main contribution is designing different algorithmic approaches for maintaining solution guarantees (i.e., not getting stuck in deadlock) with partial planning, including using a learned ML policy.
These first two contributions focus on MAPF in the discretized settings with identical/homogeneous robots; compared to real world systems in continuous space/time with heterogeneous robots. Thus, my last main contribution is generalizing MAPF techniques to heterogeneous teams in continuous space/time with each robot running different motion planners (e.g., A*, RRT, optimization, diffusion, and reinforcement learning), and using MAPF to coordinate a team of physical quadrupeds. Taken together, my thesis develops effective local planning MAPF policies/algorithms and demonstrates how MAPF can be used for complex heterogeneous teams.

From a technical perspective, my thesis shows how leveraging algorithmic search-based planning techniques with machine learning is a promising area of research. From a robotics technology perspective, I hope my work helps enable future efficient and helpful multi-robot teams.