Industrial manipulators are increasingly used in manufacturing and packaging systems where the exact tasks are not known in advance. In such settings, task and motion planning (TAMP) must be performed online, while the resulting plans should maximize throughput and satisfy velocity, acceleration, and higher-order derivative constraints. This is especially challenging when multiple fast manipulators operate close together in a shared workspace, resulting in additional constraints on trajectories, task allocations, and orderings to avoid collisions.
Existing multi-agent TAMP methods often rely on discretized space and time, resulting in trajectories that cannot be executed directly by manipulators. On the other hand, continuous trajectory optimization methods can generate smooth trajectories, but they do not address task allocations and orderings, and either consider a single manipulator and/or are too slow for online planning.
We present a soft real-time TAMP framework for multiple fast manipulators. Tasks are generated from product and place positions, assigned to robots, and converted into dynamically feasible trajectories. Experiments compare polygonal bang-bang, polygonal smoothstep, and smooth optimized Bézier trajectories with continuity up to acceleration and jerk. The results show that the polygonal trajectories are the fastest to compute, while Bézier optimization reduces the makespan at the cost of increased planning time. Additionally, bang-bang initialization gives faster convergence than smoothstep and is thus a good starting point for fast Bézier optimization. The makespan improvement reduces per iteration, allowing for a relatively large improvement in minimal time. The proposed assignment methods are shown to be feasible for online planning resulting in few potential collisions, and a custom convex-hull-based collision checker is compared to a sample-based collision checker on the tradeoff between conservativeness and runtime. ... Read more

Rail transport is one of the most used forms of public transport, and apart from the timetable, effective shunting operations are an important part of operational efficiency and robustness. Trains not used in the timetable are parked at shunting yards, where shunting operations take place, which take 10-50% of trains’ total transit time. Efficient planning of these operations is challenging due to relatively small yards that cannot be expanded easily, since they are located in urban areas. The management of trains outside of the timetable is an NP-hard problem known as the Train Unit Shunting Problem (TUSP). The TUSP concerns the matching, routing, and parking of arriving and departing trains. The current state-of-the-art Local Search (LS) approach is non-deterministic and struggles with the routing aspect of the TUSP. In this thesis, the TUSP is approached from a routing perspective with a deterministic algorithm. We apply Lagrangian Relaxation (LR) methods to the TUSP such that the problem can be split into per-train shortest path problems. Standard LR struggles with solving the TUSP due to symmetry in the trains and in the shunting yards. To address the symmetry, the approach is extended with Augmented Lagrangian Relaxation (ALR) and solved with the Alternating Direction Method of Multipliers (ADMM). Experimental results show that ADMM can be used to solve a somewhat simplified version of the TUSP and outperforms the LS approach on scenarios in which the arrival and departure of trains are more time restricted, i.e., smaller time windows. On larger time windows and for more trains, the LS outperforms the ADMM approach.
... Read more

Automated Planning, also known as Artificial Intelligence (AI) planning is a branch of AI focused on automated decision-making and scheduling. A sub-problem within AI Planning is domain-independent planning, where we want to develop methods that are generalisable for solving planning problems in many domains. A popular modelling language for domain-independent planning is PDDL. In PDDL we model our problems as having some start state and some goal state; these states are defined by the truth-values of a set of defined predicates applied to a set of objects with corresponding types. In this work we explore the concept of dynamic macro-actions for PDDL, which are macro-actions whose utility are re-evaluated as we solve more problems, and does not require prior training. We find that dynamic macro-actions are a promising method, showing average improvements in the number of nodes explored in the search space of up to 84\% depending on the domain. ... Read more

