The Optimal In-Station Train Dispatching (InSTraDi) problem consists in commanding the movements of trains inside a railway station while both (i) respecting safety, time, and travel constraints and (ii) minimizing delays. In Symbolic Pattern Planning (SPP), a pattern, suggesting the sequence of happenings to reach the goal, is encoded in a logic formula whose models correspond to valid plans. If no valid plan is found, the pattern is extended until it covers a valid plan. However, plans of better quality could exist if we had continued extending the pattern. In this paper, we formalize the InSTraDi problem as a Temporal Planning Task with Intermediate Conditions and Effects, and we show an InSTraDi-dependent way to construct, in polynomial time, a pattern ensuring the optimal plan can be found by the SPP approach without never extending the pattern. Analysis on realistic railway data validate our approach.

In this paper, we propose a novel approach for solving automated planning problems, called Symbolic Pattern Planning. Given a deterministic planning problem Π, we propose to compute a plan by first fixing a pattern –defined as an arbitrary sequence of actions– and then define a formula encoding the state resulting from the sequential execution of the actions in the pattern, starting from an arbitrary initial state. By allowing each action in the pattern to be executed consecutively zero, one or possibly more times, and by imposing the conditions on the initial and goal states, we can check whether the pattern allows determining a valid plan or whether the pattern needs to be extended and the procedure iterated. We ground our proposal in the numeric planning setting, we prove the correctness and also the completeness of the procedure (provided at each iteration the pattern is extended with a complete sequence of actions), and we define procedures for the pattern selection and for computing quality plans. When exploiting the planning as satisfiability approach, we show that our encoding allows to determine a valid plan in a number of iterations which is never higher than the one needed by the state-of-the-art rolled-up or relaxed-relaxed-∃ symbolic encodings. On the experimental side, we run an extensive analysis which included the problems and systems involved in the numeric track of the 2023 International Planning Competition, showing that the results validate the theoretical findings and that our planner Patty has remarkably good comparative performances.

We consider temporal numeric planning problems Π expressed in PDDL2.1, and show how it is possible to produce SMT formulas (i) whose models correspond to valid plans of Π, and (ii) which extends the recently proposed planning with patterns approach from the numeric to the temporal case. We prove the correctness and completeness of the approach and that it outperforms all the publicly available temporal planners on 10 domains with required concurrency.

Real-world applications of planning techniques often deal with dynamic and noisy environments, where sensor readings are often inaccurate, and the world's states can evolve in unexpected ways. This is particularly challenging for hybrid discrete-continuous planning approaches, where processes and events can be strongly affected by even slightly different initial conditions of the world, and planning tasks are notoriously difficult to cope with. In this paper, we introduce the Initial Condition Retrieving (ICR) problem to foster hybrid planning in real-world applications. Given a knowledge model of a planning task and a trace, solving the ICR problem allows identifying the space of all the initial conditions from which the provided plan is guaranteed to reach a goal state. We define three tasks: (i) retrieving any valid initial condition, (ii) fixing only some desired initial values and retrieving a complete initial condition that fills in the unassigned values, or (iii) retrieving the closest achievable initial condition to a fully specified one from which the goal cannot be reached. Experiments on well-known hybrid planning domains demonstrate the efficacy of our approach in solving such tasks. Moreover, given that our approach can be applied to numeric planning without any change, we extend our analysis to numeric domains, where we obtain positive results.

In classical planning, conditional effects (CEs) allow modelling non-idempotent actions, where the resulting state may depend on how many times each action is consecutively repeated. Though CEs have been widely studied in the literature, no one has ever studied how to exploit rolling, i.e., how to effectively model the consecutive repetition of an action. In this paper, we fill this void by (i) showing that planning with CEs remains PSPACE-complete even in the limit case of problems with a single action, (ii) presenting a correct and complete planning as satisfiability encoding exploiting rolling while effectively dealing with constraints imposed on the set of reachable states, and (iii) theoretically and empirically showing its substantial benefits.

In this paper, we present a symbolic search-based procedure for numeric planning based on Symbolic Pattern Planning (SPP). In SPP, a pattern is a sequence of actions used to define a logic formula whose models correspond to sequences of applicable actions and reachable states. Here, starting from the empty pattern, we iteratively extend and compress it using search techniques until a goal state is reached. We prove the correctness and completeness of the procedure and demonstrate its good performance compared to both the original SPP approach and other publicly available numeric planners on the 2023 International Planning Competition Agile track.

In this paper, we propose a novel approach for solving linear numeric planning problems, called Symbolic Pattern Planning. Given a planning problem Pi, a bound n and a pattern --defined as an arbitrary sequence of actions-- we encode the problem of finding a plan for Pi with bound n as a formula with fewer variables and/or clauses than the state-of-the-art rolled-up and relaxed-relaxed-exists encodings. More importantly, we prove that for any given bound, it is never the case that the latter two encodings allow finding a valid plan while ours does not. On the experimental side, we consider 6 other planning systems --including the ones which participated in this year's International Planning Competition (IPC)-- and we show that our planner Patty has remarkably good comparative performances on this year's IPC problems.

