Jörg Hoffmann 0001

ECAI Conference 2025 Conference Paper

An Operator-Centric Trustable Decision-Making Tool for Planning Ground Logistic Operations of Beluga Aircraft

• Rebecca Eifler
• Nika Beriachvili
• Arthur Bit-Monnot
• Dillon Z. Chen
• Jan Eisenhut
• Jörg Hoffmann 0001
• Sylvie Thiébaux
• Florent Teichteil-Königsbuch

This paper presents the demonstrator developed in the TUPLES European Union research project for assisting human operators at Airbus to plan Beluga cargo ground logistic operations. The demonstrator features techniques providing robust, explainable, and safe decisions, which all contribute to making our decision-support system trusted by the operators. We have also worked on various planning methods to scale up to the size of the real industrial problem, including hybrid machine learning and symbolic algorithms. We demonstrate the software that was tested by Airbus operators during a user study in Finkenwerder’s production site in May 2025.

ECAI Conference 2025 Conference Paper

Is This a Good Decision? Action Optimality Checking in Classical Planning

• Jan Eisenhut
• Daniel Fiser
• Wheeler Ruml
• Jörg Hoffmann 0001

Heuristic search is a prominent method for plan generation in classical planning. Here we address its use for a new problem that we baptize action optimality checking (AOC): checking whether a given action a is optimal in a given state s. AOC has various potential uses, e. g. quality assurance for learned action policies through checking example policy decisions. A vanilla algorithm for AOC is to run two A⋆ searches, on each of s and the outcome state s′ of applying a. We show that one can do much better than this. We introduce early termination criteria across multiple searches. Beyond this, we introduce AOCA⋆, which performs a single search on s that gives preference to paths going through s′. Our experiments show that AOCA⋆ is superior to the vanilla algorithm as well as other multiple-search configurations, consistently across three different state-of-the-art heuristic functions.

ECAI Conference 2025 Conference Paper

Policy Safety Testing in Non-Deterministic Planning: Fuzzing, Test Oracles, Fault Analysis

• Chaahat Jain
• Daniel Sherbakov
• Marcel Vinzent
• Marcel Steinmetz
• Jesse Davis
• Jörg Hoffmann 0001

Recent work has introduced methodology for testing learned action policies in AI Planning, aiming to effectively identify bug states where policy behavior is sub-optimal. While this work focused on cost-optimality in classical planning, here we apply the core ideas to safety testing in planning with initial-state and action-outcome non-determinism. We cover the entire testing pipeline, introducing fuzzing algorithms to find unsafe policy runs, as well as test oracles to identify bugs where such unsafe behavior could be avoided. Going beyond the previous framework, we introduce a final step to the pipeline, identifying faults which we define to be specific policy decisions – state/action pairs – transitioning from a safe state (where a safe policy exists) to an unsafe state (where no such policy exists). We adapt a range of known algorithms for these purposes, including also approximate ones bounding the number of times we are allowed to diverge from the learned policy. We run comprehensive experiments evaluating each part of our pipeline. Key takeaways are that safety testing can be quite cheap, in contrast to cost-optimality testing; and that variants of Tarjan’s algorithm tend to be highly effective for this purpose.

ECAI Conference 2024 Conference Paper

Decision-Focused Learning to Predict Action Costs for Planning

• Jayanta Mandi
• Marco Foschini
• Daniel Höller
• Sylvie Thiébaux
• Jörg Hoffmann 0001
• Tias Guns

In many automated planning applications, action costs can be hard to specify. An example is the time needed to travel through a certain road segment, which depends on many factors, such as the current weather conditions. A natural way to address this issue is to learn to predict these parameters based on input features (e. g. , weather forecasts) and use the predicted action costs in automated planning afterward. Decision-Focused Learning (DFL) has been successful in learning to predict the parameters of combinatorial optimization problems in a way that optimizes solution quality rather than prediction quality. This approach yields better results than treating prediction and optimization as separate tasks. In this paper, we investigate for the first time the challenges of implementing DFL for automated planning in order to learn to predict the action costs. There are two main challenges to overcome: (1) planning systems are called during gradient descent learning, to solve planning problems with negative action costs, which are not supported in planning. We propose novel methods for gradient computation to avoid this issue. (2) DFL requires repeated planner calls during training, which can limit the scalability of the method. We experiment with different methods approximating the optimal plan as well as an easy-to-implement caching mechanism to speed up the learning process. As the first work that addresses DFL for automated planning, we demonstrate that the proposed gradient computation consistently yields significantly better plans than predictions aimed at minimizing prediction error; and that caching can temper the computation requirements.

ECAI Conference 2024 Conference Paper

Iterative Oversubscription Planning with Goal-Conflict Explanations: Scaling Up Through Policy-Guidance Approximation

• Rebecca Eifler
• Daniel Fiser
• Aleena Siji
• Jörg Hoffmann 0001

In oversubscription planning (OSP), not all goals can be achieved. If a global optimization objective is difficult to fix, then an iterative planning process in which users refine their objective based on sample plans is suitable. Recent work has shown that, in such a process, explanations of plan trade-offs based on goal conflicts – minimal unsolvable goal subsets (MUGS) – are useful. A fundamental limitation of this approach is scalability. Computing MUGS is feasible only in relatively small planning instances; sometimes plan generation in iterative planning also is a limiting factor as users tend to be impatient. Here we address both these limitations by restricting the space of plans considered. We assume that an action policy π for the OSP task has been learned. We restrict both plan generation and MUGS analysis to the action sequences within a given radius r around π, so that r controls the tradeoff between scalability and the degree of approximation. We instantiate this idea with two different kinds of radii around a policy. We experimentally analyze performance as a function of r, for Action Schema Network policies. The results confirm that our approach can scale up further than prior work, and results on instances small enough to compute MUGS exactly indicate that we obtain informative MUGS even with limited runtime and memory.

ICAPS Conference 2024 Conference Paper

Neural Action Policy Safety Verification: Applicablity Filtering

• Marcel Vinzent
• Jörg Hoffmann 0001

Neural networks (NN) are an increasingly important representation of action policies pi. Applicability filtering is a commonly used practice in this context, restricting the action selection in pi to only applicable actions. Policy predicate abstraction (PPA) has recently been introduced to verify safety of neural pi, through over-approximating the state space subgraph induced by pi. Thus far however, PPA does not permit applicability filtering, which is challenging due to the additional constraints that need to be taken into account. Here we overcome that limitation, through a range of algorithmic enhancements. In our experiments, our enhancements achieve several orders of magnitude speed-up over a baseline implementation, bringing PPA with applicability filtering close to the performance of PPA without such filtering.

ICAPS Conference 2024 Conference Paper

New Fuzzing Biases for Action Policy Testing

• Jan Eisenhut
• Xandra Schuler
• Daniel Fiser
• Daniel Höller
• Maria Christakis
• Jörg Hoffmann 0001

Testing was recently proposed as a method to gain trust in learned action policies in classical planning. Test cases in this setting are states generated by a fuzzing process that performs random walks from the initial state. A fuzzing bias attempts to bias these random walks towards policy bugs, that is, states where the policy performs sub-optimally. Prior work explored a simple fuzzing bias based on policy-trace cost. Here, we investigate this topic more deeply. We introduce three new fuzzing biases based on analyses of policy-trace shape, estimating whether a trace is close to looping back on itself, whether it contains detours, and whether its goal-distance surface does not smoothly decline. Our experiments with two kinds of neural action policies show that these new biases improve bug-finding capabilities in many cases.

ECAI Conference 2024 Conference Paper

Safety Verification of Tree-Ensemble Policies via Predicate Abstraction

• Chaahat Jain
• Lorenzo Cascioli
• Laurens Devos
• Marcel Vinzent
• Marcel Steinmetz
• Jesse Davis
• Jörg Hoffmann 0001

