In this paper, we investigate the application of heuristics based on Graph Neural Networks (GNNs) to lifted numeric planning problems, an area that has been relatively unexplored. Building upon the GNN approach for learning general policies proposed by Ståhlberg, Bonet, and Geffner (2022b), we extend the architecture to make it sensitive to the numeric components inherent in the planning problems we address. We achieve this by observing that, although the state space of a numeric planning problem is infinite, the finite subgoal structure of the problem can be incorporated into the architecture, enabling the construction of a finite structure. Instead of learning general policies, we train our models to serve as heuristics within a best-first search algorithm. We explore various configurations of this architecture and demonstrate that the resulting heuristics are highly informative and, in certain domains, offer a better trade-off between guidance and computational cost compared to state-of-the-art heuristics.

We study planning in a fragment of PDDL with qualitative state-trajectory constraints, capturing safety requirements, task ordering conditions, and intermediate sub-goals commonly found in real-world problems. A prominent approach to tackle such problems is to compile their constraints away, leading to a problem that is supported by state-of-the-art planners. Unfortunately, existing compilers do not scale on problems with a large number of objects and high-arity actions, as they necessitate grounding the problem before compilation. To address this issue, we propose two methods for compiling away constraints without grounding, making them suitable for large-scale planning problems. We prove the correctness of our compilers and outline their worst-case time complexity. Moreover, we present a reproducible empirical evaluation on the domains used in the latest International Planning Competition. Our results demonstrate that our methods are efficient and produce planning specifications that are orders of magnitude more succinct than the ones produced by compilers that ground the domain, while remaining competitive when used for planning with a state-of-the-art planner.

Uncertainty over model knowledge is a core challenge in planning and has been addressed through various approaches tailored to different scenarios. In this paper, we focus on scenarios where the agent does not initially know the exact outcome of its actions but gains knowledge upon execution, i.e., each action reveals its actual effect, removing uncertainty about future occurrences. We refer to this formulation as Planning with Uncertain Models of Actions (PUMA). We show that PUMA can be compiled in polynomial time in both Fully Observable Non-Deterministic planning and, perhaps more unexpectedly, classical planning, providing a constructive proof that PUMA remains PSPACE-complete despite its apparent exponential uncertainty. Finally, we experimentally evaluate both compilations with benchmark domains that capture the key aspects of the problem. The results show the practical feasibility of our approach and reveal a complementary behavior between the two compilations.

The expressive power of PDDL+ is crucial in a wide range of real-world applications, where it is necessary to represent hybrid discrete-continuous changes and environmental dynamics. Given the complexity of the dynamics that can be modelled in PDDL+ and the scale of the problems involved, the ability to validate plans and simulate their trajectories is essential for assessing the accuracy of the models. In this paper, we present PPS (PDDL Plus Simulator), a Java-based tool that enables seamless validation and simulation of PDDL+ plans under time-discrete semantics.

PDDL 2.1 is the community standard for specifications of temporal planning problems, involving actions that have a duration and can overlap in time. Recent work has shown that some modelling features, such as intermediate and conditional effects, can be expressed in PDDL 2.1 by means of specific encodings. At the core of these encodings is a construction that requires two events to happen simultaneously. However, in practice, almost none of the state-space heuristic search planners known in the literature are capable of finding plans exhibiting this required simultaneity, suggesting that the search approach they use is actually incomplete with regards to the official PDDL 2.1 semantics. In this paper, we explore this issue both theoretically and experimentally. On the theoretical side, we define two different notions of required simultaneity, and we isolate which features of the semantics of PDDL 2.1 allow for such behaviors and how to possibly change the semantics to forbid each of them. In particular, we prove that the crucial detail is how the over-all conditions interact with the mutex relation. From these observations we isolate the reason why most search-based planners cannot find plans with required simultaneity, and provide an updated search strategy that recovers semantic completeness at the cost of a larger branching factor which, however, can be suitably pruned thanks to an application of our results. On the experimental side, we compare the proposed search strategies, showing that our pruning criterion allows us to recover semantic completeness without significant overhead.

