# Pascal Bercher

2003 bis 2009 studierte ich Informatik (Diplom) an der Albert-Ludwigs-Universität Freiburg im Breisgau. Meine Vertiefungsrichtung war Künstliche Intelligenz (KI), meine Subvertiefung innerhalb der KI war/ist das Gebiet der Handlungsplanung. Mein Nebenfach war Kognitionswissenschaft (KW); auch privat bin ich an Psychologie und der Philosophie des Geistes (beides sind Teildisziplinen der KW) interessiert.

Seit Juli 2009 bin ich Doktorand und arbeite in dem Sonderforschungsbereich Transregio 62 (SFB-TRR-62), Teilprojekt A1 (Adaptive Planung und Entscheidungsfindung).

Ich arbeite auf dem Gebiet des Hierarchischen (und im Speziellen des Hybriden) Planens. Hier liegen meine Schwerpunkte in der theoretischen Fundierung der Ansätze, der Entwicklung von Heuristiken zum effizienten Lösen der Probleme, sowie in der praktischen Anwendung des Ansatzes. Weitere Details können meinem Dissertation-Abstract "Hybrid Planning -- Theoretical Foundations and Practical Applications" (ICAPS 2015 Doctoral Consortium) entnommen werden .

# Kontakt

• Pascal.Bercher(at)uni-ulm.de
• Telefon:   +49 (0)731/50-24118
• Telefax:   +49 (0)731/50-24119
• ## Postanschrift

• Pascal Bercher
• Universität Ulm
• Institut für Künstliche Intelligenz
• D-89069 Ulm
• ## Büro

• James-Franck-Ring
• Gebäude O27, 4. Niveau
• Raum 446

