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

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

@InProceedings{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                      = {<b><i>This paper won the ICAPS 2022 Best Undergraduate Student Paper Award</i></b>}
}

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.

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

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

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

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

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

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

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

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

@InProceedings{Hoeller2018ProgressionHeuristics,
  author                    = {Daniel H{\"{o}}ller and Pascal Bercher and Gregor Behnke and Susanne Biundo},
  title                     = {A Generic Method to Guide {HTN} Progression Search with Classical Heuristics},
  booktitle                 = {Proceedings of the 28th International Conference on Automated Planning and Scheduling ({ICAPS 2018})},
  note                      = {<b><i>This paper won the ICAPS 2018 Best Student Paper Award</i></b>},
  publisher                 = {{AAAI} Press},
  year                      = {2018},
  pages                     = {114--122},
  abstract                  = {HTN planning combines actions that cause state transition with grammar-like decomposition of compound tasks that additionally restricts the structure of solutions. There are mainly two strategies to solve such planning problems: decomposition-based search in a plan space and progression-based search in a state space. Existing progression-based systems do either not rely on heuristics (e.g. SHOP2) or calculate their heuristics based on extended or modified models (e.g. GoDeL). Current heuristic planners for standard HTN models (e.g. PANDA) use decomposition-based search. Such systems represent search nodes more compactly due to maintaining a partial order between tasks, but they have no current state at hand during search. This makes the design of heuristics difficult. In this paper we present a progression-based heuristic HTN planning system: We (1) provide an improved progression algorithm, prove its correctness, and empirically show its efficiency gain; and (2) present an approach that allows to use arbitrary classical (non-hierarchical) heuristics in HTN planning. Our empirical evaluation shows that the resulting system outperforms the state-of-the-art in HTN planning.},
  doi                       = {10.1609/icaps.v28i1.13900},
  url_Paper                 = {https://bercher.net/publications/2018/Hoeller2018ProgressionHeuristics.pdf},
  url_video_of_presentation = {https://www.youtube.com/watch?v=KOZuIkJaC0w},
  keywords                  = {conference}
} 

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