Patrik Haslum

KR Conference 2025 Conference Paper

Probabilistic HTN Planning: Formalization and Computational Complexity Analysis

• Mohammad Yousefi
• Johannes Schmalz
• Patrik Haslum
• Pascal Bercher

Hierarchical Task Network (HTN) planning is an approach to sequential decision making that allows expressing complex grammar-like path constraints. In this paper, we first introduce an extension to HTN planning that takes probabilistic outcomes into account, and then study the computational complexity of deciding such problems either by finding a fixed sequence of actions (i. e. , a conformant solution) or an outcome-dependent policy. This formalization extends factored Markov Decision Processes (MDPs) to have a hierarchical structure. In all studied cases, the conformant solutions are harder to obtain than their non-deterministic analogues, whereas policies are not always harder. Surprisingly, unlike their deterministic counterparts, severely restricted cases of probabilistic HTN problems are proven to be undecidable. The result holds even if all of the transition probabilities are bounded to be 0, 0. 5, or 1.

IJCAI Conference 2024 Conference Paper

A Survey on Plan Optimization

• Pascal Bercher
• Patrik Haslum
• Christian Muise

Automated Planning deals with finding a sequence of actions that solves a given (planning) problem. The cost of the solution is a direct consequence of these actions, for example its number or their accumulated costs. Thus, in most applications, cheaper plans are preferred. Yet, finding an optimal solution is more challenging than finding some solution. So, many planning algorithms find some solution and then post-process, i. e. , optimize it -- a technique called plan optimization. Over the years many different approaches were developed, not all for the same kind of plans, and not all optimize the same metric. In this comprehensive survey, we give an overview of the existing plan optimization goals, their computational complexity (if known), and existing techniques for such optimizations.

AAAI Conference 2024 Conference Paper

NaRuto: Automatically Acquiring Planning Models from Narrative Texts

• Ruiqi Li
• Leyang Cui
• Songtuan Lin
• Patrik Haslum

Domain model acquisition has been identified as a bottleneck in the application of planning technology, especially within narrative planning. Learning action models from narrative texts in an automated way is essential to overcome this barrier, but challenging because of the inherent complexities of such texts. We present an evaluation of planning domain models derived from narrative texts using our fully automated, unsupervised system, NaRuto. Our system combines structured event extraction, predictions of commonsense event relations, and textual contradictions and similarities. Evaluation results show that NaRuto generates domain models of significantly better quality than existing fully automated methods, and even sometimes on par with those created by semi-automated methods, with human assistance.

JAIR Journal 2023 Journal Article

Maximisation of Admissible Multi-Objective Heuristics

• Patrik Haslum
• Ryan Xiao Wang

In multi-objective (MO) heuristic search, solution costs, as well as heuristic values, are sets of multi-dimensional cost vectors, representing possible non-dominated trade-offs between objectives. The maximum of two or more such vector sets, which is an important operation in creating informative admissible MO heuristics, can be defined in several ways: Geißer et al. recently proposed two MO maximum operators, the component-wise maximum (comax) and the anti-dominance maximum (admax), which represent different trade-offs between informativeness and computational cost. We show that the anti-dominance maximum is not admissibility-preserving, and propose an alternative, the “select one” maximum (somax). We also show that the comax operator is the greatest admissibility-preserving MO maximum, and briefly investigate its efficient implementation. The conclusion of our experimental results is that somax achieves a trade-off similar to that intended with admax – cheaper to compute but less informed – also when compared to an improved comax implementation.

ICAPS Conference 2022 Conference Paper

Admissible Heuristics for Multi-Objective Planning

• Florian Geißer
• Patrik Haslum
• Sylvie Thiébaux
• Felipe W. Trevizan

Planning problems of practical relevance commonly include multiple objectives that are difficult to weight a priori. Several heuristic search algorithms computing the Pareto front of non-dominated solutions have been proposed to handle these multi-objective (MO) planning problems. However, the design of informative admissible heuristics to guide these algorithms has not received the same level of attention. The standard practice is to use the so-called ideal point combination, which applies a single-objective heuristic to each objective independently, without capturing any of the trade-offs between them. This paper fills this gap: we extend several classes of classical planning heuristics to the multi-objective case, in such a way as to reflect the tradeoffs underlying the various objectives. We find that MO abstraction heuristics achieve overall the best performance, but that not every MO generalisation pays off.

KR Conference 2021 Conference Paper

Unsupervised Novelty Characterization in Physical Environments Using Qualitative Spatial Relations

• Ruiqi Li
• Hua Hua
• Patrik Haslum
• Jochen Renz

Detecting, characterizing and adapting to novelty, whether in the form of previously unseen objects or phenomena, or unexpected changes in the behavior of known elements, is essential for Artificial Intelligence agents to operate reliably in unconstrained real-world environments. We propose an automatic, unsupervised approach to novelty characterization for dynamic domains, based on describing the behaviors and interactions of objects in terms of their possible actions. To abstract from the variety of realizations of an action that can occur in physical domains, we model states in terms of qualitative spatial relations (QSRs) between their entities. By first learning a model of actions in the non-novel environment from the state transitions observed as the agent interacts with the world, we can detect novelty by the persistent deviations from this model that it causes, and characterize the novelty by new or modified actions. We also present a new method of learning action models from observation, based on conceptual similarity and hierarchical clustering.

