### Prof. Dr. Susanne Biundo-Stephan

Director of the Institute
Ulm University
Institute of Artificial Intelligence
James-Franck-Ring
89081 Ulm
Baden-Württemberg
Germany
Room: O27 - 450

# Prof. Dr. Susanne Biundo-Stephan

Susanne Biundo received her Ph.D. (Dr. rer. nat.) from the University of Karlsruhe in 1989. She held a Senior Research Position at the Intelligent User Interfaces Lab of the German Research Center for Artificial Intelligence (DFKI) from 1989 to 1998. Since 1998, she is a Professor of Computer Science at Ulm University.

Susanne Biundo is the chair of the Transregional Collaborative Research Centre SFB/TRR 62 "Companion-Technology for Cognitive Technical Systems".

Among other professional activities, she served as the Conference- and Program Co-chair of ICAPS 2005, the "15th International Conference on Automated Planning and Scheduling", as the Conference- and Program Co-chair of the "27th German Conference on Artificial Intelligence" (KI 2004), and as the Program Chair of the "5th European Conference on Planning" (ECP-99).

Susanne Biundo was the initiator and coordinator of PLANET, the "European Network of Excellence in AI Planning", which she led from 1998 to 2003.

In 2004, she was elected ECCAI Fellow.

## Further Information

AI Planning, Automated Reasoning, Knowledge Modeling, Cognitive Systems

Susanne Biundo was a Founding Member of the Executive Council of ICAPS, the International Conference on Automated Planning and Scheduling (2002 -2008) and a member of the board of the German Informatics Society (GI) (2002 - 2007).

She acted as Conference- and Program Co-chair of the "15th International Conference on Automated Planning and Scheduling" (ICAPS 2005), as the Conference- and Program Co-chair of the "27th German Conference on Artificial Intelligence" (KI 2004), as Associated Program Chair of the "6th International Conference on AI Planning and Scheduling" (AIPS-02), and as the Program Chair of the "5th European Conference on Planning" (ECP-99).

She initiated and chaired the "European Network of Excellence in AI Planning" (PLANET).

Susanne Biundo was the Area Editor of "Planning and Scheduling" of the Electronic Transactions on Artificial Intelligence (ETAI) and served on the editorial and review boards of various scientific journals including Applied Intelligence, JAIR, and the Journal of Applied Logic.
Furthermore, she was a program committee member of numerous international conferences including ICAPS 2004, ICAPS 2003, ECAI 2002, ECAI 2000, KR 2000, IJCAI-99, and IJCAI-97.

see teaching offer of the current semester

## Publications

