@InProceedings{Bercher2025ModelRepair,
  author    = {Pascal Bercher and Sarath Sreedharan and Mauro Vallati},
  booktitle = {Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI 2025)},
  title     = {A Survey on Model Repair in AI Planning},
  year      = {2025},
  publisher = {IJCAI},
  abstract  = {Accurate planning models are a prerequisite for the appropriate functioning of AI planning applications. Creating these models is however a tedious and error-prone task -- even for planning experts, which makes the provision of automated modeling support essential. In this work, we differentiate between approaches that learn models from scratch (called domain model acquisition) and those that repair flawed or incomplete ones. We survey approaches for the latter, including those that can be used for domain repair but have been developed for other applications, discuss possible optimization metrics (i.e., which repaired model to aim at), and conclude with lines of research we believe deserves more attention.},
  keywords  = {conference,DECRA},
  url_Paper = {https://bercher.net/publications/2025/Bercher2025ModelRepairSurvey.pdf}
}

Accurate planning models are a prerequisite for the appropriate functioning of AI planning applications. Creating these models is however a tedious and error-prone task – even for planning experts, which makes the provision of automated modeling support essential. In this work, we differentiate between approaches that learn models from scratch (called domain model acquisition) and those that repair flawed or incomplete ones. We survey approaches for the latter, including those that can be used for domain repair but have been developed for other applications, discuss possible optimization metrics (i.e., which repaired model to aim at), and conclude with lines of research we believe deserves more attention.

