Author name cluster

Marcel Steinmetz

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

37 papers

2 author rows

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.

ICAPS Conference 2024 Conference Paper

Explaining the Space of SSP Policies via Policy-Property Dependencies: Complexity, Algorithms, and Relation to Multi-Objective Planning

Marcel Steinmetz
Sylvie Thiébaux
Daniel Höller
Florent Teichteil-Königsbuch

Stochastic shortest path (SSP) problems are a common framework for planning under uncertainty. However, the reactive structure of their solution policies is typically not easily comprehensible by an end-user, nor do planners justify the reasons behind their choice of a particular policy over others. To strengthen confidence in the planner

ECAI Conference 2024 Conference Paper

Merge-and-Shrink Heuristics for SSPs with Prune Transformations

Thorsten Klößner
Álvaro Torralba
Marcel Steinmetz
Silvan Sievers

The merge-and-shrink framework is a powerful tool for constructing state-of-the-art admissible heuristics in classical planning. Recent work has begun generalizing the complex theory behind this framework to probabilistic planning in forms of stochastic shortest-path problems (SSPs). There however remain two important gaps. Firstly, although the previous work makes substantial efforts, the probabilistic merge-and-shrink theory is still incomplete, lacking in particular prune transformations, i. e. , transformations discarding uninteresting states, effectively reducing the size of the abstraction without losing relevant information. Secondly, an actual implementation and experimental evaluation of the merge-and-shrink framework for SSPs is so far missing. Here, we round off the previous work by contributing both a theoretical analysis of prune transformations, as well as an empirical evaluation of merge-and-shrink heuristics. Our results show that merge-and-shrink heuristics outperform previous single abstraction heuristics, but do not quite reach the performance of state-of-the-art additive combinations of such heuristics yet.

ICAPS Conference 2024 Conference Paper

On the Computational Complexity of Stackelberg Planning and Meta-Operator Verification

Gregor Behnke
Marcel Steinmetz

Stackelberg planning is a recently introduced single-turn two-player adversarial planning model, where two players are acting in a joint classical planning task, the objective of the first player being hampering the second player from achieving its goal. This places the Stackelberg planning problem somewhere between classical planning and general combinatorial two-player games. But, where exactly? All investigations of Stackelberg planning so far focused on practical aspects. We close this gap by conducting the first theoretical complexity analysis of Stackelberg planning. We show that in general Stackelberg planning is actually no harder than classical planning. Under a polynomial plan-length restriction, however, Stackelberg planning is a level higher up in the polynomial complexity hierarchy, suggesting that compilations into classical planning come with a worst-case exponential plan-length increase. In attempts to identify tractable fragments, we further study its complexity under various planning task restrictions, showing that Stackelberg planning remains intractable where classical planning is not. We finally inspect the complexity of meta-operator verification, a problem that has been recently connected to Stackelberg planning.

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.

ICAPS Conference 2024 Conference Paper

Towards Feasible Higher-Dimensional Potential Heuristics

Daniel Fiser
Marcel Steinmetz

Potential heuristics assign numerical values (potentials) to state features, where each feature is a conjunction of facts. It was previously shown that the informativeness of potential heuristics can be significantly improved by considering complex features, but computing potentials over all pairs of facts is already too costly in practice. In this paper, we investigate whether using just a few high-dimensional features instead of all conjunctions up to a dimension n can result in improved heuristics while keeping the computational cost at bay. We focus on (a) establishing a framework for studying this kind of potential heuristics, and (b) whether it is reasonable to expect improvement with just a few conjunctions. For (a), we propose two compilations that encode each conjunction explicitly as a new fact so that we can compute potentials over conjunctions in the original task as one-dimensional potentials in the compilation. Regarding (b), we provide evidence that informativeness of potential heuristics can be significantly increased with a small set of conjunctions, and these improvements have positive impact on the number of solved tasks.

ICAPS Conference 2023 Conference Paper

A Theory of Merge-and-Shrink for Stochastic Shortest Path Problems

Thorsten Klößner
Álvaro Torralba
Marcel Steinmetz
Silvan Sievers

The merge-and-shrink framework is a powerful tool to construct state space abstractions based on factored representations. One of its core applications in classical planning is the construction of admissible abstraction heuristics. In this paper, we develop a compositional theory of merge-and-shrink in the context of probabilistic planning, focusing on stochastic shortest path problems (SSPs). As the basis for this development, we contribute a novel factored state space model for SSPs. We show how general transformations, including abstractions, can be formulated on this model to derive admissible and/or perfect heuristics. To formalize the merge-and-shrink framework for SSPs, we transfer the fundamental merge-and-shrink transformations from the classical setting: shrinking, merging, and label reduction. We analyze the formal properties of these transformations in detail and show how the conditions under which shrinking and label reduction lead to perfect heuristics can be extended to the SSP setting.

ECAI Conference 2023 Conference Paper

Cartesian Abstractions and Saturated Cost Partitioning in Probabilistic Planning

Thorsten Klößner
Jendrik Seipp
Marcel Steinmetz

Stochastic shortest path problems (SSPs) capture probabilistic planning tasks with the objective of minimizing expected cost until reaching the goal. One of the strongest methods to solve SSPs optimally is heuristic search guided by an admissible (lower-bounding) heuristic function. Recently, probability-aware pattern database (PDB) abstractions have been highlighted as an efficient way of generating such lower bounds, with significant advantages over traditional determinization-based approaches. Here, we follow this work, yet consider a more general type, Cartesian abstractions, which have been used successfully in the classical setting. We show how to construct probability-aware Cartesian abstractions via a counterexample-guided abstraction refinement (CEGAR) loop akin to classical planning. This method is complete, meaning it guarantees convergence to the optimal expected cost if not terminated prematurely. Furthermore, we investigate the admissible combination of multiple such heuristics using saturated cost partitioning (SCP), marking its first application in the probabilistic setting. In our experiments, we show that probability-aware Cartesian abstractions yield much more informative heuristics than their determinization-based counterparts. Finally, we show that SCP yields probability-aware abstraction heuristics that are superior to the previous state of the art.

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

AAAI Conference 2022 Conference Paper

Classical Planning with Avoid Conditions

Marcel Steinmetz
Jörg Hoffmann
Alisa Kovtunova
Stefan Borgwardt

It is often natural in planning to specify conditions that should be avoided, characterizing dangerous or highly undesirable behavior. PDDL3 supports this with temporal-logic state trajectory constraints. Here we focus on the simpler case where the constraint is a non-temporal formula ϕ – the avoid condition – that must be false throughout the plan. We design techniques tackling such avoid conditions effectively. We show how to learn from search experience which states necessarily lead into ϕ, and we show how to tailor abstractions to recognize that avoiding ϕ will not be possible starting from a given state. We run a large-scale experiment, comparing our techniques against compilation methods and against simple state pruning using ϕ. The results show that our techniques are often superior.

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.

AAAI Conference 2022 Conference Paper

Expressivity of Planning with Horn Description Logic Ontologies

Stefan Borgwardt
Jörg Hoffmann
Alisa Kovtunova
Markus Krötzsch
Bernhard Nebel
Marcel Steinmetz

State constraints in AI Planning globally restrict the legal environment states. Standard planning languages make closeddomain and closed-world assumptions. Here we address openworld state constraints formalized by planning over a description logic (DL) ontology. Previously, this combination of DL and planning has been investigated for the light-weight DL DL-Lite. Here we propose a novel compilation scheme into standard PDDL with derived predicates, which applies to more expressive DLs and is based on the rewritability of DL queries into Datalog with stratified negation. We also provide a new rewritability result for the DL Horn-ALCHOIQ, which allows us to apply our compilation scheme to quite expressive ontologies. In contrast, we show that in the slight extension Horn-SROIQ no such compilation is possible unless the weak exponential hierarchy collapses. Finally, we show that our approach can outperform previous work on existing benchmarks for planning with DL ontologies, and is feasible on new benchmarks taking advantage of more expressive ontologies.

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

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.

PRL Workshop 2021 Workshop Paper

Debugging a Policy: A Framework for Automatic Action Policy Testing

Marcel Steinmetz
Timo P. Gros
Philippe Heim
Daniel Höller
Joerg Hoffmann

