Author name cluster

Gregor Behnke

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

TARK Conference 2025 Conference Paper

Comparing State-Representations for DEL Model Checking

Gregor Behnke
Malvin Gattinger
Avijeet Ghosh
Haitian Wang

Model checking with the standard Kripke models used in (Dynamic) Epistemic Logic leads to scalability issues. Hence alternative representations have been developed, in particular symbolic structures based on Binary Decision Diagrams (BDDs) and succinct models based on mental programs. While symbolic structures have been shown to perform well in practice, their theoretical complexity was not known so far. On the other hand, for succinct models model checking is known to be PSPACE-complete, but no implementations are available. We close this gap and directly relate the two representations. We show that model checking DEL on symbolic structures encoded with BDDs is also PSPACE-complete. In fact, already model checking Epistemic Logic without dynamics is PSPACE-complete on symbolic structures. We also provide direct translations between BDDs and mental programs. Both translations yield exponential outputs. For the translation from mental programs to BDDs we show that no small translation exists. For the other direction we conjecture the same.

ECAI Conference 2024 Conference Paper

Barely Decidable Fragments of Planning

Maurice Dekker
Gregor Behnke

Both numeric planning and Hierarchical Task Network (HTN) planning are highly expressive planning formalisms – at the cost of being undecidable in general. For both formalisms, decidable fragments are known. Studying these restricted fragments has lead to valuable insights, which ultimately gave rise to the development of new efficient planning algorithms. We identify new decidable fragments of both numeric and HTN planning. For HTN planning, we introduce the fragments of one-hole-digging, initial, and final problems. The former restrict every task network to have at most one compound task, while the latter two restrict compound tasks to be order-minimal or order-maximal, respectively. For numeric planning, we introduce Positive Numeric Planning (PNP) where the value of numeric variables can only be non-negative. We determine the complexity of these fragments: they are Ackermann-complete – which is significantly more difficult than any prior known decidable fragment, but still barely decidable.

ECAI Conference 2024 Conference Paper

Contributions to the Journal Track

Gregor Behnke

The journal track of the 27th European Conference on Artificial Intelligence (ECAI-2024) offered the authors of papers recently accepted for publication by either one of the two leading discipline-wide journals in AI, Artificial Intelligence (AIJ) and the Journal of Artificial Intelligence Research (JAIR), the opportunity to present their work at the conference without undergoing an additional round of reviewing. Papers were eligible only if no part had previously been presented at a conference with archival proceedings. Traditionally, the authors of such papers would have missed out on the opportunity to present their work to a broader research audience. This limitation tends to discourage the submission of original work to journals without prior conference publications on the same topic. The intention of the journal track is to encourage a “journal-first” publication strategy–by giving authors the option to present their work at a suitable conference venue such as ECAI. On the following pages, for each paper presented at the journal track, we list bibliographic information and the abstract of the original publication.

AAAI Conference 2024 Conference Paper

Learning Planning Domains from Non-redundant Fully-Observed Traces: Theoretical Foundations and Complexity Analysis

Pascal Bachor
Gregor Behnke

Domain learning is the task of finding an action model that can explain given observed plan executions, so-called traces. It allows us to automate the identification of actions' preconditions and effects instead of relying on hand-modeled expert knowledge. While previous research has put forth various techniques and covers multiple planning formalisms, the theoretical foundations of domain learning are still in their infancy. We investigate the most basic setting, that is grounded classical planning without negative preconditions or conditional effects with full observability of the state variables. The given traces are assumed to be justified in the sense that either no single action or no set of actions can be removed without violating correctness of the plan. Furthermore, we might be given additional constraints in the form of a propositional logical formula. We show the consequences of these assumptions for the computational complexity of identifying a satisfactory planning domain.

PDF Details DOI

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.

AAAI Conference 2024 Conference Paper

Symbolic Reasoning Methods for AI Planning

Gregor Behnke

