Abstract

In the Multi-Agent Path Finding (MAPF) problem, we study how to efficiently compute non-colliding paths for a set of agents on a given network, where each agent seeks a path from its source to its target. An important measure of solution quality is the length of the schedule, that is, the length of the longest path (including waiting times).

MAPF has many real-world applications, including warehouse management, airport towing, autonomous vehicles, robotics, digital entertainment, and computer games.

In this talk, we will discuss which structural properties of a network lead to efficient exact algorithms and which do not. In particular, we will show that computing collision-free schedules is easier on dense (almost complete) networks than on sparse ones (such as tree-like or star-like networks). We will also discuss how additional restrictions can be exploited to design efficient algorithms for sparse networks.

This presentation is based on the works: Exact Algorithms and Lower bounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024), Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures (AAAI 2025) and Solving Multiagent Path Finding on Highly Centralized Networks (AAAI 2025).

These results are part of a joint collaboration with Foivos Fioravantes, Dušan Knop, Jan Matyáš Křištan, Michal Opler (Czech Technical University), and Tung Anh Vu (Charles University).

Short bio

My name is Nikolaos Melissinos. I hold a diploma in Applied Mathematical and Physical Sciences from the National Technical University of Athens and a Ph.D. in Theoretical Computer Science from Paris-Dauphine University. Following my Ph.D., I worked as a postdoctoral researcher at the Czech Technical University and I am currently at Charles University. Lately, my research is focused on theoretical aspects of problems arising in Multi-Agent Systems, Computational Social Choice, and Artificial Intelligence.