It is well known that numeric planning can be made decidable if the domain of all numeric state variables is finite. This bounded formulation can be polynomially compiled into classical planning with Boolean conditions and conditional effects preserving the plan size exactly. However, it remains unclear whether this compilation has any practical utility. To explore this aspect, this work revisits the theoretical compilation framework from a practical perspective, focusing on the fragment of simple numeric planning. Specifically, we introduce three different compilations. The first, called one-hot, aims to systematise the current practice among planning practitioners of modelling numeric planning through classical planning. The other two, termed binary compilations, extend and specialise the logarithmic encoding introduced in previous literature. Our experimental analysis reveals that the overly complex logarithmic encoding can, surprisingly, be made practical with some representational expedients. Among these, the use of axioms is particularly crucial. Furthermore, we identify a class of mildly numeric planning problems where a classical planner, i.e., LAMA, when run on the compiled problem, is highly competitive with state-of-the-art numeric planners.

Automated planning, a core area of artificial intelligence, aims to generate action sequences that achieve specified goals based on a formal model. In classical planning, where only Boolean state variables are allowed, conditional effects are the standard approach for modelling actions with state-dependent outcomes. However, unlike in the classical setting, relatively little research has focused on developing planning methods for numeric problems with conditional effects. To address this gap in the literature, this work studies numeric planning with conditional effects. We formalise its semantics and revise existing classical planning compilations for conditional effects to account for the specific features of numeric planning. This results in three encodings: two are designed for the full class of numeric planning problems, while the third is specific to tasks with conditional effects that increase or decrease variables by a constant, transforming such problems into instances of Simple Numeric Planning, a well-known and practically significant subclass of numeric tasks. The experimental evaluation compares these compilations across both newly designed and compelling benchmarks as well as existing domains featuring conditional effects. Our empirical findings reveal complementary behaviour among the approaches, highlighting the practical impact of selecting the appropriate compilation for different problem structures.

In real-world scenarios, the successful execution of an agent’s planned actions is not always guaranteed, as actions may fail in unpredictable ways that are not explicitly modeled. To address this challenge, the concept of Resilient Planning and the RESPLAN framework were introduced focusing on the generation of k-resilient plans that enable an agent to reach its goals even in the presence of up to k execution failures. In this paper, we propose a new version of the RESPLAN planning algorithm based on two significant enhancements. The first incorporates landmarks into a pruning strategy, enabling the planner to avoid unnecessary explorations and yielding substantial performance gains, especially when no resilient plan exists. The second introduces a planning adaptation strategy exploiting regressed state formulas to support the search process during (re)planning, reducing the number of iterations required when a resilient plan does exist. We compare our methods against RESPLAN and other baselines, demonstrating substantial improvements across multiple domains.

In this paper, we tackle the problem of finding cost-optimal solutions in Fully-Observable Non-Deterministic (FOND) planning problems. First, we introduce metrics for FOND problems by interpreting solution policies under both their best and worst possible scenarios, leading to a bi-objective optimization problem. We then propose BOAND*, a novel heuristic search algorithm designed to seek Pareto-optimal solutions by navigating the space of possible policies. We conduct an empirical evaluation of the algorithm, alongside a qualitative comparison with cost-optimal solutions that consider only one objective at a time. Our findings validate this approach, paving the way for new methods of reasoning over FOND problems.

Research in planning has sought to broaden the scope of planning problems by incorporating numeric parameters into action descriptions to condition both continuous and discrete change. Focusing on the latter, this work studies the problem of numeric planning with control variables, a reformulation of actions with infinite domain parameters. To tackle the challenge of handling an infinite decision space driven by control variables, we incorporate sampling into a forward state-space search. The resulting search framework (1) partially expands nodes by sampling their successors and (2) implements a re-expansion strategy to sample additional successors if a node shows promise in future evaluations. We perform a deep probe into this concept that materializes into a new algorithm called Sampling Greedy Best-First Search (S-GBFS). Our empirical evaluation of S-GBFS across various domains shows significant improvements over existing planning approaches.

PDDL+ is a planning formalism designed to model mixed continuous-discrete problems. Despite its expressiveness, the absence of a well-established framework for evaluating plan quality makes it challenging to use PDDL+ in applications where plan shape and quality are crucial. This paper addresses this issue by introducing a comprehensive set of plan cost functions tailored for discrete-time PDDL+, along with a cost-preserving translation for generating cost-aware PDDL2.1 planning tasks. The plan cost functions provide a theoretical ground for assessing plan quality, whereas the translation shows their practicability by leveraging the connection between PDDL+ and PDDL2.1.

