-
PhD Dissertation Defense - Jingyao Ren
Thu, Dec 05, 2024 @ 11:00 AM - 01:00 PM
Thomas Lord Department of Computer Science
University Calendar
Title: Advancements in Understanding the Empirical Hardness of the Multi-Agent Pathfinding Problem
Date: December 5TH, 11:00 AM to 1:00 PM
Location: EEB 110
Committee: T.K. Satish Kumar (Chair), Stefanos Nikolaidis, Feifei Qian, Sven Koenig
Abstract: Multi-Agent Path Finding~(MAPF) involves finding collision-free paths for agents in shared environments and is crucial for applications like automated warehouses and swarm control. While solving MAPF optimally is NP-hard, many real-world instances are solvable efficiently, though factors affecting instance hardness remain unclear. This dissertation explores MAPF empirical hardness, addressing what makes instances hard, how to predict hardness, and ways to generate challenging instances. Key contributions include formalizing empirical hardness research in MAPF, introducing the MAPFAST algorithm selection framework, identifying map connectivity as a critical factor, and demonstrating methods to generate instances with varying hardness.Location: Hughes Aircraft Electrical Engineering Center (EEB) - 110
Audiences: Everyone Is Invited
Contact: Jingyao Ren
