IPAB Workshop-27/04/2023

Title: Exploiting Geometric Constraints in Large-Scale Multi-Agent Pathfinding Abstract: In an environment where multiple agents move simultaneously, Multi-Agent Pathfinding (MAPF) is the problem of finding conflict-free paths that lead each agent from its start to its end position. With automated warehousing gaining more and more traction in industrial applications (e.g. Amazon), large-scale MAPF has become the focus of intense research in the last few years. Nonetheless, MAPF for a large fleet of robots remains challenging since the problem is intrinsically hard (optimal and, in some cases, even approximately optimal path planning is NP-hard). In this talk, after introducing MAPF and its applications, I will explore a specific class of paths that are constructed by taking the agents’ shortest paths from the start to the goal locations and adding safe delays at the beginning of the paths, which guarantee that they are non-conflicting. Safe delays are calculated by exploiting a set of fundamental geometric constraints among the distances between all agents’ start and goal locations. I will then discuss how a new, fast and lightweight algorithm can be devised based on such delays to solve MAPF problems. Finally, I will conclude by presenting an extensive experimental evaluation, showing that this technique returns low-cost solutions and runs several orders of magnitudes faster than related methods while addressing problems with thousands of agents.  Bio: Sara Bernardini is a Professor of AI at Royal Holloway University of London, the Principal Research Scientist in AI and Data Science at the National Oceanography Centre and a Fellow at the Alan Turing Institute. Her research is in decision-making for autonomous systems, lying at the intersection of different disciplines: AI, cognitive robotics, and mathematical optimisation. Most of her work focuses on planning for single-agent and multi-agent systems to enable them to act intelligently in real time despite resource and environmental constraints, noisy or faulty sensors, imperfect abilities and extreme conditions. Prof Bernardini has deployed robust systems in several safe-critical applications to support autonomous operations in space, underwater, underground, offshore and nuclear facilities. She has also worked in the surveillance and logistics domains. Her extensive publication record in world-leading conferences and journals explores the theoretical foundations for designing autonomous systems that act rationally, responsibly and effectively in the real world. Prof Bernardini was the AAAI-23 Associated General Chair, and she is the ICAPS-2024 Program co-Chair.