JAIR Journal 2020 Journal Article

Subgoaling Techniques for Satisficing and Optimal Numeric Planning

• Enrico Scala
• Patrik Haslum
• Sylvie Thiébaux
• Miquel Ramirez

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 satisificing 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-off 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.

JAIR Journal 2019 Journal Article

Dynamic Controllability of Controllable Conditional Temporal Problems with Uncertainty

• Jing Cui
• Patrik Haslum

Dynamic Controllability (DC) of a Simple Temporal Problem with Uncertainty (STPU) uses a dynamic decision strategy, rather than a fixed schedule, to tackle temporal uncertainty. We extend this concept to the Controllable Conditional Temporal Problem with Uncertainty (CCTPU), which extends the STPU by conditioning temporal constraints on the assignment of controllable discrete variables. We define dynamic controllability of a CCTPU as the existence of a strategy that decides on both the values of discrete choice variables and the scheduling of controllable time points dynamically. This contrasts with previous work, which made a static assignment of choice variables and dynamic decisions over time points only. We propose an algorithm to find such a fully dynamic strategy. The algorithm computes the "envelope" of outcomes of temporal uncertainty in which a particular assignment of discrete variables is feasible, and aggregates these over all choices. When an aggregated envelope covers all uncertain situations of the CCTPU, the problem is dynamically controllable. However, the algorithm is complete only under certain assumptions. Experiments on an existing set of CCTPU benchmarks show that there are cases in which making both discrete and temporal decisions dynamically it is feasible to satisfy the problem constraints while assigning the discrete variables statically it is not.

ICAPS Conference 2019 Conference Paper

Planning with Global State Constraints and State-Dependent Action Costs

• Franc Ivankovic
• Dan Gordon 0002
• Patrik Haslum

Planning with global state constraints is an extension of classical planning in which some properties of each state are derived via a set of equations, rules or constraints. This extension enables more elegant modelling of networked physical systems such as power grids. So far, research in this setting focused on domains where action costs are constant, rather than a function of a state in which the action is applied. This limitation prevents us from accurately specifying the objective in some real-world domains, leading to generation of suboptimal plans. For example, when reconfiguring a power network, we often need to temporarily leave some users without electricity for a certain amount of time, and in such circumstances it is desirable to reduce the unsupplied load over the total time span. This preference can be expressed using statedependent action costs. We extend planning with global state constraints to include state-dependent action costs, adapt abstraction heuristics to this setting, and show improved performance on a set of problems.

ICAPS Conference 2018 Conference Paper

A TIL-Relaxed Heuristic for Planning with Time Windows

• Tony Allard
• Charles Gretton
• Patrik Haslum

We consider planning problems with time windows, in which the availability of discrete resources is time constrained. We develop a novel heuristic that addresses specifically the difficulty of coordinating actions within time windows. The heuristic is based on solving a temporally relaxed problem and measuring the magnitude by which the relaxed solution violates the time window constraints. Applied in a state-space search planner, the heuristic reduces the number of dead-ends encountered during search, and improves planner coverage.

IJCAI Conference 2018 Conference Paper

Effect-Abstraction Based Relaxation for Linear Numeric Planning

• Dongxu Li
• Enrico Scala
• Patrik Haslum
• Sergiy Bogomolov

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.

JAIR Journal 2018 Journal Article

Extending Classical Planning with State Constraints: Heuristics and Search for Optimal Planning

• Patrik Haslum
• Franc Ivankovic
• Miquel Ramirez
• Dan Gordon
• Sylvie Thiebaux
• Vikas Shivashankar
• Dana S. Nau

We present a principled way of extending a classical AI planning formalism with systems of state constraints, which relate - sometimes determine - the values of variables in each state traversed by the plan. This extension occupies an attractive middle ground between expressivity and complexity. It enables modelling a new range of problems, as well as formulating more efficient models of classical planning problems. An example of the former is planning-based control of networked physical systems - power networks, for example - in which a local, discrete control action can have global effects on continuous quantities, such as altering flows across the entire network. At the same time, our extension remains decidable as long as the satisfiability of sets of state constraints is decidable, including in the presence of numeric state variables, and we demonstrate that effective techniques for cost-optimal planning known in the classical setting - in particular, relaxation-based admissible heuristics - can be adapted to the extended formalism. In this paper, we apply our approach to constraints in the form of linear or non-linear equations over numeric state variables, but the approach is independent of the type of state constraints, as long as there exists a procedure that decides their consistency. The planner and the constraint solver interact through a well-defined, narrow interface, in which the solver requires no specialisation to the planning context.

IJCAI Conference 2018 Conference Paper

Operator Counting Heuristics for Probabilistic Planning

• Felipe Trevizan
• Sylvie Thiébaux
• Patrik Haslum

For the past 25 years, heuristic search has been used to solve domain-independent probabilistic planning problems, but with heuristics that determinise the problem and ignore precious probabilistic information. In this paper, we present a generalization of the operator-counting family of heuristics to Stochastic Shortest Path problems (SSPs) that is able to represent the probability of the actions outcomes. Our experiments show that the equivalent of the net change heuristic in this generalized framework obtains significant run time and coverage improvements over other state-of-the-art heuristics in different planners.

ICAPS Conference 2017 Conference Paper

Dynamic Controllability of Controllable Conditional Temporal Problems with Uncertainty