Planning is the act of deliberative thinking before acting. It is based on a symbolic model of the world and the options to act in it, usually defined in function-free first-order logic. The task is to find a sequence of actions (a plan) that leads from a given current state to a desired goal state. The basic, purely physical description may be augmented with a partially ordered grammar-like structure (a Hierarchical Task Network or HTN), which can describe expert knowledge, or practical, legal, or operational requirements. In this talk, I will survey a variety of methods for automatically deriving plans using symbolic methods for planning -- from both my past and future research. These symbolic methods -- in some sense -- translate planning problems into other, simpler symbolic representations and reason over them to find plans. As a basis for these methods, I will firstly introduce relevant theoretical results on planning. First, I will discuss the expressive power of planning formalisms (ECAI'14, ICAPS'16) and second, the computational complexity of HTN planning and related tasks such as HTN plan verification, plan modification, and plan recognition (ICAPS'15, ICAPS'16). Based on these theoretical results, I will develop why SAT-based HTN planning is possible and how it can be implemented. To this end, I will survey several of my publications at top-tier conferences, including papers at ICAPS'17, AAAI'18, AAAI'19, IJCAI'19, AAAI'20, and ICAPS'21 -- in which I developed an highly SAT-based planner for HTN problems including the ability to find optimal plans as well as the grounding as a preprocessing step. Here I will also give an outlook on future developments and new ideas that I propose for SAT-based planning -- including the exploitation of structures in plan (e.g.\ landmarks or operator-counting constraints). Next, I will present the idea of expressing lifted classical planning as SAT (ICAPS'22). The resulting planner LiSAT was the first lifted SAT-based planner -- and proved highly efficient and outperformed all other lifted planners at the time of publication. Notably, LiSAT was the first planner (lifted or grounded) and still is the only one to solve the challenging OrganicSynthesis benchmark -- and could even prove optimality for all plans. I will also outline future ideas to further improve the efficiency of LiSAT. Lastly, I introduce the notion of planning with symbolic symbolic representations (AAAI'21 and ICAPS'23). Here one uses Binary Decision Diagrams to encode large sets of states efficiently. For expressing the additional structure encoded by HTNs, I show how BDDs can be suitably integrated into finite automata. Based on this representation, an efficient and optimal planning algorithm can be derived. Additionally, I show how this algorithm can be extended to also cover oversubscription planning.

PDF Details DOI

ECAI Conference 2023 Conference Paper

Accelerating SAT-Based HTN Plan Verification by Exploiting Data Structures from HTN Planning

Songtuan Lin
Gregor Behnke
Pascal Bercher

Plan verification is the task of deciding whether a given plan is a solution to a planning problem. In this paper, we study the plan verification problem in the context of Hierarchical Task Network (HTN) planning, which has been proved to be NP-complete when partial order (PO) is involved. We will develop a novel SAT-based approach exploiting the data structures solution order graphs and path decomposition trees which encodes an HTN plan verification problem as a SAT one. We show in our experiments that this new approach outperforms the current state-of-the-art (SOTA) planning-based approach for verifying plans for POHTN problems.

ICAPS Conference 2023 Conference Paper

On Partial Satisfaction Planning with Total-Order HTNs

Gregor Behnke
David Speck 0001
Michael Katz 0001
Shirin Sohrabi

Since its introduction, partial satisfaction planning (PSP), including both oversubscription (OSP) and net-benefit, has received significant attention in the classical planning community. However, hierarchical aspects have been mostly ignored in this context, although several problem domains that form the main motivation for PSP, such as the rover domain, have an inherent hierarchical structure. In this paper, we are taking the necessary steps for facilitating this research direction. First, we formally define hierarchical partial satisfaction planning problems and discuss the usefulness and necessity of this formalism. Second, we present a carefully structured set of benchmarks consisting of OSP and net-benefit problems with hierarchical structure. We describe and analyze the different domains of the benchmark set and the desiderata that are met to provide an interesting and challenging starting point for upcoming research. Third, we introduce various planning techniques that can solve hierarchical OSP problems and investigate their empirical behaviour on our proposed benchmark.

AAAI Conference 2023 Conference Paper

On Total-Order HTN Plan Verification with Method Preconditions – An Extension of the CYK Parsing Algorithm

Songtuan Lin
Gregor Behnke
Simona Ondrčková
Roman Barták
Pascal Bercher

In this paper, we consider the plan verification problem for totally ordered (TO) HTN planning. The problem is proved to be solvable in polynomial time by recognizing its connection to the membership decision problem for context-free grammars. Currently, most HTN plan verification approaches do not have special treatments for the TO configuration, and the only one features such an optimization still relies on an exhaustive search. Hence, we will develop a new TOHTN plan verification approach in this paper by extending the standard CYK parsing algorithm which acts as the best decision procedure in general.

PDF Details DOI

ICAPS Conference 2022 Conference Paper

Compiling HTN Plan Verification Problems into HTN Planning Problems

Daniel Höller
Julia Wichlacz
Pascal Bercher
Gregor Behnke

Plan Verification is the task of deciding whether a sequence of actions is a solution for a given planning problem. In HTN planning, the task is computationally expensive and may be up to NP-hard. However, there are situations where it needs to be solved, e. g. when a solution is post-processed, in systems using approximation, or just to validate whether a planning system works correctly (e. g. for debugging or in a competition). There are verification systems based on translations to propositional logic and on techniques from parsing. Here we present a third approach and translate HTN plan verification problems into HTN planning problems. These can be solved using any HTN planning system. We collected a new benchmark set based on models and results of the 2020 International Planning Competition. Our evaluation shows that our compilation outperforms the approaches from the literature.

ICAPS Conference 2022 Conference Paper

Encoding Lifted Classical Planning in Propositional Logic

Daniel Höller
Gregor Behnke

Planning models are usually defined in lifted, i. e. first order formalisms, while most solvers need (variable-free) grounded representations. Though techniques for grounding prune unnecessary parts of the model, grounding might – nevertheless – be prohibitively expensive in terms of runtime. To overcome this issue, there has been renewed interest in solving planning problems based on the lifted representation in the last years. While these approaches are based on (heuristic) search, we present an encoding of lifted classical planning in propositional logic and use SAT solvers to solve it. Our evaluation shows that our approach is competitive with the heuristic search-based approaches in satisficing planning and outperforms them in a (length-)optimal setting.

AAAI Conference 2022 Conference Paper

Making Translations to Classical Planning Competitive with Other HTN Planners

Gregor Behnke
Florian Pollitt
Daniel Höller
Pascal Bercher
Ron Alford

Translation-based approaches to planning allow for solving problems in complex and expressive formalisms via the means of highly efficient solvers for simpler formalisms. To be effective, these translations have to be constructed appropriately. The current existing translation of the highly expressive formalism of HTN planning into the more simple formalism of classical planning is not on par with the performance of current dedicated HTN planners. With our contributions in this paper, we close this gap: we describe new versions of the translation that reach the performance of state-of-the-art dedicated HTN planners. We present new translation techniques both for the special case of totally-ordered HTNs as well as for the general partially-ordered case. In the latter, we show that our new translation generates only linearly many actions, while the previous encoding generates and exponential number of actions.

ICAPS Conference 2021 Conference Paper

Block Compression and Invariant Pruning for SAT-based Totally-Ordered HTN Planning

Gregor Behnke

Translations into propositional logic are currently one of the most efficient techniques for solving Totally-Ordered HTN planning problems. The two current encodings both iterate over the maximum allowed depth of decomposition. Given this depth, they compute a tree that represents all possible decompositions up to this depth. Based on this tree, a formula in propositional logic is created. We show that much of the computed tree is actually useless as it cannot possibly belong to a solution. We provide a technique for removing (parts of) these useless structures using state invariants. We further show that is often not necessary to encode all leafs of this tree as separate timesteps, as the prior encodings did. Instead, we can compress the leafs into blocks and encode all leafs of a block at one timestep. We show that these changes provide an improvement over the state-of-the-art in HTN planning.

KR Conference 2021 Conference Paper

Correcting Hierarchical Plans by Action Deletion

Roman Barták
Simona Ondrčková
Gregor Behnke
Pascal Bercher

Hierarchical task network (HTN) planning is a model-based approach to planning. The HTN domain model consists of tasks and methods to decompose them into subtasks until obtaining primitive tasks (actions). There are recent methods for verifying if a given action sequence is a valid HTN plan. However, if the plan is invalid, all existing verification methods only say so without explaining why the plan is invalid. In the paper, we propose a method that corrects a given action sequence to form a valid HTN plan by deleting the minimal number of actions. This plan correction explains what is wrong with a given action sequence concerning the HTN domain model.

PDF Details DOI

ICAPS Conference 2021 Conference Paper

Loop Detection in the PANDA Planning System

Daniel Höller
Gregor Behnke

The International Planning Competition (IPC) in 2020 was the first one for a long time to host tracks on Hierarchical Task Network (HTN) planning. HyperTensioN, the winner of the tack on totally-ordered problems, comes with an interesting technique: it stores parts of the decomposition path in the state to mark expanded tasks and forces its depth first search to leave recursive structures in the hierarchy. This can be seen as a form of loop detection (LD) – a technique that is not very common in HTN planning. This might be due to the spirit of encoding enough advice in the model to find plans (so that loop detection is simply not necessary), or because it becomes a computationally hard task in the general (i. e. partially-ordered) setting. We integrated several approximate and exact techniques for LD into the progression search of the HTN planner PANDA. We test our techniques on the benchmark set of the IPC 2020. Both in the partial ordered and total ordered track, PANDA with LD performs better than the respective winner of the competition.

AAAI Conference 2021 Conference Paper

Symbolic Search for Optimal Total-Order HTN Planning

Gregor Behnke
David Speck

Symbolic search has proven to be a useful approach to optimal classical planning. In Hierarchical Task Network (HTN) planning, however, there is little work on optimal planning. One reason for this is that in HTN planning, most algorithms are based on heuristic search, and admissible heuristics have to incorporate the structure of the task network in order to be informative. In this paper, we present a novel approach to optimal (totally-ordered) HTN planning, which is based on symbolic search. An empirical analysis shows that our symbolic approach outperforms the current state of the art for optimal totally-ordered HTN planning.

IJCAI Conference 2020 Conference Paper

Delete- and Ordering-Relaxation Heuristics for HTN Planning

Daniel Höller
Pascal Bercher
Gregor Behnke

In HTN planning, the hierarchy has a wide impact on solutions. First, there is (usually) no state-based goal given, the objective is given via the hierarchy. Second, it enforces actions to be in a plan. Third, planners are not allowed to add actions apart from those introduced via decomposition, i. e. via the hierarchy. However, no heuristic considers the interplay of hierarchy and actions in the plan exactly (without relaxation) because this makes heuristic calculation NP-hard even under delete relaxation. We introduce the problem class of delete- and ordering-free HTN planning as basis for novel HTN heuristics and show that its plan existence problem is still NP-complete. We then introduce heuristics based on the new class using an integer programming model to solve it.

PDF Details DOI

AAAI Conference 2020 Conference Paper

HDDL: An Extension to PDDL for Expressing Hierarchical Planning Problems

Daniel Höller
Gregor Behnke
Pascal Bercher
Susanne Biundo
Humbert Fiorino
Damien Pellier
Ron Alford

The research in hierarchical planning has made considerable progress in the last few years. Many recent systems do not rely on hand-tailored advice anymore to ﬁnd solutions, but are supposed to be domain-independent systems that come with sophisticated solving techniques. In principle, this development would make the comparison between systems easier (because the domains are not tailored to a single system anymore) and – much more important – also the integration into other systems, because the modeling process is less tedious (due to the lack of advice) and there is no (or less) commitment to a certain planning system the model is created for. However, these advantages are destroyed by the lack of a common input language and feature set supported by the different systems. In this paper, we propose an extension to PDDL, the description language used in non-hierarchical planning, to the needs of hierarchical planning systems.

JAIR Journal 2020 Journal Article

HTN Planning as Heuristic Progression Search

Daniel Höller
Pascal Bercher
Gregor Behnke
Susanne Biundo

The majority of search-based HTN planning systems can be divided into those searching a space of partial plans (a plan space) and those performing progression search, i.e., that build the solution in a forward manner. So far, all HTN planners that guide the search by using heuristic functions are based on plan space search. Those systems represent the set of search nodes more effectively by maintaining a partial ordering between tasks, but they have only limited information about the current state during search. In this article, we propose the use of progression search as basis for heuristic HTN planning systems. Such systems can calculate their heuristics incorporating the current state, because it is tracked during search. Our contribution is the following: We introduce two novel progression algorithms that avoid unnecessary branching when the problem at hand is partially ordered and show that both are sound and complete. We show that defining systematicity is problematic for search in HTN planning, propose a definition, and show that it is fulfilled by one of our algorithms. Then, we introduce a method to apply arbitrary classical planning heuristics to guide the search in HTN planning. It relaxes the HTN planning model to a classical model that is only used for calculating heuristics. It is updated during search and used to create heuristic values that are used to guide the HTN search. We show that it can be used to create HTN heuristics with interesting theoretical properties like safety, goal-awareness, and admissibility. Our empirical evaluation shows that the resulting system outperforms the state of the art in search-based HTN planning.

PDF Details DOI

ICAPS Conference 2020 Conference Paper

New Developments for Robert - Assisting Novice Users Even Better in DIY Projects

Gregor Behnke
Pascal Bercher
Matthias Kraus 0001
Marvin R. G. Schiller
Kristof Mickeleit
Timo Häge
Michael Dorna
Michael Dambier

Do-It-Yourself (DIY) home improvement projects require a combination of specific knowledge and practical abilities. Novice users often lack both and thus tend to fail or be frightful of performing DIY projects – even though they would like to. By providing suitable and individualised assistance in the form of step-by-step instructions, the assistant Robert allows even novice users to successfully complete their DIY projects. Simultaneously, Robert allows its users to learn how to perform these steps themselves and thus enables them to become more independent in the future. In this paper, we report on the latest progress with Robert. Compared to earlier versions, Robert is now able to adaptively change its instructions based on the wishes and preferences of the user. Further, Robert is now able to use connected tools – i. e. tools that are able to sense and communicate their status – to check whether the user is performing the project's steps correctly and to provide further assistance in the case of failure. Lastly, we present the results of an empirical study conducted to show Robert's effectiveness.

AAAI Conference 2020 Conference Paper

On Succinct Groundings of HTN Planning Problems

Gregor Behnke
Daniel Höller
Alexander Schmid
Pascal Bercher
Susanne Biundo

Both search-based and translation-based planning systems usually operate on grounded representations of the problem. Planning models, however, are commonly deﬁned using lifted description languages. Thus, planning systems usually generate a grounded representation of the lifted model as a preprocessing step. For HTN planning models, only one method to ground lifted models has been published so far. In this paper we present a new approach for grounding HTN planning problems that produces smaller groundings in a shorter timespan than the previously published method.

AAAI Conference 2019 Conference Paper

Bringing Order to Chaos – A Compact Representation of Partial Order in SAT-Based HTN Planning

Gregor Behnke
Daniel Höller
Susanne Biundo

HTN planning provides an expressive formalism to model complex application domains. It has been widely used in realworld applications. However, the development of domainindependent planning techniques for such models is still lacking behind. The need to be informed about both statetransitions and the task hierarchy makes the realisation of search-based approaches difficult, especially with unrestricted partial ordering of tasks in HTN domains. Recently, a translation of HTN planning problems into propositional logic has shown promising empirical results. Such planners benefit from a unified representation of state and hierarchy, but until now require very large formulae to represent partial order. In this paper, we introduce a novel encoding of HTN Planning as SAT. In contrast to related work, most of the reasoning on ordering relations is not left to the SAT solver, but done beforehand. This results in much smaller formulae and, as shown in our evaluation, in a planner that outperforms previous SAT-based approaches as well as the state-of-the-art in search-based HTN planning.

IJCAI Conference 2019 Conference Paper

Finding Optimal Solutions in HTN Planning - A SAT-based Approach

Gregor Behnke
Daniel Höller
Susanne Biundo

Over the last years, several new approaches to Hierarchical Task Network (HTN) planning have been proposed that increased the overall performance of HTN planners. However, the focus has been on agile planning - on finding a solution as quickly as possible. Little work has been done on finding optimal plans. We show how the currently best-performing approach to HTN planning - the translation into propositional logic - can be utilised to find optimal plans. Such SAT-based planners usually bound the HTN problem to a certain depth of decomposition and then translate the problem into a propositional formula. To generate optimal plans, the length of the solution has to be bounded instead of the decomposition depth. We show the relationship between these bounds and how it can be handled algorithmically. Based on this, we propose an optimal SAT-based HTN planner and show that it performs favourably on a benchmark set.

IJCAI Conference 2019 Conference Paper

On Guiding Search in HTN Planning with Classical Planning Heuristics

Daniel Höller
Pascal Bercher
Gregor Behnke
Susanne Biundo

Planning is the task of finding a sequence of actions that achieves the goal(s) of an agent. It is solved based on a model describing the environment and how to change it. There are several approaches to solve planning tasks, two of the most popular are classical planning and hierarchical planning. Solvers are often based on heuristic search, but especially regarding domain-independent heuristics, techniques in classical planning are more sophisticated. However, due to the different problem classes, it is difficult to use them in hierarchical planning. In this paper we describe how to use arbitrary classical heuristics in hierarchical planning and show that the resulting system outperforms the state of the art in hierarchical planning.

ICAPS Conference 2018 Conference Paper

A Generic Method to Guide HTN Progression Search with Classical Heuristics

Daniel Höller
Pascal Bercher
Gregor Behnke
Susanne Biundo

HTN planning combines actions that cause state transition with grammar-like decomposition of compound tasks that additionally restricts the structure of solutions. There are mainly two strategies to solve such planning problems: decomposition-based search in a plan space and progression-based search in a state space. Existing progression-based systems do either not rely on heuristics (e. g. SHOP2) or calculate their heuristics based on extended or modified models (e. g. GoDeL). Current heuristic planners for standard HTN models (e. g. PANDA) use decomposition-based search. Such systems represent search nodes more compactly due to maintaining a partial order between tasks, but they have no current state at hand during search. This makes the design of heuristics difficult. In this paper we present a progression-based heuristic HTN planning system: We (1) provide an improved progression algorithm, prove its correctness, and empirically show its efficiency gain; and (2) present an approach that allows to use arbitrary classical (non-hierarchical) heuristics in HTN planning. Our empirical evaluation shows that the resulting system outperforms the state-of-the-art in HTN planning.

IJCAI Conference 2018 Conference Paper

Instructing Novice Users on How to Use Tools in DIY Projects

Gregor Behnke
Marvin Schiller
Matthias Kraus
Pascal Bercher
Mario Schmautz
Michael Dorna
Wolfgang Minker
Birte Glimm

Novice users require assistance when performing handicraft tasks. Adequate instruction ensures task completion and conveys knowledge and abilities required to perform the task. We present an assistant teaching novice users how to operate electronic tools, such as drills, saws, and sanders, in the context of Do-It-Yourself (DIY) home improvement projects. First, the actions that need to be performed for the project are determined by a planner. Second, a dialogue manager capable of natural language interaction presents these actions as instructions to the user. Third, questions on these actions and involved objects are answered by generating appropriate ontology-based explanations.

AAAI Conference 2018 Conference Paper

totSAT – Totally-Ordered Hierarchical Planning Through SAT

Gregor Behnke
Daniel Höller
Susanne Biundo

In this paper, we propose a novel SAT-based planning approach for hierarchical planning by introducing the SATbased planner totSAT for the class of totally-ordered HTN planning problems. We use the same general approach as SAT planning for classical planning does: bound the problem, translate the problem into a formula, and if the formula is not satisﬁable, increase the bound. In HTN planning, a suitable bound is the maximum depth of decomposition. We show how totally-ordered HTN planning problems can be translated into a SAT formula, given this bound. Furthermore, we have conducted an extensive empirical evaluation to compare our new planner against state-of-the-art HTN planners. It shows that our technique outperforms any of these systems.

IJCAI Conference 2017 Conference Paper

An Admissible HTN Planning Heuristic

Pascal Bercher
Gregor Behnke
Daniel Höller
Susanne Biundo

Hierarchical task network (HTN) planning is well-known for being an efficient planning approach. This is mainly due to the success of the HTN planning system SHOP2. However, its performance depends on hand-designed search control knowledge. At the time being, there are only very few domain-independent heuristics, which are designed for differing hierarchical planning formalisms. Here, we propose an admissible heuristic for standard HTN planning, which allows to find optimal solutions heuristically. It bases upon the so-called task decomposition graph (TDG), a data structure reflecting reachable parts of the task hierarchy. We show (both in theory and empirically) that rebuilding it during planning can improve heuristic accuracy thereby decreasing the explored search space. The evaluation further studies the heuristic both in terms of plan quality and coverage.

ICAPS Conference 2017 Conference Paper

This Is a Solution! (. .. But Is It Though?) - Verifying Solutions of Hierarchical Planning Problems

Gregor Behnke
Daniel Höller
Susanne Biundo

Plan-Verification is the task of determining whether a plan is a solution to a given planning problem. Any plan verifier has, apart from showing that verifying plans is possible in practice, a wide range of possible applications. These include mixed-initiative planning, where a user is integrated into the planning process, and local search, e. g. , for post-optimising plans or for plan repair. In addition to its practical interest, plan verification is also a problem worth investigating for theoretical reasons. Recent work showed plan verification for hierarchical planning problems to be NP-complete, as opposed to classical planning where it is in P. As such, plan verification for hierarchical planning problem was — until now — not possible. We describe the first plan verifier for hierarchical planning. It uses a translation of the problem into a SAT formula. Further we conduct an empirical evaluation, showing that the correct output is produced within acceptable time.

ICAPS Conference 2016 Conference Paper

Assessing the Expressivity of Planning Formalisms through the Comparison to Formal Languages

Daniel Höller
Gregor Behnke
Pascal Bercher
Susanne Biundo

From a theoretical perspective, judging the expressivity of planning formalisms helps to understand the relationship of different representations and to infer theoretical properties. From a practical point of view, it is important to be able to choose the best formalism for a problem at hand, or to ponder the consequences of introducing new representation features. Most work on the expressivity is based either on compilation approaches, or on the computational complexity of the plan existence problem. Recently, we introduced a new notion of expressivity. It is based on comparing the structural complexity of the set of solutions to a planning problem by interpreting the set as a formal language and classifying it with respect to the Chomsky hierarchy. This is a more direct measure than the plan existence problem and enables also the comparison of formalisms that can not be compiled into each other. While existing work on that last approach focused on different hierarchical problem classes, this paper investigates STRIPS with and without conditional effects; though we also tighten some existing results on hierarchical formalisms. Our second contribution is a discussion on the language-based expressivity measure with respect to the other approaches.

ICAPS Conference 2016 Conference Paper

Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems

Ron Alford
Gregor Behnke
Daniel Höller
Pascal Bercher
Susanne Biundo
David W. Aha

Hierarchical Task Network (HTN) planning is a formalism that can express constraints which cannot easily be expressed by classical (non-hierarchical) planning approaches. It enables reasoning about procedural structures and domain-specific search control knowledge. Yet the cornucopia of modern heuristic search techniques remains largely unincorporated in current HTN planners, in part because it is not clear how to estimate the goal distance for a partially-ordered task network. When using SHOP2-style progression, a task network of yet unprocessed tasks is maintained during search. In the general case it can grow arbitrarily large. However, many — if not most — existing HTN domains have a certain structure (called tail-recursive) where the network's size is bounded. We show how this bound can be calculated and exploited to automatically translate tail-recursive HTN problems into non-hierarchical STRIPS representations, which allows using both hierarchical structures and classical planning heuristics. In principle, the approach can also be applied to non-tail-recursive HTNs by incrementally increasing the bound. We give three translations with different advantages and present the results of an empirical evaluation with several HTN domains that are translated to PDDL and solved by two current classical planning systems. Our results show that we can automatically find practical bounds for solving partially-ordered HTN problems. We also show that classical planners perform similarly with our automatic translations versus a previous hand-bounded HTN translation which is restricted to totally-ordered problems.

ICAPS Conference 2016 Conference Paper

Change the Plan - How Hard Can That Be?

Gregor Behnke
Daniel Höller
Pascal Bercher
Susanne Biundo

Interaction with users is a key capability of planning systems that are applied in real-world settings. Such a system has to be able to react appropriately to requests issued by its users. Most of these systems are based on a generated plan that is continually criticised by him, resulting in a mixed-initiative planning system. We present several practically relevant requests to change a plan in the setting of hierarchical task network planning and investigate their computational complexity. On the one hand, these results provide guidelines when constructing algorithms to execute the respective requests, but also provide translations to other well-known planning queries like plan existence or verification. These can be employed to extend an existing planner such that it can form the foundation of a mixed-initiative planning system simply by adding a translation layer on top.

ECAI Conference 2016 Conference Paper

More than a Name? On Implications of Preconditions and Effects of Compound HTN Planning Tasks

Pascal Bercher
Daniel Höller
Gregor Behnke
Susanne Biundo

There are several formalizations for hierarchical planning. Many of them allow to specify preconditions and effects for compound tasks. They can be used, e. g. , to assist during the modeling process by ensuring that the decomposition methods' plans "implement" the compound tasks' intended meaning. This is done based on so-called legality criteria that relate these preconditions and effects to the method's plans and pose further restrictions. Despite the variety of expressive hierarchical planning formalisms, most theoretical investigations are only known for standard HTN planning, where compound tasks are just names, i. e. , no preconditions or effects can be specified. Thus, up to know, a direct comparison to other hierarchical planning formalisms is hardly possible and fundamental theoretical properties are yet unknown. To enable a better comparison between such formalisms (in particular with respect to their computational expressivity), we first provide a survey on the different legality criteria known from the literature. Then, we investigate the theoretical impact of these criteria for two fundamental problems to planning: plan verification and plan existence. We prove that the plan verification problem is at most NP-complete, while the plan existence problem is in the general case both semi-decidable and undecidable, independent of the demanded criteria. Finally, we discuss our theoretical findings and practical implications.

AAAI Conference 2015 Conference Paper

A Planning-Based Assistance System for Setting Up a Home Theater

Pascal Bercher
Felix Richter
Thilo Hörnle
Thomas Geier
Daniel Höller
Gregor Behnke
Florian Nothdurft
Frank Honold

Modern technical devices are often too complex for many users to be able to use them to their full extent. Based on planning technology, we are able to provide advanced user assistance for operating technical devices. We present a system that assists a human user in setting up a complex home theater consisting of several HiFi devices. For a human user, the task is rather challenging due to a large number of different ports of the devices and the variety of available cables. The system supports the user by giving detailed instructions how to assemble the theater. Its performance is based on advanced user-centered planning capabilities including the generation, repair, and explanation of plans.

IJCAI Conference 2015 Conference Paper

Coherence Across Components in Cognitive Systems - One Ontology to Rule Them All

Gregor Behnke
Denis Ponomaryov
Marvin Schiller
Pascal Bercher
Florian Nothdurft
Birte Glimm
Susanne Biundo

The integration of the various specialized components of cognitive systems poses a challenge, in particular for those architectures that combine planning, inference, and human-computer interaction (HCI). An approach is presented that exploits a single source of common knowledge contained in an ontology. Based upon the knowledge contained in it, specialized domain models for the cognitive systems’ components can be generated automatically. Our integration targets planning in the form of hierarchical planning, being well-suited for HCI as it mimics planning done by humans. We show how the hierarchical structures of such planning domains can be (partially) inferred from declarative background knowledge. The same ontology furnishes the structure of the interaction between the cognitive system and the user. First, explanations of plans presented to users are enhanced by ontology explanations. Second, a dialog domain is created from the ontology coherent with the planning domain. We demonstrate the application of our technique in a fitness training scenario.

ICAPS Conference 2015 Conference Paper

On the Complexity of HTN Plan Verification and Its Implications for Plan Recognition

Gregor Behnke
Daniel Höller
Susanne Biundo

In classical planning it is easy to verify if a given sequence of actions is a solution to a planning problem. It has to be checked whether the actions are applicable in the given order and if a goal state is reached after executing them. In this paper we show that verifying whether a plan is a solution to an HTN planning problem is much harder. More specifically, we prove that this problem is NP-complete, even for very simple HTN planning problems. Furthermore, this problem remains NP-complete if an executable sequence of tasks is already provided. HTN-like hierarchical structures are commonly used to represent plan libraries in plan and goal recognition. By applying our result to plan and goal recognition we provide insight into its complexity.

ECAI Conference 2014 Conference Paper

Language Classification of Hierarchical Planning Problems

Daniel Höller
Gregor Behnke
Pascal Bercher
Susanne Biundo

Theoretical results on HTN planning are mostly related to the plan existence problem. In this paper, we study the structure of the generated plans in terms of the language they produce. We show that such languages are always context-sensitive. Furthermore we identify certain subclasses of HTN planning problems which generate either regular or context-free languages. Most importantly we have discovered that HTN planning problems, where preconditions and effects are omitted, constitute a new class of languages that lies strictly between the context-free and context-sensitive languages.