Multi-Agent Path Finding
Speaker:
Peter J. Stuckey, Monash University, Australia
Date and Time
February 8 2019, 14:15 - 15:00
Location
Polacksbacken, ITC, room 1311.
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.