Multi-Agent Pathfinding for Railway Routing

Abstract

Research in railway operations has mostly focused on operations research methods. However, these real-world problems have a state-based nature, which makes them very suitable for AI models, such as the Multi-Agent Pathfinding problem, where agents move in a grid and need to be routed from their start to their goal location without colliding with each other. The core aspect of problems like train shunting and train dispatching is routing, which is often not the main focus of current mathematical formulations. Therefore, we apply the state-of-the-art algorithms to the railway problems of shunting and dispatching and study their usability for routing trains. The Multi-Agent Pathfinding problem is often solved with one of two algorithms: conflict-based search (a two-stage algorithm detecting conflicts between individual paths and using A* search to find new conflict-free paths), and branch-cut-and-price (a linear program adding cuts (row generation) based on problem-specific constraints, and finding new paths to be selected that satisfy all constraints using a pricer). We modify these algorithms to include more railway details. First, we allow for the matching of train units (i.e., ensure the necessary train units of a certain type are available for departure) by specifying goals for agent (type) groups instead of single agent goals. Moreover, we add goal sequences for servicing stations and agents of different sizes, and we study specific aspects of the railway infrastructure to exploit in the algorithm. Finally, we show the use of Multi-Agent Pathfinding solvers in different railway settings and analyze the conditions for success.