The PDDL+ formalism allows the use of planning techniques in applications that require the ability to perform hybrid discrete-continuous reasoning. PDDL+ problems are notoriously challenging to tackle, and to reason upon them a well-established approach is discretisation. Existing systems rely on a single discretisation delta or, at most, two: a simulation delta to model the dynamics of the environment, and a planning delta, that is used to specify when decisions can be taken. However, there exist cases where this rigid schema is not ideal, for instance when agents with very different speeds need to cooperate or interact in a shared environment, and a more flexible approach that can accommodate more deltas is necessary. To address the needs of this class of hybrid planning problems, in this paper we introduce a reformulation approach that allows the encapsulation of different levels of discretisation in PDDL+ models, hence allowing any domain-independent planning engine to reap the benefits. Further, we provide the community with a new set of benchmarks that highlights the limits of fixed discretisation.

The PDDL+ formalism allows the use of planning techniques in applications that require the ability to perform hybrid discrete-continuous reasoning. PDDL+ problems are notoriously challenging to tackle, and to reason upon them a well-established approach is discretisation. Existing systems rely on a single discretisation delta or, at most, two: a simulation delta to model the dynamics of the environment, and a planning delta, that is used to specify when decisions can be taken. However, there exist cases where this rigid schema is not ideal, for instance when agents with very different speeds need to cooperate or interact in a shared environment, and a more flexible approach that can accommodate more deltas is necessary. To address the needs of this class of hybrid planning problems, in this paper we introduce a reformulation approach that allows the encapsulation of different levels of discretisation in PDDL+ models, hence allowing any domain-independent planning engine to reap the benefits. Further, we provide the community with a new set of benchmarks that highlights the limits of fixed discretisation.

Abstract Answer set programming (ASP) has demonstrated its potential as an effective tool for concisely representing and reasoning about real-world problems. In this paper, we present an application in which ASP has been successfully used in the context of dynamic traffic distribution for urban networks, within a more general framework devised for solving such a real-world problem. In particular, ASP has been employed for the computation of the “optimal” routes for all the vehicles in the network. We also provide an empirical analysis of the performance of the whole framework, and of its part in which ASP is employed, on two European urban areas, which shows the viability of the framework and the contribution ASP can give.

Abstract A core part of the rehabilitation scheduling process consists of planning rehabilitation physiotherapy sessions for patients, by assigning proper operators to them in a certain time slot of a given day, taking into account several legal, medical, and ethical requirements and optimizations, for example, patient’s preferences and operator’s work balancing. Being able to efficiently solve such problem is of upmost importance, in particular after the COVID-19 pandemic that significantly increased rehabilitation’s needs. In this paper, we present a two-phase solution to rehabilitation scheduling based on Answer Set Programming, which proved to be an effective tool for solving practical scheduling problems. We first present a general encoding and then add domain-specific optimizations. Results of experiments performed on both synthetic and real benchmarks, the latter provided by ICS Maugeri, show the effectiveness of our solution as well as the impact of our domain-specific optimizations.

Abstract The rehabilitation scheduling process consists of planning rehabilitation physiotherapy sessions for patients, by assigning proper operators to them in a certain time slot of a given day, taking into account several requirements and optimizations, e.g. patient’s preferences and operator’s work balancing. Being able to efficiently solve such problem is of upmost importance, in particular as a consequence of the COVID-19 pandemic that significantly increased rehabilitation’s needs. The problem has been recently successfully solved via a two-phase solution based on answer set programming (ASP). In this paper, we focus on the problem of rescheduling the rehabilitation sessions, which comes into play when the original schedule cannot be implemented, for reasons that involve the unavailability of operators and/or the absence of patients. We provide rescheduling solutions based on ASP for both phases, considering different scenarios. Results of experiments performed on real benchmarks, provided by ICS Maugeri, show that also the rescheduling problem can be solved in a satisfactory way. Finally, we present a web application that supports the usage of our solution.

Public railway transport systems play a crucial role in servicing the global society and are the transport backbone of a sustainable economy.While a significant effort has been devoted to predict inter-station trains movements to support stakeholders (i.e., infrastructure managers, train operators, and travellers) decisions, the problem of predicting instation movements, while being crucial to improve train dispatching (i.e., empowering human or automatic dispatchers), has been far more less investigated.In fact, stations are the most critical points in a railway network: even small improvements in the estimation of the duration of trains movements can remarkably enhance the dispatching efficiency in coping with the increase in capacity demand and with delays.In this work we will first leverage on state of the art shallow models, fed by domain experts with domain specific features, to improve the current predictive systems.Then, we will leverage on a customised deep multi scale model able to automatically learn the representation and improve the accuracy of the shallow models.Results on real-world data coming from the Italian railway network will support our proposal.* This work has been partially

In-station train dispatching is the problem of optimising the effective utilisation of available railway infrastructures for mitigating incidents and delays. In this paper, we describe an approach for dealing with the in-station dispatching problem by means of automated planning techniques.