This paper studies the use of lazy greedy best-first search for numeric planning problems in combination with relaxation-based heuristics, helpful actions, and up-to-jumping actions. In particular, the new search schema that we study, whilst postponing evaluation of the heuristic at expansion time, focuses the search over those states that are reached by helpful and up-to-jumping actions. In addition, we revisit linear abstractions by improving the balance between computation time and information, providing guidance in non-simple numeric planning problems, too. The new search schema compares favorably over the IPC-23 benchmarks with alternative complete heuristic search planners from the literature.

In automated planning, control parameters extend standard action representations through the introduction of continuous numeric decision variables. Existing state-of-the-art approaches have primarily handled control parameters as embedded constraints alongside other temporal and numeric restrictions, and thus have implicitly treated them as additional constraints rather than as decision points in the search space. In this paper, we propose an efficient alternative that explicitly handles control parameters as true decision points within a systematic search scheme. We develop a best-first, heuristic search algorithm that operates over infinite decision spaces defined by control parameters and prove a notion of completeness in the limit under certain conditions. Our algorithm leverages the concept of delayed partial expansion, where a state is not fully expanded but instead incrementally expands a subset of its successors. Our results demonstrate that this novel search algorithm is a competitive alternative to existing approaches for solving planning problems involving control parameters.

It is well known that numeric planning can be made decidable if the domain of all numeric state variables is finite. This bounded formulation can be polynomially compiled into classical planning with Boolean conditions and conditional effects preserving the plan size exactly. However, it remains unclear whether this compilation has any practical utility. To explore this aspect, this work revisits the theoretical compilation framework from a practical perspective, focusing on the fragment of simple numeric planning. Specifically, we introduce three different compilations. The first, called one-hot, aims to systematise the current practice among planning practitioners of modelling numeric planning through classical planning. The other two, termed binary compilations, extend and specialise the logarithmic encoding introduced in previous literature. Our experimental analysis reveals that the overly complex logarithmic encoding can, surprisingly, be made practical with some representational expedients. Among these, the use of axioms is particularly crucial. Furthermore, we identify a class of mildly numeric planning problems where a classical planner, i.e., LAMA, when run on the compiled problem, is highly competitive with state-of-the-art numeric planners.

In this paper, we investigate the application of heuristics based on Graph Neural Networks (GNNs) to lifted numeric planning problems, an area that has been relatively unexplored. Building upon the GNN approach for learning general policies proposed by Staahlberg et al., we extend the architecture to make it sensitive to the numeric components inherent in the planning problems we address. We achieve this by observing that, although the state space of a numeric planning problem is infinite, the finite subgoal structure of the problem can be incorporated into the architecture, allowing for the construction of only a finite number of nodes. Instead of learning general policies, we train our models to function as a heuristic within a best-first search algorithm. We explore various configurations of this architecture and demonstrate that the resulting heuristics are highly informative and, in certain domains, offer a better trade-off between guidance and computational cost compared to other inductive and deductive heuristics.

This frontmatter introduces the proceedings of the Eighteenth International Symposium on Combinatorial Search (SoCS 2025), held from August 12–15, 2025, in Scotland, United Kingdom. It includes a preface by the conference co-chairs—Maxim Likhachev, Hana Rudová, and Enrico Scala—along with details on the Best Paper Awards, the organizing and program committees, and the sponsors of this edition.

We study planning for temporally extended goals expressed in Pure-Past Linear Temporal Logic ( ppltl ) in the context of deterministic (i.e., classical) and fully observable nondeterministic (FOND) domains. ppltl is the variant of Linear-time Temporal Logic on finite traces ( ltl f ) that refers to the past rather than the future. Although ppltl is as expressive as ltl f , we show that it is computationally much more effective for planning. In particular, we show that checking the validity of a plan for a ppltl formula is Markovian. This is achieved by introducing a linear number of additional propositional variables that capture the validity of the entire formula in a modular fashion. The solution encoding introduces only a linear number of new fluents proportional to the size of the ppltl goal and does not require any additional spurious action. We implement our solution technique in a system called Plan4Past , which can be used alongside state-of-the-art classical and FOND planners. Our empirical analysis demonstrates the practical effectiveness of Plan4Past in both classical and FOND problems, showing that the resulting planner performs overall better than other planning approaches for ltl f goals.

