Dr. Pascal Bercher

I am a Lecturer researching in the area of Planning & Optimization. I've joined ANU in November 2019, and in the first year I'm probably not going to give lectures but focus on research and supervision instead. I've done my PhD (Dr. rer. nat.) under the supervision of Prof. Dr. Susanne Biundo-Stephan at the Intitute of Artificial Intelligence at Ulm University, Germany from mid of 2009 to the end of 2017. I've studied Computer Science from the end of 2003 to the mid of 2009 at the University of Freiburg, Germany.

Reserarch:

Im doing research in the fields of hierarchical planning and Partial Order Causal Link (POCL) planning. I'm interestested in theoretical foundations (mostly complexity analyses), algorithms and heuristics, and, lastly, practical applications of planning. For a more detailed description of my research interests see the respective tab.

Some News:

  • I'm going to announce several opportunities for a fully funded PhD under my supervision in the areas of Hierarchical Planning. Drop me an email or re-visit this page again in case you are interested!
  • I'm co-organizing the IPC 2020 together with Gregor Behnke and Daniel Höller. It's about Hierarchical Task Network (HTN) planning. More information: http://ipc2020.hierarchical-task.net

 

As my thesis, my research interestes span from theory to practice -- content-wise all is concerned with either Hierarchical Task Network (HTN) planning or Partial Order Causal Link (POCL) planning.

Hierarchical Task Network Planning

Short explanation of HTN planning: HTN planning is an approach to planning that's centered around problem decomposition. We are given an initial task network -- a partially ordered set of primitive or compound (or abstract) tasks. Primitive tasks are the actions known from classical planning, i.e. they specify preconditions and effects stating in which states they are applicable and how they chance a state if applied. Compound tasks are just abstracts of pre-defined task networks, so they are essentially just (parametrized) names like go(Canberra,Sydney). The planning model specifies rules how they can be achieved. These rules, called decomposition methods, are simply mappings to pre-defined task networks, which can in turn contain compound tasks. The goal is to refine the initial task netowork into a primitive one that is executable. HTN planning is more expressive than classical planning, where this mechanism of task decomposition does not exist. In its most general form (as just explained) it's undecidable.

