% % This file was created by the TYPO3 extension % publications % --- Timezone: CEST % Creation date: 2024-03-28 % Creation time: 11:38:23 % --- Number of references % 42 % @Conference { Olz23PandaDealer, author = {Olz, Conny and H\"{o}ller, Daniel and Bercher, Pascal}, title = {The PANDADealer System for Totally Ordered HTN Planning in the 2023 IPC}, year = {2023}, booktitle = {Proceedings of the 11th International Planning Competition: Planner Abstracts – Hierarchical Task Network (HTN) Planning Track (IPC)}, file_url = {t3://file?uid=483768} } @Inproceedings { Hoeller2020HTNPlanRepair, author = {H\"{o}ller, Daniel and Bercher, Pascal and Behnke, Gregor and Biundo, Susanne}, title = {HTN Plan Repair via Model Transformation}, 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.}, year = {2020}, booktitle = {Proceedings of the 43th German Conference on Artificial Intelligence (KI 2020)}, publisher = {Springer}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2020/Hoeller20Repair.pdf} } @Article { 794390675559_2020, author = {H\"{o}ller, Daniel and Bercher, Pascal and Behnke, Gregor and Biundo, Susanne}, title = {HTN Planning as Heuristic Progression Search}, year = {2020}, journal = {Journal of Artificial Intelligence Research (JAIR)}, volume = {67}, publisher = {AAAI Press}, pages = {835--880}, file_url = {https://jair.org/index.php/jair/article/view/11282/26578} } @Inproceedings { Behnke2020SuccinctGrounding, author = {Behnke, Gregor and H\"{o}ller, Daniel and Schmid, Alexander and Bercher, Pascal and Biundo, Susanne}, title = {On Succinct Groundings of HTN Planning Problems}, 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.}, year = {2020}, booktitle = {Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020)}, publisher = {AAAI Press}, pages = {9775--9784}, tags = {SFB-T3}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2020/AAAI-BehnkeG.1770.pdf} } @Inproceedings { Hoeller20HDDL, author = {H\"{o}ller, Daniel and Behnke, Gregor and Bercher, Pascal and Biundo, Susanne and Fiorino, Humbert and Pellier, Damien and Alford, Ron}, title = {HDDL: An Extension to PDDL for Expressing Hierarchical Planning Problems}, 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.}, year = {2020}, booktitle = {Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020)}, publisher = {AAAI Press}, pages = {9883--9891}, tags = {SFB-TRR-62,Planning,SFB-T3}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2020/Hoeller2020HDDL.pdf} } @Inproceedings { Bercher2019HierarchicalPlanningSurvey, author = {Bercher, Pascal and Alford, Ron and H\"{o}ller, Daniel}, title = {A Survey on Hierarchical Planning - One Abstract Idea, Many Concrete Realizations}, abstract = {Hierarchical planning has attracted renewed interest in the last couple of years, which led to numerous novel formalisms, problem classes, and theoretical investigations. Yet it is important to differentiate between the various formalisms and problem classes, since they show -- sometimes fundamental -- differences with regard to their expressivity and computational complexity: Some of them can be regarded equivalent to non-hierarchical formalisms while others are clearly more expressive. We survey the most important hierarchical problem classes and explain their differences and similarities. We furthermore give pointers to some of the best-known planning systems capable of solving the respective problem classes.}, year = {2019}, booktitle = {Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019)}, publisher = {IJCAI}, pages = {6267-6275}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2019/Bercher2019HierarchicalPlanningSurvey.pdf} } @Inproceedings { Behnke2019orderCharos, author = {Behnke, Gregor and H\"{o}ller, Daniel and Biundo, Susanne}, title = {Bringing Order to Chaos - A Compact Representation of Partial Order in SAT-based HTN Planning}, abstract = {HTN planning provides an expressive formalism to model complex application domains and has been widely used in real-world applications. However, the development of domain-independent planning techniques for such models is still lacking behind. The need to be informed about both - state-transition and hierarchy - makes the realisation of search-based approaches difficult, especially with unrestricted partial ordering of tasks in HTN domains. Recently, a translation of HTN planning problems into propositional logic has shown promising empirical results. Such planners benefit from a unified representation of state and hierarchy, but until now require very large formulae to represent partial order. In this paper, we introduce a novel encoding of HTN Planning as SAT. In contrast to related work, most of the reasoning on ordering relations is not left to the SAT solver, but done beforehand. This results in much smaller formulae and, as shown in our evaluation, in a planner that outperforms previous SAT-based approaches as well as the state-of-the-art in search-based HTN planning.}, year = {2019}, booktitle = {Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI 2019)}, publisher = {AAAI Press}, pages = {7520--7529}, keywords = {Planning}, tags = {SFB-T3}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2019/Behnke2019orderchaos.pdf} } @Inproceedings { Behnke2019SAToptimal, author = {Behnke, Gregor and H\"{o}ller, Daniel and Biundo, Susanne}, title = {Finding Optimal Solutions in HTN Planning - A SAT-based Approach}, abstract = { Over the last years, several new approaches to Hierarchical Task Network (HTN) planning have been proposed that increased the overall performance of HTN planners. However, the focus has been on agile planning -- on finding a solution as quickly as possible. Little work has been done on finding \emph\{optimal\} plans. We show how the currently best-performing approach to HTN planning -- the translation into propositional logic -- can be utilised to find optimal plans. Such SAT-based planners usually bound the HTN problem to a certain depth of decomposition and then translate the problem into a propositional formula. To generate optimal plans, the \emph\{length\} of the solution has to be bounded instead of the decomposition \emph\{depth\}. We show the relationship between these bounds and how it can be handled algorithmically. Based on this, we propose an optimal SAT-based HTN planner and show that it performs favourably on a benchmark set. }, year = {2019}, booktitle = {Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019)}, tags = {SFB-T3,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2019/Behnke2019satoptimal.pdf} } @Inproceedings { Hoeller2019HDDL, author = {H\"{o}ller, Daniel and Behnke, Gregor and Bercher, Pascal and Biundo, Susanne and Fiorino, Humbert and Pellier, Damien and Alford, Ron}, title = {HDDL - A Language to Describe Hierarchical Planning Problems}, 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.}, year = {2019}, booktitle = {Proceedings of the Second ICAPS Workshop on Hierarchical Planning}, pages = {6--14}, tags = {SFB-T3}, file_url = {http://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2019/Hoeller2019HDDL.pdf} } @Inproceedings { Behnke2019ICP, author = {Behnke, Gregor and H\"{o}ller, Daniel and Bercher, Pascal and Biundo, Susanne and Pellier, Damien and Fiorino, Humbert and Alford, Ron}, title = {Hierarchical Planning in the IPC}, 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. }, year = {2019}, booktitle = {Proceedings of the Workshop on the International Planning Competition}, tags = {Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2019/Behnke2019HTNIPC.pdf} } @Inproceedings { Behnke2019GroundingWS, author = {Behnke, Gregor and H\"{o}ller, Daniel and Bercher, Pascal and Biundo, Susanne}, title = {More Succinct Grounding of HTN Planning Problems -- Preliminary Results}, 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.}, year = {2019}, booktitle = {Proceedings of the Second ICAPS Workshop on Hierarchical Planning}, pages = {40--48}, tags = {SFB-T3}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2019/Behnke2019Grounding.pdf} } @Inproceedings { Hoeller2019OnGuiding, author = {H\"{o}ller, Daniel and Bercher, Pascal and Behnke, Gregor and Biundo, Susanne}, title = {On Guiding Search in HTN Planning with Classical Planning Heuristics}, abstract = {Planning is the task of finding a sequence of actions that achieves the goal(s) of an agent. It is solved based on a model describing the environment and how to change it. There are several approaches to solve planning tasks, two of the most popular are classical planning and hierarchical planning. Solvers are often based on heuristic search, but especially regarding domain-independent heuristics, techniques in classical planning are more sophisticated. However, due to the different problem classes, it is difficult to use them in hierarchical planning. In this paper we describe how to use arbitrary classical heuristics in hierarchical planning and show that the resulting system outperforms the state of the art in hierarchical planning.}, year = {2019}, booktitle = {Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI 2019)}, publisher = {IJCAI}, pages = {6171--6175}, tags = {SFB-T3}, file_url = {http://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2019/Hoeller2019ProgressionHeuristics.pdf} } @Inproceedings { Behnke2018totSAT, author = {Behnke, Gregor and H\"{o}ller, Daniel and Biundo, Susanne}, title = {totSAT - Totally-Ordered Hierarchical Planning through SAT}, abstract = {In this paper, we propose a novel SAT-based planning approach for hierarchical planning by introducing the SAT-based planner totSAT for the class of totally-ordered HTN planning problems. We use the same general approach as SAT planning for classical planning does: bound the problem, translate the problem into a formula, and if the formula is not satisfiable, increase the bound. In HTN planning, a suitable bound is the maximum depth of decomposition. We show how totally-ordered HTN planning problems can be translated into a SAT formula, given this bound. Furthermore, we have conducted an extensive empirical evaluation to compare our new planner against state-of-the-art HTN planners. It shows that our technique outperforms any of these systems.}, year = {2018}, booktitle = {Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI 2018)}, publisher = {AAAI Press}, pages = {6110--6118}, event_name = {AAAI 2018}, event_place = {New Orleans}, keywords = {SFB-TRR-62,Planning}, tags = {SFB-TRR-62,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2018/Behnke2018totSAT.pdf} } @Inproceedings { Behnke2018treeSATICTAI, author = {Behnke, Gregor and H\"{o}ller, Daniel and Biundo, Susanne}, title = {Tracking Branches in Trees - A Propositional Encoding for Solving Partially-Ordered HTN Planning Problems}, abstract = {Planning via SAT has proven to be an efficient and versatile planning technique. Its declarative nature allows for an easy integration of additional constraints and can harness the progress made in the SAT community without the need to adapt the planner. However, there has been only little attention to SAT planning for hierarchical domains. To ease encoding, existing approaches for HTN planning require additional assumptions, like non-recursiveness or totally-ordered methods. Both limit the expressiveness of HTN planning severely. We propose the first propositional encodings which are able to solve general, i.e., partially-ordered, HTN planning problems, based on a previous encoding for totally-ordered problems. The empirical evaluation of our encoding shows that it outperforms existing HTN planners significantly.}, year = {2018}, booktitle = {Proceedings of the 30th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2018)}, publisher = {IEEE Computer Society}, pages = {73--80}, keywords = {SFB-TRR-62,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2018/Behnke2018treeSAT.pdf} } @Inproceedings { Leichtmann2018HumanPlanning, author = {Leichtmann, Benedikt and Bercher, Pascal and H\"{o}ller, Daniel and Behnke, Gregor and Biundo, Susanne and Nitsch, Verena and Baumann, Martin}, title = {Towards a Companion System Incorporating Human Planning Behavior -- A Qualitative Analysis of Human Strategies}, 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.}, year = {2018}, booktitle = {Proceedings der dritten transdisziplin\"{a}ren Konferenz \dqTechnische Unterst\"{u}tzungssysteme, die die Menschen wirklich wollen\dq (engl: Proceedings of the 3rd \dqTransdisciplinary Conference on Support Technologies\dq), TCST 2018}, pages = {89--98}, tags = {SFB-TRR-62,Planning,SFB-T3}, file_url = {http://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2018/Leichtmann2018HumanPlanningBehavior.pdf}, note = {This paper won the Best Paper Award.} } @Article { leichtmann2018towards, author = {Leichtmann, Benedikt and Bercher, Pascal and H\"{o}ller, Daniel and Behnke, Gregor and Biundo, Susanne and Nitsch, V and Baumann, Martin}, title = {Towards a Companion System Incorporating Human Planning Behavior}, year = {2018}, journal = {Technische Unterst\"{u}tzungssysteme, die die Menschen wirklich wollen}, pages = {89} } @Inproceedings { Behnke2018TreeSAT, author = {Behnke, Gregor and H\"{o}ller, Daniel and Biundo, Susanne}, title = {Tracking Branches in Trees - A Propositional Encoding for Solving Partially-Ordered HTN Planning Problems}, abstract = {Planning via SAT has proven to be an efficient and versatile planning technique. Its declarative nature allows for an easy integration of additional constraints and can harness the progress made in the SAT community without the need to adapt the planner. However, there has been only little attention to SAT planning for hierarchical domains. To ease encoding, existing approaches for HTN planning require additional assumptions, like non-recursiveness or totally-ordered methods. Both limit the expressiveness of HTN planning severely. We propose the first propositional encodings which are able to solve general, i.e., partially-ordered, HTN planning problems, based on a previous encoding for totally-ordered problems. The empirical evaluation of our encoding shows that it outperforms existing HTN planners significantly.}, year = {2018}, booktitle = {Proceedings of the First ICAPS Workshop on Hierarchical Planning}, pages = {40--47}, tags = {SFB-TRR-62,SFB-T3}, web_url = {http://icaps18.icaps-conference.org/hierarchicalplanning/}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2018/Behnke2018partSAT.pdf} } @Proceedings { HierarchicalPlanningWorkshop2018, author = {Bercher, Pascal and H\"{o}ller, Daniel and Biundo, Susanne and Alford, Ron}, title = {Proceedings of the 1st ICAPS Workshop on Hierarchical Planning}, abstract = {The motivation for using hierarchical planning formalisms is manifold. It ranges from an explicit and predefined guidance of the plan generation process and the ability to represent complex problem solving and behavior patterns to the option of having different abstraction layers when communicating with a human user or when planning cooperatively. This led to a large set of different hierarchical formalisms and systems. With this workshop, we want to bring together scientists working on any aspect related to hierarchical planning to exchange ideas and foster cooperation. Hierarchies induce fundamental differences from classical, non-hierarchical planning, creating distinct computational properties and requiring separate algorithms for plan generation, plan verification, plan repair, and practical applications. Many of these aspects of hierarchical planning are still unexplored. This wide range of important yet insufficiently solved problems is reflected in the topics presented in this proceedings. Though the main focus lies on the development of planning systems, these tackle quite different classes of hierarchical problems and use several solving techniques. It includes work on real-time planning, planning with task insertion, distributed planning, and extensions of formalisms to enable real-world application. Beside solvers, the presented work includes techniques for the plan repair problem and discussions of the application in real-world problems.}, year = {2018}, editor = {Pascal Bercher and Daniel H\"{o}ller and Susanne Biundo and Ron Alford}, tags = {Planning}, web_url = {http://icaps18.icaps-conference.org/hierarchicalplanning/}, file_url = {http://icaps18.icaps-conference.org/fileadmin/alg/conferences/icaps18/workshops/workshop08/docs/HierarchicalPlanningProceedings.pdf} } @Inproceedings { Hoeller2018PlanRecPAIR, author = {H\"{o}ller, Daniel and Bercher, Pascal and Behnke, Gregor and Biundo, Susanne}, title = {Plan and Goal Recognition as HTN Planning}, abstract = {Plan- and Goal Recognition (PGR) is the task of inferring the goals and plans of an agent based on its actions. A few years ago, an approach has been introduced that successfully exploits the performance of planning systems to solve it. That way, no specialized solvers are needed and PGR benefits from present and future research in planning. The approach uses classical planning systems and needs to plan (at least) once for every possible goal. However, models in PGR are often structured in a hierarchical way, similar to Hierarchical Task Networks (HTNs). These models are strictly more expressive than those in classical planning and can describe partially ordered sets of tasks or multiple goals with interleaving plans. We present the approach PGR as HTN Planning that enables the recognition of complex agent behavior by using unmodified, off-the-shelf HTN planners. Planning is thereby needed only once, regardless of how many possible goals there are. Our evaluation shows that current planning systems are able to handle large models with thousands of possible goals and that the approach results in high recognition rates.}, year = {2018}, booktitle = {Proceedings of the AAAI 2018 Workshop on Plan, Activity, and Intent Recognition (PAIR 2018)}, pages = {607--613}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.planrec.org/PAIR/PAIR18/Resources.html}, file_url = {http://www.planrec.org/PAIR/PAIR18/Papers/HollerPair18.pdf} } @Inproceedings { Hoeller18Repair, author = {H\"{o}ller, Daniel and Bercher, Pascal and Behnke, Gregor and Biundo, Susanne}, title = {HTN Plan Repair Using Unmodified Planning Systems}, 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. }, year = {2018}, booktitle = {Proceedings of the First ICAPS Workshop on Hierarchical Planning}, pages = {26--30}, tags = {SFB-TRR-62,SFB-T3,Planning}, web_url = {http://icaps18.icaps-conference.org/hierarchicalplanning/}, file_url = {www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2018/Hoeller18Repair.pdf} } @Inproceedings { Hoeller18Progression, author = {H\"{o}ller, Daniel and Bercher, Pascal and Behnke, Gregor and Biundo, Susanne}, title = {A Generic Method to Guide HTN Progression Search with Classical Heuristics}, 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.}, year = {2018}, booktitle = {Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS 2018)}, publisher = {AAAI Press}, pages = {114--122}, tags = {SFB-TRR-62,Planning,SFB-T3}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2018/Hoeller18Progression.pdf}, note = {This paper has won the ICAPS Best Student Paper Award} } @Techreport { Bercher2018AssemblyAssistant, author = {Bercher, Pascal and Richter, Felix and Honold, Frank and Nielsen, Florian and Sch\"{u}ssel, Felix and Geier, Thomas and H\"{o}rnle, Thilo and Reuter, Stephan and H\"{o}ller, Daniel and Behnke, Gregor and Weber, Michael and Dietmayer, Klaus and Minker, Wolfgang and Biundo, Susanne}, title = {A Companion-System Architecture for Realizing Individualized and Situation-Adaptive User Assistance}, abstract = {We show how techniques from various research areas --most notably hierarchical planning, dialog management, and interactionmanagement -- can be employed to realize individualized andsituation-adaptive user assistance. We introduce a modular systemarchitecture that is composed of domain-independent componentsimplementing techniques from the respective areas. Systems based on thisarchitecture -- so-called Companion-Systems -- can provideintelligent assistance in a broad variety of tasks. They provide a user-and situation-adapted sequence of instructions that show how achieve therespective task. Additional explanations are, like the instructionsthemselves, automatically derived based on a declarative model of thecurrent task. These systems can react to unforeseen execution failuresrepairing their underlying plans if required. We introduce a prototypesystem that assists with setting up a home theater and use it as arunning example as well as for an empirical evaluation with testsubjects that shows the usefulness of our approach. We summarize thework of more than half a decade of research and development done byvarious research groups from different disciplines. Here, for the firsttime, we explain the full integration of all components thereby showing``the complete picture\\" of our approach to provide individualized andsituation-adaptive user assistance.}, type = {technical report}, year = {2018}, DOI = {10.18725/OPARU-11023}, institution = {Ulm University}, keywords = {planning}, tags = {SFB-TRR-62}, file_url = {https://oparu.uni-ulm.de/xmlui/bitstream/handle/123456789/11080/AssemblyAssistant.pdf} } @Inproceedings { Hoeller2018PlanRec, author = {H\"{o}ller, Daniel and Behnke, Gregor and Bercher, Pascal and Biundo, Susanne}, title = {Plan and Goal Recognition as HTN Planning}, 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.}, year = {2018}, booktitle = {Proceedings of the 30th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2018)}, publisher = {IEEE Computer Society}, pages = {466--473}, tags = {Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2018/Hoeller2018PlanRec.pdf} } @Inbook { Bercher2017CompBookHomeTheater, author = {Bercher, Pascal and Richter, Felix and H\"{o}rnle, Thilo and Geier, Thomas and H\"{o}ller, Daniel and Behnke, Gregor and Nielsen, Florian and Honold, Frank and Sch\"{u}ssel, Felix and Reuter, Stephan and Minker, Wolfgang and Weber, Michael and Dietmayer, Klaus and Biundo, Susanne}, title = {Advanced User Assistance for Setting Up a Home Theater}, abstract = {In many situations of daily life, such as in educational, work-related, or social contexts, one can observe an increasing demand for intelligent assistance systems. In this chapter, we show how such assistance can be provided in a wide range of application scenarios--based on the integration of user-centered planning with advanced dialog and interaction management capabilities. Our approach is demonstrated by a system that assists a user in the task of setting up a complex home theater. The theater consists of several hi-fi devices that need to be connected with each other using the available cables and adapters. In particular for technically inexperienced users, the task is quite challenging due to the high number of different ports of the devices and because the used cables might not be known to the user. Support is provided by presenting a detailed sequence of instructions that solves the task.}, year = {2017}, DOI = {10.1007/978-3-319-43665-4\_24}, booktitle = {Companion Technology -- A Paradigm Shift in Human-Technology Interaction}, publisher = {Springer}, chapter = {24}, series = {Cognitive Technologies}, editor = {Susanne Biundo and Andreas Wendemuth}, pages = {485--491}, tags = {SFB-TRR-62}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2017/Bercher2017CompBookHomeTheater.pdf} } @Inproceedings { Bercher17AdmissibleHTNHeuristic, author = {Bercher, Pascal and Behnke, Gregor and H\"{o}ller, Daniel and Biundo, Susanne}, title = {An Admissible HTN Planning Heuristic}, abstract = {Hierarchical task network (HTN) planning is well-known for being an efficient planning approach. This is mainly due to the success of the HTN planning system SHOP2. However, its performance depends on hand-designed search control knowledge. At the time being, there are only very few domain-independent heuristics, which are designed for differing hierarchical planning formalisms. Here, we propose an admissible heuristic for standard HTN planning, which allows to find optimal solutions heuristically. It bases upon the so-called task decomposition graph (TDG), a data structure reflecting reachable parts of the task hierarchy. We show (both in theory and empirically) that rebuilding it during planning can improve heuristic accuracy thereby decreasing the explored search space. The evaluation further studies the heuristic both in terms of plan quality and coverage.}, year = {2017}, booktitle = {Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI 2017)}, publisher = {IJCAI}, pages = {480--488}, tags = {SFB-TRR-62,Planning,SFB-T3}, web_url = {http://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2017/Bercher17AdmissibleHTNHeuristicTalk.pdf}, web_url2 = {http://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2017/Bercher17AdmissibleHTNHeuristicPoster.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2017/Bercher17AdmissibleHTNHeuristic.pdf} } @Inproceedings { Behnke2017Challenge, author = {Behnke, Gregor and Leichtmann, Benedikt and Bercher, Pascal and H\"{o}ller, Daniel and Nitsch, Verena and Baumann, Martin and Biundo, Susanne}, title = {Help me make a dinner! Challenges when assisting humans in action planning}, abstract = {A promising field of application for cognitive technical systems is individualised user assistance for complex tasks. Here, a companion system usually uses an AI planner to solve the underlying combinatorial problem. Often, the use of a bare black-box planning system is not sufficient to provide individualised assistance, but instead the user has to be able to control the process that generates the presented advice. Such an integration guarantees that the user will be satisfied with the assistance s/he is given, trust the advice more, and is thus more likely to follow it. In this paper, we provide a general theoretical view on this process, called mixed-initiative planning, and derive several research challenges from it.}, year = {2017}, booktitle = {Proceedings of the 2nd International Conference on Companion Technology (ICCT 2017)}, publisher = {IEEE}, tags = {SFB-TRR-62,Planning}, file_url = {http://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2017/Behnke2017Challenge.pdf} } @Inproceedings { behnke2017help, author = {Behnke, Gregor and Leichtmann, Benedikt and Bercher, Pascal and H\"{o}ller, Daniel and Nitsch, Verena and Baumann, Martin and Biundo, Susanne}, title = {Help me make a dinner! Challenges when assisting humans in action planning}, year = {2017}, organization = {IEEE}, booktitle = {2017 international conference on companion technology (ICCT)}, pages = {1--6} } @Inproceedings { Behnke17Verify, author = {Behnke, Gregor and H\"{o}ller, Daniel and Biundo, Susanne}, title = {This is a solution! (... but is it though?) - Verifying solutions of hierarchical planning problems}, abstract = {Plan-Verification is the task of determining whether a plan is a solution to a given planning problem. Any plan verifier has, apart from showing that verifying plans is possible in practice, a wide range of possible applications. These include mixed-initiative planning, where a user is integrated into the planning process, and local search, e.g., for post-optimising plans or for plan repair. In addition to its practical interest, plan verification is also a problem worth investigating for theoretical reasons. Recent work showed plan verification for hierarchical planning problems to be NP-complete, as opposed to classical planning where it is in P. As such, plan verification for hierarchical planning problem was – until now – not possible. We describe the first plan verifier for hierarchical planning. It uses a translation of the problem into a SAT formula. Further we conduct an empirical evaluation, showing that the correct output is produced within acceptable time.}, year = {2017}, booktitle = {Proceedings of the 27th International Conference on Automated Planning and Scheduling (ICAPS 2017)}, publisher = {AAAI Press}, pages = {20--28}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2017/Behnke17Verify\_Talk.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2017/Behnke17Verify.pdf} } @Inbook { Bercher2017CompBookUCPlanning, author = {Bercher, Pascal and H\"{o}ller, Daniel and Behnke, Gregor and Biundo, Susanne}, title = {User-Centered Planning}, abstract = {User-centered planning capabilities are core elements of Companion-Technology. They are used to implement the functional behavior of technical systems in a way that makes those systems Companion-able – able to serve users individually, to respect their actual requirements and needs, and to flexibly adapt to changes of the user’s situation and environment. This book chapter presents various techniques we have developed and integrated to realize user-centered planning. They are based on a hybrid planning approach that combines key principles also humans rely on when making plans: stepwise refining complex tasks into executable courses of action and considering causal relationships between actions. Since the generated plans impose only a partial order on actions, they allow for a highly flexible execution order as well. Planning for Companion-Systems may serve different purposes, depending on the application for which the system is created. Sometimes, plans are just like control programs and executed automatically in order to elicit the desired system behavior; but sometimes they are made for humans. In the latter case, plans have to be adequately presented and the definite execution order of actions has to coincide with the user’s requirements and expectations. Furthermore, the system should be able to smoothly cope with execution errors. To this end, the plan generation capabilities are complemented by mechanisms for plan presentation, execution monitoring, and plan repair.}, year = {2017}, DOI = {10.1007/978-3-319-43665-4\_5}, booktitle = {Companion Technology -- A Paradigm Shift in Human-Technology Interaction}, publisher = {Springer}, chapter = {5}, series = {Cognitive Technologies}, editor = {Susanne Biundo and Andreas Wendemuth}, pages = {79--100}, tags = {SFR-TRR-62,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2017/Bercher2017CompBookUCPlanning.pdf} } @Article { Smith2016Interview, author = {Bercher, Pascal and H\"{o}ller, Daniel}, title = {Interview with David E. Smith}, abstract = {David E. Smith is a senior Researcher in the Intelligent Systems Division at NASA Ames Research Center. He received his Ph.D. in 1985 from Stanford University, and spent time as a Research Associate at Stanford, a Scientist at the Rockwell Palo Alto Science Center, and a Visiting Scholar at the University of Washington before joining NASA in 1997. Beginning in 1999, he served as the lead of the 18 member planning and scheduling group at NASA Ames for six years before abdicating to devote more time to research. Much of his research has focused on pushing the boundaries of AI planning technology to handle richer models of time, concurrency, exogenous events, uncertainty, and oversubscription. Smith served as an Associate Editor for the Journal of Artificial Intelligence Research (JAIR) from 2001-2004, and as Guest Editor for the JAIR Special Issue and Special Track on the 3rd and 4th International Planning Competitions. He served on the JAIR Advisory Board 2004-2007. Smith was recognized as a AAAI Fellow in 2005, and served on the AAAI Executive Council 2007-2010.}, year = {2016}, DOI = {10.1007/s13218-015-0403-y}, journal = {K\"{u}nstliche Intelligenz}, volume = {30}, publisher = {Springer}, pages = {101--105}, number = {1}, tags = {SFB-TRR-62,Planning}, web_url = {http://link.springer.com/article/10.1007/s13218-015-0403-y}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2016/Smith2016Interview.pdf}, note = {Special Issue on Companion Technologies} } @Article { Biundo2016Editorial, author = {Biundo, Susanne and H\"{o}ller, Daniel and Bercher, Pascal}, title = {Special Issue on Companion Technologies}, abstract = {Dear reader, at present, we observe a rapid growth in the development of increasingly complex “intelligent” systems that serve users throughout all areas of their daily lives. They range from classical technical systems such as household appliances, cars, or consumer electronics through mobile apps and services to advanced service robots in various fields of application. While many of the rather conventional systems already provide multiple modalities to interact with, the most advanced are even equipped with cognitive abilities such as perception, cognition, and reasoning. However, the use of such complex technical systems and in particular the actual exploitation of their rich functionality remain challenging and quite often lead to users’ cognitive overload and frustration. Companion Technologies bridge the gap between the extensive functionality of technical systems and human users’ individual requirements and needs. They enable the construction of really smart – adaptive, flexible, and cooperative – technical systems by applying and fusing techniques from different areas of research. In our special issue we present interesting pieces of work – quite a number of new technical contributions, ongoing and completed research projects, several dissertation abstracts, as well as an interview – that are related to, or even fundamental for, Companion-Technology. In the community part of this issue, there is also a conference report on the first International Symposium on Companion-Technology.}, year = {2016}, DOI = {10.1007/s13218-015-0421-9}, journal = {K\"{u}nstliche Intelligenz}, volume = {30}, publisher = {Springer}, pages = {5-9}, number = {1}, tags = {SFB-TRR-62,Planning}, web_url = {http://link.springer.com/article/10.1007/s13218-015-0421-9}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2016/Biundo2016Editorial.pdf}, note = {Special Issue on Companion Technologies} } @Inproceedings { Bercher16HybridPlanningComplexities, author = {Bercher, Pascal and H\"{o}ller, Daniel and Behnke, Gregor and Biundo, Susanne}, title = {More than a Name? On Implications of Preconditions and Effects of Compound HTN Planning Tasks}, abstract = {There are several formalizations for hierarchical planning. Many of them allow to specify preconditions and effects for compound tasks. They can be used, e.g., to assist during the modeling process by ensuring that the decomposition methods' plans ``implement'' the compound tasks' intended meaning. This is done based on so-called legality criteria that relate these preconditions and effects to the method's plans and pose further restrictions. Despite the variety of expressive hierarchical planning formalisms, most theoretical investigations are only known for standard HTN planning, where compound tasks are just names, i.e., no preconditions or effects can be specified. Thus, up to know, a direct comparison to other hierarchical planning formalisms is hardly possible and fundamental theoretical properties are yet unknown. We therefore investigate the theoretical impact of such preconditions and effects -- depending on the legality criteria known from the literature -- for two of the most basic questions to planning: plan existence and plan verification. It turns out that for all investigated legality criteria, the respective problems are as hard as in the HTN setting and therefore equally expressive.}, year = {2016}, booktitle = {Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016)}, publisher = {IOS Press}, pages = {225--233}, tags = {SFB-TRR-62,Planning}, web_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2016/Bercher16HybridPlanningComplexitiesSlides.pdf}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2016/Bercher16HybridPlanningComplexities.pdf} } @Inproceedings { Hoeller16Expressivity, author = {H\"{o}ller, Daniel and Behnke, Gregor and Bercher, Pascal and Biundo, Susanne}, title = {Assessing the Expressivity of Planning Formalisms through the Comparison to Formal Languages}, abstract = {From a theoretical perspective, judging the expressivity of planning formalisms helps to understand the relationship of different representations and to infer theoretical properties. From a practical point of view, it is important to be able to choose the best formalism for a problem at hand, or to ponder the consequences of introducing new representation features. Most work on the expressivity is based either on compilation approaches, or on the computational complexity of the plan existence problem. Recently, we introduced a new notion of expressivity. It is based on comparing the structural complexity of the set of solutions to a planning problem by interpreting the set as a formal language and classifying it with respect to the Chomsky hierarchy. This is a more direct measure than the plan existence problem and enables also the comparison of formalisms that can not be compiled into each other. While existing work on that last approach focused on different hierarchical problem classes, this paper investigates STRIPS with and without conditional effects; though we also tighten some existing results on hierarchical formalisms. Our second contribution is a discussion on the language-based expressivity measure with respect to the other approaches.}, year = {2016}, booktitle = {Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016)}, publisher = {AAAI Press}, pages = {158--165}, event_name = {26th International Conference on Automated Planning and Scheduling}, event_place = {London}, tags = {SFB-TRR-62,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2016/Hoeller16Expressivity.pdf} } @Article { Biundo2016CompanionSurvey, author = {Biundo, Susanne and H\"{o}ller, Daniel and Schattenberg, Bernd and Bercher, Pascal}, title = {Companion-Technology: An Overview}, abstract = {Companion-technology is an emerging field of cross-disciplinary research. It aims at developing technical systems that appear as \dqCompanions'' to their users. They serve as co-operative agents assisting in particular tasks or, in a more general sense, even give companionship to humans. Overall, Companion-technology enables technical systems to smartly adapt their services to individual users' current needs, their requests, situation, and emotion. We give an introduction to the field, discuss the most relevant application areas that will benefit from its developments, and review the related research projects.}, year = {2016}, DOI = {10.1007/s13218-015-0419-3}, journal = {K\"{u}nstliche Intelligenz}, volume = {30}, publisher = {Springer}, pages = {11-20}, number = {1}, tags = {SFB-TRR-62,Planning}, web_url = {http://link.springer.com/article/10.1007/s13218-015-0419-3}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2016/Biundo2016CompanionSurvey.pdf}, note = {Special Issue on Companion Technologies} } @Inproceedings { Behnke16ChangeThePlan, author = {Behnke, Gregor and H\"{o}ller, Daniel and Bercher, Pascal and Biundo, Susanne}, title = {Change the Plan - How hard can that be?}, abstract = {Interaction with users is a key capability of planning systems that are applied in real-world settings. Such a system has to be able to react appropriately to requests issued by its users. Most of these systems are based on a generated plan that is continually criticised by him, resulting in a mixed-initiative planning system. We present several practically relevant requests to change a plan in the setting of hierarchical task network planning and investigate their computational complexity. On the one hand, these results provide guidelines when constructing algorithms to execute the respective requests, but also provide translations to other well-known planning queries like plan existence or verification. These can be employed to extend an existing planner such that it can form the foundation of a mixed-initiative planning system simply by adding a translation layer on top.}, year = {2016}, booktitle = {Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016)}, publisher = {AAAI Press}, pages = {38--46}, event_name = {26th International Conference on Automated Planning and Scheduling}, event_place = {London}, tags = {SFB-TRR-62,Planning}, web_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2016/Behnke16Change\_Talk.pdf}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2016/Behnke16ChangeThePlan.pdf} } @Inproceedings { Alford16BoundToPlan, author = {Alford, Ron and Behnke, Gregor and H\"{o}ller, Daniel and Bercher, Pascal and Biundo, Susanne and Aha, David}, title = {Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems}, abstract = {Hierarchical Task Network (HTN) planning is a formalism that can express constraints which cannot easily be expressed by classical (non-hierarchical) planning approaches. It enables reasoning about procedural structures and domain-specific search control knowledge. Yet the cornucopia of modern heuristic search techniques remains largely unincorporated in current HTN planners, in part because it is not clear how to estimate the goal distance for a partially-ordered task network. When using SHOP2-style progression, a task network of yet unprocessed tasks is maintained during search. In the general case it can grow arbitrarily large. However, many – if not most – existing HTN domains have a certain structure (called tail-recursive) where the network’s size is bounded. We show how this bound can be calculated and exploited to automatically translate tail-recursive HTN problems into non-hierarchical STRIPS representations, which allows using both hierarchical structures and classical planning heuristics. In principle, the approach can also be applied to non-tail-recursive HTNs by incrementally increasing the bound. We give three translations with different advantages and present the results of an empirical evaluation with several HTN domains that are translated to PDDL and solved by two current classical planning systems. Our results show that we can automatically find practical bounds for solving partially-ordered HTN problems. We also show that classical planners perform similarly with our automatic translations versus a previous hand-bounded HTN translation which is restricted to totally-ordered problems.}, year = {2016}, booktitle = {Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016)}, publisher = {AAAI Press}, pages = {20--28}, event_name = {26th International Conference on Automated Planning and Scheduling}, event_place = {London}, tags = {SFB-TRR-62,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2016/Alford16BoundToPlan.pdf} } @Inproceedings { Bercher2015DemoSystem, author = {Bercher, Pascal and Richter, Felix and H\"{o}rnle, Thilo and Geier, Thomas and H\"{o}ller, Daniel and Behnke, Gregor and Nothdurft, Florian and Honold, Frank and Minker, Wolfgang and Weber, Michael and Biundo, Susanne}, title = {A Planning-based Assistance System for Setting Up a Home Theater}, abstract = {Modern technical devices are often too complex for many users to be able to use them to their full extent. Based on planning technology, we are able to provide advanced user assistance for operating technical devices. We present a system that assists a human user in setting up a complex home theater consisting of several HiFi devices. For a human user, the task is rather challenging due to a large number of different ports of the devices and the variety of available cables. The system supports the user by giving detailed instructions how to assemble the theater. Its performance is based on advanced user-centered planning capabilities including the generation, repair, and explanation of plans.}, year = {2015}, booktitle = {Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015)}, publisher = {AAAI Press}, pages = {4264--4265}, tags = {SFB-TRR-62,Planning}, file_url = {http://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2015/Bercher15DemoSystem.pdf} } @Inproceedings { Behnke2015Verification, author = {Behnke, Gregor and H\"{o}ller, Daniel and Biundo, Susanne}, title = {On the Complexity of HTN Plan Verification and its Implications for Plan Recognition}, abstract = {In classical planning it is easy to verify if a given sequence of actions is a solution to a planning problem. It has to be checked whether the actions are applicable in the given order and if a goal state is reached after executing them. In this paper we show that verifying whether a plan is a solution to an HTN planning problem is much harder. More specifically, we prove that this problem is NP-complete, even for very simple HTN planning problems. Furthermore, this problem remains NP-complete if an executable sequence of tasks is already provided. HTN-like hierarchical structures are commonly used to represent plan libraries in plan and goal recognition. By applying our result to plan and goal recognition we provide insight into its complexity.}, year = {2015}, booktitle = {Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS 2015)}, publisher = {AAAI Press}, editor = {Ronen Brafman, Carmel Domshlak, Patrik Haslum, Shlomo Zilberstein}, pages = {25-33}, event_name = {25th International Conference on Automated Planning and Scheduling}, event_place = {Jerusalem}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2015/Behnke15Verify\_Talk.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2015/Behnke2015HTNVerification.pdf} } @Inproceedings { Bercher15UserCenteredDiscussion, author = {Bercher, Pascal and H\"{o}ller, Daniel and Behnke, Gregor and Biundo, Susanne}, title = {User-Centered Planning - A Discussion on Planning in the Presence of Human Users}, abstract = {AI planning forms a core capability of intelligent systems. It enables goal directed behavior and allows systems to react adequately and flexibly to the current situation. Further, it allows systems to provide advice to a human user on how to reach his or her goals. Though the process of finding a plan is, by itself, a hard computational problem, some new challenges arise when involving a human user into the process. Plans have to be generated in a certain way, so that the user can be included into the plan generation process in case he or she wishes to; the plans should be presented to the user in an adequate way to prevent confusion or even rejection; to improve the trust in the system, it needs to be able to explain its behavior or presented plans. Here, we discuss these challenges and give pointers on how to solve them.}, year = {2015}, booktitle = {Proceedings of the First International Symposium on Companion Technology (ISCT 2015)}, pages = {79--82}, event_name = {First International Symposium on Companion Technology (ISCT 2015)}, event_place = {Ulm, Germany}, tags = {SFB-TRR-62,Planning}, web_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2015/Bercher15ISCTPoster.pdf}, file_url = {https://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2015/Bercher15UserCenteredDiscussion.pdf} } @Inproceedings { Hoeller14PlanLinearization, author = {H\"{o}ller, Daniel and Bercher, Pascal and Richter, Felix and Schiller, Marvin R. G. and Geier, Thomas and Biundo, Susanne}, title = {Finding User-friendly Linearizations of Partially Ordered Plans}, 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.}, year = {2014}, booktitle = {28th PuK Workshop \dqPlanen, Scheduling und Konfigurieren, Entwerfen\dq (PuK 2014)}, keywords = {Hybrid Planning, POCL Planning, HTN Planning, Plan Linearization, User-centered Planning, User Assistance, Plan Execution}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2014/Hoeller14PlanLinearizationSlides.pdf}, web_url2 = {http://www.puk-workshop.de/puk2014/prog.html}, file_url = {http://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2014/Hoeller14PlanLinearization.pdf} } @Inproceedings { Hoeller2014HTNLanguage, author = {H\"{o}ller, Daniel and Behnke, Gregor and Bercher, Pascal and Biundo, Susanne}, title = {Language Classification of Hierarchical Planning Problems}, abstract = {Theoretical results on HTN planning are mostly related to the plan existence problem. In this paper, we study the structure of the generated plans in terms of the language they produce. We show that such languages are always context-sensitive. Furthermore we identify certain subclasses of HTN planning problems which generate either regular or context-free languages. Most importantly we have discovered that HTN planning problems, where preconditions and effects are omitted, constitute a new class of languages that lies strictly between the context-free and context-sensitive languages.}, year = {2014}, DOI = {10.3233/978-1-61499-419-0-447}, booktitle = {Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014)}, volume = {263}, publisher = {IOS Press}, address = {Amsterdam}, series = {Frontiers in Artificial Intelligence and Applications}, editor = {Schaub, Torsten and Friedrich, Gerhard and O'Sullivan, Barry}, pages = {447-452}, event_name = {21st European Conference on Artificial Intelligence (ECAI 2014)}, event_place = {Prague, Czech Republic}, tags = {SFB-TRR-62,Planning}, file_url = {http://www.uni-ulm.de/fileadmin/website\_uni\_ulm/iui.inst.090/Publikationen/2014/Hoeller2014HtnLanguages.pdf} } @Inproceedings { Hoeller2011PuK, author = {H\"{o}ller, Daniel and Mies, Christoph}, title = {Integration of a PDDL Planning Framework into the Multi-Agent Simulation System LAMPSys}, abstract = {LAMPSys is a general purpose multi-agent simulation platform that has successfully been used to simulate real-world domains during the last years. A hierarchical agent organization encapsulates decision making by planning centrally for a group of agents. This work introduces a specification framework for the generation of PDDL planning instances from a leader agent's world model. The modeling of the generation process simplifies the integration of different planning domains into LAMPSys, since general operators and specifications can be reused. Another contribution is a plan post-processing that supports plan monitoring. The temporal synchronization of actions in PDDL plans with absolute points in time is extended by a qualitative synchronization with a partial order of actions. In some situations, this approach improves the parallelism of a plan significantly. Finally, the application of PDDL planning to the real-world domain of medical evacuation is evaluated.}, year = {2011}, booktitle = {26th PuK Workshop \dqPlanen, Scheduling und Konfigurieren, Entwerfen\dq (PuK 2011)}, tags = {Planning}, web_url = {http://www.puk-workshop.de/puk2011/prog.html}, file_url = {http://www.puk-workshop.de/puk2011/paper/PuK2011HoellerMies.pdf} }