Gregor Behnke
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Gregor Behnke has a total of 29 co-authors. Here are the top co-authors by number of shared publications:
- Pascal Bercher
School of Computing, The Australian National University
4 shared publications - Daniel Höller
Saarland University, Saarland Informatics Campus
2 shared publications - P. Maurice Dekker
University of Amsterdam
2 shared publications - Pascal Bachor
University of Freiburg
2 shared publications - Roman Barták
Charles University
2 shared publications - Simona Ondrčková
Charles University
2 shared publications
Latest Publications
- Open Access
- 27 November 2025
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 437, 233-250
Comparing State-Representations for DEL Model Checking
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 PSPACEcomplete, 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.
- 27 November 2025
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 437, 233-250
Open AccessComparing State-Representations for DEL Model Checking
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 PSPACEcomplete, 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.
- Open Access
- 16 September 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the International Conference on Automated Planning and Scheduling
- Vol. 35 (1) , 11-20
Is This Plan Necessarily Redundant? On the Computational Complexity of Unobserved Domain Learning
Domain learning is the task of inferring actions' preconditions and effects (domains) from executed sequences of actions (plans) along with a varying detail of information about the corresponding world states. Remarkably, even if the state remains completely unobserved, as in this work, we can infer the existence of certain state features if we assume that the plans we learn from are non-redundant. Moreover, plans might be redundant regardless of the underlying domain. We study the computational complexity of deciding whether there exists a domain in which a given plan is justified in the sense that either no single action (well-justification) or no set of actions (perfect justification) can be removed without violating correctness of the plan. We allow either arbitrarily large domains or domains with a polynomial bound on the number of state variables. We show that the problem is in P for well-justified plans and arbitrary domains, NP-complete for well-justified plans and bounded domains, in coNP for perfectly justified plans and arbitrary domains, and in Σ₂ for perfectly justified plans and bounded domains.
- 16 September 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the International Conference on Automated Planning and Scheduling
- Vol. 35 (1) , 11-20
Open AccessIs This Plan Necessarily Redundant? On the Computational Complexity of Unobserved Domain Learning
Domain learning is the task of inferring actions' preconditions and effects (domains) from executed sequences of actions (plans) along with a varying detail of information about the corresponding world states. Remarkably, even if the state remains completely unobserved, as in this work, we can infer the existence of certain state features if we assume that the plans we learn from are non-redundant. Moreover, plans might be redundant regardless of the underlying domain. We study the computational complexity of deciding whether there exists a domain in which a given plan is justified in the sense that either no single action (well-justification) or no set of actions (perfect justification) can be removed without violating correctness of the plan. We allow either arbitrarily large domains or domains with a polynomial bound on the number of state variables. We show that the problem is in P for well-justified plans and arbitrary domains, NP-complete for well-justified plans and bounded domains, in coNP for perfectly justified plans and arbitrary domains, and in Σ₂ for perfectly justified plans and bounded domains.
- Open Access
- 16 September 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the International Conference on Automated Planning and Scheduling
- Vol. 35 (1) , 45-53
Hardness of Chosen Length Planning Games and Regular Fixed Methods FOND HTN Planning
We introduce a new version of general game-playing in which one of the players chooses the length of the game up front. Consider a classical planning problem and two players who take turns applying actions. Player 1 wins iff the goal is true after a predetermined number of moves has been made. Is there a number r such that player 1 has a winning strategy for the game of length r? We show that this problem is EXPSPACE-complete. Moreover, we show that the problem is equivalent to the plan existence problem for a class of fully observable non-deterministic hierarchical task network planning problems under the solution concept with fixed methods, which was introduced in prior work. This class consists of all regular loop-unrolling problems, where a problem is loop-unrolling if it has at most one compound task name and at most two methods. As a corollary, we obtain hardness for regular problems, solving an open problem.
- 16 September 2025
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the International Conference on Automated Planning and Scheduling
- Vol. 35 (1) , 45-53
Open AccessHardness of Chosen Length Planning Games and Regular Fixed Methods FOND HTN Planning
We introduce a new version of general game-playing in which one of the players chooses the length of the game up front. Consider a classical planning problem and two players who take turns applying actions. Player 1 wins iff the goal is true after a predetermined number of moves has been made. Is there a number r such that player 1 has a winning strategy for the game of length r? We show that this problem is EXPSPACE-complete. Moreover, we show that the problem is equivalent to the plan existence problem for a class of fully observable non-deterministic hierarchical task network planning problems under the solution concept with fixed methods, which was introduced in prior work. This class consists of all regular loop-unrolling problems, where a problem is loop-unrolling if it has at most one compound task name and at most two methods. As a corollary, we obtain hardness for regular problems, solving an open problem.
- Open Access
- 16 October 2024
- Published by IOS Press
- p. 4198-4206
Barely Decidable Fragments of Planning
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.
- 16 October 2024
- Published by IOS Press
- p. 4198-4206
Open AccessBarely Decidable Fragments of Planning
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.
- Open Access
On the Computational Complexity of Stackelberg Planning and Meta-Operator Verification: Technical Report
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.
Open AccessOn the Computational Complexity of Stackelberg Planning and Meta-Operator Verification: Technical Report
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.
- Open Access
- 24 March 2024
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 38 (20) , 22661
Symbolic Reasoning Methods for AI Planning
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.
- 24 March 2024
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 38 (20) , 22661
Open AccessSymbolic Reasoning Methods for AI Planning
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.
- Open Access
- 24 March 2024
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 38 (18) , 20028-20035
Learning Planning Domains from Non-redundant Fully-Observed Traces: Theoretical Foundations and Complexity Analysis
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.
- 24 March 2024
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the AAAI Conference on Artificial Intelligence
- Vol. 38 (18) , 20028-20035
Open AccessLearning Planning Domains from Non-redundant Fully-Observed Traces: Theoretical Foundations and Complexity Analysis
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.
- Open Access
- 1 July 2023
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the International Conference on Automated Planning and Scheduling
- Vol. 33 (1) , 42-51
On Partial Satisfaction Planning with Total-Order HTNs
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.
- 1 July 2023
- Published by Association for the Advancement of Artificial Intelligence (AAAI) in Proceedings of the International Conference on Automated Planning and Scheduling
- Vol. 33 (1) , 42-51
Open AccessOn Partial Satisfaction Planning with Total-Order HTNs
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.