• Jing Cui
• Patrik Haslum

Dynamic Controllability (DC) of a Simple Temporal Problem with Uncertainty (STPU) uses a dynamic decision strategy, rather than a fixed schedule, to tackle temporal uncertainty. We extend this concept to the Controllable Conditional Temporal Problem with Uncertainty (CCTPU), which extends the STPU by conditioning temporal constraints on the assignment of controllable discrete variables. We define dynamic controllability of a CCTPU as the existence of a strategy that decides on both the values of discrete choice variables and the scheduling of controllable time points dynamically. This contrasts with previous work, which made a static assignment of choice variables and dynamic decisions over time points only. We propose an algorithm to find such a fully dynamic strategy. The algorithm computes the ''envelope'' of outcomes of temporal uncertainty in which a particular assignment of discrete variables is feasible, and aggregates these over all choices. When an aggregated envelope covers all uncertain situations of the CCTPU, the problem is dynamically controllable. However, the algorithm is not complete. Experiments on an existing set of CCTPU benchmarks show that there are cases in which making both discrete and temporal decisions dynamically it is feasible to satisfy the problem constraints, while assigning the discrete variables statically it is not.

IJCAI Conference 2017 Conference Paper

Landmarks for Numeric Planning Problems

• Enrico Scala
• Patrik Haslum
• Daniele Magazzeni
• Sylvie Thiébaux

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.

ICAPS Conference 2017 Conference Paper

Occupation Measure Heuristics for Probabilistic Planning

• Felipe W. Trevizan
• Sylvie Thiébaux
• Patrik Haslum

For the past 25 years, heuristic search has been used to solve domain-independent probabilistic planning problems, but with heuristics that determinise the problem and ignore precious probabilistic information. To remedy this situation, we explore the use of occupation measures, which represent the expected number of times a given action will be executed in a given state of a policy. By relaxing the well-known linear program that computes them, we derive occupation measure heuristics -- the first admissible heuristics for stochastic shortest path problems (SSPs) taking probabilities into account. We show that these heuristics can also be obtained by extending recent operator-counting heuristic formulations used in deterministic planning. Since the heuristics are formulated as linear programs over occupation measures, they can easily be extended to more complex probabilistic planning models, such as constrained SSPs (C-SSPs). Moreover, their formulation can be tightly integrated into i-dual, a recent LP-based heuristic search algorithm for (constrained) SSPs, resulting in a novel probabilistic planning approach in which policy update and heuristic computation work in unison. Our experiments in several domains demonstrate the benefits of these new heuristics and approach.

JAIR Journal 2017 Journal Article

Resolving Over-Constrained Temporal Problems with Uncertainty through Conflict-Directed Relaxation

• Peng Yu
• Brian Williams
• Cheng Fang
• Jing Cui
• Patrik Haslum

Over-subscription, that is, being assigned too many things to do, is commonly encountered in temporal scheduling problems. As human beings, we often want to do more than we can actually do, and underestimate how long it takes to perform each task. Decision makers can benefit from aids that identify when these failure situations are likely, the root causes of these failures, and resolutions to these failures. In this paper, we present a decision assistant that helps users resolve over-subscribed temporal problems. The system works like an experienced advisor that can quickly identify the cause of failure underlying temporal problems and compute resolutions. The core of the decision assistant is the Best-first Conflict-Directed Relaxation (BCDR) algorithm, which can detect conflicting sets of constraints within temporal problems, and computes continuous relaxations for them that weaken constraints to the minimum extent, instead of removing them completely. BCDR is an extension to the Conflict-Directed A* algorithm, first developed in the model-based reasoning community to compute most likely system diagnoses or reconfigurations. It generalizes the discrete conflicts and relaxations, to hybrid conflicts and relaxations, which denote minimal inconsistencies and minimal relaxations to both discrete and continuous relaxable constraints. In addition, BCDR is capable of handling temporal uncertainty, expressed as either set-bounded or probabilistic durations, and can compute preferred trade-offs between the risk of violating a schedule requirement, versus the loss of utility by weakening those requirements. BCDR has been applied to several decision support applications in different domains, including deep-sea exploration, urban travel planning and transit system management. It has demonstrated its effectiveness in helping users resolve over-subscribed scheduling problems and evaluate the robustness of existing solutions. In our benchmark experiments, BCDR has also demonstrated its efficiency on solving large-scale scheduling problems in the aforementioned domains. Thanks to its conflict-driven approach for computing relaxations, BCDR achieves one to two orders of magnitude improvements on runtime performance when compared to state-of-the-art numerical solvers.

IJCAI Conference 2016 Conference Paper

Heuristics for Numeric Planning via Subgoaling

• Enrico Scala
• Patrik Haslum
• Sylvie Thi
• eacute; baux

The paper presents a new relaxation for hybrid planning with continuous numeric and propositional state variables based on subgoaling, generalising the subgoaling principle underlying the hmax and hadd heuristics to such problems. Our relaxation improves on existing interval-based relaxations by taking into account some negative interactions between effects when achieving a subgoal, resulting in better estimates. We show conditions on the planning model ensuring that this new relaxation leads to tractable, and, for the hmax version, admissible, heuristics. The new relaxation can be combined with the interval-based relaxation, to derive heuristics applicable to general numeric planning, while still providing more informed estimates for the subgoals that meet these conditions. Experiments show the effectiveness of its inadmissible and admissible version on satisficing and optimal numeric planning, respectively. As far as we know, this is the first admissible heuristic enabling cost-optimal numeric planning.

