Education

Replanning in advance for train scheduling (2025)

Refactoring for AI planning (2025)

Using PDDL models to solve TUSS: How to model TUSS as an Automated Planning problem and solve it

Nazariy Lonyuk (2024)

Due to the increased demand for train travel, train operators are considering increasing their rolling stock. Before achieving this, they must enhance the capacity of their shunting yards. This is attempted by improving methodologies for solving the Train Unit Shunting and Servicing (TUSS) problem. To address the TUSS problem, a planner determines routes on shunting yards for trains, ensuring they visit designated service tracks before parking in a configuration that facilitates a smooth departure. TUSS is a well-studied problem, and various approaches have been proposed. The first approach capable of solving real-world, complete TUSS instances is a local search method introduced by van den Broek et al. In this thesis, we explore an alternative approach using PDDL models. PDDL is the standard language for describing Automated Planning problems. Automated Planning is a well-established field within artificial intelligence, and new, improved algorithms are continually developed to solve PDDL models for problems similar to TUSS. In this thesis, we design a detailed model in PDDL and propose several methods to simplify the model so that planning algorithms perform more efficiently compared to the detailed model. When solving simplified models, a post-processing routine is employed to generate detailed shunting plans. The performance of several model-independent PDDL planners was analysed, and the best-performing planner was identified as Temporal FastDownward. By analysing plans obtained from experiments, we identified areas for improvement. Based on this knowledge, we developed a new TUSS-specific planner called Train Order Preserving Search (TOPS). TOPS employs a search algorithm with effective pruning of symmetrical states and a custom heuristic that guides the search towards states where the order of trains aligns with the departure order. TOPS significantly outperformed Temporal FastDownward in these experiments.

Inferring Robust Plans with a Rail Network Simulator

Reuben Gardos Reid (2023)

Over 700 trains in the Netherlands are used daily for passenger transportation. Train operations involve tasks like parking, recombination, cleaning, and maintenance, which take place in shunting yards. The train unit shunting problem (TUSP) is a complex planning problem made more difficult by uncertainties such as delays. Most existing approaches overlook these disturbances and the approaches that consider them incorporate heuristics to enhance the robustness of their solutions to disturbances. This thesis proposes an alternative approach: utilizing probabilistic programming to turn an existing planning algorithm and simulator into a generative model of the TUSP. The model introduces disturbances without the need to modify the planning algorithm or simulator. Through two types of inference, we infer a distribution of robust solutions for the TUSP. Empirical results demonstrate the effectiveness of our approach for inferring robust plans in small-scale scenarios.

Learning patterns in train position data (2024)

Given a set of GPS locations of trains in a railway hub, we want to be able to reconstruct the original plan of which this data is the realization. The goal of the project is to automatically detect patterns that can help in creating new plans. Each of the sub-projects uses a different aspect of the problem to focus the pattern detection on.

• Classifying locations by identifying station specific patterns
• Examining Manual Solutions of the Train Unit Shunting Problem to find Train Type Patterns
• Detecting Patterns in Train Position Data of Trains in Shunting Yards
• Automatic Detection of Whether a Solution of the Train Unit Shunting Problem (TUSP) is a Week or a Weekend Day
• Analysis of Shunting Yard Usage and Train Unit Clustering

Landmarks in planning (2024)

Landmarks in AI planning give the must-reach intermediate goals and have provided significant reductions in planning time. Different algorithms have been developed for extracting landmarks from problem files and using them in a planner. The goal of the project is to implement these different algorithm in the SymbolicPlanners library in Julia to allow for easier use of these landmark algorithms in future research. Each of the sub-projects implements a different landmark algorithm.

• Exploring the effectivity of AND/OR landmark extraction on modern planning domains
• Landmarks in Planning: Using landmarks as Intermediary Goals or as a Pseudo-Heuristic
• Re-evaluating the Full Landmark Extraction Algorithm: A Performance Analysis of FULL
• Reproducing the concept of ordered landmarks in planning: The effect of ordered landmarks on plan length in forward search
• Extending SymbolicPlanners with forward propagation landmark extraction

Comparing planners for railway planning (2023)

AI planning can formally define real-world planning problems, like the train unit shunting problem. An initial PDDL model for this problem is provided and the is extended to be more realistic. The goal of the project is to compare previously developed planners on their performance for the new problem definition. Each of the sub-projects focuses on a different aspect of the problem to include.

• Mixed-direction train shunting with numerical planning: Approach to support train departures at any time during the shunting plan
• Comparing planners for rail planning in PDDL: How multiple shunting yard layouts can be created in PDDL to replicate real-world scenarios
• Utilizing General Planners to Solve the Train Unit Shunting Problem Extended with Servicing
• Optimizing the PDDL domain of TUSP to improve planner performance: Modifying the domain to improve planner execution time, plan quality, and problem solvability
• Dealing with conflicting trains: Effectively avoiding and resolving conflicts during shunting