@InProceedings{Zhang2025AckermannRefined,
  author    = {Yifan Zhang and Pascal Bercher},
  booktitle = {Proceedings of the 34th International Joint Conference on Artificial Intelligence (IJCAI 2025)},
  title     = {Computational Complexity of Planning for Recursive Primitive Task Networks: Selective Action Nullification with State Preservation},
  year      = {2025},
  publisher = {IJCAI},
  abstract  = {This paper investigates fundamental aspects of hierarchical task network (HTN) planning by systematically exploring recursive arrangements of primitive task networks. Working within a general framework that aligns with recently identified Ackermann-complete HTN problems, we map the computational complexity across various recursive configurations, revealing a rich complexity landscape. Through a novel proof technique based on selective action nullification with state preservation, we demonstrate that even a highly restricted class of regular HTN problems remains PSPACE-complete, establishing a profound connection to classical planning. We hope these findings contribute to a deeper and broader understanding of the theoretical foundations of HTN planning.},
  keywords  = {conference,DECRA},
  url_Paper = {https://bercher.net/publications/2025/Zhang2025AckermannRefined.pdf}
}

This paper investigates fundamental aspects of hierarchical task network (HTN) planning by systematically exploring recursive arrangements of primitive task networks. Working within a general framework that aligns with recently identified Ackermann-complete HTN problems, we map the computational complexity across various recursive configurations, revealing a rich complexity landscape. Through a novel proof technique based on selective action nullification with state preservation, we demonstrate that even a highly restricted class of regular HTN problems remains PSPACE-complete, establishing a profound connection to classical planning. We hope these findings contribute to a deeper and broader understanding of the theoretical foundations of HTN planning.

@InProceedings{Lauer2025LiftedHTNVerification,
  author    = {Pascal Lauer and Songtuan Lin and Pascal Bercher},
  booktitle = {Proceedings of the 35th International Conference on Automated Planning and Scheduling ({ICAPS 2025})},
  title     = {Tight Bounds for Lifted HTN Plan Verification and Bounded Plan Existence},
  year      = {2025},
  publisher = {AAAI Press},
  abstract  = {Plan verification is a canonical problem within any planning setting, to ensure correctness. This problem is closely linked to the bounded plan existence problem. We analyze the complexity of these problems on lifted representations for Hierarchical Task Network (HTN) Planning. On top of the general analysis, we impose constraints on method orderings and the amount of tasks that methods decompose to. This pinpoints subclasses with lower complexity. Our results confirm the existence of more efficient algorithms when operating on the lifted, instead of grounded, representation.},
  keywords  = {conference,DECRA}
}

Plan verification is a canonical problem within any planning setting, to ensure correctness. This problem is closely linked to the bounded plan existence problem. We analyze the complexity of these problems on lifted representations for Hierarchical Task Network (HTN) Planning. On top of the general analysis, we impose constraints on method orderings and the amount of tasks that methods decompose to. This pinpoints subclasses with lower complexity. Our results confirm the existence of more efficient algorithms when operating on the lifted, instead of grounded, representation.

@InProceedings{Yousefi2025ImperfectAStar,
  author    = {Mohammad Yousefi and Mario Schmautz and Patrik Haslum and Pascal Bercher},
  booktitle = {Proceedings of the 35th International Conference on Automated Planning and Scheduling ({ICAPS 2025})},
  title     = {How Good is Perfect? On the Incompleteness of A* for Total-Order HTN Planning},
  year      = {2025},
  publisher = {AAAI Press},
  abstract  = {This paper highlights a critical limitation in applying A* search to Hierarchical Task Network (HTN) planning -- the predominant approach for solving problems optimally. We demonstrate that A* search is incomplete even in the severely restricted case of totally-ordered problems, and surprisingly, the result holds even when using the perfect heuristic. Nevertheless, we prove that decomposition patterns that lead to incompleteness can be detected prior to search in polynomial-time. We also introduce a mapping that preserves domain semantics while ensuring the completeness of A* in the transformed space. Our evaluation of the International Planning Competition (IPC) 2023 benchmarks reveals the frequency of these problematic conditions in real-world scenarios.},
  keywords  = {conference,DECRA},
  url_Paper = {https://bercher.net/publications/2025/Yousefi2025ImperfectAStar.pdf}
}

This paper highlights a critical limitation in applying A* search to Hierarchical Task Network (HTN) planning – the predominant approach for solving problems optimally. We demonstrate that A* search is incomplete even in the severely restricted case of totally-ordered problems, and surprisingly, the result holds even when using the perfect heuristic. Nevertheless, we prove that decomposition patterns that lead to incompleteness can be detected prior to search in polynomial-time. We also introduce a mapping that preserves domain semantics while ensuring the completeness of A* in the transformed space. Our evaluation of the International Planning Competition (IPC) 2023 benchmarks reveals the frequency of these problematic conditions in real-world scenarios.

@InProceedings{Lin2025CounterExamplePlans,
  author    = {Songtuan Lin and Alban Grastien and Rahul Shome and Pascal Bercher},
  booktitle = {Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI 2025)},
  title     = {Told You That Will Not Work: Optimal Corrections to Planning Domains Using Counter-Example Plans},
  year      = {2025},
  publisher = {AAAI},
  abstract  = {Hardness of modeling a planning domain is a major obstacle for making automated planning techniques accessible. We develop a tool that helps modelers correct domains based on available information such as the known feasibility or infeasibility of certain plans. Designing model repair strategies that are capable of repairing flawed planning domains automatically has been explored in previous work to use positive plans (invalid in the given (flawed) domain but feasible in the “true” domain). In this work, we highlight the importance of and study counter-example negative plans (valid in the given (flawed) domain but infeasible in the “true” domain). Our approach automatically corrects a domain by finding an optimal repair set to the domain which turns all negative plans into non-solutions, in addition to making all positive plans solutions. Experiments indicate strong performance in the fast-downward benchmark suite with random errors. A handcrafted benchmark with domain flaws inspired by some practical applications also motivates the method’s efficacy.},
  keywords  = {conference,DECRA},
  pages     = {26596--26604},
  doi       = {10.1609/aaai.v39i25.34861},
  url_Paper = {https://bercher.net/publications/2025/Lin2025CounterExamplePlans.pdf},
  url_zenodo = {https://zenodo.org/records/14533200}
}

Hardness of modeling a planning domain is a major obstacle for making automated planning techniques accessible. We develop a tool that helps modelers correct domains based on available information such as the known feasibility or infeasibility of certain plans. Designing model repair strategies that are capable of repairing flawed planning domains automatically has been explored in previous work to use positive plans (invalid in the given (flawed) domain but feasible in the “true” domain). In this work, we highlight the importance of and study counter-example negative plans (valid in the given (flawed) domain but infeasible in the “true” domain). Our approach automatically corrects a domain by finding an optimal repair set to the domain which turns all negative plans into non-solutions, in addition to making all positive plans solutions. Experiments indicate strong performance in the fast-downward benchmark suite with random errors. A handcrafted benchmark with domain flaws inspired by some practical applications also motivates the method’s efficacy.

@InProceedings{Olz2024TOILPHeuristic,
  author                    = {Conny Olz and Alexander Lodemann and Pascal Bercher},
  booktitle                 = {Proceedings of the 27th European Conference on Artificial Intelligence (ECAI 2024)},
  title                     = {A Heuristic for Optimal Total-Order HTN Planning Based on Integer Linear Programming},
  year                      = {2024},
  publisher                 = {IOS Press},
  abstract                  = {Heuristic Search is still the most successful approach to hierarchical planning, both for finding any and for finding an optimal solution. Yet, there exist only a very small handful heuristics for HTN planning – so there is still huge potential for improvements. It is especially noteworthy that there does not exist a single heuristic that’s tailored towards special cases. In this work we propose the very first specialized HTN heuristic, tailored towards totally ordered HTN problems. Our heuristic builds on an existing NP-complete and admissible delete-and-ordering relaxation ILP heuristic but partially incorporates ordering constraints while reducing the number of ILP constraints. It exploits inferred preconditions and effects of compound tasks and is also admissible thus allowing to find optimal solutions. Our heuristic proves to be more efficient than the one we improve, dominating it in every domain both in terms of coverage and IPC score. Compared to the current state-of-the art heuristic for optimal HTN planning, our heuristic is less efficient on average, but dominates it in roughly as many cases as it gets dominated by the other, making it a more efficient alternative in several domains.},
  pages                     = {4303--4310},
  doi                       = {10.3233/FAIA241005},
  url_Paper                 = {https://bercher.net/publications/2024/Olz2024bTOILPHeuristic.pdf},
  url_zenodo                = {https://zenodo.org/records/13269291},
  keywords                  = {conference,DECRA}
}

Heuristic Search is still the most successful approach to hierarchical planning, both for finding any and for finding an optimal solution. Yet, there exist only a very small handful heuristics for HTN planning – so there is still huge potential for improvements. It is especially noteworthy that there does not exist a single heuristic that’s tailored towards special cases. In this work we propose the very first specialized HTN heuristic, tailored towards totally ordered HTN problems. Our heuristic builds on an existing NP-complete and admissible delete-and-ordering relaxation ILP heuristic but partially incorporates ordering constraints while reducing the number of ILP constraints. It exploits inferred preconditions and effects of compound tasks and is also admissible thus allowing to find optimal solutions. Our heuristic proves to be more efficient than the one we improve, dominating it in every domain both in terms of coverage and IPC score. Compared to the current state-of-the art heuristic for optimal HTN planning, our heuristic is less efficient on average, but dominates it in roughly as many cases as it gets dominated by the other, making it a more efficient alternative in several domains.

@InProceedings{Bercher2024PlanOptimizationSurvey,
  author                    = {Pascal Bercher and Patrik Haslum and Christian Muise},
  booktitle                 = {Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI 2024)},
  title                     = {A Survey on Plan Optimization},
  year                      = {2024},
  pages                     = {7941--7950},
  doi                       = {10.24963/ijcai.2024/879},
  publisher                 = {IJCAI},
  abstract                  = {Automated Planning deals with finding a sequence of actions that solves a given (planning) problem. The cost of the solution is a direct consequence of these actions, for example its number or their accumulated costs. Thus, in most applications, cheaper plans are preferred. Yet, finding an optimal solution is more challenging than finding some solution. So, many planning algorithms find some solution and then post-process, i.e., optimize it -- a technique called plan optimization. Over the years many different approaches were developed, not all for the same kind of plans, and not all optimize the same metric. In this comprehensive survey, we give an overview of the existing plan optimization goals, their computational complexity (if known), and existing techniques for such optimizations.},
  url_Paper                 = {https://bercher.net/publications/2024/Bercher2024PlanOptimizationSurvey.pdf},
  url_Slides                = {https://bercher.net/publications/2024/Bercher2024PlanOptimizationSurveySlides.pdf}, 
  url_Poster                = {https://bercher.net/publications/2024/Bercher2024PlanOptimizationSurveyPoster.pdf}, 
  keywords                  = {conference,DECRA}
}

Automated Planning deals with finding a sequence of actions that solves a given (planning) problem. The cost of the solution is a direct consequence of these actions, for example its number or their accumulated costs. Thus, in most applications, cheaper plans are preferred. Yet, finding an optimal solution is more challenging than finding some solution. So, many planning algorithms find some solution and then post-process, i.e., optimize it – a technique called plan optimization. Over the years many different approaches were developed, not all for the same kind of plans, and not all optimize the same metric. In this comprehensive survey, we give an overview of the existing plan optimization goals, their computational complexity (if known), and existing techniques for such optimizations.

@InProceedings{Yousefi2024FONDFoundations,
  author                    = {Mohammad Yousefi and Pascal Bercher},
  booktitle                 = {Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI 2024)},
  title                     = {Laying the Foundations for Solving {FOND} {HTN} Problems: Grounding, Search, Heuristics (and Benchmark Problems)},
  year                      = {2024},
  pages                     = {6796--6804},
  publisher                 = {IJCAI},
  abstract                  = {Building upon recent advancements in formalising Fully Observable Non-Deterministic (FOND) Hierarchical Task Network (HTN) planning, we present the first approach to find strong solutions for HTN problems with uncertainty in action outcomes. We present a search algorithm, along with a compilation that relaxes a FOND HTN problem to a deterministic one. This allows the utilisation of existing grounders and heuristics from the deterministic HTN planning literature.},
  doi                       = {10.24963/ijcai.2024/751},
  url_Paper                 = {https://bercher.net/publications/2024/Yousefi2024FONDFoundations.pdf},
  url_Poster                = {https://bercher.net/publications/2024/Yousefi2024FONDFoundationsPoster.pdf},
  url_Slides_IJCAI          = {https://bercher.net/publications/2024/Yousefi2024FONDFoundationsSlidesIJCAI.pdf},
  url_Slides_HPlan          = {https://bercher.net/publications/2024/Yousefi2024FONDFoundationsSlidesHPlan.pdf},
  url_Slides_ANU            = {https://bercher.net/publications/2024/Yousefi2024FONDFoundationsSlidesANU.pdf},
  url_zenodo                = {https://zenodo.org/records/11172885},
  keywords                  = {conference,DECRA}
}

Building upon recent advancements in formalising Fully Observable Non-Deterministic (FOND) Hierarchical Task Network (HTN) planning, we present the first approach to find strong solutions for HTN problems with uncertainty in action outcomes. We present a search algorithm, along with a compilation that relaxes a FOND HTN problem to a deterministic one. This allows the utilisation of existing grounders and heuristics from the deterministic HTN planning literature.

@InProceedings{Lin2024HTNModelFixing,
  author    = {Songtuan Lin and Daniel H\"oller and Pascal Bercher},
  booktitle = {Proceedings of the 17th International Symposium on Combinatorial Search (SoCS 2024)},
  title     = {Modeling Assistance for Hierarchical Planning: An Approach for Correcting Hierarchical Domains with Missing Actions},
  note      = {<b><i>This paper won the SoCS 2024 Best Student Paper Award</i></b>},
  year      = {2024},
  publisher = {AAAI Press},
  doi       = {10.1609/socs.v17i1.31542},
  pages     = {55--63},
  abstract  = {The complexity of modeling planning domains is a major obstacle for making automated planning techniques more accessible, raising the demand of tools for providing modeling assistance. In particular, tools that can automatically correct errors in a planning domain are of great importance. Previous works have devoted efforts to developing such approaches for correcting classical (non-hierarchical) domains. However, no approaches exist for hierarchical planning, which is what we offer here. More specifically, our approach takes as input a flawed hierarchical domain together with a plan known to be a solution but actually contradicting the domain (due to errors in the domain) and outputs corrections to the domain that add missing actions to the domain and make the plan a solution. The approach achieves this by compiling the problem of finding corrections as another hierarchical planning problem.},
  url_Paper  = {https://bercher.net/publications/2024/Lin2024HTNModelFixing.pdf},
  url_Poster = {https://bercher.net/publications/2024/Lin2024HTNModelFixingPoster.pdf},
  url_Slides = {https://bercher.net/publications/2024/Lin2024HTNModelFixingSlides.pdf},
  url_zenodo = {https://zenodo.org/records/10946945},
  keywords   = {conference}
}

The complexity of modeling planning domains is a major obstacle for making automated planning techniques more accessible, raising the demand of tools for providing modeling assistance. In particular, tools that can automatically correct errors in a planning domain are of great importance. Previous works have devoted efforts to developing such approaches for correcting classical (non-hierarchical) domains. However, no approaches exist for hierarchical planning, which is what we offer here. More specifically, our approach takes as input a flawed hierarchical domain together with a plan known to be a solution but actually contradicting the domain (due to errors in the domain) and outputs corrections to the domain that add missing actions to the domain and make the plan a solution. The approach achieves this by compiling the problem of finding corrections as another hierarchical planning problem.

@InProceedings{Lin2024PlanVerificationComplexity,
  author    = {Songtuan Lin and Conny Olz and Malte Helmert and Pascal Bercher},
  booktitle = {Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024)},
  title     = {On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence},
  year      = {2024},
  publisher = {AAAI Press},
  doi       = {10.1609/aaai.v38i18.30000},
  abstract  = {In this paper we study the computational complexity of several reasoning tasks centered around the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for a grounded and a lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not yet been studied for HTN planning. For plan verification, results were available for both formalisms except for the lifted HTN planning. We will present lower and upper bounds of the complexity of plan verification in lifted HTN planning and provide some new insights into its grounded counterpart, in which we show that verification is not just NP-complete in the general case, but already for a severely restricted special case. Finally, we show the complexity concerning verifying the optimality of a given plan and discuss its connection to the bounded plan existence problem.},
  pages      = {20203--20211},
  url_Paper  = {https://bercher.net/publications/2024/Lin2024PlanVerificationComplexity.pdf},
  url_Paper_AAAI = {https://ojs.aaai.org/index.php/AAAI/article/view/30000/31754},
  url_Poster = {https://bercher.net/publications/2024/Lin2024PlanVerificationComplexityPoster.pdf},
  url_Slides = {https://bercher.net/publications/2024/Lin2024PlanVerificationComplexitySlides.pdf},
  keywords   = {conference}
}

In this paper we study the computational complexity of several reasoning tasks centered around the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for a grounded and a lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not yet been studied for HTN planning. For plan verification, results were available for both formalisms except for the lifted HTN planning. We will present lower and upper bounds of the complexity of plan verification in lifted HTN planning and provide some new insights into its grounded counterpart, in which we show that verification is not just NP-complete in the general case, but already for a severely restricted special case. Finally, we show the complexity concerning verifying the optimality of a given plan and discuss its connection to the bounded plan existence problem.

@InProceedings{Jamakatel2023HTNAviation,
  author     = {Prakash Jamakatel and Pascal Bercher and Axel Schulte and Jane Jean Kiam},
  title      = {Towards Intelligent Companion Systems in General Aviation using Hierarchical Plan and Goal Recognition},
  booktitle  = {Proceedings of the 11th International Conference on Human-Agent Interaction (HAI 2023)},
  year       = {2023},
  publisher  = {Association for Computing Machinery},
  abstract   = {Modern ultralight aircraft in general aviation are equipped with an onboard Pilot Assistance System (PAS) as a companion system, meant to guide the pilot in decision-making, e.g. with plan suggestions, especially in critical situations. For more meaningful guidance, the PAS must possess an accurate and continuous understanding of the context, i.e. the pilot's intention, so that relevant decision-making support is relevant. However, in realistic settings, the pilot's intention is not communicated manually, but can only be proactively monitored by the PAS. This paper explores the possibility of embedding domain expertise using Hierarchical Task Network (HTN) planning to recognise the plan the pilot is currently trying to conduct, by judging from the pilot's actions. Furthermore, by leveraging probability theory for state estimation, since the pilot's actions can only be estimated, we derive belief values to be associated with the recognised plans. Statistical evaluation using data collected from human-in-the-loop tests shows that our intention recognition as plan recognition function is reliable enough to provide the PAS with a contextual understanding. Empirical tests also confirm that our method is efficient enough for real-time implementation.},
  pages      = {229--237},
  doi        = {10.1145/3623809.3623877},
  url_Paper  = {https://bercher.net/publications/2023/Jamakatel2023HTNAviation.pdf},
  keywords   = {conference}
}

Modern ultralight aircraft in general aviation are equipped with an onboard Pilot Assistance System (PAS) as a companion system, meant to guide the pilot in decision-making, e.g. with plan suggestions, especially in critical situations. For more meaningful guidance, the PAS must possess an accurate and continuous understanding of the context, i.e. the pilot's intention, so that relevant decision-making support is relevant. However, in realistic settings, the pilot's intention is not communicated manually, but can only be proactively monitored by the PAS. This paper explores the possibility of embedding domain expertise using Hierarchical Task Network (HTN) planning to recognise the plan the pilot is currently trying to conduct, by judging from the pilot's actions. Furthermore, by leveraging probability theory for state estimation, since the pilot's actions can only be estimated, we derive belief values to be associated with the recognised plans. Statistical evaluation using data collected from human-in-the-loop tests shows that our intention recognition as plan recognition function is reliable enough to provide the PAS with a contextual understanding. Empirical tests also confirm that our method is efficient enough for real-time implementation.

@InProceedings{Sleath2023PossibleModelingErrors,
  author                    = {Kayleigh Sleath and Pascal Bercher},
  title                     = {Detecting AI Planning Modelling Mistakes -- Potential Errors and Benchmark Domains},
  booktitle                 = {Proceedings of the 20th Pacific Rim International Conference on Artificial Intelligence (PRICAI 2023)},
  year                      = {2023},
  publisher                 = {Springer},
  pages                     = {448--454},
  abstract                  = {AI planning systems can solve complex problems, leaving domain creation as one of the largest obstacles to a large-scale application of this technology. Domain modeling is a tedious, error-prone and manual process. Unfortunately, domain modelling assistance software is sparse and mostly restricted to editors with only surface-level functionality such as syntax highlighting. We address this important gap by proposing a list of potential domain errors which can be detected by problem parsers and modeling tools. We test well-known planning systems and modeling editors on models with those errors and report their results.},
  doi                       = {10.1007/978-981-99-7022-3_41},
  url_Paper                 = {https://bercher.net/publications/2023/Sleath2023PossibleModelingErrors.pdf},
  url_Slides                = {https://bercher.net/publications/2023/Sleath2023PossibleModelingErrorsSlides.pdf},
  url_video_of_presentation = {https://www.youtube.com/watch?v=5TR7Hf9rlpI},
  url_zenodo                = {https://zenodo.org/records/8249690},
  keywords                  = {conference}
}

AI planning systems can solve complex problems, leaving domain creation as one of the largest obstacles to a large-scale application of this technology. Domain modeling is a tedious, error-prone and manual process. Unfortunately, domain modelling assistance software is sparse and mostly restricted to editors with only surface-level functionality such as syntax highlighting. We address this important gap by proposing a list of potential domain errors which can be detected by problem parsers and modeling tools. We test well-known planning systems and modeling editors on models with those errors and report their results.

@InProceedings{Tan2023AcyclicDiMAPF,
  author     = {Xing Tan and Pascal Bercher},
  title      = {Intractability of Optimal Multi-Agent Pathfinding on Directed Graphs},
  booktitle  = {Proceedings of the 26th European Conference on Artificial Intelligence (ECAI 2023)},
  year       = {2023},
  publisher  = {IOS Press},
  pages      = {2315--2321},
  abstract   = {In Multi-Agent Pathfinding (MAPF) problems, multiple agents move simultaneously to reach their individual destinations without colliding with each other. The computational complexity of the problem has been extensively studied for undirected graphs over the past decades. However, plan existence for Directed MAPF (diMAPF) was only recently studied and was shown to be in PSPACE as well as NP-hard. In this paper, we study the optimization versions (on makespan and on travel distance of agents) of diMAPF problems and show that they remain NP-hard even when various important non-trivial restrictions are imposed (e.g., when considering the problem on directed, acyclic, and planar graphs where the vertex-degrees are bounded). We have also provide membership results, thus presenting the first set of NP-completeness results for various optimal diMAPF variants.},
  doi        = {10.3233/FAIA230531},
  url_Paper  = {https://bercher.net/publications/2023/Tan2023optimalDiMAPFComplexity.pdf},
  url_Poster = {https://bercher.net/publications/2023/Tan2023optimalDiMAPFComplexityPoster.pdf},
  url_Slides = {https://bercher.net/publications/2023/Tan2023optimalDiMAPFComplexitySlides.pdf},
  keywords   = {conference}
}

In Multi-Agent Pathfinding (MAPF) problems, multiple agents move simultaneously to reach their individual destinations without colliding with each other. The computational complexity of the problem has been extensively studied for undirected graphs over the past decades. However, plan existence for Directed MAPF (diMAPF) was only recently studied and was shown to be in PSPACE as well as NP-hard. In this paper, we study the optimization versions (on makespan and on travel distance of agents) of diMAPF problems and show that they remain NP-hard even when various important non-trivial restrictions are imposed (e.g., when considering the problem on directed, acyclic, and planar graphs where the vertex-degrees are bounded). We have also provide membership results, thus presenting the first set of NP-completeness results for various optimal diMAPF variants.

@InProceedings{Lin2023ImprovedHTNVerifyViaSAT,
  author     = {Songtuan Lin and Gregor Behnke and Pascal Bercher},
  title      = {Accelerating SAT-Based HTN Plan Verification by Exploiting Data Structures from HTN Planning},
  booktitle  = {Proceedings of the 26th European Conference on Artificial Intelligence (ECAI 2023)},
  year       = {2023},
  publisher  = {IOS Press},
  pages      = {1489--1496},
  abstract   = {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.},
  doi        = {10.3233/FAIA230428},
  url_Paper  = {https://bercher.net/publications/2023/Lin2023ImprovedHTNVerifyViaSAT.pdf},
  url_Poster = {https://bercher.net/publications/2023/Lin2023ImprovedHTNVerifyViaSATPoster.pdf},
  url_Slides = {https://bercher.net/publications/2023/Lin2023ImprovedHTNVerifyViaSATSlides.pdf},
  url_zenodo = {https://zenodo.org/records/10906075},
  keywords   = {conference}
}

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.

@InProceedings{Olz2023TOLookAhead,
  author         = {Conny Olz and Pascal Bercher},
  booktitle      = {Proceedings of the 16th International Symposium on Combinatorial Search (SoCS 2023)},
  title          = {A Look-Ahead Technique for Search-Based HTN Planning: Reducing the Branching Factor by Identifying Inevitable Task Refinements},
  year           = {2023},
  publisher      = {AAAI Press},
  pages          = {65--73},
  abstract       = {In HTN planning the choice of decomposition methods used to refine compound tasks is key to finding a valid plan. Based on inferred preconditions and effects of compound tasks, we propose a look-ahead technique for search-based total-order HTN planning that can identify inevitable refinement choices and in some cases dead-ends. The former occurs when all but one decomposition method for some task are proven infeasible for turning a task network into a solution, whereas the latter occurs when all methods are proven infeasible. We show how it can be used for pruning, as well as to strengthen heuristics and to reduce the search branching factor. An empirical evaluation proves its potential as incorporating it improves an existing HTN planner such that it is the currently best performing one in terms of coverage and IPC score.},
  doi            = {10.1609/socs.v16i1.27284},
  url_Paper      = {https://bercher.net/publications/2023/Olz2023TOLookAhead.pdf},
  url_AAAI_paper = {https://ojs.aaai.org/index.php/SOCS/article/view/27284/27057},
  url_zenodo     = {https://zenodo.org/records/7900414},
  doi            = {10.1609/socs.v16i1.27284},
  keywords       = {conference}
}

In HTN planning the choice of decomposition methods used to refine compound tasks is key to finding a valid plan. Based on inferred preconditions and effects of compound tasks, we propose a look-ahead technique for search-based total-order HTN planning that can identify inevitable refinement choices and in some cases dead-ends. The former occurs when all but one decomposition method for some task are proven infeasible for turning a task network into a solution, whereas the latter occurs when all methods are proven infeasible. We show how it can be used for pruning, as well as to strengthen heuristics and to reduce the search branching factor. An empirical evaluation proves its potential as incorporating it improves an existing HTN planner such that it is the currently best performing one in terms of coverage and IPC score.

@InProceedings{Ondrckova2023HTNParsing,
  author           = {Simona Ondr\v{c}kov\'{a} and Roman Bart{\'a}k and Pascal Bercher and Gregor Behnke},
  booktitle        = {Proceedings of the 35th International Florida Artificial Intelligence Research Society Conference ({FLAIRS} 2023)},
  title            = {Lessons Learned from the CYK Algorithm for Parsing-based Verification of Hierarchical Plans},
  year             = {2023},
  abstract         = {Verification of hierarchical plans deals with the problem of whether an action sequence is causally consistent and can be obtained by a decomposition of a goal task. This second sub-problem (finding the decomposition) makes the verification problem NP-hard. The task decomposition structure is very close to a parsing tree of context-free grammar (CFG). Recently, the CFG-parsing algorithm by Cocke-Younger-Kasami (CYK) has been modified to verify hierarchical plans efficiently. Despite being fast, the algorithm can only handle totally-ordered planning domains. In this paper, we ask whether the ideas from the CYK algorithm can be extended to a more general parsing-based approach that covers all planning domains, i.e., including partially ordered ones. More specifically, we study the effect of modifying the domain model by limiting the number of sub-tasks in decomposition methods to two and the effect of changing the parsing strategy.},
  url_Paper        = {https://bercher.net/publications/2023/Ondrckova2023CYKLessonsLearned.pdf},
  url_FLAIRS-Paper = {https://journals.flvc.org/FLAIRS/article/view/133196},
  doi              = {10.32473/flairs.36.133196},
  keywords         = {conference}
}

Verification of hierarchical plans deals with the problem of whether an action sequence is causally consistent and can be obtained by a decomposition of a goal task. This second sub-problem (finding the decomposition) makes the verification problem NP-hard. The task decomposition structure is very close to a parsing tree of context-free grammar (CFG). Recently, the CFG-parsing algorithm by Cocke-Younger-Kasami (CYK) has been modified to verify hierarchical plans efficiently. Despite being fast, the algorithm can only handle totally-ordered planning domains. In this paper, we ask whether the ideas from the CYK algorithm can be extended to a more general parsing-based approach that covers all planning domains, i.e., including partially ordered ones. More specifically, we study the effect of modifying the domain model by limiting the number of sub-tasks in decomposition methods to two and the effect of changing the parsing strategy.

@InProceedings{Olz2023ConjunctiveHTNEffects,
  author    = {Conny Olz and Pascal Bercher},
  booktitle = {Proceedings of the 33rd International Conference on Automated Planning and Scheduling ({ICAPS 2023})},
  title     = {Can They Come Together? A Computational Complexity Analysis of Conjunctive Possible Effects of Compound HTN Planning Tasks},
  year      = {2023},
  pages     = {314--323},
  publisher = {AAAI Press},
  doi       = {10.1609/icaps.v33i1.27209},
  abstract  = {Recently, inferred effects of compound (totally ordered) HTN planning tasks were introduced. Guaranteed effects are those which hold true after all executable refinements of said task, whereas possible effects are required to hold after some of them. It is known that we can decide in P whether a single fact is a precondition-relaxed possible effect. For this relaxation it wasn't clear whether groups of effects could be determined in P as well. We show that the problem turns NP-complete for conjunctive possible effects of arbitrary size. A more positive result is that this problem is fixed-parameter tractable, i.e., for any fixed number of possible effects, we can verify (and compute) them in P. As a side product of our investigations we obtain novel results for total-order HTN planning problems with goal description: When ignoring action preconditions, plan existence is NP-complete and remains NP-hard even when the problem is additionally acyclic, regular, and delete-relaxed.},
  url_Paper = {https://bercher.net/publications/2023/Olz2023CompoundTaskEffects.pdf},
  keywords  = {conference}
}

Recently, inferred effects of compound (totally ordered) HTN planning tasks were introduced. Guaranteed effects are those which hold true after all executable refinements of said task, whereas possible effects are required to hold after some of them. It is known that we can decide in P whether a single fact is a precondition-relaxed possible effect. For this relaxation it wasn't clear whether groups of effects could be determined in P as well. We show that the problem turns NP-complete for conjunctive possible effects of arbitrary size. A more positive result is that this problem is fixed-parameter tractable, i.e., for any fixed number of possible effects, we can verify (and compute) them in P. As a side product of our investigations we obtain novel results for total-order HTN planning problems with goal description: When ignoring action preconditions, plan existence is NP-complete and remains NP-hard even when the problem is additionally acyclic, regular, and delete-relaxed.

@InProceedings{Ondrckova2023GroundingInVerification,
  author                 = {Simona Ondr\v{c}kov\'{a} and Roman Bart{\'a}k and Pascal Bercher and Gregor Behnke},
  booktitle              = {Proceedings of the 15th International Conference on Agents and Artificial Intelligence (ICAART 2023)},
  title                  = {On the Impact of Grounding on HTN Plan Verification via Parsing},
  year                   = {2023},
  pages                  = {92--99},
  publisher              = {SciTePress},
  abstract               = {The problem of hierarchical plan verification focuses on checking whether an action sequence is a valid hierarchical plan - the action sequence is executable and a goal task can be decomposed into it. The existing parsing-based verifier works on lifted domain models. In this paper we study whether grounding of the models could improve efficiency of the verifier. We also explore additional implementation improvements to increase the speed of the verifier},
  url_Paper              = {https://bercher.net/publications/2023/Ondrckova2023GroundingInVerification.pdf},
  url_Paper-by-Publisher = {https://www.scitepress.org/PublicationsDetail.aspx?ID=gmWzZ9pf1D4=&t=1},
  keywords               = {conference}
}

The problem of hierarchical plan verification focuses on checking whether an action sequence is a valid hierarchical plan - the action sequence is executable and a goal task can be decomposed into it. The existing parsing-based verifier works on lifted domain models. In this paper we study whether grounding of the models could improve efficiency of the verifier. We also explore additional implementation improvements to increase the speed of the verifier

@InProceedings{Lin2023RepairingHTNModelsComplexity,
  author     = {Songtuan Lin and Pascal Bercher},
  booktitle  = {Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023)},
  title      = {Was Fixing this Really That Hard? On the Complexity of Correcting HTN Domains},
  year       = {2023},
  pages      = {12032--12040},
  publisher  = {AAAI Press},
  abstract   = {Automated modeling assistance is indispensable to the AI planning being deployed in practice, notably in industry and other non-academic contexts. Yet, little progress has been made that goes beyond smart interfaces like programming environments. They focus on autocompletion, but lack intelligent support for guiding the modeler. As a theoretical foundation of a first step towards this direction, we study the computational complexity of correcting a flawed Hierarchical Task Network (HTN) planning domain. Specifically, a modeler provides a (white) list of plans that are supposed to be solutions, and likewise a (black) list of plans that shall not be solutions. We investigate the complexity of finding a set of (optimal or suboptimal) model corrections so that those plans are (respective not) solutions to the corrected model. More specifically, we factor out each hardness source that contributes towards NP-hardness, including one that we deem important for many other complexity investigations that go beyond our specific context of application. All complexities range between NP and Sigma-2-p, raising the hope for efficient practical tools in the future.},
  doi        = {10.1609/aaai.v37i10.26419},
  url_Paper  = {https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexity.pdf},
  url_Poster = {https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexityPoster.pdf},
  url_Slides = {https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexitySlides.pdf},
  keywords   = {conference}
}

Automated modeling assistance is indispensable to the AI planning being deployed in practice, notably in industry and other non-academic contexts. Yet, little progress has been made that goes beyond smart interfaces like programming environments. They focus on autocompletion, but lack intelligent support for guiding the modeler. As a theoretical foundation of a first step towards this direction, we study the computational complexity of correcting a flawed Hierarchical Task Network (HTN) planning domain. Specifically, a modeler provides a (white) list of plans that are supposed to be solutions, and likewise a (black) list of plans that shall not be solutions. We investigate the complexity of finding a set of (optimal or suboptimal) model corrections so that those plans are (respective not) solutions to the corrected model. More specifically, we factor out each hardness source that contributes towards NP-hardness, including one that we deem important for many other complexity investigations that go beyond our specific context of application. All complexities range between NP and Sigma-2-p, raising the hope for efficient practical tools in the future.

@InProceedings{Lin2023RepairingClassicalModels,
  author     = {Songtuan Lin and Alban Grastien and Pascal Bercher},
  booktitle  = {Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023)},
  title      = {Towards Automated Modeling Assistance: An Efficient Approach for Repairing Flawed Planning Domains},
  year       = {2023},
  pages      = {12022--12031},
  publisher  = {AAAI Press},
  abstract   = {Designing a planning domain is a difficult task in AI planning. Assisting tools are thus required if we want planning to be used more broadly. In this paper, we are interested in automatically correcting a flawed domain. In particular, we are concerned with the scenario where a domain contradicts a plan that is known to be valid. Our goal is to repair the domain so as to turn the plan into a solution. Specifically, we consider both grounded and lifted representations support for negative preconditions and show how to explore the space of repairs to find the optimal one efficiently. As an evidence of the efficiency of our approach, the experiment results show that all flawed domains except one in the benchmark set can be repaired optimally by our approach within one second.},
  doi        = {10.1609/aaai.v37i10.26418},
  url_Paper  = {https://bercher.net/publications/2023/Lin2023RepairingClassicalModels.pdf},
  url_Poster = {https://bercher.net/publications/2023/Lin2023RepairingClassicalModelsPoster.pdf},
  url_Slides = {https://bercher.net/publications/2023/Lin2023RepairingClassicalModelsSlides.pdf},
  url_zenodo = {https://zenodo.org/records/7690016},
  keywords   = {conference}
}

Designing a planning domain is a difficult task in AI planning. Assisting tools are thus required if we want planning to be used more broadly. In this paper, we are interested in automatically correcting a flawed domain. In particular, we are concerned with the scenario where a domain contradicts a plan that is known to be valid. Our goal is to repair the domain so as to turn the plan into a solution. Specifically, we consider both grounded and lifted representations support for negative preconditions and show how to explore the space of repairs to find the optimal one efficiently. As an evidence of the efficiency of our approach, the experiment results show that all flawed domains except one in the benchmark set can be repaired optimally by our approach within one second.

@InProceedings{Lin2023TOVerification,
  author     = {Songtuan Lin and Gregor Behnke and Simona Ondr\v{c}kov{\'{a}} and Roman Bart{\'{a}}k and Pascal Bercher},
  booktitle  = {Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023)},
  title      = {On Total-Order HTN Plan Verification with Method Preconditions -- An Extension of the CYK Parsing Algorithm},
  year       = {2023},
  pages      = {12041--12048},
  publisher  = {AAAI Press},
  abstract   = {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.},
  doi        = {10.1609/aaai.v37i10.26420},
  url_Paper  = {https://bercher.net/publications/2023/Lin2023TOVerification.pdf},
  url_Poster = {https://bercher.net/publications/2023/Lin2023TOVerificationPoster.pdf},
  url_Slides = {https://bercher.net/publications/2023/Lin2023TOVerificationSlides.pdf},
  url_zenodo = {https://zenodo.org/records/7704558},
  keywords   = {conference}
}

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.

@InProceedings{Sreedharan2022ModelReconciliationComplexity,
  author                    = {Sarath Sreedharan and Pascal Bercher and Subbarao Kambhampati},
  booktitle                 = {Proceedings of the 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence (IJCAI-ECAI 2022)},
  title                     = {On the Computational Complexity of Model Reconciliations},
  year                      = {2022},
  pages                     = {4657--4664},
  doi                       = {10.24963/ijcai.2022/646},
  publisher                 = {IJCAI},
  abstract                  = {Model-reconciliation explanation is a popular framework for generating explanations for planning problems. While the framework has been extended to multiple settings since its introduction for classical planning problems, there is little agreement on the computational complexity of generating minimal model reconciliation explanations in the basic setting. In this paper, we address this lacuna by introducing a decision-version of the model-reconciliation explanation generation problem and we show that it is Sigma2-complete.},
  url_Paper                 = {https://bercher.net/publications/2022/Sreedharan2022ModelReconciliationComplexity.pdf},
  url_Poster                = {https://bercher.net/publications/2022/Sreedharan2022ModelReconciliationComplexityPoster.pdf},
  url_Slides                = {https://bercher.net/publications/2022/Sreedharan2022ModelReconciliationComplexitySlides.pdf},
  url_video_of_presentation = {https://www.ijcai.org/proceedings/2022/video/646},
  keywords                  = {conference}
}

Model-reconciliation explanation is a popular framework for generating explanations for planning problems. While the framework has been extended to multiple settings since its introduction for classical planning problems, there is little agreement on the computational complexity of generating minimal model reconciliation explanations in the basic setting. In this paper, we address this lacuna by introducing a decision-version of the model-reconciliation explanation generation problem and we show that it is Sigma2-complete.

@InProceedings{Bercher2022TightHybridBounds,
  author                    = {Pascal Bercher and Songtuan Lin and Ron Alford},
  booktitle                 = {Proceedings of the 31st International Joint Conference on Artificial Intelligence and the 25th European Conference on Artificial Intelligence (IJCAI-ECAI 2022)},
  title                     = {Tight Bounds for Hybrid Planning},
  year                      = {2022},
  pages                     = {4597--4605},
  publisher                 = {IJCAI},
  abstract                  = {Several hierarchical planning systems feature a rich level of language features making them capable of expressing real-work problems. One such feature that's used by several current planning systems is causal links, which are used to track search progress. The formalism combining Hierarchical Task Network (HTN) planning with these links known from Partial Order Causal Link (POCL) planning is often referred to as hybrid planning. In this paper we study the computational complexity of such hybrid planning problems. More specifically, we provide missing membership results to existing hardness proofs and thereby provide tight complexity bounds for all known subclasses of hierarchical planning problems. We also re-visit and correct a result from the literature for plan verification showing that it remains NP-complete even in the absence of a task hierarchy.},
  doi                       = {10.24963/ijcai.2022/638},
  url_Paper                 = {https://bercher.net/publications/2022/Bercher2022TightHybridBounds.pdf},
  url_Poster                = {https://bercher.net/publications/2022/Bercher2022TightHybridBoundsPoster.pdf},
  url_Slides                = {https://bercher.net/publications/2022/Bercher2022TightHybridBoundsSlides.pdf},
  url_video_of_presentation = {https://www.ijcai.org/proceedings/2022/video/638},
  keywords                  = {conference}
}

Several hierarchical planning systems feature a rich level of language features making them capable of expressing real-work problems. One such feature that's used by several current planning systems is causal links, which are used to track search progress. The formalism combining Hierarchical Task Network (HTN) planning with these links known from Partial Order Causal Link (POCL) planning is often referred to as hybrid planning. In this paper we study the computational complexity of such hybrid planning problems. More specifically, we provide missing membership results to existing hardness proofs and thereby provide tight complexity bounds for all known subclasses of hierarchical planning problems. We also re-visit and correct a result from the literature for plan verification showing that it remains NP-complete even in the absence of a task hierarchy.

@InProceedings{Ondrckova2022ParsingWithGoal,
  author           = {Simona Ondr\v{c}kov\'{a} and Roman Bart{\'a}k and Pascal Bercher and Gregor Behnke},
  booktitle        = {Proceedings of the 35th International Florida Artificial Intelligence Research Society Conference ({FLAIRS} 2022)},
  title            = {On Heuristics for Parsing-based Verification of Hierarchical Plans with a Goal Task},
  year             = {2022},
  abstract         = {Verification of hierarchical plans deals with the problem if a given action sequence is a valid hierarchical plan - the action sequence can be obtained by decomposing a particular (goal) task using given decomposition methods. The existing parsing-based verification approach greedily composes actions until it obtains the goal task. Greediness implies that this approach also generates tasks unrelated to the goal task. In this paper, we study the use of heuristics when creating new tasks. We also ask whether the prior knowledge of the goal task improves efficiency.},
  url_Paper        = {https://bercher.net/publications/2022/Ondrckova2022ParsingWithGoal.pdf},
  url_FLAIRS-Paper = {https://journals.flvc.org/FLAIRS/article/view/130606/133897},
  doi              = {10.32473/flairs.v35i.130606},
  keywords         = {conference}
}

Verification of hierarchical plans deals with the problem if a given action sequence is a valid hierarchical plan - the action sequence can be obtained by decomposing a particular (goal) task using given decomposition methods. The existing parsing-based verification approach greedily composes actions until it obtains the goal task. Greediness implies that this approach also generates tasks unrelated to the goal task. In this paper, we study the use of heuristics when creating new tasks. We also ask whether the prior knowledge of the goal task improves efficiency.

@InProceedings{Hoeller2022VerifyViaPlanning,
  author                    = {Daniel H\"oller and Julia Wichlacz and Pascal Bercher and Gregor Behnke},
  booktitle                 = {Proceedings of the 32nd International Conference on Automated Planning and Scheduling (ICAPS 2022)},
  title                     = {Compiling HTN Plan Verification Problems into HTN Planning Problems},
  year                      = {2022},
  pages                     = {145--150},
  publisher                 = {AAAI Press},
  abstract                  = {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,  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.},
  doi                       = {10.1609/icaps.v32i1.19795},
  url_Paper                 = {https://bercher.net/publications/2022/Hoeller2022VerificationViaCompilation.pdf},
  url_poster                = {http://icaps22.icaps-conference.org/posters/hoeller_MTS15.pdf},
  url_video_of_presentation = {http://icaps22.icaps-conference.org/papers/15/index.html},
  keywords                  = {conference}
}

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

@InProceedings{Lin2022LTLExpressivity,
  author                    = {Songtuan Lin and Pascal Bercher},
  booktitle                 = {Proceedings of the 32nd International Conference on Automated Planning and Scheduling (ICAPS 2022)},
  title                     = {On the Expressive Power of Planning Formalisms in Conjunction with LTL},
  year                      = {2022},
  pages                     = {231--240},
  publisher                 = {AAAI Press},
  abstract                  = {Linear Temporal Logic (LTL) has been widely employed in various planning formalisms, e.g., in the STRIPS formalism, in order to specify constraints over state trajectories in a planning problem. In this paper, we investigate the expressive power of two planning formalisms in conjunction with LTL that are most commonly seen in non-hierarchical planning and hierarchical planning respectively, namely the STRIPS formalism and the Hierarchical Task Network (HTN) formalism. We do so by interpreting the set of all solutions to a planning problem as a formal language and comparing it with other formal ones, e.g., star-free languages. Our results provide an in-depth insight into the theoretical properties of the investigated planning formalisms and henceforth explore the common structure shared by solutions to planning problems in certain planning formalisms.},
  doi                       = {10.1609/icaps.v32i1.19806},
  url_Paper                 = {https://bercher.net/publications/2022/Lin2022LTLExpressivity.pdf},
  url_Poster                = {https://bercher.net/publications/2022/Lin2022LTLExpressivityPoster.pdf},
  url_Slides                = {https://bercher.net/publications/2022/Lin2022LTLExpressivitySlides.pdf},
  url_video_of_presentation = {http://icaps22.icaps-conference.org/papers/49/index.html},
  keywords                  = {conference}
}

Linear Temporal Logic (LTL) has been widely employed in various planning formalisms, e.g., in the STRIPS formalism, in order to specify constraints over state trajectories in a planning problem. In this paper, we investigate the expressive power of two planning formalisms in conjunction with LTL that are most commonly seen in non-hierarchical planning and hierarchical planning respectively, namely the STRIPS formalism and the Hierarchical Task Network (HTN) formalism. We do so by interpreting the set of all solutions to a planning problem as a formal language and comparing it with other formal ones, e.g., star-free languages. Our results provide an in-depth insight into the theoretical properties of the investigated planning formalisms and henceforth explore the common structure shared by solutions to planning problems in certain planning formalisms.

@InProceedings{Behnke2022ImprovedHTNsToClassical,
  author    = {Gregor Behnke and Florian Pollitt and Daniel Höller and Pascal Bercher and Ron Alford},
  booktitle = {Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI 2022)},
  title     = {Making Translations to Classical Planning Competitive With Other HTN Planners},
  year      = {2022},
  pages     = {9687--9697},
  doi       = {10.1609/aaai.v36i9.21203},
  publisher = {AAAI Press},
  abstract  = {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.},
  url_Paper = {https://bercher.net/publications/2022/Behnke2022ImprovedHTNsToClassical.pdf},
  keywords  = {conference}
}

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.

@InProceedings{Bartak2021TOVerification,
  author    = {Roman Bart\'{a}k and Simona Ondr\v{c}kov\'{a} and Gregor Behnke and Pascal Bercher},
  booktitle = {Proceedings of the 33rd IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2021)},
  title     = {On the Verification of Totally-Ordered HTN Plans},
  year      = {2021},
  pages     = {263--267},
  publisher = {IEEE},
  abstract  = {Verifying HTN plans is an intractable problem with two existing approaches to solve the problem. One technique is based on compilation to SAT. Another method is using parsing, and it is currently the fastest technique for verifying HTN plans and the only technique supporting state constraints. In this paper, we propose an extension of the parsing-based approach to verify totally-ordered HTN plans more efficiently. This problem is known to be tractable if no state constraints are included, and we show theoretically and empirically that the modified parsing approach achieves better performance than the currently fastest HTN plan verifier when applied to totally-ordered HTN plans.},
  url_Paper = {https://bercher.net/publications/2021/Bartak2021TOVerification.pdf},
  doi       = {10.1109/ICTAI52525.2021.00043},
  keywords  = {conference}
}

Verifying HTN plans is an intractable problem with two existing approaches to solve the problem. One technique is based on compilation to SAT. Another method is using parsing, and it is currently the fastest technique for verifying HTN plans and the only technique supporting state constraints. In this paper, we propose an extension of the parsing-based approach to verify totally-ordered HTN plans more efficiently. This problem is known to be tractable if no state constraints are included, and we show theoretically and empirically that the modified parsing approach achieves better performance than the currently fastest HTN plan verifier when applied to totally-ordered HTN plans.

@InProceedings{Bartak2021PlanCorrections,
  author                    = {Roman Bart{\'a}k and Simona Ondr\v{c}kov\'{a} and Gregor Behnke and Pascal Bercher},
  title                     = {Correcting Hierarchical Plans by Action Deletion},
  booktitle                 = {Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning (KR 2021)},
  year                      = {2021},
  publisher                 = {IJCAI},
  abstract                  = {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.},
  pages                     = {99--109},
  doi                       = {10.24963/kr.2021/10},
  url_Paper                 = {https://bercher.net/publications/2021/Bartak2021PlanCorrections.pdf},
  url_video_of_presentation = {https://www.youtube.com/watch?v=GQoRxilDKfQ},
  keywords                  = {conference}
}

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.

@InProceedings{Lin2021FixHTNModel,
  author          = {Songtuan Lin and Pascal Bercher},
  title           = {Change the World -- How Hard Can that Be? On the Computational Complexity of Fixing Planning Models},
  booktitle       = {Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021)},
  year            = {2021},
  publisher       = {IJCAI},
  abstract        = {Incorporating humans into AI planning is an important feature of flexible planning technology. Such human integration allows to incorporate previously unknown constraints, and is also an integral part of automated modeling assistance. As a foundation for integrating user requests, we study the computational complexity of determining the existence of changes to an existing model, such that the resulting model allows for specific user-provided solutions. We are provided with a planning problem modeled either in the classical (non-hierarchical) or hierarchical task network (HTN) planning formalism, as well as with a supposed-to-be solution plan, which is actually not a solution for the current model. Considering changing decomposition methods as well as preconditions and effects of actions, we show that most change requests are NP-complete though some turn out to be tractable.},
  pages           = {4152--4159},
  doi             = {10.24963/ijcai.2021/571},
  url_Paper       = {https://bercher.net/publications//2021/Lin2021ChangeTheWorld.pdf},
  url_Slides      = {https://bercher.net/publications//2021/Lin2021ChangeTheWorldSlides.pdf},
  url_Slides-4on1 = {https://bercher.net/publications//2021/Lin2021ChangeTheWorldSlides4on1.pdf},
  url_Poster      = {https://bercher.net/publications//2021/Lin2021ChangeTheWorldPoster.pdf},
  keywords        = {conference}
}

Incorporating humans into AI planning is an important feature of flexible planning technology. Such human integration allows to incorporate previously unknown constraints, and is also an integral part of automated modeling assistance. As a foundation for integrating user requests, we study the computational complexity of determining the existence of changes to an existing model, such that the resulting model allows for specific user-provided solutions. We are provided with a planning problem modeled either in the classical (non-hierarchical) or hierarchical task network (HTN) planning formalism, as well as with a supposed-to-be solution plan, which is actually not a solution for the current model. Considering changing decomposition methods as well as preconditions and effects of actions, we show that most change requests are NP-complete though some turn out to be tractable.

@InProceedings{Chen2021FONDHTN,
  author                    = {Dillon Chen and Pascal Bercher},
  title                     = {Fully Observable Nondeterministic HTN Planning -- Formalisation and Complexity Results},
  booktitle                 = {Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021)},
  year                      = {2021},
  pages                     = {74--84},
  publisher                 = {AAAI Press},
  doi                       = {10.1609/icaps.v31i1.15949},
  abstract                  = {Much progress has been made in advancing the state of the art of HTN planning theory in recent years. However, scarce studies have been made with regards to the theory and complexity of HTN problems on nondeterministic domains. In this paper we provide a novel formalisation for fully observable nondeterministic HTN planning. We propose and study different solution criteria which differ in when nondeterministic action outcomes are considered: at plan generation or at plan execution. We integrate our solution criteria with notions of weak and strong plans canonical in nondeterministic planning and identify similarities and differences with plans in other fields of AI planning. We also provide completeness results for a majority of HTN problem subclasses and show the significant result that problems are not made any harder under nondeterminism for certain solution criteria by using compilation techniques to deterministic HTN planning. This supports and justifies the practicality and scalability of extending HTN problems over nondeterministic domains to deal with real world scenarios.},
  url_Paper                 = {https://bercher.net/publications/2021/Chen2021FONDHTNs.pdf},
  url_video_of_presentation = {https://icaps21.icaps-conference.org/papers/exhibition_files/index_44.html},
  note                      = {<b><i>This paper won the ICAPS 2021 Best Undergraduate Student Paper Award</i></b>},
  keywords                  = {conference}
}

Much progress has been made in advancing the state of the art of HTN planning theory in recent years. However, scarce studies have been made with regards to the theory and complexity of HTN problems on nondeterministic domains. In this paper we provide a novel formalisation for fully observable nondeterministic HTN planning. We propose and study different solution criteria which differ in when nondeterministic action outcomes are considered: at plan generation or at plan execution. We integrate our solution criteria with notions of weak and strong plans canonical in nondeterministic planning and identify similarities and differences with plans in other fields of AI planning. We also provide completeness results for a majority of HTN problem subclasses and show the significant result that problems are not made any harder under nondeterminism for certain solution criteria by using compilation techniques to deterministic HTN planning. This supports and justifies the practicality and scalability of extending HTN problems over nondeterministic domains to deal with real world scenarios.

@InProceedings{Bercher2021POCLComplexities,
  author                    = {Pascal Bercher},
  title                     = {A Closer Look at Causal Links: Complexity Results for Delete-Relaxation in Partial Order Causal Link (POCL) Planning}, 
  booktitle                 = {Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021)},
  year                      = {2021},
  pages                     = {36--45},
  publisher                 = {AAAI Press},
  abstract                  = {Partial Order Causal Link (POCL) planning follows the principle of least commitment in that it maintains only a partial order on its actions to prevent unnecessary early commitment during search. This can reduce the search space significantly by systematically representing up to an exponential number of action sequences in just a single search node. Progress on goal achievement is represented fully by this partial order and by causal links, which represent the causal relationships between these actions as well as between the initial state and goal. Plan existence for a state in classical planning thus corresponds to plan existence for a partial plan in POCL planning. Yet almost no theoretical investigations for POCL plan existence were conducted so far. While delete-relaxation makes plan existence tractable in classical planning, we show it to be NP-hard in POCL planning unless the current plan is totally ordered or causal links are almost completely ignored.},
  doi                       = {10.1609/icaps.v31i1.15944},
  url_Paper                 = {https://bercher.net/publications/2021/Bercher2021POCLComplexities.pdf},
  url_Slides                = {https://bercher.net/publications/2021/Bercher2021POCLComplexitiesSlides.pdf},
  url_Poster                = {https://bercher.net/publications/2021/Bercher2021POCLComplexitiesPoster.pdf},
  url_video_of_presentation = {https://icaps21.icaps-conference.org/papers/exhibition_files/index_37.html},
  keywords                  = {conference}
}

Partial Order Causal Link (POCL) planning follows the principle of least commitment in that it maintains only a partial order on its actions to prevent unnecessary early commitment during search. This can reduce the search space significantly by systematically representing up to an exponential number of action sequences in just a single search node. Progress on goal achievement is represented fully by this partial order and by causal links, which represent the causal relationships between these actions as well as between the initial state and goal. Plan existence for a state in classical planning thus corresponds to plan existence for a partial plan in POCL planning. Yet almost no theoretical investigations for POCL plan existence were conducted so far. While delete-relaxation makes plan existence tractable in classical planning, we show it to be NP-hard in POCL planning unless the current plan is totally ordered or causal links are almost completely ignored.

@InProceedings{Hoeller2021HTNLandmarks,
  author    = {Daniel H\"oller and Pascal Bercher},
  booktitle = {Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021)},
  title     = {Landmark Generation in HTN Planning},
  year      = {2021},
  pages     = {11826--11834},
  publisher = {AAAI Press},
  abstract  = {Landmarks (LMs) are state features that need to be made true or tasks that need to be contained in every solution of a planning problem. They are a valuable source of information in planning and can be exploited in various ways. LMs have been used both in classical and hierarchical planning, but while there is much work in classical planning, the techniques in hierarchical planning are less evolved. We introduce a novel LM generation method for Hierarchical Task Network (HTN) planning and show that it is sound and incomplete. We show that every complete approach is as hard as the co-class of the underlying HTN problem, i.e. coNP-hard for our setting (while our approach is in P). On a widely used benchmark set, our approach finds more than twice the number of landmarks than the approach from the literature. Though our focus is on LM generation, we show that the newly discovered landmarks bear information beneficial for solvers.},
  doi       = {10.1609/aaai.v35i13.17405},
  url_Paper = {https://bercher.net/publications/2021/Hoeller2021HTNLandmarks.pdf},
  keywords  = {conference}
}

Landmarks (LMs) are state features that need to be made true or tasks that need to be contained in every solution of a planning problem. They are a valuable source of information in planning and can be exploited in various ways. LMs have been used both in classical and hierarchical planning, but while there is much work in classical planning, the techniques in hierarchical planning are less evolved. We introduce a novel LM generation method for Hierarchical Task Network (HTN) planning and show that it is sound and incomplete. We show that every complete approach is as hard as the co-class of the underlying HTN problem, i.e. coNP-hard for our setting (while our approach is in P). On a widely used benchmark set, our approach finds more than twice the number of landmarks than the approach from the literature. Though our focus is on LM generation, we show that the newly discovered landmarks bear information beneficial for solvers.

@InProceedings{Olz2021RevealingHTNEffects,
  author    = {Conny Olz and Susanne Biundo and Pascal Bercher},
  booktitle = {Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021)},
  title     = {Revealing Hidden Preconditions and Effects of Compound HTN Planning Tasks -- A Complexity Analysis},
  year      = {2021},
  pages     = {11903--11912},
  publisher = {AAAI Press},
  abstract  = {In Hierarchical Task Network (HTN) planning, compound tasks need to be refined into executable (primitive) action sequences. In contrast to their primitive counterparts, compound tasks do not show preconditions or effects. Thus, their implications on the states in which they are applied are not explicitly known: they are “hidden” in and depending on the decomposition structure. We formalize several kinds of preconditions and effects that can be inferred for compound tasks in totally ordered HTN domains. As relevant special case we introduce a problem relaxation which admits reasoning about preconditions and effects in polynomial time. We provide procedures for doing so, thereby extending previous work, which could only deal with acyclic models. We prove our procedures to be correct and complete for any totally ordered input domain. The results are embedded into an encompassing complexity analysis of the inference of preconditions and effects of compound tasks, an investigation that has not been made so far.},
  doi       = {10.1609/aaai.v35i13.17414},
  url_Paper = {https://bercher.net/publications/2021/Olz2021CompoundEffects.pdf},
  keywords  = {conference}
}

In Hierarchical Task Network (HTN) planning, compound tasks need to be refined into executable (primitive) action sequences. In contrast to their primitive counterparts, compound tasks do not show preconditions or effects. Thus, their implications on the states in which they are applied are not explicitly known: they are “hidden” in and depending on the decomposition structure. We formalize several kinds of preconditions and effects that can be inferred for compound tasks in totally ordered HTN domains. As relevant special case we introduce a problem relaxation which admits reasoning about preconditions and effects in polynomial time. We provide procedures for doing so, thereby extending previous work, which could only deal with acyclic models. We prove our procedures to be correct and complete for any totally ordered input domain. The results are embedded into an encompassing complexity analysis of the inference of preconditions and effects of compound tasks, an investigation that has not been made so far.

@InProceedings{Bartak2020ParsingApproach,
  author    = {Roman Bart{\'a}k and Simona Ondr\v{c}kov\'{a} and Adrien Maillard and Gregor Behnke and Pascal Bercher},
  title     = {A Novel Parsing-based Approach for Verification of Hierarchical Plans},
  booktitle = {Proceedings of the 32nd IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2020)},
  year      = {2020},
  publisher = {IEEE},
  pages     = {118--125},
  doi       = {10.1109/ICTAI50040.2020.00029},
  abstract  = {Hierarchical Task Networks were proposed as a method to describe plans by decomposition of tasks to sub-tasks until primitive tasks, actions, are obtained. Valid plans -- sequences of actions -- must adhere both to causal dependencies between the actions and to the structure given by the decomposition of the goal task. Plan verification aims at finding if a given plan is valid, that is, if it is causally consistent and it can be obtained by decomposition of some task. The paper describes a novel parsing-based approach for hierarchical plan verification that is orders of magnitude faster than existing methods.},
  url_Paper = {https://bercher.net/publications/2020/Bartak2020HTNVerification.pdf},
  keywords  = {conference}
}

Hierarchical Task Networks were proposed as a method to describe plans by decomposition of tasks to sub-tasks until primitive tasks, actions, are obtained. Valid plans – sequences of actions – must adhere both to causal dependencies between the actions and to the structure given by the decomposition of the goal task. Plan verification aims at finding if a given plan is valid, that is, if it is causally consistent and it can be obtained by decomposition of some task. The paper describes a novel parsing-based approach for hierarchical plan verification that is orders of magnitude faster than existing methods.

@Inproceedings {Kraus2020ICMI,
  author    = {Matthias Kraus and Marvin Schiller and Gregor Behnke and Pascal Bercher and Michael Dorna and Michael Dambier and Birte Glimm and Susanne Biundo and Wolfgang Minker},
  title     = {{W}as that successful? {O}n Integrating Proactive Meta-Dialogue in a {DIY}-Assistant System using Multimodal Cues},
  year      = {2020},
  publisher = {ACM},
  booktitle = {Proceedings of 22nd ACM International Conference on Multimodal Interaction (ICMI 2020)},
  pages     = {585--594},
  doi       = {10.1145/3382507.3418818},
  abstract  = {Effectively supporting novices during performance of complex tasks, e.g. do-it-yourself (DIY) projects, requires intelligent assistants to be more than mere instructors. In order to be accepted as a competent and trustworthy cooperation partner, they need to be able to actively participate in the project and engage in helpful conversations with users when assistance is necessary. Therefore, a new proactive version of the DIY-assistant \textsc{Robert} is presented in this paper. It extends the previous prototype by including the capability to initiate reflective meta-dialogues using multimodal cues. Two different strategies for reflective dialogue are implemented: A progress-based strategy initiates a reflective dialogue about previous experience with the assistance for encouraging the self-appraisal of the user. An activity-based strategy is applied for providing timely, task-dependent support. Therefore, user activities with a connected drill driver are tracked that trigger dialogues in order to reflect on the current task and to prevent task failure. An experimental study comparing the proactive assistant against the baseline version shows that proactive meta-dialogue is able to build user trust significantly better than a solely reactive system. Besides, the results provide interesting insights for the development of proactive dialogue assistants.},
  url_Paper = {https://bercher.net/publications/2020/Kraus2020SuccessfulDIY.pdf},
  url_Video = {https://dl.acm.org/doi/10.1145/3382507.3418818},
  keywords  = {conference}
}

Effectively supporting novices during performance of complex tasks, e.g. do-it-yourself (DIY) projects, requires intelligent assistants to be more than mere instructors. In order to be accepted as a competent and trustworthy cooperation partner, they need to be able to actively participate in the project and engage in helpful conversations with users when assistance is necessary. Therefore, a new proactive version of the DIY-assistant \textscRobert is presented in this paper. It extends the previous prototype by including the capability to initiate reflective meta-dialogues using multimodal cues. Two different strategies for reflective dialogue are implemented: A progress-based strategy initiates a reflective dialogue about previous experience with the assistance for encouraging the self-appraisal of the user. An activity-based strategy is applied for providing timely, task-dependent support. Therefore, user activities with a connected drill driver are tracked that trigger dialogues in order to reflect on the current task and to prevent task failure. An experimental study comparing the proactive assistant against the baseline version shows that proactive meta-dialogue is able to build user trust significantly better than a solely reactive system. Besides, the results provide interesting insights for the development of proactive dialogue assistants.

@InProceedings{Hoeller2020HTNPlanRepair,
  author    = {Daniel H\"oller and Pascal Bercher and Gregor Behnke and Susanne Biundo},
  title     = {HTN Plan Repair via Model Transformation},
  booktitle = {Proceedings of the 43th German Conference on Artificial Intelligence ({KI} 2020)},
  year      = {2020},
  publisher = {Springer},
  pages     = {88--101},
  note      = {<b><i>This paper was nominated for the KI 2020 Best Paper Award</i></b>},
  abstract  = {To make planning feasible, planning models abstract from many details of the modeled system. When executing plans in the actual system, the model might be inaccurate in a critical point, and plan execution may fail. There are two options to handle this case: the previous solution can be modified to address the failure (plan repair), or the planning process can be re-started from the new situation (re-planning). In HTN planning, discarding the plan and generating a new one from the novel situation is not easily possible, because the HTN solution criteria make it necessary to take already executed actions into account. Therefore all approaches to repair plans in the literature are based on specialized algorithms. In this paper, we discuss the problem in detail and introduce a novel approach that makes it possible to use unchanged, off-the-shelf HTN planning systems to repair broken HTN plans. That way, no specialized solvers are needed.},
  doi       = {10.1007/978-3-030-58285-2_7},
  url_Paper = {https://bercher.net/publications/2020/Hoeller2020HTNRepair.pdf},
  keywords  = {conference}
}

To make planning feasible, planning models abstract from many details of the modeled system. When executing plans in the actual system, the model might be inaccurate in a critical point, and plan execution may fail. There are two options to handle this case: the previous solution can be modified to address the failure (plan repair), or the planning process can be re-started from the new situation (re-planning). In HTN planning, discarding the plan and generating a new one from the novel situation is not easily possible, because the HTN solution criteria make it necessary to take already executed actions into account. Therefore all approaches to repair plans in the literature are based on specialized algorithms. In this paper, we discuss the problem in detail and introduce a novel approach that makes it possible to use unchanged, off-the-shelf HTN planning systems to repair broken HTN plans. That way, no specialized solvers are needed.

@InProceedings{Hoeller2020ILP,
  author    = {Daniel H\"oller and Pascal Bercher and Gregor Behnke},
  title     = {Delete- and Ordering-Relaxation Heuristics for HTN Planning},
  booktitle = {Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020)},
  year      = {2020},
  publisher = {IJCAI},
  doi       = {10.24963/ijcai.2020/564},
  pages     = {4076--4083},
  abstract  = {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 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 linear programming model to solve it.},
  url_Paper = {https://bercher.net/publications/2020/Hoeller2020ILPHTNHeuristics.pdf},
  keywords  = {conference}
}

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 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 linear programming model to solve it.

@InProceedings{Behnke2020DIYAssistant,
  author                    = {Gregor Behnke and Pascal Bercher and Matthias Kraus and Marvin Schiller and Kristof Mickeleit and Timo Häge and Michael Dorna and Michael Dambier and Wolfgang Minker and Birte Glimm and Susanne Biundo},
  title                     = {New Developments for Robert -- Assisting Novice Users Even Better in DIY Projects},
  year                      = {2020},
  publisher                 = {AAAI Press},
  pages                     = {343--347},
  booktitle                 = {Proceedings of the 30th International Conference on Automated Planning and Scheduling ({ICAPS 2020})},
  abstract                  = {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.},
  doi                       = {10.1609/icaps.v30i1.6679},
  url_Paper                 = {https://bercher.net/publications/2020/Behnke2020DIYAssistant.pdf},
  url_Poster                = {https://bercher.net/publications/2020/Behnke2020DIYAssistantPoster.pdf},
  url_video_of_presentation = {https://www.youtube.com/watch?v=hLd1IdgRzRA},
  keywords                  = {conference}
}

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.

@InProceedings{Hoeller2020HDDL,
  author    = {Daniel H\"oller and Gregor Behnke and Pascal Bercher and Susanne Biundo and Humbert Fiorino and Damien Pellier and Ron Alford},
  title     = {HDDL: An Extension to PDDL for Expressing Hierarchical Planning Problems},
  booktitle = {Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020)},
  year      = {2020},
  publisher = {AAAI Press},
  pages     = {9883--9891},
  doi       = {10.1609/aaai.v34i06.6542},
  abstract  = {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 find 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.},
  url_Paper = {https://bercher.net/publications/2020/Hoeller2020HDDL.pdf},
  keywords  = {conference}
}

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

@InProceedings{Behnke2020Grounding,
  author    = {Gregor Behnke and Daniel H\"oller and Alexander Schmid and Pascal Bercher and Susanne Biundo},
  title     = {On Succinct Groundings of HTN Planning Problems},
  booktitle = {Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020)},
  year      = {2020},
  pages     = {9775--9784},
  publisher = {AAAI Press},
  doi       = {10.1609/aaai.v34i06.6529},
  abstract  = {Both search-based and translation-based planning systems usually operate on grounded representations of the problem. Planning models, however, are commonly defined using lifted description languages. Thus, planning systems usually generate a grounded representation of the lifted model as a pre-processing 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.},
  url_Paper = {https://bercher.net/publications/2020/Behnke2020Grounding.pdf},
  keywords  = {conference}
}

Both search-based and translation-based planning systems usually operate on grounded representations of the problem. Planning models, however, are commonly defined using lifted description languages. Thus, planning systems usually generate a grounded representation of the lifted model as a pre-processing 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.

@InProceedings{Bercher2020POPvsPOCL,
  author               = {Pascal Bercher and Conny Olz},
  title                = {POP \equiv POCL, right? Complexity Results for Partial Order (Causal Link) Makespan Minimization},
  booktitle            = {Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020)},
  year                 = {2020},
  pages                = {9785--9793},
  publisher            = {AAAI Press},
  doi                  = {10.1609/aaai.v34i06.6530},
  abstract             = {We study PO and POCL plans with regard to their makespan -- the execution  time when allowing the parallel execution of causally independent actions. Partially ordered (PO) plans are often assumed to be equivalent to partial order causal link  (POCL) plans, where the causal relationships between actions are explicitly represented via causal links. As a first contribution, we study the similarities and differences of PO and POCL plans, thereby clarifying a common misconception about their relationship: There are PO plans for which there does not exist a POCL plan with the same orderings.We prove that we can still always find a POCL plan with the same makespan in polynomial time. As another main result we prove that turning a PO or POCL plan into one with minimal makespan by only removing ordering constraints (called deordering) is NP-complete. We provide a series of further results on special cases and implications, such as reordering, where orderings can be changed arbitrarily.},
  url_Paper            = {https://bercher.net/publications/2020/Bercher2020POPvsPOCL.pdf},
  url_Spotlight-slides = {https://bercher.net/publications/2020/Bercher2020POPvsPOCLSlidesSpotlight.pdf},
  url_Poster           = {https://bercher.net/publications/2020/Bercher2020POPvsPOCLPoster.pdf},
  keywords             = {conference}
}

We study PO and POCL plans with regard to their makespan – the execution time when allowing the parallel execution of causally independent actions. Partially ordered (PO) plans are often assumed to be equivalent to partial order causal link (POCL) plans, where the causal relationships between actions are explicitly represented via causal links. As a first contribution, we study the similarities and differences of PO and POCL plans, thereby clarifying a common misconception about their relationship: There are PO plans for which there does not exist a POCL plan with the same orderings.We prove that we can still always find a POCL plan with the same makespan in polynomial time. As another main result we prove that turning a PO or POCL plan into one with minimal makespan by only removing ordering constraints (called deordering) is NP-complete. We provide a series of further results on special cases and implications, such as reordering, where orderings can be changed arbitrarily.

@InProceedings{Bercher2019HierarchicalPlanningSurvey,
   author               = {Pascal Bercher and Ron Alford and Daniel H{\"o}ller},
   title                = {A Survey on Hierarchical Planning -- One Abstract Idea, Many Concrete Realizations},
   year                 = {2019},
   publisher            = {IJCAI},
   pages                = {6267--6275},
   booktitle            = {Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019)},
   doi                  = {10.24963/ijcai.2019/875},
   abstract             = {Hierarchical planning has attracted renewed interest in the last couple of years, which led to numerous novel formalisms, problem classes, and theoretical investigations. Yet it is important to differentiate between the various formalisms and problem classes, since they show -- sometimes fundamental -- differences with regard to their expressivity and computational complexity: Some of them can be regarded equivalent to non-hierarchical formalisms while others are clearly more expressive. We survey the most important hierarchical problem classes and explain their differences and similarities. We furthermore give pointers to some of the best-known planning systems capable of solving the respective problem classes.},
   url_Paper            = {https://bercher.net/publications/2019/Bercher2019HierarchicalPlanningSurvey.pdf},
   url_Slides           = {https://bercher.net/publications/2019/Bercher2019HierarchicalPlanningSurveySlides.pdf},
   url_tutorial         = {http://tutorial2018.hierarchical-task.net},
  keywords              = {conference}
}

Hierarchical planning has attracted renewed interest in the last couple of years, which led to numerous novel formalisms, problem classes, and theoretical investigations. Yet it is important to differentiate between the various formalisms and problem classes, since they show – sometimes fundamental – differences with regard to their expressivity and computational complexity: Some of them can be regarded equivalent to non-hierarchical formalisms while others are clearly more expressive. We survey the most important hierarchical problem classes and explain their differences and similarities. We furthermore give pointers to some of the best-known planning systems capable of solving the respective problem classes.

@InProceedings{Hoeller2019HeuristicEncoding,
   author    = {Daniel H{\"o}ller and Pascal Bercher and Gregor Behnke and Susanne Biundo},
   title     = {On Guiding Search in {HTN} Planning with Classical Planning Heuristics},
   pages     = {6171--6175},
   year      = {2019},
   publisher = {IJCAI},
   booktitle = {Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019)},
   doi       = {10.24963/ijcai.2019/857},
   abstract  = {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.},
   url_Paper  = {https://bercher.net/publications/2019/Hoeller2019HeuristicEncoding.pdf},
  keywords    = {conference}
}

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.

@InProceedings{Olz2019StepElimination,
   author                    = {Conny Olz and Pascal Bercher},
   title                     = {Eliminating Redundant Actions in Partially Ordered Plans -- A Complexity Analysis},
   year                      = {2019},
   publisher                 = {AAAI Press},
   pages                     = {310--319},
   booktitle                 = {Proceedings of the 28th International Conference on Automated Planning and Scheduling ({ICAPS 2019})},
   abstract                  = {In this paper we study the computational complexity of post-optimizing partially ordered plans, i.e., we investigate the problem that is concerned with detecting and deleting unnecessary actions. For totally ordered plans it can easily be tested in polynomial time whether a single action can be removed without violating executability. Identifying an executable subplan, i.e., asking whether k plan steps can be removed, is known to be NP-complete. We investigate the same questions for partially ordered input plans, as they are created by many search algorithms or used by real-world applications -- in particular time-critical ones that exploit parallelism of non-conflicting actions. More formally, we investigate the computational complexity of removing an action from a partially ordered solution plan in which every linearization is a solution in the classical sense while allowing ordering insertions afterwards to repair arising executability issues. It turns out that this problem is NP-complete -- even if just a single action is removed -- and thereby show that this reasoning task is harder than for totally ordered plans. Moreover, we identify the structural properties responsible for this hardness by providing a fixed-parameter tractability (FPT) result.},
   doi                       = {10.1609/icaps.v29i1.3493},
   url_Paper                 = {https://bercher.net/publications/2019/Olz2019StepElimination.pdf},
   url_Slides                = {https://bercher.net/publications/2019/Olz2019StepEliminationSlides.pdf},
   url_video_of_presentation = {https://www.youtube.com/watch?v=nNoaWfHP7eQ&t=2415s&ab_channel=ICAPS},
  keywords                   = {conference}
}

In this paper we study the computational complexity of post-optimizing partially ordered plans, i.e., we investigate the problem that is concerned with detecting and deleting unnecessary actions. For totally ordered plans it can easily be tested in polynomial time whether a single action can be removed without violating executability. Identifying an executable subplan, i.e., asking whether k plan steps can be removed, is known to be NP-complete. We investigate the same questions for partially ordered input plans, as they are created by many search algorithms or used by real-world applications – in particular time-critical ones that exploit parallelism of non-conflicting actions. More formally, we investigate the computational complexity of removing an action from a partially ordered solution plan in which every linearization is a solution in the classical sense while allowing ordering insertions afterwards to repair arising executability issues. It turns out that this problem is NP-complete – even if just a single action is removed – and thereby show that this reasoning task is harder than for totally ordered plans. Moreover, we identify the structural properties responsible for this hardness by providing a fixed-parameter tractability (FPT) result.

@InProceedings{Leichtmann2018HumanPlanningBehavior,
   author     = {Benedikt Leichtmann and Pascal Bercher and Daniel H{\"o}ller and Gregor Behnke and Susanne Biundo and Verena Nitsch and Martin Baumann},
   title      = {Towards a Companion System Incorporating Human Planning Behavior -- A Qualitative Analysis of Human Strategies},
   year       = {2018},
   pages      = {89--98},
   booktitle  = {Proceedings of the 3rd Transdisciplinary Conference on Support Technologies (TCST 2018)},
   note       = {<b><i>This paper won the TCST 2018 Best Paper Award</i></b>},
   abstract   = {User-friendly Companion Systems require Artificial Intelligence planning to take into account human planning behavior. We conducted a qualitative exploratory study of human planning in a knowledge rich, real-world scenario. Participants were tasked with setting up a home theater. The effect of strategy knowledge on problem solving was investigated by comparing the performance of two groups: one group (n = 23) with strategy instructions for problem solving and a control group without such instructions (n = 16). We inductively identify behavioral patterns for human strategy use through Markov matrices. Based on the results, we derive implications for the design of planning-based assistance systems.},
   url_Paper  = {https://bercher.net/publications/2018/Leichtmann2018HumanPlanningBehavior.pdf},
   url_Slides = {https://bercher.net/publications/2018/Leichtmann2018HumanPlanningBehaviorSlides.pdf},
  keywords    = {conference}
}

User-friendly Companion Systems require Artificial Intelligence planning to take into account human planning behavior. We conducted a qualitative exploratory study of human planning in a knowledge rich, real-world scenario. Participants were tasked with setting up a home theater. The effect of strategy knowledge on problem solving was investigated by comparing the performance of two groups: one group (n = 23) with strategy instructions for problem solving and a control group without such instructions (n = 16). We inductively identify behavioral patterns for human strategy use through Markov matrices. Based on the results, we derive implications for the design of planning-based assistance systems.

@InProceedings{Hoeller2018PlanRecognition,
   author    = {Daniel H{\"o}ller and Gregor Behnke and Pascal Bercher and Susanne Biundo},
   title     = {Plan and Goal Recognition as {HTN} Planning},
   year      = {2018},
   publisher = {IEEE},
   pages     = {466--473},
   note      = {<b><i>This paper won the ICTAI 2018 CV Ramamoorthy Best Paper Award</i></b>},
   booktitle = {Proceedings of the 30th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2018)},
   abstract  = {Plan- and Goal Recognition (PGR) is the task of inferring the goals and plans of an agent based on its actions. Traditional approaches in PGR are based on a plan library including pairs of plans and corresponding goals. In recent years, the field successfully exploited the performance of planning systems for PGR. The main benefits are the presence of efficient solvers and well-established, compact formalisms for behavior representation. However, the expressivity of the STRIPS planning models used so far is limited, and models in PGR are often structured in a hierarchical way. We present the approach Plan and Goal Recognition as HTN Planning that combines the expressive but still compact grammar-like HTN representation with the advantage of using unmodified, off-the-shelf planning systems for PGR. Our evaluation shows that -- using our approach -- current planning systems are able to handle large models with thousands of possible goals, that the approach results in high recognition rates, and that it works even when the environment is partially observable, i.e., if the observer might miss observations.},
   doi       = {10.1109/ICTAI.2018.00078},
   url_Paper = {https://bercher.net/publications/2018/Hoeller2018bPlanRecognition.pdf},
  keywords   = {conference}
}

Plan- and Goal Recognition (PGR) is the task of inferring the goals and plans of an agent based on its actions. Traditional approaches in PGR are based on a plan library including pairs of plans and corresponding goals. In recent years, the field successfully exploited the performance of planning systems for PGR. The main benefits are the presence of efficient solvers and well-established, compact formalisms for behavior representation. However, the expressivity of the STRIPS planning models used so far is limited, and models in PGR are often structured in a hierarchical way. We present the approach Plan and Goal Recognition as HTN Planning that combines the expressive but still compact grammar-like HTN representation with the advantage of using unmodified, off-the-shelf planning systems for PGR. Our evaluation shows that – using our approach – current planning systems are able to handle large models with thousands of possible goals, that the approach results in high recognition rates, and that it works even when the environment is partially observable, i.e., if the observer might miss observations.

@InProceedings{Behnke2018DIYDemo,
   author    = {Behnke, Gregor and Schiller, Marvin and Kraus, Matthias and Pascal Bercher and Schmautz, Mario and Dorna, Michael and Minker, Wolfgang and Glimm, Birte and Biundo, Susanne},
   title     = {Instructing Novice Users on How to Use Tools in DIY Projects},
   year      = {2018},
   publisher = {IJCAI},
   booktitle = {Proceedings of the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence (IJCAI-ECAI 2018)},
   pages     = {5805--5807},
   doi       = {10.24963/ijcai.2018/844},
   abstract  = {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.},
   doi       = {10.24963/ijcai.2018/844},
   url_Paper = {https://bercher.net/publications/2018/Behnke2018DIYDemo.pdf},
  keywords   = {conference}
}

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.

@InProceedings{Hoeller2018ProgressionHeuristics,
  author                    = {Daniel H{\"{o}}ller and Pascal Bercher and Gregor Behnke and Susanne Biundo},
  title                     = {A Generic Method to Guide {HTN} Progression Search with Classical Heuristics},
  booktitle                 = {Proceedings of the 28th International Conference on Automated Planning and Scheduling ({ICAPS 2018})},
  note                      = {<b><i>This paper won the ICAPS 2018 Best Student Paper Award</i></b>},
  publisher                 = {{AAAI} Press},
  year                      = {2018},
  pages                     = {114--122},
  abstract                  = {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.},
  doi                       = {10.1609/icaps.v28i1.13900},
  url_Paper                 = {https://bercher.net/publications/2018/Hoeller2018ProgressionHeuristics.pdf},
  url_video_of_presentation = {https://www.youtube.com/watch?v=KOZuIkJaC0w},
  keywords                  = {conference}
} 

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.

@InProceedings{Bercher2017AdmissibleHTNHeuristic,
  Title      = {An Admissible {HTN} Planning Heuristic},
  Author     = {Pascal Bercher and Gregor Behnke and Daniel H{\"o}ller and Susanne Biundo},
  Year       = {2017},
  Booktitle  = {Proceedings of the 26th International Joint Conference on Artificial Intelligence ({IJCAI} 2017)},
  Publisher  = {IJCAI},
  Pages      = {480--488},
  doi        = {10.24963/ijcai.2017/68},
  keywords   = {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.},
  url_Paper  = {https://bercher.net/publications/2017/Bercher2017AdmissibleHTNHeuristic.pdf},
  url_Slides = {https://bercher.net/publications/2017/Bercher2017AdmissibleHTNHeuristicSlides.pdf},
  url_Poster = {https://bercher.net/publications/2017/Bercher2017AdmissibleHTNHeuristicPoster.pdf},
  keywords   = {conference}
}

@InProceedings{Behnke2017MIPChallenge,
  Title       = {Help me make a dinner! Challenges when assisting humans in action planning},
  Author      = {Gregor Behnke and Benedikt Leichtmann and Pascal Bercher and Daniel H\"oller and Verena Nitsch and Martin Baumann and Susanne Biundo},
  Year        = {2017},
  Booktitle   = {Proceedings of the 2nd International Conference on Companion Technology ({ICCT} 2017)},
  Publisher   = {IEEE},
  abstract    = {A promising field of application for cognitive technical systems is individualised user assistance for complex tasks. Here, a companion system usually uses an AI planner to solve the underlying combinatorial problem. Often, the use of a bare black-box planning system is not sufficient to provide individualised assistance, but instead the user has to be able to control the process that generates the presented advice. Such an integration guarantees that the user will be satisfied with the assistance s/he is given, trust the advice more, and is thus more likely to follow it. In this paper, we provide a general theoretical view on this process, called mixed-initiative planning, and derive several research challenges from it.},
  doi        = {10.1109/ICCT42709.2017.9151907},
  url_Paper  = {https://bercher.net/publications/2017/Behnke2017MIPChallenge.pdf},
  keywords   = {conference}
}

A promising field of application for cognitive technical systems is individualised user assistance for complex tasks. Here, a companion system usually uses an AI planner to solve the underlying combinatorial problem. Often, the use of a bare black-box planning system is not sufficient to provide individualised assistance, but instead the user has to be able to control the process that generates the presented advice. Such an integration guarantees that the user will be satisfied with the assistance s/he is given, trust the advice more, and is thus more likely to follow it. In this paper, we provide a general theoretical view on this process, called mixed-initiative planning, and derive several research challenges from it.

@InProceedings{Behnke2017MIPDemo,
  Title       = {SLOTH -- the Interactive Workout Planner},
  Author      = {Gregor Behnke and Florian Nielsen and Marvin Schiller and Pascal Bercher and Matthias Kraus and Wolfgang Minker and Birte Glimm and Susanne Biundo},
  Year        = {2017},
  Booktitle   = {Proceedings of the 2nd International Conference on Companion Technology ({ICCT} 2017)},
  Publisher   = {IEEE},
  doi         = {10.1109/COMPANION.2017.8287077},
  abstract    = {We present the mixed-initiative planning system SLOTH, which is designed to assist users in planning a fitness workout. Mixed-initiative planning systems are especially useful for companion systems, as they allow the seamless integration of the complex cognitive ability of planning into ambient assistance systems. This is achieved by integrating the user directly into the process of plan generation and thereby allowing him to specify these objectives and to be assisted in generating a plan that not only achieves his objectives, but at the same time also fits his preferences. We present the capabilities that are integrated into SLOTH and discuss the design choices and considerata that have to be taken into account when constructing a mixed-initiative planning system.},
  url_Paper  = {https://bercher.net/publications/2017/Behnke2017MIPDemo.pdf},
  keywords   = {conference}
}

We present the mixed-initiative planning system SLOTH, which is designed to assist users in planning a fitness workout. Mixed-initiative planning systems are especially useful for companion systems, as they allow the seamless integration of the complex cognitive ability of planning into ambient assistance systems. This is achieved by integrating the user directly into the process of plan generation and thereby allowing him to specify these objectives and to be assisted in generating a plan that not only achieves his objectives, but at the same time also fits his preferences. We present the capabilities that are integrated into SLOTH and discuss the design choices and considerata that have to be taken into account when constructing a mixed-initiative planning system.

@InProceedings{Schiller2017ModelingApproach,
  Title      = {A Paradigm for Coupling Procedural and Conceptual Knowledge in Companion Systems},
  Author     = {Marvin Schiller and Gregor Behnke and Mario Schmautz and Pascal Bercher and Matthias Kraus and Michael Dorna and Wolfgang Minker and Birte Glimm and Susanne Biundo},
  Year       = {2017},
  doi        = {10.1109/COMPANION.2017.8287072},
  Booktitle  = {Proceedings of the 2nd International Conference on Companion Technology ({ICCT} 2017)},
  Publisher  = {IEEE},
  abstract   = {Companion systems are technical systems that adjust their functionality to the needs and the situation of an individual user. Consequently, companion systems are strongly knowledge-based. We propose a modelling paradigm for integrating procedural and conceptual knowledge which is targeted at companion systems that require a combination of planning and reasoning capabilities. The presented methodology couples the hierarchical task network (HTN) planning formalism with an ontology-based knowledge representation, thereby minimising redundancies in modelling and enabling the use of state-of-the-art reasoning and planning tools on the shared knowledge model. The approach is applied within a prototype of a companion system that assists novice users in the do-it-yourself (DIY) domain with the planning and execution of home improvement projects involving the use of power tools.},
  url_Paper  = {https://bercher.net/publications/2017/Schiller2017ModelingApproach.pdf},
  keywords   = {conference}
}

Companion systems are technical systems that adjust their functionality to the needs and the situation of an individual user. Consequently, companion systems are strongly knowledge-based. We propose a modelling paradigm for integrating procedural and conceptual knowledge which is targeted at companion systems that require a combination of planning and reasoning capabilities. The presented methodology couples the hierarchical task network (HTN) planning formalism with an ontology-based knowledge representation, thereby minimising redundancies in modelling and enabling the use of state-of-the-art reasoning and planning tools on the shared knowledge model. The approach is applied within a prototype of a companion system that assists novice users in the do-it-yourself (DIY) domain with the planning and execution of home improvement projects involving the use of power tools.

@InProceedings{Bercher2016HybridPlanningComplexities,
  Title      = {More than a Name? On Implications of Preconditions and Effects of Compound {HTN} Planning Tasks},
  Author     = {Pascal Bercher and Daniel H{\"o}ller and Gregor Behnke and Susanne Biundo},
  Booktitle  = {Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016)},
  Year       = {2016},
  Pages      = {225--233},
  Publisher  = {IOS Press},
  doi        = {10.3233/978-1-61499-672-9-225},
  abstract   = {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. We therefore investigate the theoretical impact of such preconditions and effects -- depending on the legality criteria known from the literature -- for two of the most basic questions to planning: plan existence and plan verification. It turns out that for all investigated legality criteria, the respective problems are as hard as in the HTN setting and therefore equally expressive.},
  note      = {<strong>Erratum:</strong> Theorem 2 incorrectly claims P-membership for checking whether a plan is a solution to a primitive hybrid problem. This is however NP-complete. We corrected this in Section 3.2 of our follow-up paper "Tight Bounds for Hybrid Planning" (IJCAI-ECAI 2022).},
  url_Paper  = {https://bercher.net/publications/2016/Bercher2016HybridPlanningComplexities.pdf},
  url_Slides = {https://bercher.net/publications/2016/Bercher2016HybridPlanningComplexitiesSlides.pdf},
  keywords   = {conference}
}

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. We therefore investigate the theoretical impact of such preconditions and effects – depending on the legality criteria known from the literature – for two of the most basic questions to planning: plan existence and plan verification. It turns out that for all investigated legality criteria, the respective problems are as hard as in the HTN setting and therefore equally expressive.

@InProceedings{Behnke2016ChangeThePlan,
  Title      = {Change the Plan -- How Hard Can That Be?},
  Author     = {Gregor Behnke and Daniel H{\"o}ller and Pascal Bercher and Susanne Biundo},
  Booktitle  = {Proceedings of the 26th International Conference on Automated Planning and Scheduling ({ICAPS} 2016)},
  Year       = {2016},
  Pages      = {38--46},
  Publisher  = {{AAAI} Press},
  abstract   = {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.},
  doi        = {10.1609/icaps.v26i1.13754},
  url_Paper  = {https://bercher.net/publications/2016/Behnke2016ChangeThePlan.pdf},
  url_Slides = {https://bercher.net/publications/2016/Behnke2016ChangeThePlanSlides.pdf},
  keywords   = {conference}
}

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.

@InProceedings{Hoeller2016Expressivity,
  Title     = {Assessing the Expressivity of Planning Formalisms through the Comparison to Formal Languages},
  Author    = {Daniel H{\"o}ller and Gregor Behnke and Pascal Bercher and Susanne Biundo},
  Booktitle = {Proceedings of the 26th International Conference on Automated Planning and Scheduling ({ICAPS} 2016)},
  Year      = {2016},
  Pages     = {158--165},
  Publisher = {AAAI Press},
  abstract  = {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.},
  doi       = {10.1609/icaps.v26i1.13758},
  url_Paper = {https://bercher.net/publications/2016/Hoeller2016Expressivity.pdf},
  keywords  = {conference}
}

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.

@InProceedings{Alford2016BoundToPlan,
  Title     = {Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive {HTN} Problems},
  Author    = {Alford, Ron and Behnke, Gregor and H{\"o}ller, Daniel and Pascal Bercher and Biundo, Susanne and Aha, David},
  Booktitle = {Proceedings of the 26th International Conference on Automated Planning and Scheduling ({ICAPS} 2016)},
  Year      = {2016},
  Pages     = {20--28},
  Publisher = {{AAAI} Press},
  abstract  = {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.},
  doi       = {10.1609/icaps.v26i1.13765},
  url_Paper = {https://bercher.net/publications/2016/Alford2016BoundToPlan.pdf},
  keywords  = {conference}
}

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.

@InProceedings{Behnke2015MIPDiscussion,
  Title     = {A Unified Knowledge Base for Companion-Systems -- A Case Study in Mixed-Initiative Planning},
  Author    = {Gregor Behnke and Marvin Schiller and Denis Ponomaryov and Florian Nothdurft and Pascal Bercher and Wolfgang Minker and Birte Glimm and Susanne Biundo},
  Booktitle = {Proceedings of the International Symposium on Companion Technology (ISCT 2015)},
  Year      = {2015},
  Pages     = {43--48},
  abstract  = {Companion systems aim to extend the abilities of ordinary technical systems, for instance by modeling the user's situation, by recognizing the user's intentions, and by being able to interact with the user and to adapt to her/him. Such a system depends on planning capabilities to determine which actions are necessary to achieve a particular goal. In many situations it may not be appropriate for a companion system to develop plans on its own, but instead it has to integrate the user while creating the plan, i.e., it needs to be mixed-initiative. Based on earlier work, we demonstrate how a central knowledge base for a mixed-initiative planning system can be designed. We outline various benefts our approach brings to bear within a companion system. Lastly, we present several requests a user might issue towards the mixed-initiative planning system and how they can be answered by harnessing the knowledge base.},
  url_Paper = {https://bercher.net/publications/2015/Behnke2015MIPDiscussion.pdf},
  keywords  = {conference}
}

Companion systems aim to extend the abilities of ordinary technical systems, for instance by modeling the user's situation, by recognizing the user's intentions, and by being able to interact with the user and to adapt to her/him. Such a system depends on planning capabilities to determine which actions are necessary to achieve a particular goal. In many situations it may not be appropriate for a companion system to develop plans on its own, but instead it has to integrate the user while creating the plan, i.e., it needs to be mixed-initiative. Based on earlier work, we demonstrate how a central knowledge base for a mixed-initiative planning system can be designed. We outline various benefts our approach brings to bear within a companion system. Lastly, we present several requests a user might issue towards the mixed-initiative planning system and how they can be answered by harnessing the knowledge base.

@InProceedings{Bercher2015UserCenteredPlanning,
  Title      = {User-Centered Planning -- A Discussion on Planning in the Presence of Human Users},
  Author     = {Pascal Bercher and Daniel H{\"o}ller and Gregor Behnke and Susanne Biundo},
  Booktitle  = {Proceedings of the International Symposium on Companion Technology ({ISCT} 2015)},
  Year       = {2015},
  Pages      = {79--83},
  abstract   = {AI planning forms a core capability of intelligent systems. It enables goal directed behavior and allows systems to react adequately and flexibly to the current situation. Further, it allows systems to provide advice to a human user on how to reach his or her goals. Though the process of finding a plan is, by itself, a hard computational problem, some new challenges arise when involving a human user into the process. Plans have to be generated in a certain way, so that the user can be included into the plan generation process in case he or she wishes to; the plans should be presented to the user in an adequate way to prevent confusion or even rejection; to improve the trust in the system, it needs to be able to explain its behavior or presented plans. Here, we discuss these challenges and give pointers on how to solve them.},
  url_Paper  = {https://bercher.net/publications/2015/Bercher2015UserCenteredPlanning.pdf},
  url_Poster = {https://bercher.net/publications/2015/Bercher2015UserCenteredPlanningPoster.pdf},
  keywords   = {conference}
}

AI planning forms a core capability of intelligent systems. It enables goal directed behavior and allows systems to react adequately and flexibly to the current situation. Further, it allows systems to provide advice to a human user on how to reach his or her goals. Though the process of finding a plan is, by itself, a hard computational problem, some new challenges arise when involving a human user into the process. Plans have to be generated in a certain way, so that the user can be included into the plan generation process in case he or she wishes to; the plans should be presented to the user in an adequate way to prevent confusion or even rejection; to improve the trust in the system, it needs to be able to explain its behavior or presented plans. Here, we discuss these challenges and give pointers on how to solve them.

@InProceedings{Behnke2015CoherentModels,
  Title     = {Coherence Across Components in Cognitive Systems -- One Ontology to Rule Them All},
  Author    = {Gregor Behnke and Denis Ponomaryov and Marvin Schiller and Pascal Bercher and Florian Nothdurft and Birte Glimm and Susanne Biundo},
  Booktitle = {Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015)},
  Year      = {2015},
  Pages     = {1442--1449},
  Publisher = {{AAAI} Press},
  abstract  = {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.},
  url_Paper = {https://bercher.net/publications/2015/Behnke2015CoherentModels.pdf},
  keywords  = {conference}
}

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.

@InProceedings{Alford15TightTIHTNBoundsAbstract,
  Title     = {Tight Bounds for HTN planning with Task Insertion (Extended Abstract)},
  Author    = {Ron Alford and Pascal Bercher and David Aha},
  Booktitle = {Proceedings of the 8th Annual Symposium on Combinatorial Search ({SoCS} 2015)},
  Year      = {2015},
  Pages     = {221--222},
  Publisher = {AAAI Press},
  abstract  = {Hierarchical Task Network (HTN) planning with task insertion (TIHTN planning) is a variant of HTN planning. In HTN planning, the only means to alter task networks is to decompose compound tasks. In TIHTN planning, tasks may also be inserted directly. In this paper we provide tight complexity bounds for TIHTN planning along two axis: whether variables are allowed and whether methods must be totally ordered.},
  note      = {This is an extended abstract of the paper by Alford et al. with the same name.},
  doi       = {10.1609/socs.v6i1.18347},
  url_Paper = {https://bercher.net/publications/2015/Alford2015TightTIHTNBoundsAbstract.pdf},
  keywords  = {conference}
}

Hierarchical Task Network (HTN) planning with task insertion (TIHTN planning) is a variant of HTN planning. In HTN planning, the only means to alter task networks is to decompose compound tasks. In TIHTN planning, tasks may also be inserted directly. In this paper we provide tight complexity bounds for TIHTN planning along two axis: whether variables are allowed and whether methods must be totally ordered.

@InProceedings{ Alford2015TightHTNBounds,
   title                     = {Tight Bounds for {HTN} Planning},
   year                      = {2015},
   publisher                 = {AAAI Press},
   booktitle                 = {Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS 2015)},
   pages                     = {7--15},
   author                    = {Ron Alford and Pascal Bercher and David Aha},
   abstract                  = {Although HTN planning is in general undecidable, there are many syntactically identifiable sub-classes of HTN problems that can be decided. For these sub-classes, the decision procedures provide upper complexity bounds. Lower bounds were often not investigated in more detail, however. We generalize a propositional HTN formalization to one that is based upon a function-free first-order logic and provide tight upper and lower complexity results along three axes: whether variables are allowed in operator and method schemas, whether the initial task and methods must be totally ordered, and where recursion is allowed (arbitrary recursion, tail-recursion, and acyclic problems). Our findings have practical implications, both for the reuse of classical planning techniques for HTN planning, and for the design of efficient HTN algorithms},
   doi                       = {10.1609/icaps.v25i1.13721},
   url_Paper                 = {https://bercher.net/publications/2015/Alford2015TightHTNBounds.pdf},
   url_video_of_presentation = {https://www.youtube.com/watch?v=EFnsTzIVvUo},
  keywords                   = {conference}
}

Although HTN planning is in general undecidable, there are many syntactically identifiable sub-classes of HTN problems that can be decided. For these sub-classes, the decision procedures provide upper complexity bounds. Lower bounds were often not investigated in more detail, however. We generalize a propositional HTN formalization to one that is based upon a function-free first-order logic and provide tight upper and lower complexity results along three axes: whether variables are allowed in operator and method schemas, whether the initial task and methods must be totally ordered, and where recursion is allowed (arbitrary recursion, tail-recursion, and acyclic problems). Our findings have practical implications, both for the reuse of classical planning techniques for HTN planning, and for the design of efficient HTN algorithms

@InProceedings{Alford2015TightTIHTNBounds,
  Title     = {Tight Bounds for {HTN} planning with Task Insertion},
  Author    = {Ron Alford and Pascal Bercher and David Aha},
  Booktitle = {Proceedings of the 24th International Joint Conference on Artificial Intelligence ({IJCAI} 2015)},
  Year      = {2015},
  Pages     = {1502--1508},
  Publisher = {AAAI Press},
  abstract  = {Hierarchical Task Network (HTN) planning with Task Insertion (TIHTN planning) is a formalism that hybridizes classical planning with HTN planning by allowing the insertion of operators from outside the method hierarchy. This additional capability has some practical benefits, such as allowing more flexibility for design choices of HTN models: the task hierarchy may be specified only partially, since ``missing required tasks'' may be inserted during planning rather than prior planning by means of the (predefined) HTN methods. While task insertion in a hierarchical planning setting has already been applied in practice, its theoretical properties have not been studied in detail, yet -- only EXPSPACE membership is known so far. We lower that bound proving NEXPTIME-completeness and further prove tight complexity bounds along two axes: whether variables are allowed in method and action schemas, and whether methods must be totally ordered. We also introduce a new planning technique called acyclic progression, which we use to define provably efficient TIHTN planning algorithms.},
  url_Paper = {https://bercher.net/publications/2015/Alford2015TightTIHTNBounds.pdf},
  keywords  = {conference}
}

Hierarchical Task Network (HTN) planning with Task Insertion (TIHTN planning) is a formalism that hybridizes classical planning with HTN planning by allowing the insertion of operators from outside the method hierarchy. This additional capability has some practical benefits, such as allowing more flexibility for design choices of HTN models: the task hierarchy may be specified only partially, since ``missing required tasks'' may be inserted during planning rather than prior planning by means of the (predefined) HTN methods. While task insertion in a hierarchical planning setting has already been applied in practice, its theoretical properties have not been studied in detail, yet – only EXPSPACE membership is known so far. We lower that bound proving NEXPTIME-completeness and further prove tight complexity bounds along two axes: whether variables are allowed in method and action schemas, and whether methods must be totally ordered. We also introduce a new planning technique called acyclic progression, which we use to define provably efficient TIHTN planning algorithms.

@InProceedings{Nothdurft2015InterplayDialogPlanning,
  Title     = {The Interplay of User-Centered Dialog Systems and AI Planning},
  Author    = {Florian Nothdurft and Gregor Behnke and Pascal Bercher and Susanne Biundo and Minker, Wolfgang},
  Booktitle = {Proceedings of the 16th Annual Meeting of the Special Interest Group on Discourse and Dialogue ({SIGDIAL} 2015)},
  Year      = {2015},
  Pages     = {344--353},
  Publisher = {Association for Computational Linguistics},
  abstract  = {Technical systems evolve from simple dedicated task solvers to cooperative and competent assistants, helping the user with increasingly complex and demanding tasks. For this, they may proactively take over some of the users responsibilities and help to find or reach a solution for the user's task at hand, using e.g., Artificial Intelligence (AI) Planning techniques. However, this intertwining of user-centered dialog and AI planning systems, often called mixed-initiative planning (MIP), does not only facilitate more intelligent and competent systems, but does also raise new questions related to the alignment of AI and human problem solving. In this paper, we describe our approach on integrating AI Planning techniques into a dialog system, explain reasons and effects of arising problems, and provide at the same time our solutions resulting in a coherent, userfriendly and efficient mixed-initiative system. Finally, we evaluate our MIP system and provide remarks on the use of explanations in MIP-related phenomena.},
  doi       = {10.18653/v1/W15-4646},
  url_Paper = {https://bercher.net/publications/2015/Nothdurft2015InterplayDialogPlanning.pdf},
  keywords  = {conference}
}

Technical systems evolve from simple dedicated task solvers to cooperative and competent assistants, helping the user with increasingly complex and demanding tasks. For this, they may proactively take over some of the users responsibilities and help to find or reach a solution for the user's task at hand, using e.g., Artificial Intelligence (AI) Planning techniques. However, this intertwining of user-centered dialog and AI planning systems, often called mixed-initiative planning (MIP), does not only facilitate more intelligent and competent systems, but does also raise new questions related to the alignment of AI and human problem solving. In this paper, we describe our approach on integrating AI Planning techniques into a dialog system, explain reasons and effects of arising problems, and provide at the same time our solutions resulting in a coherent, userfriendly and efficient mixed-initiative system. Finally, we evaluate our MIP system and provide remarks on the use of explanations in MIP-related phenomena.

@InProceedings{Bercher2015AssemblyAssistantDemo,
  Title            = {A Planning-based Assistance System for Setting Up a Home Theater},
  Author           = {Pascal Bercher and Felix Richter and Thilo H\"ornle and Thomas Geier and Daniel H\"oller and Gregor Behnke and Florian Nothdurft and Frank Honold and Wolfgang Minker and Michael Weber and Susanne Biundo},
  Booktitle        = {Proceedings of the 29th National Conference on Artificial Intelligence ({AAAI} 2015)},
  pages            = {4264--4265},
  Year             = {2015},
  Doi              = {10.1609/aaai.v29i1.9274},
  Publisher        = {{AAAI Press}},
  abstract         = {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.},
  url_Paper        = {https://bercher.net/publications/2015/Bercher2015AssemblyAssistantDemo.pdf},
  url_domain-model = {https://bercher.net/publications/2014/Bercher2014PlanRepairExecuteExplainDomainModel.zip},
  keywords         = {conference}
}

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.

@InProceedings{Hoeller2014HTNLanguage,
  Title     = {Language Classification of Hierarchical Planning Problems},
  Author    = {Daniel H{\"o}ller and Gregor Behnke and Pascal Bercher and Susanne Biundo},
  Booktitle = {Proceedings of the 21st European Conference on Artificial Intelligence ({ECAI} 2014)},
  Year      = {2014},
  pages     = {447--452},
  publisher = {{IOS} Press},
  doi       = {10.3233/978-1-61499-419-0-447},
  abstract  = {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.},
  url_Paper = {https://bercher.net/publications/2014/Hoeller2014HTNLanguages.pdf},
  keywords  = {conference}
}

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.

@InProceedings{Bercher2014MMEHeuristicAndLandmarks,
  Title      = {Hybrid Planning Heuristics Based on Task Decomposition Graphs},
  Author     = {Pascal Bercher and Shawn Keen and Susanne Biundo},
  Booktitle  = {Proceedings of the 7th Annual Symposium on Combinatorial Search (SoCS 2014)},
  Year       = {2014},
  Pages      = {35--43},
  Publisher  = {AAAI Press},
  abstract   = {Hybrid Planning combines Hierarchical Task Network (HTN) planning with concepts known from Partial-Order Causal-Link (POCL) planning. We introduce novel heuristics for Hybrid Planning that estimate the number of necessary modifications to turn a partial plan into a solution. These estimates are based on the task decomposition graph that contains all decompositions of the abstract tasks in the planning domain. Our empirical evaluation shows that the proposed heuristics can significantly improve planning performance.},
  doi        = {10.1609/socs.v5i1.18323},
  url_Paper  = {https://bercher.net/publications/2014/Bercher2014MMEHeuristicAndLandmarks.pdf},
  url_Slides = {https://bercher.net/publications/2014/Bercher2014MMEHeuristicAndLandmarksSlides.pdf},
  keywords   = {conference}
}

Hybrid Planning combines Hierarchical Task Network (HTN) planning with concepts known from Partial-Order Causal-Link (POCL) planning. We introduce novel heuristics for Hybrid Planning that estimate the number of necessary modifications to turn a partial plan into a solution. These estimates are based on the task decomposition graph that contains all decompositions of the abstract tasks in the planning domain. Our empirical evaluation shows that the proposed heuristics can significantly improve planning performance.

@InProceedings{Bercher2014PlanRepairExecuteExplain,
  Title                  = {Plan, Repair, Execute, Explain -- How Planning Helps to Assemble your Home Theater},
  Author                 = {Pascal Bercher and Susanne Biundo and Thomas Geier and Thilo H\"ornle and Florian Nothdurft and Felix Richter and Bernd Schattenberg},
  Booktitle              = {Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014)},
  Year                   = {2014},
  Pages                  = {386--394},
  Publisher              = {{AAAI} Press},
  abstract               = {In various social, work-related, or educational contexts, an increasing demand for intelligent assistance systems can be observed. In this paper, we present a domain-independent approach that combines a number of planning and interaction components to realize advanced user assistance. Based on a hybrid planning formalism, the components provide facilities including the generation, execution, and repair as well as the presentation and explanation of plans. We demonstrate the feasibility of our approach by means of a system that aims to assist users in the assembly of their home theater. An empirical evaluation shows the benefit of such a supportive system, in particular for persons with a lack of domain expertise.},
  doi                    = {10.1609/icaps.v24i1.13664},
  url_Paper              = {https://bercher.net/publications/2014/Bercher2014PlanRepairExecuteExplain.pdf},
  url_Slides             = {https://bercher.net/publications/2014/Bercher2014PlanRepairExecuteExplainSlides.pdf},
  url_Slides-with-Videos = {https://bercher.net/publications/2014/Bercher2014PlanRepairExecuteExplainSlides.zip},
  url_domain-model       = {https://bercher.net/publications/2014/Bercher2014PlanRepairExecuteExplainDomainModel.zip},
  keywords               = {conference}
}

In various social, work-related, or educational contexts, an increasing demand for intelligent assistance systems can be observed. In this paper, we present a domain-independent approach that combines a number of planning and interaction components to realize advanced user assistance. Based on a hybrid planning formalism, the components provide facilities including the generation, execution, and repair as well as the presentation and explanation of plans. We demonstrate the feasibility of our approach by means of a system that aims to assist users in the assembly of their home theater. An empirical evaluation shows the benefit of such a supportive system, in particular for persons with a lack of domain expertise.

@InProceedings{Honold2014CompanionVideo,
  Title     = {Companion-Technology: Towards User- and Situation-Adaptive Functionality of Technical Systems},
  Author    = {Frank Honold and Pascal Bercher and Felix Richter and Florian Nothdurft and Thomas Geier and Roland Barth and Thilo H{\"o}rnle and Felix Sch{\"u}ssel and Stephan Reuter and Matthias Rau and Gregor Bertrand and Bastian Seegebarth and Peter Kurzok and Bernd Schattenberg and Wolfgang Minker and Michael Weber and Susanne Biundo},
  Booktitle = {10th International Conference on Intelligent Environments (IE 2014)},
  Year      = {2014},
  Pages     = {378--381},
  Publisher = {IEEE},
  doi       = {10.1109/IE.2014.60},
  abstract  = {The properties of multimodality, individuality, adaptability, availability, cooperativeness and trustworthiness are at the focus of the investigation of Companion Systems. In this article, we describe the involved key components of such a system and the way they interact with each other. Along with the article comes a video, in which we demonstrate a fully functional prototypical implementation and explain the involved scientific contributions in a simplified manner. The realized technology considers the entire situation of the user and the environment in current and past states. The gained knowledge reflects the context of use and serves as basis for decision-making in the presented adaptive system.},
  url_Paper = {https://bercher.net/publications/2014/Honold2014CompanionVideo.pdf},
  url_Video = {https://mirkwood.informatik.uni-ulm.de/sfbtrr62/SFB-TRR-62_Demonstrationsszenario_1_1080.mp4},
  keywords  = {conference}
}

The properties of multimodality, individuality, adaptability, availability, cooperativeness and trustworthiness are at the focus of the investigation of Companion Systems. In this article, we describe the involved key components of such a system and the way they interact with each other. Along with the article comes a video, in which we demonstrate a fully functional prototypical implementation and explain the involved scientific contributions in a simplified manner. The realized technology considers the entire situation of the user and the environment in current and past states. The gained knowledge reflects the context of use and serves as basis for decision-making in the presented adaptive system.

@InProceedings{Bercher2013POCL-DeleteRelaxation,
  Title      = {On Delete Relaxation in Partial-Order Causal-Link Planning},
  Author     = {Pascal Bercher and Thomas Geier and Felix Richter and Susanne Biundo},
  Booktitle  = {Proceedings of the 2013 IEEE 25th International Conference on Tools with Artificial Intelligence ({ICTAI} 2013)},
  Year       = {2013},
  Pages      = {674--681},
  doi        = {10.1109/ICTAI.2013.105},
  publisher  = {{IEEE} Computer Society},
  abstract   = {We prove a new complexity result for Partial-Order Causal-Link (POCL) planning, in which we study the hardness of refining a search node (i.e., a partial plan) to a valid solution given a delete effect-free domain model. While the corresponding decision problem is known to be polynomial in state-based search (where search nodes are states), it turns out to be intractable in the POCL setting. Since both of the currently best-informed heuristics for POCL planning are based on delete relaxation, we hope that our result sheds some new light on the problem of designing heuristics for POCL planning. Based on this result, we developed a new variant of one of these heuristics which incorporates more information of the current partial plan. We evaluate our heuristic on several domains of the early International Planning Competitions and compare it with other POCL heuristics from the literature.},
  url_Paper  = {https://bercher.net/publications/2013/Bercher2013POCL-DeleteRelaxation.pdf},
  url_Slides = {https://bercher.net/publications/2013/Bercher2013POCL-DeleteRelaxationSlides.pdf},
  keywords   = {conference}
}

We prove a new complexity result for Partial-Order Causal-Link (POCL) planning, in which we study the hardness of refining a search node (i.e., a partial plan) to a valid solution given a delete effect-free domain model. While the corresponding decision problem is known to be polynomial in state-based search (where search nodes are states), it turns out to be intractable in the POCL setting. Since both of the currently best-informed heuristics for POCL planning are based on delete relaxation, we hope that our result sheds some new light on the problem of designing heuristics for POCL planning. Based on this result, we developed a new variant of one of these heuristics which incorporates more information of the current partial plan. We evaluate our heuristic on several domains of the early International Planning Competitions and compare it with other POCL heuristics from the literature.

@InProceedings{Bercher2013POCLHeuristicsViaEncoding,
  author     = {Pascal Bercher and Thomas Geier and Susanne Biundo},
  title      = {Using State-Based Planning Heuristics for Partial-Order Causal-Link Planning},
  booktitle  = {Advances in Artificial Intelligence, Proceedings of the 36th German Conference on Artificial Intelligence ({KI} 2013)},
  year       = {2013},
  pages      = {1--12},
  publisher  = {Springer},
  doi        = {10.1007/978-3-642-40942-4_1},
  abstract   = {We present a technique which allows partial-order causal-link (POCL) planning systems to use heuristics known from state-based planning to guide their search. The technique encodes a given partially ordered partial plan as a new classical planning problem that yields the same set of solutions reachable from the given partial plan. As heuristic estimate of the given partial plan a state-based heuristic can be used estimating the goal distance of the initial state in the encoded problem. This technique also provides the first admissible heuristics for POCL planning, simply by using admissible heuristics from state-based planning. To show the potential of our technique, we conducted experiments where we compared two of the currently strongest heuristics from state-based planning with two of the currently best-informed heuristics from POCL planning.},
  url_Paper  = {https://bercher.net/publications/2013/Bercher2013POCLHeuristicsViaEncoding.pdf},
  url_Slides = {https://bercher.net/publications/2013/Bercher2013POCLHeuristicsViaEncodingSlides.pdf},
  keywords   = {conference}
}

We present a technique which allows partial-order causal-link (POCL) planning systems to use heuristics known from state-based planning to guide their search. The technique encodes a given partially ordered partial plan as a new classical planning problem that yields the same set of solutions reachable from the given partial plan. As heuristic estimate of the given partial plan a state-based heuristic can be used estimating the goal distance of the initial state in the encoded problem. This technique also provides the first admissible heuristics for POCL planning, simply by using admissible heuristics from state-based planning. To show the potential of our technique, we conducted experiments where we compared two of the currently strongest heuristics from state-based planning with two of the currently best-informed heuristics from POCL planning.

@InProceedings{Elkawkagy2012LandmarkStrategies,
  author     = {Mohamed Elkawkagy and Pascal Bercher and Bernd Schattenberg and Susanne Biundo},
  title      = {Improving Hierarchical Planning Performance by the Use of Landmarks},
  booktitle  = {Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI 2012)},
  year       = {2012},
  pages      = {1763--1769},
  publisher  = {{AAAI} Press},
  doi        = {10.1609/aaai.v26i1.8366},
  abstract   = {In hierarchical planning, landmarks are tasks that occur on every search path leading from the initial plan to a solution. In this work, we present novel domain-independent planning strategies based on such hierarchical landmarks. Our empirical evaluation on four benchmark domains shows that these landmark-aware strategies outperform established search strategies in many cases.},
  url_Paper  = {https://bercher.net/publications/2012/Elkawkagy2012LandmarkStrategies.pdf},
  url_Slides = {https://bercher.net/publications/2012/Elkawkagy2012LandmarkStrategiesSlides.pdf},
  url_Poster = {https://bercher.net/publications/2012/Elkawkagy2012LandmarkStrategiesPoster.pdf},
  keywords   = {conference}
}

In hierarchical planning, landmarks are tasks that occur on every search path leading from the initial plan to a solution. In this work, we present novel domain-independent planning strategies based on such hierarchical landmarks. Our empirical evaluation on four benchmark domains shows that these landmark-aware strategies outperform established search strategies in many cases.

@InProceedings{Bercher2012HTNPreferenceHeuristic,
  author     = {Pascal Bercher and Susanne Biundo},
  title      = {A Heuristic for Hybrid Planning with Preferences},
  booktitle  = {Proceedings of the 25th International Florida Artificial Intelligence Research Society Conference ({FLAIRS} 2012)},
  year       = {2012},
  publisher  = {{AAAI} Press},
  pages      = {120--123},
  abstract   = {In this paper, we introduce an admissible heuristic for hybrid planning with preferences. Hybrid planning is the fusion of hierarchical task network (HTN) planning with partial order causal link (POCL) planning. We consider preferences to be soft goals -- facts one would like to see satisfied in a goal state, but which do not have to hold necessarily. Our heuristic estimates the best quality of any solution that can be developed from the current plan under consideration. It can thus be used by any branch-and-bound algorithm that performs search in the space of plans to prune suboptimal plans from the search space.},
  url_Paper  = {https://bercher.net/publications/2012/Bercher2012HTNPreferenceHeuristic.pdf},
  url_Poster = {https://bercher.net/publications/2012/Bercher2012HTNPreferenceHeuristicPoster.pdf},
  keywords   = {conference}
}

In this paper, we introduce an admissible heuristic for hybrid planning with preferences. Hybrid planning is the fusion of hierarchical task network (HTN) planning with partial order causal link (POCL) planning. We consider preferences to be soft goals – facts one would like to see satisfied in a goal state, but which do not have to hold necessarily. Our heuristic estimates the best quality of any solution that can be developed from the current plan under consideration. It can thus be used by any branch-and-bound algorithm that performs search in the space of plans to prune suboptimal plans from the search space.

@InProceedings{Geier2011TIHTNDecidability,
  author     = {Thomas Geier and Pascal Bercher},
  title      = {On the Decidability of {HTN} Planning with Task Insertion},
  booktitle  = {Proceedings of the 22nd International Joint Conference on Artificial Intelligence ({IJCAI} 2011)},
  year       = {2011},
  pages      = {1955--1961},
  publisher  = {{AAAI} Press},
  abstract   = {The field of deterministic AI planning can roughly be divided into two approaches - classical state-based planning and hierarchical task network (HTN) planning. The plan existence problem of the former is known to be decidable while it has been proved undecidable for the latter. When extending HTN planning by allowing the unrestricted insertion of tasks and ordering constraints, one obtains a form of planning which is often referred to as "hybrid planning". We present a simplified formalization of HTN planning with and without task insertion. We show that the plan existence problem is undecidable for the HTN setting without task insertion and that it becomes decidable when allowing task insertion. In the course of the proof, we obtain an upper complexity bound of EXPSPACE for the plan existence problem for propositional HTN planning with task insertion.},
  url_Paper  = {https://bercher.net/publications/2011/Geier2011TIHTNDecidability.pdf},
  url_Poster = {https://bercher.net/publications/2011/Geier2011TIHTNDecidabilityPoster.pdf},
  keywords   = {conference}
}

The field of deterministic AI planning can roughly be divided into two approaches - classical state-based planning and hierarchical task network (HTN) planning. The plan existence problem of the former is known to be decidable while it has been proved undecidable for the latter. When extending HTN planning by allowing the unrestricted insertion of tasks and ordering constraints, one obtains a form of planning which is often referred to as "hybrid planning". We present a simplified formalization of HTN planning with and without task insertion. We show that the plan existence problem is undecidable for the HTN setting without task insertion and that it becomes decidable when allowing task insertion. In the course of the proof, we obtain an upper complexity bound of EXPSPACE for the plan existence problem for propositional HTN planning with task insertion.

@InProceedings{Mattmueller2010NondeterministicPlanning,
  author    = {Robert Mattm{\"u}ller and Manuela Ortlieb and Malte Helmert and Pascal Bercher},
  title     = {Pattern Database Heuristics for Fully Observable Nondeterministic Planning},
  booktitle = {Proceedings of the 20th International Conference on Automated Planning and Scheduling ({ICAPS} 2010)},
  year      = {2010},
  pages     = {105--112},
  publisher = {{AAAI} Press},
  abstract  = {When planning in an uncertain environment, one is often interested in finding a contingent plan that prescribes appropriate actions for all possible states that may be encountered during the execution of the plan. We consider the problem of finding strong and strong cyclic plans for fully observable nondeterministic (FOND) planning problems. The algorithm we choose is LAO*, an informed explicit state search algorithm. We investigate the use of pattern database (PDB) heuristics to guide LAO* towards goal states. To obtain a fully domain-independent planning system, we use an automatic pattern selection procedure that performs local search in the space of pattern collections. The evaluation of our system on the FOND benchmarks of the Uncertainty Part of the International Planning Competition 2008 shows that in selected domains our approach is competitive with symbolic regression search in terms of problem coverage and speed, and that plan sizes are often significantly smaller than with symbolic regression search.},
  doi       = {10.1609/icaps.v20i1.13408},
  url_Paper = {https://bercher.net/publications/2010/Mattmueller2010NondeterministicPlanning.pdf},
  keywords  = {conference}
}

When planning in an uncertain environment, one is often interested in finding a contingent plan that prescribes appropriate actions for all possible states that may be encountered during the execution of the plan. We consider the problem of finding strong and strong cyclic plans for fully observable nondeterministic (FOND) planning problems. The algorithm we choose is LAO*, an informed explicit state search algorithm. We investigate the use of pattern database (PDB) heuristics to guide LAO* towards goal states. To obtain a fully domain-independent planning system, we use an automatic pattern selection procedure that performs local search in the space of pattern collections. The evaluation of our system on the FOND benchmarks of the Uncertainty Part of the International Planning Competition 2008 shows that in selected domains our approach is competitive with symbolic regression search in terms of problem coverage and speed, and that plan sizes are often significantly smaller than with symbolic regression search.

@InProceedings{Bercher2009FONDWithPDBHeuristics,
  author     = {Pascal Bercher and Robert Mattm{\"u}ller},
  title      = {Solving Non-deterministic Planning Problems with Pattern Database Heuristics},
  booktitle  = {Advances in Artificial Intelligence, Proceedings of the 32nd German Conference on Artificial Intelligence ({KI} 2009)},
  year       = {2009},
  pages      = {57--64},
  publisher  = {Springer},
  doi        = {10.1007/978-3-642-04617-9_8},
  abstract   = {Non-determinism arises naturally in many real-world applications of action planning. Strong plans for this type of problems can be found using AO* search guided by an appropriate heuristic function. Most domain-independent heuristics considered in this context so far are based on the idea of ignoring delete lists and do not properly take the non-determinism into account. Therefore, we investigate the applicability of pattern database (PDB) heuristics to non-deterministic planning. PDB heuristics have emerged as rather informative in a deterministic context. Our empirical results suggest that PDB heuristics can also perform reasonably well in non-deterministic planning. Additionally, we present a generalization of the pattern additivity criterion known from classical planning to the non-deterministic setting.},
  url_Paper  = {https://bercher.net/publications/2009/Bercher2009FONDWithPDBHeuristics.pdf},
  url_Slides = {https://bercher.net/publications/2009/Bercher2009FONDWithPDBHeuristicsSlides.pdf},
  keywords   = {conference}
}

Non-determinism arises naturally in many real-world applications of action planning. Strong plans for this type of problems can be found using AO* search guided by an appropriate heuristic function. Most domain-independent heuristics considered in this context so far are based on the idea of ignoring delete lists and do not properly take the non-determinism into account. Therefore, we investigate the applicability of pattern database (PDB) heuristics to non-deterministic planning. PDB heuristics have emerged as rather informative in a deterministic context. Our empirical results suggest that PDB heuristics can also perform reasonably well in non-deterministic planning. Additionally, we present a generalization of the pattern additivity criterion known from classical planning to the non-deterministic setting.

@InProceedings{Bercher2008FONDPGHeuristic,
  author               = {Pascal Bercher and Robert Mattm{\"u}ller},
  title                = {A Planning Graph Heuristic for Forward-Chaining Adversarial Planning},
  booktitle            = {Proceedings of the 18th European Conference on Artificial Intelligence ({ECAI} 2008)},
  year                 = {2008},
  pages                = {921--922},
  publisher            = {{IOS} Press},
  doi                  = {10.3233/978-1-58603-891-5-921},
  abstract             = {In contrast to classical planning, in adversarial planning, the planning agent has to face an adversary trying to prevent him from reaching his goals. In this paper, we investigate a forwardchaining approach to adversarial planning based on the AO* algorithm. The exploration of the underlying AND/OR graph is guided by a heuristic evaluation function, inspired by the relaxed planning graph heuristic used in the FF planner. Unlike FF, our heuristic uses an adversarial planning graph with distinct proposition and action layers for the protagonist and antagonist. First results suggest that in certain planning domains, our approach yields results competitive with the state of the art.},
  note                 = {There is also a (rather detailed) technical report about this work with the same title.},
  url_Paper            = {https://bercher.net/publications/2008/Bercher2008FONDPGHeuristic.pdf},
  url_Technical-report = {https://bercher.net/publications/2008/Bercher2008FONDPGHeuristicTR.pdf},
  keywords             = {conference}
}

In contrast to classical planning, in adversarial planning, the planning agent has to face an adversary trying to prevent him from reaching his goals. In this paper, we investigate a forwardchaining approach to adversarial planning based on the AO* algorithm. The exploration of the underlying AND/OR graph is guided by a heuristic evaluation function, inspired by the relaxed planning graph heuristic used in the FF planner. Unlike FF, our heuristic uses an adversarial planning graph with distinct proposition and action layers for the protagonist and antagonist. First results suggest that in certain planning domains, our approach yields results competitive with the state of the art.