ECAI Conference 2016 Conference Paper

Interval-Based Relaxation for General Numeric Planning

• Enrico Scala
• Patrik Haslum
• Sylvie Thiébaux
• Miquel Ramírez

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.

ICAPS Conference 2016 Conference Paper

Numeric Planning with Disjunctive Global Constraints via SMT

• Enrico Scala
• Miquel Ramírez
• Patrik Haslum
• Sylvie Thiébaux

This paper describes a novel encoding for sequential numeric planning into the problem of determining the satisfiability of a logical theory T. We introduce a novel technique, orthogonal to existing work aiming at producing more succinct encodings that enables the theory solver to roll up an unbounded yet finite number of instances of an action into a single plan step, greatly reducing the horizon at which T models valid plans. The technique is then extended to deal with problems featuring disjunctive global constraints, in which the state space becomes a non-convex n dimensional polytope. In order to empirically evaluate the encoding, we build a planner, SPRINGROLL, around a state–of–the–art off– the–shelf SMT solver. Experiments on a diverse set of domains are finally reported, and results show the generality and efficiency of the approach.

ICAPS Conference 2016 Conference Paper

Practical Undoability Checking via Contingent Planning

• Jeanette Daum
• Álvaro Torralba
• Jörg Hoffmann 0001
• Patrik Haslum
• Ingo Weber

We consider a general concept of undoability, asking whether a given action can always be undone, no matter which state it is applied to. This generalizes previous concepts of invertibility, and is relevant for search as well as applications. Naïve undoability checking requires to enumerate all states an action is applicable to. Extending and operationalizing prior work in this direction, we introduce a compilation into contingent planning, replacing such enumeration by standard techniques handling large belief states. We furthermore introduce compilations for checking whether one can always get back to an at-least-as-good state, as well as for determining partial undoability, i. e. , undoability on a subset of states an action is applicable to. Our experiments on IPC benchmarks and in a cloud management application show that contingent planners are often effective at solving this kind of problem, hence providing a practical means for undoability checking.

JAIR Journal 2015 Journal Article

Continuing Plan Quality Optimisation

• Fazlul Hasan Siddiqui
• Patrik Haslum

Finding high quality plans for large planning problems is hard. Although some current anytime planners are often able to improve plans quickly, they tend to reach a limit at which the plans produced are still very far from the best possible, but these planners fail to find any further improvement, even when given several hours of runtime. We present an approach to continuing plan quality optimisation at larger time scales, and its implementation in a system called BDPO2. Key to this approach is a decomposition into subproblems of improving parts of the current best plan. The decomposition is based on block deordering, a form of plan deordering which identifies hierarchical plan structure. BDPO2 can be seen as an application of the large neighbourhood search (LNS) local search strategy to planning, where the neighbourhood of a plan is defined by replacing one or more subplans with improved subplans. On-line learning is also used to adapt the strategy for selecting subplans and subplanners over the course of plan optimisation. Even starting from the best plans found by other means, BDPO2 is able to continue improving plan quality, often producing better plans than other anytime planners when all are given enough runtime. The best results, however, are achieved by a combination of different techniques working together.

IJCAI Conference 2015 Conference Paper

Optimal Planning with Axioms

• Franc Ivankovic
• Patrik Haslum

The use of expressive logical axioms to specify derived predicates often allows planning domains to be formulated more compactly and naturally. We consider axioms in the form of a logic program with recursively defined predicates and negationas-failure, as in PDDL 2. 2. We show that problem formulations with axioms are not only more elegant, but can also be easier to solve, because specifying indirect action effects via axioms removes unnecessary choices from the search space of the planner. Despite their potential, however, axioms are not widely supported, particularly by cost-optimal planners. We draw on the connection between planning axioms and answer set programming to derive a consistency-based relaxation, from which we obtain axiom-aware versions of several admissible planning heuristics, such as hmax and pattern database heuristics.

ICAPS Conference 2015 Conference Paper

Optimising Bounds in Simple Temporal Networks with Uncertainty under Dynamic Controllability Constraints

• Jing Cui
• Peng Yu
• Cheng Fang
• Patrik Haslum
• Brian Williams 0001

Dynamically controllable simple temporal networks with uncertainty (STNU) are widely used to represent temporal plans or schedules with uncertainty and execution flexibility. While the problem of testing an STNU for dynamic controllability is well studied, many use cases — for example, problem relaxation or schedule robustness analysis — require optimising a function over STNU time bounds subject to the constraint that the network is dynamically controllable. We present a disjunctive linear constraint model of dynamic controllability, show how it can be used to formulate a range of applications, and compare a mixed-integer, a non-linear programming, and a conflict-directed search solver on the resulting optimisation problems. Our model also provides the first solution to the problem of optimisation over a probabilistic STN subject to dynamic controllability and chance constraints.

ICAPS Conference 2015 Conference Paper

Temporal Landmarks: What Must Happen, and When

• Erez Karpas
• David Wang
• Brian Williams 0001
• Patrik Haslum

