Hierarchical Planning : Expressivity Analysis, Solving Techniques, and Problem Compilations
Loading...
Date
2023-02-24
Authors
Höller, Daniel
Journal Title
Journal ISSN
Volume Title
Publication Type
Dissertation
Published in
Abstract
Automated planning enables systems to act in a goal-directed way and flexibly react on their environment and other agents. This makes it a valuable technology for intelligent systems. Based on a model of the environment and a goal to reach or a task to accomplish, those systems come up with a detailed plan on how to achieve it. Two widely-used approaches to planning are classical planning and hierarchical planning. Classical planning comes with a large number of domain-independent solving techniques that enable a simple adaptation to new application domains. The motivation to use a hierarchy (which is usually defined on the things to do, the tasks) is manifold: some application domains can be modeled much more intuitive using hierarchical structures, the hierarchy can be exploited to communicate with a human user on different levels of abstraction, and it has often been used to guide the search to find solutions more quickly. Further it enables the definition of more complex behavior patterns than possible with commonly-used non-hierarchical formalisms. In both classical and hierarchical planning, there is a range of slightly different formalisms that come with different properties. This thesis advances the state of the art in hierarchical planning along three lines of research. We provide an expressivity analysis of common planning formalisms, novel solving techniques for hierarchical planning, and compilations to solve three problems related to planning.
We first systematically investigate the expressivity of different classical and hierarchical planning formalisms. To this end, we compare them with formal languages and show what kind of languages can be expressed by which formalism. We show that the expressivity ranges from a subset of the regular languages for basic classical planning to a (non-context-free) subset of the context-sensitive languages for the most widely-used hierarchical formalism called Hierarchical Task Network (HTN) planning.
We introduce novel solving techniques for HTN planning. We start with a new input language that became the standard for the 2020 International Planning Competition (IPC) and a grounding technique to compile the first-order model used to specify the planning domain into a propositional model as required for most planning systems. Then we show how HTN planners based on heuristic search can benefit from the sophisticated domain-independent heuristics developed for classical planning. We introduce a generic method to use them to guide the HTN search. Our system outperforms the participants of the 2020 IPC and several other systems from the literature. We further show that our techniques can also be used to find optimal plans, i.e. plans with minimal action cost.
Besides plan generation, there are several related tasks to solve when applying planning in intelligent systems. For three of them, we show how they can be compiled into standard planning problems. This enables the use of standard planning systems to solve the problems instead of coming up with specialized solvers. We introduce compilations for (1) plan and goal recognition, the task of identifying the goals and plans of other agents, (2) plan repair, the task of coming up with a novel plan when the execution of an initial one failed, and (3) plan verification, the task of deciding whether a given sequence of actions is a solution for a given problem.
In reference to IEEE copyrighted material which is used with permission in this thesis, the IEEE does not endorse any of Ulm University's products or services. Internal or personal use of this material is permitted. If interested in reprinting/republishing IEEE copyrighted material for advertising or promotional purposes or for creating new collective works for resale or redistribution, please go to http://www.ieee.org/publications_standards/publications/rights/rights_link.html to learn how to obtain a License from RightsLink.
In reference to IEEE copyrighted material which is used with permission in this thesis, the IEEE does not endorse any of Ulm University's products or services. Internal or personal use of this material is permitted. If interested in reprinting/republishing IEEE copyrighted material for advertising or promotional purposes or for creating new collective works for resale or redistribution, please go to http://www.ieee.org/publications_standards/publications/rights/rights_link.html to learn how to obtain a License from RightsLink.
Description
Faculties
Fakultät für Ingenieurwissenschaften, Informatik und Psychologie
Institutions
Institut für Künstliche Intelligenz
Citation
DFG Project uulm
TRR 62 Teilprojekt T03 / Do it yourself, but not alone: Companion - Technology for DIY support / DFG / 54371073
TRR 62 / Eine Companion-Technologie für kognitive technische Systeme / DFG / 54371073
SFB 1102 / Informationsdichte und sprachliche Kodierung / DFG / 232722074
TRR 62 / Eine Companion-Technologie für kognitive technische Systeme / DFG / 54371073
SFB 1102 / Informationsdichte und sprachliche Kodierung / DFG / 232722074
EU Project THU
Other projects THU
License
Lizenz B (ohne Print-on-Demand)
Is version of
Has version
Supplement to
Supplemented by
Has erratum
Erratum to
Has Part
D. Höller, G. Behnke, P. Bercher, and S. Biundo. “Language Classification of Hierarchical Planning Problems.” In: Proceedings of the 21st European Conference on Artificial Intelligence (ECAI). IOS Press, 2014, pp. 447–452, https://doi.org/10.3233/978-1-61499-419-0-447
G. Behnke, D. Höller, and S. Biundo. “On the Complexity of HTN Plan Verification and its Implications for Plan Recognition.” In: Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS). AAAI Press, 2015, pp. 25–33
D. Höller, G. Behnke, P. Bercher, and S. Biundo. “Assessing the Expressivity of Planning Formalisms through the Comparison to Formal Languages.” In: Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS). AAAI Press, 2016, pp. 158–165
D. Höller, P. Bercher, G. Behnke, and S. Biundo. “A Generic Method to Guide HTN Progression Search with Classical Heuristics.” In: Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS). AAAI Press, 2018, pp. 114–122
D. Höller, G. Behnke, P. Bercher, and S. Biundo. “Plan and Goal Recognition as HTN Planning.” In: Proceedings of the 30th International Conference on Tools with Artificial Intelligence (ICTAI). IEEE Computer Society, 2018, pp. 466–473, https://doi.org/10.1109/ICTAI.2018.00078
D. Höller, P. Bercher, G. Behnke, and S. Biundo. “On Guiding Search in HTN Planning with Classical Planning Heuristics.” In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI). IJCAI Organization, 2019, pp. 6171–6175, https://doi.org/10.24963/ijcai.2019/857
G. Behnke, D. Höller, and S. Biundo. “Finding Optimal Solutions in HTN Planning – A SAT-based Approach.” In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI). IJCAI Organization, 2019, pp. 5500–5508, https://doi.org/10.24963/ijcai.2019/764
D. Höller, P. Bercher, G. Behnke, and S. Biundo. “HTN Planning as Heuristic Progression Search.” In: The Journal of Artificial Intelligence Research (JAIR) 67 (2020), pp. 835–880, https://doi.org/10.1613/jair.1.11282
D. Höller, P. Bercher, G. Behnke, and S. Biundo. “HTN Plan Repair via Model Transformation.” In: Proceedings of the 43rd German Conference on AI (KI). Springer, 2020, pp. 88–101, https://doi.org/10.1007/978-3-030-58285-2_7
D. Höller, G. Behnke, P. Bercher, S. Biundo, H. Fiorino, D. Pellier, and R. Alford. “HDDL: An Extension to PDDL for Expressing Hierarchical Planning Problems.” In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 2020, pp. 9883–9891
G. Behnke, D. Höller, A. Schmid, P. Bercher, and S. Biundo. “On Succinct Groundings of HTN Planning Problems.” In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 2020, pp. 9775–9784
D. Höller, G. Behnke, P. Bercher, and S. Biundo. “The PANDA Framework for Hierarchical Planning.” In: Künstliche Intelligenz (KI) 35.3 (2021), pp. 391–396, https://doi.org/10.1007/s13218-020-00699-y
D. Höller and G. Behnke. “Loop Detection in the PANDA Planning System.” In: Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS). AAAI Press, 2021, pp. 168–173
G. Behnke, D. Höller, and S. Biundo. “On the Complexity of HTN Plan Verification and its Implications for Plan Recognition.” In: Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS). AAAI Press, 2015, pp. 25–33
D. Höller, G. Behnke, P. Bercher, and S. Biundo. “Assessing the Expressivity of Planning Formalisms through the Comparison to Formal Languages.” In: Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS). AAAI Press, 2016, pp. 158–165
D. Höller, P. Bercher, G. Behnke, and S. Biundo. “A Generic Method to Guide HTN Progression Search with Classical Heuristics.” In: Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS). AAAI Press, 2018, pp. 114–122
D. Höller, G. Behnke, P. Bercher, and S. Biundo. “Plan and Goal Recognition as HTN Planning.” In: Proceedings of the 30th International Conference on Tools with Artificial Intelligence (ICTAI). IEEE Computer Society, 2018, pp. 466–473, https://doi.org/10.1109/ICTAI.2018.00078
D. Höller, P. Bercher, G. Behnke, and S. Biundo. “On Guiding Search in HTN Planning with Classical Planning Heuristics.” In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI). IJCAI Organization, 2019, pp. 6171–6175, https://doi.org/10.24963/ijcai.2019/857
G. Behnke, D. Höller, and S. Biundo. “Finding Optimal Solutions in HTN Planning – A SAT-based Approach.” In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI). IJCAI Organization, 2019, pp. 5500–5508, https://doi.org/10.24963/ijcai.2019/764
D. Höller, P. Bercher, G. Behnke, and S. Biundo. “HTN Planning as Heuristic Progression Search.” In: The Journal of Artificial Intelligence Research (JAIR) 67 (2020), pp. 835–880, https://doi.org/10.1613/jair.1.11282
D. Höller, P. Bercher, G. Behnke, and S. Biundo. “HTN Plan Repair via Model Transformation.” In: Proceedings of the 43rd German Conference on AI (KI). Springer, 2020, pp. 88–101, https://doi.org/10.1007/978-3-030-58285-2_7
D. Höller, G. Behnke, P. Bercher, S. Biundo, H. Fiorino, D. Pellier, and R. Alford. “HDDL: An Extension to PDDL for Expressing Hierarchical Planning Problems.” In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 2020, pp. 9883–9891
G. Behnke, D. Höller, A. Schmid, P. Bercher, and S. Biundo. “On Succinct Groundings of HTN Planning Problems.” In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 2020, pp. 9775–9784
D. Höller, G. Behnke, P. Bercher, and S. Biundo. “The PANDA Framework for Hierarchical Planning.” In: Künstliche Intelligenz (KI) 35.3 (2021), pp. 391–396, https://doi.org/10.1007/s13218-020-00699-y
D. Höller and G. Behnke. “Loop Detection in the PANDA Planning System.” In: Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS). AAAI Press, 2021, pp. 168–173
Part of
DOI external
DOI external
Institutions
Periodical
Degree Program
DFG Project THU
item.page.thu.projectEU
item.page.thu.projectOther
Series
Keywords
AI planning, Automated planning, HTN planning, Künstliche Intelligenz, Artificial intelligence, DDC 620 / Engineering & allied operations