This paper studies an approach to planning with PDDL3 constraints involving mixed propositional and numeric conditions, as well as metric time constraints. We show how the whole PDDL3 with instantaneous actions can be compiled away into a numeric planning problem without PDDL3 constraints, enabling the use of any state-of-the-art numeric planner that is agnostic to the existence of PDDL3. Our solution exploits the concept of regression. In addition to a basic compilation, we present an optimized variant based on the observation that it is possible to make the compilation sensitive to the structure of the problem to solve; this can be done by reasoning on the interactions between the problem actions and the constraints. The resulting optimization substantially reduces the size of the planning task. We experimentally observe that our approach significantly outperforms existing state-of-the-art planners supporting the same class of constraints over known benchmark domains, settling a new state-of-the-art planning system for PDDL3.

The paper introduces a novel polynomial compilation technique for the sound and complete removal of conditional effects in classical planning problems. Similar to Nebel's polynomial compilation of conditional effects, our solution also decomposes each action with conditional effects into several simpler actions. However, it does so more effectively by exploiting the actual structure of the given conditional effects. We characterise such a structure using a directed graph and leverage it to significantly reduce the number of additional atoms required, thereby shortening the size of valid plans. Our experimental analysis indicates that this approach enables the effective use of polynomial compilations, offering benefits in terms of modularity and reusability of existing planners. It also demonstrates that a compilation-based approach can be more efficient, either independently or in synergy with state-of-the-art optimal planners that directly support conditional effects.

In this paper, we introduce Shielded FOND planning (S-FOND), which is the problem of computing a strategy to reach a final-state goal while preserving a safety specification called shield. In particular, we characterize shields as Pure-Past Linear Temporal Logic formulas that must hold in every prefix of a state trace induced by a solution strategy, thus capturing the whole safety fragment of Linear Temporal Logic formulas over finite traces. We propose three solution encodings for handling S-FOND problems: the first, which is our baseline, simply views a shield as a temporally extended goal; the second, instead, blocks the execution of further actions when the shield gets violated, and the third prevents the execution of actions that could violate the shield by using the notion of regression. We formally prove the correctness of each encoding and experimentally prove their effectiveness over a set of benchmark shields.

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.

Powerful domain-independent planners have been developed to solve various types of planning problems. These planners often require a model of the acting agent's actions, given in some planning domain description language. Manually designing such an action model is a notoriously challenging task. An alternative is to automatically learn action models from observation. Such an action model is called safe if every plan created with it is consistent with the real, unknown action model. Algorithms for learning such safe action models exist, yet they cannot handle domains with conditional or universal effects, which are common constructs in many planning problems. We prove that learning non-trivial safe action models with conditional effects may require an exponential number of samples. Then, we identify reasonable assumptions under which such learning is tractable and propose Conditional-SAM, the first algorithm capable of doing so. We analyze Conditional-SAM theoretically and evaluate it experimentally. Our results show that the action models learned by Conditional-SAM can be used to solve perfectly most of the test set problems in most of the experimented domains.

This paper studies the problem of action model learning with full observability. Following the learning by search paradigm by Mitchell, we develop a theory for action model learning based on version spaces that interprets the task as search for hypotheses that are consistent with the learning samples. Our theoretical findings are instantiated in an online algorithm that maintains a compact representation of all solutions of the problem. Among this range of solutions, we bring attention to action models approximating the actual transition system from below (sound models) and from above (complete models). We show how to manipulate the output of our learning algorithm to build deterministic and non-deterministic formulations of the sound and complete models and prove that, given enough examples, both formulations converge into the very same true model. Our experiments reveal their usefulness over a range of planning domains.

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.

Conditional effects are a key feature in classical planning, enabling the description of actions whose outcomes are state-dependent. It is well known that the polynomial removal of conditional effects necessarily increases the size of a valid plan by a polynomial factor while preserving exactly the plan size requires an exponential encoding of the problem. The paper proposes and empirically evaluates optimisations for existing polynomial compilations. These optimisations aim to make the resulting compilations more suitable for planners while limiting the increase in plan size, which is inevitable if we want to keep the compilation polynomial. Specifically, the paper introduces a polynomial compilation technique that expands conditional effects when their number is below a certain threshold and sequentialises them otherwise. Additionally, the paper demonstrates that even straightforward optimisations can have a notable impact.