Neural network (NN) action policies are an attractive option for real-time action decisions in dynamic environments. Yet this requires a high degree of trust in the NN. How to gain such trust? Systematic testing certainly is one possible answer, in analogy to program testing. The input to the program becomes the start state for the policy; and erroneous program behaviors – “bugs” – become bad policy behavior, e. g. not reaching the goal from a solvable state. We introduce a framework spelling out this concept. The framework is generic and in principle applicable to arbitrary planning models. We discuss how this form of testing can be operationalized, i. e. , how to confirm a bug has been found, and how potential bugs might be identified in the first place. This essentially involves seeing standard planning concepts through the new lense of policy testing. The implementation and practical exploration of this framework remains open for future work. We believe that action policy testing is an important topic for ICAPS, and we hope that our framework will serve to start its discussion.

AAAI Conference 2021 Conference Paper

Faster Stackelberg Planning via Symbolic Search and Information Sharing

Álvaro Torralba
Patrick Speicher
Robert Künnemann
Marcel Steinmetz
Jörg Hoffmann

Stackelberg planning is a recent framework where a leader and a follower each choose a plan in the same planning task, the leader’s objective being to maximize plan cost for the follower. This formulation naturally captures security-related (leader=defender, follower=attacker) as well as robustnessrelated (leader=adversarial event, follower=agent) scenarios. Solving Stackelberg planning tasks requires solving many related planning tasks at the follower level (in the worst case, one for every possible leader plan). Here we introduce new methods to tackle this source of complexity, through sharing information across follower tasks. Our evaluation shows that these methods can significantly reduce both the time needed to solve follower tasks and the number of follower tasks that need to be solved in the first place.

KR Conference 2021 Short Paper

Making DL-Lite Planning Practical

Stefan Borgwardt
Jörg Hoffmann
Alisa Kovtunova
Marcel Steinmetz

Planning in the presence of background ontologies is a topic of long-standing interest in AI. It combines the problems of (1) belief update complexity and (2) state-space combinatorics. DL-Lite offers an attractive solution to (1), with belief updates possible at the ABox level. Indeed, it has been shown that DL-Lite planning can be compiled into the commonly used planning language PDDL. Yet that compilation was previously found to be infeasible for off-the-shelf planning systems. Here we analyze the reasons for this problem and find that the bottleneck lies in the planner pre-processes, in particular in the naïve DNF transformations used to compile the PDDL input into the planners' internal representations. Consequently, we design a PDDL pre-compiler realizing a polynomial DNF transformation. We leverage a particular PDDL language feature ("derived predicates") to avoid the need for excessive control structure. Our pre-compiler turns out to be quite effective: the previous bottleneck disappears, and experiments on a broad range of benchmarks demonstrate the first practical technology for DL-Lite planning.

PDF Details DOI

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.

AAAI Conference 2020 Conference Paper

A New Approach to Plan-Space Explanation: Analyzing Plan-Property Dependencies in Oversubscription Planning

Rebecca Eifler
Michael Cashmore
Jörg Hoffmann
Daniele Magazzeni
Marcel Steinmetz

In many usage scenarios of AI Planning technology, users will want not just a plan π but an explanation of the space of possible plans, justifying π. In particular, in oversubscription planning where not all goals can be achieved, users may ask why a conjunction A of goals is not achieved by π. We propose to answer this kind of question with the goal conjunctions B excluded by A, i. e. , that could not be achieved if A were to be enforced. We formalize this approach in terms of plan-property dependencies, where plan properties are propositional formulas over the goals achieved by a plan, and dependencies are entailment relations in plan space. We focus on entailment relations of the form g∈A g ⇒ ¬ g∈B g, and devise analysis techniques globally identifying all such relations, or locally identifying the implications of a single given plan property (user question) g∈A g. We show how, via compilation, one can analyze dependencies between a richer form of plan properties, specifying formulas over action subsets touched by the plan. We run comprehensive experiments on adapted IPC benchmarks, and ﬁnd that the suggested analyses are reasonably feasible at the global level, and become signiﬁcantly more effective at the local level.

JAIR Journal 2020 Journal Article

Bridging the Gap Between Probabilistic Model Checking and Probabilistic Planning: Survey, Compilations, and Empirical Comparison

Michaela Klauck
Marcel Steinmetz
Jörg Hoffmann
Holger Hermanns