% % This file was created by the TYPO3 extension % publications % --- Timezone: CEST % Creation date: 2022-11-27 % Creation time: 00:00:35 % --- Number of references % 109 % @Article { Bercher2021DIY, author = {Bercher, Pascal and Behnke, Gregor and Kraus, Matthias and Schiller, Marvin R. G. and Manstetten, Dietrich and Dambier, Michael and Dorna, Michael and Minker, Wolfgang and Glimm, Birte and Biundo, Susanne}, title = {Do It Yourself, but Not Alone: Companion-Technology for Home Improvement {\\&}ndash; Bringing a Planning-Based Interactive DIY Assistant to Life}, abstract = {We report on the technology transfer project “Do it yourself, but not alone: Companion-Technology for Home Improvement” that was carried out by Ulm University in cooperation with Robert Bosch GmbH. We developed a prototypical assistance system that assists a Do It Yourself (DIY) handyman in carrying out DIY projects. The assistant, based on various AI and dialog management capabilities, generates a sequence of detailed instructions that users may just follow or adapt according to their individual preferences. It features explanation capabilities as well as pro-active support based on communication with the user as well as with the involved tools. We report on the project’s main achievements, including the findings of various empirical studies conducted in various development stages of the prototype.}, year = {2021}, journal = {K{\"u}nstliche Intelligenz {\\&}ndash; Special Issue on NLP and Semantics}, web_url2 = {https://rdcu.be/cmGwb}, file_url = {http://link.springer.com/article/10.1007/s13218-021-00721-x} } @Inproceedings { Olz21RevealingEffects, author = {Olz, Conny and Biundo, Susanne and Bercher, Pascal}, title = {Revealing Hidden Preconditions and Effects of Compound HTN Planning Tasks {\\&}ndash; A Complexity Analysis}, year = {2021}, booktitle = {Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021)}, publisher = {AAAI Press}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2021/Olz21CompoundEffects.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} } @Article { 708520658245_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 { Behnke2020DIYAssistant, author = {Behnke, Gregor and Bercher, Pascal and Kraus, Matthias and Schiller, Marvin R. G. and Mickeleit, Kristof and H{\"a}ge, Timo and Dorna, Michael and Dambier, Michael and Minker, Wolfgang and Glimm, Birte and Biundo, Susanne}, title = {New Developments for Robert {\\&}ndash; Assisting Novice Users Even Better in DIY Projects}, year = {2020}, booktitle = {Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS 2020)}, publisher = {AAAI Press}, pages = {343--347}, keywords = {SFB-T3,Planning}, tags = {SFB-T3,Planning,KnowledgeModelling}, web_url = {https://aaai.org/ojs/index.php/ICAPS/article/view/6679/6533 - - {\dq}Link to the AAAI Paper Version{\dq}}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2020/Behnke2020DIYAssistant.pdf} } @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 { Kraus2020ICMI, author = {Kraus, Matthias and Schiller, Marvin R. G. and Behnke, Gregor and Bercher, Pascal and Dorna, Michael and Dambier, Michael and Glimm, Birte and Biundo, Susanne and Minker, Wolfgang}, title = {Was that successful? On Integrating Proactive Meta-Dialogue in a DIY-Assistant System using Multimodal Cues}, abstract = {Effectively supporting novices during performance of complex tasks, e.g. do-it-yourself (DIY) projects, requires intelligent assistants to be more than mere instructors. In order to be accepted as a competent and trustworthy cooperation partner, they need to be able to actively participate in the project and engage in helpful conversations with users when assistance is necessary. Therefore, a new proactive version of the DIY-assistant \textsc{Robert} is presented in this paper. It extends the previous prototype by including the capability to initiate reflective meta-dialogues using multimodal cues. Two different strategies for reflective dialogue are implemented: A progress-based strategy initiates a reflective dialogue about previous experience with the assistance for encouraging the self-appraisal of the user. An activity-based strategy is applied for providing timely, task-dependent support. Therefore, user activities with a connected drill driver are tracked that trigger dialogues in order to reflect on the current task and to prevent task failure. An experimental study comparing the proactive assistant against the baseline version shows that proactive meta-dialogue is able to build user trust significantly better than a solely reactive system. Besides, the results provide interesting insights for the development of proactive dialogue assistants.}, year = {2020}, booktitle = {Proceedings of 22nd ACM International Conference on Multimodal Interaction (ICMI 2020)}, publisher = {ACM}, tags = {SFB-T3}, web_url = {https://dl.acm.org/doi/pdf/10.1145/3382507.3418818 - - {\dq}Link to the Conference Paper{\dq}}, file_url = {t3://file?uid=431053} } @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} } @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 { 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 { 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 { 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 {\\&}ndash; much more important {\\&}ndash; 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 { 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 { 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} } @Article { Behnke2019bosch, author = {Behnke, Gregor and Schiller, Marvin R. G. and Kraus, Matthias and Bercher, Pascal and Schmautz, Mario and Dorna, Michael and Dambier, Michael and Minker, Wolfgang and Glimm, Birte and Biundo, Susanne}, title = {Alice in DIY wonderland or: Instructing novice users on how to use tools in DIY projects}, abstract = {We present the interactive assistant Robert that provides situation-adaptive support in the realisation of do-it-yourself (DIY) home improvement projects. Robert assists its users by providing comprehensive step-by-step instructions for completing the DIY project. Each instruction is illustrated with detailed graphics, written and spoken text, as well as with videos. They explain how the steps of the project have to be prepared and assembled and give precise instructions on how to operate the required electric devices. The step-by-step instructions are generated by a hierarchical planner, which enables Robert to adapt to a multitude of environments easily. Parts of the underlying model are derived from an ontology storing information about the available devices and resources. A dialogue manager capable of natural language interaction is responsible for hands-free interaction. We explain the required background technology and present preliminary results of an empirical evaluation.}, year = {2019}, DOI = {10.3233/AIC-180604}, journal = {AI Communications}, volume = {32}, publisher = {IOS Press}, pages = {31-57}, number = {1}, tags = {SFB-T3,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2019/Behnke2019bosch.pdf}, note = {The final publication is available at IOS Press through http://dx.doi.org/10.3233/AIC-180604}, annotation = {The final publication is available at IOS Press through http://dx.doi.org/10.3233/AIC-180604} } @Inbook { Kraus2019CloudCompanion, author = {Kraus, Matthias and Schiller, Marvin R. G. and Behnke, Gregor and Bercher, Pascal and Biundo, Susanne and Glimm, Birte and Minker, Wolfgang}, title = {9th International Workshop on Spoken Dialogue Systems}, abstract = {Companion systems are cooperative, cognitive systems aiming at assist-ing a user in everyday situations. Therefore, these systems require a high level ofavailability. One option to meet this requirement is to use a web-deployable archi-tecture. In this demo paper, we present a multimodal cloud-based dialogue frame-work for the development of a distributed, web-based companion system. The pro-posed framework is intended to provide an efficient, easily extensible, and scalableapproach for these kinds of systems and will be demonstrated in a do-it-yourselfassistance scenario.}, year = {2019}, publisher = {Springer}, chapter = {A Multimodal Dialogue Framework for Cloud-Based Companion Systems}, series = {Lecture Notes in Electrical Engineering}, editor = {Rafael Banchs and Luis Fernando D'Haro and Haizhou Li}, tags = {SFB-T3,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2019/Kraus2019CloudCompanion.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} } @Article { Behnke2018SATltljournal, author = {Behnke, Gregor and Biundo, Susanne}, title = {X and more Parallelism: Integrating LTL-Next into SAT-based Planning with Trajectory Constraints While Allowing for Even More Parallelism}, year = {2018}, DOI = {10.4114/intartif.vol21iss62pp75-90}, journal = {Inteligencia Artificial}, volume = {21}, pages = {75--90}, number = {62}, tags = {SFB-T3}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2018/Behnke2018SATltljournal.pdf} } @Inproceedings { Behnke2018MoreParallelLTL, author = {Behnke, Gregor and Biundo, Susanne}, title = {X and more Parallelism - Integrating LTL-Next into SAT-based Planning with Trajectory Constraints while Allowing for even more Parallelism}, abstract = {Linear temporal logic (LTL) provides expressive means to specify temporally extended goals as well as preferences. Recent research has focussed on compilation techniques, i.e., methods to alter the domain ensuring that every solution adheres to the temporally extended goals. This requires either new actions or an construction that is exponential in the size of the formula. A translation into boolean satisfiability (SAT) on the other hand requires neither. So far only one such encoding exists, which is based on the parallel ∃-step encoding for classical planning. We show a connection between it and recently developed compilation techniques for LTL, which may be exploited in the future. The major drawback of the encoding is that it is limited to LTL without the X operator. We show how to integrate X and describe two new encodings, which allow for more parallelism than the original encoding. An empirical evaluation shows that the new encodings outperform the current state-of-the-art encoding.}, year = {2018}, booktitle = {Proceedings of the Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems (COPLAS)}, pages = {1--10}, tags = {SFB-T3}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2018/Behnke2018satltl.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 {\dq}Technische Unterst{\"u}tzungssysteme, die die Menschen wirklich wollen{\dq} (engl: Proceedings of the 3rd {\dq}Transdisciplinary 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.} } @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} } @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 { 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 { 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 { 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} } @Inproceedings { Behnke2018HomeImprovementSystem, author = {Behnke, Gregor and Schiller, Marvin R. G. and Kraus, Matthias and Bercher, Pascal and Schmautz, Mario and Dorna, Michael and Minker, Wolfgang and Glimm, Birte and Biundo, Susanne}, title = {Instructing Novice Users on How to Use Tools in DIY Projects}, abstract = {Novice users require assistance when performing handicraft tasks. Adequate instruction ensures task completion and conveys knowledge and abilities required to perform the task. We present an assistant teaching novice users how to operate electronic tools, such as drills, saws, and sanders, in the context of Do-It-Yourself (DIY) home improvement projects. First, the actions that need to be performed for the project are determined by a planner. Second, a dialogue manager capable of natural language interaction presents these actions as instructions to the user. Third, questions on these actions and involved objects are answered by generating appropriate ontology-based explanations.}, year = {2018}, DOI = {10.24963/ijcai.2018/844}, booktitle = {Proceedings of the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence (IJCAI-ECAI 2018)}, publisher = {IJCAI}, pages = {5805--5807}, tags = {SFB-T3}, web_url = {www.ijcai.org}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2018/Behnke2018DIY.pdf} } @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 showingthe complete picture{\\&}quot; 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 { 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} } @Inproceedings { Kraus2018CompanionCloudDemo, author = {Kraus, Matthias and Behnke, Gregor and Bercher, Pascal and Schiller, Marvin R. G. and Biundo, Susanne and Glimm, Birte and Minker, Wolfgang}, title = {A Multimodal Dialogue Framework for Cloud-Based Companion Systems}, abstract = {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.}, year = {2018}, booktitle = {Proc. of the 10th International Workshop on Spoken Dialog Systems Technology (IWSDS 2018)}, tags = {SFB-TRR-62,SFB-T3,Planning,KnowledgeModeling}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2018/Kraus2018CompanionCloudDemo.pdf} } @Inproceedings { schillerEtAlMCI2018, author = {Schiller, Marvin R. G. and Behnke, Gregor and Bercher, Pascal 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}, 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 {\\&}ndash; if necessary {\\&}ndash; 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.}, year = {2018}, booktitle = {Proceedings of MCI Workshop {\dq}Digital Companion{\dq}}, pages = {925--930}, tags = {SFB-TRR-62,SFB-T3}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2018/MCI-WS19-schillerEtAl2018.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} } @Inbook { Hoernle2017CompBookReferenceArchitecture, author = {H{\"o}rnle, Thilo and Tornow, Michael and Honold, Frank and Schwegler, Reinhard and Heinemann, Ralph and Biundo, Susanne and Wendemuth, Andreas}, title = {Companion-Systems: A Reference Architecture}, abstract = {Companion-Technology for cognitive technical systems consists of a multitude of components that implement different properties. A primary point is the architecture which is responsible for the interoperability of all components. It defines the capabilities of the systems crucially. For research concerning the requirements and effects of the architecture, several demonstration scenarios were developed. Each of these demonstration scenarios focuses on some aspects of a Companion-System. For the implementation a middleware concept was used, having the capability to realize the major part of the Companion-Systems. Currently the system architecture takes up only a minor property in projects which are working on related research topics. For the description of an architecture representing the major part of possible Companion-Systems, the demonstration scenarios are studied with regard to their system structure and the constituting components. A monolithic architecture enables a simple system design and fast direct connections between the components, such as: sensors with their processing and fusion components, knowledge bases, planning components, dialog systems and interaction components. Herein, only a limited number of possible Companion-Systems can be represented. In a principled approach, a dynamic architecture, capable of including new components during run time, is able to represent almost all Companion-Systems. Furthermore, an approach for enhancing the architecture is introduced.}, year = {2017}, DOI = {10.1007/978-3-319-43665-4_22}, booktitle = {Companion Technology -- A Paradigm Shift in Human-Technology Interaction}, publisher = {Springer}, chapter = {22}, series = {Cognitive Technologies}, editor = {Susanne Biundo and Andreas Wendemuth}, pages = {449-469}, keywords = {SFB-TRR-62}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/Hoernle2017CompBookReferenceArchitecture.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 {\\&}ndash; 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} } @Inbook { Behnke2017CompBookMIP, author = {Behnke, Gregor and Nielsen, Florian and Schiller, Marvin R. G. and Ponomaryov, Denis and Bercher, Pascal and Glimm, Birte and Minker, Wolfgang and Biundo, Susanne}, title = {To Plan for the User Is to Plan With the User -- Integrating User Interaction Into the Planning Process}, abstract = {Settings where systems and users work together to solve problems collaboratively are among the most challenging applications of Companion-Technology. So far we have seen how planning technology can be exploited to realize Companion-Systems that adapt flexibly to changes in the user’s situation and environment and provide detailed help for users to realize their goals. However, such systems lack the capability to generate their plans in cooperation with the user. In this chapter we go one step further and describe how to involve the user directly into the planning process. This enables users to integrate their wishes and preferences into plans and helps the system to produce individual plans, which in turn let the Companion-System gain acceptance and trust from the user. Such a Companion-System must be able to manage diverse interactions with a human user. A so-called mixed-initiative planning system integrates several Companion-Technologies which are described in this chapter. For example, a{--}not yet final{--}plan, including its flaws and solutions, must be presented to the user to provide a basis for her or his decision. We describe how a dialog manager can be constructed such that it can handle all communication with a user. Naturally, the dialog manager and the planner must use coherent models. We show how an ontology can be exploited to achieve such models. Finally, we show how the causal information included in plans can be used to answer the questions a user might have about a plan. The given capabilities of a system to integrate user decisions and to explain its own decisions to the user in an appropriate way are essential for systems that interact with human users.}, year = {2017}, DOI = {10.1007/978-3-319-43665-4_7}, booktitle = {Companion Technology -- A Paradigm Shift in Human-Technology Interaction}, publisher = {Springer}, chapter = {7}, series = {Cognitive Technologies}, editor = {Susanne Biundo and Andreas Wendemuth}, pages = {123--144}, tags = {SFB-TRR-62,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/Behnke2017CompBookMIP.pdf} } @Inproceedings { Behnke2017Sloth, author = {Behnke, Gregor and Nielsen, Florian and Schiller, Marvin R. G. and Bercher, Pascal and Kraus, Matthias and Minker, Wolfgang and Biundo, Susanne and Glimm, Birte}, title = {SLOTH - the Interactive Workout Planner}, abstract = {We present the mixed-initiative planning system SLOTH, which is designed to assist users in planning a fitness workout. Mixed-initiative planning systems are especially useful for companion systems, as they allow the seamless integration of the complex cognitive ability of planning into ambient assistance systems. This is achieved by integrating the user directly into the process of plan generation and thereby allowing him to specify these objectives and to be assisted in generating a plan that not only achieves his objectives, but at the same time also fits his preferences. We present the capabilities that are integrated into SLOTH and discuss the design choices and considerata that have to be taken into account when constructing a mixed-initiative planning system.}, year = {2017}, DOI = {10.1109/COMPANION.2017.8287077}, booktitle = {Proceedings of the 2nd International Conference on Companion Technology (ICCT 2017)}, publisher = {IEEE}, tags = {SFB-TRR-62,Planning}, web_url = {http://ieeexplore.ieee.org/document/8287077/}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/Behnke2017Sloth.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 { 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 {\\&}ndash; until now {\\&}ndash; 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} } @Book { Biundo2017ParadigmShift, author = {Biundo, Susanne and Wendemuth, Andreas}, title = {Companion Technology - A Paradigm Shift in Human-Technology Interaction}, abstract = {Future technical systems will be companion systems, competent assistants that provide their functionality in a completely individualized way, adapting to a user’s capabilities, preferences, requirements, and current needs, and taking into account both the emotional state and the situation of the individual user. This book presents the enabling technology for such systems. It introduces a variety of methods and techniques to implement an individualized, adaptive, flexible, and robust behavior for technical systems by means of cognitive processes, including perception, cognition, interaction, planning, and reasoning. The technological developments are complemented by empirical studies from psychological and neurobiological perspectives.}, year = {2017}, DOI = {10.1007/978-3-319-43665-4}, publisher = {Springer}, editor = {Susanne Biundo and Andreas Wendemuth}, keywords = {Companion Systems, Cognitive Systems, Artificial Intelligence (AI), Automated Planning, Knowledge Representation (KR), Human-Computer Interaction (HCI), Multimodal Interaction, Dialogue Management, Emotion Recognition, Information Fusion}, tags = {SFB-TRR-62,Planning}, web_url = {https://link.springer.com/book/10.1007/978-3-319-43665-4}, file_url = {https://link.springer.com/book/10.1007/978-3-319-43665-4} } @Inbook { Richter2017UserCenteredPlanningUnderUncertainty, author = {Richter, Felix and Biundo, Susanne}, title = {Addressing Uncertainty in Hierarchical User-Centered Planning}, abstract = {Companion-Systems need to reason about dynamic properties of their users, e.g., their emotional state, and the current state of the environment. The values of these properties are often not directly accessible; hence information on them must be pieced together from indirect, noisy or partial observations. To ensure probability-based treatment of partial observability on the planning level, planning problems can be modeled as Partially Observable Markov Decision Processes (POMDPs). While POMDPs can model relevant planning problems, it is algorithmically difficult to solve them. A starting point for mitigating this is that many domains exhibit hierarchical structures where plans consist of a number of higher-level activities, each of which can be implemented in different ways that are known a priori. We show how to make use of such structures in POMDPs using the Partially Observable HTN (POHTN) planning approach by developing a Partially Observable HTN (POHTN) action hierarchy for an example domain derived from an existing deterministic demonstration domain. We then apply Monte-Carlo Tree Search to POHTNs for generating plans and evaluate both the developed domain and the POHTN approach empirically.}, year = {2017}, DOI = {10.1007/978-3-319-43665-4_6}, booktitle = {Companion Technology -- A Paradigm Shift in Human-Technology Interaction}, publisher = {Springer}, chapter = {6}, series = {Cognitive Technologies}, editor = {Susanne Biundo and Andreas Wendemuth}, pages = {101--121}, keywords = {SFB-TRR-62, Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/Richter2017UserCenteredPlanningUnderUncertainty.pdf} } @Inbook { Biundo2017CompBookIntro, author = {Biundo, Susanne and Wendemuth, Andreas}, title = {An Introduction to Companion-Technology}, abstract = {Companion-technology enables a new generation of intelligent systems. These Companion-systems smartly adapt their functionality to a user’s individual requirements. They comply with his or her abilities, preferences, and current needs and adjust their behavior as soon as critical changes of the environment or changes of the user’s emotional state or disposition are observed. Companion-systems are distinguished by characteristics such as competence, individuality, adaptability, availability, cooperativeness, and trustworthiness. These characteristics are realized by integrating the technical functionality of systems with a combination of cognitive processes. Companion-systems are able to perceive the user and the environment; they reason about the current situation, exploit background knowledge, and provide and pursue appropriate plans of action; and they enter into a dialog with the user where they select the most suitable modes of interaction in terms of media, modalities and dialog strategies. This chapter introduces the essence of Companion-technology and sheds light on the huge range of its prospective applications.}, year = {2017}, DOI = {10.1007/978-3-319-43665-4_1}, booktitle = {Companion Technology -- A Paradigm Shift in Human-Technology Interaction}, publisher = {Springer}, chapter = {1}, series = {Cognitive Technologies}, editor = {Susanne Biundo and Andreas Wendemuth}, pages = {1--15}, tags = {SFB-TRR-62}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/Biundo2017CompBookIntro.pdf} } @Inproceedings { Schiller17CouplingKnowledge, author = {Schiller, Marvin R. G. and Behnke, Gregor and Schmautz, Mario and Bercher, Pascal and Kraus, Matthias and Dorna, Michael and Minker, Wolfgang and Glimm, Birte and Biundo, Susanne}, title = {A Paradigm for Coupling Procedural and Conceptual Knowledge in Companion Systems}, abstract = {Companion systems are technical systems that adjust their functionality to the needs and the situation of an individual user. Consequently, companion systems are strongly knowledge-based. We propose a modelling paradigm for integrating procedural and conceptual knowledge which is targeted at companion systems that require a combination of planning and reasoning capabilities. The presented methodology couples the hierarchical task network (HTN) planning formalism with an ontology-based knowledge representation, thereby minimising redundancies in modelling and enabling the use of state-of-the-art reasoning and planning tools on the shared knowledge model. The approach is applied within a prototype of a companion system that assists novice users in the do-it-yourself (DIY) domain with the planning and execution of home improvement projects involving the use of power tools.}, year = {2017}, DOI = {10.1109/COMPANION.2017.8287072}, booktitle = {Proceedings of the 2nd International Conference on Companion Technology (ICCT 2017)}, publisher = {IEEE}, tags = {SFB-TRR-62,SFB-T3,Planning,KnowledgeModeling}, web_url = {http://ieeexplore.ieee.org/document/8287072/}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/SBSBKDMGB-ICCT2017.pdf} } @Inbook { Geier2017CompBookMLKP, author = {Geier, Thomas and Biundo, Susanne}, title = {Multi-Level Knowledge Processing in Cognitive Technical Systems}, abstract = {Companion-Systems are composed of different modules that have to share a single, sound estimate of the current situation. While the long-term decision-making of automated planning requires knowledge about the user’s goals, short-term decisions, like choosing among modes of user-interaction, depend on properties such as lighting conditions. In addition to the diverse scopes of the involved models, a large portion of the information required within such a system cannot be directly observed, but has to be inferred from background knowledge and sensory data{--}sometimes via a cascade of abstraction layers, and often resulting in uncertain predictions. In this contribution, we interpret an existing cognitive technical system under the assumption that it solves a factored, partially observable Markov decision process. Our interpretation heavily draws from the concepts of probabilistic graphical models and hierarchical reinforcement learning, and fosters a view that cleanly separates between inference and decision making. The results are discussed and compared to those of existing approaches from other application domains.}, year = {2017}, DOI = {10.1007/978-3-319-43665-4_2}, booktitle = {Companion Technology -- A Paradigm Shift in Human-Technology Interaction}, publisher = {Springer}, chapter = {2}, series = {Cognitive Technologies}, editor = {Susanne Biundo}, pages = {17--36}, tags = {SFB-TRR-62}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/Geier2017CompBookMLKP.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 { 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} } @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 {\\&}ndash; if not most {\\&}ndash; 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} } @Article { Biundo16CompanionTechnology, author = {Biundo, Susanne and Wendemuth, Andreas}, title = {Companion-Technology for Cognitive Technical Systems}, abstract = {We introduce the Transregional Collaborative Research Centre “Companion-Technology for Cognitive Technical Systems” {\\&}ndash; a cross-disciplinary endeavor towards the development of an enabling technology for Companion-systems. These systems completely adjust their functionality and service to the individual user. They comply with his or her capabilities, preferences, requirements, and current needs and adapt to the individual’s emotional state and ambient conditions. Companion-like behavior of technical systems is achieved through the investigation and implementation of cognitive abilities and their well-orchestrated interplay.}, year = {2016}, DOI = {10.1007/s13218-015-0414-8}, journal = {K{\"u}nstliche Intelligenz}, volume = {30}, publisher = {Springer}, pages = {71-75}, number = {1}, tags = {SFB-TRR-62}, web_url = {http://link.springer.com/article/10.1007/s13218-015-0414-8}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2016/Biundo16CompanionTechnology.pdf}, note = {Special Issue on Companion Technologies}, annotation = {Special Issue on Companion Technologies} } @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 {\dq}Companions'' to their users. They serve as co-operative agents assisting in particular tasks or, in a more general sense, even give companionship to humans. Overall, Companion-technology enables technical systems to smartly adapt their services to individual users' current needs, their requests, situation, and emotion. We give an introduction to the field, discuss the most relevant application areas that will benefit from its developments, and review the related research projects.}, 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 { 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} } @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 {\\&}ndash; adaptive, flexible, and cooperative {\\&}ndash; technical systems by applying and fusing techniques from different areas of research. In our special issue we present interesting pieces of work {\\&}ndash; quite a number of new technical contributions, ongoing and completed research projects, several dissertation abstracts, as well as an interview {\\&}ndash; 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 { 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 { Geier2015, author = {Geier, Thomas and Richter, Felix and Biundo, Susanne}, title = {Locally Conditioned Belief Propagation}, abstract = {Conditioned Belief Propagation (CBP) is an algorithm for approximate inference in probabilistic graphical models. It works by conditioning on a subset of variables and solving the remainder using loopy Belief Propagation. Unfortunately, CBP's runtime scales exponentially in the number of conditioned variables. Locally Conditioned Belief Propagation (LCBP) approximates the results of CBP by treating conditions locally, and in this way avoids the exponential blow-up. We formulate LCBP as a variational optimization problem and derive a set of update equations that can be used to solve it. We show empirically that LCBP delivers results that are close to those obtained from CBP, while the computational cost scales favorably with problem size. }, year = {2015}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence (UAI)}, publisher = {AUAI Press}, pages = {296--305}, event_place = {Amsterdam}, keywords = {probablistic inference, belief propagation, approximate inference, graphical models}, tags = {SFB-TRR-62}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2015/Geier2015Lcbp.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 { Nothdurft2015InterplayDialogPlanning, author = {Nothdurft, Florian and Behnke, Gregor and Bercher, Pascal and Biundo, Susanne and Minker, Wolfgang}, title = {The Interplay of User-Centered Dialog Systems and AI Planning}, abstract = {Technical systems evolve from simple dedicated task solvers to cooperative and competent assistants, helping the user with increasingly complex and demanding tasks. For this, they may proactively take over some of the users responsibilities and help to find or reach a solution for the user’s task at hand, using e.g., Artificial Intelligence (AI) Planning techniques. However, this intertwining of user-centered dialog and AI planning systems, often called mixed-initiative planning (MIP), does not only facilitate more intelligent and competent systems, but does also raise new questions related to the alignment of AI and human problem solving. In this paper, we describe our approach on integrating AI Planning techniques into a dialog system, explain reasons and effects of arising problems, and provide at the same time our solutions resulting in a coherent, userfriendly and efficient mixed-initiative system. Finally, we evaluate our MIP system and provide remarks on the use of explanations in MIP-related phenomena.}, year = {2015}, booktitle = {Proceedings of the 16th Annual Meeting of the Special Interest Group on Discourse and Dialogue (SIGDIAL)}, publisher = {Association for Computational Linguistics}, pages = {344--353}, event_place = {Prague, Czech Republic}, tags = {SFB-TRR-62,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2015/Nothdurft15MIP.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 { Behnke2015Coherence, author = {Behnke, Gregor and Ponomaryov, Denis and Schiller, Marvin R. G. and Bercher, Pascal and Nothdurft, Florian and Glimm, Birte and Biundo, Susanne}, title = {Coherence Across Components in Cognitive Systems {\\&}ndash; One Ontology to Rule Them All}, abstract = {The integration of the various specialized components of cognitive systems poses a challenge, in particular for those architectures that combine planning, inference, and human-computer interaction (HCI). An approach is presented that exploits a single source of common knowledge contained in an ontology. Based upon the knowledge contained in it, specialized domain models for the cognitive systems’ components can be generated automatically. Our integration targets planning in the form of hierarchical planning, being well-suited for HCI as it mimics planning done by humans. We show how the hierarchical structures of such planning domains can be (partially) inferred from declarative background knowledge. The same ontology furnishes the structure of the interaction between the cognitive system and the user. First, explanations of plans presented to users are enhanced by ontology explanations. Second, a dialog domain is created from the ontology coherent with the planning domain. We demonstrate the application of our technique in a fitness training scenario.}, year = {2015}, booktitle = {Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2015)}, publisher = {AAAI Press}, pages = {1442-1449}, event_name = {IJCAI 2015}, event_place = {Buenos Aires}, tags = {SFB-TRR-62,Planning,AutomatedReasoning}, web_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2015/Behnke15IJCAI-poster.pdf}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2015/BPSB15a.pdf} } @Inproceedings { BBBGPS2015OntologiesAndPlanning, author = {Behnke, Gregor and Bercher, Pascal and Biundo, Susanne and Glimm, Birte and Ponomaryov, Denis and Schiller, Marvin R. G.}, title = {Integrating Ontologies and Planning for Cognitive Systems}, 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.}, year = {2015}, booktitle = {Proceedings of the 28th International Workshop on Description Logics (DL 2015)}, publisher = {CEUR Workshop Proceedings}, tags = {AutomatedReasoning, Planning, SFB-TRR-62}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2015/BBBG15a.pdf} } @Inproceedings { Richter2015believing, author = {Richter, Felix and Geier, Thomas and Biundo, Susanne}, title = {Believing in POMDPs}, abstract = {Partially observable Markov decision processes (POMDP) are well-suited for realizing sequential decision making capabilities that respect uncertainty in Companion systems that are to naturally interact with and assist human users. Unfortunately, their complexity prohibits modeling the entire Companion system as a POMDP. We therefore propose an approach that makes use of abstraction to enable employing POMDPs in Companion systems and discuss challenges for applying it.}, year = {2015}, booktitle = {Proceedings of the First International Symposium on Companion Technology (ISCT 2015)}, event_name = {First International Symposium on Companion Technology}, event_place = {Ulm, Germany}, keywords = {POMDP, cognitive technical systems}, tags = {SFB-TRR-62,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2015/believingPOMDPs.pdf} } @Inproceedings { Behnke15MIPDiscussion, author = {Behnke, Gregor and Schiller, Marvin R. G. and Ponomaryov, Denis and Nothdurft, Florian and Bercher, Pascal and Minker, Wolfgang and Glimm, Birte and Biundo, Susanne}, title = {A Unified Knowledge Base for Companion-Systems - A Case Study in Mixed-Initiative Planning}, abstract = {Companion systems aim to extend the abilities of ordinary technical systems, for instance by modeling the user's situation, by recognizing the user's intentions, and by being able to interact with the user and to adapt to her/him. Such a system depends on planning capabilities to determine which actions are necessary to achieve a particular goal. In many situations it may not be appropriate for a companion system to develop plans on its own, but instead it has to integrate the user while creating the plan, i.e., it needs to be mixed-initiative. Based on earlier work, we demonstrate how a central knowledge base for a mixed-initiative planning system can be designed. We outline various benefts our approach brings to bear within a companion system. Lastly, we present several requests a user might issue towards the mixed-initiative planning system and how they can be answered by harnessing the knowledge base.}, year = {2015}, booktitle = {Proceedings of the First International Symposium on Companion Technology (ISCT 2015)}, pages = {43--48}, event_name = {First International Symposium on Companion Technology (ISCT 2015)}, event_place = {Ulm, Germany}, tags = {SFB-TRR-62,Planning,AutomatedReasoning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2015/Behnke15MIPDiscussion.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} } @Article { Glodek201517, author = {Glodek, Michael and Honold, Frank and Geier, Thomas and Krell, Gerald and Nothdurft, Florian and Reuter, Stephan and Sch{\"u}ssel, Felix and H{\"o}rnle, Thilo and Dietmayer, Klaus and Minker, Wolfgang and Biundo, Susanne and Weber, Michael and Palm, G{\"u}nther and Schwenker, Friedhelm}, title = {Fusion paradigms in cognitive technical systems for human{\\&}ndash;computer interaction}, abstract = {Abstract Recent trends in human{\\&}ndash;computer interaction (HCI) show a development towards cognitive technical systems (CTS) to provide natural and efficient operating principles. To do so, a CTS has to rely on data from multiple sensors which must be processed and combined by fusion algorithms. Furthermore, additional sources of knowledge have to be integrated, to put the observations made into the correct context. Research in this field often focuses on optimizing the performance of the individual algorithms, rather than reflecting the requirements of CTS. This paper presents the information fusion principles in CTS architectures we developed for Companion Technologies. Combination of information generally goes along with the level of abstractness, time granularity and robustness, such that large CTS architectures must perform fusion gradually on different levels {--} starting from sensor-based recognitions to highly abstract logical inferences. In our CTS application we sectioned information fusion approaches into three categories: perception-level fusion, knowledge-based fusion and application-level fusion. For each category, we introduce examples of characteristic algorithms. In addition, we provide a detailed protocol on the implementation performed in order to study the interplay of the developed algorithms.}, year = {2015}, issn = {0925-2312}, DOI = {10.1016/j.neucom.2015.01.076}, journal = {Neurocomputing}, volume = {161}, pages = {17 - 37}, keywords = {Human{\\&}ndash;computer interaction}, tags = {SFB-TRR-62}, file_url = {http://www.sciencedirect.com/science/article/pii/S0925231215002155/pdfft?md5=0f4a009f3f5ba7b155a82192be2a0dbe{\\&}pid=1-s2.0-S0925231215002155-main.pdf} } @Techreport { Geier2014CBPTR, author = {Geier, Thomas and Richter, Felix and Biundo, Susanne}, title = {Conditioned Belief Propagation Revisited: Extended Version}, abstract = {Belief Propagation (BP) applied to cyclic problems is a well known approximate inference scheme for probabilistic graphical models. To improve its accuracy, Conditioned Belief Propagation (CBP) has been proposed, which splits a problem into subproblems by conditioning on variables, applies BP to subproblems, and merges the results to produce an answer to the original problem. In this work, we propose a reformulated version of CBP that exhibits anytime behavior and allows for more specific tuning by formalizing a further aspect of the algorithm through the use of a leaf selection heuristic. We propose several simple and easy to compute heuristics and demonstrate their performance using an empirical evaluation on randomly generated problems.}, year = {2014}, month = {8}, institution = {Ulm University}, number = {UIB 2014-03}, tags = {SFB-TRR-62,KnowledgeModeling}, web_url = {http://vts.uni-ulm.de/doc.asp?id=9201 }, file_url = {http://vts.uni-ulm.de/docs/2014/9201/vts_9201_13795.pdf} } @Inproceedings { Bercher14TDGHeuristics, author = {Bercher, Pascal and Keen, Shawn and Biundo, Susanne}, title = {Hybrid Planning Heuristics Based on Task Decomposition Graphs}, abstract = {Hybrid Planning combines Hierarchical Task Network (HTN) planning with concepts known from Partial-Order Causal-Link (POCL) planning. We introduce novel heuristics for Hybrid Planning that estimate the number of necessary modifications to turn a partial plan into a solution. These estimates are based on the task decomposition graph that contains all decompositions of the abstract tasks in the planning domain. Our empirical evaluation shows that the proposed heuristics can significantly improve planning performance.}, year = {2014}, booktitle = {Proceedings of the Seventh Annual Symposium on Combinatorial Search (SoCS 2014)}, publisher = {AAAI Press}, pages = {35--43}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2014/Bercher14HybridHeuristicsSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2014/Bercher14HybridHeuristics.pdf} } @Inproceedings { Bercher14HybridPlanningApplication, author = {Bercher, Pascal and Biundo, Susanne and Geier, Thomas and Hoernle, Thilo and Nothdurft, Florian and Richter, Felix and Schattenberg, Bernd}, title = {Plan, Repair, Execute, Explain - How Planning Helps to Assemble your Home Theater}, abstract = {In various social, work-related, or educational contexts, an increasing demand for intelligent assistance systems can be observed. In this paper, we present a domain-independent approach that combines a number of planning and interaction components to realize advanced user assistance. Based on a hybrid planning formalism, the components provide facilities including the generation, execution, and repair as well as the presentation and explanation of plans. We demonstrate the feasibility of our approach by means of a system that aims to assist users in the assembly of their home theater. An empirical evaluation shows the benefit of such a supportive system, in particular for persons with a lack of domain expertise.}, year = {2014}, booktitle = {Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014) }, publisher = {AAAI Press}, pages = {386--394}, tags = {SFB-TRR-62,Planning,KnowledgeModeling}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2014/Bercher14PlanRepairExecuteExplainSlides.pdf}, web_url2 = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2014/movie.zip}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2014/Bercher14PlanRepairExecuteExplain.pdf}, note = {The domain can be downloaded from http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2014/Bercher14PlanRepairExecuteExplain.zip} } @Inproceedings { Pragst14CyberSecurity, author = {Pragst, Louisa and Richter, Felix and Bercher, Pascal and Schattenberg, Bernd and Biundo, Susanne}, title = {Introducing Hierarchy to Non-Hierarchical Planning Models {\\&}ndash; A Case Study for Behavioral Adversary Models}, 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.}, year = {2014}, booktitle = {28th PuK Workshop {\dq}Planen, Scheduling und Konfigurieren, Entwerfen{\dq} (PuK 2014)}, keywords = {Hybrid Planning, Hierarchical Planning, POCL Planning, Domain Modeling, Task Hierarchy, Abstractions}, tags = {SFB-TRR-62,Planning,KnowledgeModeling}, 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/Pragst14CyberSecurity.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 { 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 {\dq}Planen, 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 { Geier2014CBP, author = {Geier, Thomas and Richter, Felix and Biundo, Susanne}, title = {Conditioned Belief Propagation Revisited}, abstract = {Belief Propagation (BP) applied to cyclic problems is a well known approximate inference scheme for probabilistic graphical models. To improve the accuracy of BP, a divide-and-conquer approach termed Conditioned Belief Propagation (CBP) has been proposed in the literature. It recursively splits a problem by conditioning on variables, applies BP to subproblems, and merges the results to produce an answer to the original problem. In this essay, we propose a reformulated version of CBP that exhibits anytime behavior, and allows for more specific tuning by formalizing a further decision point that decides which subproblem is to be decomposed next. We propose some simple and easy to compute heuristics, and demonstrate their performance using an empirical evaluation on randomly generated problems.}, year = {2014}, DOI = {10.3233/978-1-61499-419-0-1011}, 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 = {1011-1012}, event_name = {21st European Conference on Artificial Intelligence (ECAI 2014)}, event_place = {Prague, Czech Republic}, tags = {SFB-TRR-62,KnowledgeModeling}, web_url = {http://ebooks.iospress.nl/volumearticle/37095} } @Inproceedings { honold2014b, author = {Honold, Frank and Bercher, Pascal and Richter, Felix and Nothdurft, Florian and Geier, Thomas and Barth, Roland and H{\"o}rnle, Thilo and Sch{\"u}ssel, Felix and Reuter, Stephan and Rau, Matthias and Bertrand, Gregor and Seegebarth, Bastian and Kurzok, Peter and Schattenberg, Bernd and Minker, Wolfgang and Weber, Michael and Biundo, Susanne}, title = {Companion-Technology: Towards User- and Situation-Adaptive Functionality of Technical Systems}, abstract = {The properties of multimodality, individuality, adaptability, availability, cooperativeness and trustworthiness are at the focus of the investigation of Companion Systems. In this article, we describe the involved key components of such a system and the way they interact with each other. Along with the article comes a video, in which we demonstrate a fully functional prototypical implementation and explain the involved scientific contributions in a simplified manner. The realized technology considers the entire situation of the user and the environment in current and past states. The gained knowledge reflects the context of use and serves as basis for decision-making in the presented adaptive system.}, year = {2014}, DOI = {10.1109/IE.2014.60}, booktitle = {10th International Conference on Intelligent Environments (IE 2014)}, publisher = {IEEE}, pages = {378--381}, keywords = {Adaptive HCI; AI Planning; Dialog Management; Interaction Management; Companion Technology}, tags = {SFB-TRR-62,Planning,KnowledgeModeling}, web_url = {https://mirkwood.informatik.uni-ulm.de/sfbtrr62/companion-system.mp4}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2014/Honold2014HomeTheaterVideo.pdf} } @Article { Glodek2014, author = {Glodek, Michael and Geier, Thomas and Biundo, Susanne and Palm, G{\"u}nther}, title = {A layered architecture for probabilistic complex pattern recognition to detect user preferences}, abstract = {The recognition of complex patterns is nowadays one of the most challenging tasks in machine learning, and it promises to be of great benefit for many applications, e.g. by allowing advanced human computer interaction to access the user’s situative context. This work examines a layered architecture that operates on different temporal granularities to infer complex patterns of user preferences. Classical hidden Markov models (HMM), conditioned HMM (CHMM) and fuzzy CHMM (FCHMM) are compared to find the best configuration in the lower architecture layers. In the uppermost layer, a Markov logic network (MLN) is applied to infer the user preference in a probabilistic rule-based manner. For each layer a comprehensive evaluation is given. We provide empirical evidence showing that the layered architecture using FCHMM and MLN is well-suited to recognize patterns on different layers.}, year = {2014}, DOI = {10.1016/j.bica.2014.06.003}, journal = {Neural-Symbolic Networks for Cognitive Capacities}, tags = {SFB-TRR-62}, web_url = {http://www.sciencedirect.com/science/article/pii/S2212683X14000486} } @Inproceedings { Bercher13EncodingPlans, author = {Bercher, Pascal and Biundo, Susanne}, title = {Encoding Partial Plans for Heuristic Search}, 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.}, year = {2013}, booktitle = {Proceedings of the 4th Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2013) at ICAPS 2013}, pages = {11--15}, tags = {SFB-TRR-62,Planning,KnowledgeModeling}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13EncodingPlansSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13EncodingPlans.pdf} } @Inproceedings { Bercher13SampleFF, author = {Bercher, Pascal and Geier, Thomas and Richter, Felix and Biundo, Susanne}, title = {On Delete Relaxation in Partial-Order Causal-Link Planning}, abstract = {We prove a new complexity result for Partial-Order Causal-Link (POCL) planning, in which we study the hardness of refining a search node (i.e., a partial plan) to a valid solution given a delete effect-free domain model. While the corresponding decision problem is known to be polynomial in state-based search (where search nodes are states), it turns out to be intractable in the POCL setting. Since both the currently best-informed heuristics for POCL planning are based on delete relaxation, we hope that our result sheds some new light on the problem of designing heuristics for POCL planning. Based on this result, we developed a new variant of one of these heuristics which incorporates more information of the current partial plan. We evaluate our heuristic on several domains of the early International Planning Competitions and compare it with other POCL heuristics from the literature.}, year = {2013}, booktitle = {Proceedings of the 2013 IEEE 25th International Conference on Tools with Artificial Intelligence (ICTAI 2013)}, publisher = {IEEE Computer Society}, pages = {674--681}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13SampleFFSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13SampleFF.pdf} } @Inproceedings { Glodek2013LayeredLogic, author = {Glodek, Michael and Geier, Thomas and Biundo, Susanne and Schwenker, Friedhelm and Palm, G{\"u}nther}, title = {Recognizing User Preferences Based on Layered Activity Recognition and First-Order Logic}, abstract = {Only few cognitive architectures have been proposed that cover the complete range from recognizers working on the direct sensor input, to logical inference mechanisms of classical artificial intelligence (AI). Logical systems operate on abstract predicates, which are often related to an action-like state transition, especially when compared to the classes recognized by pattern recognition approaches. On the other hand, pattern recognition is often limited to static patterns, and temporal and multi-modal aspects of a class are often not regarded, e.g. by testing only on pre-segmented data. Recent trends in AI aim at developing applications and methods that are motivated by data-driven real world scenarios, while the field of pattern recognition attempts to push forward the boundary of pattern complexity. We propose a new generic architecture to close the gap between AI and pattern recognition approaches. In order to detect abstract complex patterns, we process sequential data in layers. On each layer, a set of elementary classes is recognized and the outcome of the classification is passed to the successive layer such that the time granularity increases. Layers can combine modalities, additional symbolic information or make use of reasoning algorithms. We evaluated our approach in an on-line scenario of activity recognition using three layers. The obtained results show that the combination of concepts from pattern recognition and high-level symbolic information leads to a prosperous and powerful symbiosis.}, year = {2013}, DOI = {10.1109/ICTAI.2013.101}, booktitle = {Proceedings of the 2013 IEEE 25th International Conference on Tools with Artificial Intelligence (ICTAI 2013)}, pages = {648-653}, keywords = {Conditioned hidden Markov model;Layered architecture;Markov logic network}, tags = {SFB-TRR-62}, web_url = {http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp={\\&}arnumber=6735312} } @Inproceedings { Bercher13POCLPreferences, author = {Bercher, Pascal and Ginter, Fabian and Biundo, Susanne}, title = {Search Strategies for Partial-Order Causal-Link Planning with Preferences}, 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 \textitnet-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.}, year = {2013}, booktitle = {27th PuK Workshop {\dq}Planen, Scheduling und Konfigurieren, Entwerfen{\dq} (PuK 2013)}, pages = {29--40}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13POCLPreferencesSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13POCLPreferences.pdf} } @Inproceedings { Bercher13POCLHeuristics, author = {Bercher, Pascal and Geier, Thomas and Biundo, Susanne}, title = {Using State-Based Planning Heuristics for Partial-Order Causal-Link Planning}, abstract = {We present a technique which allows partial-order causal-link (POCL) planning systems to use heuristics known from state-based planning to guide their search. The technique encodes a given partially ordered partial plan as a new classical planning problem that yields the same set of solutions reachable from the given partial plan. As heuristic estimate of the given partial plan a state-based heuristic can be used estimating the goal distance of the initial state in the encoded problem. This technique also provides the first admissible heuristics for POCL planning, simply by using admissible heuristics from state-based planning. To show the potential of our technique, we conducted experiments where we compared two of the currently strongest heuristics from state-based planning with two of the currently best-informed heuristics from POCL planning.}, year = {2013}, booktitle = {Advances in Artificial Intelligence, Proceedings of the 36th German Conference on Artificial Intelligence (KI 2013)}, publisher = {Springer}, pages = {1--12}, tags = {SFB-TRR-62,Planning,KnowledgeModeling}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13POCLHeuristicsSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13POCLHeuristics.pdf} } @Inproceedings { Mueller2012HPOMDPs, author = {M{\"u}ller, Felix and Sp{\"a}th, Christian and Geier, Thomas and Biundo, Susanne}, title = {Exploiting Expert Knowledge in Factored POMDPs}, abstract = {Decision support in real-world applications is often challenging because one has to deal with large and only partially observable domains. In case of full observability, large domains are successfully tackled by making use of expert knowledge and employing methods like Hierarchical Task Network (HTN) planning. In this paper, we present an approach that transfers the advantages of HTN planning to partially observable domains. Experimental results for two implemented algorithms, UCT and A* search, show that our approach significantly speeds up the generation of high-quality policies: the policies generated by our approach consistently outperform policies generated by Symbolic Perseus and can be computed in less than 10% of its runtime on average.}, year = {2012}, month = {8}, booktitle = {Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012)}, publisher = {IOS Press}, pages = {606--611}, tags = {SFB-TRR-62,Planning}, web_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Mueller12HierarchicalFSCsReloadedSlides.pdf}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Mueller12HierarchicalFSCsReloaded.pdf} } @Inproceedings { Geier2012PersonTracking, author = {Geier, Thomas and Reuter, Stephan and Dietmayer, Klaus and Biundo, Susanne}, title = {Goal-Based Person Tracking Using a First-Order Probabilistic Model}, abstract = {This work addresses the problem of person tracking using additional background information. We augment a particle filter-based tracking algorithm with a first-order probabilistic model expressed through Markov Logic Networks to tackle the data association problem in domains with a high occlusion rate. Using a high-level model description allows us to easily integrate additional information like a floor plan or goal information into a joint model and resolve occlusion situations that would otherwise result in the loss of association. We discuss the engineered model in detail and give an empirical evaluation using an indoor setting.}, year = {2012}, month = {8}, booktitle = {Proceedings of the Ninth UAI Bayesian Modeling Applications Workshop (UAI-AW 2012)}, tags = {SFB-TRR-62, KnowledgeModeling}, web_url = {http://ceur-ws.org/Vol-962}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Geier12TrackingGoals.pdf} } @Inproceedings { Elkawkagy12LandmarkStrategies, author = {Elkawkagy, Mohamed and Bercher, Pascal and Schattenberg, Bernd and Biundo, Susanne}, title = {Improving Hierarchical Planning Performance by the Use of Landmarks}, abstract = {Hierarchical landmarks can be extracted and used to reduce hierarchical domain models, thereby leading to substantial runtime improvements. In this work, we present novel domain-independent planning strategies based on these landmarks. Our empirical evaluation on four benchmark domains shows that these landmark-aware strategies outperform established search strategies in many cases, even for reduced domain models.}, year = {2012}, month = {7}, booktitle = {Proceedings of the 26th AAAI Conference on Artificial Intelligence ({AAAI} 2012)}, publisher = {AAAI Press}, pages = {1763--1769}, tags = {SFB-TRR-62,Planning}, web_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Elkawkagy12LandmarkStrategiesPoster.pdf}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Elkawkagy12LandmarkStrategies.pdf} } @Inproceedings { Seegebarth12Explanation, author = {Seegebarth, Bastian and M{\"u}ller, Felix and Schattenberg, Bernd and Biundo, Susanne}, title = {Making Hybrid Plans More Clear to Human Users - A Formal Approach for Generating Sound Explanations}, abstract = {Human users who execute an automatically generated plan want to understand the rationale behind it. Knowledge-rich plans are particularly suitable for this purpose, because they provide the means to give reason for causal, temporal, and hierarchical relationships between actions. Based on this information, focused arguments can be generated that constitute explanations on an appropriate level of abstraction. In this paper, we present a formal approach to plan explanation. Information about plans is represented as first-order logic formulae and explanations are constructed as proofs in the resulting axiomatic system. With that, plan explanations are provably correct w.r.t. the planning system that produced the plan. A prototype plan explanation system implements our approach and first experiments give evidence that finding plan explanations is feasible in real-time.}, year = {2012}, month = {6}, day = {27}, booktitle = {Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS 2012)}, publisher = {AAAI Press}, pages = {225--233}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Seegebarth12PlanExplanationSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Seegebarth12PlanExplanation.pdf} } @Inproceedings { Bercher12PreferenceHeuristic, author = {Bercher, Pascal and Biundo, Susanne}, title = {A Heuristic for Hybrid Planning with Preferences}, abstract = {In this paper, we introduce an admissible heuristic for hybrid planning with preferences. Hybrid planning is the fusion of hierarchical task network (HTN) planning with partial order causal link (POCL) planning. We consider preferences to be soft goals - facts one would like to see satisfied in a goal state, but which do not have to hold necessarily. Our heuristic estimates the best quality of any solution that can be developed from the current plan under consideration. It can thus be used by any branch-and-bound algorithm that performs search in the space of plans to prune suboptimal plans from the search space.}, year = {2012}, month = {5}, booktitle = {Proceedings of the Twenty-Fifth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2012)}, publisher = {AAAI Press}, pages = {120--123}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Bercher12PreferenceHeuristicPoster.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Bercher12PreferenceHeuristic.pdf} } @Inproceedings { Schattenberg12Mice, author = {Schattenberg, Bernd and L. Schulz, Andreas and Brechmann, Andr{\'e} and W. Ohl, Frank and Biundo, Susanne}, title = {Planning Models for Two-Way Avoidance and Reversal Learning}, abstract = {Reinforcement learning models can explain various aspects of two-way avoidance learning but do not provide a rationale for the relationship found between the dynamics of initial learning and those of reversal learning. Artificial Intelligence planning offers a novel way to conceptualize the learners’ cognitive processes by providing an explicit representation of and reasoning about internal processing stages. Our hybrid planning and plan repair approach demonstrates that the empirically found relationships could be motivated from a consistent theoretical framework.}, year = {2012}, month = {2}, booktitle = {Proceedings of the 7th Vienna International Conference on Mathematical Modelling (MATHMOD 2012)}, address = {Vienna, Austria}, tags = {SFB-TRR-62,Planning}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Schattenberg12PlanningModels.pdf} } @Inproceedings { geier2012association, author = {Geier, Thomas and Reuter, Stephan and Dietmayer, Klaus and Biundo, Susanne}, title = {Track-Person Association Using a First-Order Probabilistic Model}, year = {2012}, DOI = {10.1109/ICTAI.2013.101}, booktitle = {Proceedings of the 24th IEEE International Conference on Tools with Artificial Intelligence (ICTAI)}, pages = {844--851}, event_name = {Tools with Artificial Intelligence}, event_place = {Athens, Greece}, keywords = {SFB-TRR-62, KnowledgeModeling}, web_url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6495131{\\&}tag=1}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Geier2012TrackingB.pdf} } @Inproceedings { Wendemuth2012CompanionTechnology, author = {Wendemuth, Andreas and Biundo, Susanne}, title = {A Companion Technology for Cognitive Technical Systems}, abstract = {The Transregional Collaborative Research Centre SFB/TRR 62 {\dq}A Companion Technology for Cognitive Technical Systems{\dq}, funded by the German Research Foundation (DFG) at Ulm and Magdeburg sites, deals with the systematic and interdisciplinary study of cognitive abilities and their implementation in technical systems. The properties of multimodality, individuality, adaptability, availability, cooperativeness and trustworthiness are at the focus of the investigation. These characteristics show a new type of interactive device which is not only practical and efficient to operate, but as well agreeable, hence the term ”companion”. The realisation of such a technology is supported by technical advancement as well as by neurobiological findings. Companion technology has to consider the entire situation of the user, machine, environment and (if applicable) other people or third interacting parties, in current and historical states. This will reflect the mental state of the user, his embeddedness in the task, and how he is situated in the current process.}, year = {2012}, DOI = {10.1007/978-3-642-34584-5_7}, booktitle = {Cognitive Behavioural Systems: COST 2102 International Training School, Revised Selected Papers}, publisher = {Springer Berlin Heidelberg}, series = {Lecture Notes in Computer Science}, editor = {Anna Esposito, Alessandro Vinciarelli, R{\"u}diger Hoffman, Vincent C. M{\"u}ller}, pages = {89--103}, tags = {SFB-TRR-62,Planning}, web_url = {http://link.springer.com/chapter/10.1007%2F978-3-642-34584-5_7} } @Inproceedings { Geier2011OnlineInference, author = {Geier, Thomas and Biundo, Susanne}, title = {Approximate Online Inference for Dynamic Markov Logic Networks}, abstract = {We examine the problem of filtering for dynamic probabilistic systems using Markov Logic Networks. We propose a method to approximately compute the marginal probabilities for the current state variables that is suitable for online inference. Contrary to existing algorithms, our approach does not work on the level of belief propagation, but can be used with every algorithm suitable for inference in Markov Logic Networks, such as MCSAT. We present an evaluation of its performance on two dynamic domains.}, year = {2011}, DOI = {10.1109/ICTAI.2011.120}, booktitle = {Proceedings of the 23rd IEEE International Conference on Tools with Artificial Intelligence (ICTAI)}, pages = {764--768}, keywords = {dmln, mln, dynamic, inference}, tags = {SFB-TRR-62, KnowledgeModeling}, web_url = {http://www.cse.fau.edu/ictai2011/}, web_url2 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6103411}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Geier11ApproxDMLNs.pdf} } @Incollection { Bidot2011AmbientEnvironments, author = {Bidot, Julien and Biundo, Susanne}, title = {Artificial Intelligence Planning for Ambient Environments}, abstract = {In this chapter, we describe how Artificial Intelligence planning techniques are used in The Adapted and TRusted Ambient eCOlogies (ATRACO) in order to provide Sphere Adaptation . We introduce the Planning Agent (PA) which plays a central role in the realization and the structural adaptation of activity spheres. Based on the particular information included in the ontology of the execution environment, the PA delivers workflows that consist of the basic activities to be executed in order to achieve a user’s goals. The PA encapsulates a search engine for hybrid planning{--}the combination of hierarchical task network (HTN) planning and partial-order causal-link (POCL) planning . In this chapter, we describe a formal framework and a development platform for hybrid planning, PANDA. This platform allows for the implementation of many search strategies, and we explain how we realize the search engine of the PA by adapting and configuring PANDA specifically for addressing planning problems that are part of the ATRACO service composition. We describe how the PA interacts with the Sphere Manager and the Ontology Manager in order to create planning problems dynamically and generate workflows in the ATRACO-BPEL language. In addition, an excerpt of a planning domain for ATRACO is provided.}, year = {2011}, DOI = {10.1007/978-3-319-23452-6_8}, booktitle = {Next Generation Intelligence Environments - Ambient Adaptive Systems}, edition = {1}, publisher = {Springer}, chapter = {6}, editor = {Tobias Heinroth and Wolfgang Minker}, pages = {195--225}, tags = {SFB-TRR-62,Planning} } @Inproceedings { Mueller2011HierarchicalFSCs, author = {M{\"u}ller, Felix and Biundo, Susanne}, title = {HTN-Style Planning in Relational POMDPs Using First-Order FSCs}, abstract = {n this paper, a novel approach to hierarchical planning under partial observability in relational domains is presented. It combines hierarchical task network planning with the finite state controller (FSC) policy representation for partially observable Markov decision processes. Based on a new first-order generalization of FSCs, action hierarchies are defined as in traditional hierarchical planning, so that planning corresponds to finding the best plan in a given decomposition hierarchy of predefined, partially abstract FSCs. Finally, we propose an algorithm for solving planning problems in this setting. Our approach offers a way of practically dealing with real-world partial observability planning problems: it avoids the complexity originating from the dynamic programming backup operation required in many present-day policy generation algorithms.}, year = {2011}, booktitle = {Proceedings of the 34th Annual German Conference on Artificial Intelligence (KI 2011)}, publisher = {Springer}, editor = {Joscha Bach and Stefan Edelkamp}, pages = {216--227}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.springerlink.com/content/g051ht236j73761m/}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/paper-hierarchicalFOFSCs.pdf} } @Inproceedings { Elkawkagy2011HybridMultiAgent2, author = {Elkawkagy, Mohamed and Biundo, Susanne}, title = {Hybrid Multi-agent Planning}, abstract = {Although several approaches have been constructed for multi-agent planning, solving large planning problems is still quite difficult. In this paper, we present a new approach that integrates landmark preprocessing technique in the context of hierarchical planning with multi-agent planning. Our approach uses Dependent and Independent clustering techniques to break up the planning problem into smaller clusters. These clusters are solved individually according to landmark information, then the obtained individual plans are merged according to the notion of fragments to generate a final solution plan. In hierarchical planning, landmarks are those tasks that occur in the decomposition refinements on every plan development path. Hierarchical landmark technique shows how a preprocessing step that extracts landmarks from a hierarchical planning domain and problem description can be used to prune the search space that is to be explored before actual search is performed. The methodologies in this paper have been implemented successfully, and we will present some experimental results that give evidence for the considerable performance increase gained through our system.}, year = {2011}, booktitle = {Proceedings of the of the Ninth German Conference on Multi-Agent System Technologies (MATES 2011)}, publisher = {IOS Press}, pages = {16--28}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Elkawkagy11HybridMultiAgentSlides.pdf}, web_url2 = {http://www.springerlink.com/content/e73066483x2j7502/}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Elkawkagy11HybridMultiAgent.pdf} } @Inproceedings { Bercher2011Preferences, author = {Bercher, Pascal and Biundo, Susanne}, title = {Hybrid Planning with Preferences Using a Heuristic for Partially Ordered Plans}, 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.}, year = {2011}, booktitle = {26th PuK Workshop {\dq}Planen, Scheduling und Konfigurieren, Entwerfen{\dq} (PuK 2011)}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Bercher11PreferencesSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Bercher11Preferences.pdf} } @Inproceedings { Elkawkagy2011LandmarkStrategies, author = {Elkawkagy, Mohamed and Bercher, Pascal and Schattenberg, Bernd and Biundo, Susanne}, title = {Landmark-Aware Strategies for Hierarchical Planning}, 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.}, year = {2011}, booktitle = {Workshop on Heuristics for Domain-independent Planning (HDIP 2011) at ICAPS 2011}, pages = {73--79}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Elkawkagy11LandmarkStrategiesSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Elkawkagy11LandmarkStrategies.pdf} } @Article { Biundo2011RealWorldPlanning, author = {Biundo, Susanne and Bidot, Julien and Schattenberg, Bernd}, title = {Planning in the Real World}, abstract = {In this article, we describe how real world planning problems can be solved by employing Artificial Intelligence planning techniques. We introduce the paradigm of hybrid planning, which is particularly suited for applications where plans are not intended to be automatically executed by systems, but are made for humans. Hybrid planning combines hierarchical planning {\\&}ndash; the stepwise refinement of complex tasks {\\&}ndash; with explicit reasoning about causal dependencies between actions, thereby reflecting exactly the kinds of reasoning humans perform when developing plans. We show how plans are generated and how failed plans are repaired in a way that guarantees stability. Our illustrating examples are taken from a domain model for disaster relief missions enforced upon extensive floods. Finally, we present a tool to support the challenging task of constructing planning domain models. The article ends with an overview of a wide varity of actual planning applications and outlines further such in the area of cognitive technical systems.}, year = {2011}, DOI = {10.1007/s00287-011-0562-7}, journal = {Informatik-Spektrum}, volume = {34}, pages = {443--454}, number = {5}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.springerlink.com/content/514981j48161127x/}, file_url = {http://www.springerlink.com/content/514981j48161127x/fulltext.pdf} } @Inproceedings { Schulz2011ReversalLearning, author = {Schulz, Andreas and Schattenberg, Bernd and Woldeit, Marie and Brechmann, Andr{\'e} and Biundo, Susanne and W. Ohl, Frank}, title = {Reinforcement learning and planning models for two-way-avoidance and reversal learning}, abstract = {The framework of reinforcement learning (RL), in particular temporal difference (TD) learning, is traditionally utilized to model Pavlovian and Instrumental Learning in animal and human subjects. Neurophysiological correlates model parameters, on the level of both single cells and fMRI data, support this approach ( Barto and Sutton 1998, Schulz 2001, Doya 2008). Notably, most of these models are applied to appetitive learning, as their nature demands that reinforcement is directly related to an action. In aversive learning this is not the case, at least not for directly observable actions of the animal. Therefore RL models of avoidance learning are studied only relatively recently (e.g. Moutoussis et al. 2008). The first aim of the present study was the investigation of RL models in the context of two-way avoidance and reversal learning. We used a well-established animal model for two-way avoidance, the Mongolian gerbil trained in a shuttle box Go/NoGo paradigm (Wetzel 1998; Ohl et al. 2001). We have extended the RL model of Moutoussis et al. and compared the results to the animal behavior.We also found, that Reinforcement Learning models can explain various aspects of two-way avoidance learning but do not provide a rationale for the relationship found between dynamics of initial learning and dynamics of reversal learning. However, the Artificial Intelligence (AI) paradigm of Automated Planning can provide a rationale for explaining such relationships. As the second aim of this study, we therefore modeled the avoidance learning by a Hybrid Planning ( Biundo and Schattenberg 2001) and plan repair approach (Bidot et al. 2008) and demonstrated that the empirically found relationships could be motivated from a consistent theoretical framework. The AI planning framework has the additional advantage over mere Reinforcement models to provide an explicit representation of and reasoning about {\\&}quot;internal{\\&}quot; processing stages.}, year = {2011}, booktitle = {Proceedings of the Annual Meeting of the Society For Neuroscience}, keywords = {avoidance,reinforcement learning, modeling}, tags = {SFB-TRR-62,Planning,KnowledgeModeling}, web_url = {http://www.abstractsonline.com/Plan/ViewAbstract.aspx?sKey=36dc39eb-9262-472e-9ee0-df4fc3c6abd5{\\&}cKey=f1c0c307-ad80-41c9-b32f-f5def2a643e0{\\&}mKey=%7b8334BE29-8911-4991-8C31-32B32DD5E6C8%7d} } @Article { Biundo2011CognitiveSystems, author = {Biundo, Susanne and Bercher, Pascal and Geier, Thomas and M{\"u}ller, Felix and Schattenberg, Bernd}, title = {Advanced user assistance based on AI planning}, abstract = {Artificial Intelligence technologies enable the implementation of cognitive systems with advanced planning and reasoning capabilities. This article presents an approach to use hybrid planning - a method that combines reasoning about procedural knowledge and causalities - to provide user-centered assistance.Based on a completely declarative description of actions, tasks, and solution methods, hybrid planning allows for the generation of knowledge-rich plans of action. The information those plans comprise includes causal dependencies between actions on both abstract and primitive levels as well as information about their hierarchical and temporal relationships.We present the hybrid planning approach in detail and show its potential by describing the realization of various assistance functionalities based on complex cognitive processes like the generation, repair, and explanation of plans. Advanced user assistance is demonstrated by means of a practical application scenario where an innovative electronic support mechanism helps a user to operate a complex mobile communication device.}, year = {2011}, issn = {1389--0417}, DOI = {10.1016/j.cogsys.2010.12.005}, journal = {Cognitive Systems Research}, volume = {12}, pages = {219--236}, number = {3-4}, keywords = {Cognitive technical systems, Companion-technology, Hybrid planning, Plan repair, Plan explanation, Real-world planning}, tags = {SFB-TRR-62,Planning}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Biundo11AdvancedUserAssistance.pdf}, note = {Special Issue on Complex Cognition} } @Inproceedings { Biundo2010Explanations, author = {Bidot, Julien and Biundo, Susanne and Heinroth, Tobias and Minker, Wolfgang and Nothdurft, Florian and Schattenberg, Bernd}, title = {Verbal Explanations for Hybrid Planning}, abstract = {State-of-the-art AI planning systems are able to generate complex plans thanks to their efficient reasoning engines. In a large number of application domains, the plans are automatically executed by systems such as autonomous robots. In this context, it is not necessary to make these automated systems understand what they are actually doing during execution and why they are doing that. In other words, these systems do not need to understand the underlying semantics of the plans they execute and how these plans have been generated. However, there are a significant number of key application domains, such as disaster relief mission support or project planning, where plans are supposed to be executed by a human user who is not necessarily a planning expert, an application expert, or both. In addition, for real-world applications, the plans and the plan generation are often complex. In order to unlock a part of the application potential of the AI planning technology, it is necessary that the user trusts the technology. Increasing trust in AI planning systems requires the design and implementation of user-friendly interfaces and the development of plan explanation methods that allow for taking into consideration the human user’s queries related to some components of the plan about their meaning and relevance for the plan and giving back the appropriate information that answers these queries. The verbal communication by speech constitutes the most natural form of communication for humans. By means of natural language dialogs in this work, we focus on the explanation of plans that are generated by a refinement-based planning system. Contrary to most approaches presented in the literature that try to provide explanations when backtracking occurs in failure situations during search, we assume in this work that the plans for which explanations are looked for are consistent. We present a domain-independent approach to enabling verbal human queries and producing verbal plan explanations.}, year = {2010}, booktitle = {Proceedings of the Conference {\dq}Multikonferenz Wirtschaftsinformatik{\dq} (MKWI 2010), Teilkonferenz {\\&}quot;Planen, Scheduling und Konfigurieren, Entwerfen{\\&}quot; (PuK 2010)}, publisher = {Universit{\"a}tsverlag G{\"o}ttingen}, editor = {Matthias Schumann and Lutz M. Kolbe and Michael H. Breitner and Arne Frerichs}, pages = {2309--2320}, tags = {SFB-TRR-62,Planning}, file_url = {http://webdoc.sub.gwdg.de/univerlag/2010/mkwi/03_anwendungen/planen_scheduling/06_verbal_plan_explanations_for_hybrid_plannings.pdf} } @Article { Biundo2010mpanionSysteme, author = {Biundo, Susanne and Wendemuth, Andreas}, title = {Von kognitiven technischen Systemen zu Companion-Systemen}, abstract = {Hoffnung, l{\"a}stige Routineaufgaben zu automatisieren, der unerw{\"u}nschten Informationsflut Herr zu werden, erw{\"u}nschte Informationen zu erhalten, zeitraubende Koordinations- und Kommunikationsaufgaben zu bew{\"a}ltigen und sich von langweiligen Alltagsentscheidungen entlasten zu k{\"o}nnen. Von Informationstechnik erhoffen sich viele Menschen {\\&}ndash; entsprechend dem Heinzelm{\"a}nnchenmotiv {\\&}ndash; eine umfassende Assistenz, die ihren Wunsch nach individueller Produktivit{\"a}t und pers{\"o}nlicher Bequemlichkeit in einem immer komplexer werdenden Alltag erf{\"u}llt. Der dadurch gewonnene Freiraum soll ihnen erm{\"o}glichen, sich auf die interessanten und wesentlichen Aufgaben zu konzentrieren. Sie wollen sich diesen Aufgaben ohne technische Einschr{\"a}nkung jederzeit und {\"u}berall widmen k{\"o}nnen. Die damit verbundene Zeitersparnis f{\"u}r delegierbare Arbeit soll es au{\"s}erdem erm{\"o}glichen, in signifikanter Weise Kosten einzusparen und Waren oder Dienstleistungen deutlich preisg{\"u}nstiger anzubieten}, year = {2010}, DOI = {10.1007/s13218-010-0056-9}, journal = {K{\"u}nstliche Intelligenz}, volume = {24}, pages = {335--339}, number = {4}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.springerlink.com/content/e558815w08k09531/}, file_url = {http://www.springerlink.com/content/e558815w08k09531/fulltext.pdf} } @Inproceedings { Elkawkagy10LandmarksInHTN, author = {Elkawkagy, Mohamed and Schattenberg, Bernd and Biundo, Susanne}, title = {Landmarks in Hierarchical Planning}, abstract = {In this paper we introduce a novel landmark technique for hierarchical planning. Landmarks are abstract tasks that are mandatory. They have to be performed by any solution plan. Our technique relies on a landmark extraction procedure that pre-processes a given planning problem by systematically analyzing the ways in which relevant abstract tasks can be decomposed. We show how the landmark information is used to guide hierarchical planning and present some experimental results that give evidence for the considerable performance increase gained through our technique.}, year = {2010}, booktitle = {Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010)}, publisher = {IOS Press}, pages = {229--234}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2010/Elkawkagy10LandmarksInHierarchicalSlides.pdf}, web_url2 = {http://www.booksonline.iospress.nl/Content/View.aspx?piid=17747}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2010/Elkawkagy10LandmarksInHierarchical.pdf} } @Inproceedings { Elkawkagy10LandmarksInHybrid, author = {Elkawkagy, Mohamed and Bercher, Pascal and Schattenberg, Bernd and Biundo, Susanne}, title = {Exploiting Landmarks for Hybrid Planning}, 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.}, year = {2010}, booktitle = {Proceedings of the 25th PuK Workshop {\\&}quot;Planen, Scheduling und Konfigurieren, Entwerfen{\\&}quot; (PuK 2010)}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2010/Elkawkagy10LandmarksInHybridSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2010/Elkawkagy10LandmarksInHybrid.pdf} } @Inproceedings { Schattenberg2009Framework, author = {Schattenberg, Bernd and Bidot, Julien and Ge{\"s}ler, Sascha and Biundo, Susanne}, title = {A Framework for Interactive Hybrid Planning}, abstract = {Hybrid planning, the integration of hierarchical task decomposition and partial-order planning, provides a powerful mechanism to solve real-world planning problems. We present a domain-independent, mixed-initiative approach to plan generation that is based on a formal concept of hybrid planning. It allows for any interaction modalities and models of initiative while preserving the soundness of the plan generation process. Adequately involving the decision competences of end-users this way will improve the application potential as well as the acceptance of the technology.}, year = {2009}, isbn = {978-3-642-04616-2}, DOI = {10.1007/978-3-642-04617-9_3}, booktitle = {Proceedings of the 32nd Annual German Conference on Artificial Intelligence (KI 2009)}, volume = {5803}, publisher = {Springer}, series = {LNAI 5803}, pages = {17--24}, tags = {Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2009/Schattenberg2009FrameworkSlides.pdf}, web_url2 = {http://www.springerlink.com/content/v3171u800470815r/}, file_url = {http://www.springerlink.com/content/v3171u800470815r/fulltext.pdf} } @Inproceedings { Bidot2008PlanRepair, author = {Bidot, Julien and Biundo, Susanne and Schattenberg, Bernd}, title = {Plan Repair in Hybrid Planning}, abstract = {Hybrid Planning, the integration of hierarchical task decomposition and partial-order-causal-link planning provides a powerful mechanism to solve real-world planning problems. While the generation of hybrid plans is well understood, the problem of how to adequately deal with the various types of execution failures in this context has not yet been addressed. We present a domain-independent approach to plan repair in hybrid planning. It exploits the generation process of the failed plan by retracting decisions that led to the failed plan fragments. They are selectively replaced by suitable alternatives, and the repaired plan is completed by following the previous generation process as close as possible. This way, a stable solution is obtained, i.e. a repair of the failed plan that causes minimal perturbation. We show how plan repair fits into a formal framework for hybrid planning and present a generic refinement-retraction-and-repair algorithm.}, year = {2008}, DOI = {10.1007/978-3-540-85845-4_21}, booktitle = {Proceedings of the 31st Annual German Conference on Artificial Intelligence (KI 2008)}, volume = {5243}, publisher = {Springer}, series = {Lecture Notes in Artificial Intelligence}, editor = {Andreas Dengel and Karsten Berns and Thomas Breuel and Frank Bomarius and Thomas R. Roth-Berghofer}, pages = {169--176}, tags = {Planning}, web_url = {http://www.springerlink.com/content/7h142500k7211717/}, file_url = {http://www.springerlink.com/content/7h142500k7211717/fulltext.pdf} } @Inproceedings { Schattenberg2007UnifyingFramework, author = {Schattenberg, Bernd and Biundo, Susanne}, title = {A Unifying Framework For Hybrid Planning And Scheduling}, abstract = {Many real-world application domains that demand planning and scheduling support do not allow for a clear separation of these capabilities. Typically, an adequate mixture of both methodologies is required, since some aspects of the underlying planning problem imply consequences on the scheduling part and vice versa. Several integration efforts have been undertaken to couple planning and scheduling methods, most of them using separate planning and scheduling components which iteratively exchange partial solutions until both agree on a result. This paper presents a framework that provides a uniform integration of hybrid planning {\\&}ndash;the combination of operator based partial order planning and abstraction based hierarchical task network planning{\\&}ndash; and a hierarchical scheduling approach. It is based on a proper formal account of refinement planning, which allows for the formal definition of hybrid planning, scheduling, and search strategies. In a first step, the scheduling functionality is used to produce plans that comply with time restrictions and resource bounds. We show how the resulting framework is thereby able to perform novel kinds of search strategies that opportunistically interleave what used to be separate planning and scheduling processes.}, year = {2007}, DOI = {10.1007/978-3-540-69912-5_27}, booktitle = {Advances in Artificial Intelligence, Proceedings of the 29th German Conference on Artificial Intelligence (KI 2006)}, volume = {4314}, publisher = {Springer}, series = {Lecture Notes in Artificial Intelligence}, editor = {Christian Freksa and Michael Kohlhase and Kerstin Schill}, pages = {361--373}, tags = {Planning}, web_url = {http://www.springerlink.com/content/3821231298565uk3/}, file_url = {http://www.springerlink.com/content/3821231298565uk3/fulltext.pdf} } @Inproceedings { Schattenberg2007FlexibleStrategies, author = {Schattenberg, Bernd and Bidot, Julien and Biundo, Susanne}, title = {On the Construction and Evaluation of Flexible Plan-Refinement Strategies}, abstract = {This paper describes a system for the systematic construction and evaluation of planning strategies. It is based on a proper formal account of refinement planning and allows to decouple plan-deficiency detection, refinement computation, and search control. In adopting this methodology, planning strategies can be explicitly described and easily deployed in various system configurations. We introduce novel domain-independent planning strategies that are applicable to a wide range of planning capabilities and methods. These so-called HotSpot strategies are guided by information about current plan defects and solution options. The results of a first empirical performance evaluation are presented in the context of hybrid planning.}, year = {2007}, DOI = {10.1007/978-3-540-74565-5_28}, booktitle = {Advances in Artificial Intelligence, Proceedings of the 30th German Conference on Artificial Intelligence (KI 2007)}, volume = {4667}, publisher = {Springer}, address = {Osnabr{\"u}ck, Germany}, series = {Lecture Notes in Artificial Intelligence}, editor = {Joachim Hertzberg and Michael Beetz and Roman Englert}, pages = {367--381}, tags = {Planning}, web_url = {http://www.springerlink.com/content/lx1l87180v450468/}, file_url = {http://www.springerlink.com/content/lx1l87180v450468/fulltext.pdf} } @Article { Schattenberg07HybridSoftware, author = {Schattenberg, Bernd and Balzer, Steffen and Biundo, Susanne}, title = {Realizing Hybrid Planning Systems as Modern Software Environments}, abstract = {We present an architecture for planning and scheduling systems that addresses key requirements of real-world applications in a unique manner. It provides a robust, scalable, and flexible framework through the use of industrialstrength middleware and multi-agent technology. The architectural concepts extend knowledge-based components that dynamically perform and verify the system’s configuration; standardized components and communication protocols allow a seamless integration with third-party libraries and application environments. The system is based on a proper formal account of hybrid planning, the integration of HTN and POCL planning. The framework allows to decouple the detection of plan flaws, the computation of plan modifications, and search control. Consequently, planning and scheduling capabilities can be easily combined by orchestrating respective elementary modules and strategies. This platform can implement and evaluate various configurations of planning methods and strategies, without jeopardizing system consistency through interfering module activity.}, year = {2007}, journal = {K{\"u}nstliche Intelligenz}, volume = {21}, pages = {16--22}, number = {1}, web_url = {http://www.kuenstliche-intelligenz.de/archives/ki-journal-20160917/index.php-id=7754{\\&}tx_ki_pi1[showUid]=1248{\\&}cHash=6d9424bc18.html}, file_url = {http://www.kuenstliche-intelligenz.de/archives/ki-journal-20160917/fileadmin/template/main/archiv/2007_1/realizing-schattenberg-web.pdf} } @Inproceedings { Schattenberg06KnowledgeBasedMiddleware, author = {Schattenberg, Bernd and Balzer, Steffen and Biundo, Susanne}, title = {Knowledge-based Middleware as an Architecture for Planning and Scheduling Systems}, abstract = {We present an architecture that provides a robust, scalable and flexible software framework for planning and scheduling systems through the use of standardized industrial-strength middleware and multi-agent technology. It utilizes knowledgebased components that dynamically perform and verify the system's configuration. The system is based on a proper formal account of hybrid planning, the integration of HTN and POCL planning, which allows to decouple flaw detection, modification computation,and search control. In adopting this methodology, planning and scheduling capabilities can be easily combined by orchestrating respective elementary modules and strategies without jeopardizing system consistency through interfering module activity.}, year = {2006}, booktitle = {Proceedings of the 16th International Conference on Automated Planning and Scheduling (ICAPS 2006)}, publisher = {AAAI Press}, address = {Ambleside, The English Lake District, UK}, editor = {Derek Long and Stephen F. Smith and Daniel Borrajo and Thomas Lee McCluskey}, pages = {422--425}, tags = {Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2006/Schattenberg06KnowledgeBasedMiddleware.pdf} } @Inproceedings { Schattenberg2006WebTechnology, author = {Schattenberg, Bernd and Balzer, Steffen and Biundo, Susanne}, title = {Semantic Web Technology as a Basis for Planning and Scheduling Systems}, abstract = {This paper presents an architecture for planning and scheduling systems that addresses key requirements of real-world applications in a unique manner. The system provides a robust, scalable and flexible framework for planning and scheduling software through the use of industrial-strength middleware and multi-agent technology. The architectural concepts extend knowledge-based components that dynamically perform and verify the system's configuration. The use of standardized components and communication protocols allows a seamless integration with third-party libraries and existing application environments. The system is based on a proper formal account of hybrid planning, the integration of HTN and POCL planning. The theoretical framework allows to decouple flaw detection, modification computation, and search control. In adopting this methodology, planning and scheduling capabilities can be easily combined by orchestrating respective elementary modules and strategies. The conceptual platform can be used to implement and evaluate various configurations of planning methods and strategies, without jeopardizing system consistency through interfering module activity.}, year = {2006}, booktitle = {Proceedings of the 20th Workshop Planen und Konfigurieren´´ (PuK 2006)}, address = {University of Bremen}, editor = {J{\"u}rgen Sauer}, pages = {26--36}, tags = {Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2006/Schattenberg2006WebTechnologySlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2006/Schattenberg2006WebTechnology.pdf} } @Inproceedings { Schattenberg05FlexibleStrategies, author = {Schattenberg, Bernd and Weigl, Andreas and Biundo, Susanne}, title = {Hybrid Planning Using Flexible Strategies}, abstract = {In this paper we present a highly modular planning system architecture. It is based on a proper formal account of hybrid planning, which allows for the formal definition of (flexible) planning strategies. Groups of modules for flaw detection and plan refinement provide the basic functionalities of a planning system. The concept of explicit strategy modules serves to formulate and implement strategies that orchestrate the basic modules. This way a variety of fixed plan generation procedures as well as novel flexible planning strategies can easily be implemented and evaluated. We present a number of such strategies and show some first comparative performance results.}, year = {2005}, isbn = {3-540-28761-2}, DOI = {10.1007/10.1007/11551263_21}, booktitle = {Advances in Artificial Intelligence, Proceedings of the 28th German Conference on Artificial Intelligence (KI 2005)}, volume = {3698}, publisher = {Springer-Verlag Berlin Heidelberg}, series = {Lecture Notes in Artificial Intelligence}, pages = {249--263}, tags = {Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2005/Schattenberg05FlexibleStrategiesSlides.pdf}, web_url2 = {http://www.springerlink.com/content/ab18236tekp4wvfu/}, file_url = {http://www.springerlink.com/content/ab18236tekp4wvfu/fulltext.pdf} } @Incollection { Biundo05PlanningUnderTemporalUncertainty, author = {Biundo, Susanne and Holzer, Roland and Schattenberg, Bernd}, title = {Project Planning Under Temporal Uncertainty}, abstract = {This paper presents an approach towards probabilistic planning with continuous time. It adopts stochastic concepts for continuous probabilities and integrates them into an HTN-based planning framework. Based on uncertain time durations associated with primitive tasks the time consumption probabilities of non-linear plans can be accumulated and thus an overall probability for a successful execution of complex plans can be computed. Furthermore, heuristics for the decomposition of abstract tasks can be derived that guide the search towards plans with a minimized average value/variance of their overall time consumption. An example from software project planning is used to demonstrate our approach.}, year = {2005}, booktitle = {Planning, Scheduling, and Constraint Satisfaction: From Theory to Practice}, volume = {117}, publisher = {IOS Press}, series = {Frontiers in Artificial Intelligence and Applications}, editor = {Luis A. Castillo and Daniel Borrajo and Miguel A. Salido and Angelo Oddi}, pages = {189--198}, tags = {Planning}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2004/Biundo04ProjectPlanning.pdf} } @Inproceedings { Biundo04ContinuousResources, author = {Biundo, Susanne and Holzer, Roland and Schattenberg, Bernd}, title = {Dealing with Continuous Resources in AI Planning}, abstract = {This paper presents an approach towards probabilistic planning with continuous resources. It adopts stochastic concepts for continuous probabilities and integrates them into a STRIPS-based planning framework. The approach enables the construction of plans that are guaranteed to meet certain probability thresholds w.r.t. the consumption of critical resources. Furthermore, the consumption probabilities of multiple resources can be accumulated and thus an overall probability for a successful execution of an aggregate plan can be computed. We extend our approach to HTN-based planning and show how heuristics can be derived that lead to plans with a minimized average value/variance of their overallresource consumption.}, year = {2004}, booktitle = {Proceedings of the 4th International Workshop on Planning and Scheduling for Space (IWPSS 2004)}, publisher = {European Space Agency Publications Division}, address = {ESA-ESOC, Darmstadt, Germany}, pages = {213--218}, number = {WPP-228}, tags = {Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2004/Biundo04ContinuousResources.pdf} } @Inproceedings { Biundo04ProjectPlanning, author = {Biundo, Susanne and Holzer, Roland and Schattenberg, Bernd}, title = {Project Planning Under Temporal Uncertainty}, abstract = {This paper presents an approach towards probabilistic planning with continuous time. It adopts stochastic concepts for continuous probabilities and integrates them into an HTN-based planning framework. Based on uncertain time durations associated with primitive tasks the time consumption probabilities of non-linear plans can be accumulated and thus an overall probability for a successful execution of complex plans can be computed. Furthermore, heuristics for the decomposition of abstract tasks can be derived that guide the search towards plans with a minimized average value/variance of their overall time consumption. An example from software project planning is used to demonstrate our approach.}, year = {2004}, booktitle = {Proceedings of the Workshop on Planning and Scheduling: Bridging Theory to Practice at The 16th European Conference on Artificial Intelligence (ECAI 2004)}, tags = {Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2004/Biundo04ProjectPlanningSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2004/Biundo04ProjectPlanning.pdf} } @Inproceedings { Schattenberg02HierarchicalResources, author = {Schattenberg, Bernd and Biundo, Susanne}, title = {On the Identification and Use of Hierarchical Resources in Planning and Scheduling}, abstract = {Many real-world planning applications have to deal with resource allocation problems, and so does planning in the domain of crisis management assistance. In order to support resource allocation in these kind of applications, we present a new approach to the integration of scheduling capabilities and planning. The proposed methodology relies on a hybrid planner, which combines action and state abstraction by integrating hierarchical task network (HTN) planning and state based partial order causal link (POCL) planning into a common framework. We extend the abstraction mechanism of the planner to different kinds of abstraction for resources, namely subsumption, approximation, qualification, and aggregation. We show how these abstractions can be used when modeling the domain and how reasoning about resources can be performed in a flexible way, namely by merging opportunistic planning and scheduling strategies.}, year = {2002}, booktitle = {Proceedings of the 6th International Conference on Artificial Intelligence Planning Systems (AIPS 2002)}, publisher = {AAAI Press}, pages = {263--272}, tags = {Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2002/Schattenberg02HierarchicalResourcesSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2002/Schattenberg02HierarchicalResources.pdf} } @Inproceedings { Biundo01FromCrisisToRelief, author = {Biundo, Susanne and Schattenberg, Bernd}, title = {From Abstract Crisis to Concrete Relief (A Preliminary Report on Combining State Abstraction and HTN Planning)}, abstract = {Flexible support for crisis management can definitely be improved by making use of advanced planning capabilities. However, the complexity of the underlying domain often causes intractable efforts in modeling the domain as well as a huge search space to be explored by the system. A way to overcome these problems is to impose a structure not only according to tasks but also according to relationships between and properties of the objects involved, thereby using so-called decomposition axioms. We outline the prototype of a system that is capable of tackling planning for complex application domains. It is based on a well-founded combination of action and state abstractions. The paper presents the basic techniques and provides a formal semantic foundation of the approach. It introduces the planning system and illustrates its underlying principles by examples taken from the crisis management domain used in our ongoing project.}, year = {2001}, booktitle = {Proceedings of the 6th European Conference on Planning (ECP 2001)}, publisher = {AAAI Press}, pages = {157--168}, tags = {Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2001/Biundo01FromCrisisToReliefSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2001/Biundo01FromCrisisToRelief.pdf} }

## Publications

% % This file was created by the TYPO3 extension % publications % --- Timezone: CEST % Creation date: 2022-11-27 % Creation time: 00:00:35 % --- Number of references % 109 % @Article { Bercher2021DIY, author = {Bercher, Pascal and Behnke, Gregor and Kraus, Matthias and Schiller, Marvin R. G. and Manstetten, Dietrich and Dambier, Michael and Dorna, Michael and Minker, Wolfgang and Glimm, Birte and Biundo, Susanne}, title = {Do It Yourself, but Not Alone: Companion-Technology for Home Improvement {\\&}ndash; Bringing a Planning-Based Interactive DIY Assistant to Life}, abstract = {We report on the technology transfer project “Do it yourself, but not alone: Companion-Technology for Home Improvement” that was carried out by Ulm University in cooperation with Robert Bosch GmbH. We developed a prototypical assistance system that assists a Do It Yourself (DIY) handyman in carrying out DIY projects. The assistant, based on various AI and dialog management capabilities, generates a sequence of detailed instructions that users may just follow or adapt according to their individual preferences. It features explanation capabilities as well as pro-active support based on communication with the user as well as with the involved tools. We report on the project’s main achievements, including the findings of various empirical studies conducted in various development stages of the prototype.}, year = {2021}, journal = {K{\"u}nstliche Intelligenz {\\&}ndash; Special Issue on NLP and Semantics}, web_url2 = {https://rdcu.be/cmGwb}, file_url = {http://link.springer.com/article/10.1007/s13218-021-00721-x} } @Inproceedings { Olz21RevealingEffects, author = {Olz, Conny and Biundo, Susanne and Bercher, Pascal}, title = {Revealing Hidden Preconditions and Effects of Compound HTN Planning Tasks {\\&}ndash; A Complexity Analysis}, year = {2021}, booktitle = {Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021)}, publisher = {AAAI Press}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2021/Olz21CompoundEffects.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} } @Article { 180186415662_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 { Behnke2020DIYAssistant, author = {Behnke, Gregor and Bercher, Pascal and Kraus, Matthias and Schiller, Marvin R. G. and Mickeleit, Kristof and H{\"a}ge, Timo and Dorna, Michael and Dambier, Michael and Minker, Wolfgang and Glimm, Birte and Biundo, Susanne}, title = {New Developments for Robert {\\&}ndash; Assisting Novice Users Even Better in DIY Projects}, year = {2020}, booktitle = {Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS 2020)}, publisher = {AAAI Press}, pages = {343--347}, keywords = {SFB-T3,Planning}, tags = {SFB-T3,Planning,KnowledgeModelling}, web_url = {https://aaai.org/ojs/index.php/ICAPS/article/view/6679/6533 - - {\dq}Link to the AAAI Paper Version{\dq}}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2020/Behnke2020DIYAssistant.pdf} } @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 { Kraus2020ICMI, author = {Kraus, Matthias and Schiller, Marvin R. G. and Behnke, Gregor and Bercher, Pascal and Dorna, Michael and Dambier, Michael and Glimm, Birte and Biundo, Susanne and Minker, Wolfgang}, title = {Was that successful? On Integrating Proactive Meta-Dialogue in a DIY-Assistant System using Multimodal Cues}, abstract = {Effectively supporting novices during performance of complex tasks, e.g. do-it-yourself (DIY) projects, requires intelligent assistants to be more than mere instructors. In order to be accepted as a competent and trustworthy cooperation partner, they need to be able to actively participate in the project and engage in helpful conversations with users when assistance is necessary. Therefore, a new proactive version of the DIY-assistant \textsc{Robert} is presented in this paper. It extends the previous prototype by including the capability to initiate reflective meta-dialogues using multimodal cues. Two different strategies for reflective dialogue are implemented: A progress-based strategy initiates a reflective dialogue about previous experience with the assistance for encouraging the self-appraisal of the user. An activity-based strategy is applied for providing timely, task-dependent support. Therefore, user activities with a connected drill driver are tracked that trigger dialogues in order to reflect on the current task and to prevent task failure. An experimental study comparing the proactive assistant against the baseline version shows that proactive meta-dialogue is able to build user trust significantly better than a solely reactive system. Besides, the results provide interesting insights for the development of proactive dialogue assistants.}, year = {2020}, booktitle = {Proceedings of 22nd ACM International Conference on Multimodal Interaction (ICMI 2020)}, publisher = {ACM}, tags = {SFB-T3}, web_url = {https://dl.acm.org/doi/pdf/10.1145/3382507.3418818 - - {\dq}Link to the Conference Paper{\dq}}, file_url = {t3://file?uid=431053} } @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} } @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 { 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 { 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 { 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 {\\&}ndash; much more important {\\&}ndash; 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 { 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 { 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} } @Article { Behnke2019bosch, author = {Behnke, Gregor and Schiller, Marvin R. G. and Kraus, Matthias and Bercher, Pascal and Schmautz, Mario and Dorna, Michael and Dambier, Michael and Minker, Wolfgang and Glimm, Birte and Biundo, Susanne}, title = {Alice in DIY wonderland or: Instructing novice users on how to use tools in DIY projects}, abstract = {We present the interactive assistant Robert that provides situation-adaptive support in the realisation of do-it-yourself (DIY) home improvement projects. Robert assists its users by providing comprehensive step-by-step instructions for completing the DIY project. Each instruction is illustrated with detailed graphics, written and spoken text, as well as with videos. They explain how the steps of the project have to be prepared and assembled and give precise instructions on how to operate the required electric devices. The step-by-step instructions are generated by a hierarchical planner, which enables Robert to adapt to a multitude of environments easily. Parts of the underlying model are derived from an ontology storing information about the available devices and resources. A dialogue manager capable of natural language interaction is responsible for hands-free interaction. We explain the required background technology and present preliminary results of an empirical evaluation.}, year = {2019}, DOI = {10.3233/AIC-180604}, journal = {AI Communications}, volume = {32}, publisher = {IOS Press}, pages = {31-57}, number = {1}, tags = {SFB-T3,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2019/Behnke2019bosch.pdf}, note = {The final publication is available at IOS Press through http://dx.doi.org/10.3233/AIC-180604}, annotation = {The final publication is available at IOS Press through http://dx.doi.org/10.3233/AIC-180604} } @Inbook { Kraus2019CloudCompanion, author = {Kraus, Matthias and Schiller, Marvin R. G. and Behnke, Gregor and Bercher, Pascal and Biundo, Susanne and Glimm, Birte and Minker, Wolfgang}, title = {9th International Workshop on Spoken Dialogue Systems}, abstract = {Companion systems are cooperative, cognitive systems aiming at assist-ing a user in everyday situations. Therefore, these systems require a high level ofavailability. One option to meet this requirement is to use a web-deployable archi-tecture. In this demo paper, we present a multimodal cloud-based dialogue frame-work for the development of a distributed, web-based companion system. The pro-posed framework is intended to provide an efficient, easily extensible, and scalableapproach for these kinds of systems and will be demonstrated in a do-it-yourselfassistance scenario.}, year = {2019}, publisher = {Springer}, chapter = {A Multimodal Dialogue Framework for Cloud-Based Companion Systems}, series = {Lecture Notes in Electrical Engineering}, editor = {Rafael Banchs and Luis Fernando D'Haro and Haizhou Li}, tags = {SFB-T3,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2019/Kraus2019CloudCompanion.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} } @Article { Behnke2018SATltljournal, author = {Behnke, Gregor and Biundo, Susanne}, title = {X and more Parallelism: Integrating LTL-Next into SAT-based Planning with Trajectory Constraints While Allowing for Even More Parallelism}, year = {2018}, DOI = {10.4114/intartif.vol21iss62pp75-90}, journal = {Inteligencia Artificial}, volume = {21}, pages = {75--90}, number = {62}, tags = {SFB-T3}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2018/Behnke2018SATltljournal.pdf} } @Inproceedings { Behnke2018MoreParallelLTL, author = {Behnke, Gregor and Biundo, Susanne}, title = {X and more Parallelism - Integrating LTL-Next into SAT-based Planning with Trajectory Constraints while Allowing for even more Parallelism}, abstract = {Linear temporal logic (LTL) provides expressive means to specify temporally extended goals as well as preferences. Recent research has focussed on compilation techniques, i.e., methods to alter the domain ensuring that every solution adheres to the temporally extended goals. This requires either new actions or an construction that is exponential in the size of the formula. A translation into boolean satisfiability (SAT) on the other hand requires neither. So far only one such encoding exists, which is based on the parallel ∃-step encoding for classical planning. We show a connection between it and recently developed compilation techniques for LTL, which may be exploited in the future. The major drawback of the encoding is that it is limited to LTL without the X operator. We show how to integrate X and describe two new encodings, which allow for more parallelism than the original encoding. An empirical evaluation shows that the new encodings outperform the current state-of-the-art encoding.}, year = {2018}, booktitle = {Proceedings of the Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems (COPLAS)}, pages = {1--10}, tags = {SFB-T3}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2018/Behnke2018satltl.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 {\dq}Technische Unterst{\"u}tzungssysteme, die die Menschen wirklich wollen{\dq} (engl: Proceedings of the 3rd {\dq}Transdisciplinary 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.} } @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} } @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 { 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 { 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 { 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} } @Inproceedings { Behnke2018HomeImprovementSystem, author = {Behnke, Gregor and Schiller, Marvin R. G. and Kraus, Matthias and Bercher, Pascal and Schmautz, Mario and Dorna, Michael and Minker, Wolfgang and Glimm, Birte and Biundo, Susanne}, title = {Instructing Novice Users on How to Use Tools in DIY Projects}, abstract = {Novice users require assistance when performing handicraft tasks. Adequate instruction ensures task completion and conveys knowledge and abilities required to perform the task. We present an assistant teaching novice users how to operate electronic tools, such as drills, saws, and sanders, in the context of Do-It-Yourself (DIY) home improvement projects. First, the actions that need to be performed for the project are determined by a planner. Second, a dialogue manager capable of natural language interaction presents these actions as instructions to the user. Third, questions on these actions and involved objects are answered by generating appropriate ontology-based explanations.}, year = {2018}, DOI = {10.24963/ijcai.2018/844}, booktitle = {Proceedings of the 27th International Joint Conference on Artificial Intelligence and the 23rd European Conference on Artificial Intelligence (IJCAI-ECAI 2018)}, publisher = {IJCAI}, pages = {5805--5807}, tags = {SFB-T3}, web_url = {www.ijcai.org}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2018/Behnke2018DIY.pdf} } @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 showingthe complete picture{\\&}quot; 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 { 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} } @Inproceedings { Kraus2018CompanionCloudDemo, author = {Kraus, Matthias and Behnke, Gregor and Bercher, Pascal and Schiller, Marvin R. G. and Biundo, Susanne and Glimm, Birte and Minker, Wolfgang}, title = {A Multimodal Dialogue Framework for Cloud-Based Companion Systems}, abstract = {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.}, year = {2018}, booktitle = {Proc. of the 10th International Workshop on Spoken Dialog Systems Technology (IWSDS 2018)}, tags = {SFB-TRR-62,SFB-T3,Planning,KnowledgeModeling}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2018/Kraus2018CompanionCloudDemo.pdf} } @Inproceedings { schillerEtAlMCI2018, author = {Schiller, Marvin R. G. and Behnke, Gregor and Bercher, Pascal 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}, 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 {\\&}ndash; if necessary {\\&}ndash; 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.}, year = {2018}, booktitle = {Proceedings of MCI Workshop {\dq}Digital Companion{\dq}}, pages = {925--930}, tags = {SFB-TRR-62,SFB-T3}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2018/MCI-WS19-schillerEtAl2018.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} } @Inbook { Hoernle2017CompBookReferenceArchitecture, author = {H{\"o}rnle, Thilo and Tornow, Michael and Honold, Frank and Schwegler, Reinhard and Heinemann, Ralph and Biundo, Susanne and Wendemuth, Andreas}, title = {Companion-Systems: A Reference Architecture}, abstract = {Companion-Technology for cognitive technical systems consists of a multitude of components that implement different properties. A primary point is the architecture which is responsible for the interoperability of all components. It defines the capabilities of the systems crucially. For research concerning the requirements and effects of the architecture, several demonstration scenarios were developed. Each of these demonstration scenarios focuses on some aspects of a Companion-System. For the implementation a middleware concept was used, having the capability to realize the major part of the Companion-Systems. Currently the system architecture takes up only a minor property in projects which are working on related research topics. For the description of an architecture representing the major part of possible Companion-Systems, the demonstration scenarios are studied with regard to their system structure and the constituting components. A monolithic architecture enables a simple system design and fast direct connections between the components, such as: sensors with their processing and fusion components, knowledge bases, planning components, dialog systems and interaction components. Herein, only a limited number of possible Companion-Systems can be represented. In a principled approach, a dynamic architecture, capable of including new components during run time, is able to represent almost all Companion-Systems. Furthermore, an approach for enhancing the architecture is introduced.}, year = {2017}, DOI = {10.1007/978-3-319-43665-4_22}, booktitle = {Companion Technology -- A Paradigm Shift in Human-Technology Interaction}, publisher = {Springer}, chapter = {22}, series = {Cognitive Technologies}, editor = {Susanne Biundo and Andreas Wendemuth}, pages = {449-469}, keywords = {SFB-TRR-62}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/Hoernle2017CompBookReferenceArchitecture.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 {\\&}ndash; 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} } @Inbook { Behnke2017CompBookMIP, author = {Behnke, Gregor and Nielsen, Florian and Schiller, Marvin R. G. and Ponomaryov, Denis and Bercher, Pascal and Glimm, Birte and Minker, Wolfgang and Biundo, Susanne}, title = {To Plan for the User Is to Plan With the User -- Integrating User Interaction Into the Planning Process}, abstract = {Settings where systems and users work together to solve problems collaboratively are among the most challenging applications of Companion-Technology. So far we have seen how planning technology can be exploited to realize Companion-Systems that adapt flexibly to changes in the user’s situation and environment and provide detailed help for users to realize their goals. However, such systems lack the capability to generate their plans in cooperation with the user. In this chapter we go one step further and describe how to involve the user directly into the planning process. This enables users to integrate their wishes and preferences into plans and helps the system to produce individual plans, which in turn let the Companion-System gain acceptance and trust from the user. Such a Companion-System must be able to manage diverse interactions with a human user. A so-called mixed-initiative planning system integrates several Companion-Technologies which are described in this chapter. For example, a{--}not yet final{--}plan, including its flaws and solutions, must be presented to the user to provide a basis for her or his decision. We describe how a dialog manager can be constructed such that it can handle all communication with a user. Naturally, the dialog manager and the planner must use coherent models. We show how an ontology can be exploited to achieve such models. Finally, we show how the causal information included in plans can be used to answer the questions a user might have about a plan. The given capabilities of a system to integrate user decisions and to explain its own decisions to the user in an appropriate way are essential for systems that interact with human users.}, year = {2017}, DOI = {10.1007/978-3-319-43665-4_7}, booktitle = {Companion Technology -- A Paradigm Shift in Human-Technology Interaction}, publisher = {Springer}, chapter = {7}, series = {Cognitive Technologies}, editor = {Susanne Biundo and Andreas Wendemuth}, pages = {123--144}, tags = {SFB-TRR-62,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/Behnke2017CompBookMIP.pdf} } @Inproceedings { Behnke2017Sloth, author = {Behnke, Gregor and Nielsen, Florian and Schiller, Marvin R. G. and Bercher, Pascal and Kraus, Matthias and Minker, Wolfgang and Biundo, Susanne and Glimm, Birte}, title = {SLOTH - the Interactive Workout Planner}, abstract = {We present the mixed-initiative planning system SLOTH, which is designed to assist users in planning a fitness workout. Mixed-initiative planning systems are especially useful for companion systems, as they allow the seamless integration of the complex cognitive ability of planning into ambient assistance systems. This is achieved by integrating the user directly into the process of plan generation and thereby allowing him to specify these objectives and to be assisted in generating a plan that not only achieves his objectives, but at the same time also fits his preferences. We present the capabilities that are integrated into SLOTH and discuss the design choices and considerata that have to be taken into account when constructing a mixed-initiative planning system.}, year = {2017}, DOI = {10.1109/COMPANION.2017.8287077}, booktitle = {Proceedings of the 2nd International Conference on Companion Technology (ICCT 2017)}, publisher = {IEEE}, tags = {SFB-TRR-62,Planning}, web_url = {http://ieeexplore.ieee.org/document/8287077/}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/Behnke2017Sloth.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 { 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 {\\&}ndash; until now {\\&}ndash; 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} } @Book { Biundo2017ParadigmShift, author = {Biundo, Susanne and Wendemuth, Andreas}, title = {Companion Technology - A Paradigm Shift in Human-Technology Interaction}, abstract = {Future technical systems will be companion systems, competent assistants that provide their functionality in a completely individualized way, adapting to a user’s capabilities, preferences, requirements, and current needs, and taking into account both the emotional state and the situation of the individual user. This book presents the enabling technology for such systems. It introduces a variety of methods and techniques to implement an individualized, adaptive, flexible, and robust behavior for technical systems by means of cognitive processes, including perception, cognition, interaction, planning, and reasoning. The technological developments are complemented by empirical studies from psychological and neurobiological perspectives.}, year = {2017}, DOI = {10.1007/978-3-319-43665-4}, publisher = {Springer}, editor = {Susanne Biundo and Andreas Wendemuth}, keywords = {Companion Systems, Cognitive Systems, Artificial Intelligence (AI), Automated Planning, Knowledge Representation (KR), Human-Computer Interaction (HCI), Multimodal Interaction, Dialogue Management, Emotion Recognition, Information Fusion}, tags = {SFB-TRR-62,Planning}, web_url = {https://link.springer.com/book/10.1007/978-3-319-43665-4}, file_url = {https://link.springer.com/book/10.1007/978-3-319-43665-4} } @Inbook { Richter2017UserCenteredPlanningUnderUncertainty, author = {Richter, Felix and Biundo, Susanne}, title = {Addressing Uncertainty in Hierarchical User-Centered Planning}, abstract = {Companion-Systems need to reason about dynamic properties of their users, e.g., their emotional state, and the current state of the environment. The values of these properties are often not directly accessible; hence information on them must be pieced together from indirect, noisy or partial observations. To ensure probability-based treatment of partial observability on the planning level, planning problems can be modeled as Partially Observable Markov Decision Processes (POMDPs). While POMDPs can model relevant planning problems, it is algorithmically difficult to solve them. A starting point for mitigating this is that many domains exhibit hierarchical structures where plans consist of a number of higher-level activities, each of which can be implemented in different ways that are known a priori. We show how to make use of such structures in POMDPs using the Partially Observable HTN (POHTN) planning approach by developing a Partially Observable HTN (POHTN) action hierarchy for an example domain derived from an existing deterministic demonstration domain. We then apply Monte-Carlo Tree Search to POHTNs for generating plans and evaluate both the developed domain and the POHTN approach empirically.}, year = {2017}, DOI = {10.1007/978-3-319-43665-4_6}, booktitle = {Companion Technology -- A Paradigm Shift in Human-Technology Interaction}, publisher = {Springer}, chapter = {6}, series = {Cognitive Technologies}, editor = {Susanne Biundo and Andreas Wendemuth}, pages = {101--121}, keywords = {SFB-TRR-62, Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/Richter2017UserCenteredPlanningUnderUncertainty.pdf} } @Inbook { Biundo2017CompBookIntro, author = {Biundo, Susanne and Wendemuth, Andreas}, title = {An Introduction to Companion-Technology}, abstract = {Companion-technology enables a new generation of intelligent systems. These Companion-systems smartly adapt their functionality to a user’s individual requirements. They comply with his or her abilities, preferences, and current needs and adjust their behavior as soon as critical changes of the environment or changes of the user’s emotional state or disposition are observed. Companion-systems are distinguished by characteristics such as competence, individuality, adaptability, availability, cooperativeness, and trustworthiness. These characteristics are realized by integrating the technical functionality of systems with a combination of cognitive processes. Companion-systems are able to perceive the user and the environment; they reason about the current situation, exploit background knowledge, and provide and pursue appropriate plans of action; and they enter into a dialog with the user where they select the most suitable modes of interaction in terms of media, modalities and dialog strategies. This chapter introduces the essence of Companion-technology and sheds light on the huge range of its prospective applications.}, year = {2017}, DOI = {10.1007/978-3-319-43665-4_1}, booktitle = {Companion Technology -- A Paradigm Shift in Human-Technology Interaction}, publisher = {Springer}, chapter = {1}, series = {Cognitive Technologies}, editor = {Susanne Biundo and Andreas Wendemuth}, pages = {1--15}, tags = {SFB-TRR-62}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/Biundo2017CompBookIntro.pdf} } @Inproceedings { Schiller17CouplingKnowledge, author = {Schiller, Marvin R. G. and Behnke, Gregor and Schmautz, Mario and Bercher, Pascal and Kraus, Matthias and Dorna, Michael and Minker, Wolfgang and Glimm, Birte and Biundo, Susanne}, title = {A Paradigm for Coupling Procedural and Conceptual Knowledge in Companion Systems}, abstract = {Companion systems are technical systems that adjust their functionality to the needs and the situation of an individual user. Consequently, companion systems are strongly knowledge-based. We propose a modelling paradigm for integrating procedural and conceptual knowledge which is targeted at companion systems that require a combination of planning and reasoning capabilities. The presented methodology couples the hierarchical task network (HTN) planning formalism with an ontology-based knowledge representation, thereby minimising redundancies in modelling and enabling the use of state-of-the-art reasoning and planning tools on the shared knowledge model. The approach is applied within a prototype of a companion system that assists novice users in the do-it-yourself (DIY) domain with the planning and execution of home improvement projects involving the use of power tools.}, year = {2017}, DOI = {10.1109/COMPANION.2017.8287072}, booktitle = {Proceedings of the 2nd International Conference on Companion Technology (ICCT 2017)}, publisher = {IEEE}, tags = {SFB-TRR-62,SFB-T3,Planning,KnowledgeModeling}, web_url = {http://ieeexplore.ieee.org/document/8287072/}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/SBSBKDMGB-ICCT2017.pdf} } @Inbook { Geier2017CompBookMLKP, author = {Geier, Thomas and Biundo, Susanne}, title = {Multi-Level Knowledge Processing in Cognitive Technical Systems}, abstract = {Companion-Systems are composed of different modules that have to share a single, sound estimate of the current situation. While the long-term decision-making of automated planning requires knowledge about the user’s goals, short-term decisions, like choosing among modes of user-interaction, depend on properties such as lighting conditions. In addition to the diverse scopes of the involved models, a large portion of the information required within such a system cannot be directly observed, but has to be inferred from background knowledge and sensory data{--}sometimes via a cascade of abstraction layers, and often resulting in uncertain predictions. In this contribution, we interpret an existing cognitive technical system under the assumption that it solves a factored, partially observable Markov decision process. Our interpretation heavily draws from the concepts of probabilistic graphical models and hierarchical reinforcement learning, and fosters a view that cleanly separates between inference and decision making. The results are discussed and compared to those of existing approaches from other application domains.}, year = {2017}, DOI = {10.1007/978-3-319-43665-4_2}, booktitle = {Companion Technology -- A Paradigm Shift in Human-Technology Interaction}, publisher = {Springer}, chapter = {2}, series = {Cognitive Technologies}, editor = {Susanne Biundo}, pages = {17--36}, tags = {SFB-TRR-62}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/Geier2017CompBookMLKP.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 { 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} } @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 {\\&}ndash; if not most {\\&}ndash; 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} } @Article { Biundo16CompanionTechnology, author = {Biundo, Susanne and Wendemuth, Andreas}, title = {Companion-Technology for Cognitive Technical Systems}, abstract = {We introduce the Transregional Collaborative Research Centre “Companion-Technology for Cognitive Technical Systems” {\\&}ndash; a cross-disciplinary endeavor towards the development of an enabling technology for Companion-systems. These systems completely adjust their functionality and service to the individual user. They comply with his or her capabilities, preferences, requirements, and current needs and adapt to the individual’s emotional state and ambient conditions. Companion-like behavior of technical systems is achieved through the investigation and implementation of cognitive abilities and their well-orchestrated interplay.}, year = {2016}, DOI = {10.1007/s13218-015-0414-8}, journal = {K{\"u}nstliche Intelligenz}, volume = {30}, publisher = {Springer}, pages = {71-75}, number = {1}, tags = {SFB-TRR-62}, web_url = {http://link.springer.com/article/10.1007/s13218-015-0414-8}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2016/Biundo16CompanionTechnology.pdf}, note = {Special Issue on Companion Technologies}, annotation = {Special Issue on Companion Technologies} } @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 {\dq}Companions'' to their users. They serve as co-operative agents assisting in particular tasks or, in a more general sense, even give companionship to humans. Overall, Companion-technology enables technical systems to smartly adapt their services to individual users' current needs, their requests, situation, and emotion. We give an introduction to the field, discuss the most relevant application areas that will benefit from its developments, and review the related research projects.}, 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 { 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} } @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 {\\&}ndash; adaptive, flexible, and cooperative {\\&}ndash; technical systems by applying and fusing techniques from different areas of research. In our special issue we present interesting pieces of work {\\&}ndash; quite a number of new technical contributions, ongoing and completed research projects, several dissertation abstracts, as well as an interview {\\&}ndash; 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 { 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 { Geier2015, author = {Geier, Thomas and Richter, Felix and Biundo, Susanne}, title = {Locally Conditioned Belief Propagation}, abstract = {Conditioned Belief Propagation (CBP) is an algorithm for approximate inference in probabilistic graphical models. It works by conditioning on a subset of variables and solving the remainder using loopy Belief Propagation. Unfortunately, CBP's runtime scales exponentially in the number of conditioned variables. Locally Conditioned Belief Propagation (LCBP) approximates the results of CBP by treating conditions locally, and in this way avoids the exponential blow-up. We formulate LCBP as a variational optimization problem and derive a set of update equations that can be used to solve it. We show empirically that LCBP delivers results that are close to those obtained from CBP, while the computational cost scales favorably with problem size. }, year = {2015}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence (UAI)}, publisher = {AUAI Press}, pages = {296--305}, event_place = {Amsterdam}, keywords = {probablistic inference, belief propagation, approximate inference, graphical models}, tags = {SFB-TRR-62}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2015/Geier2015Lcbp.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 { Nothdurft2015InterplayDialogPlanning, author = {Nothdurft, Florian and Behnke, Gregor and Bercher, Pascal and Biundo, Susanne and Minker, Wolfgang}, title = {The Interplay of User-Centered Dialog Systems and AI Planning}, abstract = {Technical systems evolve from simple dedicated task solvers to cooperative and competent assistants, helping the user with increasingly complex and demanding tasks. For this, they may proactively take over some of the users responsibilities and help to find or reach a solution for the user’s task at hand, using e.g., Artificial Intelligence (AI) Planning techniques. However, this intertwining of user-centered dialog and AI planning systems, often called mixed-initiative planning (MIP), does not only facilitate more intelligent and competent systems, but does also raise new questions related to the alignment of AI and human problem solving. In this paper, we describe our approach on integrating AI Planning techniques into a dialog system, explain reasons and effects of arising problems, and provide at the same time our solutions resulting in a coherent, userfriendly and efficient mixed-initiative system. Finally, we evaluate our MIP system and provide remarks on the use of explanations in MIP-related phenomena.}, year = {2015}, booktitle = {Proceedings of the 16th Annual Meeting of the Special Interest Group on Discourse and Dialogue (SIGDIAL)}, publisher = {Association for Computational Linguistics}, pages = {344--353}, event_place = {Prague, Czech Republic}, tags = {SFB-TRR-62,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2015/Nothdurft15MIP.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 { Behnke2015Coherence, author = {Behnke, Gregor and Ponomaryov, Denis and Schiller, Marvin R. G. and Bercher, Pascal and Nothdurft, Florian and Glimm, Birte and Biundo, Susanne}, title = {Coherence Across Components in Cognitive Systems {\\&}ndash; One Ontology to Rule Them All}, abstract = {The integration of the various specialized components of cognitive systems poses a challenge, in particular for those architectures that combine planning, inference, and human-computer interaction (HCI). An approach is presented that exploits a single source of common knowledge contained in an ontology. Based upon the knowledge contained in it, specialized domain models for the cognitive systems’ components can be generated automatically. Our integration targets planning in the form of hierarchical planning, being well-suited for HCI as it mimics planning done by humans. We show how the hierarchical structures of such planning domains can be (partially) inferred from declarative background knowledge. The same ontology furnishes the structure of the interaction between the cognitive system and the user. First, explanations of plans presented to users are enhanced by ontology explanations. Second, a dialog domain is created from the ontology coherent with the planning domain. We demonstrate the application of our technique in a fitness training scenario.}, year = {2015}, booktitle = {Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2015)}, publisher = {AAAI Press}, pages = {1442-1449}, event_name = {IJCAI 2015}, event_place = {Buenos Aires}, tags = {SFB-TRR-62,Planning,AutomatedReasoning}, web_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2015/Behnke15IJCAI-poster.pdf}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2015/BPSB15a.pdf} } @Inproceedings { BBBGPS2015OntologiesAndPlanning, author = {Behnke, Gregor and Bercher, Pascal and Biundo, Susanne and Glimm, Birte and Ponomaryov, Denis and Schiller, Marvin R. G.}, title = {Integrating Ontologies and Planning for Cognitive Systems}, 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.}, year = {2015}, booktitle = {Proceedings of the 28th International Workshop on Description Logics (DL 2015)}, publisher = {CEUR Workshop Proceedings}, tags = {AutomatedReasoning, Planning, SFB-TRR-62}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2015/BBBG15a.pdf} } @Inproceedings { Richter2015believing, author = {Richter, Felix and Geier, Thomas and Biundo, Susanne}, title = {Believing in POMDPs}, abstract = {Partially observable Markov decision processes (POMDP) are well-suited for realizing sequential decision making capabilities that respect uncertainty in Companion systems that are to naturally interact with and assist human users. Unfortunately, their complexity prohibits modeling the entire Companion system as a POMDP. We therefore propose an approach that makes use of abstraction to enable employing POMDPs in Companion systems and discuss challenges for applying it.}, year = {2015}, booktitle = {Proceedings of the First International Symposium on Companion Technology (ISCT 2015)}, event_name = {First International Symposium on Companion Technology}, event_place = {Ulm, Germany}, keywords = {POMDP, cognitive technical systems}, tags = {SFB-TRR-62,Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2015/believingPOMDPs.pdf} } @Inproceedings { Behnke15MIPDiscussion, author = {Behnke, Gregor and Schiller, Marvin R. G. and Ponomaryov, Denis and Nothdurft, Florian and Bercher, Pascal and Minker, Wolfgang and Glimm, Birte and Biundo, Susanne}, title = {A Unified Knowledge Base for Companion-Systems - A Case Study in Mixed-Initiative Planning}, abstract = {Companion systems aim to extend the abilities of ordinary technical systems, for instance by modeling the user's situation, by recognizing the user's intentions, and by being able to interact with the user and to adapt to her/him. Such a system depends on planning capabilities to determine which actions are necessary to achieve a particular goal. In many situations it may not be appropriate for a companion system to develop plans on its own, but instead it has to integrate the user while creating the plan, i.e., it needs to be mixed-initiative. Based on earlier work, we demonstrate how a central knowledge base for a mixed-initiative planning system can be designed. We outline various benefts our approach brings to bear within a companion system. Lastly, we present several requests a user might issue towards the mixed-initiative planning system and how they can be answered by harnessing the knowledge base.}, year = {2015}, booktitle = {Proceedings of the First International Symposium on Companion Technology (ISCT 2015)}, pages = {43--48}, event_name = {First International Symposium on Companion Technology (ISCT 2015)}, event_place = {Ulm, Germany}, tags = {SFB-TRR-62,Planning,AutomatedReasoning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2015/Behnke15MIPDiscussion.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} } @Article { Glodek201517, author = {Glodek, Michael and Honold, Frank and Geier, Thomas and Krell, Gerald and Nothdurft, Florian and Reuter, Stephan and Sch{\"u}ssel, Felix and H{\"o}rnle, Thilo and Dietmayer, Klaus and Minker, Wolfgang and Biundo, Susanne and Weber, Michael and Palm, G{\"u}nther and Schwenker, Friedhelm}, title = {Fusion paradigms in cognitive technical systems for human{\\&}ndash;computer interaction}, abstract = {Abstract Recent trends in human{\\&}ndash;computer interaction (HCI) show a development towards cognitive technical systems (CTS) to provide natural and efficient operating principles. To do so, a CTS has to rely on data from multiple sensors which must be processed and combined by fusion algorithms. Furthermore, additional sources of knowledge have to be integrated, to put the observations made into the correct context. Research in this field often focuses on optimizing the performance of the individual algorithms, rather than reflecting the requirements of CTS. This paper presents the information fusion principles in CTS architectures we developed for Companion Technologies. Combination of information generally goes along with the level of abstractness, time granularity and robustness, such that large CTS architectures must perform fusion gradually on different levels {--} starting from sensor-based recognitions to highly abstract logical inferences. In our CTS application we sectioned information fusion approaches into three categories: perception-level fusion, knowledge-based fusion and application-level fusion. For each category, we introduce examples of characteristic algorithms. In addition, we provide a detailed protocol on the implementation performed in order to study the interplay of the developed algorithms.}, year = {2015}, issn = {0925-2312}, DOI = {10.1016/j.neucom.2015.01.076}, journal = {Neurocomputing}, volume = {161}, pages = {17 - 37}, keywords = {Human{\\&}ndash;computer interaction}, tags = {SFB-TRR-62}, file_url = {http://www.sciencedirect.com/science/article/pii/S0925231215002155/pdfft?md5=0f4a009f3f5ba7b155a82192be2a0dbe{\\&}pid=1-s2.0-S0925231215002155-main.pdf} } @Techreport { Geier2014CBPTR, author = {Geier, Thomas and Richter, Felix and Biundo, Susanne}, title = {Conditioned Belief Propagation Revisited: Extended Version}, abstract = {Belief Propagation (BP) applied to cyclic problems is a well known approximate inference scheme for probabilistic graphical models. To improve its accuracy, Conditioned Belief Propagation (CBP) has been proposed, which splits a problem into subproblems by conditioning on variables, applies BP to subproblems, and merges the results to produce an answer to the original problem. In this work, we propose a reformulated version of CBP that exhibits anytime behavior and allows for more specific tuning by formalizing a further aspect of the algorithm through the use of a leaf selection heuristic. We propose several simple and easy to compute heuristics and demonstrate their performance using an empirical evaluation on randomly generated problems.}, year = {2014}, month = {8}, institution = {Ulm University}, number = {UIB 2014-03}, tags = {SFB-TRR-62,KnowledgeModeling}, web_url = {http://vts.uni-ulm.de/doc.asp?id=9201 }, file_url = {http://vts.uni-ulm.de/docs/2014/9201/vts_9201_13795.pdf} } @Inproceedings { Bercher14TDGHeuristics, author = {Bercher, Pascal and Keen, Shawn and Biundo, Susanne}, title = {Hybrid Planning Heuristics Based on Task Decomposition Graphs}, abstract = {Hybrid Planning combines Hierarchical Task Network (HTN) planning with concepts known from Partial-Order Causal-Link (POCL) planning. We introduce novel heuristics for Hybrid Planning that estimate the number of necessary modifications to turn a partial plan into a solution. These estimates are based on the task decomposition graph that contains all decompositions of the abstract tasks in the planning domain. Our empirical evaluation shows that the proposed heuristics can significantly improve planning performance.}, year = {2014}, booktitle = {Proceedings of the Seventh Annual Symposium on Combinatorial Search (SoCS 2014)}, publisher = {AAAI Press}, pages = {35--43}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2014/Bercher14HybridHeuristicsSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2014/Bercher14HybridHeuristics.pdf} } @Inproceedings { Bercher14HybridPlanningApplication, author = {Bercher, Pascal and Biundo, Susanne and Geier, Thomas and Hoernle, Thilo and Nothdurft, Florian and Richter, Felix and Schattenberg, Bernd}, title = {Plan, Repair, Execute, Explain - How Planning Helps to Assemble your Home Theater}, abstract = {In various social, work-related, or educational contexts, an increasing demand for intelligent assistance systems can be observed. In this paper, we present a domain-independent approach that combines a number of planning and interaction components to realize advanced user assistance. Based on a hybrid planning formalism, the components provide facilities including the generation, execution, and repair as well as the presentation and explanation of plans. We demonstrate the feasibility of our approach by means of a system that aims to assist users in the assembly of their home theater. An empirical evaluation shows the benefit of such a supportive system, in particular for persons with a lack of domain expertise.}, year = {2014}, booktitle = {Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014) }, publisher = {AAAI Press}, pages = {386--394}, tags = {SFB-TRR-62,Planning,KnowledgeModeling}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2014/Bercher14PlanRepairExecuteExplainSlides.pdf}, web_url2 = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2014/movie.zip}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2014/Bercher14PlanRepairExecuteExplain.pdf}, note = {The domain can be downloaded from http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2014/Bercher14PlanRepairExecuteExplain.zip} } @Inproceedings { Pragst14CyberSecurity, author = {Pragst, Louisa and Richter, Felix and Bercher, Pascal and Schattenberg, Bernd and Biundo, Susanne}, title = {Introducing Hierarchy to Non-Hierarchical Planning Models {\\&}ndash; A Case Study for Behavioral Adversary Models}, 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.}, year = {2014}, booktitle = {28th PuK Workshop {\dq}Planen, Scheduling und Konfigurieren, Entwerfen{\dq} (PuK 2014)}, keywords = {Hybrid Planning, Hierarchical Planning, POCL Planning, Domain Modeling, Task Hierarchy, Abstractions}, tags = {SFB-TRR-62,Planning,KnowledgeModeling}, 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/Pragst14CyberSecurity.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 { 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 {\dq}Planen, 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 { Geier2014CBP, author = {Geier, Thomas and Richter, Felix and Biundo, Susanne}, title = {Conditioned Belief Propagation Revisited}, abstract = {Belief Propagation (BP) applied to cyclic problems is a well known approximate inference scheme for probabilistic graphical models. To improve the accuracy of BP, a divide-and-conquer approach termed Conditioned Belief Propagation (CBP) has been proposed in the literature. It recursively splits a problem by conditioning on variables, applies BP to subproblems, and merges the results to produce an answer to the original problem. In this essay, we propose a reformulated version of CBP that exhibits anytime behavior, and allows for more specific tuning by formalizing a further decision point that decides which subproblem is to be decomposed next. We propose some simple and easy to compute heuristics, and demonstrate their performance using an empirical evaluation on randomly generated problems.}, year = {2014}, DOI = {10.3233/978-1-61499-419-0-1011}, 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 = {1011-1012}, event_name = {21st European Conference on Artificial Intelligence (ECAI 2014)}, event_place = {Prague, Czech Republic}, tags = {SFB-TRR-62,KnowledgeModeling}, web_url = {http://ebooks.iospress.nl/volumearticle/37095} } @Inproceedings { honold2014b, author = {Honold, Frank and Bercher, Pascal and Richter, Felix and Nothdurft, Florian and Geier, Thomas and Barth, Roland and H{\"o}rnle, Thilo and Sch{\"u}ssel, Felix and Reuter, Stephan and Rau, Matthias and Bertrand, Gregor and Seegebarth, Bastian and Kurzok, Peter and Schattenberg, Bernd and Minker, Wolfgang and Weber, Michael and Biundo, Susanne}, title = {Companion-Technology: Towards User- and Situation-Adaptive Functionality of Technical Systems}, abstract = {The properties of multimodality, individuality, adaptability, availability, cooperativeness and trustworthiness are at the focus of the investigation of Companion Systems. In this article, we describe the involved key components of such a system and the way they interact with each other. Along with the article comes a video, in which we demonstrate a fully functional prototypical implementation and explain the involved scientific contributions in a simplified manner. The realized technology considers the entire situation of the user and the environment in current and past states. The gained knowledge reflects the context of use and serves as basis for decision-making in the presented adaptive system.}, year = {2014}, DOI = {10.1109/IE.2014.60}, booktitle = {10th International Conference on Intelligent Environments (IE 2014)}, publisher = {IEEE}, pages = {378--381}, keywords = {Adaptive HCI; AI Planning; Dialog Management; Interaction Management; Companion Technology}, tags = {SFB-TRR-62,Planning,KnowledgeModeling}, web_url = {https://mirkwood.informatik.uni-ulm.de/sfbtrr62/companion-system.mp4}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2014/Honold2014HomeTheaterVideo.pdf} } @Article { Glodek2014, author = {Glodek, Michael and Geier, Thomas and Biundo, Susanne and Palm, G{\"u}nther}, title = {A layered architecture for probabilistic complex pattern recognition to detect user preferences}, abstract = {The recognition of complex patterns is nowadays one of the most challenging tasks in machine learning, and it promises to be of great benefit for many applications, e.g. by allowing advanced human computer interaction to access the user’s situative context. This work examines a layered architecture that operates on different temporal granularities to infer complex patterns of user preferences. Classical hidden Markov models (HMM), conditioned HMM (CHMM) and fuzzy CHMM (FCHMM) are compared to find the best configuration in the lower architecture layers. In the uppermost layer, a Markov logic network (MLN) is applied to infer the user preference in a probabilistic rule-based manner. For each layer a comprehensive evaluation is given. We provide empirical evidence showing that the layered architecture using FCHMM and MLN is well-suited to recognize patterns on different layers.}, year = {2014}, DOI = {10.1016/j.bica.2014.06.003}, journal = {Neural-Symbolic Networks for Cognitive Capacities}, tags = {SFB-TRR-62}, web_url = {http://www.sciencedirect.com/science/article/pii/S2212683X14000486} } @Inproceedings { Bercher13EncodingPlans, author = {Bercher, Pascal and Biundo, Susanne}, title = {Encoding Partial Plans for Heuristic Search}, 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.}, year = {2013}, booktitle = {Proceedings of the 4th Workshop on Knowledge Engineering for Planning and Scheduling (KEPS 2013) at ICAPS 2013}, pages = {11--15}, tags = {SFB-TRR-62,Planning,KnowledgeModeling}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13EncodingPlansSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13EncodingPlans.pdf} } @Inproceedings { Bercher13SampleFF, author = {Bercher, Pascal and Geier, Thomas and Richter, Felix and Biundo, Susanne}, title = {On Delete Relaxation in Partial-Order Causal-Link Planning}, abstract = {We prove a new complexity result for Partial-Order Causal-Link (POCL) planning, in which we study the hardness of refining a search node (i.e., a partial plan) to a valid solution given a delete effect-free domain model. While the corresponding decision problem is known to be polynomial in state-based search (where search nodes are states), it turns out to be intractable in the POCL setting. Since both the currently best-informed heuristics for POCL planning are based on delete relaxation, we hope that our result sheds some new light on the problem of designing heuristics for POCL planning. Based on this result, we developed a new variant of one of these heuristics which incorporates more information of the current partial plan. We evaluate our heuristic on several domains of the early International Planning Competitions and compare it with other POCL heuristics from the literature.}, year = {2013}, booktitle = {Proceedings of the 2013 IEEE 25th International Conference on Tools with Artificial Intelligence (ICTAI 2013)}, publisher = {IEEE Computer Society}, pages = {674--681}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13SampleFFSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13SampleFF.pdf} } @Inproceedings { Glodek2013LayeredLogic, author = {Glodek, Michael and Geier, Thomas and Biundo, Susanne and Schwenker, Friedhelm and Palm, G{\"u}nther}, title = {Recognizing User Preferences Based on Layered Activity Recognition and First-Order Logic}, abstract = {Only few cognitive architectures have been proposed that cover the complete range from recognizers working on the direct sensor input, to logical inference mechanisms of classical artificial intelligence (AI). Logical systems operate on abstract predicates, which are often related to an action-like state transition, especially when compared to the classes recognized by pattern recognition approaches. On the other hand, pattern recognition is often limited to static patterns, and temporal and multi-modal aspects of a class are often not regarded, e.g. by testing only on pre-segmented data. Recent trends in AI aim at developing applications and methods that are motivated by data-driven real world scenarios, while the field of pattern recognition attempts to push forward the boundary of pattern complexity. We propose a new generic architecture to close the gap between AI and pattern recognition approaches. In order to detect abstract complex patterns, we process sequential data in layers. On each layer, a set of elementary classes is recognized and the outcome of the classification is passed to the successive layer such that the time granularity increases. Layers can combine modalities, additional symbolic information or make use of reasoning algorithms. We evaluated our approach in an on-line scenario of activity recognition using three layers. The obtained results show that the combination of concepts from pattern recognition and high-level symbolic information leads to a prosperous and powerful symbiosis.}, year = {2013}, DOI = {10.1109/ICTAI.2013.101}, booktitle = {Proceedings of the 2013 IEEE 25th International Conference on Tools with Artificial Intelligence (ICTAI 2013)}, pages = {648-653}, keywords = {Conditioned hidden Markov model;Layered architecture;Markov logic network}, tags = {SFB-TRR-62}, web_url = {http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp={\\&}arnumber=6735312} } @Inproceedings { Bercher13POCLPreferences, author = {Bercher, Pascal and Ginter, Fabian and Biundo, Susanne}, title = {Search Strategies for Partial-Order Causal-Link Planning with Preferences}, 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 \textitnet-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.}, year = {2013}, booktitle = {27th PuK Workshop {\dq}Planen, Scheduling und Konfigurieren, Entwerfen{\dq} (PuK 2013)}, pages = {29--40}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13POCLPreferencesSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13POCLPreferences.pdf} } @Inproceedings { Bercher13POCLHeuristics, author = {Bercher, Pascal and Geier, Thomas and Biundo, Susanne}, title = {Using State-Based Planning Heuristics for Partial-Order Causal-Link Planning}, abstract = {We present a technique which allows partial-order causal-link (POCL) planning systems to use heuristics known from state-based planning to guide their search. The technique encodes a given partially ordered partial plan as a new classical planning problem that yields the same set of solutions reachable from the given partial plan. As heuristic estimate of the given partial plan a state-based heuristic can be used estimating the goal distance of the initial state in the encoded problem. This technique also provides the first admissible heuristics for POCL planning, simply by using admissible heuristics from state-based planning. To show the potential of our technique, we conducted experiments where we compared two of the currently strongest heuristics from state-based planning with two of the currently best-informed heuristics from POCL planning.}, year = {2013}, booktitle = {Advances in Artificial Intelligence, Proceedings of the 36th German Conference on Artificial Intelligence (KI 2013)}, publisher = {Springer}, pages = {1--12}, tags = {SFB-TRR-62,Planning,KnowledgeModeling}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13POCLHeuristicsSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2013/Bercher13POCLHeuristics.pdf} } @Inproceedings { Mueller2012HPOMDPs, author = {M{\"u}ller, Felix and Sp{\"a}th, Christian and Geier, Thomas and Biundo, Susanne}, title = {Exploiting Expert Knowledge in Factored POMDPs}, abstract = {Decision support in real-world applications is often challenging because one has to deal with large and only partially observable domains. In case of full observability, large domains are successfully tackled by making use of expert knowledge and employing methods like Hierarchical Task Network (HTN) planning. In this paper, we present an approach that transfers the advantages of HTN planning to partially observable domains. Experimental results for two implemented algorithms, UCT and A* search, show that our approach significantly speeds up the generation of high-quality policies: the policies generated by our approach consistently outperform policies generated by Symbolic Perseus and can be computed in less than 10% of its runtime on average.}, year = {2012}, month = {8}, booktitle = {Proceedings of the 20th European Conference on Artificial Intelligence (ECAI 2012)}, publisher = {IOS Press}, pages = {606--611}, tags = {SFB-TRR-62,Planning}, web_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Mueller12HierarchicalFSCsReloadedSlides.pdf}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Mueller12HierarchicalFSCsReloaded.pdf} } @Inproceedings { Geier2012PersonTracking, author = {Geier, Thomas and Reuter, Stephan and Dietmayer, Klaus and Biundo, Susanne}, title = {Goal-Based Person Tracking Using a First-Order Probabilistic Model}, abstract = {This work addresses the problem of person tracking using additional background information. We augment a particle filter-based tracking algorithm with a first-order probabilistic model expressed through Markov Logic Networks to tackle the data association problem in domains with a high occlusion rate. Using a high-level model description allows us to easily integrate additional information like a floor plan or goal information into a joint model and resolve occlusion situations that would otherwise result in the loss of association. We discuss the engineered model in detail and give an empirical evaluation using an indoor setting.}, year = {2012}, month = {8}, booktitle = {Proceedings of the Ninth UAI Bayesian Modeling Applications Workshop (UAI-AW 2012)}, tags = {SFB-TRR-62, KnowledgeModeling}, web_url = {http://ceur-ws.org/Vol-962}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Geier12TrackingGoals.pdf} } @Inproceedings { Elkawkagy12LandmarkStrategies, author = {Elkawkagy, Mohamed and Bercher, Pascal and Schattenberg, Bernd and Biundo, Susanne}, title = {Improving Hierarchical Planning Performance by the Use of Landmarks}, abstract = {Hierarchical landmarks can be extracted and used to reduce hierarchical domain models, thereby leading to substantial runtime improvements. In this work, we present novel domain-independent planning strategies based on these landmarks. Our empirical evaluation on four benchmark domains shows that these landmark-aware strategies outperform established search strategies in many cases, even for reduced domain models.}, year = {2012}, month = {7}, booktitle = {Proceedings of the 26th AAAI Conference on Artificial Intelligence ({AAAI} 2012)}, publisher = {AAAI Press}, pages = {1763--1769}, tags = {SFB-TRR-62,Planning}, web_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Elkawkagy12LandmarkStrategiesPoster.pdf}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Elkawkagy12LandmarkStrategies.pdf} } @Inproceedings { Seegebarth12Explanation, author = {Seegebarth, Bastian and M{\"u}ller, Felix and Schattenberg, Bernd and Biundo, Susanne}, title = {Making Hybrid Plans More Clear to Human Users - A Formal Approach for Generating Sound Explanations}, abstract = {Human users who execute an automatically generated plan want to understand the rationale behind it. Knowledge-rich plans are particularly suitable for this purpose, because they provide the means to give reason for causal, temporal, and hierarchical relationships between actions. Based on this information, focused arguments can be generated that constitute explanations on an appropriate level of abstraction. In this paper, we present a formal approach to plan explanation. Information about plans is represented as first-order logic formulae and explanations are constructed as proofs in the resulting axiomatic system. With that, plan explanations are provably correct w.r.t. the planning system that produced the plan. A prototype plan explanation system implements our approach and first experiments give evidence that finding plan explanations is feasible in real-time.}, year = {2012}, month = {6}, day = {27}, booktitle = {Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS 2012)}, publisher = {AAAI Press}, pages = {225--233}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Seegebarth12PlanExplanationSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Seegebarth12PlanExplanation.pdf} } @Inproceedings { Bercher12PreferenceHeuristic, author = {Bercher, Pascal and Biundo, Susanne}, title = {A Heuristic for Hybrid Planning with Preferences}, abstract = {In this paper, we introduce an admissible heuristic for hybrid planning with preferences. Hybrid planning is the fusion of hierarchical task network (HTN) planning with partial order causal link (POCL) planning. We consider preferences to be soft goals - facts one would like to see satisfied in a goal state, but which do not have to hold necessarily. Our heuristic estimates the best quality of any solution that can be developed from the current plan under consideration. It can thus be used by any branch-and-bound algorithm that performs search in the space of plans to prune suboptimal plans from the search space.}, year = {2012}, month = {5}, booktitle = {Proceedings of the Twenty-Fifth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2012)}, publisher = {AAAI Press}, pages = {120--123}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Bercher12PreferenceHeuristicPoster.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Bercher12PreferenceHeuristic.pdf} } @Inproceedings { Schattenberg12Mice, author = {Schattenberg, Bernd and L. Schulz, Andreas and Brechmann, Andr{\'e} and W. Ohl, Frank and Biundo, Susanne}, title = {Planning Models for Two-Way Avoidance and Reversal Learning}, abstract = {Reinforcement learning models can explain various aspects of two-way avoidance learning but do not provide a rationale for the relationship found between the dynamics of initial learning and those of reversal learning. Artificial Intelligence planning offers a novel way to conceptualize the learners’ cognitive processes by providing an explicit representation of and reasoning about internal processing stages. Our hybrid planning and plan repair approach demonstrates that the empirically found relationships could be motivated from a consistent theoretical framework.}, year = {2012}, month = {2}, booktitle = {Proceedings of the 7th Vienna International Conference on Mathematical Modelling (MATHMOD 2012)}, address = {Vienna, Austria}, tags = {SFB-TRR-62,Planning}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Schattenberg12PlanningModels.pdf} } @Inproceedings { geier2012association, author = {Geier, Thomas and Reuter, Stephan and Dietmayer, Klaus and Biundo, Susanne}, title = {Track-Person Association Using a First-Order Probabilistic Model}, year = {2012}, DOI = {10.1109/ICTAI.2013.101}, booktitle = {Proceedings of the 24th IEEE International Conference on Tools with Artificial Intelligence (ICTAI)}, pages = {844--851}, event_name = {Tools with Artificial Intelligence}, event_place = {Athens, Greece}, keywords = {SFB-TRR-62, KnowledgeModeling}, web_url = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6495131{\\&}tag=1}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2012/Geier2012TrackingB.pdf} } @Inproceedings { Wendemuth2012CompanionTechnology, author = {Wendemuth, Andreas and Biundo, Susanne}, title = {A Companion Technology for Cognitive Technical Systems}, abstract = {The Transregional Collaborative Research Centre SFB/TRR 62 {\dq}A Companion Technology for Cognitive Technical Systems{\dq}, funded by the German Research Foundation (DFG) at Ulm and Magdeburg sites, deals with the systematic and interdisciplinary study of cognitive abilities and their implementation in technical systems. The properties of multimodality, individuality, adaptability, availability, cooperativeness and trustworthiness are at the focus of the investigation. These characteristics show a new type of interactive device which is not only practical and efficient to operate, but as well agreeable, hence the term ”companion”. The realisation of such a technology is supported by technical advancement as well as by neurobiological findings. Companion technology has to consider the entire situation of the user, machine, environment and (if applicable) other people or third interacting parties, in current and historical states. This will reflect the mental state of the user, his embeddedness in the task, and how he is situated in the current process.}, year = {2012}, DOI = {10.1007/978-3-642-34584-5_7}, booktitle = {Cognitive Behavioural Systems: COST 2102 International Training School, Revised Selected Papers}, publisher = {Springer Berlin Heidelberg}, series = {Lecture Notes in Computer Science}, editor = {Anna Esposito, Alessandro Vinciarelli, R{\"u}diger Hoffman, Vincent C. M{\"u}ller}, pages = {89--103}, tags = {SFB-TRR-62,Planning}, web_url = {http://link.springer.com/chapter/10.1007%2F978-3-642-34584-5_7} } @Inproceedings { Geier2011OnlineInference, author = {Geier, Thomas and Biundo, Susanne}, title = {Approximate Online Inference for Dynamic Markov Logic Networks}, abstract = {We examine the problem of filtering for dynamic probabilistic systems using Markov Logic Networks. We propose a method to approximately compute the marginal probabilities for the current state variables that is suitable for online inference. Contrary to existing algorithms, our approach does not work on the level of belief propagation, but can be used with every algorithm suitable for inference in Markov Logic Networks, such as MCSAT. We present an evaluation of its performance on two dynamic domains.}, year = {2011}, DOI = {10.1109/ICTAI.2011.120}, booktitle = {Proceedings of the 23rd IEEE International Conference on Tools with Artificial Intelligence (ICTAI)}, pages = {764--768}, keywords = {dmln, mln, dynamic, inference}, tags = {SFB-TRR-62, KnowledgeModeling}, web_url = {http://www.cse.fau.edu/ictai2011/}, web_url2 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=6103411}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Geier11ApproxDMLNs.pdf} } @Incollection { Bidot2011AmbientEnvironments, author = {Bidot, Julien and Biundo, Susanne}, title = {Artificial Intelligence Planning for Ambient Environments}, abstract = {In this chapter, we describe how Artificial Intelligence planning techniques are used in The Adapted and TRusted Ambient eCOlogies (ATRACO) in order to provide Sphere Adaptation . We introduce the Planning Agent (PA) which plays a central role in the realization and the structural adaptation of activity spheres. Based on the particular information included in the ontology of the execution environment, the PA delivers workflows that consist of the basic activities to be executed in order to achieve a user’s goals. The PA encapsulates a search engine for hybrid planning{--}the combination of hierarchical task network (HTN) planning and partial-order causal-link (POCL) planning . In this chapter, we describe a formal framework and a development platform for hybrid planning, PANDA. This platform allows for the implementation of many search strategies, and we explain how we realize the search engine of the PA by adapting and configuring PANDA specifically for addressing planning problems that are part of the ATRACO service composition. We describe how the PA interacts with the Sphere Manager and the Ontology Manager in order to create planning problems dynamically and generate workflows in the ATRACO-BPEL language. In addition, an excerpt of a planning domain for ATRACO is provided.}, year = {2011}, DOI = {10.1007/978-3-319-23452-6_8}, booktitle = {Next Generation Intelligence Environments - Ambient Adaptive Systems}, edition = {1}, publisher = {Springer}, chapter = {6}, editor = {Tobias Heinroth and Wolfgang Minker}, pages = {195--225}, tags = {SFB-TRR-62,Planning} } @Inproceedings { Mueller2011HierarchicalFSCs, author = {M{\"u}ller, Felix and Biundo, Susanne}, title = {HTN-Style Planning in Relational POMDPs Using First-Order FSCs}, abstract = {n this paper, a novel approach to hierarchical planning under partial observability in relational domains is presented. It combines hierarchical task network planning with the finite state controller (FSC) policy representation for partially observable Markov decision processes. Based on a new first-order generalization of FSCs, action hierarchies are defined as in traditional hierarchical planning, so that planning corresponds to finding the best plan in a given decomposition hierarchy of predefined, partially abstract FSCs. Finally, we propose an algorithm for solving planning problems in this setting. Our approach offers a way of practically dealing with real-world partial observability planning problems: it avoids the complexity originating from the dynamic programming backup operation required in many present-day policy generation algorithms.}, year = {2011}, booktitle = {Proceedings of the 34th Annual German Conference on Artificial Intelligence (KI 2011)}, publisher = {Springer}, editor = {Joscha Bach and Stefan Edelkamp}, pages = {216--227}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.springerlink.com/content/g051ht236j73761m/}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/paper-hierarchicalFOFSCs.pdf} } @Inproceedings { Elkawkagy2011HybridMultiAgent2, author = {Elkawkagy, Mohamed and Biundo, Susanne}, title = {Hybrid Multi-agent Planning}, abstract = {Although several approaches have been constructed for multi-agent planning, solving large planning problems is still quite difficult. In this paper, we present a new approach that integrates landmark preprocessing technique in the context of hierarchical planning with multi-agent planning. Our approach uses Dependent and Independent clustering techniques to break up the planning problem into smaller clusters. These clusters are solved individually according to landmark information, then the obtained individual plans are merged according to the notion of fragments to generate a final solution plan. In hierarchical planning, landmarks are those tasks that occur in the decomposition refinements on every plan development path. Hierarchical landmark technique shows how a preprocessing step that extracts landmarks from a hierarchical planning domain and problem description can be used to prune the search space that is to be explored before actual search is performed. The methodologies in this paper have been implemented successfully, and we will present some experimental results that give evidence for the considerable performance increase gained through our system.}, year = {2011}, booktitle = {Proceedings of the of the Ninth German Conference on Multi-Agent System Technologies (MATES 2011)}, publisher = {IOS Press}, pages = {16--28}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Elkawkagy11HybridMultiAgentSlides.pdf}, web_url2 = {http://www.springerlink.com/content/e73066483x2j7502/}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Elkawkagy11HybridMultiAgent.pdf} } @Inproceedings { Bercher2011Preferences, author = {Bercher, Pascal and Biundo, Susanne}, title = {Hybrid Planning with Preferences Using a Heuristic for Partially Ordered Plans}, 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.}, year = {2011}, booktitle = {26th PuK Workshop {\dq}Planen, Scheduling und Konfigurieren, Entwerfen{\dq} (PuK 2011)}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Bercher11PreferencesSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Bercher11Preferences.pdf} } @Inproceedings { Elkawkagy2011LandmarkStrategies, author = {Elkawkagy, Mohamed and Bercher, Pascal and Schattenberg, Bernd and Biundo, Susanne}, title = {Landmark-Aware Strategies for Hierarchical Planning}, 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.}, year = {2011}, booktitle = {Workshop on Heuristics for Domain-independent Planning (HDIP 2011) at ICAPS 2011}, pages = {73--79}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Elkawkagy11LandmarkStrategiesSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Elkawkagy11LandmarkStrategies.pdf} } @Article { Biundo2011RealWorldPlanning, author = {Biundo, Susanne and Bidot, Julien and Schattenberg, Bernd}, title = {Planning in the Real World}, abstract = {In this article, we describe how real world planning problems can be solved by employing Artificial Intelligence planning techniques. We introduce the paradigm of hybrid planning, which is particularly suited for applications where plans are not intended to be automatically executed by systems, but are made for humans. Hybrid planning combines hierarchical planning {\\&}ndash; the stepwise refinement of complex tasks {\\&}ndash; with explicit reasoning about causal dependencies between actions, thereby reflecting exactly the kinds of reasoning humans perform when developing plans. We show how plans are generated and how failed plans are repaired in a way that guarantees stability. Our illustrating examples are taken from a domain model for disaster relief missions enforced upon extensive floods. Finally, we present a tool to support the challenging task of constructing planning domain models. The article ends with an overview of a wide varity of actual planning applications and outlines further such in the area of cognitive technical systems.}, year = {2011}, DOI = {10.1007/s00287-011-0562-7}, journal = {Informatik-Spektrum}, volume = {34}, pages = {443--454}, number = {5}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.springerlink.com/content/514981j48161127x/}, file_url = {http://www.springerlink.com/content/514981j48161127x/fulltext.pdf} } @Inproceedings { Schulz2011ReversalLearning, author = {Schulz, Andreas and Schattenberg, Bernd and Woldeit, Marie and Brechmann, Andr{\'e} and Biundo, Susanne and W. Ohl, Frank}, title = {Reinforcement learning and planning models for two-way-avoidance and reversal learning}, abstract = {The framework of reinforcement learning (RL), in particular temporal difference (TD) learning, is traditionally utilized to model Pavlovian and Instrumental Learning in animal and human subjects. Neurophysiological correlates model parameters, on the level of both single cells and fMRI data, support this approach ( Barto and Sutton 1998, Schulz 2001, Doya 2008). Notably, most of these models are applied to appetitive learning, as their nature demands that reinforcement is directly related to an action. In aversive learning this is not the case, at least not for directly observable actions of the animal. Therefore RL models of avoidance learning are studied only relatively recently (e.g. Moutoussis et al. 2008). The first aim of the present study was the investigation of RL models in the context of two-way avoidance and reversal learning. We used a well-established animal model for two-way avoidance, the Mongolian gerbil trained in a shuttle box Go/NoGo paradigm (Wetzel 1998; Ohl et al. 2001). We have extended the RL model of Moutoussis et al. and compared the results to the animal behavior.We also found, that Reinforcement Learning models can explain various aspects of two-way avoidance learning but do not provide a rationale for the relationship found between dynamics of initial learning and dynamics of reversal learning. However, the Artificial Intelligence (AI) paradigm of Automated Planning can provide a rationale for explaining such relationships. As the second aim of this study, we therefore modeled the avoidance learning by a Hybrid Planning ( Biundo and Schattenberg 2001) and plan repair approach (Bidot et al. 2008) and demonstrated that the empirically found relationships could be motivated from a consistent theoretical framework. The AI planning framework has the additional advantage over mere Reinforcement models to provide an explicit representation of and reasoning about {\\&}quot;internal{\\&}quot; processing stages.}, year = {2011}, booktitle = {Proceedings of the Annual Meeting of the Society For Neuroscience}, keywords = {avoidance,reinforcement learning, modeling}, tags = {SFB-TRR-62,Planning,KnowledgeModeling}, web_url = {http://www.abstractsonline.com/Plan/ViewAbstract.aspx?sKey=36dc39eb-9262-472e-9ee0-df4fc3c6abd5{\\&}cKey=f1c0c307-ad80-41c9-b32f-f5def2a643e0{\\&}mKey=%7b8334BE29-8911-4991-8C31-32B32DD5E6C8%7d} } @Article { Biundo2011CognitiveSystems, author = {Biundo, Susanne and Bercher, Pascal and Geier, Thomas and M{\"u}ller, Felix and Schattenberg, Bernd}, title = {Advanced user assistance based on AI planning}, abstract = {Artificial Intelligence technologies enable the implementation of cognitive systems with advanced planning and reasoning capabilities. This article presents an approach to use hybrid planning - a method that combines reasoning about procedural knowledge and causalities - to provide user-centered assistance.Based on a completely declarative description of actions, tasks, and solution methods, hybrid planning allows for the generation of knowledge-rich plans of action. The information those plans comprise includes causal dependencies between actions on both abstract and primitive levels as well as information about their hierarchical and temporal relationships.We present the hybrid planning approach in detail and show its potential by describing the realization of various assistance functionalities based on complex cognitive processes like the generation, repair, and explanation of plans. Advanced user assistance is demonstrated by means of a practical application scenario where an innovative electronic support mechanism helps a user to operate a complex mobile communication device.}, year = {2011}, issn = {1389--0417}, DOI = {10.1016/j.cogsys.2010.12.005}, journal = {Cognitive Systems Research}, volume = {12}, pages = {219--236}, number = {3-4}, keywords = {Cognitive technical systems, Companion-technology, Hybrid planning, Plan repair, Plan explanation, Real-world planning}, tags = {SFB-TRR-62,Planning}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2011/Biundo11AdvancedUserAssistance.pdf}, note = {Special Issue on Complex Cognition} } @Inproceedings { Biundo2010Explanations, author = {Bidot, Julien and Biundo, Susanne and Heinroth, Tobias and Minker, Wolfgang and Nothdurft, Florian and Schattenberg, Bernd}, title = {Verbal Explanations for Hybrid Planning}, abstract = {State-of-the-art AI planning systems are able to generate complex plans thanks to their efficient reasoning engines. In a large number of application domains, the plans are automatically executed by systems such as autonomous robots. In this context, it is not necessary to make these automated systems understand what they are actually doing during execution and why they are doing that. In other words, these systems do not need to understand the underlying semantics of the plans they execute and how these plans have been generated. However, there are a significant number of key application domains, such as disaster relief mission support or project planning, where plans are supposed to be executed by a human user who is not necessarily a planning expert, an application expert, or both. In addition, for real-world applications, the plans and the plan generation are often complex. In order to unlock a part of the application potential of the AI planning technology, it is necessary that the user trusts the technology. Increasing trust in AI planning systems requires the design and implementation of user-friendly interfaces and the development of plan explanation methods that allow for taking into consideration the human user’s queries related to some components of the plan about their meaning and relevance for the plan and giving back the appropriate information that answers these queries. The verbal communication by speech constitutes the most natural form of communication for humans. By means of natural language dialogs in this work, we focus on the explanation of plans that are generated by a refinement-based planning system. Contrary to most approaches presented in the literature that try to provide explanations when backtracking occurs in failure situations during search, we assume in this work that the plans for which explanations are looked for are consistent. We present a domain-independent approach to enabling verbal human queries and producing verbal plan explanations.}, year = {2010}, booktitle = {Proceedings of the Conference {\dq}Multikonferenz Wirtschaftsinformatik{\dq} (MKWI 2010), Teilkonferenz {\\&}quot;Planen, Scheduling und Konfigurieren, Entwerfen{\\&}quot; (PuK 2010)}, publisher = {Universit{\"a}tsverlag G{\"o}ttingen}, editor = {Matthias Schumann and Lutz M. Kolbe and Michael H. Breitner and Arne Frerichs}, pages = {2309--2320}, tags = {SFB-TRR-62,Planning}, file_url = {http://webdoc.sub.gwdg.de/univerlag/2010/mkwi/03_anwendungen/planen_scheduling/06_verbal_plan_explanations_for_hybrid_plannings.pdf} } @Article { Biundo2010mpanionSysteme, author = {Biundo, Susanne and Wendemuth, Andreas}, title = {Von kognitiven technischen Systemen zu Companion-Systemen}, abstract = {Hoffnung, l{\"a}stige Routineaufgaben zu automatisieren, der unerw{\"u}nschten Informationsflut Herr zu werden, erw{\"u}nschte Informationen zu erhalten, zeitraubende Koordinations- und Kommunikationsaufgaben zu bew{\"a}ltigen und sich von langweiligen Alltagsentscheidungen entlasten zu k{\"o}nnen. Von Informationstechnik erhoffen sich viele Menschen {\\&}ndash; entsprechend dem Heinzelm{\"a}nnchenmotiv {\\&}ndash; eine umfassende Assistenz, die ihren Wunsch nach individueller Produktivit{\"a}t und pers{\"o}nlicher Bequemlichkeit in einem immer komplexer werdenden Alltag erf{\"u}llt. Der dadurch gewonnene Freiraum soll ihnen erm{\"o}glichen, sich auf die interessanten und wesentlichen Aufgaben zu konzentrieren. Sie wollen sich diesen Aufgaben ohne technische Einschr{\"a}nkung jederzeit und {\"u}berall widmen k{\"o}nnen. Die damit verbundene Zeitersparnis f{\"u}r delegierbare Arbeit soll es au{\"s}erdem erm{\"o}glichen, in signifikanter Weise Kosten einzusparen und Waren oder Dienstleistungen deutlich preisg{\"u}nstiger anzubieten}, year = {2010}, DOI = {10.1007/s13218-010-0056-9}, journal = {K{\"u}nstliche Intelligenz}, volume = {24}, pages = {335--339}, number = {4}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.springerlink.com/content/e558815w08k09531/}, file_url = {http://www.springerlink.com/content/e558815w08k09531/fulltext.pdf} } @Inproceedings { Elkawkagy10LandmarksInHTN, author = {Elkawkagy, Mohamed and Schattenberg, Bernd and Biundo, Susanne}, title = {Landmarks in Hierarchical Planning}, abstract = {In this paper we introduce a novel landmark technique for hierarchical planning. Landmarks are abstract tasks that are mandatory. They have to be performed by any solution plan. Our technique relies on a landmark extraction procedure that pre-processes a given planning problem by systematically analyzing the ways in which relevant abstract tasks can be decomposed. We show how the landmark information is used to guide hierarchical planning and present some experimental results that give evidence for the considerable performance increase gained through our technique.}, year = {2010}, booktitle = {Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010)}, publisher = {IOS Press}, pages = {229--234}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2010/Elkawkagy10LandmarksInHierarchicalSlides.pdf}, web_url2 = {http://www.booksonline.iospress.nl/Content/View.aspx?piid=17747}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2010/Elkawkagy10LandmarksInHierarchical.pdf} } @Inproceedings { Elkawkagy10LandmarksInHybrid, author = {Elkawkagy, Mohamed and Bercher, Pascal and Schattenberg, Bernd and Biundo, Susanne}, title = {Exploiting Landmarks for Hybrid Planning}, 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.}, year = {2010}, booktitle = {Proceedings of the 25th PuK Workshop {\\&}quot;Planen, Scheduling und Konfigurieren, Entwerfen{\\&}quot; (PuK 2010)}, tags = {SFB-TRR-62,Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2010/Elkawkagy10LandmarksInHybridSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2010/Elkawkagy10LandmarksInHybrid.pdf} } @Inproceedings { Schattenberg2009Framework, author = {Schattenberg, Bernd and Bidot, Julien and Ge{\"s}ler, Sascha and Biundo, Susanne}, title = {A Framework for Interactive Hybrid Planning}, abstract = {Hybrid planning, the integration of hierarchical task decomposition and partial-order planning, provides a powerful mechanism to solve real-world planning problems. We present a domain-independent, mixed-initiative approach to plan generation that is based on a formal concept of hybrid planning. It allows for any interaction modalities and models of initiative while preserving the soundness of the plan generation process. Adequately involving the decision competences of end-users this way will improve the application potential as well as the acceptance of the technology.}, year = {2009}, isbn = {978-3-642-04616-2}, DOI = {10.1007/978-3-642-04617-9_3}, booktitle = {Proceedings of the 32nd Annual German Conference on Artificial Intelligence (KI 2009)}, volume = {5803}, publisher = {Springer}, series = {LNAI 5803}, pages = {17--24}, tags = {Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2009/Schattenberg2009FrameworkSlides.pdf}, web_url2 = {http://www.springerlink.com/content/v3171u800470815r/}, file_url = {http://www.springerlink.com/content/v3171u800470815r/fulltext.pdf} } @Inproceedings { Bidot2008PlanRepair, author = {Bidot, Julien and Biundo, Susanne and Schattenberg, Bernd}, title = {Plan Repair in Hybrid Planning}, abstract = {Hybrid Planning, the integration of hierarchical task decomposition and partial-order-causal-link planning provides a powerful mechanism to solve real-world planning problems. While the generation of hybrid plans is well understood, the problem of how to adequately deal with the various types of execution failures in this context has not yet been addressed. We present a domain-independent approach to plan repair in hybrid planning. It exploits the generation process of the failed plan by retracting decisions that led to the failed plan fragments. They are selectively replaced by suitable alternatives, and the repaired plan is completed by following the previous generation process as close as possible. This way, a stable solution is obtained, i.e. a repair of the failed plan that causes minimal perturbation. We show how plan repair fits into a formal framework for hybrid planning and present a generic refinement-retraction-and-repair algorithm.}, year = {2008}, DOI = {10.1007/978-3-540-85845-4_21}, booktitle = {Proceedings of the 31st Annual German Conference on Artificial Intelligence (KI 2008)}, volume = {5243}, publisher = {Springer}, series = {Lecture Notes in Artificial Intelligence}, editor = {Andreas Dengel and Karsten Berns and Thomas Breuel and Frank Bomarius and Thomas R. Roth-Berghofer}, pages = {169--176}, tags = {Planning}, web_url = {http://www.springerlink.com/content/7h142500k7211717/}, file_url = {http://www.springerlink.com/content/7h142500k7211717/fulltext.pdf} } @Inproceedings { Schattenberg2007UnifyingFramework, author = {Schattenberg, Bernd and Biundo, Susanne}, title = {A Unifying Framework For Hybrid Planning And Scheduling}, abstract = {Many real-world application domains that demand planning and scheduling support do not allow for a clear separation of these capabilities. Typically, an adequate mixture of both methodologies is required, since some aspects of the underlying planning problem imply consequences on the scheduling part and vice versa. Several integration efforts have been undertaken to couple planning and scheduling methods, most of them using separate planning and scheduling components which iteratively exchange partial solutions until both agree on a result. This paper presents a framework that provides a uniform integration of hybrid planning {\\&}ndash;the combination of operator based partial order planning and abstraction based hierarchical task network planning{\\&}ndash; and a hierarchical scheduling approach. It is based on a proper formal account of refinement planning, which allows for the formal definition of hybrid planning, scheduling, and search strategies. In a first step, the scheduling functionality is used to produce plans that comply with time restrictions and resource bounds. We show how the resulting framework is thereby able to perform novel kinds of search strategies that opportunistically interleave what used to be separate planning and scheduling processes.}, year = {2007}, DOI = {10.1007/978-3-540-69912-5_27}, booktitle = {Advances in Artificial Intelligence, Proceedings of the 29th German Conference on Artificial Intelligence (KI 2006)}, volume = {4314}, publisher = {Springer}, series = {Lecture Notes in Artificial Intelligence}, editor = {Christian Freksa and Michael Kohlhase and Kerstin Schill}, pages = {361--373}, tags = {Planning}, web_url = {http://www.springerlink.com/content/3821231298565uk3/}, file_url = {http://www.springerlink.com/content/3821231298565uk3/fulltext.pdf} } @Inproceedings { Schattenberg2007FlexibleStrategies, author = {Schattenberg, Bernd and Bidot, Julien and Biundo, Susanne}, title = {On the Construction and Evaluation of Flexible Plan-Refinement Strategies}, abstract = {This paper describes a system for the systematic construction and evaluation of planning strategies. It is based on a proper formal account of refinement planning and allows to decouple plan-deficiency detection, refinement computation, and search control. In adopting this methodology, planning strategies can be explicitly described and easily deployed in various system configurations. We introduce novel domain-independent planning strategies that are applicable to a wide range of planning capabilities and methods. These so-called HotSpot strategies are guided by information about current plan defects and solution options. The results of a first empirical performance evaluation are presented in the context of hybrid planning.}, year = {2007}, DOI = {10.1007/978-3-540-74565-5_28}, booktitle = {Advances in Artificial Intelligence, Proceedings of the 30th German Conference on Artificial Intelligence (KI 2007)}, volume = {4667}, publisher = {Springer}, address = {Osnabr{\"u}ck, Germany}, series = {Lecture Notes in Artificial Intelligence}, editor = {Joachim Hertzberg and Michael Beetz and Roman Englert}, pages = {367--381}, tags = {Planning}, web_url = {http://www.springerlink.com/content/lx1l87180v450468/}, file_url = {http://www.springerlink.com/content/lx1l87180v450468/fulltext.pdf} } @Article { Schattenberg07HybridSoftware, author = {Schattenberg, Bernd and Balzer, Steffen and Biundo, Susanne}, title = {Realizing Hybrid Planning Systems as Modern Software Environments}, abstract = {We present an architecture for planning and scheduling systems that addresses key requirements of real-world applications in a unique manner. It provides a robust, scalable, and flexible framework through the use of industrialstrength middleware and multi-agent technology. The architectural concepts extend knowledge-based components that dynamically perform and verify the system’s configuration; standardized components and communication protocols allow a seamless integration with third-party libraries and application environments. The system is based on a proper formal account of hybrid planning, the integration of HTN and POCL planning. The framework allows to decouple the detection of plan flaws, the computation of plan modifications, and search control. Consequently, planning and scheduling capabilities can be easily combined by orchestrating respective elementary modules and strategies. This platform can implement and evaluate various configurations of planning methods and strategies, without jeopardizing system consistency through interfering module activity.}, year = {2007}, journal = {K{\"u}nstliche Intelligenz}, volume = {21}, pages = {16--22}, number = {1}, web_url = {http://www.kuenstliche-intelligenz.de/archives/ki-journal-20160917/index.php-id=7754{\\&}tx_ki_pi1[showUid]=1248{\\&}cHash=6d9424bc18.html}, file_url = {http://www.kuenstliche-intelligenz.de/archives/ki-journal-20160917/fileadmin/template/main/archiv/2007_1/realizing-schattenberg-web.pdf} } @Inproceedings { Schattenberg06KnowledgeBasedMiddleware, author = {Schattenberg, Bernd and Balzer, Steffen and Biundo, Susanne}, title = {Knowledge-based Middleware as an Architecture for Planning and Scheduling Systems}, abstract = {We present an architecture that provides a robust, scalable and flexible software framework for planning and scheduling systems through the use of standardized industrial-strength middleware and multi-agent technology. It utilizes knowledgebased components that dynamically perform and verify the system's configuration. The system is based on a proper formal account of hybrid planning, the integration of HTN and POCL planning, which allows to decouple flaw detection, modification computation,and search control. In adopting this methodology, planning and scheduling capabilities can be easily combined by orchestrating respective elementary modules and strategies without jeopardizing system consistency through interfering module activity.}, year = {2006}, booktitle = {Proceedings of the 16th International Conference on Automated Planning and Scheduling (ICAPS 2006)}, publisher = {AAAI Press}, address = {Ambleside, The English Lake District, UK}, editor = {Derek Long and Stephen F. Smith and Daniel Borrajo and Thomas Lee McCluskey}, pages = {422--425}, tags = {Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2006/Schattenberg06KnowledgeBasedMiddleware.pdf} } @Inproceedings { Schattenberg2006WebTechnology, author = {Schattenberg, Bernd and Balzer, Steffen and Biundo, Susanne}, title = {Semantic Web Technology as a Basis for Planning and Scheduling Systems}, abstract = {This paper presents an architecture for planning and scheduling systems that addresses key requirements of real-world applications in a unique manner. The system provides a robust, scalable and flexible framework for planning and scheduling software through the use of industrial-strength middleware and multi-agent technology. The architectural concepts extend knowledge-based components that dynamically perform and verify the system's configuration. The use of standardized components and communication protocols allows a seamless integration with third-party libraries and existing application environments. The system is based on a proper formal account of hybrid planning, the integration of HTN and POCL planning. The theoretical framework allows to decouple flaw detection, modification computation, and search control. In adopting this methodology, planning and scheduling capabilities can be easily combined by orchestrating respective elementary modules and strategies. The conceptual platform can be used to implement and evaluate various configurations of planning methods and strategies, without jeopardizing system consistency through interfering module activity.}, year = {2006}, booktitle = {Proceedings of the 20th Workshop Planen und Konfigurieren´´ (PuK 2006)}, address = {University of Bremen}, editor = {J{\"u}rgen Sauer}, pages = {26--36}, tags = {Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2006/Schattenberg2006WebTechnologySlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2006/Schattenberg2006WebTechnology.pdf} } @Inproceedings { Schattenberg05FlexibleStrategies, author = {Schattenberg, Bernd and Weigl, Andreas and Biundo, Susanne}, title = {Hybrid Planning Using Flexible Strategies}, abstract = {In this paper we present a highly modular planning system architecture. It is based on a proper formal account of hybrid planning, which allows for the formal definition of (flexible) planning strategies. Groups of modules for flaw detection and plan refinement provide the basic functionalities of a planning system. The concept of explicit strategy modules serves to formulate and implement strategies that orchestrate the basic modules. This way a variety of fixed plan generation procedures as well as novel flexible planning strategies can easily be implemented and evaluated. We present a number of such strategies and show some first comparative performance results.}, year = {2005}, isbn = {3-540-28761-2}, DOI = {10.1007/10.1007/11551263_21}, booktitle = {Advances in Artificial Intelligence, Proceedings of the 28th German Conference on Artificial Intelligence (KI 2005)}, volume = {3698}, publisher = {Springer-Verlag Berlin Heidelberg}, series = {Lecture Notes in Artificial Intelligence}, pages = {249--263}, tags = {Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2005/Schattenberg05FlexibleStrategiesSlides.pdf}, web_url2 = {http://www.springerlink.com/content/ab18236tekp4wvfu/}, file_url = {http://www.springerlink.com/content/ab18236tekp4wvfu/fulltext.pdf} } @Incollection { Biundo05PlanningUnderTemporalUncertainty, author = {Biundo, Susanne and Holzer, Roland and Schattenberg, Bernd}, title = {Project Planning Under Temporal Uncertainty}, abstract = {This paper presents an approach towards probabilistic planning with continuous time. It adopts stochastic concepts for continuous probabilities and integrates them into an HTN-based planning framework. Based on uncertain time durations associated with primitive tasks the time consumption probabilities of non-linear plans can be accumulated and thus an overall probability for a successful execution of complex plans can be computed. Furthermore, heuristics for the decomposition of abstract tasks can be derived that guide the search towards plans with a minimized average value/variance of their overall time consumption. An example from software project planning is used to demonstrate our approach.}, year = {2005}, booktitle = {Planning, Scheduling, and Constraint Satisfaction: From Theory to Practice}, volume = {117}, publisher = {IOS Press}, series = {Frontiers in Artificial Intelligence and Applications}, editor = {Luis A. Castillo and Daniel Borrajo and Miguel A. Salido and Angelo Oddi}, pages = {189--198}, tags = {Planning}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2004/Biundo04ProjectPlanning.pdf} } @Inproceedings { Biundo04ContinuousResources, author = {Biundo, Susanne and Holzer, Roland and Schattenberg, Bernd}, title = {Dealing with Continuous Resources in AI Planning}, abstract = {This paper presents an approach towards probabilistic planning with continuous resources. It adopts stochastic concepts for continuous probabilities and integrates them into a STRIPS-based planning framework. The approach enables the construction of plans that are guaranteed to meet certain probability thresholds w.r.t. the consumption of critical resources. Furthermore, the consumption probabilities of multiple resources can be accumulated and thus an overall probability for a successful execution of an aggregate plan can be computed. We extend our approach to HTN-based planning and show how heuristics can be derived that lead to plans with a minimized average value/variance of their overallresource consumption.}, year = {2004}, booktitle = {Proceedings of the 4th International Workshop on Planning and Scheduling for Space (IWPSS 2004)}, publisher = {European Space Agency Publications Division}, address = {ESA-ESOC, Darmstadt, Germany}, pages = {213--218}, number = {WPP-228}, tags = {Planning}, file_url = {https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2004/Biundo04ContinuousResources.pdf} } @Inproceedings { Biundo04ProjectPlanning, author = {Biundo, Susanne and Holzer, Roland and Schattenberg, Bernd}, title = {Project Planning Under Temporal Uncertainty}, abstract = {This paper presents an approach towards probabilistic planning with continuous time. It adopts stochastic concepts for continuous probabilities and integrates them into an HTN-based planning framework. Based on uncertain time durations associated with primitive tasks the time consumption probabilities of non-linear plans can be accumulated and thus an overall probability for a successful execution of complex plans can be computed. Furthermore, heuristics for the decomposition of abstract tasks can be derived that guide the search towards plans with a minimized average value/variance of their overall time consumption. An example from software project planning is used to demonstrate our approach.}, year = {2004}, booktitle = {Proceedings of the Workshop on Planning and Scheduling: Bridging Theory to Practice at The 16th European Conference on Artificial Intelligence (ECAI 2004)}, tags = {Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2004/Biundo04ProjectPlanningSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2004/Biundo04ProjectPlanning.pdf} } @Inproceedings { Schattenberg02HierarchicalResources, author = {Schattenberg, Bernd and Biundo, Susanne}, title = {On the Identification and Use of Hierarchical Resources in Planning and Scheduling}, abstract = {Many real-world planning applications have to deal with resource allocation problems, and so does planning in the domain of crisis management assistance. In order to support resource allocation in these kind of applications, we present a new approach to the integration of scheduling capabilities and planning. The proposed methodology relies on a hybrid planner, which combines action and state abstraction by integrating hierarchical task network (HTN) planning and state based partial order causal link (POCL) planning into a common framework. We extend the abstraction mechanism of the planner to different kinds of abstraction for resources, namely subsumption, approximation, qualification, and aggregation. We show how these abstractions can be used when modeling the domain and how reasoning about resources can be performed in a flexible way, namely by merging opportunistic planning and scheduling strategies.}, year = {2002}, booktitle = {Proceedings of the 6th International Conference on Artificial Intelligence Planning Systems (AIPS 2002)}, publisher = {AAAI Press}, pages = {263--272}, tags = {Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2002/Schattenberg02HierarchicalResourcesSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2002/Schattenberg02HierarchicalResources.pdf} } @Inproceedings { Biundo01FromCrisisToRelief, author = {Biundo, Susanne and Schattenberg, Bernd}, title = {From Abstract Crisis to Concrete Relief (A Preliminary Report on Combining State Abstraction and HTN Planning)}, abstract = {Flexible support for crisis management can definitely be improved by making use of advanced planning capabilities. However, the complexity of the underlying domain often causes intractable efforts in modeling the domain as well as a huge search space to be explored by the system. A way to overcome these problems is to impose a structure not only according to tasks but also according to relationships between and properties of the objects involved, thereby using so-called decomposition axioms. We outline the prototype of a system that is capable of tackling planning for complex application domains. It is based on a well-founded combination of action and state abstractions. The paper presents the basic techniques and provides a formal semantic foundation of the approach. It introduces the planning system and illustrates its underlying principles by examples taken from the crisis management domain used in our ongoing project.}, year = {2001}, booktitle = {Proceedings of the 6th European Conference on Planning (ECP 2001)}, publisher = {AAAI Press}, pages = {157--168}, tags = {Planning}, web_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2001/Biundo01FromCrisisToReliefSlides.pdf}, file_url = {http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2001/Biundo01FromCrisisToRelief.pdf} }