All over the world, people plan their daily activities. These plans include a lot of different tasks and can vary widely in kinds of activities. These plans must account for uncertainties and unknowns in the world. Planning around these uncertainties is difficult and hard to accomplish with traditional means of programming. For this set of problems, probabilistic programming is proposed. Given the Minecraft planner from the Planning Domain Definition Language (PDDL) gym library, is it possible to create Robust plans that incorporate inference without changing the underlying planner? "PDDL is a human-readable format for problems in automated planning that gives a description of the possible states of the world, a description of the set of possible actions, a specific initial state of the world, and a specific set of desired goals." [6] The current approach is using heuristics to find the optimal plan for the problem. In this research paper, an alternative method is proposed; using probabilistic programming and the existing planner to create a simulated world of Minecraft. This model introduces inference without changing the already existing planner. ... Read more

Scheduling problems are present in many real-world situations, such as construction projects, manufacturing processes, or train timetabling. One common formalization is the Resource Constrained Project Scheduling Problem (RCPSP), where the goal is to find an optimal schedule given limited resources. Traditional algorithms optimize for project duration under deterministic assumptions, which could lead to poor performance under uncertainty. This thesis explores how to create robust schedules, meaning they can withstand uncertainty, for stochastic task durations. Robust schedules minimize delays, measured as the difference between a task's completion time and its deadline. The method proposed uses probabilistic programming as a tool to accomplish this. A robustness distribution over schedules is inferred using importance sampling, and a robust schedule can be selected from that explored distribution. Importantly, this approach presented in this thesis can be applied on top of existing scheduling and simulation algorithms without requiring any knowledge or changes to themselves. Created schedules can also be abstracted, thus do not need to be analyzed or seen. This makes the proposed method general and easy to adopt in practice. ... Read more

Train Unit Shunting is a complex process that directs trains through a shunting yard. In real-world railway operations, disturbances are common, requiring shunting schedules to be robust against uncertainties such as delays. Previous research has proposed algorithms for the Train Unit Shunting Problem (TUSP) and one study attempted to create robust shunting plans by defining a probabilistic model of the uncertainties involved and inferring a distribution of robust solutions for the TUSP. Following this approach, this paper investigates the use of probabilistic programming in increasing robustness of shunting plans using an advanced TUSP solver. This research develops a model for uncertain shunting scenarios, solves these scenarios, and applies importance sampling to infer the posterior distribution, producing a distribution of robust shunting plans instead of a single plan. The paper presents examples demonstrating that it is beneficial to use one of the output robust plans over the plan made for the deterministic scenario, revealing the potential of integrating probabilistic programming techniques into the planning process to improve railway efficiency and reduce delays. ... Read more

Planning problems are a set of problems in which an objective must be reached by a sequence of actions. Planning problems traditionally do not consider uncertainty, however for most real-world planning problems uncertainty must be considered to create effective plans. The objective of this paper is to use an existing deterministic planning algorithm in order to create robust plans that solve an uncertain version of Sokoban called Uncertain Move Sokoban. To this end a probabilistic programming language, Gen.jl, is used, which enables creating probabilistic models and inferring its parameters using code. A probabilistic model is created in Gen.jl, that generates plans for the problem as well as robustness scores using a simulator embedded in the model. Probabilistic inference techniques are then used to obtain a robust plan for the uncertain problem, namely: importance sampling and Metropolis-Hastings. We find that the technique is able to create robust plans for small to medium-sized problems and that Metropolis-Hastings is the better-performing inference technique. ... Read more

Planning is very important in everyday life, whether it would be creating schedules for planes or plans for manufacturing. These domains contain uncertainties requiring plans that are robust. However, there is a need for an approach which creates robust plans regardless of the domain and without changing its planning agent. Here, a replanning approach is proposed akin to the Metropolis-Hastings algorithm and its performance is compared to the performance of importance sampling. Replanning works by iteratively trying to improve the previously generated plan. The performance is compared by means of the Keys and Doors problem. It is found that replanning performed better than importance sampling in the two analysed problems. Furthermore, changing the parameter, σ, used in the replanning approach showed a significant difference in its corresponding performance. While the replanning approach has only been tested on the Keys and Doors problem, the results show that replanning is a promising approach which could work irrespective of the domain at hand. ... Read more

