Author name cluster

Daniel Gnad

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.

16 papers

1 author row

AAAI Conference 2026 Conference Paper

Managing Infinite Abstractions in Numeric Pattern Database Heuristics

Markus Fritzsche
Daniel Gnad
Mikhail Gruntov
Alexander Shleyfman

Pattern Database (PDB) heuristics are an established approach in optimal classical planning that is used in state-of-the-art planning systems. PDBs are based on projections, which induce an abstraction of the original problem. Computing all cheapest plans in the abstraction yields an admissible heuristic. Despite their success, PDBs have only recently been adapted to numeric planning, which extends classical planning with numeric state variables. The difficulty in supporting numeric variables is that the induced abstractions, in contrast to classical planning, are generally infinite. Thus, they cannot be explored exhaustively to compute a heuristic. The foundational work that introduced numeric PDBs employed a simple approach that computes only a finite part of the abstraction. We analyze this framework and identify cases where it necessarily results in an uninformed heuristic. We propose several improvements over the basic variant of numeric PDBs that lead to enhanced heuristic accuracy.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Counting and Reasoning with Plans

David Speck
Markus Hecher
Daniel Gnad
Johannes K. Fichte
Augusto B. Corrêa

Classical planning asks for a sequence of operators reaching a given goal. While the most common case is to compute a plan, many scenarios require more than that. However, quantitative reasoning on the plan space remains mostly unexplored. A fundamental problem is to count plans, which relates to the conditional probability on the plan space. Indeed, qualitative and quantitative approaches are well-established in various other areas of automated reasoning. We present the first study to quantitative and qualitative reasoning on the plan space. In particular, we focus on polynomially bounded plans. On the theoretical side, we study its complexity, which gives rise to rich reasoning modes. Since counting is hard in general, we introduce the easier notion of facets, which enables understanding the significance of operators. On the practical side, we implement quantitative reasoning for planning. Thereby, we transform a planning task into a propositional formula and use knowledge compilation to count different plans. This framework scales well to large plan spaces, while enabling rich reasoning capabilities such as learning pruning functions and explainable planning.

PDF Details DOI

IJCAI Conference 2025 Conference Paper

Decoupled Search for the Masses: A Novel Task Transformation for Classical Planning (Extended Abstract)

David Speck
Daniel Gnad

Classical planning provides a framework for solving sequential decision-making problems, i. e. , finding a sequence of actions that transforms the current state of the world into a state that satisfies a desired goal condition. Planning tasks are modeled in a logic that describes the environment and its dynamics. It is well known that the specific problem formulation can significantly affect the performance of planning systems solving problems like the Rubik's Cube or finding algorithms for matrix multiplication. In this work, we propose a domain-general problem reformulation that embodies decoupled search, a search-reduction technique from classical planning and model checking. Decoupled search decomposes a given problem to exploit its structure, achieving exponential reductions over other search techniques. We show that decoupled search can be captured exactly as a task reformulation and that, on many benchmark domains, it performs as good and sometimes even better than a native decoupled-search implementation.

PDF Details DOI

HAXP Workshop 2025 Workshop Paper

Explainable Planning via Counterfactual Task Analysis for the Beluga Challenge and Beyond

Elliot Gestrin
Gustaf Söderholm
Paul Höft
Mauricio Salerno
Jendrik Seipp
Daniel Gnad

The Beluga Challenge, recently organized by the Tuples consortium, offered a track on explainable planning (XAIP), to the best of our knowledge the first XAIP competition to date. Within the setting of the Beluga logistics domain, participants were given a planning task and a plan, and were supposed to answer a query to explain to a human expert certain choices made in the plan. The queries ask about particular state atoms that were achieved and alternatives “why achieve this atom A instead of that atom B? ”, action reordering “can I do A before B instead? ”, or about the consequences of object removal “what happens if we forbid to use object X? ”. In this work, we propose counterfactual reasoning to come up with explanations that answer these queries. We design task reformulations, modifications that alter the input planning task, such that the solutions for the modified task allow to explain the choices made in the initial plan. Our framework generalizes the queries posed in the Beluga challenge. To obtain textual explanations, we employ a large language model (LLM) that allows our system to be used without planning-specific knowledge. We empirically show that solving the modified task is similarly hard as finding a plan for the original task, showing that our approach is efficient for practical usage.