Learned action policies are gaining traction in AI, but come without safety guarantees. Recent work devised a method for safety verification of neural policies via predicate abstraction. Here we extend this approach to policies represented by tree ensembles, through replacing the underlying SMT queries with queries that can be dispatched by Veritas, a reasoning tool dedicated to tree ensembles. The query language supported by Veritas is limited, and we show how to encode richer constraints we need into additional trees and decision variables. We run experiments on benchmarks previously used to evaluate neural policy verification, and we design new benchmarks based on a logistics application at Airbus as well as on a real-world robotics domain. We find that (1) verification with Veritas vastly outperforms verification with Z3 and Gurobi; (2) tree-ensemble policies are much faster to verify than neural policies, while being competitive in policy quality; (3) our techniques are highly complementary to, and often outperform, an encoding of tree-ensemble policy verification into NUXMV.

ECAI Conference 2023 Conference Paper

A Landmark-Cut Heuristic for Lifted Optimal Planning

• Julia Wichlacz
• Daniel Höller
• Daniel Fiser
• Jörg Hoffmann 0001

Lifted planning – finding plans directly on the PDDL input model – has attracted renewed attention during the last years. This avoids the process of grounding, which can become computationally prohibitive very easily. However, the main focus of recent research in this area has been on satisficing, i. e. , (potentially) suboptimal planning. We present a novel heuristic for optimal lifted planning. Our basic idea is inspired by the LM-cut heuristic, which has been very successful in grounded optimal planning. Like LM-cut, we generate cut-based landmarks via back-chaining from the goal, generating cuts of partially grounded actions. However, exactly mimicking the ground formulation is not feasible, this includes computing the hmax heuristic several times for one computation of the LM-cut heuristic (which is already NP-hard to compute). We show that our heuristic is admissible and evaluate it in a cost optimal setting.

ICAPS Conference 2023 Conference Paper

Automatic Metamorphic Test Oracles for Action-Policy Testing

• Jan Eisenhut
• Álvaro Torralba
• Maria Christakis
• Jörg Hoffmann 0001

Testing is a promising way to gain trust in learned action policies π. Prior work on action-policy testing in AI planning formalized bugs as states t where π is sub-optimal with respect to a given testing objective. Deciding whether or not t is a bug is as hard as (optimal) planning itself. How can we design test oracles able to recognize some states t to be bugs efficiently? Recent work introduced metamorphic oracles which compare policy behavior on state pairs (s, t) where t is easier to solve; if π performs worse on t than on s, we know that t is a bug. Here, we show how to automatically design such oracles in classical planning, based on simulation relations between states. We introduce two oracle families of this kind: first, morphing query states t to obtain suitable s; second, maintaining and comparing upper bounds on h* across the states encountered during testing. Our experiments on ASNet policies show that these oracles can find bugs much more quickly than the existing alternatives, which are search-based; and that the combination of our oracles with search-based ones almost consistently dominates all other oracles.

ICAPS Conference 2023 Conference Paper

Lifted Stackelberg Planning

• Philipp Sauer
• Marcel Steinmetz
• Robert Künnemann
• Jörg Hoffmann 0001

In Stackelberg planning, a leader and a follower each choose a plan in the same planning task, the leader

ICAPS Conference 2022 Conference Paper

Debugging a Policy: Automatic Action-Policy Testing in AI Planning

• Marcel Steinmetz
• Daniel Fiser
• Hasan Ferit Eniser
• Patrick Ferber
• Timo P. Gros
• Philippe Heim
• Daniel Höller
• Xandra Schuler

Testing is a promising way to gain trust in neural action policies π. Previous work on policy testing in sequential decision making targeted environment behavior leading to failure conditions. But if the failure is unavoidable given that behavior, then π is not actually to blame. For a situation to qualify as a "bug" in π, there must be an alternative policy π' that does better. We introduce a generic policy testing framework based on that intuition. This raises the bug confirmation problem, deciding whether or not a state is a bug. We analyze the use of optimistic and pessimistic bounds for the design of test oracles approximating that problem. We contribute an implementation of our framework in classical planning, experimenting with several test oracles and with random-walk methods generating test states biased to poor policy performance and/or state novelty. We evaluate these techniques on policies π learned with ASNets. We find that they are able to effectively identify bugs in these π, and that our random-walk biases improve over uninformed baselines.

ICAPS Conference 2022 Conference Paper

Evaluating Plan-Property Dependencies: A Web-Based Platform and User Study

• Rebecca Eifler
• Martim Brandão
• Amanda Jane Coles
• Jeremy Frank
• Jörg Hoffmann 0001

The trade-offs between different desirable plan properties -- e. g. PDDL temporal plan preferences -- are often difficult to understand. Recent work addresses this by iterative planning with explanations elucidating the dependencies between such plan properties. Users can ask questions of the form ``Why does the plan not satisfy property p? '', which are answered by ``Because then we would have to forego q''. It has been shown that such dependencies can be computed reasonably efficiently. But is this form of explanation actually useful for users? We run a large crowd-worker user study (N=100 in each of 3 domains) evaluating that question. To enable such a study in the first place, we contribute a Web-based platform for iterative planning with explanations, running in standard browsers. Comparing users with vs. without access to the explanations, we find that the explanations enable users to identify better trade-offs between the plan properties, indicating an improved understanding of the planning task.

ICAPS Conference 2022 Conference Paper

Merge and Shrink Abstractions for Temporal Planning

• Martim Brandão
• Amanda Jane Coles
• Andrew Coles
• Jörg Hoffmann 0001

Temporal planning is a hard problem that requires good heuristic and memoization strategies to solve efficiently. Merge-and-shrink abstractions have been shown to serve as effective heuristics for classical planning, but they have not yet been applied to temporal planning. Currently, it is still unclear how to implement merge-and-shrink in the temporal domain and how effective the method is in this setting. In this paper we propose a method to compute merge-and-shrink abstractions for temporal planning, applicable to both partial- and total-order temporal planners. The method relies on pre-computing heuristics as formulas of temporal variables that are evaluated at search time, and it allows to use standard shrinking strategies and label reduction. Compared to state-of-the-art Relaxed Planning Graph heuristics, we show that the method leads to improvements in coverage, computation time, and number of explored nodes to solve optimal problems, as well as leading to improvements in unsolvability-proving of problems with deadlines.

ICAPS Conference 2022 Conference Paper

Neural Network Action Policy Verification via Predicate Abstraction

• Marcel Vinzent
• Marcel Steinmetz
• Jörg Hoffmann 0001

Neural networks (NN) are an increasingly important representation of action policies. Verifying that such policies are safe is potentially very hard as it compounds the state space explosion with the difficulty of analyzing even single NN decision episodes. Here we address that challenge through abstract reachability analysis. We show how to compute predicate abstractions of the policy state space subgraph induced by fixing an NN action policy. A key sub-problem here is the computation of abstract state transitions that may be taken by the policy, which as we show can be tackled by connecting to off-the-shelf SMT solvers. We devise a range of algorithmic enhancements, leveraging relaxed tests to avoid costly calls to SMT. We empirically evaluate the resulting machinery on a collection of benchmarks. The results show that our enhancements are required for practicality, and that our approach can outperform two competing approaches based on explicit enumeration and bounded-length verification.

ICAPS Conference 2022 Conference Paper

Neural Network Heuristic Functions for Classical Planning: Bootstrapping and Comparison to Other Methods

• Patrick Ferber
• Florian Geißer
• Felipe W. Trevizan
• Malte Helmert
• Jörg Hoffmann 0001