# Publikationen

 40 Nothdurft, Florian; Bercher, Pascal; Behnke, Gregor; Minker, Wolfgang User Involvement in Collaborative Decision-Making Dialog Systems In Kristiina Jokinen and Graham Wilcock, Editor, Dialogues with Social Robots: Enablements, Analyses, and Evaluation Herausgeber: Springer, 2017 http://www.springer.com/us/book/9789811025846 Marker: SFB-TRR-62,Planning Zusammenfassung: Abstract Mixed-initiative assistants are systems that support humans in their decision-making and problem-solving capabilities in a collaborative manner. Such systems have to integrate various artificial intelligence capabilities, such as knowledge representation, problem solving and planning, learning, discourse and dialog, and human-computer interaction. These systems aim at solving a given problem autonomously for the user, yet involve the user into the planning process for a collaborative decision-making, to respect e. g. user preferences. However, how the user is involved into the planning can be framed in various ways, using different involvement strategies, varying e. g. in their degree of user freedom. Hence, here we present results of a study examining the effects of different user involvement strategies on the user experience in a mixed-initiative system. Bemerkung: This book chapter was accepted at the 7th International Workshop On Spoken Dialogue Systems (IWSDS 2016) 39 Bercher, Pascal; Höller, Daniel Interview with David E. Smith Künstliche Intelligenz, 30(1):101-105 2016 http://link.springer.com/...10.1007/s13218-015-0403-y Marker: SFB-TRR-62,Planning Bemerkung: Special Issue on Companion Technologies 38 Biundo, Susanne; Höller, Daniel; Bercher, Pascal Special Issue on Companion Technologies Künstliche Intelligenz, 30(1):5-9 2016 http://link.springer.com/...10.1007/s13218-015-0421-9 Marker: SFB-TRR-62,Planning Bemerkung: Special Issue on Companion Technologies 37 Biundo, Susanne; Höller, Daniel; Schattenberg, Bernd; Bercher, Pascal Companion-Technology: An Overview Künstliche Intelligenz, 30(1):11-20 2016 http://link.springer.com/...10.1007/s13218-015-0419-3 Marker: SFB-TRR-62,Planning Bemerkung: Special Issue on Companion Technologies 36 Behnke, Gregor; Höller, Daniel; Bercher, Pascal; Biundo, Susanne Change the Plan - How hard can that be? Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016) , Seite 38--46. Herausgeber: AAAI Press, 2016 Marker: SFB-TRR-62,Planning 35 Höller, Daniel; Behnke, Gregor; Bercher, Pascal; Biundo, Susanne Assessing the Expressivity of Planning Formalisms through the Comparison to Formal Languages Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016) , Seite 158--165. Herausgeber: AAAI Press, 2016 Marker: SFB-TRR-62,Planning 34 Alford, Ron; Behnke, Gregor; Höller, Daniel; Bercher, Pascal; Biundo, Susanne; Aha, David Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems Proceedings of the 26th International Conference on Automated Planning and Scheduling (ICAPS 2016) , Seite 20--28. Herausgeber: AAAI Press, 2016 Marker: SFB-TRR-62,Planning 33 Bercher, Pascal; Höller, Daniel; Behnke, Gregor; Biundo, Susanne More than a Name? On Implications of Preconditions and Effects of Compound HTN Planning Tasks Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016) , Seite 225--233. Herausgeber: IOS Press, 2016 Marker: SFB-TRR-62,Planning,AutomatedReasoning Zusammenfassung: 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. 32 Bercher, Pascal Hybrid Planning -- Theoretical Foundations and Practical Applications Doctoral Consortium at ICAPS 2015 2015 Marker: SFB-TRR-62,Planning Zusammenfassung: The thesis presents a novel set-theoretic formalization of (propositional) hybrid planning – a planning framework that fuses Hierarchical Task Network (HTN) planning with Partial-Order Causal-Link (POCL) planning. Several sub classes thereof are identified that capture well-known problems such as HTN planning and POCL planning. For these problem classes, the complexity of the plan-existence problem is investigated, i.e., the problem of deciding whether there exists a solution for a given planning problem. For solving the problems of the respective problem classes, a hybrid planning algorithm is presented. Its search is guided by informed heuristics. Several such heuristics are introduced, both for POCL planning problems (i.e., problems without task hierarchy) and for hybrid planning problems (i.e., heuristics that are "hierarchy-aware"). 31 Behnke, Gregor; Ponomaryov, Denis; Schiller, Marvin; Bercher, Pascal; Nothdurft, Florian; Glimm, Birte; Biundo, Susanne Coherence Across Components in Cognitive Systems – One Ontology to Rule Them All Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2015) , Seite 1442-1449. Herausgeber: AAAI Press, 2015 Marker: SFB-TRR-62,Planning,AutomatedReasoning Zusammenfassung: 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. 30 Alford, Ron; Bercher, Pascal; Aha, David Tight Bounds for HTN planning with Task Insertion Proceedings of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2015) , Seite 1502--1508. Herausgeber: AAAI Press, 2015 Marker: SFB-TRR-62,Planning Zusammenfassung: Hierarchical Task Network (HTN) planning with Task Insertion (TIHTN planning) is a formalism that hybridizes classical planning with HTN planning by allowing the insertion of operators from outside the method hierarchy. This additional capability has some practical benefits, such as allowing more flexibility for design choices of HTN models: the task hierarchy may be specified only partially, since missing required tasks'' may be inserted during planning rather than prior planning by means of the (predefined) HTN methods. While task insertion in a hierarchical planning setting has already been applied in practice, its theoretical properties have not been studied in detail, yet -- only \EXPSPACE{} membership is known so far. We lower that bound proving \NEXPTIME-completeness and further prove tight complexity bounds along two axes: whether variables are allowed in method and action schemas, and whether methods must be totally ordered. We also introduce a new planning technique called {\em acyclic progression}, which we use to define provably efficient TIHTN planning algorithms. 29 Behnke, Gregor; Bercher, Pascal; Biundo, Susanne; Glimm, Birte; Ponomaryov, Denis; Schiller, Marvin Integrating Ontologies and Planning for Cognitive Systems Proceedings of the 28th International Workshop on Description Logics (DL 2015) Herausgeber: CEUR Workshop Proceedings, 2015 Marker: AutomatedReasoning, Planning, SFB-TRR-62 Zusammenfassung: 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. 28 Alford, Ron; Bercher, Pascal; Aha, David Tight Bounds for HTN planning with Task Insertion (Extended Abstract) Proceedings of the Eighth Annual Symposium on Combinatorial Search (SoCS) , Seite 221--222. Herausgeber: AAAI Press, 2015 Marker: SFB-TRR-62,Planning Zusammenfassung: Hierarchical Task Network (HTN) planning with task insertion (TIHTN planning) is a variant of HTN planning. In HTN planning, the only means to alter task networks is to decompose compound tasks. In TIHTN planning, tasks may also be inserted directly. In this paper we provide tight complexity bounds for TIHTN planning along two axis: whether variables are allowed and whether methods must be totally ordered. 27 Nothdurft, Florian; Behnke, Gregor; Bercher, Pascal; Biundo, Susanne; Minker, Wolfgang The Interplay of User-Centered Dialog Systems and AI Planning Proceedings of the 16th Annual Meeting of the Special Interest Group on Discourse and Dialogue (SIGDIAL) , Seite 344--353. Herausgeber: Association for Computational Linguistics, 2015 Marker: SFB-TRR-62,Planning Zusammenfassung: 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. 26 Bercher, Pascal; Höller, Daniel; Behnke, Gregor; Biundo, Susanne User-Centered Planning - A Discussion on Planning in the Presence of Human Users Proceedings of the First International Symposium on Companion Technology (ISCT 2015) , Seite 79--82. 2015 https://www.uni-ulm.de/fi...5/Bercher15ISCTPoster.pdf Marker: SFB-TRR-62,Planning Zusammenfassung: 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. 25 Behnke, Gregor; Schiller, Marvin; Ponomaryov, Denis; Nothdurft, Florian; Bercher, Pascal; Minker, Wolfgang; Glimm, Birte; Biundo, Susanne A Unified Knowledge Base for Companion-Systems - A Case Study in Mixed-Initiative Planning Proceedings of the First International Symposium on Companion Technology (ISCT 2015) , Seite 43--48. 2015 Schlüsselwörter: SFB-TRR-62,Planning,AutomatedReasoning Marker: SFB-TRR-62,Planning,AutomatedReasoning Zusammenfassung: 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. 24 Alford, Ron; Bercher, Pascal; Aha, David Tight Bounds for HTN Planning Proceedings of the 25th International Conference on Automated Planning and Scheduling (ICAPS 2015) , Seite 7--15. Herausgeber: AAAI Press, 2015 Marker: SFB-TRR-62,Planning Zusammenfassung: Although HTN planning is in general undecidable, there are many syntactically identifiable sub-classes of HTN problems that can be decided. For these sub-classes, the decision procedures provide upper complexity bounds. Lower bounds were often not investigated in more detail, however. We generalize a propositional HTN formalization to one that is based upon a function-free first-order logic and provide tight upper and lower complexity results along three axes: whether variables are allowed in operator and method schemas, whether the initial task and methods must be totally ordered, and where recursion is allowed (arbitrary recursion, tail-recursion, and acyclic problems). Our findings have practical implications, both for the reuse of classical planning techniques for HTN planning, and for the design of efficient HTN algorithms 23 Bercher, Pascal; Richter, Felix; Hörnle, Thilo; Geier, Thomas; Höller, Daniel; Behnke, Gregor; Nothdurft, Florian; Honold, Frank; Minker, Wolfgang; Weber, Michael; Biundo, Susanne A Planning-based Assistance System for Setting Up a Home Theater Proceedings of the 29th National Conference on Artificial Intelligence (AAAI 2015) , Seite 4264--4265. Herausgeber: AAAI Press, 2015 Marker: SFB-TRR-62,Planning Zusammenfassung: 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. 22 Bercher, Pascal; Keen, Shawn; Biundo, Susanne Hybrid Planning Heuristics Based on Task Decomposition Graphs Proceedings of the Seventh Annual Symposium on Combinatorial Search (SoCS 2014) , Seite 35--43. Herausgeber: AAAI Press, 2014 http://www.uni-ulm.de/fil...ybridHeuristicsSlides.pdf Marker: SFB-TRR-62,Planning Zusammenfassung: 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. 21 Honold, Frank; Bercher, Pascal; Richter, Felix; Nothdurft, Florian; Geier, Thomas; Barth, Roland; Hörnle, Thilo; Schüssel, Felix; Reuter, Stephan; Rau, Matthias; Bertrand, Gregor; Seegebarth, Bastian; Kurzok, Peter; Schattenberg, Bernd; Minker, Wolfgang; Weber, Michael; Biundo, Susanne Companion-Technology: Towards User- and Situation-Adaptive Functionality of Technical Systems 10th International Conference on Intelligent Environments (IE 2014) , Seite 378--381. Herausgeber: IEEE, 2014 http://companion.informat...2014/companion-system.mp4 Schlüsselwörter: Adaptive HCI; AI Planning; Dialog Management; Interaction Management; Companion Technology Marker: SFB-TRR-62,Planning,KnowledgeModeling Zusammenfassung: 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. 20 Höller, Daniel; Behnke, Gregor; Bercher, Pascal; Biundo, Susanne Language Classification of Hierarchical Planning Problems In Schaub, Torsten and Friedrich, Gerhard and O'Sullivan, Barry, Editor, Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014) Band 263 aus Frontiers in Artificial Intelligence and Applications , Seite 447-452. Herausgeber: IOS Press, Amsterdam 2014 Marker: SFB-TRR-62,Planning Zusammenfassung: 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. 19 Bercher, Pascal; Biundo, Susanne; Geier, Thomas; Hoernle, Thilo; Nothdurft, Florian; Richter, Felix; Schattenberg, Bernd Plan, Repair, Execute, Explain - How Planning Helps to Assemble your Home Theater Proceedings of the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014) , Seite 386--394. Herausgeber: AAAI Press, 2014 http://www.uni-ulm.de/fil...rExecuteExplainSlides.pdf http://www.uni-ulm.de/fil...likationen/2014/movie.zip Marker: SFB-TRR-62,Planning,KnowledgeModeling Zusammenfassung: 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. Bemerkung: The domain can be downloaded from http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2014/Bercher14PlanRepairExecuteExplain.zip 18 Höller, Daniel; Bercher, Pascal; Richter, Felix; Schiller, Marvin; Geier, Thomas; Biundo, Susanne Finding User-friendly Linearizations of Partially Ordered Plans 28th PuK Workshop "Planen, Scheduling und Konfigurieren, Entwerfen" (PuK 2014) 2014 http://www.uni-ulm.de/fil...anLinearizationSlides.pdf http://www.puk-workshop.de/puk2014/prog.html Schlüsselwörter: Hybrid Planning, POCL Planning, HTN Planning, Plan Linearization, User-centered Planning, User Assistance, Plan Execution Marker: SFB-TRR-62,Planning Zusammenfassung: 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. 17 Pragst, Louisa; Richter, Felix; Bercher, Pascal; Schattenberg, Bernd; Biundo, Susanne Introducing Hierarchy to Non-Hierarchical Planning Models – A Case Study for Behavioral Adversary Models 28th PuK Workshop "Planen, Scheduling und Konfigurieren, Entwerfen" (PuK 2014) 2014 http://www.puk-workshop.de/puk2014/prog.html Schlüsselwörter: Hybrid Planning, Hierarchical Planning, POCL Planning, Domain Modeling, Task Hierarchy, Abstractions Marker: SFB-TRR-62,Planning,KnowledgeModeling Zusammenfassung: 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. 16 Bercher, Pascal; Geier, Thomas; Richter, Felix; Biundo, Susanne On Delete Relaxation in Partial-Order Causal-Link Planning Proceedings of the 2013 IEEE 25th International Conference on Tools with Artificial Intelligence (ICTAI 2013) , Seite 674--681. Herausgeber: IEEE Computer Society, 2013 http://www.uni-ulm.de/fil...rcher13SampleFFSlides.pdf Marker: SFB-TRR-62,Planning Zusammenfassung: 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.
Export als: BibTeX, XML

# Betreuungen

Ich habe diverse Bachelor-/Master- und Diplomarbeiten ausgeschrieben sowie einige HiWi-Jobs. Siehe: