Author name cluster

Daniel Gnad 0001

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.

17 papers

1 author row

ECAI Conference 2025 Conference Paper

Combining Heuristics and Transition Classifiers in Classical Planning

Farid Musayev
Dominik Drexler
Daniel Gnad 0001
Jendrik Seipp

Recent work on learning for classical planning has primarily focused on exclusively employing the learned heuristics or policies. However, no purely learning-based method has consistently outperformed state-of-the-art planners to date. To address this, we return to the research paradigm that integrates learned domain knowledge with traditional, non-learned planning techniques. We propose a novel and simple approach for learning transition classifiers, using tree-based statistical learning over description logic features. In experiments, we evaluate various strategies for integrating learned classifiers with the FF heuristic, a state-of-the-art non-learned heuristic. Our results demonstrate that augmenting classical heuristics with transition classifiers leads to substantial performance improvements. The strongest variant combines classifier-based lookahead search with learned knowledge to avoid transitions into unsolvable states, frequently outperforming state-of-the-art traditional and learning-based planners.

ECAI Conference 2024 Conference Paper

Cost Partitioning for Multiple Sequence Alignment

Mika Skjelnes
Daniel Gnad 0001
Jendrik Seipp

Multiple Sequence Alignment (MSA) is a fundamental problem in computational biology that is used to understand the evolutionary history of protein, DNA, or RNA sequences. An optimal alignment for two sequences can efficiently be found using dynamic programming, but computing optimal alignments for more sequences continues to be a hard problem. A common method to solve MSA problems is A* search with admissible heuristics, computed from subsets of the input sequences. In this paper, we consider MSA from the perspective of cost partitioning and relate the existing heuristics for MSA to uniform cost partitioning and post-hoc optimization, two well-known techniques from the automated planning literature. We show that the MSA heuristics are bounded by uniform cost partitioning and that post-hoc optimization yields strictly dominating heuristics. For a common benchmark set of protein sequences and a set of DNA sequences, we show that the theoretical dominance relations between the heuristics carry over to practical instances.

ICAPS Conference 2024 Conference Paper

Decoupled Search for the Masses: A Novel Task Transformation for Classical Planning

David Speck 0001
Daniel Gnad 0001

Automated problem reformulation is a common technique in classical planning to identify and exploit problem structures. Decoupled search is an approach that automatically decomposes planning tasks based on their causal structure, often significantly reducing the search effort. However, its broad applicability is limited by the need for specialized algorithms. In this paper, we present an approach that embodies decoupled search for non-optimal planning through a novel task transformation. Specifically, given a task and a decomposition, we create a transformed task such that the state space of the transformed task is isomorphic to that of decoupled search on the original task. This eliminates the need for specialized algorithms and allows the use of various planning technology in the decoupled-search framework. Empirical evaluation shows that our method is empirically competitive with specialized decoupled algorithms and favorable to other related problem reformulation techniques.

ICAPS Conference 2023 Conference Paper

Efficient Evaluation of Large Abstractions for Decoupled Search: Merge-and-Shrink and Symbolic Pattern Databases

Daniel Gnad 0001
Silvan Sievers
Álvaro Torralba

Abstraction heuristics are a state-of-the-art technique to solve classical planning problems optimally. A common approach is to precompute many small abstractions and combine them admissibly using cost partitioning. Recent work has shown that this approach does not work out well when using such heuristics for decoupled state space search, where search nodes represent potentially large sets of states. This is due to the fact that admissibly combining the estimates of several heuristics without sacrificing accuracy is NP-hard for decoupled states. In this work we propose to use a single large abstraction instead. We focus on merge-and-shrink and symbolic pattern database heuristics, which are designed to produce such abstractions. For these heuristics, we prove that the evaluation of decoupled states is NP-hard in general, but we also identify conditions under which it is polynomial. We introduce algorithms for both the general and the polynomial case. Our experimental evaluation shows that single large abstraction heuristics lead to strong performance when the heuristic evaluation is polynomial.

ICAPS Conference 2023 Conference Paper

Finding Matrix Multiplication Algorithms with Classical Planning

David Speck 0001
Paul Höft
Daniel Gnad 0001
Jendrik Seipp

Matrix multiplication is a fundamental operation of linear algebra, with applications ranging from quantum physics to artificial intelligence. Given its importance, enormous resources have been invested in the search for faster matrix multiplication algorithms. Recently, this search has been cast as a single-player game. By learning how to play this game efficiently, the newly-introduced AlphaTensor reinforcement learning agent is able to discover many new faster algorithms. In this paper, we show that finding matrix multiplication algorithms can also be cast as a classical planning problem. Based on this observation, we introduce a challenging benchmark suite for classical planning and evaluate state-of-the-art planning techniques on it. We analyze the strengths and limitations of different planning approaches in this domain and show that we can use classical planning to find lower bounds and concrete algorithms for matrix multiplication.

ICAPS Conference 2023 Conference Paper

Planning over Integers: Compilations and Undecidability

Daniel Gnad 0001
Malte Helmert
Peter Jonsson
Alexander Shleyfman

Restricted Tasks (RT) are a special case of numeric planning characterized by numeric conditions that involve one numeric variable per formula and numeric effects that allow only the addition of constants. Despite this, RTs form an expressive class whose planning problem is undecidable. The restricted nature of RTs often makes problem modeling awkward and unnecessarily complicated. We show that this can be alleviated by compiling mathematical operations that are not natively supported into RTs using macro-like action sequences. With that, we can encode many features found in general numeric planning such as constant multiplication, addition of linear formulas, and integer division and residue. We demonstrate how our compilations can be used to capture challenging mathematical problems such as the (in)famous Collatz conjecture. Our approach additionally gives a simple undecidability proof for RTs, and the proof shows that the number of variables needed to construct an undecidable class of RTs is surprisingly low: two numeric and one propositional variable.

SoCS Conference 2022 Conference Paper

Additive Pattern Databases for Decoupled Search

Silvan Sievers
Daniel Gnad 0001
Álvaro Torralba

Abstraction heuristics are the state of the art in optimal classical planning as heuristic search. Despite their success for explicit-state search, though, abstraction heuristics are not available for decoupled state-space search, an orthogonal reduction technique that can lead to exponential savings by decomposing planning tasks. In this paper, we show how to compute pattern database (PDB) heuristics for decoupled states. The main challenge lies in how to additively employ multiple patterns, which is crucial for strong search guidance of the heuristics. We show that in the general case, for arbitrary collections of PDBs, computing the heuristic for a decoupled state is exponential in the number of leaf components of decoupled search. We derive several variants of decoupled PDB heuristics that allow to additively combine PDBs avoiding this blow-up and evaluate them empirically.

ICAPS Conference 2022 Conference Paper

Beyond Stars - Generalized Topologies for Decoupled Search

Daniel Gnad 0001
Álvaro Torralba
Daniel Fiser

Decoupled search decomposes a classical planning task by partitioning its variables such that the dependencies between the resulting factors form a star topology. In this topology, a single center factor can interact arbitrarily with a set of leaf factors. The leaves, however, can interact with each other only indirectly via the center. In this work, we generalize this structural requirement and allow arbitrary topologies. The components must not overlap, i. e. , each state variable is assigned to exactly one factor, but the interaction between factors is not restricted. We show how this generalization is connected to star topologies, which implies the correctness of decoupled search with this novel type of decomposition. We introduce factoring methods that automatically identify these topologies on a given planning task. Empirically, the generalized factorings lead to increased applicability of decoupled search on standard IPC benchmarks, as well as to superior performance compared to known factoring methods.

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

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

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.

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.