Solutions for the Train Unit Shunting Problem are constantly being researched and improved to be- come more efficient and match the needs of train transport in the Netherlands. For this reason, we are exploring new ways to find patterns in the train data to identify where those solutions could be en- hanced. More specifically, we are trying to find patterns that make identifying different locations possible. We identify patterns in the capacity of the shunting yards and the types of trains used in various locations, which result in reasonable ac- curacy in classification. Some locations operate closer to their capacity, and some require longer paths to get inside the shunting yards. These find- ings could be helpful not only for the planning algo- rithms but also in identifying which locations might need expansion or restructuring and where more of the train fleet should be allocated. ... Read more

This paper analyses manually realised solutions to the Train Unit Shunting Problem (TUSP) to find patterns in train type. The parking element is most important for the TUSP. Therefore, this research specifically investigates the presence of train type patterns in parking track and parking time. The difference in the patterns between main train type and train subtype is also analysed. The study uses statistical hypothesis testing to look for biases between individual train types and parking tracks. Kernel density estimation is used to analyse the differences in parking time between the types. The results show that there are strong patterns in type and parking track, but no clear difference in parking time. Considering subtype results in the differences being more specific. It is suspected that the strongly present track pattern is a strategy used by human planners. ... Read more

Shunting yards are locations next to train stations that serve as parking places for trains when they are not in operation and often contain facilities for maintenance and cleaning for passenger trains. Planning of the tasks regarding shunting trains involves routing, assignment of tracks, and scheduling tasks. This is done manually and requires a lot of effort, making it inefficient. Identifying patterns specific in the arrival times of trains at shunting yards can help to predict future train arrivals and potential delays throughout the year more accurately. This enables the alignment of staff and equipment with train arrivals, minimizing idle time and optimizing cost efficiency.
This research focuses on extracting and analyzing the arrival times of trains at shunting yards using a dataset consisting of GPS data. It conducts two algorithms to cluster the given data for each train unit within and across days to identify the same train across different days. Distributions and heatmaps of the arrival times and delays are created based on the identified train series. They are analyzed to identify patterns in train arrival times and delays across different months. ... Read more

When not in service, trains are parked and serviced at shunting yards. The Train Unit Shunting Problem (TUSP), an NP-hard problem, encompasses the challenge of planning movements and tasks in shunting yards. A feasible shunting plan serves as a solution to the TUSP. Current automated planning tools utilized to assist human planners in this computationally heavy planning task are not able to distinguish inherent patterns in input train data, as opposed to humans. This paper aims to address this technological gap by examining whether valuable patterns could be extracted from shunting plan data, consisting of solutions to the TUSP. More specifically, it is mainly concerned with the automatic detection of whether a solution to the TUSP is a week or a weekend day. Therefore, the data is examined for the presence of several groups of patterns. Moreover, binary classification is performed on the data. The experiments conducted in this study suggest the presence of valuable patterns in the data, which could be leveraged to design specialized heuristics for automated planning models tailored to generate shunting plans for weekdays and weekends. ... Read more

This research aims to find patterns in the live position data of trains within shunting yards. These patterns can be converted to heuristics and applied in algorithms developed by railway operators in the Netherlands to tackle the Train Unit Shunting Problem. The usage patterns were extracted from real-world location data of train units. Specifically, this research focuses on finding patterns in the paths taken in both temporal and spatial metrics. These investigations identified the busiest times in the shunting yards according to various metrics, such as the total number of trains and the number of serviced trains. These metrics are extracted from the type of train movement at a given moment, which was provided with the dataset. The accuracy of the provided train movement category has been analyzed and shown to be inaccurate for uses within shunting yards compared to a proposed approach. Finally, an algorithm for classifying train units that belong to the same train has been shown to have initial success. ... Read more

This paper explores the application of landmark-based planning algorithms, specifically focusing on AND/OR landmark extraction methods. Drawing from classical planning principles and recent advancements, we investigate the effectiveness of landmark extraction in guiding the search for solutions to planning problems. Our research questions center on identifying effective domains for landmark extraction, assessing the utility of extracted landmarks, and comparing our implementation with existing literature. Utilizing the Symbolicplanners.jl framework, we implement AND/OR landmark extraction and evaluate its performance across various domains. Due to challenges in implementation, the landmarks we were able to extract had limited meaning. We propose future work to refine the AND/OR method and expand our analysis to include the Hm procedure. ... Read more

Landmarks are propositions or actions that must be true at some point in every valid solution plan [16]. Using landmarks, planners can develop solutions more efficiently. Different algorithms exist to extract landmarks from a planning problem. The one used in this study is FULL [13], a landmark extraction algorithm by Marzal et al. from 2011.
In this research, the performance of the FULL algorithm is analysed by comparing the total number of landmarks found to two other landmark extraction algorithms, namely forward propagation by Zhu and Givan [22] and backward propagation by Porteous et al. [16].
The original FULL algorithm is slightly modified, by removing orderings and disjunctive landmark extraction. FULL is implemented using Julia and was run on five different domains from the International Planning Competitions.
All of these domains are logical and 15 problems were randomly selected from them.
FULL managed to extract more landmarks in two out of the five domains, Grid and Logistics, compared to the two aforementioned algorithms.
In the three other domains, FULL matched the number of landmarks found by the best out of the two. The two domains where FULL performed well, were both transportation domains and this is where FULL's performance excels.
Runtime was not an issue when extracting landmarks in four of the five domains. Freecell consistently exceeded the timeout put in place, likely due to a bug.
Furthermore, a higher number of landmarks is also a desired outcome due to its use in planners, either as heuristics or intermediary goals. ... Read more

The Fast Downward planning system is currently mainly used for solving classical problems. Another alternative to Fast Downward is SymbolicPlanners, which sacrifices speed for generality and extensibility. SymbolicPlanners is missing landmark based planners and landmark extraction algorithms. The research question we are trying to answer in this research paper is: What design choices can be made to adapt the forward propagation extraction algorithm into SymbolicPlanners?
The forward propagation landmark generation design choices are discussed and implemented in SymbolicPlanners. The runtime performance of the implementation is only about two times slower than the Fast Downward implementation. Another aspect of the implementation is the incorrect amount of landmarks generated in complex problems caused by limitation in the relaxed planning graph from SymbolicPlanners. ... Read more

A lot of research has been conducted to make the task of plan generation more efficient. One idea to do so is the use of landmarks, which are sub-goals that must be true in every solution to the problem. The approximation of landmarks has a lower complexity than solving the task itself, and they can be used to guide the planner in the right direction.
In previous work, ideas to order landmarks are proposed and compared to algorithms that do not use them. We verify if this comparison is fair by testing both algorithms implemented in the same language and framework. In our experiment not many problem instances finish in time, but those that do are in line with previous experiments in that on average planners using landmarks produce longer solutions than planners that do not use them. ... Read more

Algorithmic planners occasionally waste effort and thus computing time trying to solve certain tasks, as they often lack the human ability to recognize essential paths. These essential paths, termed landmarks, are vital for optimizing planning processes. This study revisits landmark-based planning methods introduced by Richter, Helmert, and Westphal in their 2008 paper, adapting and implementing them within a different framework, SymbolicPlanners, using the Julia programming language. The primary research question explores the performance of using landmarks as intermediary goals and pseudo-heuristics in the SymbolicPlanner framework. Sub-questions delve into the effectiveness of specific planning strategies, such as A^∗ Planner with GoalCount and HAdd heuristics, as well as planners utilizing landmarks. Evaluation over diverse domains reveals that LM^Local  and LM^LocalSmart outperform the basic GoalCount
heuristic and are on par with the HAdd heuristic. LM^Count, despite solving fewer instances, exhibits speed improvements over GoalCount in the instances that they both solve. Discussion highlights limitations, such as the non-exhaustive interference check in LM^LocalSmart and limiting factors in the SymbolicPlanner framework. ... Read more

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. ... Read more

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.
... Read more