Markov decision processes are of major interest in the planning community as well as in the model checking community. But in spite of the similarity in the considered formal models, the development of new techniques and methods happened largely independently in both communities. This work is intended as a beginning to unite the two research branches. We consider goal-reachability analysis as a common basis between both communities. The core of this paper is the translation from Jani, an overarching input language for quantitative model checkers, into the probabilistic planning domain definition language (PPDDL), and vice versa from PPDDL into Jani. These translations allow the creation of an overarching benchmark collection, including existing case studies from the model checking community, as well as benchmarks from the international probabilistic planning competitions (IPPC). We use this benchmark set as a basis for an extensive empirical comparison of various approaches from the model checking community, variants of value iteration, and MDP heuristic search algorithms developed by the AI planning community. On a per benchmark domain basis, techniques from one community can achieve state-ofthe-art performance in benchmarks of the other community. Across all benchmark domains of one community, the performance comparison is however in favor of the solvers and algorithms of that particular community. Reasons are the design of the benchmarks, as well as tool-related limitations. Our translation methods and benchmark collection foster crossfertilization between both communities, pointing out specific opportunities for widening the scope of solvers to different kinds of models, as well as for exchanging and adopting algorithms across communities.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Let’s Learn Their Language? A Case for Planning with Automata-Network Languages from Model Checking

Jorg Hoffmann
Holger Hermanns
Michaela Klauck
Marcel Steinmetz
Erez Karpas
Daniele Magazzeni

It is widely known that AI planning and model checking are closely related. Compilations have been devised between various pairs of language fragments. What has barely been voiced yet, though, is the idea to let go of one’s own modeling language, and use one from the other area instead. We advocate that idea here – to use automata-network languages from model checking instead of PDDL – motivated by modeling difﬁculties relating to planning agents surrounded by exogenous agents in complex environments. One could, of course, address this by designing additional extended planning languages. But one can also leverage decades of work on modeling in the formal methods community, creating potential for deep synergy and integration with their techniques as a side effect. We believe there’s a case to be made for the latter, as one modeling alternative in planning among others.

IJCAI Conference 2020 Conference Paper

Plan-Space Explanation via Plan-Property Dependencies: Faster Algorithms & More Powerful Properties

Rebecca Eifler
Marcel Steinmetz
Álvaro Torralba
Jörg Hoffmann

Justifying a plan to a user requires answering questions about the space of possible plans. Recent work introduced a framework for doing so via plan-property dependencies, where plan properties p are Boolean functions on plans, and p entails q if all plans that satisfy p also satisfy q. We extend this work in two ways. First, we introduce new algorithms for computing plan-property dependencies, leveraging symbolic search and devising pruning methods for this purpose. Second, while the properties p were previously limited to goal facts and so-called action-set (AS) properties, here we extend them to LTL. Our new algorithms vastly outperform the previous ones, and our methods for LTL cause little overhead on AS properties.

PDF Details DOI

ICAPS Conference 2019 Conference Paper

Bridging the Gap between Abstractions and Critical-Path Heuristics via Hypergraphs

Marcel Steinmetz
Álvaro Torralba

Abstractions and critical-path heuristics are among the most important families of admissible heuristics in classical planning. In this paper, we present a new family of heuristics, which we name hyperabstractions, given by the combination of the principal ideas underlying abstractions and critical-path heuristics. Hyperabstractions approximate goal distances through a mapping from states to sets of abstract states. The abstract transition behavior forms a relation between abstract states and sets of abstract states, and is formally represented via the notion of hypergraphs. We show that both abstractions and critical-path heuristics can naturally be expressed as members of this family. Moreover, we devise a method to construct hyperabstractions, using either a set of abstractions or a critical-path heuristic as a seed, in a way that guarantees that the resulting distance estimations dominate those of the input heuristics, sometimes even strictly. By finding suitable cost partitionings for hyperabstraction heuristics, this dominance result is preserved even in comparison to the additive combination of the input heuristics. Our experiments indicate the potential of this new class of heuristics, opening a wide range of future research topics.

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.

IJCAI Conference 2018 Conference Paper

LP Heuristics over Conjunctions: Compilation, Convergence, Nogood Learning

Marcel Steinmetz
Joerg Hoffmann