My research interests in HTN planning are, roughly ordered my interest:

  • Design of well-informed heuristics. (This is still a young field with only a limited number of heuristics availaible.)
  • Investigation of the computational complexity of various problems like the plan existence problem (how hard is it do decide whether there exists a solution?)
  • Essentially all questions that are related to incorporating human users into the loop. These comprise:
    • Plan abstraction and presentation (how can plans be presented on a more abstract level? can we stop planning on more abstract levels?)
    • Plan linearization and presentation (in which order should plan steps be presented to a human user so that the pan's execution order seems reasonable?)
    • Plan explanations (how to find reasonable explanations for plans and how they look like?)

Partial Order Causal Link (POCL) Planning

Short explanation of POCL planning: POCL planning is a technique for solving classical panning problems, where we would like to find a plan in order to achieve some (state-based) goals. In POCL planning, this is done in the space of partially ordered (also called non-linear) plans. Search is done in a regression-like fashion starting with the goals: select a condition not yet achieved (called "open") and select an appropriate action (i.e., with matching effect) from the plan or model and "document" that goal achievement by the insertion of a so-called causal link. Tis procedure is repeated until a goal plan has been found. Since search nodes are partially ordered plans (rather than states as in standard progression search), heuristic desingn is much more complicated.

Some mor ebackground of POCL planning: Since roughly 15 years this kind of problem solving is generally regarded outdated (some even say obsolete!) because state-based progression search is simply much more efficient nowadays. However, this argument is a purely empirial one. Moreover, there is a vast variety of well-informed heuristics in classical state-based planning, but almonst none exist in POCL planning. Hence, it's interesting to imagine where POCL could be by now if we had as well-informed heuristics for that search as well. (Whether this can even be is another question, as some of my theoretical results indicate that heuristic design is computationally harder than in the progression setting.) Another important note to make is that POCL techniques are still used in hierarchical planning, as one of the few standard techniques for solving HTN problems relies on POCL planning techniques.

My research interests in POCL planning are, roughly ordered my interest:

  • Design of well-informed heuristics. (Again, almos no heuristics exist so far!)
  • Investigation of the computational complexity related to POCL plans (such as the plan existence or plan opimization.)

Practical Application

Well, most that I am intersted in is already covered above as part of HTN planning: When ever one integrates a human into the loop, several new questions arise that need to be addressed in a systematic way. For instance, once we have found a solution to a problem (i.e., a plan) that plan can be executed successfully as otherwise it wouldn't be a solution. However, for a human it might be a big difference in which order its actions are executed (by him or her) since there might be a switch of contexts that could be confusing or even annoying. Finding a reasonable (we called it "user-friendly") reordering is one such task that can be investigated on both a formal and an empircal level. Other related questions, as mentioned above, are the presentation of plans on higher levels of abstraction and the explanation of plans.

Another important aspect in the practical application of planning technology is the planning language's level of expressiveness. In order to solve real-world problems, we need to be able to express time (at the least!) or more generally functions. This will require new formalisms, reductions, and heuristics.

I'll only provide a list of selected publications here. For further publications, please refer to my DBLP and google scholar page for now (a complete list will be provided here soon).

Selected publications:
(with me as first or last author)

  • Pascal Bercher, Ron Alford, Daniel Höller: A Survey on Hierarchical Planning – One Abstract Idea, Many Concrete Realizations. IJCAI 2019, p.6267-6275. ijcai.org
  • Conny Olz, Pascal Bercher: Eliminating Redundant Actions in Partially Ordered Plans – A Complexity Analysis. ICAPS 2019, p.310-319. AAAI Press
  • Pascal Bercher, Gregor Behnke, Daniel Höller, Susanne Biundo: An Admissible HTN Planning Heuristic. IJCAI 2017, p.480-488. ijcai.org
  • Pascal Bercher, Daniel Höller, Gregor Behnke, Susanne Biundo: More than a Name? On Implications of Preconditions and Effects of Compound HTN Planning Tasks. ECAI 2016. p.225-233. IOS Press
  • Pascal Bercher, Susanne Biundo, Thomas Geier, Thilo Hoernle, Florian Nothdurft, Felix Richter, Bernd Schattenberg: Plan, Repair, Execute, Explain – How Planning Helps to Assemble your Home Theater. ICAPS 2014, p.386-394. AAAI Press
  • Thomas Geier, Pascal Bercher: On the Decidability of HTN Planning with Task Insertion. IJCAI 2011, p.1955-1961. AAAI Press.

Selected publications:
(with me as co-author)

  • Daniel Höller, Pascal Bercher, Gregor Behnke, Susanne Biundo: A Generic Method to Guide HTN Progression Search with Classical Heuristics. ICAPS 2018. p. 114-122. AAAI Press (won best student paper award)
  • Daniel Höller, Gregor Behnke, Pascal Bercher, Susanne Biundo: Plan and Goal Recognition as HTN Planning. ICTAI 2018. p.466-473. IEEE Press (won best paper award)
  • Daniel Höller, Gregor Behnke, Pascal Bercher, Susanne Biundo: Assessing the Expressivity of Planning Formalisms through the Comparison to Formal Languages. ICAPS 2016. p.158-165. AAAI Press
  • Ron Alford, Gregor Behnke, Daniel Höller, Pascal Bercher, Susanne Biundo, David W. Aha: Bound to Plan: Exploiting Classical Heuristics via Automatic Translations of Tail-Recursive HTN Problems. ICAPS 2016. p.20-28. AAAI Press
  • Ron Alford, Pascal Bercher, David W. Aha: Tight Bounds for HTN Planning. ICAPS 2015: p.7-15. AAAI Press
  • Ron Alford, Pascal Bercher, David W. Aha: Tight Bounds for HTN Planning with Task Insertion. IJCAI 2015. p.1502-1508. AAAI Press

Dissertation:

  • Cooperation Award: Science – Economy 2019
    The research project Do it yourself, but not alone: Companion-Technology for Home Improvement" that was coordinated by me for its entire runtime from 2016 to 2019 won Ulm University's "Cooperation Award: Science – Economy 2019" (German: Kooperationspreis: Wissenschaft – Wirtschaft 2019).
     
  • ICAPS 2019 Best Dissertation Award
    For my dissertation Hybrid Planning -- From Theory to Practice
     
  • AAAI 2019 Outstanding Program Committee Member
     
  • Theoretical Computer Science Outstanding Reviewer Award (Elsevier journal)
    (Year omitted to maintain anonymity.)
     
  • ICAPS 2018 Best Student Paper Award
    For the paper A Generic Method to Guide HTN Progression Search with Classical Heuristics by Daniel Höller, Pascal Bercher, Gregor Behnke, and Susanne Biundo, published at the International Conference of Planning and Scheduling (ICAPS)
     
  • ICTAI 2018 Best Paper Award
    For the paper Plan and Goal Recognition as HTN Planning by Daniel Höller, Gregor Behnke, Pascal Bercher, and Susanne Biundo, published at the International Conference on Tools in Artificial Intelligence (ICTAI)
     
  • TCST 2018 Best Paper Award
    For the paper Towards a Companion System Incorporating Human Planning Behavior -- A Qualitative Analysis of Human Strategies by Benedikt Leichtmann, Pascal Bercher, Daniel Höller, Gregor Behnke, Susanne Biundo, Verena Nitsch, and Martin Baumann, published at the Transdisciplinary Conference on Support Technologies (TCST)
     
  • Nomination for the GI Best Dissertation Award 2017
    Ulm University nominated my dissertation for the GI Best Dissertation Award 2017, a national award (joint with the GI Germany, Switzerland, and Austria) for the best dissertation in the field of Computer Science. The GI (Gesellschaft für Informatik, eng: Society for Computer Science) encourages nominations that make progress in the field of Computer Science or related practical-oriented areas; they should further have some impact on the today's society. The final winners were announced here. My 10-page dissertation abstract (in German), as well as all other nomitated dissertations, are published in the Proceedings "Ausgezeichnete Informatikdissertationen" (eng: Awarded Computer Science Dissertations).
     
  • Paper Presentation at Press Conference of AAAI 2015
    I was presenting my system demo paper "A Planning-based Assistance System for Setting Up a Home Theater" (AAAI 2015) at a press conference that was hold during the AAAI conference 2015. They selected five papers that are of interest to the public due to their relevance for today's society.

 

Reviewing:

Reviewer for journals:
(Years omitted to maintain anonymity.)

  • Theoretical Computer Science (awarded for outstanding reviewing)
  • IEEE Transactions on Systems, Man and Cybernetics: Systems
  • KI – Künstliche Intelligenz

Senior Program Committee (SPC) member at conferences:

  • ICAPS: 2019

Program Committee (PC) member at conferences:

  • IJCAI: 2013, 2019
  • IJCAI-ECAI: 2018
  • ECAI: 2020
  • AAAI: 2015, 2017–2019 (honored as outstanding PC member 2019)

Program Committee (PC) member at workshops:

  • ICAPS-Hiearchical Planning: 2018, 2019

Reviewer for conferences (in addition to the PC/SPC memberships):

  • ICAPS: 2012, 2015–2018
  • ECAI: 2016
  • AAAI: 2012, 2014
  • KI: 2012–2013

Reviewer for workshops:

  • Computer Games Workshop: at IJCAI 2017

 

Invited Talks:

  • I gave a keynote speech about Companion Systems at the Digital Companion Workshop at MuC (Mensch und Computer; eng.: Human and Computer) 2018 in Dresden, Germany
  • KI 2017, where I presented my 2017 IJCAI paper "An admissible HTN planning heuristic" in the "sister conference track".
  • In November 2017, I was invited to discuss the potentials and risks of AI in a so-called Junior Science Working Group of a high school in Fulda, Germany, in a plenum discussion together with other experts on the field (Prof. Dr. Gepperth, Prof. Dr. Winzerling, and Dr. Quarch).

 

Further services to the University and the AI community:

  • I am supporting my former colleagues Gregor Behnke and Daniel Höller in the organization of the IPC 2020 on Hierarchical Task Network (HTN) Planning. For more information see http://ipc2020.hierarchical-task.net.
  • I was in the appointment committee for the new Junior Professorship in Explainable Artificial Intelligence at Ulm University, Germany in 2019.
  • I was the initiator of the ICAPS Workshop for Hierarchical Planning – to the best of our knowledge the very first workshop dedicated to hierarchical planning.
  • Together with Daniel Höller, I gave the first Tutorial on HTN Planning at ICAPS 2018. Here, you can download the slides.
  • I was a guest editor for the journal "KI - Künstliche Intelligenz" for the Special Issue on Companion-Technologies, which appeared in February 2016.
  • I was in charge of creating a video that promotes a planning-based assistant for setting up a complex home theater. The video further explains the applied scientific technologies for a not necessarily scientific audience.

Updated:  1 June 2019/Responsible Officer:  Head of School/Page Contact:  CECS Marketing