Personal tools
You are here: Home CG seminar 2022 Multi-Agent Path Finding: New Analysis, Problem Variants and Algorithms
« August 2022 »
Log in

Forgot your password?

Multi-Agent Path Finding: New Analysis, Problem Variants and Algorithms

Wednesday, November 24th, 4:10pm Tel Aviv time (3:10pm CET, 9:10am NY time)


Oren Salzman, Technion


The problem of Multi-Agent Path Finding (MAPF) calls for finding a set of
conflict-free paths for a fleet of agents operating in a given environment. It
has applications in diverse domains such as warehouse automation, pipe routing
and more. This problem has been extensively studied by the planning community
in the last decade. Indeed, the tools developed to address this problem were
used to dramatically outperform learning-based approaches in the recent 2020
Flatland Challenge---a NeurIPS competition trying to determine how to
efficiently manage dense traffic on rail networks.
Arguably, the state-of-the-art approach to computing optimal solutions to the
MAPF problem is Conflict-Based Search (CBS). In this talk I will describe
recent work where we revisit the complexity analysis of CBS to provide tighter
bounds on the algorithm's run-time in the worst-case. Our analysis paves the
way to better pinpoint the parameters that govern (in the worst case) the
algorithm's computational complexity. Following this theoretical analysis, I
will shift to describe two new variants of the MAPF problem, both motivated by
real world applications, and describe algorithmic approaches to solve these
The talk is based on work done by Ofir Gordon, Nir Greshler, David Weinstein
and Nitzan Madar with the support of Yuval Filmus and Nahum Shimkin and myself.
Document Actions