PDF

KR Conference 2025 System Paper

Interactive Exploration of Plan Spaces

Daniel Gnad
Markus Hecher
Sarah Alice Gaggl
Dominik Rusovac
David Speck
Johannes K. Fichte

Many planning applications require not only a single solution but benefit substantially from having a set of possible plans from which users can select, for example, when explaining plans. For decades, research in classical AI planning has primarily focused on quickly finding single plans. Only recently researchers have started to investigate preferences, enumerate plans by top-k planning, or count plans to reason about the plan space. Unfortunately, reasoning about the plan space is computationally extremely hard and feeding many similar plans to the user is hardly practical. To circumvent computational shortcomings while still being able to reason about variability in plans, faceted actions have been introduced very recently. These are meaningful actions that can be used by some plan but are not required by all plans. Enforcing or forbidding such facets allows for navigating even large plan spaces while ensuring desired properties quickly and step by step. In this paper, we illustrate an industrial challenge, the Beluga logistics problem of Airbus, where reasoning with facets enables targeted plan space navigation. We present an approach to handle large plan spaces iteratively and interactively and present a tool that we call PlanPilot.

PDF Details DOI

AAAI Conference 2025 Conference Paper

PDBs Go Numeric: Pattern-Database Heuristics for Simple Numeric Planning

Daniel Gnad
Lee-Or Alon
Eyal Weiss
Alexander Shleyfman

Despite the widespread success of pattern database (PDB) heuristics in classical planning, to date there has been no application of PDBs to planning with numeric variables. In this paper we attempt to close this gap. We address optimal numeric planning involving conditions characterized by linear expressions and actions that modify numeric variables by constant quantities. Building upon prior research, we present an adaptation of PDB heuristics to numeric planning, introducing several approaches to deal with the unbounded nature of numeric variable projections. These approaches aim to restrict the initially infinite projections, thereby bounding the number of states and ultimately constraining the resulting PDBs. We show that the PDB heuristics obtained with our approach can provide strong guidance for the search.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Structurally Restricted Fragments of Numeric Planning – a Complexity Analysis

Alexander Shleyfman
Daniel Gnad
Peter Jonsson

Numeric planning is known to be undecidable even under severe restrictions. Prior work has investigated the decidability boundaries by restricting the expressiveness of the planning formalism in terms of the numeric functions allowed in conditions and effects. We study a well-known restricted form of Hoffmann's simple numeric planning, which is undecidable. We analyze the complexity by imposing restrictions on the causal structure, exploiting a novel method for bounding variable domain sizes. First, we show that plan existence for tasks where all numeric variables are root nodes in the causal graph is in PSPACE. Second, we show that for tasks with only numeric leaf variables the problem is decidable, and that it is in PSPACE if the propositional state space has a fixed size. Our work lays a strong foundation for future investigations of structurally more complex tasks. From a practical perspective, our method allows to employ heuristics and methods that are geared towards finite variable domains (such as pattern database heuristics or decoupled search) to solve non-trivial families of numeric planning problems.

PDF Details DOI

IJCAI Conference 2021 Conference Paper

Custom-Design of FDR Encodings: The Case of Red-Black Planning

Daniel Fišer
Daniel Gnad
Michael Katz
Jörg Hoffmann

Classical planning tasks are commonly described in PDDL, while most planning systems operate on a grounded finite-domain representation (FDR). The translation of PDDL into FDR is complex and has a lot of choice points---it involves identifying so called mutex groups---but most systems rely on the translator that comes with Fast Downward. Yet the translation choice points can strongly impact performance. Prior work has considered optimizing FDR encodings in terms of the number of variables produced. Here we go one step further by proposing to custom-design FDR encodings, optimizing the encoding to suit particular planning techniques. We develop such a custom design here for red-black planning, a partial delete relaxation technique. The FDR encoding affects the causal graph and the domain transition graph structures, which govern the tractable fragment of red-black planning and hence affects the respective heuristic function. We develop integer linear programming techniques optimizing the scope of that fragment in the resulting FDR encoding. We empirically show that the performance of red-black planning can be improved through such FDR custom design.

PDF Details DOI