In the real world, the execution of the actions planned for an agent is never guaranteed to succeed, as they can fail in a number of unexpected ways that are not explicitly captured in the planning model. Based on these observations, we introduce the task of finding plans for classical planning that are resilient to action execution failures. We refer to this problem as Resilient Planning and to its solutions as K-resilient plans; such plans guarantee that an agent will always be able to reach its goals (possibly by replanning alternative sequences of actions) as long as no more than K failures occur along the way. We also present RESPLAN, a new algorithm for Resilient Planning, and we compare its performance to methods based on compiling Resilient Planning to Fully-Observable-Non-Deterministic (FOND) planning.

Recently, Pure-Past Temporal Logic (PPLTL) has proven highly effective in specifying temporally extended goals in deterministic planning domains. In this paper, we show its effectiveness also for fully observable nondeterministic (FOND) planning, both for strong and strong-cyclic plans. We present a notably simple encoding of FOND planning for PPLTL goals into standard FOND planning for final-state goals. The encoding only introduces few fluents (at most linear in the PPLTL goal) without adding any spurious action and allows planners to lazily build the relevant part of the deterministic automaton for the goal formula on-the-fly during the search. We formally prove its correctness, implement it in a tool called Plan4Past, and experimentally show its practical effectiveness.

Bounded numeric planning, where each numeric variable domain is bounded, is PSPACE-complete, but such a complexity result does not capture how hard it really is, since the same holds even for the practically much easier STRIPS fragment. A finer way to compare the difficulty of planning formalisms is through the notion of compilability, which has been however extensively studied only for classical planning by Nebel. This paper extends Nebel's framework to the setting of bounded numeric planning. First, we identify a variety of numeric fragments differing on the degree of the polynomials involved and the availability of features such as conditional effects and Boolean conditions; then we study the compilability of these fragments to each other and to the classical fragments. Surprisingly, numeric and classical planning with conditional effects and Boolean conditions can be compiled both ways preserving plan size exactly, while the same does not hold when targeting pure STRIPS. Our study reveals also that numeric fragments cluster into two equivalence classes separated by the availability of incomplete initial state specifications, a feature allowing to specify uncertainty in the initial state.

When planning the tasks of some physical entities that need to perform actions in the world (e.g., a Robot) it is necessary to take into account quite complex models for ensuring that the plan is actually executable. Indeed the state of these systems evolves according to potentially non-linear dynamics where interdependent discrete and continuous changes happen over the entire course of the task. Systems of this kind are typically compactly represented in planning using languages mixing propositional logic and mathematics. However, these languages are still poorly understood and exploited. What are the difficulties for planning in these settings? How can we build systems that can scale up over realistically sized problems? What are the domains which can benefit from these languages? This short paper shows the main two ingredients that are needed to build a heuristic search planner, outline the main impact that such techniques have on application, and provide some open challenges. These models and relative planners hold the promise to deliver explainable AI solutions that do not rely on large amounts of data.

PDDL+ is an expressive formalism that allows for the use of planning in hybrid discrete-continuous domains. To cope with unexpected situations, it is crucial for deployed planning-based systems to efficiently repair existing plans. In this paper, we revisit a recently proposed FIXABILITY framework for expressing and solving problems from validation to rescheduling of actions in PDDL+ plans.

PDDL+ models are advanced models of hybrid systems and the resulting problems are notoriously difficult for planning engines to cope with. An additional limiting factor for the exploitation of PDDL+ approaches in real-world applications is the restricted number of domain-independent planning engines that can reason upon those models. With the aim of deepening the understanding of PDDL+ models, in this work, we study a novel mapping between a time discretisation of pddl+ and numeric planning as for PDDL2.1 (level 2). The proposed mapping not only clarifies the relationship between these two formalisms but also enables the use of a wider pool of engines, thus fostering the use of hybrid planning in real-world applications. Our experimental analysis shows the usefulness of the proposed translation and demonstrates the potential of the approach for improving the solvability of complex PDDL+ instances.

