@InProceedings{Olz2024TOILPHeuristic,
  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}
}

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.

@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}
}

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.

@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}
}

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.

@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       = {<strong>Erratum:</strong> 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}
}

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.

@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}
}

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

@InProceedings{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}
}

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.

@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}
}

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.

@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}
}

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.

@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}
}

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.

@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}
}

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.

@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}
}

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.

@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}
}

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.

@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}
}

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.

@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}
}

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.

@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}
}

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.

@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}
}

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.

@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}
}

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.

@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}
}

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.

@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       = {<strong>Erratum:</strong> 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}
}

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.

@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}
}

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.

@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}
}

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.

@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}
}

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.

@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}
}

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.

@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}
}

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{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  = {workshop}
}

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.

@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}
}

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.

@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}
}

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.

@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}
}

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.

@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}
}

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.

@InProceedings{Bercher13EncodingPlans,
  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}
}

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.

@Inproceedings{Bercher13POCLSoftGoals,
  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}
}

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

@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}
}

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.

@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}
}

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.

@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}
}

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.