Two strands of research in classical planning are LP heuristics and conjunctions to improve approximations. Combinations of the two have also been explored. Here, we focus on convergence properties, forcing the LP heuristic to equal the perfect heuristic h* in the limit. We show that, under reasonable assumptions, partial variable merges are strictly dominated by the compilation Pi^C of explicit conjunctions, and that both render the state equation heuristic equal to h* for a suitable set C of conjunctions. We show that consistent potential heuristics can be computed from a variant of Pi^C, and that such heuristics can represent h* for suitable C. As an application of these convergence properties, we consider sound nogood learning in state space search, via refining the set C. We design a suitable refinement method to this end. Experiments on IPC benchmarks show significant performance improvements in several domains.

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.

AAAI Conference 2018 Conference Paper

Stackelberg Planning: Towards Effective Leader-Follower State Space Search

Patrick Speicher
Marcel Steinmetz
Michael Backes
Jörg Hoffmann
Robert Künnemann

Inspired by work on Stackelberg security games, we introduce Stackelberg planning, where a leader player in a classical planning task chooses a minimum-cost action sequence aimed at maximizing the plan cost of a follower player in the same task. Such Stackelberg planning can provide useful analyses not only in planning-based security applications like network penetration testing, but also to measure robustness against perturbances in more traditional planning applications (e. g. with a leader sabotaging road network connections in transportation-type domains). To identify all equilibria – exhibiting the leader’s own-cost-vs. -follower-cost tradeoff – we design leader-follower search, a state space search at the leader level which calls in each state an optimal planner at the follower level. We devise simple heuristic guidance, branch-and-bound style pruning, and partial-order reduction techniques for this setting. We run experiments on Stackelberg variants of IPC and pentesting benchmarks. In several domains, Stackelberg planning is quite feasible in practice.

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

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.

IJCAI Conference 2017 Conference Paper

Search and Learn: On Dead-End Detectors, the Traps they Set, and Trap Learning

Marcel Steinmetz
Jörg Hoffmann

A key technique for proving unsolvability in classical planning are dead-end detectors \Delta: effectively testable criteria sufficient for unsolvability, pruning (some) unsolvable states during search. Related to this, a recent proposal is the identification of traps prior to search, compact representations of non-goal state sets T that cannot be escaped. Here, we create new synergy across these ideas. We define a generalized concept of traps, relative to a given dead-end detector \Delta, where T can be escaped, but only into dead-end states detected by \Delta. We show how to learn compact representations of such T during search, extending the reach of \Delta. Our experiments show that this can be quite beneficial. It improves coverage for many unsolvable benchmark planning domains and dead-end detectors \Delta, in particular on resource-constrained domains where it outperforms the state of the art.

AIJ Journal 2017 Journal Article

State space search nogood learning: Online refinement of critical-path dead-end detectors in planning

Marcel Steinmetz
Jörg Hoffmann

Conflict-directed learning is ubiquitous in constraint satisfaction problems like SAT, but has been elusive for state space search on reachability problems like classical planning. Almost all existing approaches learn nogoods relative to a fixed solution-length bound, in which case planning/reachability reduces to a constraint satisfaction problem. Here we introduce an approach to learning more powerful nogoods, that are sound regardless of solution length, i. e. , that identify dead-end states for which no solution exists. The key technique we build on are critical-path heuristics h C, relative to a set C of conjunctions. These recognize a dead-end state s, returning h C ( s ) = ∞, if s has no solution even when allowing to break up conjunctive subgoals into the elements of C. Our key idea is to learn C during search. Whenever forward search has identified an unrecognized dead-end s, where h C ( s ) < ∞, we analyze the situation at s, and add new conjunctions into C in a way guaranteeing to obtain h C ( s ) = ∞. Thus we learn to recognize s, as well as similar dead-ends search may encounter in the future. We furthermore learn clauses ϕ where s ′ ⊭ ϕ implies h C ( s ′ ) = ∞, to avoid the overhead of computing h C on every search state. Arranging these techniques in a depth-first search, we obtain an algorithm approaching the elegance of nogood learning in constraint satisfaction, learning to refute search subtrees. We run comprehensive experiments on solvable and unsolvable planning benchmarks. In cases where forward search can identify dead-ends, and where h C dead-end detection is effective, our techniques reduce the depth-first search space size by several orders of magnitude, and often result in state-of-the-art performance.

