Abstrakt
In the Coordinated Motion Planning problem, sometimes referred to as Multiagent Pathfinding (MAPF), we are given a graph together with the starting positions and destinations of k distinct robots. The goal is to route a set of k robots to their destinations without any collision while minimizing a certain objective target—prominently the number of time steps in the schedule, i.e., the makespan, or the total length traveled by the robots. In this talk, we will discuss some parameterized algorithmic results related to the problem and its generalizations.