AAAI Conference 2021 Conference Paper

Revisiting Dominance Pruning in Decoupled Search

Daniel Gnad

In classical planning as search, duplicate state pruning is a standard method to avoid unnecessarily handling the same state multiple times. In decoupled search, similar to symbolic search approaches, search nodes, called decoupled states, do not correspond to individual states, but to sets of states. Therefore, duplicate state pruning is less effective in decoupled search, and dominance pruning is employed, taking into account the state sets. We observe that the time required for dominance checking dominates the overall runtime, and propose two ways to tackle this issue. Our main contribution is a stronger variant of dominance checking for optimal planning, where efficiency and pruning power are most crucial. The new variant greatly improves the latter, without incurring a computational overhead. Moreover, we develop three methods that make the dominance check more efficient: exact duplicate checking, which, albeit resulting in weaker pruning, can pay off due to the use of hashing; avoiding the dominance check in non-optimal planning if leaf state spaces are invertible; and exploiting the transitivity of the dominance relation to only check against the relevant subset of visited decoupled states. We show empirically that all our improvements are indeed beneficial in many standard benchmarks.

PDF Details

AAAI Conference 2019 Conference Paper

Learning How to Ground a Plan – Partial Grounding in Classical Planning

Daniel Gnad
Álvaro Torralba
Martín Domínguez
Carlos Areces
Facundo Bustos

Current classical planners are very successful in finding (nonoptimal) plans, even for large planning instances. To do so, most planners rely on a preprocessing stage that computes a grounded representation of the task. Whenever the grounded task is too big to be generated (i. e. , whenever this preprocess fails) the instance cannot even be tackled by the actual planner. To address this issue, we introduce a partial grounding approach that grounds only a projection of the task, when complete grounding is not feasible. We propose a guiding mechanism that, for a given domain, identifies the parts of a task that are relevant to find a plan by using off-the-shelf machine learning methods. Our empirical evaluation attests that the approach is capable of solving planning instances that are too big to be fully grounded.

PDF Details

JAIR Journal 2019 Journal Article

Strong Stubborn Set Pruning for Star-Topology Decoupled State Space Search

Daniel Gnad
Jörg Hoffmann
Martin Wehrle

Analyzing reachability in large discrete transition systems is an important sub-problem in several areas of AI, and of CS in general. State space search is a basic method for conducting such an analysis. A wealth of techniques have been proposed to reduce the search space without affecting the existence of (optimal) solution paths. In particular, strong stubborn set (SSS) pruning is a prominent such method, analyzing action dependencies to prune commutative parts of the search space. We herein show how to apply this idea to star-topology decoupled state space search, a recent search reformulation method invented in the context of classical AI planning. Star-topology decoupled state space search, short decoupled search, addresses planning tasks where a single center component interacts with several leaf components. The search exploits a form of conditional independence arising in this setting: given a fixed path p of transitions by the center, the possible leaf moves compliant with p are independent across the leaves. Decoupled search thus searches over center paths only, maintaining the compliant paths for each leaf separately. This avoids the enumeration of combined states across leaves. Just like standard search, decoupled search is adversely affected by commutative parts of its search space. The adaptation of strong stubborn set pruning is challenging due to the more complex structure of the search space, and the resulting ways in which action dependencies may affect the search. We spell out how to address this challenge, designing optimality-preserving decoupled strong stubborn set (DSSS) pruning methods. We introduce a design for star topologies in full generality, as well as simpler design variants for the practically relevant fork and inverted fork special cases. We show that there are cases where DSSS pruning is exponentially more effective than both, decoupled search and SSS pruning, exhibiting true synergy where the whole is more than the sum of its parts. Empirically, DSSS pruning reliably inherits the best of its components, and sometimes outperforms both.

PDF Details DOI

AIJ Journal 2018 Journal Article

Star-topology decoupled state space search

Daniel Gnad
Jörg Hoffmann

