Multi-agent pathfinding with discrete speeds - and its application for vehicle road networks

Abstract

This work contributes to the multi-agent path-finding problem (MAPF) by extending existing algorithms with optimal and efficient routing for roads with multiple lanes and intersections. It also considers the continuous case, where agents are forbidden from performing actions during a non-discrete interval of time. Further, a method to plan for the speed of agents is introduced. In order to create a strong base for this problem, rigorous mathematical models are defined and proved to have properties of both completeness and optimality. Experiments are used to validate the abstract models.