Mixed-Initiative Hierarchical Planning - Challenges and Solutions
University of Ulm, Germany
Modern assistance systems provide users with instructions that, if followed, will achieve their goals. For example, they can assist in setting up an ensemble of HiFi devices, planning a workout schedule, or doing a DIY project. Instructions are often generated by an AI planner using hierarchical (HTN) planning, as such plans are suited for interaction with humans.
So far, most employed planners produce these instructions without any further input from or interaction with the user. Good assistance, however, has to be adapted to the user’s individual wishes and preferences to ensure maximum utility. I will discuss mixed-initiative planning, which incorporates the user into the planning process and allows for the direct integration of user wishes, preferences, and the user's domain-specific knowledge. I will address general considerations and elaborate on three main capabilities an AI planner must possess when used in such a system: fast generation of plans, altering plans according to the user's instructions, and explaining plans.
I present a theoretical investigation of user instructions, which we classified for this purpose by intended outcome and allowed additional changes. Inspired by these results, we have developed a new HTN planner, which solves planning problems by a translation into a sequence of SAT formulae. We have shown that this new planner outperforms all currently existing HTN planning systems, some of them significantly.
Lastly, I will present a technique for answering the user's instructions to a plan based on our newly developed planner. Due to its declarative nature, new constraints and restrictions can easily be added to the SAT encoding and thus form a good basis for answering requests to change a plan by the user.
In general, the requests can be interpreted as formulae in Linear Temporal Logic (LTL). I will propose a novel technique for translating LTL formulae into additional clauses for SAT-based planners.
Gregor Behnke received his MSc. in Computer Science in 2014 from the University of Rostock. He received a gold and a silver medal in the North-Eastern European Contest of the ACMs ICPC. He has been a PhD student at Ulm University's Institute of AI under the supervision of Prof. Dr. Biundo since 2014. He has been part of the Transregional Collaborative Research Centre SFB/TRR 62 "Companion-Technology for Cognitive Technical Systems" funded by the German Research Foundation (DFG). Currently, he is working in the industry transfer-project "Do it yourself, but not alone" in collaboration with the Robert Bosch GmbH.