How can we train neural network (NN) heuristic functions for classical planning, using only states as the NN input? Prior work addressed this question by (a) per-instance imitation learning and/or (b) per-domain learning. The former limits the approach to instances small enough for training data generation, the latter to domains where the necessary knowledge generalizes across instances. Here we explore three methods for (a) that make training data generation scalable through bootstrapping and approximate value iteration. In particular, we introduce a new bootstrapping variant that estimates search effort instead of goal distance, which as we show converges to the perfect heuristic under idealized circumstances. We empirically compare these methods to (a) and (b), aligning three different NN heuristic function learning architectures for cross-comparison in an experiment of unprecedented breadth in this context. Key lessons are that our methods and imitation learning are highly complementary; that per-instance learning often yields stronger heuristics than per-domain learning; and the LAMA planner is still dominant but our methods outperform it in one benchmark domain.

SoCS Conference 2022 Conference Paper

Neural Network Heuristic Functions: Taking Confidence into Account

• Daniel Heller
• Patrick Ferber
• Julian Bitterwolf
• Matthias Hein 0001
• Jörg Hoffmann 0001

Neural networks (NN) are increasingly investigated in AI Planning, and are used successfully to learn heuristic functions. NNs commonly not only predict a value, but also output a confidence in this prediction. From the perspective of heuristic search with NN heuristics, it is a natural idea to take this into account, e. g. falling back to a standard heuristic where confidence is low. We contribute an empirical study of this idea. We design search methods which prune nodes, or switch between search queues, based on the confidence of NNs. We furthermore explore the possibility of out-of-distribution (OOD) training, which tries to reduce the overconfidence of NNs on inputs different to the training distribution. In experiments on IPC benchmarks, we find that our search methods improve coverage over standard methods, and that OOD training has the desired effect in terms of prediction accuracy and confidence, though its impact on search seems marginal.

ICAPS Conference 2022 Conference Paper

Operator-Potentials in Symbolic Search: From Forward to Bi-directional Search

• Daniel Fiser
• Álvaro Torralba
• Jörg Hoffmann 0001

Symbolic search using binary decision diagrams is a state-of-the-art technique for cost-optimal planning. Heuristic search in this context has been problematic as even a very informative heuristic can be detrimental in case it induces difficult-to-represent state partitionings. It was recently shown that operator-potential heuristics can address this issue in forward search by computing a numeric potential for each operator corresponding to the change of the heuristic value induced by that operator. Forward search is, however, not the best known variant of symbolic search. Here we investigate the integration with backward and bi-directional search instead. We prove that forward search (distance-to-goal) operator-potential heuristics can be turned into backward search (distance-to-initial-state) heuristics elegantly in this context, by summing the backward search path operator-potentials with the initial state goal-distance estimate. We run exhaustive experiments on IPC benchmarks, showing that significant performance improvements can be obtained over symbolic forward search and other state-of-the-art techniques.

ICAPS Conference 2022 Conference Paper

Pattern Selection Strategies for Pattern Databases in Probabilistic Planning

• Thorsten Klößner
• Marcel Steinmetz
• Álvaro Torralba
• Jörg Hoffmann 0001

Recently, pattern databases have been extended to probabilistic planning, to derive heuristics for the objectives of goal probability maximization and expected cost minimization. While this approach yields both theoretical and practical advantages over techniques relying on determinization, the problem of selecting the patterns in the first place has only been scantily addressed as yet, through a method that systematically enumerates patterns up to a fixed size. Here we close this gap, extending pattern generation techniques known from classical planning to the probabilistic case. We consider hill-climbing as well as counter-example guided abstraction refinement (CEGAR) approaches, and show how they need to be adapted to obtain desired properties such as convergence to the perfect value function in the limit. Our experiments show substantial improvements over systematic pattern generation and the previous state of the art.

SoCS Conference 2021 Conference Paper

Landmark Heuristics for Lifted Planning - Extended Abstract

• Julia Wichlacz
• Daniel Höller
• Jörg Hoffmann 0001

Planning problems are usually modeled using lifted representations, they specify predicates and action schemas using variables over a finite universe of objects. However, current planning systems like Fast Downward need a grounded (propositional) input model. The process of grounding might result in an exponential blowup of the model size. This limits the application of grounded planning systems in practical applications. Recent work introduced an efficient planning system for lifted heuristic search, but the work on lifted heuristics is still limited. In this extended abstract, we introduce a novel lifted heuristic based on landmarks, which we extract from the lifted problem representation. Preliminary results on a benchmark set specialized to lifted planning show that there are domains where our approach finds enough landmarks to guide the search more effective than the heuristics available.

ICAPS Conference 2021 Conference Paper

Pattern Databases for Goal-Probability Maximization in Probabilistic Planning

• Thorsten Klößner
• Jörg Hoffmann 0001
• Marcel Steinmetz
• Álvaro Torralba

Heuristic search algorithms for goal-probability maximization (MaxProb) have been known since a decade. Yet prior work on heuristic functions for MaxProb relies on determinization, not actually taking the probabilities into account. Here we begin to fix this, by introducing MaxProb pattern databases (PDB). We show that, for the special case of PDBs in contrast to more general abstractions, abstract transitions have a unique probability so that the abstract planning task is still an MDP. The resulting heuristic functions are admissible, i. e. , they upper-bound the real goal probability. We identify conditions allowing to admissibly multiply heuristic values across several PDBs. Our experiments show that even non-probabilistic PDB heuristics often outperform previous MaxProb heuristics, and that our new probabilistic PDBs can in turn yield significant performance gains over non-probabilistic ones.

SoCS Conference 2021 Conference Paper

Pattern Databases for Stochastic Shortest Path Problems

• Thorsten Klößner
• Jörg Hoffmann 0001

Stochastic shortest-path problems (SSP) are an important subclass of MDPs for which heuristic search algorithms exist since over a decade. Yet most known heuristic functions rely on determinization so do not actually take the transition probabilities into account. The only exceptions are Trevizan et al.

SoCS Conference 2020 Conference Paper

Applying Monte-Carlo Tree Search in HTN Planning

• Julia Wichlacz
• Daniel Höller
• Álvaro Torralba
• Jörg Hoffmann 0001

Search methods are useful in hierarchical task network (HTN) planning to make performance less dependent on the domain knowledge provided, and to minimize plan costs. Here we investigate Monte-Carlo tree search (MCTS) as a new algorithmic alternative in HTN planning. We implement combinations of MCTS with heuristic search in PANDA. We furthermore investigate MCTS in JSHOP, to address lifted (non-grounded) planning, leveraging the fact that, in contrast to other search methods, MCTS does not require a grounded task representation. Our new methods yield coverage performance on par with the state of the art, but in addition can effectively minimize plan cost over time.

ECAI Conference 2020 Conference Paper

Neural Network Heuristics for Classical Planning: A Study of Hyperparameter Space

• Patrick Ferber
• Malte Helmert
• Jörg Hoffmann 0001

Neural networks (NN) have been shown to be powerful state-value predictors in several complex games. Can similar successes be achieved in classical planning? Towards a systematic exploration of that question, we contribute a study of hyperparameter space in the most canonical setup: input = state, feed-forward NN, supervised learning, generalization only over initial state. We investigate a broad range of hyperparameters pertaining to NN design and training. We evaluate these techniques through their use as heuristic functions in Fast Downward. The results on IPC benchmarks show that highly competitive heuristics can be learned, yielding substantially smaller search spaces than standard techniques on some domains. But the heuristic functions are costly to evaluate, and the range of domains where useful heuristics are learned is limited. Our study provides the basis for further research improving on current weaknesses.

ICAPS Conference 2019 Conference Paper

Advanced Factoring Strategies for Decoupled Search Using Linear Programming

• Frederik Schmitt
• Daniel Gnad 0001
• Jörg Hoffmann 0001