Current temporal planners have a hard time solving large, real-world problems which involve dealing with metric time and concurrent actions. While landmarks have enabled classical planners to scale up to significantly larger problems, they have not yet brought as much benefit to temporal planning. We argue that the reason for this is that for landmarks to make an effective addition to planning with complex temporal interactions (such as required concurrency), they must incorporate information about the timing of conditions and events. We define temporal landmarks, which associate time intervals and time points, respectively, with state and action landmarks, thereby capturing both what must happen and when it must happen. We show how to derive temporal landmarks and constraints on their associated time points from planning problems, and how exploiting them, in a planner-independent way, can improve planner performance. Notably, the greatest gain is on problems which require concurrency, showing that the temporal information we add to landmarks complements the reasoning used by current temporal planners.

ICAPS Conference 2014 Conference Paper

Optimal Planning with Global Numerical State Constraints

• Franc Ivankovic
• Patrik Haslum
• Sylvie Thiébaux
• Vikas Shivashankar
• Dana S. Nau

Automating the operations of infrastructure networks such as energy grids and oil pipelines requires a range of planning and optimisation technologies. However, current planners face significant challenges in responding to this need. Notably, they are unable to model and reason about the global numerical state constraints necessary to capture flows and similar physical phenomena occurring in these networks. A single discrete control action can affect the flow throughout the network in a way that may depend on the entire network topology. Determining whether preconditions, goals and invariant conditions are satisfied requires solving a system of numerical constraints after each action application. This paper extends domain-independent optimal planning to this kind of reasoning. We present extensions of the formalism, relaxed plans, and heuristics, as well as new search variants and experimental results on two problem domains.

TCS Journal 2014 Journal Article

Recent advances in unfolding technique

• Blai Bonet
• Patrik Haslum
• Victor Khomenko
• Sylvie Thiébaux
• Walter Vogler

ICAPS Conference 2013 Conference Paper

Heuristics for Bounded-Cost Search

• Patrik Haslum

The problem of searching for a plan with cost at most equal to a given absolute bound has attracted interest recently, and several search algorithms tailored specifically to this problem have been proposed. We investigate instead how to adapt planning heuristics to this setting. A few of the resulting heuristics, used in a greedy bounded-cost search, perform better than previous and baseline methods, but only by a small margin. Making effective use of the cost bound in bounded-cost planning, it appears, remains a challenge.

IJCAI Conference 2013 Conference Paper

Optimal Delete-Relaxed (and Semi-Relaxed) Planning with Conditional Effects

• Patrik Haslum

Recently, several methods have been proposed for optimal delete-free planning. We present an incremental compilation approach that enables these methods to be applied to problems with conditional effects, which none of them support natively. With an h+ solver for problems with conditional effects in hand, we also consider adapting the h++ anytime lower bound function to use the more spaceefficient PC ce compilation. This avoids the memory limitation of the original h++ caused by its reliance on an exponential-space compilation. It also leads to improvements on some problems where memory is not an issue.

IJCAI Conference 2013 Conference Paper

Plan Quality Optimisation via Block Decomposition

• Fazlul Hasan Siddiqui
• Patrik Haslum

AI planners have to compromise between the speed of the planning process and the quality of the generated plan. Anytime planners try to balance these objectives by finding plans of better quality over time, but current anytime planners often do not make effective use of increasing runtime beyond a certain limit. We present a new method of continuing plan improvement, that works by repeatedly decomposing a given plan into subplans and optimising each subplan locally. The decomposition exploits block-structured plan deordering to identify coherent subplans, which make sense to treat as units. This approach extends the “anytime capability” of current planners – to provide continuing plan quality improvement at any time scale.

ICAPS Conference 2013 Conference Paper

Safe, Strong, and Tractable Relevance Analysis for Planning

• Patrik Haslum
• Malte Helmert
• Anders Jonsson 0001

In large and complex planning problems, there will almost inevitably be aspects that are not relevant to a specific problem instance. Thus, identifying and removing irrelevant parts from an instance is one of the most important techniques for scaling up automated planning. We examine the path-based relevance analysis method, which is safe (preserves plan existence and cost) and powerful but has exponential time complexity, and show how to make it run in polynomial time with only a minimal loss of pruning power.

KR Conference 2012 Conference Paper

Conflict-Based Diagnosis of Discrete Event Systems: Theory and Practice

• Grastien Alban
• Patrik Haslum
• Sylvie Thiebaux