JAIR Journal 2016 Journal Article

Combining the Delete Relaxation with Critical-Path Heuristics: A Direct Characterization

Maximilian Fickert
Joerg Hoffmann
Marcel Steinmetz

Recent work has shown how to improve delete relaxation heuristics by computing relaxed plans, i.e., the hFF heuristic, in a compiled planning task PiC which represents a given set C of fact 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, and the size of PiC grows exponentially in |C|. We herein provide a direct characterization, without compilation, making explicit how the approach arises from a combination of the delete-relaxation with critical-path heuristics. Designing equations characterizing a novel view on h+ on the one hand, and a generalized version hC of hm on the other hand, we show that h+(PiC) can be characterized in terms of a combined hcplus equation. This naturally generalizes the standard delete-relaxation framework: understanding that framework as a relaxation over singleton facts as atomic subgoals, one can refine the relaxation by using the conjunctions C as atomic subgoals instead. Thanks to this explicit view, we identify the precise source of complexity in hFF(PiC), namely maximization of sets of supported atomic subgoals during relaxed plan extraction, which is easy for singleton-fact subgoals but is NP-complete in the general case. Approximating that problem greedily, we obtain a polynomial-time hCFF version of hFF(PiC), superseding the PiC compilation, and superseding the modified PiCce compilation which achieves the same complexity reduction but at an information loss. Experiments on IPC benchmarks show that these theoretical advantages can translate into empirical ones.

PDF Details DOI

JAIR Journal 2016 Journal Article

Goal Probability Analysis in Probabilistic Planning: Exploring and Enhancing the State of the Art

Marcel Steinmetz
Jörg Hoffmann
Olivier Buffet

Unavoidable dead-ends are common in many probabilistic planning problems, e.g. when actions may fail or when operating under resource constraints. An important objective in such settings is MaxProb, determining the maximal probability with which the goal can be reached, and a policy achieving that probability. Yet algorithms for MaxProb probabilistic planning are severely underexplored, to the extent that there is scant evidence of what the empirical state of the art actually is. We close this gap with a comprehensive empirical analysis. We design and explore a large space of heuristic search algorithms, systematizing known algorithms and contributing several new algorithm variants. We consider MaxProb, as well as weaker objectives that we baptize AtLeastProb (requiring to achieve a given goal probabilty threshold) and ApproxProb (requiring to compute the maximum goal probability up to a given accuracy). We explore both the general case where there may be 0-reward cycles, and the practically relevant special case of acyclic planning, such as planning with a limited action-cost budget. We design suitable termination criteria, search algorithm variants, dead-end pruning methods using classical planning heuristics, and node selection strategies. We design a benchmark suite comprising more than 1000 instances adapted from the IPPC, resource-constrained planning, and simulated penetration testing. Our evaluation clarifies the state of the art, characterizes the behavior of a wide range of heuristic search algorithms, and demonstrates significant benefits of our new algorithm variants.

PDF Details DOI

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

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.

AAAI Conference 2016 Conference Paper

Towards Clause-Learning State Space Search: Learning to Recognize Dead-Ends

Marcel Steinmetz
Joerg Hoffmann

We introduce a state space search method that identiﬁes deadend states, analyzes the reasons for failure, and learns to avoid similar mistakes in the future. Our work is placed in classical planning. The key technique are critical-path heuristics hC, relative to a set C of conjunctions. These recognize a dead-end state s, returning hC (s) = ∞, if s has no solution even when allowing to break up conjunctive subgoals into the elements of C. Our key idea is to learn C during search. Starting from a simple initial C, we augment search to identify unrecognized dead-ends s, where hC (s) < ∞. We design methods analyzing the situation at such s, adding new conjunctions into C to obtain hC (s) = ∞, thus learning to recognize s as well as similar dead-ends search may encounter in the future. We furthermore learn clauses φ where s |= φ implies hC (s ) = ∞, to avoid the prohibitive overhead of computing hC on every search state. Arranging these techniques in a depth-ﬁrst search, we obtain an algorithm approaching the elegance of clause learning in SAT, learning to refute search subtrees. Our experiments show that this can be quite powerful. On problems where dead-ends abound, the learning reliably reduces the search space by several orders of magnitude.