Star-topology decoupled state space search decomposes a planning task and searches over the component state spaces instead of multiplying the state variables. This can lead to an exponential reduction of the search effort. To do so, in a preprocess before the search, the given planning task is partitioned into factors, such that the interaction between these factors takes the form of a star topology. Prior work has identified several ways to automatically decompose planning tasks, however, was not able to release the full potential of decoupled search. We try to close this gap by introducing an integer linear programming formulation of the factoring process, allowing us to explicitly specify the properties that a factoring should have. We prove that our approach returns the factoring that maximizes the number of factors, if this is the objective, and employ two other properties to assess the quality of a factoring. Our experimental evaluation shows that this leads to superior performance and substantially increases the applicability of decoupled search.

ICAPS Conference 2019 Conference Paper

On the Relation between Star-Topology Decoupling and Petri Net Unfolding

• Daniel Gnad 0001
• Jörg Hoffmann 0001

Petri net unfolding expands concurrent sub-threads of a transition system separately. In AI Planning, star-topology decoupling (STD) finds a partitioning of state variables into components whose dependencies take a star shape, and expands leafcomponent state spaces separately. Thus both techniques rely on the separate expansion of state-space composites. How do they relate? We show that, provided compatible search orderings, STD state space size dominates that of unfolding if every component contains a single state variable, and unfolding dominates STD in the absence of prevail conditions (nondeleted action preconditions). In all other cases, exponential state space size advantages are possible on either side. Thus the sources of exponential advantages of STD are exactly a) state space size in the presence of prevail conditions (our results), and b) decidability of reachability in time linear in state space size vs. NP-hard for unfolding (known results).

ICAPS Conference 2018 Conference Paper

Compiling Probabilistic Model Checking into Probabilistic Planning

• Michaela Klauck
• Marcel Steinmetz
• Jörg Hoffmann 0001
• Holger Hermanns

It has previously been observed that the verification of safety properties in deterministic model-checking frameworks can be compiled into classical planning. A similar connection exists between goal probability analysis on either side, yet that connection has not been explored. We fill that gap with a translation from Jani, an input language for quantitative model checkers including the Modest toolset and PRISM, into PPDDL. Our experiments motivate further cross-fertilization between both research areas, specifically the exchange of algorithms. Our study also initiates the creation of new benchmarks for goal probability analysis.

ICAPS Conference 2018 Conference Paper

On Stubborn Sets and Planning with Resources

• Anna Wilhelm
• Marcel Steinmetz
• Jörg Hoffmann 0001

Stubborn sets are a well-established technique to admissibly prune permutable parts of forward search in classical planning. But what about planning with resources? The identification of effective stubborn sets relies on non-interfering actions. Yet, a priori, all actions affecting the same resource interfere. We show how to exploit the fact that, nevertheless, with commutativity of addition and subtraction, many resource-affecting action sequences are permutable. We design suitable notions of stubborn sets for planning with resources, with and without resource production. We show empirically, on classical IPC benchmarks with discrete resource variables, that our new pruning methods are often, and sometimes dramatically, superior to previous ones. Together with a novel way of automatically identifying the resource variables, this result holds under IPC conditions.

ICAPS Conference 2018 Conference Paper

Simulated Penetration Testing as Contingent Planning

• Dorin Shmaryahu
• Guy Shani
• Jörg Hoffmann 0001
• Marcel Steinmetz

In penetration testing (pentesting), network administrators attack their own network to identify and fix vulnerabilities. Planning-based simulated pentesting can achieve much higher testing coverage than manual pentesting. A key challenge is for the attack planning to imitate human hackers as faithfully as possible. POMDP models have been proposed to this end, yet they are computationally very hard, and it is unclear how to acquire the models in practice. At the other extreme, classical planning models are scalable and simple to obtain, yet completely ignore the incomplete knowledge characteristic of hacking. We propose contingent planning as a new middle ground, feasible in both computation burden and model acquisition effort while allowing for a representation of incomplete knowledge. We design the model, show how to adapt available solvers, and show how to acquire the model from real network scans in practice. We experiment on real networks and show that our approach scales to practical input sizes.

ICAPS Conference 2017 Conference Paper

Beyond Red-Black Planning: Limited-Memory State Variables

• Patrick Speicher
• Marcel Steinmetz
• Daniel Gnad 0001
• Jörg Hoffmann 0001
• Alfonso Emilio Gerevini

Red-black planning delete-relaxes only some of the state variables. This is coarse-grained in that, for each variable, it either remembers all past values (red), or remembers only the most recent one (black). We herein introduce limited-memory state variables, that remember a subset of their most recent values. It turns out that planning is still PSPACE-complete even when the memory is large enough to store all but a single value. Nevertheless, limited memory can be used to substantially broaden a known tractable fragment of red-black planning, yielding better heuristic functions in some domains.

ICAPS Conference 2017 Conference Paper

Complete Local Search: Boosting Hill-Climbing through Online Relaxation Refinement

• Maximilian Fickert
• Jörg Hoffmann 0001

Several known heuristic functions can capture the input at different levels of precision, and support relaxation-refinement operations guaranteeing to converge to exact information in a finite number of steps. A natural idea is to use such refinement online, during search, yet this has barely been addressed. We do so here for local search, where relaxation refinement is particularly appealing: escape local minima not by search, but by removing them from the search surface. Thanks to convergence, such an escape is always possible. We design a family of hill-climbing algorithms along these lines. We show that these are complete, even when using helpful actions pruning. Using them with the partial delete relaxation heuristic hCFF, the best-performing variant outclasses FF's enforced hill-climbing, outperforms FF, outperforms dual-queue greedy best-first search with hFF, and in 6 IPC domains outperforms both LAMA and Mercury.

ICAPS Conference 2017 Conference Paper

Critical-Path Dead-End Detection versus NoGoods: Offline Equivalence and Online Learning

• Marcel Steinmetz
• Jörg Hoffmann 0001

One traditional use of critical-path heuristic functions is as effective sufficient criteria for unsolvability. To employ this for dead-end detection, the heuristic function must be evaluated on every new state to be tested, incurring a substantial runtime overhead. We show herein that the exact same dead-end detector can be captured through a nogood, a formula phiOFF computed once prior to search. This is mostly of theoretical interest, as phiOFF is large. We obtain practical variants by instead incrementally generating a stronger nogood psi, that implies phiOFF, online during search, generalizing from already tested states to avoid future heuristic-function evaluations.

SoCS Conference 2017 Conference Paper

Ranking Conjunctions for Partial Delete Relaxation Heuristics in Planning

• Maximilian Fickert
• Jörg Hoffmann 0001

Heuristic search is one of the most successful approaches to classical planning, finding solution paths in large state spaces. A major focus has been the development of domain-independent heuristic functions. One recent method are partial delete relaxation heuristics, improving over the standard delete relaxation heuristic through imposing a set C of conjunctions to be treated as atomic. Practical methods for selecting C are based on counter-example guided abstraction refinement, where iteratively a relaxed plan is checked for conflicts and new atomic conjunctions are introduced to address these. However, in each refinement step, the choice of possible new conjunctions is huge. The literature so far offers merely one simple strategy to make that choice. Here we fill that gap, considering a sizable space of basic ranking strategies as well as combinations thereof. We furthermore devise ranking strategies for conjunction-forgetting, where the ranking pertains to the current conjunctions and thus statistics over their usefulness can be maintained. Our experiments show that ranking strategies do make a large difference in performance, and that our new strategies can be useful.

SoCS Conference 2017 Conference Paper

Symbolic Leaf Representation in Decoupled Search

• Daniel Gnad 0001
• Álvaro Torralba
• Jörg Hoffmann 0001

Star-Topology Decoupled Search has recently been introduced in classical planning. It splits the planning task into a set of components whose dependencies take a star structure, where one center component interacts with possibly many leaf components. Here we address a weakness of decoupled search, namely large leaf components, whose state space is enumerated explicitly. We propose a symbolic representation of the leaf state spaces via decision diagrams, which can be dramatically smaller, and also more runtime efficient. We further introduce a symbolic version of the LM-cut heuristic, that nicely connects to our new leaf representation. We show empirically that the symbolic representation indeed pays off when the leaf components are large.