State space search is a basic method for analyzing reachability in discrete transition systems. To tackle large compactly described transition systems – the state space explosion – a wealth of techniques (e. g. , partial-order reduction) have been developed that reduce the search space without affecting the existence of (optimal) solution paths. Focusing on classical AI planning, where the compact description is in terms of a vector of state variables, an initial state, a goal condition, and a set of actions, we add another technique, that we baptize star-topology decoupling, into this arsenal. A star topology partitions the state variables into components so that a single center component directly interacts with several leaf components, but the leaves interact only via the center. Many applications explicitly come with such structure; any classical planning task can be viewed in this way by selecting the center as a subset of state variables separating connected leaf components. Our key observation is that, given such a star topology, the leaves are conditionally independent given the center, in the sense that, given a fixed path of transitions by the center, the possible center-compliant paths are independent across the leaves. Our decoupled search hence branches over center transitions only, and maintains the center-compliant paths for each leaf separately. As we show, this method has exponential separations to all previous search reduction techniques, i. e. , examples where it results in exponentially less effort. One can, in principle, prune duplicates in a way so that the decoupled state space can never be larger than the original one. Standard search algorithms remain applicable using simple transformations. Our experiments exhibit large improvements on standard AI planning benchmarks with a pronounced star topology. 1

Details DOI

IJCAI Conference 2018 Conference Paper

Unchaining the Power of Partial Delete Relaxation, Part II: Finding Plans with Red-Black State Space Search

Maximilian Fickert
Daniel Gnad
Joerg Hoffmann

Red-black relaxation in classical planning allows to interpolate between delete-relaxed and real planning. Yet the traditional use of relaxations to generate heuristics restricts relaxation usage to tractable fragments. How to actually tap into the red-black relaxation's interpolation power? Prior work has devised red-black state space search (RBS) for intractable red-black planning, and has explored two uses: proving unsolvability, generating seed plans for plan repair. Here, we explore the generation of plans directly through RBS. We design two enhancements to this end: (A) use a known tractable fragment where possible, use RBS for the intractable parts; (B) check RBS state transitions for realizability, spawn relaxation refinements where the check fails. We show the potential merits of both techniques on IPC benchmarks.

PDF Details

IJCAI Conference 2017 Conference Paper

Beyond Forks: Finding and Ranking Star Factorings for Decoupled Search

Daniel Gnad
Valerie Poser
Jörg Hoffmann

Star-topology decoupling is a recent search reduction method for forward state space search. The idea basically is to automatically identify a star factoring, then search only over the center component in the star, avoiding interleavings across leaf components. The framework can handle complex star topologies, yet prior work on decoupled search considered only factoring strategies identifying fork and inverted-fork topologies. Here, we introduce factoring strategies able to detect general star topologies, thereby extending the reach of decoupled search to new factorings and to new domains, sometimes resulting in significant performance improvements. Furthermore, we introduce a predictive portfolio method that reliably selects the most suitable factoring for a given planning task, leading to superior overall performance.

PDF Details

IJCAI Conference 2016 Conference Paper

Decoupled Strong Stubborn Sets

Daniel Gnad
Martin Wehrle
J
ouml; rg Hoffmann

Recent work has introduced fork-decoupled search, addressing classical planning problems where a single center component provides preconditions for several leaf components. Given a fixed center path π C, the leaf moves compliant with π C can then be scheduled independently for each leaf. Fork-decoupled search thus searches over center paths only, maintaining the compliant paths for each leaf separately. This can yield dramatic benefits. It is empirically complementary to partial order reduction via strong stubborn sets, in that each method yields its strongest reductions in different benchmarks. Here we show that the two methods can be combined, in the form of strong stubborn sets for fork-decoupled search. This can yield exponential advantages relative to both methods. Empirically, the combination reliably inherits the best of its components, and often outperforms both.

PDF Details

IJCAI Conference 2016 Conference Paper

On State-Dominance Criteria in Fork-Decoupled Search

aacute; lvaro Torralba
Daniel Gnad
Patrick Dubbert
J
ouml; rg Hoffmann

Fork-decoupled search is a recent approach to classical planning that exploits fork structures, where a single center component provides preconditions for several leaf components. The decoupled states in this search consist of a center state, along with a price for every leaf state. Given this, when does one decoupled state dominate another? Such state-dominance criteria can be used to prune dominated search states. Prior work has devised only a trivial criterion. We devise several more powerful criteria, show that they preserve optimality, and establish their interrelations. We show that they can yield exponential reductions. Experiments on IPC benchmarks attest to the possible practical benefits.

PDF Details