The Multi-Agent Path Finding Problem

Database and Artificial Intelligence Group hosted a talk by Peter Stuckey

ABSTRACT

Multi-agent pathfinding (MAPF) is a planning problem which asks us to coordinate the movements of a team of agents: from a set of unique starting locations to a set of unique target positions all while avoiding collisions. This problem appears in a variety of different application areas including warehouse logistics, office robots, aircraft-towing vehicles and computer games. Often the the environment in which agents operate is given as an undirected graph, such a grid. Common objectives then include minimising the total arrival time of all agents (aka. sum-of-costs) and minimising the arrival of the last agent at its target location (aka. makespan). In each of these common settings MAPF is known to be NP-hard (Yu and LaValle 2013) to solve optimally. Interest in the problem has nevertheless generated a wide variety of methods including optimal, suboptimal and and bounded suboptimal techniques. In this talk we will examine the conflict based search approach to multi-agent path finding, which is currently state-of-the-art, and show how it can be improved by reasoning about symmetry and sub-problem splitting.

Bio

Professor Peter J. Stuckey is a Professor in the Faculty of Information Technology at Monash University, and project leader in the Data61 CSIRO laboratory. Peter Stuckey is a pioneer in constraint programming, the science of modelling and solving complex combinatorial problems.  His research interests include: discrete optimization; programming languages, in particular declarative programming languages; constraint solving algorithms; bioinformatics; and constraint-based graphics. He enjoys problem-solving in any area, having publications in e.g. databases, timetabling, and system security, and working with companies such as Oracle and Rio Tintoon problems that interest them. Peter Stuckey received a B.Sc and Ph.D both in Computer Science from Monash University in 1985 and 1988 respectively. In 2009 he was recognized as an ACM Distinguished Scientist. In 2010 he was awarded the Google Australia Eureka Prize for Innovation in Computer Science for his work on lazy clause generation. He was awarded the 2010 University of Melbourne Woodward Medal for most outstanding publication in Science and Technology across the university. In 2019 he was elected as a Fellow of the Association for the Advancement of Artificial Intelligence.

Peter Stuckey, University of Melbourne