ICAPS Conference 2017 Conference Paper

Symmetry Breaking in Star-Topology Decoupled Search

• Daniel Gnad 0001
• Álvaro Torralba
• Alexander Shleyfman
• Jörg Hoffmann 0001

Symmetry breaking is a well-known method for search reduction. It identifies state-space symmetries prior to search, and prunes symmetric states during search. A recent proposal, star-topology decoupled search, is to search not in the state space, but in a factored version thereof, which avoids the multiplication of states across leaf components in an underlying star-topology structure. We show that, despite the much more complex structure of search states -- so-called decoupled states -- symmetry breaking can be brought to bear in this framework as well. Starting from the notion of structural symmetries over states, we identify a sub-class of such symmetries suitable for star-topology decoupled search, and we show how symmetries from that sub-class induce symmetry relations over decoupled states. We accordingly extend the routines required for search pruning and solution reconstruction. The resulting combined method can be exponentially better than both its components in theory, and this synergetic advantage is also manifested in practice: empirically, our method reliably inherits the best of its base components, and often outperforms them both.

SoCS Conference 2016 Conference Paper

Partial Delete Relaxation, Unchained: On Intractable Red-Black Planning and Its Applications

• Daniel Gnad 0001
• Marcel Steinmetz
• Mathäus Jany
• Jörg Hoffmann 0001
• Ivan Serina
• Alfonso Emilio Gerevini

Partial delete relaxation methods, like red-black planning, are extremely powerful, allowing in principle to force relaxed plans to behave like real plans in the limit. Alas, that power has so far been chained down by the computational overhead of the use as heuristic functions, necessitating to compute a relaxed plan on every search state. For red-black planning in particular, this has entailed an exclusive focus on tractable fragments. We herein unleash the power of red-black planning on two applications not necessitating such a restriction: (i) generating seed plans for plan repair, and (ii) proving planning task unsolvability. We introduce a method allowing to generate red-black plans for arbitrary inputs — intractable red-black planning — and we evaluate its use for (i) and (ii). With (i), our results show promise and outperform standard baselines in several domains. With (ii), we obtain substantial, in some domains dramatic, improvements over the state of the art.

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.

ICAPS Conference 2016 Conference Paper

Revisiting Goal Probability Analysis in Probabilistic Planning

• Marcel Steinmetz
• Jörg Hoffmann 0001
• Olivier Buffet

Maximizing goal probability is an important objective in probabilistic planning, yet algorithms for its optimal solution are severely underexplored. There is scant evidence of what the empirical state of the art actually is. Focusing on heuristic search, we close this gap with a comprehensive empirical analysis of known and adapted algorithms. We explore both, the general case where there may be 0-reward cycles, and the practically relevant special case of acyclic planning, like planning with a limited action-cost budget. We consider three different algorithmic objectives. We design suitable termination criteria, search algorithm variants, dead-end pruning methods using classical planning heuristics, and node selection strategies. Our evaluation on more than 1000 benchmark instances from the IPPC, resource-constrained planning, and simulated penetration testing reveals the behavior of heuristic search, and exhibits several improvements to the state of the art.

ICAPS Conference 2015 Conference Paper

Beating LM-Cut with h max (Sometimes): Fork-Decoupled State Space Search

• Daniel Gnad 0001
• Jörg Hoffmann 0001

Factored planning decouples planning tasks into subsets (factors) of state variables. The traditional focus is on handling complex cross-factor interactions. Departing from this, we introduce a form of target-profile factoring, forcing the cross-factor interactions to take the form of a fork, with several leaf factors and one potentially very large root factor. We show that forward state space search gracefully extends to such structure, by augmenting regular search on the root factor with maintenance of the cheapest compliant paths within each leaf factor. We analyze how to guarantee optimality. Connecting to standard heuristics, the performance improvements relative to A* are substantial, and sometimes dramatic: In four IPC benchmark domains, fork-decoupled state space search outperforms standard state space search even when using h^max in the former vs. LM-cut in the latter.

ICAPS Conference 2015 Conference Paper

Explicit Conjunctions without Compilation: Computing h FF (Pi C ) in Polynomial Time

• Jörg Hoffmann 0001
• Maximilian Fickert

A successful partial delete relaxation method is to compute hFF in a compiled planning task PiC which represents a set C of conjunctions explicitly. While this compilation view of such partial delete relaxation is simple and elegant, its meaning with respect to the original planning task is opaque. We provide a direct characterization of h+(PiC), without compilation, making explicit how it arises from a "marriage" of the critical-path heuristic hm with (a somewhat novel view of) h+. This explicit view allows us to derive a direct characterization of hFF(PiC), which in turn allows us to compute a version of that heuristic function in time polynomial in |C|.

SoCS Conference 2015 Conference Paper

From Fork Decoupling to Star-Topology Decoupling

• Daniel Gnad 0001
• Jörg Hoffmann 0001
• Carmel Domshlak

Fork decoupling is a recent approach to exploiting problem structure in state space search. The problem is assumed to take the form of a fork, where a single (large) center component provides preconditions for several (small) leaf components. The leaves are then conditionally independent in the sense that, given a fixed center path p, the compliant leaf moves - those leaf moves enabled by the preconditions supplied along p - can be scheduled independently for each leaf. Fork-decoupled state space search exploits this through conducting a regular search over center paths, augmented with maintenance of the compliant paths for each leaf individually. We herein show that the same ideas apply to much more general star-topology structures, where leaves may supply preconditions for the center, and actions may affect several leaves simultaneously as long as they also affect the center. Our empirical evaluation in planning, super-imposing star topologies by automatically grouping the state variables into suitable components, shows the merits of the approach.

ICAPS Conference 2015 Conference Paper

Journal Track Paper Abstracts

• Jörg Hoffmann 0001
• Alan Fern

This edited compilation contains abstracts of the journal paper summaries presented at the 25th ICAPs conference Journal Paper Track. Papers include Simple Regret Optimization in Online Planning for Markov Decision Processes, by Zohar Feldman and Carmel Domshlak; Energy Efficient Execution of POMDP Policies by Marek Grzes, Pascal Poupart, Xiao Yang, and Jesse Hoey; Envisioning the Qualitative Effects of Robot Manipulation Actions Using Simulation-Based Projections by Lars Kunze and Michael Beetz; and Distributed Heuristic Forward Search for Multi-Agent Planning by Raz Nissim and Ronen Brafman.

SoCS Conference 2015 Conference Paper

Red-Black Planning: A New Tractability Analysis and Heuristic Function

• Daniel Gnad 0001
• Jörg Hoffmann 0001

Red-black planning is a recent approach to partial delete relaxation, where red variables take the relaxed semantics (accumulating their values), while black variables take the regular semantics. Practical heuristic functions can be generated from tractable sub-classes of red-black planning. Prior work has identified such sub-classes based on the black causal graph, i. e. , the projection of the causal graph onto the black variables. Here, we consider cross-dependencies between black and red variables instead. We show that, if no red variable relies on black preconditions, then red-black plan generation is tractable in the size of the black state space, i. e. , the product of the black variables. We employ this insight to devise a new red-black plan heuristic in which variables are painted black starting from the causal graph leaves. We evaluate this heuristic on the planning competition benchmarks. Compared to a standard delete relaxation heuristic, while the increased runtime overhead often is detrimental, in some cases the search space reduction is strong enough to result in improved performance overall.

ICAPS Conference 2015 Invited Paper

Simulated Penetration Testing: From "Dijkstra" to "Turing Test++"

• Jörg Hoffmann 0001

