@inproceedings{Teixeira2023PlanningFromOntology, author = {Milene Santos Teixeira and Michael Welt and Raphael Chis and Birte Glimm}, title = {Challenges on Deriving Planning Problems from Ontologies}, booktitle = {Proceedings of the 1st International Planning and Ontology Workshop}, publisher = {CEUR-WS.org}, year = {2023}, url_paper = {https://ceur-ws.org/Vol-3493/short-paper-1.pdf} } @inproceedings{Glimm2022ConceptAbduction, author = {Birte Glimm and Yevgeny Kazakov and Michael Welt}, title = {Concept Abduction for Description Logics}, booktitle = {Proceedings of the 35th International Workshop on Description Logics (DL 2022)}, publisher = {CEUR-WS.org}, year = {2022}, url_paper = {https://ceur-ws.org/Vol-3263/paper-11.pdf} } @inproceedings{Bavandpour2025DC, title = {Automated Modelling Assistance for Creation of Planning Models}, author = {Nader Karimi Bavandpour}, Booktitle = {Doctoral Consortium at ICAPS 2025 (ICAPS DC 2025)}, year = {2025} } @inproceedings{Lutalo2022AngryAgent, title = {Agent X: Improving Exploration vs Exploitation in the State of the Art Angry Birds AI}, author = {Daniel Lutalo}, booktitle = {2022 IEEE Conference on Games (CoG 2022)}, pages = {330--337}, year = {2022}, publisher = {IEEE}, doi = {10.1109/CoG51982.2022.9893625}, abstract = {AI agents have successfully employed deep reinforcement learning methods to surpass human performance in various new tasks over the past decade, notably including the domain of games. However, Angry Birds requires complex physical and spacial reasoning that is yet to be captured by such means. We present our logic-based Angry Birds AI which won the 2021 IJCAI AIBIRDS competition and propose a simple new method we call Second Order Thompson Sampling (SOTS) which allows for fine-tuning the balance between exploration and exploitation. We cover the competition scores of our entrant Agent X, its predecessor - the former state of the art Bambirds 2019, and the new and improved Bambirds 2021. We find that our agent has the best all-round performance, but would gain a lot by incorporating the improvements of Bambirds 2021. We list other potential areas of improvement for a future superhuman Angry Birds AI.} } @inproceedings{Lauer2025ConstrainingActionRepetitions, author = {Pascal Lauer}, booktitle = {Proceedings of the 14th Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2025)}, title = {Arguments in Favor of Allowing a Modeler to Constrain Action Repetitions}, url_Paper = {https://fai.cs.uni-saarland.de/lauer/papers/keps2025.pdf}, year = {2025}, abstract = {It is increasingly recognized that adding additional constraints to a planning domain can significantly enhance expressiveness and solvability. In this paper, we advocate for bounding action repetitions, i.e., the number of times an action occurs in a plan. We show that bounds on action repetitions occur naturally in many domains and, when enforced, reduce computational complexity. In particular, we show that bounding all actions reduces the complexity of plan existence to NP. We also identify planning tasks where plan existence remains NP-complete when bounding only some actions.} } @inproceedings{Lauer2025PotentialHeuristics, author = {Pascal Lauer and Daniel Fi{\v{s}}er}, booktitle = {Proceedings of the 35th International Conference on Automated Planning and Scheduling (ICAPS 2025)}, title = {Potential Heuristics: Weakening Consistency Constraints}, year = {2025}, doi = {10.1609/icaps.v35i1.36121}, publisher = {AAAI Press}, abstract = {In classical planning, admissible potential heuristics are computed by solving linear programs (LPs) with constraints expressing consistency and goal-awareness of the heuristic. Potential heuristics can return negative estimates. So, given a potential heuristic h^P, the actual heuristic used in search is another heuristic defined as h^P_0+(s) = max(h^P(s),0) for every reachable state s. In this paper, we reformulate the LP constraints for consistency of h^P so that they ensure consistency of h^P_0+ instead. This leads to more informative heuristics with positive impact on the overall performance in exchange for a more time and memory demanding computation using mixed integer linear programs instead of LPs.}, pages = {218--222}, url_Paper = {https://fai.cs.uni-saarland.de/lauer/papers/icaps25-potentials.pdf} } @inproceedings{Lauer2025LiftedHeuristics, author = {Pascal Lauer and {\'A}lvaro Torralba and Daniel H{\"o}ller and J{\"o}rg Hoffmann}, booktitle = {Proceedings of the 35th International Conference on Automated Planning and Scheduling (ICAPS 2025)}, title = {Continuing the Quest for Polynomial Time Heuristics in PDDL Input Size: Tractable Cases for Lifted hAdd}, year = {2025}, publisher = {AAAI Press}, doi = {10.1609/icaps.v35i1.36103}, abstract = {Recent interest in solving planning tasks, where full grounding is infeasible, has highlighted the need to compute heuristics at a lifted level. We turn our attention to the evaluation of the $h^{add}$ heuristic, which is an important cornerstone in many classical planning approaches, including the best performing lifted planning approach. We show that $h^{add}$'s grounded efficiency does not extend to lifted tasks, where the computation is EXPTIME-complete. This prompts to identify tractability islands matching practical use cases. We identify two, where a lifted computation is feasible while grounding may fail: The first constraints to acyclic action schemata and bounds predicate arity. For the second case we introduce a novel computation, operating without grounding. Assuming the extraction encounters only acyclic conditions, and $h^{add}$ values per subgoal are bounded, it remains tractable. (Even with unbounded predicate and action arity.) In an empirical evaluation of the new technique, we observe complementary behavior to the existing lifted forward $h^{add}$ evaluation. Combining both sets a new state-of-the-art in pure-heuristic performance on the hard-to-ground benchmarks.}, pages = {74--83} } @Misc{Lauer2025Code, author = {Pascal Lauer and {\'A}lvaro Torralba and Daniel H{\"o}ller and J{\"o}rg Hoffmann}, title = {Code and Appendix for paper: ``Continuing the Quest for Polynomial Time Heuristics in PDDL Input Size: Tractable Cases for Lifted hAdd''}, year = {2025}, doi = {10.5281/zenodo.15323404}, publisher = {Zenodo} } @inproceedings{Lauer2024LiftedhAdd, author = {Pascal Lauer and {\'{A}}lvaro Torralba and Daniel H{\"{o}}ller and J{\"{o}}rg Hoffmann}, booktitle = {Proceedings of the 16th Workshop on Heuristic Search for Domain-Independent Planning (HSDIP 2024)}, note = {This paper is the workshop version of a paper by Lauer et al. at ICAPS 2025. Please refer to the conference version instead.}, title = {A Lifted Backward Computation of hAdd}, url_Paper = {https://icaps24.icaps-conference.org/program/workshops/hsdip-papers/paper_9.pdf}, url_Slides = {https://fai.cs.uni-saarland.de/lauer/talks/hsdip-2024.pdf}, year = {2024}, abstract = {Recent interest in solving planning tasks where full grounding is infeasible has brought attention to how to compute heuristics to guide the search at a lifted level. h add is a well understood heuristic for classical planning. Methods to compute h add perform a forward fix-point computation, as this takes polynomial time with respect to the grounded representation. However, this computational efficiency does not carry over to lifted planning tasks, where it is EXPTIME-complete to compute hadd. In this paper, we introduce a novel approach for computing h add on lifted planning tasks. Our approach proceeds backwards, constructing a fully lifted regression graph whose nodes are assessed using conjunctive query evaluation. We provide a complexity analysis and show that our backward computation is complementary to the traditional forward computation. Our empirical evaluation confirms that there are significant differences in the performance of both methods in each domain. Overall, both methods are very complementary, and their combination advances the state-of-the-art in lifted h add computations.} } @article{Gros2019Amazeing, title = {{aMAZEing} Programming-Providing {SKILLs} to Fellow Students}, author = {Timo P. Gros and Pascal L. Held and Pascal Lauer and Niklas O. Metzger and Kallistos Weis}, journal = {SKILL 2019-Studierendenkonferenz Informatik}, year = {2019}, publisher = {Gesellschaft f{\"u}r Informatik e.V.} } @inproceedings{Lauer2020LMCut, title = {Beating LM-cut with LM-cut: Quick Cutting and Practical Tie Breaking for the Precondition Choice Function}, author = {Pascal Lauer and Maximilian Fickert}, booktitle = {Proceedings of the 12th Workshop on Heuristics and Search for Domain-independent Planning (HSDIP 2020)}, year = {2020}, url_Paper_PDF = {https://icaps20subpages.icaps-conference.org/wp-content/uploads/2020/10/proceedings.pdf#page=13}, url_Video_of_Presentation = {https://www.youtube.com/watch?v=n03g6Y6zJWI}, pages = {9--15}, abstract = {LM-cut is one of the most popular heuristics in optimal planning that computes strong admissible estimates of the perfect delete relaxation heuristic h+. The heuristic iteratively computes disjunctive action landmarks for the current state, reducing their action costs until no more landmarks with remaining action costs can be found. These landmarks are generated by finding cuts in the justification graph, which depends on a precondition choice function mapping each action to its most expensive precondition according to hmax. This precondition is not necessarily unique, yet the performance of the heuristic heavily depends on this choice. We introduce and analyze several new tie breaking strategies for the precondition choice function, and evaluate their effectiveness on the IPC benchmarks. Furthermore, we suggest a modification to the computation of the cut, which trades a negligible loss in heuristic accuracy for a significant speedup of the LM-cut computation.} } @inproceedings{Lauer2021FeasibleDelRelax, title = {Polynomial-Time in PDDL Input Size: Making the Delete Relaxation Feasible for Lifted Planning}, author = {Pascal Lauer and Alvaro Torralba and Daniel Fiser and Daniel H\"{o}ller and Julia Wichlacz and Joerg Hoffmann}, year = {2021}, booktitle = {Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021)}, pages = {4119--4126}, doi = {10.24963/ijcai.2021/567}, publisher = {IJCAI}, url_Paper = {https://fai.cs.uni-saarland.de/wichlacz/papers/polynomial_time_in_pddl_input.pdf}, url_video_of_presentation = {https://www.youtube.com/watch?v=ZqjXqMBM7KEI}, url_Code = {https://zenodo.org/record/4768791#.Y2qxmuzMLuU}, abstract = {Polynomial-time heuristic functions for planning are commonplace since 20 years. But polynomial-time in which input? Almost all existing approaches are based on a grounded task representation, not on the actual PDDL input which is exponentially smaller. This limits practical applicability to cases where the grounded representation is “small enough”. Previous attempts to tackle this problem for the delete relaxation leveraged symmetries to reduce the blow-up. Here we take a more radical approach, applying an additional relaxation to obtain a heuristic function that runs in time polynomial in the size of the PDDL input. Our relaxation splits the predicates into smaller predicates of fixed arity K. We show that computing a relaxed plan is still NP-hard (in PDDL input size) for K ≥ 2, but is polynomial-time for K = 1. We implement a heuristic function for K = 1 and show that it can improve the state of the art on benchmarks whose grounded representation is large.} } @Misc{Lauer2021FeasibleDelRelaxCode, author = {Pascal Lauer and {\'A}lvaro Torralba and Daniel Fi\v{s}er and Daniel H{\"o}ller and Julia Wichlacz and J{\"o}rg Hoffmann}, title = {Code and benchmarks from the paper ``Polynomial-Time in PDDL Input Size: Making the Delete Relaxation Feasible for Lifted Planning''}, year = {2021}, doi = {10.5281/zenodo.4768790}, publisher = {Zenodo} } @PhdThesis{Olz2024Dissertation, author = {Conny Olz}, title = {Exploring the Hierarchy: Extracting and Exploiting State Information of Compound Tasks in {HTN} Planning}, school = {Ulm University}, year = {2024}, abstract = {Automated Planning is a domain-independent paradigm that can be applied to solve various problems in many areas such as robotics, autonomous factories, or assistance systems by finding a sequence of actions that an agent needs to perform in order to achieve a desired goal. In planning, the application domain is typically described using states and actions. States are represented as sets of propositional state features, and actions are characterized by their respective preconditions and effects, which in turn represent state changes. Hierarchical Task Network (HTN) planning extends this basic framework by introducing compound actions (also called abstract or compound tasks), which need to be refined into less abstract and eventually primitive actions according to predefined refinement rules.

One limitation of the conventional HTN planning formalism is the lack of explicit state-change information for compound actions. These actions primarily serve as placeholders for potential sequences of primitive and compound actions, without clearly stating their implications on states. Such insights, however, can be valuable for both planning systems and domain modelers. This dissertation addresses this insufficiency by deriving state information of compound actions based on their refinements, focusing on three core contributions in total-order HTN planning:

Firstly, a theoretical foundation is provided by formally defining several types of inferred preconditions and effects for compound actions and analyzing their computational complexity. The latter revealed that while directly computing these inferences is computationally intractable, an approximation exists that can be computed in polynomial time.

Secondly, leveraging these inferred preconditions and effects, a look-ahead technique designed for search-based HTN planning systems has been developed. This novel technique can reduce the search space by identifying dead-ends and inevitable decomposition choices. Empirical evaluations show that incorporating this approach considerably improves the performance of state-of-the-art HTN planning systems, leading to several wins at the latest International Planning Competition. Thus, it pushes the boundaries of how quickly practical problems can be solved.

Lastly, motivated by considerations for the look-ahead technique, the concept of conjunctive possible effects is introduced, which goes beyond the before-mentioned types of inferred preconditions and effects. These offer a more nuanced representation of state changes and are found to be computationally challenging even under several relaxations but fixed-parameter tractable for a fixed number of facts, making them practically useful for smaller problem instances. As a byproduct, this investigation also revealed new complexity results for the plan existence problem under precondition-relaxation.}, doi = {10.18725/OPARU-53481}, url_Dissertation = {https://oparu.uni-ulm.de/bitstreams/6ec28966-8f42-439b-a934-65e10f89ac3d/download} } @InProceedings{Lindner22BeyondCausalLinks, author = {Felix Lindner and Conny Olz}, title = {Step-by-Step Task Plan Explanations Beyond Causal Links}, booktitle = {2022 31st IEEE International Conference on Robot \& Human Interactive Communication (RO-MAN)}, year = {2022}, publisher = {IEEE}, pages = {45--51}, doi = {10.1109/RO-MAN53752.2022.9900590} } @PhdThesis{Lin2025Dissertation, author = {Songtuan Lin}, title = {Automated Modeling Support for Automated Planning}, school = {Australian National University}, year = {2025}, abstract = {Automated planning is concerned with the task of finding a sequence of actions to achieve a certain goal. Theoretical investigations have shown that many practical scenarios, e.g., logistics, factories, and Mars rovers, can be modeled using planning frameworks. In spite of that, Automated Planning is not widely deployed in practice, especially outside academia. One major reason for this is the complexity of modeling a practical problem as a planning problem, which necessitates techniques for automated modeling support. In this talk, I would like to address two critical problems in this direction, namely, how to check whether a planning model is constructed correctly and how to repair a flawed planning model. Our approaches for solving these two problems are originated from the common debugging paradigm in programming, i.e., by providing test cases. In our context, a test case is an action sequence that must be a solution (i.e., is feasible and can achieve the goal) if the planning model is flawless. More concretely, we could validate a planning model by checking whether all test cases we provide pass, i.e., whether all provided action sequences are indeed solutions. If some test cases fail, then we know that there are some issues in the planning model, and we call these failed test cases counter-example action sequences (because they are supposed to be solutions but are actually not due to the errors in the model). The repairs can then be made to the planning model which turn all counter-example action sequences into solutions. In my dissertation, I will discuss the computational complexity of verifying whether an action sequence is a solution to a planning problem (i.e., the plan verification problem) and of correcting a planning model by turning counter-example action sequences into solutions. On top of that, I will also introduce some practical approaches we developed for solving those two problems. Lastly, some alternative frameworks for modeling support will also be discussed.}, doi = {10.25911/FCYW-1W77}, url_Dissertation = {https://openresearch-repository.anu.edu.au/bitstreams/73186331-5225-4095-8ee6-f39f8048755c/download} } @InProceedings{Li2024DomainLearning, author = {Ruiqi Li and Leyang Cui and Songtuan Lin and Patrik Haslum}, booktitle = {Proceedings of the 38th AAAI Conference on Artificial Intelligence (AAAI 2024)}, title = {NaRuto: Automatically Acquiring Planning Models from Narrative Texts}, year = {2024}, publisher = {AAAI Press}, abstract = {Domain model acquisition has been identified as a bottleneck in the application of planning technology, especially within narrative planning. Learning action models from narrative texts in an automated way is essential to overcome this barrier, but challenging because of the inherent complexities of such texts. We present an evaluation of planning domain models derived from narrative texts using our fully automated, unsupervised system, NaRuto. Our system combines structured event extraction, predictions of commonsense event relations, and textual contradictions and similarities. Evaluation results show that NaRuto generates domain models of significantly better quality than existing fully automated methods, and even sometimes on par with those created by semi-automated methods, with human assistance.}, pages = {20194--20202} } @article{Li2023DomainLearning, author = {Ruiqi Li and Leyang Cui and Songtuan Lin and Patrik Haslum}, title = {Automated Action Model Acquisition from Narrative Texts}, journal = {CoRR}, volume = {abs/2307.10247}, year = {2023}, url = {https://arxiv.org/abs/2307.10247}, doi = {10.48550/ARXIV.2307.10247}, url_Paper = {https://arxiv.org/pdf/2307.10247.pdf}, abstract = {Action models, which take the form of precondition/effect axioms, facilitate causal and motivational connections between actions for AI agents. Action model acquisition has been identified as a bottleneck in the application of planning technology, especially within narrative planning. Acquiring action models from narrative texts in an automated way is essential, but challenging because of the inherent complexities of such texts. We present NaRuto, a system that extracts structured events from narrative text and subsequently generates planning-language-style action models based on predictions of commonsense event relations, as well as textual contradictions and similarities, in an unsupervised manner. Experimental results in classical narrative planning domains show that NaRuto can generate action models of significantly better quality than existing fully automated methods, and even on par with those of semi-automated methods.} } @InProceedings{Lin2023FLTLvsLTL, author = {Songtuan Lin}, booktitle = {Proceedings of the 31st AAAI Spring Symposium Series (SSS 2023)}, title = {Comparing the Expressivity of {STRIPS} Planning with Finite-{LTL} vs. {LTL}}, year = {2023}, abstract = {STRIPS is one of the most widely used planning frameworks for modeling planning problems in Automated Planning. A significant extension to STRIPS is allowing it to specify temporal constraints over the execution of a plan. One way to do so is to fuse the STRIPS framework with finite-LTL (f-LTL) or LTL. In this paper, I will discuss some results from our previous work about the expressivity of such combinations. Specifically, the expressivity is measured in terms of the class of formal languages that can be expressed by the framework.}, url_Paper = {https://bercher.net/publications/2023/Lin2023FLTLvsLTL.pdf}, url_Slides = {https://ltlf-symposium.github.io/assets/slides/SongtuanLin.pdf}, url_webpage = {https://ltlf-symposium.github.io/} } @InProceedings{Lin2022ICAPS-DC, author = {Songtuan Lin}, title = {Modeling Assistance for AI Planning From the Perspective of Model Reconciliation}, booktitle = {Proceedings of the 20th ICAPS Doctoral Consortium (ICAPS DC 2022)}, year = {2022}, pages = {36--40}, abstract = {Providing modeling assistance to domain modelers is a prominent challenge in incorporating humans into planning processes. Many efforts have been devoted to this direction in classical planning, however, only few works have been done in hierarchical planning. In this thesis, we will study a methodology for providing modeling assistance in HTN planning, which is the most commonly used hierarchical planning framework. Particularly, we will address two bottleneck problems for this purpose, namely domain model validation and domain model refinements. For the former one, we propose an approach based on plan verification, and for the latter, we view it as a model reconciliation problem and will study a novel approach for solving it.}, url_paper = {https://icaps22.icaps-conference.org/dc/ICAPS_2022_paper_359.pdf}, url_presentation = {https://www.youtube.com/watch?v=MUYl845Dy4I&list=PLj-ZdQ5rfSEqD1SztBXJppdjIE9CQQfzV} } @Article{Lin2017DAB, author = {Songtuan Lin and Xiaodong Li and Chuan Sun and Yu Tang}, journal = {Electronics Letters}, title = {Fast transient control for power adjustment in a dual-active-bridge converter}, year = {2017}, number = {16}, pages = {1130--1132}, volume = {53}, doi = {10.1049/el.2017.1662}, publisher = {{IET}} } @Article{Schiller2026DIYEvaluation, author = {Marvin Schiller and Matthias Kraus and Gregor Behnke and Michael Dorna and Michael Dambier and Stephanie Linder and Heiko Taxis and Susanne Biundo and Wolfgang Minker and Birte Glimm and Pascal Bercher}, journal = {International Journal of Human-Computer Interaction (IJHCI)}, title = {Designing an Intelligent Do-It-Yourself (DIY) Assistant in a User-Centered Process -- AI Planning, Knowledge Representation, and Proactive Dialog for Supporting Aspiring DIY Novices}, year = {2026}, keywords = {article,DECRA}, abstract = {How should a companion system be designed that assists novice users in the Do-It-Yourself (DIY) domain? We investigate this question with a series of extensive empirical experiments and development iterations of a companion system prototype. We investigate the benefit of using hierarchical task planning, an ontology-based domainmodel, and agent-based dialog management for familiarizing novices with their DIY devices (electric drill driver, electric jigsaw)and proactively assisting them with successful execution of a DIYproject. We outline the progression of our empirical methodology from qualitative towards quantitative investigation of various versions of our assistant with increasing sets of capabilities based on previous evaluations.}, url_questionnaires = {https://doi.org/10.7910/DVN/DYXJQF} } @Article{Olz2025CompoundPrecEffInference, author = {Conny Olz and Alexander Lodemann and Benedikt Jutz and Mario Schmautz and Maximilian Borowiec and Susanne Biundo and Pascal Bercher}, journal = {Journal of Artificial Intelligence Research (JAIR)}, title = {An Extensive Empirical Evaluation of Inferring Preconditions and Effects of Compound Tasks in Ground HTN Planning Problems}, year = {2025}, abstract = {HTN planning requires the decomposition of compound tasks into primitive and executable actions. In the currently most frequently used formalism, compound tasks lack explicit preconditions and effects. Those are, however, useful, e.g., for pruning techniques,heuristics, or the comprehension of domains. Recently, we have introduced and formalized different kinds of inferred preconditions and effects of compound tasks based on their decomposition methods together with a complexity analysis. In this paper, we present an empirical evaluation of computing these inferred preconditions and effects using theIPC benchmark sets. Specifically, we analyze their frequency of occurrence and compare the performance of an approximation to the exact preconditions and effects. Our goal is to provide a comprehensive overview of the proposed techniques, enabling researchers to determine the extent to which they can be utilized in their given application.}, doi = {10.1613/jair.1.17279}, volume = {82}, pages = {1407--1444}, url_paper = {https://jair.org/index.php/jair/article/view/17279/27150}, url_zenodo = {10.5281/zenodo.14678643}, keywords = {article,DECRA} } @Article{Bercher2022SurveyOfOwnWork, author = {Pascal Bercher}, title = {Hierarchical Planning and Reasoning about Partially Ordered Plans -- From Theory to Practice}, journal = {AI Magazine}, year = {2022}, abstract = {This invited paper (part of the New Faculty Highlights Invited Speaker Program of AAAI'21) surveys my work done until today. The reviewed work focuses on hierarchical task network (HTN) planning as well as on partial order causal link (POCL) planning. Lines of research include theoretical investigations (mostly computational complexity analyses), heuristic search, as well as the practical application of the technology for planning-based assistants which support a human user in carrying out various tasks.}, doi = {10.1002/aaai.12073}, pages = {353--364}, publisher = {John Wiley \& Sons, Ltd}, url_Paper = {https://bercher.net/publications/2022/Bercher2022SurveyOfOwnWork.pdf}, url_Paper-Wiley = {https://onlinelibrary.wiley.com/doi/epdf/10.1002/aaai.12073}, url_Paper-AAAI = {https://ojs.aaai.org/index.php/aimagazine/article/view/22007}, url_video_of_presentation = {https://slideslive.com/38952027/hierarchical-planning-and-reasoning-about-partially-ordered-plans-from-theory-to-practice}, keywords = {article} } @Article{Bercher2021DIY, author = {Pascal Bercher and Gregor Behnke and Matthias Kraus and Marvin Schiller and Dietrich Manstetten and Michael Dambier and Michael Dorna and Wolfgang Minker and Birte Glimm and Susanne Biundo}, title = {Do It Yourself, but Not Alone: Companion-Technology for Home Improvement -- Bringing a Planning-Based Interactive DIY Assistant to Life}, journal = {K{\"u}nstliche Intelligenz -- Special Issue on NLP and Semantics}, year = {2021}, abstract = {We report on the technology transfer project “Do it yourself, but not alone: Companion-Technology for Home Improvement” that was carried out by Ulm University in cooperation with Robert Bosch GmbH. We developed a prototypical assistance system that assists a Do It Yourself (DIY) handyman in carrying out DIY projects. The assistant, based on various AI and dialog management capabilities, generates a sequence of detailed instructions that users may just follow or adapt according to their individual preferences. It features explanation capabilities as well as pro-active support based on communication with the user as well as with the involved tools. We report on the project's main achievements, including the findings of various empirical studies conducted in various development stages of the prototype.}, doi = {10.1007/s13218-021-00721-x}, pages = {367--375}, volume = {35}, url_Paper_free-access = {https://rdcu.be/cmGwb}, url_Paper = {https://link.springer.com/article/10.1007/s13218-021-00721-x}, keywords = {article,nerdyTitle}, bibbase_note = {
Favorite title, because: Notably, the first part is the exact title of our entire research project; it has been replicated into this work since it summarizes all findings of the entire project. Anyway, strictly speaking, the title is just about companion technology for home improvement. However, in English the phrasing also reads as a classic double entendre: "do it yourself" already carries occasional sexual undertones, and adding "but not alone" flips it into an unmistakable innuendo.
} } @Article{Hoeller2021PANDA, author = {Daniel H\"oller and Gregor Behnke and Pascal Bercher and Susanne Biundo}, title = {The PANDA Framework for Hierarchical Planning}, journal = {KI -- Künstliche Intelligenz}, year = {2021}, doi = {10.1007/s13218-020-00699-y}, abstract = {During the last years, much progress has been made in hierarchical planning towards domain-independent systems that come with sophisticated techniques to solve planning problems instead of relying on advice in the input model. Several of these novel methods have been integrated into the PANDA framework, which is a software system to reason about hierarchical planning tasks. Besides solvers for planning problems based on plan space search, progression search, and translation to propositional logic, it also includes techniques for related problems like plan repair, plan and goal recognition, or plan verification. These various techniques share a common infrastructure, like e.g. a standard input language or components for grounding and reachability analysis. This article gives an overview over the PANDA framework, introduces the basic techniques from a high level perspective, and surveys the literature describing the diverse components in detail.}, pages = {391--396}, volume = {35}, url_Paper = {https://link.springer.com/epdf/10.1007/s13218-020-00699-y}, keywords = {article} } @Article{Bercher2021HPlanWorkshopReport, author = {Pascal Bercher and Daniel H\"oller and Gregor Behnke and Susanne Biundo and Vikas Shivashankar and Ron Alford}, title = {Report on the First and Second Workshops on Hierarchical Planning Held at the International Conference on Automated Planning and Scheduling}, journal = {AI Magazine}, year = {2021}, volume = {42}, number = {1}, pages = {83--85}, abstract = {Hierarchical planning has attracted renewed interest in the last couple of years. As a consequence, the time was right to establish a workshop devoted entirely to hierarchical planning -- an insight shared by many supporters. In this paper we report on the first ICAPS workshop on Hierarchical Planning held in Delft, The Netherlands, in 2018 as well as on the second workshop held in Berkeley, CA, USA, in 2019.}, url_Paper = {https://bercher.net/publications/2021/Bercher2021HPlanWorkshopReport.pdf}, url = {https://ojs.aaai.org/index.php/aimagazine/article/view/7393}, keywords = {article} } @Article{Hoeller2020HTNProgression, author = {Daniel H\"oller and Pascal Bercher and Gregor Behnke and Susanne Biundo}, title = {HTN Planning as Heuristic Progression Search}, journal = {Journal of Artificial Intelligence Research (JAIR)}, year = {2020}, volume = {67}, pages = {835--880}, doi = {10.1613/jair.1.11282}, abstract = {The majority of search-based HTN planning systems can be divided into those searching a space of partial plans (a plan space) and those performing progression search, i.e., that build the solution in a forward manner. So far, all HTN planners that guide the search by using heuristic functions are based on plan space search. Those systems represent the set of search nodes more effectively by maintaining a partial ordering between tasks, but they have only limited information about the current state during search. In this article, we propose the use of progression search as basis for heuristic HTN planning systems. Such systems can calculate their heuristics incorporating the current state, because it is tracked during search. Our contribution is the following: We introduce two novel progression algorithms that avoid unnecessary branching when the problem at hand is partially ordered and show that both are sound and complete. We show that defining systematicity is problematic for search in HTN planning, propose a definition, and show that it is fulfilled by one of our algorithms. Then, we introduce a method to apply arbitrary classical planning heuristics to guide the search in HTN planning. It relaxes the HTN planning model to a classical model that is only used for calculating heuristics. It is updated during search and used to create heuristic values that are used to guide the HTN search. We show that it can be used to create HTN heuristics with interesting theoretical properties like safety, goal-awareness, and admissibility. Our empirical evaluation shows that the resulting system outperforms the state of the art in search-based HTN planning.}, url_Paper = {https://bercher.net/publications/2020/Hoeller2020HTNProgressionSearch.pdf}, url_Paper_by-publisher = {https://jair.org/index.php/jair/article/view/11282/26578}, keywords = {article} } @Article{Behnke2019DIYWonderland, author = {Behnke, Gregor and Schiller, Marvin and Kraus, Matthias and Pascal Bercher and Schmautz, Mario and Dorna, Michael and Dambier, Michael and Minker, Wolfgang and Glimm, Birte and Biundo, Susanne}, title = {Alice in {DIY} wonderland or: Instructing novice users on how to use tools in {DIY} projects}, journal = {AI Communications}, year = {2019}, publisher = {IOS Press}, doi = {10.3233/AIC-180604}, volume = {32}, number = {1}, pages = {31--57}, abstract = {We present the interactive assistant ROBERT that provides situation-adaptive support in the realisation of do-it-yourself (DIY) home improvement projects. ROBERT assists its users by providing comprehensive step-by-step instructions for completing the DIY project. Each instruction is illustrated with detailed graphics, written and spoken text, as well as with videos. They explain how the steps of the project have to be prepared and assembled and give precise instructions on how to operate the required electric devices. The step-by-step instructions are generated by a hierarchical planner, which enables ROBERT to adapt to a multitude of environments easily. Parts of the underlying model are derived from an ontology storing information about the available devices and resources. A dialogue manager capable of natural language interaction is responsible for hands-free interaction. We explain the required background technology and present preliminary results of an empirical evaluation.}, url_Paper = {https://bercher.net/publications/2019/Behnke2019DIYWonderland.pdf}, url_domain-model = {https://bercher.net/publications/2019/Behnke2019DIYWonderlandDomain.zip}, keywords = {article,nerdyTitle}, bibbase_note = {
Favorite title, because: This is an obvious reference to Alice in Wonderland; we simply made it more concrete to put her into the DIY (=Do it Yourself) wonderland! Besides, the paper is actually using Alice and Bob as main protagonists, which is often done in academia as a substitute to the more generic "agent A" and "agent B".
} } @Article{Biundo2011AdvancedAssistance, author = {Susanne Biundo and Pascal Bercher and Thomas Geier and Felix M\"uller and Bernd Schattenberg}, title = {Advanced user assistance based on {AI} planning}, journal = {Cognitive Systems Research}, year = {2011}, volume = {12}, pages = {219--236}, number = {3-4}, month = {4}, note = {Special Issue on Complex Cognition}, doi = {10.1016/j.cogsys.2010.12.005}, abstract = {Artificial Intelligence technologies enable the implementation of cognitive systems with advanced planning and reasoning capabilities. This article presents an approach to use hybrid planning -- a method that combines reasoning about procedural knowledge and causalities -- to provide user-centered assistance. Based on a completely declarative description of actions, tasks, and solution methods, hybrid planning allows for the generation of knowledge-rich plans of action. The information those plans comprise includes causal dependencies between actions on both abstract and primitive levels as well as information about their hierarchical and temporal relationships. We present the hybrid planning approach in detail and show its potential by describing the realization of various assistance functionalities based on complex cognitive processes like the generation, repair, and explanation of plans. Advanced user assistance is demonstrated by means of a practical application scenario where an innovative electronic support mechanism helps a user to operate a complex mobile communication device.}, url_Paper = {https://bercher.net/publications/2011/Biundo2011AdvancedAssistance.pdf}, keywords = {article} } @Article{Biundo2016CompanionSurvey, Title = {Companion-Technology: An Overview}, Author = {Susanne Biundo and Daniel H\"oller and Bernd Schattenberg and Pascal Bercher}, Journal = {K{\"u}nstliche Intelligenz}, Year = {2016}, Note = {Special Issue on Companion Technologies}, Number = {1}, Pages = {11--20}, Volume = {30}, Doi = {10.1007/s13218-015-0419-3}, abstract = {Companion-technology is an emerging field of cross-disciplinary research. It aims at developing technical systems that appear as "Companions" to their users. They serve as co-operative agents assisting in particular tasks or, in a more general sense, even give companionship to humans. Overall, Companion-technology enables technical systems to smartly adapt their services to individual users' current needs, their requests, situation, and emotion. We give an introduction to the field, discuss the most relevant application areas that will benefit from its developments, and review the related research projects.}, url_Paper = {https://bercher.net/publications/2016/Biundo2016CompanionSurvey.pdf}, keywords = {article} } @InProceedings{Med2026HTNReversibility, author = {Jakub Med and Mohammad Yousefi and Lukas Chrpa and Pascal Bercher}, booktitle = {Proceedings of the 36th International Conference on Automated Planning and Scheduling ({ICAPS 2026})}, title = {Reversibility and Reachability in HTN Planning: Formalization and Computational Complexities in the Totally-Ordered Setting}, year = {2026}, publisher = {AAAI Press}, abstract = {Action reversibility, that is, whether it is possible to undo effects of an action by other actions, has been studied in classical planning and, recently, in non-deterministic planning. In this paper, we formalize the notions of method and primitive task reversibility in the context of hierarchical task network (HTN) planning, and provide complexity results. On top of that, we introduce various notions of reachability in HTN setting, for which the reachability is still an unexplored area (in contrast to classical planning, in which reachability is well studied). We divide the reachability into two classes based on two perspectives, one restricting the allowed progression rules (i.e., reachability using executions of primitive tasks, or reachability using decompositions of compound tasks, or unrestricted progression), and the other focusing on the desired target (i.e., a state (independently on the a network), a task network (independently on a state), or both at once). We show that the complexity of these problems varies significantly, ranging from EXPTIME-complete decision problems to constant-time ones. We also show that the introduced reversibility problems exhibit theoretical properties and complexity results analogous to the broader reachability classes.}, keywords = {conference,DECRA} } @InProceedings{Sreedharan2026FONDCompilations, author = {Sarath Sreedharan and Pascal Bercher}, booktitle = {Proceedings of the 36th International Conference on Automated Planning and Scheduling ({ICAPS 2026})}, title = {Compiling Model Reconciliation Explanation Problems into Stackelberg and FOND Planning Problems}, year = {2026}, publisher = {AAAI Press}, abstract = {Despite its popularity, most model reconciliation explanation generation methods rely on blind breadth-first search, and even available heuristics are rudimentary at best. In this paper, we propose two novel approaches to compile the problem of generating bounded model-reconciliation explanations into existing planning formalisms. First, we compile the problem into a Stackelberg planning problem, which is an adversarial problem consisting of a leader and follower agent. Here, the leader agent is responsible for identifying the explanation, while the follower checks the validity of the identified explanation. In the second approach, we see how the same problem can also be converted into a fully observable non-deterministic (FOND) planning problem. Here, the nondeterministic actions are used to generate and test the possibility of a shorter plan. We show the effectiveness of the proposed approaches by comparing them against each other and two existing baselines on standard planning benchmark problems.}, keywords = {conference,DECRA} } @InProceedings{Sheng2026LTLModelRepair, author = {Huanghua Sheng and Pascal Bercher}, booktitle = {Proceedings of the 36th International Conference on Automated Planning and Scheduling ({ICAPS 2026})}, title = {Complexity Results for Fixing Classical Models Using LTL to Express Which Solutions Are (Un)Desired}, year = {2026}, publisher = {AAAI Press}, abstract = {Model repair is the task of modifying a given planning model so that it satisfies a set of validity constraints. Prior frameworks encode constraints as finite sets of positive and negative plans, which cannot capture the properties of infinite sets of plans or patterns that all solutions and non-solutions exhibit, thereby limiting their usefulness. We propose a unified formalism that subsumes prior approaches by incorporating validity constraints specified in Linear Temporal Logic over process traces (LTLp), thereby capturing temporal and structural properties of plans. We further present a comprehensive complexity analysis that begins with a highly restricted fragment of LTLp and progressively lifts restrictions, tracking how increasing expressivity impacts the complexity of model repair. This yields a complexity landscape ranging from NP through Sigma_2^p up to PSPACE. We also highlight connections between our framework and several well-studied problems, including planning with temporally extended goals (TEGs), model repair using positive and negative plans, and the model reconciliation explanation (MRE) problem.}, keywords = {conference,DECRA,favorite}, bibbase_note = {
Favorite paper, because: For a number of years, one of my major research interests is model repair technology, which ensures that models express what we actually desire them to express. Until this paper, all repair approaches were only guided by desired or undesired action sequences. This paper extends this significantly by allowing to provide LTL formulae to express desired plan patterns (both desired and undesired), which I believe is a significant improvement.
} } @InProceedings{Oates2026LiftedPOCLComplexities, author = {Harrison Oates and Pascal Bercher}, booktitle = {Proceedings of the 36th International Conference on Automated Planning and Scheduling ({ICAPS 2026})}, title = {Relaxing is Hard: Complexity Results for Lifted Partial Order Causal Link Planning}, year = {2026}, publisher = {AAAI Press}, abstract = {We investigate Partial Order Causal Link (POCL) planning in the lifted setting, where plan steps are represented as parameterised action schemas. While delete relaxation has been shown to reduce the complexity of plan existence in the ground POCL setting, operating on lifted representations may at times be necessary to avoid the prohibitive cost of grounding. This motivates a separate complexity analysis for the lifted case. We formalise delete-relaxation via filter functions that selectively suppress delete effects, yielding differently strong relaxation semantics, with and without respect for pre-existing delete effects and causal links of the input plan. We prove that plan existence is EXPTIME--complete for most variants, even when the input plan is totally ordered. Further, we prove results ranging from NP--completeness to PSPACE--completeness for fixed-schema plan existence, with a tractable case when planning is done from scratch.}, keywords = {conference,DECRA,nerdyTitle}, url_Paper = {https://bercher.net/publications/2026/Oates2026LiftedPOCLComplexities.pdf}, bibbase_note = {
Favorite title, because: Every who knows me refers to myself as "always driven", "never calm". Hence, this is a reference to one of my most prominent personality traits, while also being a pun because in the paper we show that it's not that easy to obtain an easier problem class by relaxing problem components.
} } @InProceedings{Lauer2026OverratedOrder, author = {Pascal Lauer and Yifan Zhang and Patrik Haslum and Pascal Bercher}, booktitle = {Proceedings of the 36th International Conference on Automated Planning and Scheduling ({ICAPS 2026})}, title = {I Always Told My Mom That Order Is Overrated: Unordered HTN Planning is in PSPACE and Models Problems Beyond STRIPS}, year = {2026}, publisher = {AAAI Press}, abstract = {Hierarchical Task Network (HTN) planning is (in)famous for offering great modeling power but making plan existence undecidable. To lift the computational barrier, it is common to enforce orders between all tasks, which allows for an EXPTIME computation. We show that the opposite extreme, using no ordering constraints, reduces complexity further to PSPACE. This unites benefits of classical and HTN planning in a single formalism: It matches the complexity of classical planning while provably giving modelers more expressive power. We observe similar benefits on more, partially new, planning formalisms along the way to the main result.}, keywords = {conference,DECRA} } @InProceedings{Oates2026MakespanInvestigations, author = {Harrison Oates and Pascal Bercher}, booktitle = {Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI 2026)}, title = {Makespan Investigations of Sequential, Parallel, PO, and POCL Plans}, year = {2026}, publisher = {AAAI Press}, keywords = {conference,DECRA,favorite}, abstract = {Modern planning systems utilize various plan representations - sequential, parallel, partially ordered (PO), and partial-order causal link (POCL) - each with different models for concurrency. These formalisms are often implicitly assumed to have the same base properties, particularly regarding makespan. We challenge this assumption, proving the relationship between them is fundamentally asymmetric. Our analysis shows conversions from plans with rigid concurrency layers (sequential, parallel) to those with flexible partial orders (PO, POCL) can preserve makespan. However, the reverse generally fails; the flexible orderings in PO/POCL plans can yield shorter makespans for solutions that cannot be represented in parallel plans without serialization. We prove that finding an optimal parallel representation for a given POCL plan is -complete, resolving a key question about their practical interchangeability. We also provide tight complexity bounds for makespan-bounded plan existence. Notably, our results disprove a claim in the literature that planning graph-based planners maximize concurrency by minimizing the critical path in derived PO plans.}, url_Paper = {https://bercher.net/publications/2026/Oates2026MakespanInvestigations.pdf}, url_Slides = {https://bercher.net/publications/2026/Oates2026MakespanInvestigationsSlides.pdf}, url_Poster = {https://bercher.net/publications/2026/Oates2026MakespanInvestigationsPoster.pdf}, bibbase_note = {
Favorite paper, because: This one I also very much like since it points to something that the scientific community has overlooked for quite a while. I argue that many people assume that different "plan structures" -- ways to represent sets of actions to solve a problem -- have identical properties regarding their execution time under parallelism. Here, we challenge this often implicit assumption and show that two well-knows parallel plan representations differ in how compactly they can represent plans. More precisely: one plan representation can achieve a shorter execution time than others, making some planners claimed to be "makespan optimal" not optimal in general.
} } @InProceedings{Lutalo2026TOHTNRepairViaLLMs, author = {Daniel Lutalo and Pascal Bercher}, booktitle = {Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI 2026)}, title = {Automated Repair of Totally-Ordered Hierarchical Task Network Domains via Context-Free Grammars with Large Language Model Support}, year = {2026}, publisher = {AAAI Press}, keywords = {conference,DECRA}, abstract = {Repairing flawed domain models remains a critical challenge in AI planning, with few effective techniques available. We propose a novel approach for repairing totally ordered hierarchical task network (TO-HTN) models with missing actions, guided by a plan that must be valid for the repaired model. This problem has only one previously documented approach, which relies on complex re-encoding that's solved via TO-HTN planning. In contrast, our approach translates the repair task into a context-free grammar repair problem and leverages a large language model (LLM) to identify and insert relevant actions directly, simplifying the repair process. We evaluate our approach on established benchmarks and demonstrate substantially improved results over the prior approach, achieving nearly three times the number of instances solved, and nearly solving all instances of domains in which the previous approach solved zero. Importantly, we mask all natural language hints, such as action names, forcing the LLM to simulate reasoning and planning, and mitigating the risk of data leakage from its training corpus.}, url_Paper = {https://bercher.net/publications/2026/Lutalo2026TOHTNRepairViaLLMs.pdf} } @InProceedings{Tang2026HTNSymmetryResults, author = {Hadyn Tang and Pascal Bercher}, booktitle = {Proceedings of the 40th AAAI Conference on Artificial Intelligence (AAAI 2026)}, title = {Symmetries and Other Variations of ``End-Recursive'' HTN Problems: Mapping the Border Between Decidable and Undecidable Restrictions}, year = {2026}, publisher = {AAAI Press}, keywords = {conference,DECRA}, abstract = {In this paper, we investigate the complexity of determining if various restricted forms of hierarchical task network (HTN) planning have a plan. We perform a systematic analysis of new restrictions formed by applying symmetries and relaxations to two existing restrictions called regularity and tail-recursiveness. By doing so, we find that many variations on common restrictions do not affect the complexity of the plan existence problem at all, but we also obtain the counter-intuitive result that combining some of these seemingly inert relaxations together renders the plan existence problem undecidable. We also unearth a critical difference in definitions between an early paper in HTN planning and modern formalisms that appears to have gone unnoticed.}, url_Paper = {https://bercher.net/publications/2026/Tang2026HTNSymmetryResults.pdf} } @InProceedings{Yuan2025SearchSpaceStatistics, author = {Lijia Yuan and Pascal Bercher}, booktitle = {Proceedings of the 38th Australasian Joint Conference on AI (AJCAI 2025)}, title = {Towards Search Node-Specific HTN Heuristics}, year = {2025}, publisher = {Springer}, keywords = {conference,DECRA}, doi = {10.1007/978-981-95-4972-6_34}, pages = {439--452}, abstract = {While effective in hierarchical task network (HTN) planning, heuristic search currently relies on few pre-selected heuristics. However, during progression-based search, many search nodes exhibit specific properties, e.g., they may become totally ordered or acyclic, allowing for the application of specialized heuristics. For these search nodes, we conducted an experimental evaluation, employing reachability analysis, to examine the special cases encountered during search. Measuring how often various special cases occur informs us which heuristics developed for special cases -- selected on a per-search node basis-- are most promising. As a side contribution, we propose a slight modification of a technical definition used to decide properties of the task hierarchy.}, url_Paper = {https://link.springer.com/chapter/10.1007/978-981-95-4972-6_34}, url_Slides = {https://bercher.net/publications/2025/Yuan2025SearchSpaceStatisticsSlides.pdf} } @InProceedings{Yousefi2025ProbabilisticHTNs, author = {Mohammad Yousefi and Johannes Schmalz and Patrik Haslum and Pascal Bercher}, booktitle = {Proceedings of the 22th International Conference on Principles of Knowledge Representation and Reasoning (KR 2025)}, title = {Probabilistic HTN Planning: Formalization and Computational Complexity Analysis}, year = {2025}, publisher = {IJCAI}, doi = {10.24963/kr.2025/84}, pages = {869--879}, keywords = {conference,DECRA}, abstract = {Hierarchical Task Network (HTN) planning is an approach to sequential decision making that allows expressing complex grammar-like path constraints. In this paper, we first introduce an extension to HTN planning that takes probabilistic outcomes into account, and then study the computational complexity of deciding such problems either by finding a fixed sequence of actions (i.e., a conformant solution) or an outcome-dependent policy. This formalization extends factored Markov Decision Processes (MDPs) to have a hierarchical structure. In all studied cases, the conformant solutions are harder to obtain than their non-deterministic analogues, whereas policies are not always harder. Surprisingly, unlike their deterministic counterparts, severely restricted cases of probabilistic HTN problems are proven to be undecidable. The result holds even if all of the transition probabilities are bounded to be 0, 0.5, or 1.}, url_Paper = {https://bercher.net/publications/2025/Yousefi2025ProbabilisticHTNs.pdf}, url_Slides = {https://bercher.net/publications/2025/Yousefi2025ProbabilisticHTNsSlides.pdf} } @InProceedings{Welt2025SolveTheUnsolvable, author = {Michael Welt and Alexander Lodemann and Conny Olz and Pascal Bercher and Birte Glimm}, booktitle = {Proceedings of the 28th European Conference on Artificial Intelligence (ECAI 2025)}, title = {Calculating Optimal Corrections for Unsolvable Planning Problems}, year = {2025}, publisher = {IOS Press}, keywords = {conference,DECRA}, pages = {4637--4644}, doi = {10.3233/FAIA251368}, abstract = {Detecting and resolving unsolvable planning problems is an active research area that has recently received increased attention. Nevertheless, unsolvability remains a significant challenge, particularly when it comes to efficiently identifying potential causes for a problem's unsolvability. To address this challenge, we propose a method that computes modifications to the underlying domain. Specifically, given an unsolvable planning problem, our approach identifies a cardinality-minimal set of state variables whose removal renders the problem solvable. Existing literature typically relies on subset enumeration to identify such sets. While effective for small variable sets, we find that this approach becomes impractical for larger sets due to its high computational cost. To overcome this limitation, we introduce a novel method based on hitting set duality, a well-established technique for solving various combinatorial problems. Our results show that this new approach consistently outperforms subset enumeration for medium-sized and large result sets. We validate the effectiveness of our method through experiments on modified problems from the 2016 International Planning Competition on Unsolvability.}, url_Paper = {https://bercher.net/publications/2025/Welt2025SolveTheUnsolvable.pdf}, url_Poster = {https://bercher.net/publications/2025/Welt2025SolveTheUnsolvablePoster.pdf}, url_zenodo = {10.5281/zenodo.16761001} } @InProceedings{Bavandpour2025LiftedTestPlans, author = {Nader Karimi Bavandpour and Pascal Lauer and Songtuan Lin and Pascal Bercher}, booktitle = {Proceedings of the 28th European Conference on Artificial Intelligence (ECAI 2025)}, title = {Repairing Planning Domains Based on Lifted Test Plans}, year = {2025}, publisher = {IOS Press}, pages = {4774--4781}, doi = {10.3233/FAIA251385}, keywords = {conference,DECRA}, abstract = {Knowledge engineering for AI planning remains a significant challenge, particularly in the creation and maintenance of accurate domain models. A recent approach to correcting flawed models involves using test plans: non-solution plans that are intended to be solutions. However, these plans must be grounded, which restricts the modeler's ability to specify repairs at various levels of abstraction, especially when only partial information is available. In this paper, we propose a novel approach that extends domain repair capabilities to handle lifted test plans, where action parameters may remain unspecified. We introduce a new lifted repair problem set, a search algorithm, different designs of proper search spaces, and a novel lifted heuristic for solving the lifted repair problem. Our implementation and experimental results shows that our approach can solve a wide range of problems efficiently and reach solutions that are close to optimal.}, url_Paper = {https://bercher.net/publications/2025/Bavandpour2025LiftedTestPlans.pdf}, url_Slides = {https://bercher.net/publications/2025/Bavandpour2025LiftedTestPlansSlides.pdf}, url_zenodo = {10.5281/zenodo.16935964} } @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}, doi = {10.24963/ijcai.2025/1152}, pages = {10371--10380}, url_Paper = {https://bercher.net/publications/2025/Bercher2025ModelRepairSurvey.pdf}, url_Slides = {https://bercher.net/publications/2025/Bercher2025ModelRepairSurveySlides.pdf}, url_Poster = {https://bercher.net/publications/2025/Bercher2025ModelRepairSurveyPoster.pdf} } @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}, doi = {10.24963/ijcai.2025/967}, pages = {8696--8704}, url_Paper = {https://bercher.net/publications/2025/Zhang2025AckermannRefined.pdf}, url_Slides = {https://bercher.net/publications/2025/Zhang2025AckermannRefinedSlides.pdf}, url_Poster = {https://bercher.net/publications/2025/Zhang2025AckermannRefinedPoster.pdf} } @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}, doi = {10.1609/icaps.v35i1.36102}, pages = {64--73}, url_Paper = {https://bercher.net/publications/2025/Lauer2025LiftedHTNVerification.pdf} } @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,favorite,nerdyTitle}, doi = {10.1609/icaps.v35i1.36107}, pages = {112--120}, url_Paper = {https://bercher.net/publications/2025/Yousefi2025ImperfectAStar.pdf}, url_Slides = {https://bercher.net/publications/2025/Yousefi2025ImperfectAStarSlides.pdf}, bibbase_note = {
Favorite paper, because: This is definitely one of my most favorite ones. A* search is the most famous and standard approach for solving planning problems and assumed to be complete unless there are zero-cost actions involved. Here, we show that A* is incomplete, i.e., can get stuck in loops from which it cannot escape, not only without zero-cost actions, but even in the presence of the perfect heuristic.
Favorite title, because: This is a reference to the award-winning paper by Helmert and Roeger called How good is almost perfect? It follows the same pattern, and even investigates the same question: Behavior of A* with almost (or completely) perfect heuristics. Also, clearly it's almost contradictory to ask how good "perfect" is, since by definition is is as good as it gets: perfect! Yet, that's not the case since we prove incompleteness, so we need more than perfect heuristics!
} } @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 Press}, 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,nerdyTitle}, 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}, bibbase_note = {
Favorite title, because: This title strikes the same chord as one of my other paper titles: It's supposed to sound passive-aggressive, or know-it-all-ish (German: "besserwisserisch"). It relates to the content because it's about counter example plans, i.e., plans that don't work.
} } @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} } @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} } @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,favorite}, bibbase_note = {
Favorite paper, because: Even though this is not the first paper in the realm of FOND HTN Planning (i.e., Hierarchical Task Network planning with actions having non-deterministic effects), it stands out because it is the first to propose a planner for this problem setting. Besides, it's packed with content, as we provide an efficient grounder, heuristics, a planner, and benchmarks.
} } @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 = {This paper won the SoCS 2024 Best Student Paper Award}, 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} } @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} } @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} } @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} } @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} } @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} } @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} } @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} } @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,nerdyTitle}, bibbase_note = {
Favorite title, because: Well, the first question is clearly referring to a potential future couple, yet from the subtitle it becomes clear that it's about the hardness of checking whether two "possible effects" can occur at the same time. (Fun fact: the paper presentation used little hearts to illustrate the technical co-occurrence questions.)
} } @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} } @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,nerdyTitle}, bibbase_note = {
Favorite title, because: I love the passive-agressiveness here. :) Note that "Really" is set in italics to make clear how to pronounce it, namely passive aggressive. It's a pun since the remaining title points out that the paper is on the computational complexity of fixing planning models. So the answer to the question whether it was *really* that hard is given in the paper.
} } @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,favorite}, bibbase_note = {
Favorite paper, because: Following formal definitions of my IJCAI 2021 paper listed below, this work is the first to perform testplan-based model repair in practice. It's performance is extremely high, solving all test plans in seconds. It is currently the only one that supports all kinds of repairs, i.e., changing preconditions and effects arbitrarily (not just adding missing ones). This work already served as basis for several follow-up works as well.
} } @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} } @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} } @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} } @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} } @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} } @InProceedings{Chen2022FlexibleFONDHTNs, author = {Dillon Z. Chen and Pascal Bercher}, booktitle = {Proceedings of the 32nd International Conference on Automated Planning and Scheduling (ICAPS 2022)}, title = {Flexible FOND HTN planning: A Complexity Analysis}, year = {2022}, pages = {26--34}, doi = {10.1609/icaps.v32i1.19782}, publisher = {AAAI Press}, abstract = {Hierarchical Task Network (HTN) planning is an expressive planning formalism that has often been advocated to address real-world problems. Yet few extensions exist that can deal with the many challenges encountered in the real world, one being the capability to express uncertainty. Recently, a new HTN formalism for fully observable nondeterministic problems was proposed and studied theoretically. In this paper, we lay out limitations of that formalism and propose an alternative definition, which addresses and resolves such limitations. We also study its complexity for certain problems.}, url_Paper = {https://bercher.net/publications/2022/Chen2022FlexibleFONDHTNs.pdf}, url_Poster = {https://bercher.net/publications/2022/Chen2022FlexibleFONDHTNsPoster.pdf}, url_Slides = {https://bercher.net/publications/2022/Chen2022FlexibleFONDHTNsSlides.pdf}, url_video_of_presentation = {http://icaps22.icaps-conference.org/papers/187/index.html}, note = {This paper won the ICAPS 2022 Best Undergraduate Student Paper Award}, keywords = {conference} } @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} } @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} } @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} } @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} } @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,favorite,nerdyTitle}, bibbase_note = {
Favorite paper, because: This paper is one of the first (if not the first) to propose model repair based on input plans (though for a more detailed discussion, please read my 2025 survey on that matter). It formally defines the problem and studies its computational complexity for classical planning as well as for Hierarchical Task Network (HTN) planning. It forms the foundation of much of my work in this realm that comes later and hence forms a landmark paper for model repair (at least for me).
Favorite paper, because: I love this one! For two reasons: For one, because it's a reference to the paper mentioned above (it's literally just one word exchanged), and because it makes sense content-wise! This paper is about the computational complexity of fixing the domain model, i.e., "the world". (And I always regarded myself an idealist, so I liked that title because of this, too.)
} } @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 = {This paper won the ICAPS 2021 Best Undergraduate Student Paper Award}, keywords = {conference} } @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,favorite}, bibbase_note = {
Favorite paper, because: This is one of my favorites because it proves the impact of the pruning power of causal links in POCL planning. It further systematically investigates the computational landscape of different problem relaxations of POCL planning problems.
} } @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} } @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} } @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} } @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} } @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 = {This paper was nominated for the KI 2020 Best Paper Award}, 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} } @InProceedings{Hoeller2020ILPHTNHeuristic, 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} } @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} } @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,favorite}, bibbase_note = {
Favorite paper, because: This paper introduced HDDL, the now de-facto model description language for HTN planning problems. It has been used by both HTN planning competitions so far, and is hence supported by most planning systems.
} } @InProceedings{Behnke2020HTNGrounder, 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} } @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} } @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,favorite,nerdyTitle}, bibbase_note = {
Favorite paper, because: This survey reviews various different hierarchical planning formalisms, pointing to novel contributions in the field that has seen a surge in interest in the years leading to this work.
Favorite title, because: I admit: this is only borderline-funny if at all.^^ There are two parts in here: First, hierarchical planning is about refinement from very abstract to very concrete. The title hence fits since it's a survey on hierarchical planning, of which there are many distinct (concrete) realizations. The title, unnoticed to many, is a reference to a paper by my former doctoral mother "From Abstract Crisis to Concrete Relief -- A Preliminary Report on Combining State Abstraction and HTN Planning".
} } @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} } @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} } @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 = {This paper won the TCST 2018 Best Paper Award}, 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} } @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 = {This paper won the ICTAI 2018 CV Ramamoorthy Best Paper Award}, 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} } @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 = {This paper won the ICAPS 2018 Best Student Paper Award}, 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,favorite}, bibbase_note = {
Favorite paper, because: This paper makes major contributions to the field of HTN planning as it shows how to use classical planning heuristics in HTN planning. The resulting planner remains one of the state-of-the-art planners because of this even years later, and the idea could further be transformed to non-deterministic settings as well. Another important (though I argue less impactful) contribution is the identification of redundant branching points in standard progression search, making search more effective if addressed.
} } @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}, abstract = {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} } @InProceedings{Behnke2017MIPSystem, 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,nerdyTitle}, bibbase_note = {
Favorite title, because: This should be self-explanatory: A sloth that helps with working out! :) If course, SLOTH is an acronym that gets resolved in the paper. (Once more, a title I am innocent of.)
} } @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} } @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 = {Erratum: 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} } @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} } @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} } @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,nerdyTitle}, bibbase_note = {
Favorite title, because: Once more: only borderline funny... The subtitle is a reference to the Lord of the Rings movies: One Ring to rule them all. (It still makes sense here since the ontology unifies among different sources of knowledge.)
} } @InProceedings{Alford2015TightTIHTNBoundsAbstract, 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} } @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,nerdyTitle}, bibbase_note = {
Favorite title, because: Sadly, that title wasn't made up by me.^^ Yet, I love it. :) It's simple: It asks the every-day question how hard it is to change one's plan; this is funny because the paper is quite literally about the computational hardness of changing plans! So, now we know!
} } @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} } @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} } @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} } @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,nerdyTitle}, bibbase_note = {
Favorite title, because: Another title that sadly I did not come up with. The fun lies in the first/main title: "Bound to plan" is an English idiom, meaning that one "has to plan", which is what we do both in this paper as well as in our field in general. Though the actual pun lies in the fact that the paper shows how a certain bound can be computed and exploited to make planning possible in the first place. (Well, I had to be more technical, but that's the gist of it.)
} } @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} } @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} } @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} } @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} } @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} } @InProceedings{Bercher2013POCLDeleteRelaxation, 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} } @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} } @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} } @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} } @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,favorite}, bibbase_note = {
Favorite paper, because:This paper stands out as it proposed a novel formalization of HTN planning problems (especially how the solution set is formally defined) that has become a new accepted standard in the field. The formalism is significantly simplified compared to the formalism most commonly used until then, yet it maintains its computational complexity, as proved. Besides, it's the first that proves another problem relaxation that leads to decidability: Task Insertion -- called TIHTN planning. This problem relaxation has further been studied in several subsequent works as well. This paper can hence be regarded the most influential one of my career to date.
} } @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} } @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} } @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} } @InProceedings{Stern2025EvalModelLearning, author = {Roni Stern and Leonardo Lamanna and Argaman Mordoch and Yarin Benyamin and Pascal Lauer and Brendan Juba and Gregor Behnke and Christian Muise and Pascal Bercher and Mauro Vallati and Kai Xi and Omar Wattad and Omer Eliyahu}, booktitle = {Proceedings of the 14th Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2025)}, title = {Evaluating Planning Model Learning Algorithms}, year = {2025}, abstract = {Formulating domain models for model-based planning is a challenging, time consuming, and error-prone task. A number of approaches have been proposed to automatically learn domain models from a given set of observations. A key question is how to compare models learned by different approaches. Currently, there are no standard evaluation metrics or benchmarks. In this paper, we describe a set of metrics designed to assess different characteristics of a learned domain model. We then present a benchmark suite based on domain models from the International Planning Competition (IPC) and an evaluation process for using it. Four domain model learning algorithms are evaluated on this benchmark, which highlights the importance of the diverse evaluation metrics we proposed.}, keywords = {workshop,DECRA}, url_Paper = {https://bercher.net/publications/2025/Stern2025LearnedModelMetrics.pdf} } @InProceedings{Lutalo2025LLMBasedTOHTNRepair, author = {Daniel Lutalo and Pascal Bercher}, booktitle = {Proceedings of the 2nd workshop on planning in the era of LLMs (LM4Plan)}, title = {Automated Repair of Totally-Ordered Hierarchical Task Network Domains via Context-Free Grammars with Large Language Model Support}, year = {2025}, abstract = {Repairing flawed domain models remains a critical challenge in AI planning, with few effective techniques available. We propose a novel approach for repairing totally ordered hierarchical task network (TO-HTN) models with missing actions, guided by a plan that must be valid for the repaired model. This problem has only one previously documented approach, which relies on complex re-encoding that's solved via TO-HTN planning. In contrast, our approach translates the repair task into a context-free grammar repair problem and leverages a large language model (LLM) to identify and insert relevant actions directly, simplifying the repair process. We evaluate our approach on established benchmarks and demonstrate substantially improved results over the prior approach, achieving nearly three times the number of instances solved, and nearly solving all instances of domains in which the previous approach solved zero. Importantly, we mask all natural language hints, such as action names, forcing the LLM to simulate reasoning and planning, and mitigating the risk of data leakage from its training corpus.}, keywords = {workshop,DECRA}, url_Paper = {https://bercher.net/publications/2025/Lutalo2025TOHTNRepairViaLLMs.pdf} } @InProceedings{Bavandpour2025LLMRepairIdeas, author = {Nader Karimi Bavandpour and Pascal Bercher}, booktitle = {Proceedings of the 6th workshop on Human-Aware and Explainable Planning (HAXP 2025)}, title = {Finding Semantically Guided Repairs in PDDL Domains Using LLMs}, year = {2025}, abstract = {Repairing Planning Domain Definition Language (PDDL) models is difficult because solutions must ensure correctness while remaining interpretable to human modellers. Existing hitting set methods identify minimal repair sets from whitelist and blacklist traces, but they cannot prefer semantically meaningful fixes and the true repair may not be minimal. We propose combining large language models (LLMs) with the hitting set framework, using semantic cues in PDDL action and predicate names to guide repairs. This hybrid approach provides contrastive, counterfactual explanations of why traces fail and how domains could behave differently.}, keywords = {workshop,DECRA}, url_Paper = {https://bercher.net/publications/2025/Bavandpour2025LLMRepairIdeas.pdf}, url_Slides = {https://bercher.net/publications/2025/Bavandpour2025LLMRepairIdeasSlides.pdf} } @InProceedings{Lauer2025ExpressivePlanningFormalisms, author = {Pascal Lauer and Yifan Zhang and Patrik Haslum and Pascal Bercher}, booktitle = {Proceedings of the 8th ICAPS Workshop on Hierarchical Planning (HPlan 2025)}, title = {PSPACE Planning With Expressivity Beyond STRIPS: Plan Constraints via Unordered HTNs, ILPs, Numerical Goals, and More}, year = {2025}, abstract = {To better capture real-world problems, Hierarchical Task Network (HTN) planning and numerical planning provide enhanced modeling capabilities over classical planning. However, the plan existence problem in these formalisms is generally undecidable. We identify restricted fragments that remain PSPACE-complete, matching the complexity of classical planning, while being more expressive. The most important result proves that plan existence in unordered HTN planning, i.e.\, ignoring all ordering relations, is PSPACE-complete. This shows that even minimal partial ordering causes a drastic increase in complexity. The result motivates a strong preference for unordered HTN models, a largely ignored fragment that deserves more attention. To bridge the gap between the tractable fragments of numerical and HTN planning, we introduce new formalisms that use Integer Linear Programs, Presburger formulas, and grammatical constraints to express action sequence restrictions within PSPACE, offering practical alternatives when the HTN structure is too complex to model.}, keywords = {workshop,DECRA} } @InProceedings{Olz2024aTOILPHeuristic, author = {Conny Olz and Alexander Lodemann and Pascal Bercher}, booktitle = {Proceedings of the 7th ICAPS Workshop on Hierarchical Planning (HPlan 2024)}, title = {An ILP Heuristic for Total-Order HTN Planning}, year = {2024}, pages = {10--18}, 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. Our current heuristic proves to be more efficient than the one we build on, though it still performs worse than other existing (admissible) heuristics.}, url_Paper = {https://bercher.net/publications/2024/Olz2024aTOILPHeuristic.pdf}, keywords = {workshop,DECRA} } @InProceedings{Yuan2024HTNSearchSpaceAnalysis, author = {Lijia Yuan and Pascal Bercher}, booktitle = {Proceedings of the 7th ICAPS Workshop on Hierarchical Planning (HPlan 2024)}, title = {Towards Search Node-Specific Special-Case Heuristics for HTN Planning -- An Empirical Analysis of Search Space Properties under Progression}, year = {2024}, pages = {45--53}, abstract = {In hierarchical task network (HTN) planning, heuristic search is highly effective, but currently, there are only a few available heuristics and they are pre-selected for use. However, during the progression-based search, many search nodes exhibit specific properties, e.g., they may become totally ordered or acyclic allowing for the application of specialized heuristics. In these search nodes, we conducted an experimental evaluation, employing reachability analysis, to examine the special cases encountered during the search. Measuring how often these special cases occur informs us of which special cases specialized heuristics are most promising.}, url = {https://bercher.net/publications/2024/Yuan2024HTNSearchSpaceAnalysis.pdf}, url_Poster = {https://bercher.net/publications/2024/Yuan2024HTNSearchSpaceAnalysisPoster.pdf}, url_Slides = {https://bercher.net/publications/2024/Yuan2024HTNSearchSpaceAnalysisSlides.pdf}, keywords = {workshop,DECRA} } @InProceedings{Behnke2024LearningTrack, author = {Gregor Behnke and Pascal Bercher}, booktitle = {Proceedings of the Workshop on the International Planning Competition (WIPC 2024)}, title = {Envisioning a Domain Learning Track for the IPC}, year = {2024}, abstract = {ICKEPS (International Competition on Knowledge Engineering for Planning and Scheduling) was created to make aware of the importance of domain engineering for planning and scheduling, but in past editions humans competed with the help of planning tools, thus encouraging the development of those tools (where humans were an integral part). We propose an IPC Domain Learning track, where learning algorithms would compete completely on their own, creating valid domain models without further use of input other than the constraints (like input plans) they base upon. We believe that this might help to establish some standard in the field of domain learning, such as a standard benchmark set, standard inputs (possibly an input language), and metrics to evaluate the learned domains against.}, url_Paper = {https://bercher.net/publications/2024/Behnke2024LearningTrack.pdf}, url_Slides = {https://bercher.net/publications/2024/Behnke2024LearningTrackSlides.pdf}, keywords = {workshop,DECRA} } @InProceedings{Lin2023VerificationComplexity, author = {Songtuan Lin and Conny Olz and Malte Helmert and Pascal Bercher}, title = {On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence}, booktitle = {Proceedings of the 6th ICAPS Workshop on Hierarchical Planning (HPlan 2023)}, pages = {35--43}, year = {2023}, note = {Erratum: Corollary 1 and Proposition 5 incorrectly claimed NEXPTIME and co-NEXPTIME membership, respectively. Both should be one exponential harder, which is stated correctly in the AAAI 2024 version of this paper (same Corollary and Proposition).}, abstract = {In this paper we study the computational complexity of several reasoning tasks centered at the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for the grounded and the lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not been studied yet for HTN planning. For plan verification, results were available for both formalisms except the lifted representation of HTN planning. We will thus present the lower bound and the upper bound of the complexity of plan verification in lifted HTN planning and provide novel 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 computational complexity concerning the optimality of a given plan, i.e., answering the question whether such a plan is optimal, and discuss its connection to the bounded plan existence problem.}, url_Paper = {https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanEx.pdf}, url_Slides = {https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanExSlides.pdf}, url_Poster = {https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanExPoster.pdf}, keywords = {workshop} } @InProceedings{Olz2023bTOLookAhead, author = {Conny Olz and Pascal Bercher}, title = {A Look-Ahead Technique for Search-Based HTN Planning: Reducing the Branching Factor by Identifying Inevitable Task Refinements}, booktitle = {Proceedings of the 6th ICAPS Workshop on Hierarchical Planning (HPlan 2023)}, note = {This paper was simultaneously accepted at SoCS and hence only published there.}, year = {2023}, 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.}, url_Paper = {https://bercher.net/publications/2023/Olz2023TOLookAhead.pdf}, keywords = {workshop} } @InProceedings{Wu2022HTNLinearization, author = {Ying Xian Wu and Songtuan Lin and Gregor Behnke and Pascal Bercher}, booktitle = {33rd {PuK} Workshop ``Planen, Scheduling und Konfigurieren, Entwerfen'' (PuK 2022)}, title = {Finding Solution Preserving Linearizations For Partially Ordered Hierarchical Planning Problems}, year = {2022}, abstract = {Solving partially ordered hierarchical planning problems is more computationally expensive compared to solving totally ordered ones. Therefore, automatically transforming partially ordered problem domains into totally ordered ones, such that the totally ordered problem still retains at least one solution, would be a desired capability as it would reduce complexity and thus make it easier for planning systems to solve the problem. This is a complex endeavour, because even creating all possible linearizations of all methods in the original domain does not guarantee that solutions are preserved. It also allows the planner to use algorithms and heuristics specialised for the totally ordered case to solve the transformed problem. In this paper, we propose an algorithm for converting partially ordered problems into totally ordered ones and give criterion for when this is possible. We test our techniques on the partially-ordered track of the bench-mark set of the IPC 2020 and solve both the linearized and the original partially-ordered problems using state-of-the-art planning systems. We find that in the majority of problems across a variety of domains, the linearized problem remains solvable, and can always be solved faster than the without our proposed pre-processing technique.}, url_Paper = {https://bercher.net/publications/2022/Wu2022HTNLinearization.pdf}, url_Slides = {https://bercher.net/publications/2022/Wu2022HTNLinearizationSlides.pdf}, url_Workshop = {http://www.member.uni-oldenburg.de/juergen.sauer/PuK/PuK2022/index.html}, keywords = {workshop} } @InProceedings{Lin2022RepairAsDiagnosis, author = {Songtuan Lin and Alban Grastien and Pascal Bercher}, booktitle = {Proceedings of the 33rd International Workshop on Principles of Diagnosis (DX 2022)}, title = {Planning Domain Repair as a Diagnosis Problem}, year = {2022}, abstract = {Techniques for diagnosis have been used in many applications. We explore the connection between diagnosis and AI planning in this paper and apply the diagnosis algorithm to repair a flawed planning domain. In particular, the scenario we are concerned with is that we are given a plan which is supposed to be a solution to a planning problem, but it is actually not due to some flaws in the planning domain, and we want to repair the domain to turn the plan into a solution. For this, we will first frame this problem as a diagnosis problem and then solve it via using diagnosis algorithms.}, url_Paper = {https://bercher.net/publications/2022/Lin2022RepairAsDiagnosis.pdf}, url_Slides = {https://bercher.net/publications/2022/Lin2022RepairAsDiagnosisSlides.pdf}, keywords = {workshop} } @InProceedings{Lin2022SATviaSOGs, author = {Songtuan Lin and Gregor Behnke and Pascal Bercher}, booktitle = {Proceedings of the 5th ICAPS Workshop on Hierarchical Planning (HPlan 2022)}, title = {Exploiting Solution Order Graphs and Path Decomposition Trees for More Efficient HTN Plan Verification via SAT Solving}, year = {2022}, pages = {24--28}, abstract = {The research on the plan verification problem has drawn increasing attention in the last few years. It can serve as an approach for validating a planning domain by viewing an input plan as a test case which is supposed to be a solution to a planning problem in the domain which is to be validated. In this paper, we study the plan verification problem in the context of Hierarchical Task Network (HTN) planning. Concretely, we will develop an SAT-based approach via exploiting the data structures solution order graphs and path decomposition trees employed by the state-of-the-art SAT-based HTN planner which transforms an HTN plan verification problem into an SAT formula. Additionally, for the purpose of completeness, we will also reimplement the old SAT-based plan verifier within an outdated planning system called PANDA-3 and integrate it into the new version called PANDA-pi.}, url_Paper = {https://bercher.net/publications/2022/Lin2022SATbasedVerification.pdf}, url_Poster = {https://bercher.net/publications/2022/Lin2022SATbasedVerificationPoster.pdf}, url_presentation = {https://youtu.be/DbDTuY7dOxM}, keywords = {workshop} } @InProceedings{Lin2022CYKParsing, author = {Songtuan Lin and Gregor Behnke and Simona Ondrčková and Roman Barták and Pascal Bercher}, booktitle = {Proceedings of the 5th ICAPS Workshop on Hierarchical Planning (HPlan 2022)}, title = {On Total-Order HTN Plan Verification with Method Preconditions -- An Extension of the CYK Parsing Algorithm}, year = {2022}, pages = {52--58}, 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. The current state-of-the-art TO plan verifier solves the problem by a blind search approach in order to deal with some state constraints and henceforth results in several overheads. However, many existing TOHTN planning benchmarks do not have these constraints. Hence, we ignore them in the paper and develop a TOHTN plan verification approach which avoids those overheads in the state-of-the-art TO verifier via extending the CYK algorithm.}, url_Paper = {https://bercher.net/publications/2022/Lin2022HTNCYKParsing.pdf}, url_Poster = {https://bercher.net/publications/2022/Lin2022HTNCYKParsingPoster.pdf}, url_presentation = {https://youtu.be/AJqmbG9Bs2M}, keywords = {workshop} } @InProceedings{Olz2022POPrecsAndEffects, author = {Conny Olz and Pascal Bercher}, booktitle = {Proceedings of the 5th ICAPS Workshop on Hierarchical Planning (HPlan 2022)}, title = {On the Efficient Inference of Preconditions and Effects of Compound Tasks in Partially Ordered HTN Planning Domains}, year = {2022}, Pages = {47--51}, abstract = {Recently, preconditions and effects of compound tasks based on their possible refinements have been introduced together with an efficient inference procedure to compute a subset of them. However, they were restricted to total-order HTN planning domains. In this paper we generalize the definitions and algorithm to the scenario of partially ordered domains.}, url_Paper = {https://bercher.net/publications/2022/Olz2022POPrecsAndEffects.pdf}, url_presentation = {https://youtu.be/QsQsXBYu0yI}, keywords = {workshop} } @InProceedings{Johnson2022aSATPruning, author = {Christopher Johnson and Pascal Bercher and Charles Gretton}, booktitle = {Proceedings of the 14th Workshop on Heuristics and Search for Domain-independent Planning (HSDIP 2022)}, title = {A Study of the Power of Heuristic-based Pruning via SAT Planning}, year = {2022}, abstract = {Planning as SAT (satisfiability) is the method of representing a horizon-bounded planning problem as a Boolean SAT problem, and using a SAT decision procedure to solve that problem. Representations are direct, thus a solution plan can be obtained directly from a satisfying valuation. By querying a SAT solver over a series of horizon lengths, up to a completeness threshold, this approach can be the basis of a complete planning procedure. SAT planning algorithms have been theoretically contrasted with IDA∗ search, a heuristic state-based search algorithm, where a theoretical exponential separation is demonstrated in favour of the SAT approach. Here a nominated heuristic is implemented in SAT with the query formulae encoding heuristic information. We make two practical contributions related to this background. First, we provide to the best of our knowledge the first practical implementation of a theoretical SAT encoding of the h-2 heuristic. Second, we empirically evaluate SAT-based pruning by implementing heuristics h-max and h-2.}, note = {This paper has also been accepted at KEPS 2022.}, url_Paper = {https://bercher.net/publications/2022/Johnson2022SATBasedHeuristicPruning.pdf}, url_presentation = {https://www.youtube.com/watch?v=HFntrSAyszU}, url_openReview = {https://openreview.net/forum?id=c2-QShxGZt}, keywords = {workshop} } @InProceedings{Johnson2022bSATPruning, author = {Christopher Johnson and Pascal Bercher and Charles Gretton}, booktitle = {Proceedings of the 11th Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2022)}, title = {A Study of the Power of Heuristic-based Pruning via SAT Planning}, year = {2022}, abstract = {Planning as SAT (satisfiability) is the method of representing a horizon-bounded planning problem as a Boolean SAT problem, and using a SAT decision procedure to solve that problem. Representations are direct, thus a solution plan can be obtained directly from a satisfying valuation. By querying a SAT solver over a series of horizon lengths, up to a completeness threshold, this approach can be the basis of a complete planning procedure. SAT planning algorithms have been theoretically contrasted with IDA* search, a heuristic state-based search algorithm, where a theoretical exponential separation is demonstrated in favour of the SAT approach. Here a nominated heuristic is implemented in SAT with the query formulae encoding heuristic information. We make two practical contributions related to this background. First, we provide to the best of our knowledge the first practical implementation of a theoretical SAT encoding of the h-2 heuristic. Second, we empirically evaluate SAT-based pruning by implementing heuristics h-max and h-2.}, note = {This paper has also been accepted at HSDIP 2022, the linked openReview reviews are from HSDIP.}, url_Paper = {https://bercher.net/publications/2022/Johnson2022SATBasedHeuristicPruning.pdf}, url_openReview = {https://openreview.net/forum?id=c2-QShxGZt}, keywords = {workshop} } @InProceedings{Olz2021ComprehendHTNModels, author = {Conny Olz and Eva Wierzba and Pascal Bercher and Felix Lindner}, title = {Towards Improving the Comprehension of HTN Planning Domains by Means of Preconditions and Effects of Compound Tasks}, booktitle = {Proceedings of the 10th Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2021)}, year = {2021}, abstract = {Hierarchical Task Network (HTN) planning is a paradigm that offers engineers a formalism for modeling planning domains in terms of possible decompositions of compound tasks. A complete decomposition of a compound task results in totally or partially ordered primitive tasks, i.e., plans in the classical sense. Existing specification languages for HTN domains, such as HDDL, do only allow the assertion of preconditions and effects for primitive tasks but not for compound ones. Recently, a method for inferring preconditions and effects for compound tasks was proposed. It was hypothesized that inferred preconditions and effects can aid knowledge engineers in understanding HTN domain specifications and in predicting the meaning of particular compound tasks. We describe preliminary results from a study that supports this hypothesis and discuss future research directions.}, url_Paper = {https://bercher.net/publications/2021/Olz2021ComprehendHTNModels.pdf}, url_Slides = {https://bercher.net/publications/2021/Olz2021ComprehendHTNModelsSlides.pdf}, url_video-of-paper-presentation = {https://www.youtube.com/watch?v=jLcTjrtNhaY&list=PLd_hcmfMPvAhDzHla0ZR6dNsiKBlwsx6K&index=11}, keywords = {workshop} } @InProceedings{Chen2021FlexibleFONDHTNs, author = {Dillon Chen and Pascal Bercher}, title = {The Complexity of Flexible FOND HTN Planning}, booktitle = {Proceedings of the 4th ICAPS Workshop on Hierarchical Planning (HPlan 2021)}, year = {2021}, pages = {62--70}, abstract = {Hierarchical Task Network (HTN) planning is an expressive planning formalism that has often been advocated as a first choice to address real-world problems. Yet only a few extensions exist that can deal with the many challenges encountered in the real world. One of them is the capability to express uncertainty. Recently, a new HTN formalism for Fully Observable Nondeterministic (FOND) problems was proposed and studied theoretically. In this paper, we lay out limitations of that formalism and propose an alternative definition, which addresses and resolves such` limitations. We conduct a complexity study of an alternative, more flexible formalism and provide tight complexity bounds for most of the investigated special cases of the problem.}, url_Paper = {https://bercher.net/publications/2021/Chen2021FlexibleFONDHTNs.pdf}, keywords = {workshop} } @InProceedings{Hoeller2021VerificationViaPlanning, author = {Daniel H\"oller and Julia Wichlacz and Pascal Bercher and Gregor Behnke}, title = {Compiling HTN Plan Verification Problems to HTN Planning Problems}, booktitle = {Proceedings of the 4th ICAPS Workshop on Hierarchical Planning (HPlan 2021)}, year = {2021}, pages = {8--15}, 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, e.g. when a solution is post-processed, in systems using approximation, or just to validate whether a planning system works correctly (e.g. for debugging or in a competition). In the literature, there are verification systems based on translations to propositional logic and based on techniques from parsing. Here we present a third approach and translate plan verification problems to HTN planning problems. These can be solved using any HTN planning system. We test our solver on the set of solutions from the 2020 International Planning Competition. Our evaluation is yet preliminary, because it does not include all systems from the literature, but it already shows that our approach performs well compared with the included systems.}, url_Paper = {https://bercher.net/publications/2021/Hoeller2021VerificationViaCompilation.pdf}, keywords = {workshop} } @InProceedings{Kiam2021TemporalHTNsChallenge, author = {Jane Jean Kiam and Pascal Bercher and Axel Schulte}, title = {Temporal Hierarchical Task Network Planning with Nested Multi-Vehicle Routing Problems -- A Challenge to be Resolved}, booktitle = {Proceedings of the 4th ICAPS Workshop on Hierarchical Planning (HPlan 2021)}, year = {2021}, pages = {71--75}, abstract = {This paper focuses on presenting a complex real-world planning application based on a rescue mission. While temporal hierarchical planning seems to be a promising solution to such class of problems, given its ability to consider experts' knowledge and dissect the search space, many major challenges of complex real-world planning problems are not addressed yet formally, i.e. recursive decomposition to achieve a goal state, optimization of utility functions defined for abstract tasks, and optimal allocation of tasks to multiple actors.}, url_Paper = {https://bercher.net/publications/2021/Kiam2021TemporalHTNsChallenge.pdf}, keywords = {workshop} } @InProceedings{Lin2021CorrectingHTNModels, author = {Songtuan Lin and Pascal Bercher}, title = {On the Computational Complexity of Correcting HTN Domain Models}, booktitle = {Proceedings of the 4th ICAPS Workshop on Hierarchical Planning (HPlan 2021)}, year = {2021}, pages = {35--43}, abstract = {Incorporating user requests into planning processes is a key concept in developing flexible planning technologies. Such systems may be required to change its planning model to adapt to certain user requests. In this paper, we assume a user provides a non-solution plan to a system and asks it to change the planning model so that the plan becomes a solution. We study the computational complexity of deciding whether such changes exist in the context of Hierarchical Task Network (HTN) planning. We prove that the problem is NP-complete in general independent of what or how many changes are allowed. We also identify several conditions which make the problem tractable when they are satisfied.}, url_Paper = {https://bercher.net/publications/2021/Lin2021HTNChangeComplexity.pdf}, url_Slides = {https://bercher.net/publications/2021/Lin2021HTNChangeComplexitySlides.pdf}, url_Poster = {https://bercher.net/publications/2021/Lin2021HTNChangeComplexityPoster.pdf}, keywords = {workshop} } @InProceedings{Bartak2021TOHTNVerification, author = {Roman Bart{\'a}k and Simona Ondr\v{c}kov\'{a} and Gregor Behnke and Pascal Bercher}, title = {On the Verification of Totally-Ordered HTN Plans}, booktitle = {Proceedings of the 4th ICAPS Workshop on Hierarchical Planning (HPlan 2021)}, year = {2021}, pages = {44--48}, 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. In this paper, we propose an extension of the parsing-based approach to verify totally-ordered HTN plans. This problem is known to be tractable, 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/Bartak2021TOHTNVerification.pdf}, keywords = {workshop} } @InProceedings{Hoeller2020Landmarks, author = {Daniel Höller and Pascal Bercher}, title = {Landmark Extraction in HTN Planning}, booktitle = {Proceedings of the 3rd ICAPS Workshop on Hierarchical Planning (HPlan 2020)}, year = {2020}, pages = {9--17}, abstract = {Landmarks are a valuable source of information for heuristics in planning. They 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. In this paper we summarize landmark techniques for HTN planning, discuss their limitations, and show how to use techniques from classical planning to find more landmarks in HTN planning than previously possible. On a widely used benchmark set, our approach finds 2.3 times the number of landmarks compared to the approach from the literature. We conduct some preliminary tests on landmark-based heuristics for HTN planning. Our empirical evaluation shows that the heuristics based on our new extraction method perform better than the one based on the extraction technique from the literature. However, all landmark-based heuristics are not competitive with recent heuristics in HTN planning.}, note = {Erratum: Corollary 1 incorrectly claims an NP-completeness result. This should be co-NP-complete, which is stated correctly in the AAAI 2021 version of this paper (also Corollary 1).}, url_Paper = {https://bercher.net/publications/2020/Hoeller2020LandmarkExtraction.pdf}, keywords = {workshop} } @Inproceedings{Behnke2019HTN-IPC, author = {Gregor Behnke and Daniel H{\"o}ller and Pascal Bercher and Susanne Biundo and Damien Pellier and Humbert Fiorino and Ron Alford}, title = {Hierarchical Planning in the IPC}, year = {2019}, booktitle = {Proceedings of the Workshop on the International Planning Competition (WIPC 2019)}, abstract = {Over the last years, the amount of research in hierarchical planning has increased, leading to significant improvements in the performance of planners. However, the research is diverging and planners are somewhat hard to compare against each other. This is mostly caused by the fact that there is no standard set of benchmark domains, nor even a common description language for hierarchical planning problems. As a consequence, the available planners support a widely varying set of features and (almost) none of them can solve (or even parse) any problem developed for another planner. With this paper, we propose to create a new track for the IPC in which hierarchical planners will compete. This competition will result in a standardised description language, broader support for core features of that language among planners, a set of benchmark problems, a means to fairly and objectively compare HTN planners, and for new challenges for planners.}, url_Paper = {https://bercher.net/publications/2019/Behnke2019HTN-IPC.pdf}, url_Slides = {https://bercher.net/publications/2019/Behnke2019HTN-IPCSlides.pdf}, url_IPC-website = {http://ipc2020.hierarchical-task.net}, keywords = {workshop} } @Inproceedings{Hoeller2019HDDL, author = {Daniel H{\"o}ller and Gregor Behnke and Pascal Bercher and Susanne Biundo and Humbert Fiorino and Damien Pellier and Ron Alford}, title = {HDDL -- A Language to Describe Hierarchical Planning Problems}, year = {2019}, booktitle = {Proceedings of the Second ICAPS Workshop on Hierarchical Planning (HPlan 2019)}, pages = {6--14}, 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. We restrict our language to a basic feature set shared by many recent systems, give an extension of PDDL's EBNF syntax definition, and discuss our extensions, especially with respect to planner-specific input languages from related work.}, url_Paper = {https://bercher.net/publications/2019/Hoeller2019HDDL.pdf}, url_openReview = {https://openreview.net/forum?id=HJeT8HBbt4}, keywords = {workshop} } @Inproceedings{Behnke2019GroundingHTNs, author = {Gregor Behnke and Daniel H{\"o}ller and Pascal Bercher and Susanne Biundo}, title = {More Succinct Grounding of HTN Planning Problems -- Preliminary Results}, year = {2019}, booktitle = {Proceedings of the Second ICAPS Workshop on Hierarchical Planning (HPlan 2019)}, pages = {40--48}, abstract = {Planning systems usually operate on grounded representations of the planning problems during search. Further, planners that use translations into other combinatorial problems also often perform their translations based on a grounded model. Planning models, however, are commonly defined in a lifted formalism. As such, one of the first preprocessing steps a planner performs is to generate a grounded representation. In this paper we present a new approach for grounding HTN planning problems that produces smaller groundings than the previously published method. We expect this decrease in size to lead to more efficient planners.}, url_Paper = {https://bercher.net/publications/2019/Behnke2019GroundingHTNs.pdf}, url_openReview = {https://openreview.net/forum?id=H1lgDHr-FE}, keywords = {workshop} } @Inproceedings{Schiller2018EvaluatingDIY, author = {Schiller, Marvin and Behnke, Gregor and Pascal Bercher and Kraus, Matthias and Dorna, Michael and Richter, Felix and Biundo, Susanne and Glimm, Birte and Minker, Wolfgang}, title = {Evaluating Knowledge-Based Assistance for DIY}, year = {2018}, pages = {925--930}, booktitle = {Proceedings of MCI Workshop Digital Companion}, abstract = {We report on the development of a companion system incorporating hierarchical planning, ontology-based knowledge modeling and multimodal cloud-based dialog. As an application scenario, we consider the domain of do-it-yourself (DIY) home improvement involving the use of power tools. To test and -- if necessary -- adjust the developed techniques, user studies are conducted throughout the development phase. We present fundamental considerations and open questions encountered when testing the implemented prototype with potential users and report first observations from a current study.}, url_Paper = {https://bercher.net/publications/2018/Schiller2018EvaluatingDIY.pdf}, url_Slides = {https://bercher.net/publications/2018/Schiller2018EvaluatingDIYSlides.pdf}, keywords = {workshop} } @Inproceedings{Hoeller2018HTNRepair, author = {Daniel Höller and Pascal Bercher and Gregor Behnke and Susanne Biundo}, title = {HTN Plan Repair Using Unmodified Planning Systems}, year = {2018}, pages = {26--30}, booktitle = {Proceedings of the First ICAPS Workshop on Hierarchical Planning (HPlan 2018)}, 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.}, url_Paper = {https://bercher.net/publications/2018/Hoeller2018HTNRepair.pdf}, keywords = {workshop} } @Inproceedings{Hoeller2018PlanRecognitionWorkshop, title = {Plan and Goal Recognition as HTN Planning}, year = {2018}, booktitle = {Proceedings of the AAAI 2018 Workshop on Plan, Activity, and Intent Recognition (PAIR 2018)}, author = {H{\"o}ller, Daniel and Pascal Bercher and Behnke, Gregor and Biundo, Susanne}, abstract = {Companion systems are cooperative, cognitive systems aiming at assisting a user in everyday situations. Therefore, these systems require a high level of availability. One option to meet this requirement is to use a web-deployable architecture. In this demo paper, we present a multimodal cloud-based dialogue framework for the development of a distributed, web-based companion system. The proposed framework is intended to provide an efficient, easily extensible, and scalable approach for this kind of systems and will be demonstrated in a do-it-yourself assistance scenario. 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.}, url_Paper = {https://bercher.net/publications/2018/Hoeller2018aPlanRecognition.pdf}, keywords = {workshop} } @InProceedings{Hoeller2014PlanLinearization, Title = {Finding User-friendly Linearizations of Partially Ordered Plans}, Author = {Daniel H{\"o}ller and Pascal Bercher and Felix Richter and Marvin Schiller and Thomas Geier and Susanne Biundo}, Booktitle = {28th {PuK} Workshop ``Planen, Scheduling und Konfigurieren, Entwerfen'' (PuK 2014)}, Year = {2014}, abstract = {Planning models usually do not discriminate between different possible execution orders of the actions within a plan, as long as the sequence remains executable. As the formal planning problem is an abstraction of the real world, it can very well occur that one linearization is more favorable than the other for reasons not captured by the planning model --- in particular if actions are performed by a human. Post-hoc linearization of plans is thus a way to improve the quality of a plan enactment. The cost of this transformation decouples from the planning process, and it allows to incorporate knowledge that cannot be expressed within the limitations of a certain planning formalism. In this paper we discuss the idea of finding useful plan linearizations within the formalism of hybrid planning (although the basic ideas are applicable to a broader class of planning models). We propose three concrete models for plan linearization, discuss their ramifications using the application domain of automated user-assistance, and sketch out ways how to empirically validate the assumptions underlying these user-centric models.}, url_Paper = {https://bercher.net/publications/2014/Hoeller2014PlanLinearization.pdf}, url_Slides = {https://bercher.net/publications/2014/Hoeller2014PlanLinearizationSlides.pdf}, keywords = {workshop} } @InProceedings{Pragst2014CyberSecurityDomain, Title = {Introducing Hierarchy to Non-Hierarchical Planning Models: A Case Study for Behavioral Adversary Models}, Author = {Louisa Pragst and Felix Richter and Pascal Bercher and Schattenberg, Bernd and Susanne Biundo}, Booktitle = {28th {PuK} Workshop ``Planen, Scheduling und Konfigurieren, Entwerfen'' (PuK 2014)}, Year = {2014}, abstract = {Hierarchical planning approaches are often pursued when it comes to a real-world application scenario, because they allow for incorporating additional expert knowledge into the domain. That knowledge can be used both for improving plan explanations and for reducing the explored search space. In case a non-hierarchical planning model is already available, for instance because a bottom-up modeling approach was used, one has to concern oneself with the question of how to introduce a hierarchy. This paper discusses the points to consider when adding a hierarchy to a non-hierarchical planning model using the example of the BAMS Cyber Security domain.}, url_Paper = {https://bercher.net/publications/2014/Pragst2014CyberSecurityDomain.pdf}, keywords = {workshop} } @InProceedings{Bercher2013EncodingPlans, author = {Pascal Bercher and Susanne Biundo}, title = {Encoding Partial Plans for Heuristic Search}, booktitle = {Proceedings of the 4th Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2013)}, year = {2013}, pages = {11--15}, abstract = {We propose a technique that allows any planning system that searches in the space of partial plans to make use of heuristics from the literature which are based on search in the space of states. The technique uses a problem encoding that reduces the problem of finding a heuristic value for a partial plan to finding a heuristic value for a state: It encodes a partial plan into a new planning problem, s.t. solutions for the new problem correspond to solutions reachable from the partial plan. Evaluating the goal distance of the partial plan then corresponds to evaluating the goal distance of the initial state in the new planning problem.}, url_Paper = {https://bercher.net/publications/2013/Bercher2013EncodingPlans.pdf}, url_Slides = {https://bercher.net/publications/2013/Bercher2013EncodingPlansSlides.pdf}, keywords = {workshop} } @InProceedings{Behnke2015OntologiesAndPlanning, Title = {Integrating Ontologies and Planning for Cognitive Systems}, Author = {Gregor Behnke and Pascal Bercher and Susanne Biundo and Birte Glimm and Denis Ponomaryov and Marvin Schiller}, Booktitle = {Proceedings of the 28th International Workshop on Description Logics (DL 2015)}, Year = {2015}, Publisher = {CEUR Workshop Proceedings}, abstract = {We present an approach for integrating ontological reasoning and planning within cognitive systems. Patterns and mechanisms that suitably link planning domains and interrelated knowledge in an ontology are devised. In particular, this enables the use of (standard) ontology reasoning for extending a (hierarchical) planning domain. Furthermore, explanations of plans generated by a cognitive system benefit from additional explanations relying on background knowledge in the ontology and inference. An application of this approach in the domain of fitness training is presented.}, url_Paper = {https://bercher.net/publications/2015/Behnke2015OntologiesAndPlanning.pdf}, keywords = {workshop} } @Inproceedings{Bercher2013POCLSoftGoals, author = {Pascal Bercher and Fabian Ginter and Susanne Biundo}, title = {Search Strategies for Partial-Order Causal-Link Planning with Preferences}, year = {2013}, pages = {29--40}, booktitle = {27th PuK Workshop ''Planen, Scheduling und Konfigurieren, Entwerfen'' (PuK 2013)}, abstract = {This paper studies how to solve classical planning problems with preferences by means of a partial-order causal-link (POCL) planning algorithm. Preferences are given by soft goals -- optional goals which increase a plan's benefit if satisfied at the end of a plan. Thus, we aim at finding a plan with the best \textit{net-benefit}, which is the difference of the achieved preferences' benefit minus the cost of all actions in the plan that achieves them. While many approaches compile soft goals away, we study how they can be addressed natively by a POCL planning system. We propose novel search and flaw selection strategies for that problem class and evaluate them empirically.}, url_Paper = {https://bercher.net/publications/2013/Bercher13POCLSoftGoals.pdf}, url_Slides = {https://bercher.net/publications/2013/Bercher13POCLSoftGoalsSlides.pdf}, keywords = {workshop} } @InProceedings{Elkawkagy2011LandmarkStrategies, author = {Mohamed Elkawkagy and Pascal Bercher and Bernd Schattenberg and Susanne Biundo}, title = {Landmark-Aware Strategies for Hierarchical Planning}, booktitle = {Workshop on Heuristics for Domain-independent Planning ({HDIP} 2011)}, year = {2011}, pages = {73--79}, abstract = {In hierarchical planning, landmarks are abstract tasks the decomposition of which are mandatory when trying to find a solution to a given problem. In this paper, we present novel domain-independent strategies that exploit landmark information to speed up the planning process. The empirical evaluation shows that the landmark-aware strategies outperform established search strategies for hierarchical planning.}, url_Paper = {https://bercher.net/publications/2011/Elkawkagy2011LandmarkStrategies.pdf}, url_Slides = {https://bercher.net/publications/2011/Elkawkagy2011LandmarkStrategiesSlides.pdf}, keywords = {workshop} } @inproceedings{Bercher2011Preferences, author = {Pascal Bercher and Susanne Biundo}, title = {Hybrid Planning with Preferences Using a Heuristic for Partially Ordered Plans}, booktitle = {26th {PuK} Workshop "Planen, Scheduling und Konfigurieren, Entwerfen" (PuK 2011)}, year = {2011}, abstract = {This paper is concerned with the problem of finding preferred plans in a hybrid planning setting, which is the fusion of classical and hierarchical planning. Here, we define preferences as weighted soft goals -- facts one would like to see satisfied in a goal state, but which do not have to hold necessarily. We present a branch-and-bound algorithm that allows a broad variety of search strategies, as opposed to the majority of existing planning systems which usually perform progression. The algorithm prunes task networks from the search space which will never lead to a better solution than the best solution found so far. To this end, we developed an admissible heuristic, based on a combination of the h^2 heuristic and delete relaxation, which takes as input a task network and estimates the best quality of any solution that can be developed from it.}, url_Paper = {https://bercher.net/publications/2011/Bercher2011Preferences.pdf}, url_Slides = {https://bercher.net/publications/2011/Bercher2011PreferencesSlides.pdf}, keywords = {workshop} } @InProceedings{Elkawkagy2010LandmarksInHybrid, author = {Mohamed Elkawkagy and Pascal Bercher and Bernd Schattenberg and Susanne Biundo}, title = {Exploiting Landmarks for Hybrid Planning}, booktitle = {25th {PuK} Workshop "Planen, Scheduling und Konfigurieren, Entwerfen" (PuK 2010)}, year = {2010}, abstract = {Very recently, the well-known concept of landmarks has been adapted from the classical planning setting to hierarchical planning. It was shown how a pre-processing step that extracts local landmarks from a planning domain and problem description can be used in order to prune the search space that is to be explored before the actual search is performed. This pruning technique eliminates all branches of the task decomposition tree, for which can be proven that they will never lead to a solution. In this paper, we investigate this technique in more detail and extend it by introducing search strategies which use these local landmarks in order to guide the planning process more effectively towards a solution. Our empirical evaluation shows that the pre-processing step dramatically improves performance because dead ends can be detected much earlier than without pruning and that our search strategies using the local landmarks outperform many other possible search strategies.}, url_Paper = {https://bercher.net/publications/2010/Elkawkagy2010LandmarksInHybrid.pdf}, keywords = {workshop} } @InCollection{Bercher2017UserCenteredPlanning, author = {Pascal Bercher and Daniel H{\"o}ller and Gregor Behnke and Susanne Biundo}, title = {User-Centered Planning}, chapter = {5}, pages = {79--100}, doi = {10.1007/978-3-319-43665-4_5}, abstract = {User-centered planning capabilities are core elements of Companion-Technology. They are used to implement the functional behavior of technical systems in a way that makes those systems Companion-able – able to serve users individually, to respect their actual requirements and needs, and to flexibly adapt to changes of the user's situation and environment. This book chapter presents various techniques we have developed and integrated to realize user-centered planning. They are based on a hybrid planning approach that combines key principles also humans rely on when making plans: stepwise refining complex tasks into executable courses of action and considering causal relationships between actions. Since the generated plans impose only a partial order on actions, they allow for a highly flexible execution order as well. Planning for Companion-Systems may serve different purposes, depending on the application for which the system is created. Sometimes, plans are just like control programs and executed automatically in order to elicit the desired system behavior; but sometimes they are made for humans. In the latter case, plans have to be adequately presented and the definite execution order of actions has to coincide with the user's requirements and expectations. Furthermore, the system should be able to smoothly cope with execution errors. To this end, the plan generation capabilities are complemented by mechanisms for plan presentation, execution monitoring, and plan repair.}, booktitle = {Companion Technology -- A Paradigm Shift in Human-Technology Interaction}, editor = {Susanne Biundo and Andreas Wendemuth}, publisher = {Springer}, year = {2017}, series = {Cognitive Technologies}, url_Paper = {https://bercher.net/publications/2017/Bercher2017UserCenteredPlanning.pdf}, url_Poster = {https://bercher.net/publications/2015/Bercher2015UserCenteredPlanningPoster.pdf}, keywords = {bookchapter} } @InCollection{Bercher2017HomeTheater, Author = {Pascal Bercher and Felix Richter and Thilo H\"ornle and Thomas Geier and Daniel H\"oller and Gregor Behnke and Florian Nielsen and Frank Honold and Felix Sch\"ussel and Stephan Reuter and Wolfgang Minker and Michael Weber and Klaus Dietmayer and Susanne Biundo}, title = {Advanced User Assistance for Setting Up a Home Theater}, pages = {485--491}, chapter = {24}, doi = {10.1007/978-3-319-43665-4_24}, keywords = {bookchapter}, booktitle = {Companion Technology -- A Paradigm Shift in Human-Technology Interaction}, editor = {Susanne Biundo and Andreas Wendemuth}, publisher = {Springer}, year = {2017}, series = {Cognitive Technologies}, abstract = {In many situations of daily life, such as in educational, work-related, or social contexts, one can observe an increasing demand for intelligent assistance systems. In this chapter, we show how such assistance can be provided in a wide range of application scenarios—based on the integration of user-centered planning with advanced dialog and interaction management capabilities. Our approach is demonstrated by a system that assists a user in the task of setting up a complex home theater. The theater consists of several hi-fi devices that need to be connected with each other using the available cables and adapters. In particular for technically inexperienced users, the task is quite challenging due to the high number of different ports of the devices and because the used cables might not be known to the user. Support is provided by presenting a detailed sequence of instructions that solves the task.}, url_Paper = {https://bercher.net/publications/2017/Bercher2017HomeTheater.pdf} } @InCollection{Behnke2017UserIntegration, Author = {Gregor Behnke and Florian Nielsen and Marvin Schiller and Denis Ponomaryov and Pascal Bercher and Birte Glimm and Wolfgang Minker and Susanne Biundo}, title = {To Plan for the User Is to Plan With the User -- Integrating User Interaction Into the Planning Process}, chapter = {7}, pages = {123--144}, doi = {10.1007/978-3-319-43665-4_7}, abstract = {Settings where systems and users work together to solve problems collaboratively are among the most challenging applications of Companion-Technology. So far we have seen how planning technology can be exploited to realize Companion-Systems that adapt flexibly to changes in the user's situation and environment and provide detailed help for users to realize their goals. However, such systems lack the capability to generate their plans in cooperation with the user. In this chapter we go one step further and describe how to involve the user directly into the planning process. This enables users to integrate their wishes and preferences into plans and helps the system to produce individual plans, which in turn let the Companion-System gain acceptance and trust from the user. Such a Companion-System must be able to manage diverse interactions with a human user. A so-called mixed-initiative planning system integrates several Companion-Technologies which are described in this chapter. For example, a—not yet final—plan, including its flaws and solutions, must be presented to the user to provide a basis for her or his decision. We describe how a dialog manager can be constructed such that it can handle all communication with a user. Naturally, the dialog manager and the planner must use coherent models. We show how an ontology can be exploited to achieve such models. Finally, we show how the causal information included in plans can be used to answer the questions a user might have about a plan. The given capabilities of a system to integrate user decisions and to explain its own decisions to the user in an appropriate way are essential for systems that interact with human users.}, booktitle = {Companion Technology -- A Paradigm Shift in Human-Technology Interaction}, editor = {Susanne Biundo and Andreas Wendemuth}, publisher = {Springer}, year = {2017}, series = {Cognitive Technologies}, url_Paper = {https://bercher.net/publications/2017/Behnke2017UserIntegration.pdf}, keywords = {bookchapter} } @InCollection{Nothdurft2016UserInvolvement, booktitle = {Dialogues with Social Robots: Enablements, Analyses, and Evaluation}, Author = {Florian Nothdurft and Pascal Bercher and Gregor Behnke and Wolfgang Minker}, title = {User Involvement in Collaborative Decision-Making Dialog Systems}, Editor = {Kristiina Jokinen and Graham Wilcock}, Publisher = {Springer}, Year = {2017}, pages = {129--141}, note = {This book chapter was accepted at the 7th International Workshop On Spoken Dialogue Systems (IWSDS 2016).}, doi = {10.1007/978-981-10-2585-3_10}, abstract = {Abstract Mixed-initiative assistants are systems that support humans in their decision-making and problem-solving capabilities in a collaborative manner. Such systems have to integrate various artificial intelligence capabilities, such as knowledge representation, problem solving and planning, learning, discourse and dialog, and human-computer interaction. These systems aim at solving a given problem autonomously for the user, yet involve the user into the planning process for a collaborative decision-making, to respect e.g. user preferences. However, how the user is involved into the planning can be framed in various ways, using different involvement strategies, varying e.g. in their degree of user freedom. Hence, here we present results of a study examining the effects of different user involvement strategies on the user experience in a mixed-initiative system.}, url_Paper = {https://bercher.net/publications/2016/Nothdurft2016UserInvolvement.pdf}, keywords = {bookchapter} } @InCollection{Kraus2019CloudCompanion, author = {Matthias Kraus and Marvin Schiller and Gregor Behnke and Pascal Bercher and Susanne Biundo and Birte Glimm and Wolfgang Minker}, title = {A Multimodal Dialogue Framework for Cloud-Based Companion Systems}, booktitle = {9th International Workshop on Spoken Dialogue Systems}, year = {2019}, pages = {405--410}, editor = {Rafael Banchs and Luis Fernando D'Haro and Haizhou Li}, publisher = {Springer}, note = {This book chapter is a slightly newer version of the paper by Kraus et al. that was accepted at the 10th International Workshop On Spoken Dialog Systems Technology (IWSDS 2018).}, series = {Lecture Notes in Electrical Engineering}, abstract = {Companion systems are cooperative, cognitive systems aiming at assist- ing a user in everyday situations. Therefore, these systems require a high level of availability. One option to meet this requirement is to use a web-deployable architecture. In this demo paper, we present a multimodal cloud-based dialogue frame- work for the development of a distributed, web-based companion system. The pro- posed framework is intended to provide an efficient, easily extensible, and scalable approach for these kinds of systems and will be demonstrated in a do-it-yourself assistance scenario.}, url_Paper = {https://bercher.net/publications/2019/Kraus2019CloudCompanion.pdf}, keywords = {bookchapter} } @inproceedings{Wu2023IPCLinearizer, title = {Grounded (Lifted) Linearizer at the IPC 2023: Solving Partial Order HTN Problems by Linearizing Them}, author = {Ying Xian Wu and Conny Olz and Songtuan Lin and Pascal Bercher}, booktitle = {Proceedings of the 11th {I}nternational {P}lanning {C}ompetition: Planner Abstracts -- Hierarchical Task Network (HTN) Planning Track, {IPC} 2023}, year = {2023}, abstrac = {In this paper, we would like to present Grounded (Lifted) Linearizer, a hierarchical task network (HTN) planning system which won the Partial Order (PO) Agile and Satisficing tracks of the International Planning Competition 2023 on Hierarchical Task Network (HTN) Planning. This system consists of two parts. The first part is a preprocessor developed in house which transforms a POHTN problem into a total order (TO) one and which is the main contribution of this paper. The second part is an existing HTN planner. The outstanding performance of our assembled planning system thus serves as an evidence for how our preprocessor can enhance the efficiency of other existing planners.}, url_Paper = {https://bercher.net/publications/2023/Wu2023IPCLinearizer.pdf}, keywords = {various} } @inproceedings{Olz2023IPCPANDADealer, title = {The PANDADealer System for Totally Ordered HTN Planning in the 2023 IPC}, author = {Conny Olz and Daniel H{\"o}ller and Pascal Bercher}, booktitle = {Proceedings of the 11th {I}nternational {P}lanning {C}ompetition: Planner Abstracts -- Hierarchical Task Network (HTN) Planning Track (IPC)}, year = {2023}, abstract = {The PANDADealer system is an HTN planning system for solving totally ordered HTN planning problems. It builds on the heuristic progression search of the PANDApro system, and extends it with a look-ahead technique to detect dead-ends and inevitable refinement choices. The technique is based on inferred preconditions and effects of tasks, or more precisely, their decomposition methods.}, url_Paper = {https://bercher.net/publications/2023/Olz2023IPCPANDADealer.pdf}, keywords = {various} } @Article{Bercher2023SurveyOfOwnWorkAbstract, author = {Pascal Bercher}, title = {Hierarchical Planning and Reasoning about Partially Ordered Plans -- From Theory to Practice (extended abstract)}, journal = {Interactive AI Magazine}, year = {2023}, abstract = {This is an invited paper and part of the New Faculty Highlights Invited Speaker Program of AAAI'21. It surveys some of my work done until today in hierarchical task network (HTN) planning as well as partial order causal link (POCL) planning. Lines or research outlined include complexity investigations, heuristic search, as well as practical application for planning-based assistants.}, url_Paper-AIMag = {https://interactiveaimag.org/columns/articles/hierarchical-planning-and-reasoning-about-partially-ordered-plans-from-theory-to-practice-new-faculty-highlights-extended-abstract/}, url_Paper = {https://bercher.net/publications/2023/Bercher2023SurveyOfOwnWorkAbstract.pdf}, url_video_of_presentation = {https://slideslive.com/38952027/hierarchical-planning-and-reasoning-about-partially-ordered-plans-from-theory-to-practice}, keywords = {various} } @inproceedings{Schattenberg2021Woodworking, title = {The Hierarchical Woodworking Domain}, author = {Bernd Schattenberg and Pascal Bercher}, booktitle = {Proceedings of 10th {I}nternational {P}lanning {C}ompetition: Planner and Domain Abstracts -- Hierarchical Task Network (HTN) Planning Track (IPC 2020)}, year = {2021}, pages = {43--44}, abstract = {The Woodworking domain is one of the classical benchmark domains in the canon of the International Planning Competition. This paper describes our hierarchical take on it.}, url_Paper = {https://bercher.net/publications/2021/Schattenberg2021Woodworking.pdf}, keywords = {various} } @inproceedings{Bercher2021Smartphone, title = {The Smartphone Domain}, author = {Pascal Bercher and Susanne Biundo and Bernd Schattenberg}, booktitle = {Proceedings of 10th {I}nternational {P}lanning {C}ompetition: Planner and Domain Abstracts -- Hierarchical Task Network (HTN) Planning Track (IPC 2020)}, year = {2021}, pages = {47--47}, abstract = {This extended abstract is about the Smartphone domain, submitted as a benchmark domain to the IPC 2020.}, url_Paper = {https://bercher.net/publications/2021/Bercher2021Smartphone.pdf}, keywords = {various} } @inproceedings{Hoeller2021PCP, title = {From PCP to HTN Planning Through CFGs}, author = {Daniel H\"oller and Songtuan Lin and Kutluhan Erol and Pascal Bercher}, booktitle = {Proceedings of 10th {I}nternational {P}lanning {C}ompetition: Planner and Domain Abstracts -- Hierarchical Task Network (HTN) Planning Track (IPC 2020)}, year = {2021}, pages = {24--25}, abstract = {The International Planning Competition in 2020 was the first one for a long time to host tracks on HTN planning. The used benchmark set included a domain describing the undecidable Post Correspondence Problem (PCP). In this paper we describe the two-step process applied to generate HTN problems based on PCP instances. It translates the PCP into a grammar intersection problem of two context-free languages, which is then encoded into an HTN problem.}, url_Paper = {https://bercher.net/publications/2021/Hoeller2021PCP.pdf}, keywords = {various} } @TechReport{Bercher2018AssemblyAssistant, author = {Pascal Bercher and Felix Richter and Frank Honold and Florian Nielsen and Felix Schüssel and Thomas Geier and Thilo Hörnle and Stephan Reuter and Daniel H{\"o}ller and Gregor Behnke and Klaus Dietmayer and Wolfgang Minker and Michael Weber and Susanne Biundo}, title = {A Companion-System Architecture for Realizing Individualized and Situation-Adaptive User Assistance}, institution = {Ulm University}, year = {2018}, doi = {10.18725/OPARU-11023}, pages = {1--48}, abstract = {We show how techniques from various research areas -- most notably hierarchical planning, dialog management, and interaction management -- can be employed to realize individualized and situation-adaptive user assistance. We introduce a modular system architecture that is composed of domain-independent components implementing techniques from the respective areas. Systems based on this architecture -- so-called \emph{Companion}-Systems -- can provide intelligent assistance in a broad variety of tasks. They provide a user- and situation-adapted sequence of instructions that show how achieve the respective task. Additional explanations are, like the instructions themselves, automatically derived based on a declarative model of the current task. These systems can react to unforeseen execution failures repairing their underlying plans if required. We introduce a prototype system that assists with setting up a home theater and use it as a running example as well as for an empirical evaluation with test subjects that shows the usefulness of our approach. We summarize the work of more than half a decade of research and development done by various research groups from different disciplines. Here, for the first time, we explain the full integration of all components thereby showing ``the complete picture'' of our approach to provide individualized and situation-adaptive user assistance.}, url_Paper = {https://bercher.net/publications/2018/Bercher2018AssemblyAssistant.pdf}, keywords = {various} } @Article{Bercher2016SmithInterview, Title = {Interview with {David E. Smith}}, Author = {Pascal Bercher and Daniel H\"oller}, Journal = {K{\"u}nstliche Intelligenz}, Year = {2016}, Note = {Special Issue on Companion Technologies}, Number = {1}, Pages = {101--105}, Volume = {30}, Doi = {10.1007/s13218-015-0403-y}, abstract = {David E. Smith is a senior Researcher in the Intelligent Systems Division at NASA Ames Research Center. He received his Ph.D. in 1985 from Stanford University, and spent time as a Research Associate at Stanford, a Scientist at the Rockwell Palo Alto Science Center, and a Visiting Scholar at the University of Washington before joining NASA in 1997. Beginning in 1999, he served as the lead of the 18 member planning and scheduling group at NASA Ames for 6 years before abdicating to devote more time to research. Much of his research has focused on pushing the boundaries of AI planning technology to handle richer models of time, concurrency, exogenous events, uncertainty, and oversubscription. Smith served as an Associate Editor for the Journal of Artificial Intelligence Research (JAIR) from 2001-2004, and as Guest Editor for the JAIR Special Issue and Special Track on the 3rd and 4th International Planning Competitions. He served on the JAIR Advisory Board 2004–2007. Smith was recognized as a AAAI Fellow in 2005, and served on the AAAI Executive Council 2007-2010.}, url_Paper = {https://bercher.net/publications/2016/Bercher2016SmithInterview.pdf}, keywords = {various} } @Article{Biundo2016Editorial, Title = {Special Issue on Companion Technologies}, Author = {Susanne Biundo and Daniel H\"oller and Pascal Bercher}, Journal = {K{\"u}nstliche Intelligenz}, Year = {2016}, Note = {This is the editorial of our Special Issue on Companion Technologies, in which we were the guest editors}, Number = {1}, Pages = {5--9}, Volume = {30}, Doi = {10.1007/s13218-015-0421-9}, abstract = {Dear reader, at present, we observe a rapid growth in the development of increasingly complex ``intelligent systems'' that serve users throughout all areas of their daily lives. They range from classical technical systems such as household appliances, cars, or consumer electronics through mobile apps and services to advanced service robots in various fields of application. While many of the rather conventional systems already provide multiple modalities to interact with, the most advanced are even equipped with cognitive abilities such as perception, cognition, and reasoning. However, the use of such complex technical systems and in particular the actual exploitation of their rich functionality remain challenging and quite often lead to users' cognitive overload and frustration. Companion Technologies bridge the gap between the extensive functionality of technical systems and human users' individual requirements and needs. They enable the construction of really smart -- adaptive, flexible, and cooperative -- technical systems by applying and fusing techniques from different areas of research. In our special issue we present interesting pieces of work -- quite a number of new technical contributions, ongoing and completed research projects, several dissertation abstracts, as well as an interview -- that are related to, or even fundamental for, Companion-Technology. In the community part of this issue, there is also a conference report on the first International Symposium on Companion-Technology}, url_Paper = {https://bercher.net/publications/2016/Biundo2016Editorial.pdf}, keywords = {various} } @InProceedings{Bercher2018DissertationAbstract, Title = {Hybrides Planen --- Von der Theorie zur Praxis}, Author = {Pascal Bercher}, Booktitle = {Ausgezeichnete Informatikdissertationen 2017}, Year = {2018}, pages = {21--30}, Publisher = {Gesellschaft für Informatik}, abstract = {Die Dissertation legt Grundlagen, die es erlauben, Planungstechnologie der Künstlichen Intelligenz als Basis für flexible Assistenzsysteme einzusetzen. Die Aufgabe der automatischen Handlungsplanung ist es hierbei, selbständig einen Plan zu entwickeln, der dem Nutzer Schritt für Schritt präsentiert wird und ihn oder sie bei der Bearbeitung einer entsprechenden Aufgabe anleitet. Durch die starke Miteinbeziehung eines menschlichen Nutzers ergeben sich viele neue Herausforde- rungen: Pläne müssen schnell gefunden werden; und sie sollen nicht nur korrekt sein, sondern auch kostengünstig und dem Nutzer plausibel erscheinen; und sie sollen erklärbar sein, um Transparenz zu schaffen. Aus diesem Grund wurde das hybride Planen gewählt, ein hierarchischer, nicht-linearer Planungsansatz. Es wurden neue Komplexitätsergebnisse für das Planexistenz- und das Planverifikationsproblem erzielt; die ersten zulässigen Heuristiken erforscht, welche das Finden optimaler Pläne garantieren; und es wurde ein prototypisches Assistenzsystem realisiert, das seinen Nutzer bei dem Aufbau einer komplexen Heimkinoanlage unterstützt.}, note = {This dissertation abstract (in German) was written as part of being nominated for the GI (Gesellschaft für Informatik, eng.: Society for Computer Science) Best Dissertation Award 2017.}, url_Paper = {https://bercher.net/publications/2018/Bercher2018DissertationAbstract.pdf}, url_Slides = {https://bercher.net/publications/2018/Bercher2018DissertationAbstractSlides.pdf}, url_Proceedings = {https://dl.gi.de/bitstream/handle/20.500.12116/19479/lni-d-18-komplet.pdf}, url_Papers-of-Nominated-Theses = {https://dl.gi.de/handle/20.500.12116/19456}, keywords = {various} } @InProceedings{Bercher2015DissertationAbstractDC, Title = {Hybrid Planning -- Theoretical Foundations and Practical Applications}, Author = {Pascal Bercher}, Booktitle = {Doctoral Consortium at ICAPS 2015 (ICAPS DC 2015)}, Year = {2015}, abstract = {The thesis presents a novel set-theoretic formalization of (propositional) hybrid planning -- a planning framework that fuses Hierarchical Task Network (HTN) planning with Partial-Order Causal-Link (POCL) planning. Several sub classes thereof are identified that capture well-known problems such as HTN planning and POCL planning. For these problem classes, the complexity of the plan-existence problem is investigated, i.e., the problem of deciding whether there exists a solution for a given planning problem. For solving the problems of the respective problem classes, a hybrid planning algorithm is presented. Its search is guided by informed heuristics. Several such heuristics are introduced, both for POCL planning problems (i.e., problems without task hierarchy) and for hybrid planning problems (i.e., heuristics that are ''hierarchy-aware'').}, url_Paper = {https://bercher.net/publications/2015/Bercher2015DissertationAbstractDC.pdf}, url_Slides = {https://bercher.net/publications/2015/Bercher2015DissertationAbstractDCSlides.pdf}, url_Poster = {https://bercher.net/publications/2015/Bercher2015DissertationAbstractDCPoster.pdf}, keywords = {various} } @PhdThesis{Bercher2017PhDThesis, Title = {Hybrid Planning --- From Theory to Practice}, Author = {Pascal Bercher}, School = {Ulm University}, Year = {2018}, doi = {10.18725/OPARU-5242}, abstract = {This work lays fundamental groundwork for the development of so-called Companion Systems - cognitive technical systems that are capable to reason about themselves, their users and environment, and to plan a course of action to achieve their users' goals. They are intelligent devices that assist their users in operating them: instead of the user having to learn how to operate the respective system, the system is intelligent and flexible enough to provide its functionality in a truly user-friendly way.

To fully meet a user's demands, Companion Systems rely on a multi-facet of capabilities that stem from different disciplines, such as Artificial Intelligence (AI) planning, knowledge representation and reasoning, dialog management, and user interaction management, to name just a few. This thesis focuses on the relevant aspects of AI planning technology that are of importance for such systems. AI planning is the central technology for many Companion Systems as it allows to compute a course of action that, if followed by its user, achieves his or her goals and therefore serves as a basis of providing advanced user assistance. This thesis is concerned with hybrid planning - a hierarchical planning formalism that is especially suited for the basis of providing assistance to human users. Based on this formalism we will investigate the full endeavor of developing Companion Systems - from theory to practice.

The thesis presents a novel formalization for hierarchical planning problems, which has become a standard in the field. We present a categorization of different problem classes into which hybrid planning as well as other well-known problem classes fall. This formalization allowed to prove a series of novel complexity results that are of interest both for theoretical and practical considerations. For many of the identified classes we introduce novel heuristics that are used to speed up the solution generation process. Some of them are the very first for the respective problem class, and some are the first admissible ones, thereby allowing to find optimal solutions -- which is especially important when plans are generated for human users. We apply hybrid planning in a prototypical Companion System. It assists a user in the task of setting up a complex home entertainment system. Based on a declarative (planning) model of the available hardware and its functionality, the assistant computes a sequence of actions that the user simply needs to follow to complete the setup task. Several so-called user-centered planning capabilities are applied in this system, such as a technique for generating user-friendly linearizations of non-linear plans or the capability to answer questions about the necessity of actions - an essential property to ensure transparency of the system's behavior. In conclusion: Most modern technical devices are still lacking true intelligence - since no research such as AI planning is sufficiently applied, so there is still huge potential in making such devices really smart by implementing them as cognitive systems that effectively assist their human users. Applying the research presented in this thesis is one step towards achieving this goal.}, note = {This work won the ICAPS Best Dissertation Award 2019}, url_Dissertation = {https://bercher.net/publications/2017/Bercher2017Dissertation.pdf}, url_Slides-from-ICAPS-Award = {https://bercher.net/publications/2017/Bercher2019ICAPSDissertationTalk.pdf}, keywords = {various} } @techreport{Bercher2008FONDPGHeuristicTR, author = {Pascal Bercher and Robert Mattm{\"u}ller}, title = {A Planning Graph Heuristic for Forward-Chaining Adversarial Planning}, institution = {University of Freiburg, Germany}, year = {2008}, number = {238}, month = {7}, 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 report, we investigate a forward-chaining 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.}, url_Paper = {https://bercher.net/publications/2008/Bercher2008FONDPGHeuristicTR.pdf}, keywords = {various} } @Proceedings{HPlan2025proceedings, editor = {Pascal Bercher and Mauro Vallati and Conny Olz and Ron Alford}, title = {Proceedings of the 8th ICAPS Workshop on Hierarchical Planning (HPlan 2025)}, year = {2025}, url_website = {http://hplan2025.hierarchical-task.net}, url_proceedings = {https://icaps25.icaps-conference.org/files/HPlan/HPlanProceedings-2025.pdf}, keywords = {proceedings} } @Proceedings{HPlan2024proceedings, editor = {Pascal Bercher and Dominik Schreiber and Simona Ondrčková and Ron Alford}, title = {Proceedings of the 7th ICAPS Workshop on Hierarchical Planning (HPlan 2024)}, year = {2024}, url_website = {http://hplan2024.hierarchical-task.net}, url_proceedings = {https://icaps24.icaps-conference.org/program/workshops/hplan/HPlanProceedings-2024.pdf}, keywords = {proceedings} } @Proceedings{HPlan2023proceedings, editor = {Pascal Bercher and Daniel H\"oller and Julia Wichlacz and Ron Alford}, title = {Proceedings of the 6th ICAPS Workshop on Hierarchical Planning (HPlan 2023)}, year = {2023}, url_website = {http://hplan2023.hierarchical-task.net}, url_proceedings = {https://icaps23.icaps-conference.org/papers/hplan/HPlanProceedings-2023.pdf}, keywords = {proceedings} } @Proceedings{HPlan2022proceedings, editor = {Pascal Bercher and Jane Jean Kiam and Arthur Bit-Monnot and Ron Alford}, title = {Proceedings of the 5th ICAPS Workshop on Hierarchical Planning (HPlan 2022)}, year = {2022}, url_website = {http://hplan2022.hierarchical-task.net}, url_proceedings = {https://icaps22.icaps-conference.org/workshops/HPlan/papers/HPlanProceedings-2022.pdf}, keywords = {proceedings} } @proceedings{HPlan2021proceedings, Title = {Proceedings of the 4thd ICAPS Workshop on Hierarchical Planning (HPlan 2021)}, editor = {Pascal Bercher and Jane Jean Kiam and Zhanhao Xiao and Ron Alford}, Year = {2021}, url_Proceedings = {https://hierarchical-task.net/publications/hplan/HPlanProceedings-2021.pdf}, url_Workshop = {http://hplan2021.hierarchical-task.net}, keywords = {proceedings} } @proceedings{HPlan2020proceedings, Title = {Proceedings of the 3rd ICAPS Workshop on Hierarchical Planning (HPlan 2020)}, editor = {Pascal Bercher and Daniel H{\"o}ller and Roman Bart{\'a}k and Ron Alford}, Year = {2020}, url_Proceedings = {https://hierarchical-task.net/publications/hplan/HPlanProceedings-2020.pdf}, url_Workshop = {http://hplan2020.hierarchical-task.net}, keywords = {proceedings} } @proceedings{HPlan2019proceedings, Title = {Proceedings of the 2nd ICAPS Workshop on Hierarchical Planning (HPlan 2019)}, editor = {Pascal Bercher and Gregor Behnke and Vikas Shivashankar and Ron Alford}, Year = {2019}, url_Proceedings = {https://hierarchical-task.net/publications/hplan/HPlanProceedings-2019.pdf}, url_Workshop = {http://hplan2019.hierarchical-task.net}, keywords = {proceedings} } @proceedings{HPlan2018proceedings, Title = {Proceedings of the 1st ICAPS Workshop on Hierarchical Planning (HPlan 2018)}, editor = {Pascal Bercher and Daniel H{\"o}ller and Susanne Biundo and Ron Alford}, Year = {2018}, url_Proceedings = {https://hierarchical-task.net/publications/hplan/HPlanProceedings-2018.pdf}, url_Workshop = {http://hplan2018.hierarchical-task.net}, keywords = {proceedings} } @Proceedings{ICAPS-DC-2022, title = {Proceedings of the 20th ICAPS Doctoral Consortium (ICAPS DC 2022)}, year = {2022}, editor = {Pascal Bercher and Sara Bernardini}, abstract = {This is the proceedings of the ICAPS Doctoral Consortium 2022.}, url_website = {https://icaps22.icaps-conference.org/dc-2022}, url_proceedings = {https://icaps22.icaps-conference.org/dc/DC-Proceedings-2022.pdf}, keywords = {proceedings} } @proceedings{IPC2020Booklet, title = {Proceedings of 10th {I}nternational {P}lanning {C}ompetition: Planner and Domain Abstracts -- Hierarchical Task Network (HTN) Planning Track (IPC 2020)}, year = {2021}, editor = {Gregor Behnke and Daniel H{\"o}ller and Pascal Bercher}, url_IPC-Booklet = {https://bercher.net/publications/2021/Behnke2021IPC-Booklet.pdf}, abstract = {

Since its first edition in 1998, the International Planning Competition (IPC) has been an integral event of the planning community. For more than 20 years, it established unified input languages for planners, enabled an objective comparison between them based on an accessible benchmark set. The IPC drove the development of planners and fostered research. Thus, the IPC enabled planning researchers to compare their own work against the work of others -- not only within the competition, but also outside of it. Due to the IPC almost all contemporary planners understand (some form of) PDDL, which allows for using IPC benchmarks across a multitude of planners.


The first two IPCs had -- in addition to the regular track -- a track on hand-tailored planners in which the planners could be provided with additional information or select their algorithms based on the input domain. Among these planners, some used Hierarchical Planning -- most notably SHOP. Following the second IPC in 2000 the hand-tailored track was discontinued. Hierarchical planning was thereafter not part of the IPC any more. Research in the field however continued.


The International Planning Competition 2020 features for the first time a track dedicated to hierarchical planning. In contrast to the previous track on hand-tailored planners we don't want to evaluate how good planners can become given any possible additional knowledge, but ask how well planners can exploit a given hierarchical refinement structure. We therefore faced several unique challenges. We had to establish a common input language for all planners such that all of them operate on the very same model. We also had to specify a plan-output format and provide a verifier, since we had to ensure that the found plans satisfy the decompositional structure of the given task hierarchy. Further, we had to gather a comprehensive set of benchmark domains, since no such set existed before. We hope that this first competition for Hierarchical Task Network planners will foster future research into hierarchical planning and provide a common basis for many researchers -- by establishing a unified input language, a common benchmark set, and an evaluation of the state of the art in HTN planning. We hope that many future editions of this competition will follow.


Gregor, Daniel, and Pascal

Organizers of the IPC 2020,

May 2021}, keywords = {proceedings} } @proceedings{WIPC2021Proceedings, Title = {Proceedings of the Workshop on the International Planning Competition (WIPC 2021)}, editor = {Gregor Behnke and Daniel H{\"o}ller and Pascal Bercher}, Year = {2021}, url_Proceedings = {https://bercher.net/publications/2021/WIPC2021Proceedings.pdf}, url_Workshop = {https://icaps21.icaps-conference.org/workshops/WIPC/}, keywords = {proceedings} } @misc{Schiller2025IJHCISupplement, author = {Marvin Schiller and Matthias Kraus and Gregor Behnke and Michael Dorna and Michael Dambier and Stephanie Linder and Heiko Taxis and Susanne Biundo and Wolfgang Minker and Birte Glimm and Pascal Bercher}, publisher = {Harvard Dataverse}, title = {{Questionnaires Supplement for the IJHCI Article ``Designing an Intelligent Do-It-Yourself (DIY) Assistant in a User-Centered Process -- AI Planning, Knowledge Representation, and Proactive Dialog for Supporting Aspiring DIY Novices''}}, year = {2025}, note = {version V2}, doi = {10.7910/DVN/DYXJQF}, keywords = {experiments} } @misc{Bavandpour2025ExperimentalResultsLiftedTestPlans, author = {Nader Karimi Bavandpour and Pascal Lauer and Songtuan Lin and Pascal Bercher}, title = {Supplementary Material, Code, and Experimental Results for the ECAI 2025 Paper: ``Repairing Planning Domains Based on Lifted Test Plans''}, year = {2025}, publisher = {Zenodo}, doi = {10.5281/zenodo.16935964}, keywords = {experiments} } @misc{Welt2025ExperimentalResultsSolveTheUnsolvable, author = {Michael Welt and Alexander Lodemann and Conny Olz and Pascal Bercher and Birte Glimm}, title = {Experimental Setup for the {ECAI} 2025 Paper: ``{C}alculating {O}ptimal {C}orrections for {U}nsolvable {P}lanning {P}roblems''}, year = {2025}, publisher = {Zenodo}, doi = {10.5281/zenodo.16761001}, keywords = {experiments} } @misc{Olz2025ExperimentalResultsCompoundPrecEffInference, author = {Conny Olz and Alexander Lodemann and Benedikt Jutz and Mario Schmautz and Maximilian Borowiec and Susanne Biundo and Pascal Bercher}, title = {Experimental Results for the {JAIR} Article ``{A}n Extensive Empirical Evaluation of Inferring Preconditions and Effects of Compound Tasks in Ground {HTN} Planning Problems''}, year = {2025}, copyright = {Creative Commons Attribution 4.0 International}, doi = {10.5281/zenodo.14678643}, publisher = {Zenodo}, keywords = {experiments} } @Misc{Lin2024ExperimentalResultsSATVerifier, author = {Songtuan Lin and Gregor Behnke and Pascal Bercher}, title = {Experimental Results for the ECAI 2023 Paper ``Accelerating SAT-Based HTN Plan Verification by Exploiting Data Structures from HTN Planning''}, year = {2024}, copyright = {Creative Commons Attribution 4.0 International}, doi = {10.5281/ZENODO.10906075}, publisher = {Zenodo}, keywords = {experiments} } @Misc{Lin2024ExperimentalResultsRepairingDomains, author = {Songtuan Lin and Alban Grastien and Rahul Shome and Pascal Bercher}, title = {Experimental Results for the AAAI 2025 Paper: ``Told You That Will Not Work: Optimal Corrections to Planning Domains Using Counter-Example Plans''}, year = {2024}, copyright = {Creative Commons Attribution 4.0 International}, doi = {10.5281/ZENODO.14533200}, publisher = {Zenodo}, keywords = {experiments} } @Misc{Olz2024TOILPExperiments, author = {Conny Olz and Alexander Lodemann and Pascal Bercher}, title = {Experimental Results for the {ECAI} 2024 Paper ``{A} Heuristic for Optimal Total-Order {HTN} Planning Based on Integer Linear Programming''}, year = {2024}, doi = {10.5281/zenodo.13269291}, publisher = {Zenodo}, keywords = {experiments} } @Misc{Lin2024ExpRepairingHTNDomains, author = {Songtuan Lin and Daniel H\"oller and Pascal Bercher}, title = {Experimental Results for the SoCS 2024 Paper: ``Modeling Assistance for Hierarchical Planning: An Approach for Correcting Hierarchical Domains with Missing Actions''}, year = {2024}, copyright = {Creative Commons Attribution 4.0 International}, doi = {10.5281/zenodo.10946945}, publisher = {Zenodo}, keywords = {experiments} } @Misc{Yousefi2024ExperimantalData, author = {Mohammad Yousefi and Pascal Bercher}, title = {Experimental Setup for the {IJCAI} 2024 Paper: ``{L}aying the Foundations for Solving {FOND} {HTN} Problems: Grounding, Search, Heuristics (and Benchmark Problems)''}, year = {2024}, copyright = {Creative Commons Attribution 4.0 International}, doi = {10.5281/zenodo.11172885}, publisher = {Zenodo}, keywords = {experiments} } @Misc{Olz2023ExperimentalData, author = {Conny Olz and Pascal Bercher}, title = {Experimental Results for the SoCS 2023 Paper ``A Look-Ahead Technique for Search-Based HTN Planning: Reducing the Branching Factor by Identifying Inevitable Task Refinements''}, year = {2023}, copyright = {Creative Commons Attribution 4.0 International}, doi = {10.5281/zenodo.7900414}, publisher = {Zenodo}, keywords = {experiments} } @Misc{Sleath2023ExperimentalData, author = {Kayleigh Sleath and Pascal Bercher}, title = {Experimental Results for the PRICAI 2023 Paper ``Detecting AI Planning Modelling Mistakes -- Potential Errors and Benchmark Domains''}, year = {2023}, copyright = {Creative Commons Attribution 4.0 International}, doi = {10.5281/zenodo.8249689}, publisher = {Zenodo}, keywords = {experiments} } @Misc{Lin2023RepairingClassicalModelsExperimentalResults, author = {Songtuan Lin and Alban Grastien and Pascal Bercher}, title = {Experimental Results for the AAAI 2023 Paper ``Towards Automated Modeling Assistance: An Efficient Approach for Repairing Flawed Planning Domains''}, year = {2023}, copyright = {Creative Commons Attribution 4.0 International}, doi = {10.5281/zenodo.7690016}, publisher = {Zenodo}, keywords = {experiments} } @Misc{Lin2023ExperimentalResultsTOVerification, author = {Songtuan Lin and Gregor Behnke and Simona Ondr\v{c}kov{\'{a}} and Roman Bart{\'{a}}k and Pascal Bercher}, title = {Experimental Results for the AAAI 2023 Paper ``On Total-Order HTN Plan Verification with Method Preconditions -- An Extension of the CYK Parsing Algorithm''}, year = {2023}, copyright = {Creative Commons Attribution 4.0 International}, doi = {10.5281/zenodo.7704558}, publisher = {Zenodo}, keywords = {experiments} } @InProceedings{Yousefi2025HDDLVSPlugin, author = {Mohammad Yousefi and Pascal Bercher}, booktitle = {ICAPS 2025 Demonstrations}, title = {HDDL Parser: A Realtime Hierarchical Planning Language Validation Toolkit}, year = {2025}, abstract = {We present HDDL Parser, an open-source language server providing real-time validation for the Hierarchical Planning Domain Definition Language (HDDL). The toolkit implements the well-known Language Server Protocol (LSP), enabling integration into any IDE, with a provided VS Code client demonstrating seamless real-time error detection and correction feedback. The language server performs a comprehensive analysis including: syntax validation, parameter inconsistencies, undefined entities, duplicate definitions, cyclic hierarchies, contradictory formulae, and type checking. Implemented in Rust, the correctness of the HDDL Parser has been validated against all 33 domains from the hierarchical track of the IPC 2023, and even detected critical errors in one of those domains. By providing automated quality assurance directly within the development environment, this tool significantly reduces debugging time and improves model reliability for hierarchical planning applications.}, url_Paper = {https://bercher.net/publications/2025/Yousefi2025HDDLVSPlugin.pdf}, url_Poster = {https://bercher.net/publications/2025/Yousefi2025HDDLVSPluginPoster.pdf}, url_video_of_tool = {https://www.youtube.com/watch?v=hRZ21HmcEQU}, keywords = {demo,DECRA} } @InProceedings{Lin2024ModelingSupportVSPlugin, author = {Songtuan Lin and Mohammad Yousefi and Pascal Bercher}, booktitle = {ICAPS 2024 Demonstrations}, title = {A Visual Studio Code Extension for Automatically Repairing Planning Domains}, year = {2024}, abstract = {We demonstrate a Visual Studio Code extension which aims at providing modeling assistance for modeling planning domains in PDDL. More specifically, the extension can identify potential flaws in a domain and propose respective corrections by taking as input a set of counter-example plans, which are known to be valid but actually contradict the domain. Those input plans shall be provided by the user. The flaws are then identified and corrected by making changes to the domain so as to turn those plans into solutions, i.e., the changes are regarded as potential corrections to the domain. Currently, the extension only supports corrections that add predicates to or remove predicates from actions' preconditions and effects.}, url_Paper = {https://bercher.net/publications/2024/Lin2024ModelingSupportVSPlugin.pdf}, keywords = {demo,DECRA} } @Inproceedings{Kraus2018CompanionCloudDemo, author = {Kraus, Matthias and Behnke, Gregor and Pascal Bercher and Schiller, Marvin and Biundo, Susanne and Glimm, Birte and Minker, Wolfgang}, title = {A Multimodal Dialogue Framework for Cloud-Based Companion Systems}, year = {2018}, booktitle = {Proceedings of the 9th International Workshop on Spoken Dialog Systems Technology (IWSDS 2018)}, abstract = {Companion systems are cooperative, cognitive systems aiming at assisting a user in everyday situations. Therefore, these systems require a high level of availability. One option to meet this requirement is to use a web-deployable architecture. In this demo paper, we present a multimodal cloud-based dialogue framework for the development of a distributed, web-based companion system. The proposed framework is intended to provide an efficient, easily extensible, and scalable approach for this kind of systems and will be demonstrated in a do-it-yourself assistance scenario.}, url_Paper = {https://bercher.net/publications/2018/Kraus2018CompanionCloudDemo.pdf}, keywords = {demo} } @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 = {demo} } @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}, note = {This paper is describing a AAAI System Demonstration}, 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 = {demo} }