RAIL: Responsible Decision Support for Efficient and Dynamic Railway Systems
The RAIL Lab is a research lab dedicated to developing AI technology to increase the overall logistic rail capacity. The lab works towards algorithmic support to ensure safe and reliable logistic operations and capacity planning that is trusted by human experts. The lab’s research goal is to tackle long-term challenges related to the dynamic management of transport demand on railway nodes, with the aim of responding quickly and adequately to changing circumstances. RAIL Lab is a collaboration between Delft University of Technology, Utrecht University, Dutch Railways, and ProRail.
Public transportation has always been an important public service to facilitate mobility for all people. Rail is a major public transportation backbone that links cities all over Europe. It is green, safe, fast, and reliable, and expected to replace a significant part of the current air traffic between these cities. Due to its design principle, rail is a high-density mode of transportation with respect to the environment. However, to be able to make full use of the rail infrastructure capacity, some technological barriers need to be overcome. Traditionally, rail infrastructure capacity assignment to operators has been rather static, as laid down in a timetable that is made well in advance and remains valid for a long time period. Uncertainties are anticipated by adding slack regarding time and space.
To increase the overall logistic rail capacity, the industry has to reduce this slack and act on the actual circumstances and near-future expectations more often, which requires adaptive rail capacity assignment and dynamic, data-driven traffic control. This presents researchers and developers with difficult challenges related to the specific features of the rail infrastructure, as being characterized by a network of ‘pipelines’; that is, trains cannot overtake each other, and sequencing decisions are crucial but difficult to make due to their far-reaching effect. AI technology could enable a major breakthrough and hence deliver an important contribution to a permanently affordable, reliable, sustainable, and resilient public transportation system, accessible to all and ready for the next decades.
Two goals for the rail system are difficult to reconcile: on the one hand, meeting a growing demand for transport and, on the other hand, a robust operation. Passengers want seats and therefore need more trains, and for sustainable transport, we would like to use more cargo trains, but more trains on the same infrastructure are more likely to cause disruptions, and high-frequency dynamics in the case of cargo further complicates the situation. The incorporation of slack makes the system more robust but reduces the track capacity. This capacity is difficult and expensive to expand, especially in large cities. Significant work has been done on finding a good trade-off by proper timetabling, but many capacity issues nowadays appear around the stations, at the so-called railway nodes. This lab thus addresses robust operation on and around these railway nodes.
We investigate whether, and how, an AI entity can be developed that supports human experts in answering logistics questions so that the transport system becomes more robust and the infrastructure is used as effectively as possible. Examples of these kinds of logistical questions are: what is a feasible shunting plan around railway nodes for the current situation? When is such a planning question not solvable? What is the logistics capacity of a railway node (station and shunting yard) under dynamic conditions? And what is the effect of a proposed adjustment of the rail infrastructure?
Throughout its run-time, the RAIL Lab will work towards algorithmic support to ensure safe and reliable logistic operations and capacity planning that is trusted by human experts in NS & ProRail. One outcome of the lab will be for trains to run with higher frequency and better punctuality and maximize seat availability for passengers so that people are more likely to choose rail over road. Another outcome is to have a more reliable estimate of available capacity and transport times for cargo companies that use rail to transfer goods. In order to achieve these outcomes, the long-term research challenges described in the Research section will be tackled. This will be done by addressing domain-related challenges regarding the dynamic management of transport demand on railway nodes: responding quickly and adequately to changing circumstances.
Target 9.1: Develop quality, reliable, sustainable, and resilient infrastructure, including regional and transborder infrastructure, to support economic development and human well-being, with a focus on affordable and equitable access for all.
Target 11.2: By 2030, provide access to safe, affordable, accessible, and sustainable transport systems for all, improving road safety, notably by expanding public transport, with special attention to the needs of those in vulnerable situations, women, children, persons with disabilities, and older persons.
Future planning of infrastructure usage requires a dynamic approach in which human operators interact with automated planning tools to jointly optimize the planning process. This research project aims to improve this interaction in the logistical planning process of the railways. The key scientific challenges are to identify which factors of planning processes are relevant for optimal decision-making by the joint human-AI system, how these factors as well as the plans computed by the algorithms can be explained to human operators, how the human operators can be better supported (e.g., when under stress or time-pressure), and how to inform algorithmic decision-making protocols with strategic human interventions.
A variety of methods from the social, behavioral, and AI sciences will be used. We will use qualitative methods to study how human planners at NS and ProRail currently operate. This study will reveal requirements, expectations, and potential pitfalls of human-AI interaction [1], specifically of interaction with (future) algorithmic planners. These results will be augmented with data science techniques to extract important factors from past decision-making and planning processes, to develop a (computational) cognitive model of the decision and planning process [2,5]. This model will serve as a benchmark for unsupported operator behavior. To specify the optimal decision support, we will experimentally identify the factors that contribute to the explainability of the algorithmic planner [3], as well as acceptability, trust, and joint decision-making efficiency. Through quantitative and modeling studies we then will compare which explanation formats provide the best decision support under stressful circumstances. A goal of automated systems is that humans can make strategic decisions, while the automated system makes the appropriate corresponding operational decisions [4]. Through qualitative studies, we will investigate the right moment and the right level at which humans can intervene.
[1] Janssen, C. P., Donker, S. F., Brumby, D. P., & Kun, A. L. (2019). History and future of human-automation interaction. International Journal of Human-Computer Studies, 131, 99-107.
[2] Kolvoort, I.R., Fisher, B, Van Rooij, R., Schultz, K., & Van Maanen, L. (submitted). Probabilistic causal reasoning under time pressure.
[3] Koopman, T. & Renooij, S. (2021) Persuasive contrastive explanations for Bayesian networks. Proc. of European Conference on Symbolic and Quantitative Approaches with Uncertainty, p 229-242
[4] Michon, J. A. (1985). A critical review of driver behavior models: What do we know, what should we do? In Human behavior and traffic safety (pp. 487-525). Plenum Press, NY.
[5] Dastani, M., Hulstijn, J., & van der Torre, L. (2005), How to decide what to do? European Journal of Operational Research 160(3): p 762-784
Service sites are very dynamic environments in which many disturbances take place with respect to the arrival of the trains (delays, differences in composition) and the service work (cleaning, inspection, maintenance). The challenge in this project is to deal with this. Therefore we aim to design algorithms that can construct shunting plans that are resilient against small changes in the original input and that can repair an initial plan with a minimum number of changes. To increase the acceptance of the algorithms by human planners, similar plans should be produced in similar circumstances, finding such easily adjustable base plans is a further challenge. We want to extend the usage of these algorithms to deal with similar challenges that play a role in freight train planning in the Rotterdam harbor area. Finally, the train traffic on a hub interferes with (freight) traffic on the main lines, which requires synchronization.
In an earlier PhD project, we developed, together with researchers from NS, the algorithms for the program HIP, see [1]. HIP uses Local Search to find solutions for a deterministic environment, in which all data are certain. To address the scientific challenges above, we must extend the ideas behind HIP in many ways. Thereto, we want to use techniques from the fields of Local Search, Directed Local Search, and Constraint Programming [2]. The resilience of a plan depends on its robustness, which determines how well it can cope with small disturbances. To find a resilient plan, it is important that the base solution is as robust as possible. We need to capture this in the objective of the search and investigate how to make the Local Search suitable for dealing with this objective. Robustness is difficult to capture, and therefore we have developed in [3] several surrogate robustness measures, which we want to apply here as a start. We further want to extend the techniques used in [4] to guide local search in an uncertain environment. Furthermore, many instances of the daily planning problem are very similar. Therefore, we want to find plans for these situations that are similar as well. We want to achieve this by starting with a robust base plan that, if necessary, we change to deal with the small differences between the daily instances, such that the number of changes is minimal. Hereto, we want to use Directed Local Search and Constraint Programming. In the case of a hub, the shunting between the railway yards will interfere with the train traffic on the lines that cross the hub. We enlarge the scope of the Local Search to synchronize the movements of the multiple carriers. This will result in much larger problem instances that are heavily constrained. We will investigate how to limit the computation time despite the increasing instance size to find resilient plans for this situation. This will be in cooperation with the PhD student that will work on research project 4.
[1] R.W. van den Broek, J.A. Hoogeveen, J.M. van den Akker, and B. Huisman (2021). A Local Search Algorithm for Train Unit Shunting with Service Scheduling. Transportation Science, published online nov 2021, https://doi-org.proxy.library.uu.nl/10.1287/trsc.2021.1090.
[2] E. Hebrard and N. Musliu (2020). Integration of constraint programming, artificial intelligence, and operations Research. LNCS proceedings, Vol. 12.296. Springer.
[3] Roel van den Broek, Han Hoogeveen, Marjan van den Akker (2018). How to measure robustness of shunting plans. 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS). OASICS, Vol. 65.
[4] Hoogeveen, J. A., van den Akker, J. M., Passage, G. J. P. N. & Posthoorn, J. I. (2019). Solving stochastic machine scheduling problems by estimating the solution value within local search. Proceedings of the 14th Workshop on Models and Algorithms for Planning and Scheduling Problems, MAPSP 2019.
This PhD project addresses challenges that arise once a (shunting) plan has been established, but circumstances are different from what was expected. In such scenarios, the first challenge is to efficiently detect when (significant) replanning is necessary. To evaluate the replanning decision and control plan adaptation accordingly, we require a comprehensive assessment of risks in dynamic environments. Second, we work closely with the human planner to resolve plan violations. Finally, we need algorithms to adapt plans and monitoring procedures according to human feedback.
To address the above scientific challenges, we will investigate existing methodology on continuous monitoring and adaptation of complex systems in dynamic environments and design novel approaches for detecting robustness violations of plans on multiple levels of abstraction; research suitable risk estimation techniques, and in algorithm visualization (Task 1). Robust plans developed on the previous day will be accompanied by a monitoring procedure during the day to detect and process any violations (Task 2). If a disruption occurs, the monitor will assess the risk of more severe violations of the plan based on the calculated multi-level risk scenarios. If the risk is low, the monitor will repair minor violations (together with the PhD student for research project 2). Otherwise, the system will inform the human operator and explain the necessity of human intervention via an interpretable prediction. Existing approaches to risk analysis of systems under uncertainty can provide guarantees in a static environment [2]. To account for dynamic changes, we will take inspiration from recent advances in multi-environment modeling and explore conditional value at risk for evaluating multiple strategies [3] (Task 3). An effective feedback loop between a human planner and a monitoring procedure will be established by providing an interpretable and complete explanation of the detected violation and required action (Task 4). We will leverage advanced visualization techniques to design a comfortable and visually accessible environment for humans to analyze the robustness violation, its source, and expected consequences [6] (in collaboration with the PhD students for research projects 1 and 2). Newly designed robust plans accompanied by human feedback will serve as training data for learning-based disruption response, together with the PhD student for research project 5 (Task 5). Future transitioning towards Automated Train Operation (ATO) will largely rely on learned local decision-makers: e.g., when a shunting plan is deployed, the learned components (trained on expert demonstrations of how to execute the plan locally) would drive the train across the yard. However, in highly dynamic environments, where not only novel disruptions can decrease the reliability of such learned components but also expert decisions would change, monitoring procedures must be in place to continuously help the whole system adapt. We will build on recently developed techniques for monitoring systems with learned components under frequent changes in the environment [1]. Resulting risk-scenario-aware adjustments in the plans must be incorporated into the whole system, which in the fully automated case requires high-level control over affected vehicles. For this purpose, we will design a rigorous control synthesis approach based on the approximation of the predicted future performance [4, 5] (Task 6).
[1] Lukina, A. et al. (2021). Into the unknown: Active monitoring of neural networks. In RV.
[2] Křetínský, J., & Meggendorfer, T. (2018). Conditional value-at-risk for reachability and mean payoff in Markov decision processes. In LICS.
[3] Chatterjee, K. et al. (2020). Multiple-Environment Markov Decision Processes: Efficient Analysis and Applications. In ICAPS.
[4] Alamdari, P. A. et al. (2020). Formal methods with a touch of magic. In FMCAD.
[5] Cavone, G. et al. (2020). An MPC-Based Rescheduling Algorithm for Disruptions and Disturbances in Large-Scale Railway Networks. In IEEE TASE.
[6] Jia, S. et al. (2021). Towards Visual Explainable Active Learning for Zero-Shot Classification. In IEEE TVCG.
The main challenge is to find the most promising infrastructure changes to extend the capacity of the hubs to deal with the future amount and type of traffic, and the future amount of rolling stock. To this end, we aim to develop methods to identify bottlenecks within the hub infrastructure and we need to increase the efficiency of the capacity analysis of the hubs. Moreover, we assess how to work closely with human decision/policymakers.
To address the above challenges, we need to investigate beyond state-of-the-art algorithms and heuristics, methods to analyze their outcomes, and methods to make them deal with uncertainty. In earlier research [1], we developed the first algorithm to solve the service location planning problem for realistic instances, the foundations of the Local Search algorithm HIP. The algorithm uses Simple Temporal Networks ([2]) to represent a plan. It has already been applied by NS to capacity analysis and currently, pilots for operational application take place. In [3] we developed heuristics for train routing strategies that led to more efficient produced route plans. Our first step is to identify the bottlenecks and thereby limit the set of appropriate changes in the infrastructure. We plan to analyze near-feasible instances and use Directed Local Search and extend the algorithm from [1] to search for different solutions w.r.t. violations of the soft constraints. Next, we study Infrastructure changes. We investigate how to efficiently adapt a solution to a change in infrastructure elements. Using this, we include infrastructure decisions in the local search from [1]. After that, we investigate algorithms to change a solution for a changed situation w.r.t. the timetable and traffic volume. This is closely related to the work by the PhD students for research projects 2 and 3. We try to include as much traffic as possible, first without changing infrastructure and next with a minimal number of (or least costly) infrastructure changes. After that we want to include uncertainty on the timetable and amount of rolling stock in the Local Search, i.e. make our Local Search work with a given set of future scenarios. The key observation here is that if there is uncertainty in traffic, the objective function becomes a stochastic variable as well. Two approaches for evaluation of the objective are 1) using a deterministic approximation or 2) Monte Carlo simulation. Related to 1) it should be noted that in the literature there is no consensus on which function is the most appropriate. In [4] we applied a new function based on a normal approximation function to planning at railway yards. In [5], we applied a combination of simulation and local search to solve the job shop scheduling problem. In this project, we intend to investigate both options and their combination. Again our starting point is the case without infrastructure changes and next with a minimal number of (or least costly) infrastructure changes. Finally, based on the experience and insights from the research above, we want to investigate possibilities to design a more global (high-level) optimization model. We intend to investigate the possibilities for a hybrid approach for capacity analysis and explore the possibilities to include forecasts for traffic growth and for infrastructure change.
[1] R.W. van den Broek et al. (2021). A Local Search Algorithm for Train Unit Shunting with Service Scheduling. Transportation Science.
[2] Dechter et a.l (1991). Temporal constraint networks. Artificial intelligence.
[3] Trepat Borecka, et al. (2021). Solving the train unit shunting problem using multi-agent deep reinforcement learning with routing optimization. IEEE Transactions on Int. Transp. Systems.
[4] Roel van den Broek et al. (2018). How to measure robustness of shunting plans. ATMOS.
[5] J.M. van den Akker et al. (2013). Finding robust solutions for the stochastic job shop scheduling problem by including simulation in local search. SEA
This PhD research topic explores the scientific challenges that arise when trying to reuse previous solutions to network planning problems. When reusing previous solutions, the first challenge is to learn patterns that can be reused in future planning problems. To aid collaborative human-machine planning, the second challenge is to represent these patterns in a format understandable by both human and machine planners. In the third challenge, we investigate how to adapt the learned patterns and earlier search to the variants of the problem. Finally, we investigate how to closely work with human planners.
To address the defined scientific challenges, we will investigate the existing techniques for learning and adapting patterns in planning solutions, and develop novel techniques for detecting and reusing patterns and searches in rail network planning (Task 0). Rail network plans are regular in the sense that the plans repeat, with small variations on a daily or weekly basis. Therefore, it makes sense to try to reuse previous plans as much as possible, and by doing that improve the efficiency of future planning [1,2,3]. We will develop techniques for detecting patterns in plans that are insensitive to small variances in schedules, e.g., a certain train departs 5 minutes later, and planning procedures that make use of extracted patterns (Task 1). As plans frequently need to be adjusted due to unforeseen circumstances, we will investigate techniques that discover patterns in plan adjustments (Task 2). For detected patterns to be truly useful, human planners should be able to understand them. Therefore, we will develop a representation of plans and patterns that is understandable both to human and automated planners, together with the PhD students for research projects 1 and 3 (Task 3). Such representation will not only aid collaborative planning but will also support the inclusion of preferences on what makes a good reusable pattern. This task will also focus on discovering implicit preferences while interacting with human planners, together with the PhD student for research project 1. As collections of planning patterns might be large and make planning problems more difficult to solve [1,2], we will develop techniques to identify a subset of patterns relevant to a new planning problem, improving planning efficiency (Task 4). Composing plans from successful patterns will also lead to more robustness because extracted patterns, when adjusted for variance, reflect best-case planning scenarios. To make collaborative human-machine planning productive, we will develop techniques for collaborative and interactive human-machine planning where an automated planner produces a partial plan first, a human planner verifies and adapts it, and the procedure iterates until the plan is complete (Task 5). Being able to do so, even partially, will focus human efforts where it is most needed, significantly increasing productivity in collaborative planning.
[1] S. Dumančić, T. Guns, A, Cropper: Knowledge Refactoring for Inductive Program Synthesis. AAAI Conference on Artificial Intelligence (AAAI), 2020
[2] K. Ellis, L. Morales, M. Sablé-Meyer, A. Solar Lezama, J. Tenenbaum: Library learning for neurally-guided Bayesian program induction. NeurIPS 2018
[3] R. van der Krogt, M. de Weerdt: Plan repair using a plan library. Belgium-Netherlands conference on artificial intelligence (BNAIC) 2005
Marjan van den Akker is associate professor at the Department of Information and Computing Sciences at Utrecht University, where she is a leader of the Operations Research team. After het PhD at TU/e, she has been a research engineer at the National Aerospace Center NLR for more than 5 years. Her research is in the intersection of Operations research and Artificial Intelligence and considers advanced planning algorithms, robust planning and simulation. In her research, characteristics from practice are combined with state-of-the-art theoretical models. She want to contribute to a more sustainable environment by developing sound algorithms for challenges in mobility and energy. She holds a joint senior position with KLM within the kickstartAI program and is scientific director of the Utrecht AI & Mobility Lab.
Mathijs de Weerdt is full professor on Algorithms for Planning and Scheduling and section head of the Algorithmics Group at Delft University of Technology. After his PhD he received the prestigious VENI grant from NWO to support his research into coordinated planning from 2005 to 2008. He has been a visiting researcher at the Dutch Center for Mathematics and Computer Science (CWI) from 2005 to 2016, Cork in 2006, Southampton between 2012 and 2015 and Duke in 2017, and is one of the founders of the TU Delft Rail Institute (2020). He has been and is (co-)promotor of in total 15 PhD students of which 9 have completed their PhD so far. An important challenge for him is to identify how Artificial Intelligence can contribute to the energy transition and sustainability of our society, and what is needed to speed-up such developments.