REU Project

Graph-based Multi-Robot Path Planning (MRPP), also known as Multi-Agent Path Finding (MAPF), seeks to quickly find high-quality paths for routing a large number of robots. MRPP/MAPF has numerous important applications, such as enabling the coordination of thousands of robots at Amazon warehouses. In this project, we leverage graph connectivity to design better MAPF algorithms. In particular, we focus on 3-regular graphs, and note the sharp structural transition that occurs between 2 and 3-regular graphs. We integrate the routing-via-matchings theorem of Alon, Chung, and Graham and give a transfer argument to simulate each matching as a MAPF instance.