Home Events AI-based Optimisation Seminar Series 29 Sept 2021

Date

29 Sep 2021

Time

AEST AUSTRALIA
4:00 pm - 5:00 pm

Cost

$0

AI-based Optimisation Seminar Series 29 Sept 2021

Speaker Professor Peter Stuckey, OPTIMA

Combinatorial Optimisation for Multi-Agent Path Finding

Multi-Agent Path Finding (MAPF) is a problem that requires one to compute a set of collision-free paths for a team of moving agents. The problem appears in variety of practical applications including warehouse logistics, traffic management, aircraft towing and computer games. The general version of the problem (minimizing makespan or sum of path costs, on graphs with parallel actions and rotations) is known to be NP-hard. One of the leading methods for solving MAPF optimally, employs a strategy known as Conflict-based Search (CBS). The central idea is to plan paths for each agent independently and resolve collisions by branching the current plan. Each branch is a new candidate plan wherein one agent or the other is forced to find a new path that avoids the selected collision. When we examine CBS from an optimisation perspective, it is clearly a form of (Logic-based) Benders Decomposition. This begs the question: can we use combinatorial optimisation techniques to tackle the MAPF problem efficiently? In this talk, I will show two approaches: the first uses core-guided search together with a no good learning Constraint Programming solver; the second uses Branch-and-Cut-and-Price together with a MIP solver. Both methods prove to be highly competitive to previous CBS approaches.

Peter Stuckey is the Deputy Director of OPTIMA, and a Professor in the Faculty of Information Technology at Monash University, and a project leader in the Data61 CSIRO laboratory.

WED 29 SEPT AUGUST 4PM – 5PM AEST

ZOOM Meeting ID: 873 1557 5255; Password: 778635

Event Flyer

More Info

SEMINAR RECORDING

The event is finished.

Date

29 Sep 2021
OPTIMA

Advancing an industry-ready optimisation toolkit, while training a new generation of industry practitioners and over 120 young researchers, who will vanguard a highly skilled workforce of change agents for industrial transformation.

Monash University
Clayton, Victoria, 3080
Australia

University of Melbourne
Parkville, Victoria, 3010
Australia

© 2021 ARC Industrial Transformation Training Centre in Optimisation Technologies, Integrated Methodologies and Applications (OPTIMA)