sistency against the system model and observation, either proving it to be a diagnosis candidate or deriving a conflict which summarises the reasons why the hypothesis was rejected. The conflict is then used to generate successor hypotheses to be tested, ruling out any hypothesis that will fail the test for the same reasons. In this paper, we generalise the notion of conflict, and present a new conflict-based diagnosis approach that applies to a much broader class of systems, including DES. In our framework, a conflict represents a set of hypotheses which it excludes; the notion of conflict established by Reiter for static systems is a special case. In this sense, we unify the two previously disparate threads of diagnosis research. Using a sequence of relatively simple tests, our approach correctly computes the set of all preferred diagnosis candidates (under a few assumptions on the hypothesis space), and does so without needing to explicitly represent all possible system behaviors. This results in substantial efficiency gains, compared to state-of-the-art DES diagnosis methods. Conflicts help reduce the part of the hypothesis space that needs to be tested, but they also enable the presentation of new types of diagnostic information to users, e. g. that the occurrence of a certain fault excludes or implies that of another, or that some fault definitely occured before another. Any practical implementation of our approach relies on representing and manipulating sets of hypotheses symbolically, i. e., via sets of properties. We state the requirements that a property space used to implement the algorithm must satisfy, and we identify a suitable property space. For DES, we provide a SAT-based implementation, where hypotheses are represented by Boolean formulae over atomic properties and consistency tests are performed by a SAT solver. We demonstrate the improved efficiency of our approach on the problem of processing alarms generated by a power transmission system operated by TransGrid, an Australian utility. Summing up, our contributions are (1) a general characterisation of conflicts, (2) a conflict-based diagnosis algorithm for a broad class of systems, (3) the identification of the principles the symbolic representation must satisfy to facilitate an efficient implementation, and (4) a SAT implementation of the framework for DES systems which is used to solve a real-world problem. The paper is organised as follows. Section 2 introduces a small example which will be used for illustration throughout the paper. Section 3 provides background on Reiter’s con- We present a conflict-based approach to diagnosing Discrete Event Systems (DES) which generalises Reiter’s Diagnose algorithm to a much broader class of problems. This approach obviates the need to explicitly reconstruct the system’s behaviors that are consistent with the observation, as is typical of existing DES diagnosis algorithms. Instead, our algorithm explores the space of diagnosis hypotheses, testing hypotheses for consistency, and generating conflicts which rule out successors and other portions of the search space. Under relatively mild assumptions, our algorithm correctly computes the set of preferred diagnosis candidates. We investigate efficient symbolic representations of the hypotheses space and provide a SAT-based implementation of this framework which is used to address a real-world problem in processing alarms for a power transmission system.

ICAPS Conference 2012 Conference Paper

Incremental Lower Bounds for Additive Cost Planning Problems

• Patrik Haslum

We present a novel method for computing increasing lower bounds on the cost of solving planning problems, based on repeatedly solving and strengthening the delete relaxation of the problem. Strengthening is done by compiling select conjunctions into new atoms, similar to the Pm* construction. Because it does not rely on search in the state space, this method does not suffer some of the weaknesses of admissible search algorithms and therefore is able to prove higher lower bounds for many problems that are too hard for optimal planners to solve, thus narrowing the gap between lower bound and cost of the best known plan, providing better assurances of plan quality.

ICAPS Conference 2012 Conference Paper

Minimal Landmarks for Optimal Delete-Free Planning

• Patrik Haslum
• John K. Slaney
• Sylvie Thiébaux

We present a simple and efficient algorithm to solve delete-free planning problems optimally and calculate the h+ heuristic. The algorithm efficiently computes a minimum-cost hitting set for a complete set of disjunctive action landmarks generated on the fly. Unlike other recent approaches, the landmarks it generates are guaranteed to be set-inclusion minimal. In almost all delete-relaxed IPC domains, this leads to a significant coverage and runtime improvement.

ICAPS Conference 2012 Conference Paper

Semi-Relaxed Plan Heuristics

• Emil Ragip Keyder
• Jörg Hoffmann 0001
• Patrik Haslum

Heuristics based on the delete relaxation are at the forefront of modern domain-independent planning techniques. Here we introduce a principled and flexible technique for augmenting delete-relaxed tasks with a limited amount of delete information, by introducing special fluents that explicitly represent conjunctions of fluents in the original planning task. Differently from previous work in this direction, conditional effects are used to limit the growth of the task to be linear, rather than exponential, in the number of conjunctions that are introduced, making its use for obtaining heuristic functions feasible. We discuss how to obtain an informative set of conjunctions to be represented explicitly, and analyze and extend existing methods for relaxed planning in the presence of conditional effects. The resulting heuristics are empirically evaluated, and shown to be sometimes much more informative than standard delete-relaxation heuristics.

AAAI Conference 2012 Conference Paper

Semi-Relaxed Plan Heuristics

• Emil Keyder
• Joerg Hoffmann
• Patrik Haslum

The currently dominant approach to domain-independent planning is planning as heuristic search, with most successful planning heuristics being based on solutions to delete-relaxed versions of planning problems, in which the negative effects of actions are ignored. We introduce a principled, flexible, and practical technique for augmenting delete-relaxed tasks with a limited amount of delete information, by introducing special fluents that explicitly represent conjunctions of fluents in the original planning task. Differently from previous work, conditional effects are used to limit the growth of the task to be linear in the number of such conjunctions, making its use for obtaining heuristic functions feasible. The resulting heuristics are empirically evaluated, and shown to be sometimes much more informative than standard delete-relaxation heuristics. 1

ICAPS Conference 2011 Conference Paper

Partial-Order Support-Link Scheduling

• Debdeep Banerjee
• Patrik Haslum

Partial-order schedules are valued because they are flexible, and therefore more robust to unexpected delays. Previous work has indicated that constructing partial-order schedules by a two-stage method, in which a fixed-time schedule is first found and a partial order then lifted from it, is far more efficient than constructing them directly by a least-commitment partial-order scheduling algorithm. However, the two-stage method is limited to exploring only a fraction of the space of partial-order schedules, namely those that can be obtained from the given fixed-time schedule. We introduce a novel constraint formulation of partial-order scheduling, which establishes explicit resource-providing "links" between activities instead of detecting and eliminating potential resource conflicts. We show that this yields an algorithm that is much faster than previous (precedence constraint posting) partial-order scheduling methods, and comparable to the two-stage method in terms of the quality and robustness of the schedules it finds. This algorithm is also complete, and because it searches the entire space of partial-order schedules, can be adapted to optimising different robustness criteria.