Automated planning is a prominent Artificial Intelligence (AI) challenge that has been extensively studied for decades, which has led to the development of powerful domain-independent planning systems. The performance of domain-independent planning systems are strongly affected by the structure of the search space, that is dependent on the application domain and on its encoding.This paper proposes and investigates a novel way of combining machine learning and heuristic search to improve domain-independent planning. On the learning side, we use learning to predict the plan cost of a good solution for a given instance. On the planning side, we propose a bound-sensitive heuristic function that exploits such a prediction in a state-space planner. Our function combines the input prediction (derived inductively) with some pieces of information gathered during search (derived deductively). As the prediction can sometimes be grossly inaccurate, the function also provides means to recognise when the provided information is actually misguiding the search. Our experimental analysis demonstrates the usefulness of the proposed approach in a standard heuristic best-first search schema.

Automated planning is a prominent AI challenge, and it is now exploited in a range of real-world applications. There are three crucial aspects of automated planning: the planning engine, the domain model, and the problem instance. While the planning engine and the domain model can be engineered and optimised offline, in many applications there is the need to generate problem instances on the fly. In this paper we focus on the challenges of on-the-fly knowledge acquisition for complex and variegated problem instances. We consider as a case study the application of planning to urban traffic control and we describe the designed and developed knowledge acquisition process. This allows us to discuss a range of lessons learned from the experience, and to point to important lines of research to support the knowledge acquisition process for automated planning applications.

The aim of this work is to explain the observed behaviour of a hybrid system (HS). The explanation problem is cast as finding a trajectory of the HS that matches some observations. By using the formalism of hybrid automata (HA), we characterize the explanations as the language of a network of HA that comprises one automaton for the HS and another one for the observations, thus restricting the behaviour of the HS exclusively to trajectories that explain the observations. We observe that this problem corresponds to a reachability problem in model-checking, but that state-of-the-art model checkers struggle to find concrete trajectories. To overcome this issue we provide a formal mapping from HA to PDDL+ and show how to use an off-the-shelf automated planner. An experimental analysis over domains with piece-wise constant, linear and nonlinear dynamics reveals that the proposed PDDL+ approach is much more efficient than solving directly the explanation problem with model-checking solvers.

In automated planning the ability of expressing constraints on the structure of the desired plans is important to deal with solution quality, as well as to express control knowledge. In PDDL3, this is supported through state-trajectory constraints corresponding to a class of LTLf formulae. In this paper, first we introduce a formalism to express trajectory constraints over actions in the plan, rather than over traversed states; Then we investigate compilation-based methods to deal with such constraints in propositional planning, and propose a new simple effective method. Finally, we experimentally study the usefulness of our action-trajectory constraints as a tool to express control knowledge. The experimental results show that the performance of a classical planner can be significantly improved by exploiting knowledge expressed by action constraints and handled by our compilation method, while the same knowledge turns out to be less beneficial when specified as state constraints and handled by two state-of-the-art systems supporting state constraints.

PDDL+ is an expressive planning formalism that enables the modelling of hybrid discrete-continuous domains. The resulting models are notoriously difficult to cope with, and few planning engines are natively supporting PDDL+. To foster the use of PDDL+, this paper revisits a set of recently proposed translations allowing to reformulate a PDDL+ task into a PDDL2.1 one. Such translations permit the use of a wider set of engines to solve complex hybrid problems.

In this paper, we study the computational complexity of action-based temporal planning interpreted over dense time. When time is assumed to be discrete, the problem is known to be EXPSPACE-complete. However, the official PDDL 2.1 semantics and many implementations interpret time as a dense domain. This work provides several results about the complexity of the problem, focusing on some particularly interesting cases: whether a minimum amount ε of separation between mutually exclusive events is given, in contrast to the separation being simply required to be non-zero, and whether or not actions are allowed to overlap already running instances of themselves. We prove the problem to be PSPACE-complete when self-overlap is forbidden, whereas, when it is allowed, it becomes EXPSPACE-complete with ε-separation and even undecidable with non-zero separation. These results clarify the computational consequences of different choices in the definition at the core of the PDDL 2.1 semantics, which have been vague until now.1