Penetration testing (pentesting) is a well established method for identifying security weaknesses, by conducting friendly attacks. Simulated pentesting automates this process, through designing a model of the system at hand, and using model-based attack planning to generate the attacks. Classical planning variants of this idea are being used commercially by the pentesting industry since 2010. Such models can pinpoint potentially dangerous combinations of known vulnerabilities, but ignore the incomplete knowledge characteristic of hacking from the attacker's point of view. Yet, ideally, the simulation should conduct its attacks the same way a real attacker would. Hence the ultimate goal is much more ambitious: to realistically simulate a human hacker. This is a grand vision indeed; e. g. , the classical Turing Test can be viewed as a sub-problem. Taking a more practical perspective, the simulated pentesting model space spans a broad range of sequential decision making problems. Analyzing prior work in AI and other relevant areas, we derive a systematization of this model space, highlighting a multitude of interesting challenges to AI sequential decision making research.

ECAI Conference 2014 Conference Paper

"Distance"? Who Cares? Tailoring Merge-and-Shrink Heuristics to Detect Unsolvability

• Jörg Hoffmann 0001
• Peter Kissmann
• Álvaro Torralba

Research on heuristic functions is all about estimating the length (or cost) of solution paths. But what if there is no such path? Many known heuristics have the ability to detect (some) unsolvable states, but that ability has always been treated as a by-product. No attempt has been made to design heuristics specifically for that purpose, where there is no need to preserve distances. As a case study towards leveraging that advantage, we investigate merge-and-shrink abstractions in classical planning. We identify safe abstraction steps (no information loss regarding solvability) that would not be safe for traditional heuristics. We design practical algorithm configurations, and run extensive experiments showing that our heuristics outperform the state of the art for proving planning tasks unsolvable.

ICAPS Conference 2014 Conference Paper

Improved Features for Runtime Prediction of Domain-Independent Planners

• Chris Fawcett
• Mauro Vallati
• Frank Hutter
• Jörg Hoffmann 0001
• Holger H. Hoos
• Kevin Leyton-Brown

State-of-the-art planners often exhibit substantial runtime variation, making it useful to be able to efficiently predict how long a given planner will take to run on a given instance. In other areas of AI, such needs are met by building so-called empirical performance models (EPMs), statistical models derived from sets of problem instances and performance observations. Historically, such models have been less accurate for predicting the running times of planners. A key hurdle has been a relative weakness in instance features for characterizing instances: mappings from problem instances to real numbers that serve as the starting point for learning an EPM. We propose a new, extensive set of instance features for planning, and investigate its effectiveness across a range of model families. We built EPMs for various prominent planning systems on several thousand benchmark problems from the planning literature and from IPC benchmark sets, and conclude that our models predict runtime much more accurately than the previous state of the art. We also study the relative importance of these features.

ECAI Conference 2014 Conference Paper

Learning Pruning Rules for Heuristic Search Planning

• Michal Krajnanský
• Jörg Hoffmann 0001
• Olivier Buffet
• Alan Fern

When it comes to learning control knowledge for planning, most works focus on "how to do it" knowledge which is then used to make decisions regarding which actions should be applied in which state. We pursue the opposite approach of learning "how to not do it" knowledge, used to make decisions regarding which actions should not be applied in which state. Our intuition is that "bad actions" are often easier to characterize than "good" ones. An obvious application, which has not been considered by the few prior works on learning bad actions, is to use such learned knowledge as action pruning rules in heuristic search planning. Fixing a canonical rule language and an off-the-shelf learning tool, we explore a novel method for generating training data, and implement rule evaluators in state-of-the-art planners. The experiments show that the learned rules can yield dramatic savings, even when the native pruning rules of these planners, i. e. , preferred operators, are already switched on.

ICAPS Conference 2014 Conference Paper

Optimizing Planning Domains by Automatic Action Schema Splitting

• Carlos Areces
• Facundo Bustos
• Martín Ariel Domínguez
• Jörg Hoffmann 0001

As modeling details can have a large impact on planner perormance, domain transformation has been a traditional subject of interest in the planning community not only betweenlanguages, but also within languages. Herein, we automatean intra-language transformation method that has as yet beenapplied only manually, and that has never been formally described: action schema splitting, which transforms an actionschema with a big interface (many parameters) into severalschemas with smaller interfaces, exponentially reducing thenumber of ground actions. We spell out this method, characterizing exactly the choice of splits preserving equivalence tothe original schema. Making that choice involves a trade-off between interface size and plan length, which we explore bydesigning automatic domain optimization methods. Our experiments show that these methods can substantially improveperformance on domains with large interfaces.

SoCS Conference 2013 Conference Paper

Red-Black Relaxed Plan Heuristics Reloaded

• Michael Katz 0001
• Jörg Hoffmann 0001

Despite its success, the delete relaxation has significant pitfalls. In an attempt to overcome these pitfalls, recent work has devised so-called red-black relaxed plan heuristics, where red variables take the relaxed semantics (accumulating their values), while black variables take the regular semantics. These heuristics were shown to significantly improve over standard delete relaxation heuristics. However, the experiments also brought to light a major weakness: Being based on repairing fully delete-relaxed plans, the returned estimates depend on arbitrary choices made in such plans. This can lead to huge over-estimation in arbitrary subsets of states. Here we devise a new red-black planning method not based on repairing relaxed plans, getting rid of much of this variance. Our experiments show a significant improvement over previous red-black relaxed plan heuristics, and other related methods.

ICAPS Conference 2013 Conference Paper

What's in It for My BDD? On Causal Graphs and Variable Orders in Planning

• Peter Kissmann
• Jörg Hoffmann 0001

One decisive factor for the success of symbolic search using BDDs is whether or not the variable ordering is good. A general intuition is that smaller BDDs result if inter-dependent variables are close together. The most common means to capture variable dependencies in planning are causal graphs, and consequently previous work defined variable orders based on these. Starting from the observation that the two concepts of “dependency” are actually quite different, we introduce a framework for assessing the strength of variable ordering heuristics in sub-classes of planning. It turns out that causal graph based variable orders may be exponentially worse than optimal even for very simple planning tasks. Experiments with a broad range of such variable ordering variants indicate that they are mediocre at best.

ICAPS Conference 2013 Conference Paper

Who Said We Need to Relax All Variables?

• Michael Katz 0001
• Jörg Hoffmann 0001
• Carmel Domshlak

Despite its success in both satisficing and optimal planning, thedelete relaxation has significant pitfalls in many important classesof planning domains, and it has been a challenge from the outset todevise heuristics that take some deletes into account. Weherein devise an elegant and simple method for doing just that. In thecontext of finite-domain state variables, we define red variables to take the relaxed semantics, in which they accumulate their values rather than switching between them, as opposed to black variables that take the regular semantics. Red-black planning then interpolates between relaxed planning and regular planning simply by allowing a subset of variables to be painted red. Of course, this relaxation is useful as a basis for devising heuristic functions only if the resulting red-black planning task is polynomial-time solvable. We herein investigate the tractability region of red-black planning, extending Chen and Gimenez' characterization theorems for regular planning to the more generalred-black setting. In particular, we identify significant islands of tractable red-black planning, opening the road to the efficient computation of very powerful heuristics.

ICAPS Conference 2012 Conference Paper

How to Relax a Bisimulation?

• Michael Katz 0001
• Jörg Hoffmann 0001
• Malte Helmert

Merge-and-shrink abstraction (M&S) is an approach for constructing admissible heuristic functions for cost-optimal planning. It enables the targeted design of abstractions, by allowing to choose individual pairs of (abstract) states to aggregate into one. A key question is how to actually make these choices, so as to obtain an informed heuristic at reasonable computational cost. Recent work has addressed this via the well-known notion of bisimulation. When aggregating only bisimilar states -- essentially, states whose behavior is identical under every planning operator -- M&S yields a perfect heuristic. However, bisimulations are typically exponentially large. Thus we must relax the bisimulation criterion, so that it applies to more state pairs, and yields smaller abstractions. We herein devise a fine-grained method for doing so. We restrict the bisimulation criterion to consider only a subset K of the planning operators. We show that, if K is chosen appropriately, then M&S still yields a perfect heuristic, while abstraction size may decrease exponentially. Designing practical approximations for K, we obtain M&S heuristics that are competitive with the state of the art.