ICAPS Conference 2010 Conference Paper

Cost-Optimal Factored Planning: Promises and Pitfalls

• Eric Fabre
• Loïg Jezequel
• Patrik Haslum
• Sylvie Thiébaux

Factored planning methods aim to exploit locality to efficiently solve large but "loosely coupled" planning problems by computing solutions locally and propagating limited information between components. However, all factored planning methods presented so far work with representations that require certain parameters to be bounded (e. g. number of coordination points between local plans considered); the satisfaction of those bounds by a given problem instance is difficult to establish a priori, and the influence of those parameters on the problem complexity is unclear. We present an instance of the factored planning framework using a representation of the (regular) sets of local plans by finite automata, which does not require any such bound. By substituting weighted automata, we can even do factored cost-optimal planning. We test an implementation of the method on the few standard planning benchmarks that we have found to be amenable to factoring. We show that this method runs in polynomial time under conditions similar to those considered in previous work, but not only under those conditions. Thus, what constitutes an essential measure of "factorability" remains obscure.

ECAI Conference 2010 Conference Paper

LTL Goal Specifications Revisited

• Andreas Bauer 0002
• Patrik Haslum

The language of linear temporal logic (LTL) has been proposed as a formalism for specifying temporally extended goals and search control constraints in planning. However, the semantics of LTL is defined wrt. infinite state sequences, while a finite plan generates only a finite trace. This necessitates the use of a finite trace semantics for LTL. A common approach is to evaluate LTL formulae on an infinite extension of the finite trace, obtained by infinitely repeating the last state. We study several aspects of this finite LTL se mantics: we show its satisfiability problem is PSpace-complete (same as normal LTL), show that it complies with all equivalence laws that hold under standard (infinite) LTL semantics, and compare it with other finite trace semantics for LTL proposed in planning and in runtime verification. We also examine different mechanisms for determining whether or not a finite trace satisfies or violates an LTL formula, interpreted using the infinite extension semantics.

AIJ Journal 2009 Journal Article

Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners

• Alfonso E. Gerevini
• Patrik Haslum
• Derek Long
• Alessandro Saetti
• Yannis Dimopoulos

ICAPS Conference 2009 Conference Paper

h m ( P ) = h 1 ( P m ): Alternative Characterisations of the Generalisation From h max To h m

• Patrik Haslum

The hm (m = 1...) family of admissible heuristics for STRIPS planning with additive costs generalise the hmax heuristic, which results when m = 1. We show that the step from h1 to hm can be made by changing the planning problem instead of the heuristic function. This furthers our understanding of the hm heuristic, and may inspire application of the same generalisation to admissible heuristics stronger than hmax. As an example, we show how it applies to the additive variant of hm obtained via cost splitting.

ICAPS Conference 2008 Conference Paper

A New Approach to Tractable Planning

• Patrik Haslum

We describe a restricted class of planning problems and polynomial time membership and plan existence decision algorithms for this class. The definition of the problem class is based on a graph representation of planning problems, similar to Petri nets, and the use of a graph grammar to characterise a subset of such graphs. Thus, testing membership in the class is a graph parsing problem. The planning algorithm also exploits this connection, making use of the parse tree. We show that the new problem class is incomparable with, i. e., neither a subset nor a superset of, previously known classes of tractable planning problems.

IJCAI Conference 2007 Conference Paper

• Patrik Haslum

Although even propositional STRIPS planning is a hard problem in general, many instances of the problem, including many of those commonly used as benchmarks, are easy. In spite of this, they are often hard to solve for domain-independent planners, because the encoding of the problem into a general problem specification formalism such as STRIPS hides structure that needs to be exploited to solve problems easily. We investigate the use of automatic problem transformations to reduce this "accidental" problem complexity. The main tool is abstraction: we identify a new, weaker, condition under which abstraction is "safe, " in the sense that any solution to the abstracted problem can be refined to a concrete solution (in polynomial time, for most cases) and also show how different kinds of problem reformulations can be applied to create greater opportunities for such safe abstraction.

AAAI Conference 2007 Conference Paper

Domain-Independent Construction of Pattern Database Heuristics for Cost-Optimal Planning

• Patrik Haslum
• Malte Helmert

Heuristic search is a leading approach to domain-independent planning. For cost-optimal planning, however, existing admissible heuristics are generally too weak to effectively guide the search. Pattern database heuristics (PDBs), which are based on abstractions of the search space, are currently one of the most promising approaches to developing better admissible heuristics. The informedness of PDB heuristics depends crucially on the selection of appropriate abstractions (patterns). Although PDBs have been applied to many search problems, including planning, there are not many insights into how to select good patterns, even manually. What constitutes a good pattern depends on the problem domain, making the task even more difficult for domain-independent planning, where the process needs to be completely automatic and general. We present a novel way of constructing good patterns automatically from the specification of planning problem instances. We demonstrate that this allows a domainindependent planner to solve planning problems optimally in some very challenging domains, including a STRIPS formulation of the Sokoban puzzle.

ICAPS Conference 2007 Conference Paper