This paper studies the computational complexity of temporal planning, as represented by PDDL 2.1, interpreted over dense time. When time is considered discrete, the problem is known to be EXPSPACE-complete. However, the official PDDL 2.1 semantics, and many implementations, interpret time as a dense domain. This work provides several results about the complexity of the problem, studying a few interesting cases: whether a minimum amount ϵ of separation between mutually exclusive events is given, in contrast to the separation being simply required to be non-zero, and whether or not actions are allowed to overlap already running instances of themselves. We prove the problem to be PSPACE-complete when self-overlap is forbidden, whereas, when allowed, it becomes EXPSPACE-complete with ϵ-separation and undecidable with non-zero separation. These results clarify the computational consequences of different choices in the definition of the PDDL 2.1 semantics, which were vague until now.

In a counter-example based approach to conformant planning, choosing the right counter-example can improve performance. We formalise this observation by introducing the notion of “superiority” of a counter-example over another one, that holds whenever the superior counter-example exhibits more tags than the latter. We provide a theoretical explanation that supports the strategy of searching for maximally superior counter-examples, and we show how this strategy can be implemented. The empirical experiments validate our approach.

Hybrid PDDL+ models are amongst the most advanced models of systems and the resulting problems are notoriously difficult for planners to cope with due to nonlinear behaviours and immense search spaces. This difficulty is exacerbated by the potentially huge size of the fully ground representations that are used by modern planners in order to effectively explore the search space, which can make some problems impossible to tackle, with the result that in several situations the grounding phase has to be done externally or manually. This not only produces a much less compact problem description, but also complicates debugging and model reuse. To overcome the aforementioned limit, in this paper we investigate two simple grounding techniques for PDDL+ problems. The former method we propose extends the simple mechanism of invariance analysis to limit the groundings of operators upfront. The latter proposes to tackle the grounding process by means of a PDDL+ to Classical Planning abstraction. A preliminary experimental analysis over benchmarks coming from real case study shows that not only the grounding can be sped up, but that also problems that were out of the reach before can now be efficiently solved in an automated manner.

This paper studies novel subgoaling relaxations for automated planning with propositional and numeric state variables. Subgoaling relaxations address one source of complexity of the planning problem: the requirement to satisfy conditions simultaneously. The core idea is to relax this requirement by recursively decomposing conditions into atomic subgoals that are considered in isolation. Such relaxations are typically used for pruning, or as the basis for computing admissible or inadmissible heuristic estimates to guide optimal or satis_cing heuristic search planners. In the last decade or so, the subgoaling principle has underpinned the design of an abundance of relaxation-based heuristics whose formulations have greatly extended the reach of classical planning. This paper extends subgoaling relaxations to support numeric state variables and numeric conditions. We provide both theoretical and practical results, with the aim of reaching a good trade-o_ between accuracy and computation costs within a heuristic state-space search planner. Our experimental results validate the theoretical assumptions, and indicate that subgoaling substantially improves on the state of the art in optimal and satisficing numeric planning via forward state-space search.

In several industrial applications of planning, complex temporal metric trajectory constraints are needed to adequately model the problem at hand. For example, in production plants, items must be processed following a “recipe” of steps subject to precise timing constraints. Modeling such domains is very challenging in existing action-based languages due to the lack of sufficiently expressive trajectory constraints.We propose a novel temporal planning formalism allowing quantified temporal constraints over execution timing of action instances. We build on top of instantaneous actions borrowed from classical planning and add expressive temporal constructs. The paper details the semantics of our new formalism and presents a solving technique grounded in classical, heuristic forward search planning. Our experiments prove the proposed framework superior to alternative state-of-theart planning approaches on industrial benchmarks, and competitive with similar solving methods on well known benchmarks took from the planning competition.

This paper studies an effect-abstraction based relaxation for reasoning about linear numeric planning problems. The effect-abstraction decomposes non-constant linear numeric effects into actions with conditional effects over additive constant numeric effects. With little effort, on this compiled version, it is possible to use known subgoaling based relaxations and relative heuristics. The combination of these two steps leads to a novel relaxation based heuristic. Theoretically, the relaxation is proved tighter than previous interval based relaxation and leading to safe-pruning heuristics. Empirically, a heuristic developed on this relaxation leads to substantial improvements for a class of problems that are currently out of the reach of state-of-the-art numeric planners.