ICAPS Conference 2012 Conference Paper

Resource-Constrained Planning: A Monte Carlo Random Walk Approach

• Hootan Nakhost
• Jörg Hoffmann 0001
• Martin Müller 0003

The need to economize limited resources, such as fuel or money, is aubiquitous feature of planning problems. If the resources cannot bereplenished, the planner must make do with the initial supply. It isthen of paramount importance how constrained the problem is, i. e. , whether and to which extent the initial resource supply exceedsthe minimum need. While there is a large body of literature on numericplanning and planning with resources, such resource constrainednesshas only been scantily investigated. We herein start to address thisin more detail. We generalize the previous notion of resourceconstrainedness, characterized through a numeric problem feature C≥ 1, to the case of multiple resources. We implement an extendedbenchmark suite controlling C. We conduct a large-scale study of thecurrent state of the art as a function of C, highlighting whichtechniques contribute to success. We introduce two new techniques ontop of a recent Monte Carlo Random Walk method, resulting in a plannerthat, in these benchmarks, outperforms previous planners whenresources are scarce (C close to 1). We investigate the parametersinfluencing the performance of that planner, and we show that one ofthe two new techniques works well also on the regular IPC benchmarks.

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.

ICAPS Conference 2011 Conference Paper

Where Ignoring Delete Lists Works, Part II: Causal Graphs

• Jörg Hoffmann 0001

The ignoring delete lists relaxation is of paramount importance for both satisficing and optimal planning. In earlier work (Hoffmann 2005), it was observed that the optimal relaxation heuristic h+ has amazing qualities in many classical planning benchmarks, in particular pertaining to the complete absence of local minima. The proofs of this are hand-made, raising the question whether such proofs can be lead automatically by domain analysis techniques. In contrast to earlier disappointing results (Hoffmann 2005) - the analysis method has exponential runtime and succeeds only in two extremely simple benchmark domains - we herein answer this question in the affirmative. We establish connections between causal graph structure and h+ topology. This results in low-order polynomial time analysis methods, implemented in a tool we call TorchLight. Of the 12 domains where the absence of local minima has been proved, TorchLight gives strong success guarantees in 8 domains. Empirically, its analysis exhibits strong performance in a further 2 of these domains, plus in 4 more domains where local minima may exist but are rare. In this way, TorchLight can distinguish ``easy'' domains from "hard" ones. By summarizing structural reasons for analysis failure, TorchLight also provides diagnostic output indicating domain aspects that may cause local minima.

ECAI Conference 2010 Conference Paper

Brothers in Arms? On AI Planning and Cellular Automata

• Jörg Hoffmann 0001
• Nazim Fatès
• Héctor Palacios

AI Planning is concerned with the selection of actions towards achieving a goal. Research on cellular automata (CA) is concerned with the question how global behaviours arise from local updating rules relating a cell to its direct neighbours. While these two areas are disparate at first glance, we herein identify a problem that is interesting to both: How to reach a fixed point in an asynchronous CA where cells are updated one-by-one? Considering a particular local updating rule, we encode this problem into PDDL and show that the resulting benchmark is an interesting challenge for AI Planning. For example, our experiments determine that, very atypically, an optimal SAT-based planner outperforms state-of-the-art satisficing heuristic search planners. This points to a severe weakness of current heuristics because, as we prove herein, plans for this problem can always be constructed in time linear in the size of the automaton. Our proof of this starts from a high-level argument and then relies on using a planner for flexible case enumeration within localised parts of the ar gument. Besides the formal result itself, this establishes a new proof technique for CAs and thus demonstrates that the potential benefit of research crossing the two fields is mutual.

SoCS Conference 2010 Conference Paper

Improving Local Search for Resource-Constrained Planning

• Hootan Nakhost
• Jörg Hoffmann 0001
• Martin Müller 0003

A ubiquitous feature of planning problems - problems involving the automatic generation of action sequences for attaining a given goal - is the need to economize limited resources such as fuel or money. While heuristic search, mostly based on standard algorithms such as A*, is currently the superior method for most varieties of planning, its ability to solve critically resource-constrained problems is limited: current planning heuristics are bad at dealing with this kind of structure. To address this, one can try to devise better heuristics. An alternative approach is to change the nature of the search instead. Local search has received some attention in planning, but not with a specific focus on how to deal with limited resources. We herein begin to fill this gap. We highlight the limitations of previous methods, and we devise a new improvement (smart restarts) to the local search method of a previously proposed planner (Arvand). Systematic experiments show how performance depends on problem structure and search parameters. In particular, we show that our new method can outperform previous planners by a large margin.

ICAPS Conference 2010 Conference Paper

Waking Up a Sleeping Rabbit: On Natural-Language Sentence Generation with FF

• Alexander Koller
• Jörg Hoffmann 0001

We present a planning domain that encodes the problem of generating natural language sentences. This domain has a number of features that provoke fairly unusual behavior in planners. In particular, hitherto no existing automated planner was sufficiently effective to be of practical value in this application. We analyze in detail the reasons for ineffectiveness in FF, resulting in a few minor implementation fixes in FF's preprocessor, and in a basic reconfiguration of its search options. The performance of the modified FF is up to several orders of magnitude better than that of the original FF, and for the first time makes automated planners a practical possibility for this application. Beside thus highlighting the importance of preprocessing and automated configuration techniques, we show that the domain still poses several interesting challenges to the development of search heuristics.

ICAPS Conference 2009 Conference Paper

Enhancing the Context-Enhanced Additive Heuristic with Precedence Constraints

• Dunbo Cai
• Jörg Hoffmann 0001
• Malte Helmert

Recently, Helmert and Geffner proposed the context-enhanced additive heuristic, where fact costs are evaluated relative to context states that arise from achieving first a pivot condition of each operator. As Helmert and Geffner pointed out, the method can be generalized to consider contexts arising from arbitrary precedence constraints over operator conditions instead. Herein, we provide such a generalization. We extend Helmert and Geffner's equations, and discuss a number of design choices that arise. Drawing on previous work on goal orderings, we design a family of methods for automatically generating precedence constraints. We run large-scale experiments, showing that the technique can help significantly, depending on the choice of precedence constraints. We shed some light on this by profiling the behavior of all possible precedence constraints, using a sampling technique.

ECAI Conference 2008 Conference Paper

Towards Efficient Belief Update for Planning-Based Web Service Composition

• Jörg Hoffmann 0001

At the "functional level", Semantic Web Services (SWS) are described akin to planning operators, with preconditions and effects relative to an ontology; the ontology provides the formal vocabulary and an axiomatisation of the underlying domain. Composing such SWS is similar to planning. A key obstacle in doing so effectively is handling the ontology axioms, which act as state constraints. Computing the outcome of an action involves the frame and ramification problems, and corresponds to belief update. The complexity of such updates motivates the search for tractable classes. Herein we investigate a class that is of practical relevance because it deals with many commonly used ontology axioms, in particular with attribute cardinality upper bounds which are not handled by other known tractable classes. We present an update computation that is exponential only in a comparatively uncritical parameter; we present an approximate update which is polynomial in that parameter as well.

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.

SAT Conference 2007 Conference Paper

Short XORs for Model Counting: From Theory to Practice

• Carla P. Gomes
• Jörg Hoffmann 0001
• Ashish Sabharwal
• Bart Selman

Abstract A promising approach for model counting was recently introduced, which in theory requires the use of large random xor or parity constraints to obtain near-exact counts of solutions to Boolean formulas. In practice, however, short xor constraints are preferred as they allow better constraint propagation in SAT solvers. We narrow this gap between theory and practice by presenting experimental evidence that for structured problem domains, very short xor constraints can lead to probabilistic variance as low as large xor constraints, and thus provide the same correctness guarantees. We initiate an understanding of this phenomenon by relating it to structural properties of synthetic instances.