Flexible Abstraction Heuristics for Optimal Sequential Planning

• Malte Helmert
• Patrik Haslum
• Jörg Hoffmann 0001

We describe an approach to deriving consistent heuristics for automated planning, based on explicit search in abstract state spaces. The key to managing complexity is interleaving composition of abstractions over different sets of state variables with abstraction of the partial composites.

AAAI Conference 2005 Conference Paper

New Admissible Heuristics for Domain-Independent Planning

• Patrik Haslum

Admissible heuristics are critical for effective domainindependent planning when optimal solutions must be guaranteed. Two useful heuristics are the hm heuristics, which generalize the reachability heuristic underlying the planning graph, and pattern database heuristics. These heuristics, however, have serious limitations: reachability heuristics capture only the cost of critical paths in a relaxed problem, ignoring the cost of other relevant paths, while PDB heuristics, additive or not, cannot accommodate too many variables in patterns, and methods for automatically selecting patterns that produce good estimates are not known. We introduce two refinements of these heuristics: First, the additive hm heuristic which yields an admissible sum of hm heuristics using a partitioning of the set of actions. Second, the constrained PDB heuristic which uses constraints from the original problem to strengthen the lower bounds obtained from abstractions. The new heuristics depend on the way the actions or problem variables are partitioned. We advance methods for automatically deriving additive hm and PDB heuristics from STRIPS encodings. Evaluation shows improvement over existing heuristics in several domains, although, not surprisingly, no heuristic dominates all the others over all domains.

ECAI Conference 2004 Conference Paper

Improving Heuristics Through Search

• Patrik Haslum

ICAPS Conference 2000 Conference Paper

Admissible Heuristics for Optimal Planning

• Patrik Haslum
• Hector Geffner

tlSP ~tm[HSPriLrt~ twor(’¢’Pllt p]. allllors th~tt st.,trch th, " statt~-Sl);.’, "1tsiltg i). lt heuristicfl|n, ’tiolt (’xtt’act, ’, l froill Strips cnt’tMiatgs, liSP dot’s a f(, rward s(mrch frtmt the ialt. bd stlttt, rt: vc, tuputiltg tim Imuristic in vv(. ry static. whih: HSPr tit)its a l’t: grt. ssit, u s(. ~Lr0’h fl’cJmth(. g0,:tl t’,,utpuling~t. -uitalth. r(. prv. ~vtttati,)u -f th(. h,., trim. it. nly om. v. Bt)th plmmvrs have. sht, wn Ko, td pvrfi)rman, ’o..ftt. n lm-lu, ’ingst dutic uts that a. rt. t’()lnpot it iv(" in tim(" mMnuml)vr of at: ti, ms with the s. hlti(, us fi, m, d Graphld~at and SATplanno. rs. HSPand HSPr. h,,wvvt. r. ar, ~uotoptimal plaonrrs. ThisisImcmts(. tht. |t(. uristit’ fu|, cti, mis n. t ~ulntissil, h: amltit(. s,.arch Mg,,rithnts arv not,,ptintal. In this palm/weaddrvss this probh. m. ’~, Vc fi)rntulatv, t now, tthnissiblc Iwuristlc fin’ lflanuing. us(~ it mguido: ut IDA*s(. art: h, a|ttl,.mpirically (. valuate tit, " result. trig optimMplann, ’r ov(. r ~, llllllll)(. r dt nue. hta. Tit(’ maiu c. ntrilmti,,n is tit(. id, ’a un, h. riyivg tht" Imuristic th~Lt yivhIs n. t (tilt" 11111". i’t whuh~fim, ily of Imlyutmlial att, I a, huissild, " houristi, ’s that Ira, b. avt: uracy fitr (’fiici(. ncy. Timformulation is gt’not’~d and sheds s. me light. n the hvuristics usvd ill liSP and Gr~qfltplan. and their rohttitm. It cxphfits tim fact,,rvd [Strips) rc. lm’s(’ntat. i~m c~f phtmting pr. bh. nm, mapping sh, rtcst. -imt. h probh: msin st,,tr-space into suit~tbly (l’r-fln, ’d sl.,rt(~st-patl, pr. l, hmls in otom-. ~pacv. Timfi)rvmlati-n applio. s with litt. lc vari: di-n to seqm. vtlal attd Itaxallvl l)[anning, and prtddcms will, ditll. rt. nt m: tiou,.,,sts.

ECAI Conference 2000 Conference Paper

Extending TALplanner with Concurrency and Resources

• Jonas Kvarnström
• Patrick Doherty 0001
• Patrik Haslum

ICAPS Conference 2000 Conference Paper

Planning with Reduced Operator Sets

• Patrik Haslum
• Peter Jonsson

Classical propositional STRIPSplanning is nothing but the search for a path in the state-transition graph induced by the operators in the planning problem. What makes the problem hard is the size and the sometimesadverse structure of this graph. Weconjecture that the search for a plan wouldbe moreefficient if there were only a small numberof paths from the initial state to the goal state. Toverify this conjecture, we define the notion of reducedoperator sets and describe ways of finding such reduced sets. We demonstrate that somestate-of-the-art planners run faster using reduced operator sets.

AIJ Journal 2000 Journal Article

Towards efficient universal planning: A randomized approach

• Peter Jonsson
• Patrik Haslum
• Christer Bäckström