We propose a new method for conformant planning based on two ideas. First given a small sample of the initial belief state we reduce conformant planning for this sample to a classical planning problem, giving us a candidate solution. Second we exploit regression as a way to compactly represent necessary conditions for such a solution to be valid for the non-deterministic setting. If necessary, we use the resulting formula to extract a counter-example to populate our next sampling. Our experiments show that this approach is competitive on a class of problems that are hard for traditional planners, and also returns generally shorter plans. We are also able to demonstrate unsatisfiability of some problems.

The paper generalises the notion of landmarks for reasoning about planning problems involving propositional and numeric variables. Intuitively, numeric landmarks are regions in the metric space defined by the problem whose crossing is necessary for its resolution. The paper proposes a relaxation-based method for their automated extraction directly from the problem structure, and shows how to exploit them to infer what we call disjunctive and additive hybrid action landmarks. The justification of such a disjunctive representation results from the intertwined propositional and numeric structure of the problem. The paper exercises their use in two novel admissible LP-Based numeric heuristics, and reports experiments on cost-optimal numeric planning problems. Results show the heuristics are more informed and effective than previous work for problems involving a higher number of (sub)goals.

We generalise the interval-based relaxation to sequential numeric planning problems with non-linear conditions and effects, and cyclic dependencies. This effectively removes all the limitations on the problem placed in previous work on numeric planning heuristics, and even allows us to extend the planning language with a wider set of mathematical functions. Heuristics obtained from the generalised relaxation are pruning-safe. We derive one such heuristic and use it to solve discrete-time control-like planning problems with autonomous processes. Few planners can solve such problems, and search with our new heuristic compares favourably with them.

Restricting the search space has shown to be an effective approach for improving the performance of automated planning systems. A planner-independent technique for pruning the search space is domain and problem reformulation. Recently, Outer Entanglements, which are relations between planning operators and initial or goal predicates, have been introduced as a reformulation technique for eliminating potential undesirable instances of planning operators, and thus restricting the search space. Reformulation techniques, however, have been mainly applied in classical planning, although many real-world planning applications require to deal with numerical information. In this paper, we investigate the usefulness of reformulation approaches in planning with numerical fluents. In particular, we propose and extension of the notion of outer entanglements for handling numeric fluents. An empirical evaluation, which involves 150 instances from 5 domains, shows promising results.

The paper addresses the problem of executing a plan in a dynamic environment for tasks involving constraints on consumable resources modeled as numeric fluents. In particular, the paper proposes a novel monitoring and adaptation strategy joining reactivity and proactivity in a unified framework. By exploiting the flexibility of a multi modality plan (where each action can be executed in different modalities), reactivity and proactivity are guaranteed by means of a reconfiguration step. The reconfiguration is performed (i) when the plan is no more valid to recovery from the impasse (reactively), or (ii) under the lead of a kernel based strategy to enforce the tolerance to unexpected situations (proactivity). Both mechanisms have been integrated into a continual planning system and experimentally evaluated over three numeric domains, extensions of planning competition domains. Results show that the approach is able to increase the percentage of cases successfully solved while preserving efficiency in most situations.

Robust execution of exploration mission plans has to deal with limited computational power on-board a planetary rover, and with limited rover's autonomy. Typically, these limitations prevent the rover to synthesize a new mission plan when some unexpected contingency arises. The paper shows that when such deviations refers to anomalies on the consumption of resources, robust execution can be achieved efficiently through an action reconfiguration approach instead of a replanning from scratch. Building up on an extended action model representation, the paper proposes an effective continual planner - ReCon - that, exploiting a general purpose CSP solver, is able to (i) detect violations of mission resource constraints, and (ii) find (if any) a new configuration of actions

Many realistic life scenarios require dealing with deadlines and action durations. Such constraints, together with propositional and resource conditions must be taken into account in order to make plans which are actually feasible. In order to combine these aspects, the paper deals with the entailed temporal constrained planning problem by using the framework of numeric planning, based on an action centred philosophy a-la PDDL. The approach is motivated by the necessity of integrating scheduling and planning in the context of a multi-modal journey planning problem. In order to evaluate the feasibility of the approach, the paper presents JoPA, a web service architecture which has been thoroughly evaluated employing two state of the art numeric planning systems, i.e. Metric-FF and Colin. Results show that the approach is feasible considering (un) constrained and optimization tasks.