ICAPS Conference 2006 Conference Paper

Fast Probabilistic Planning through Weighted Model Counting

• Carmel Domshlak
• Jörg Hoffmann 0001

We present a new algorithm for probabilistic planning with no observability. Our algorithm, called Probabilistic-FF, extends the heuristic forward-search machinery of Conformant-FF to problems with probabilistic uncertainty about both the initial state and action effects. Specifically, Probabilistic-FF combines Conformant-FF's techniques with a powerful machinery for weighted model counting in (weighted) CNFs, serving to elegantly define both the search space and the heuristic function. Our evaluation of Probabilistic-FF on several probabilistic domains shows an unprecedented, several orders of magnitude improvement over previous results in this area.

ICAPS Conference 2006 Conference Paper

Friends or Foes? An AI Planning Perspective on Abstraction and Search

• Jörg Hoffmann 0001
• Ashish Sabharwal
• Carmel Domshlak

There is increasing awareness that planning and model checking are closely related fields. Abstraction means to perform search in an over-approximation of the original problem instance, with a potentially much smaller state space. This is the most essential method in model checking. One would expect that it can also be made successful in planning. We show, however, that this is likely to not be the case. The main reason is that, while in model checking one traditionally uses blind search to exhaust the state space and prove the absence of solutions, in planning informed search is used to find solutions. We give an exhaustive theoretical and practical account of the use of abstraction in planning. For all abstraction (over-approximation) methods known in planning, we prove that they cannot improve the best-case behavior of informed search. While this is easy to see for heuristic search, we were quite surprised to find that it also holds, in most cases, for the resolution-style proofs of unsolvability underlying SAT-based optimal planners. This result is potentially relevant also for model checking, where SAT-based techniques have recently been combined with abstraction. Exploring the issue in planning practice, we find that even hand-made abstractions do not tend to improve the performance of planners, unless the attacked task contains huge amounts of irrelevance. We relate these findings to the kinds of application domains that are typically addressed in model checking.

ICAPS Conference 2006 Conference Paper

Structure and Problem Hardness: Goal Asymmetry and DPLL Proofs in SAT-Based Planning

• Jörg Hoffmann 0001
• Carla P. Gomes
• Bart Selman

In AI Planning, as well as Verification, a successful method is to compile the application into boolean satisfiability (SAT), and solve it with state-of-the-art DPLL-based procedures. There is a lack of formal understanding why this works so well. Focussing on the Planning context, we identify a form of problem structure concerned with the symmetrical or asymmetrical nature of the cost of achieving the individual planning goals. We quantify this sort of structure with a simple numeric parameter called AsymRatio, ranging between 0 and 1. We show empirically that AsymRatio correlates strongly with SAT solver performance in a broad range of Planning benchmarks, including the domains used in the 3rd International Planning Competition. We then examine carefully crafted synthetic planning domains that allow to control the amount of structure, and that are clean enough for a rigorous analysis of the combinatorial search space. The domains are parameterized by size n, and by a structure parameter k, so that AsymRatio is asymptotic to k/n. The CNFs we examine are unsatisfiable, encoding one planning step less than the length of the optimal plan. We prove upper and lower bounds on the size of the best possible DPLL refutations, under different settings of k, as a function of n. We also identify the best possible sets of branching variables (backdoors). With minimum AsymRatio, we prove exponential lower bounds, and identify minimal backdoors of size linear in the number of variables. With maximum AsymRatio, we identify logarithmic DPLL refutations (and backdoors), showing a doubly exponential gap between the two structural extreme cases. This provides a concrete insight into the practical efficiency of modern SAT solvers.

ICAPS Conference 2005 Conference Paper

Contingent Planning via Heuristic Forward Search witn Implicit Belief States

• Jörg Hoffmann 0001
• Ronen I. Brafman

Contingent planning is the task of generating a conditional plan given uncertainty about the initial state and action effects, but with the ability to observe some aspects of the current world state. Contingent planning can be transformed into an And-Or search problem in belief space, the space whose elements are sets of possible worlds. In Brafman and Hoffmann (2004), we introduced a method for implicitly representing a belief state using a propositional formula that describes the sequence of actions leading to that state. This representation trades off space for time and was shown to be quite effective for conformant planning within a heuristic forward-search planner based on the FF system. In this paper we apply the same architecture to contingent planning. The changes required to adapt the search space representation are small. More effort is required to adapt the relaxed planning problems whose solution informs the forward search algorithm. We propose the targeted use of an additional relaxation, mapping the relaxed contingent problem into a relaxed conformant problem. Experimental results show that the resulting planning system, Contingent-FF, is highly competitive with the state-of-the-art contingent planners POND and MBP.

ICAPS Conference 2004 Conference Paper

Conformant Planning via Heuristic Forward Search: A New Approach

• Ronen I. Brafman
• Jörg Hoffmann 0001

Conformant planning is the task of generating plans given uncertainty about the initial state and action effects, and without any sensing capabilities during plan execution. The plan should be successful regardless of which particular initial world we start from. It is well known that conformant planning can be transformed into a search problem in belief space, the space whose elements are sets of possible worlds. We introduce a new representation of that search space, replacing the need to store sets of possible worlds with a need to reason about the effects of action sequences. The reasoning is done by deciding solvability of CNFs that capture the action sequence’s semantics. Based on this approach, we extend the classical heuristic planning system FF to the conformant setting. The key to this extension is the introduction of approximative CNF reasoning in FF’s heuristic function. Our experimental evaluation shows Conformant-FF to be superior to the state-of-the-art conformant planners MBP, KACMBP, and GPT in a variety of benchmark domains.

ICAPS Conference 2003 Conference Paper

Branching Matters: Alternative Branching in Graphplan

• Jörg Hoffmann 0001
• Hector Geffner

Graphplan can be understood as a heuristic search planner that performs an IDA* regression search with a heuristic function encoded in the plan graph. In this paper we study two alternatives to Graphplan where the IDA* search algorithm and the heuristic encoded in the plan graph are maintained but the branching scheme is changed: rather than constructing plans from the tail, commitments are allowed anywhere in the plan. These commitments force certain actions in or out of certain time steps. While the regression search allows Graphplan to build the plan graph only once, in the new branching scheme the plan graph must be computed anew for each state. This re-computation is expensive but is often compensated by a reduced number of states in the search. We show through a number of experiments that the resulting planner scales up much better than the original Graphplan in domains involving a higher degree of parallelism, and compares well to state-of-the-art domain-independent optimal parallel planners.

ECAI Conference 2002 Conference Paper

Extending FF to Numerical State Variables

• Jörg Hoffmann 0001

ICAPS Conference 2002 Conference Paper

Local Search Topology in Planning Benchmarks: A Theoretical Analysis

• Jörg Hoffmann 0001

Many state-of-the-art heuristic planners derive their heuristic function by relaxing the planning task at hand, where the relaxation is to assume that all delete lists are empty. The success of such planners on many of the current benchmarks suggests that in those task’s state spaces relaxed goal distances yield a heuristic function of high quality. Recent work has revealed empirical evidence confirming this intuition, stating several hypotheses about the local search topology of the current benchmarks, concerning the non-existence of dead ends and of local minima, as well as a limited maximal distance to exits on benches. Investigating a large range of planning domains, we prove that the above hypotheses do in fact hold true for the majority of the current benchmarks. This explains the recent success of heuristic planners. Specifically, it follows that FF’s search algorithm, using an idealized heuristic function, is polynomial in (at least) eight commonly used benchmark domains. Our proof methods shed light on what the structural reasons are behind the topological phenomena, giving hints on how these phenomena might be automatically recognizable.