Search

AI Planning is a core technology in enabling advanced assistance for human users. When faced with complex problems such as handicraft tasks for household repairs, Do-It-Yourself projects, or difficult assembly tasks, a planning-based assistance system can provide individualised and context-dependent instructions. It thus effectively supports the user in achieving his or her goals. High-quality assistance should in addition conform to the user���s current wishes and preferences to ensure maximum utility. This can be achieved by involving the user into the planning process, i.e. by making planning mixed-initiative. Hierarchical Task Network (HTN) planning is a method particularly well suited for providing user support, as it resembles the means and structures humans use for problem solving. We identified two major challenges that every mixed-initiative HTN planning system must face and show how to address them: generating plans quickly and flexibly altering them according to the user's demands. The main focus of this thesis lies on addressing the first challenge, i.e. on developing a quickly responding and efficient HTN planner. Designing efficient HTN planners is particularly difficult. Their algorithms have to take both dimensions of the problem description - state and hierarchy - into account and have to consider interactions between them. We use a translation into propositional logic, enabling for the first time a uniform view on the whole planning problem. First, we describe a new encoding for totally-ordered HTN planning, before extending it in two consecutive steps to capture general, partially-ordered domains. Second, we introduce Path Decomposition Trees (PDTs) and Solution Order Graphs (SOGs) which enable a compact encoding and alleviate unnecessary reasoning from a SAT solver. They also pave the way for future insights into structural properties of HTN planning problems, which allow for more efficient planning as well as for more advanced user support. Third, we show that our encodings are a significant empirical improvement over the current state of the art in HTN planning. Lastly, we present a fundamental technique for optimal HTN planning - which is especially important in assistance scenarios - namely a method to compute succinct depth bounds for plan-length optimisation. In a mixed-initiative planning environment, users will frequently request the planner to change a currently considered plan. We start solving this second challenge by considering the most basic task involved: to verify that the changed plan is a solution to the planning problem at hand. First, we show that this task is NP-complete. Second, we develop the first plan verifier for HTN planning, which is based on a transformation into propositional logic. Third, we analyse and categorise the requests possibly made by a user and show that the objectives posed by her or him can be suitably represented as formulae in Linear Temporal Logic (LTL). Fourth, we analyse the computational complexity of changing a plan, showing that this task can be between NP-complete and undecidable. Lastly, we use our SAT-based planner to change a plan with respect to a request formulated as an LTL formula. We show that the full spectrum of LTL formulae can be supported efficiently in a propositional encoding. For that, we introduce a new theoretical foundation for reasoning about parallelism in LTL traces. The practical applicability of our techniques has been demonstrated within a joint transfer project with Robert Bosch GmbH. In it, we developed an assistance system that guides novice users through a handicraft Do-It-Yourself project. The underlying hierarchical planning model is highly complex. Currently the only planner that is able to find plans for this model within an acceptable time frame is the SAT-based HTN planner developed as part of this thesis.

The concept of complex IT systems includes all systems consisting of a large number of inter-connected and computer-managed components. The configuration and management of these systems involves a multitude of tasks that are critical to their proper functioning and their evolution. The problem of defining procedures for managing and configuring such systems becomes very critical in view of their increasing complexity and their rapid evolution. The aim of this thesis is to develop a mixed-initiative planning tool for the automatic co-generation of a set of management and configuration actions, regardless of the application domain. In this perspective, we develop GTOHP, a hierarchical automatic planner, with HTN, that present the high performance needed for a mixed-initiative interaction. We propose an algorithm for the instantiation and the simplification of HTN planning problems, which significantly reduces their complexity and improves the performance of the planning algorithms. We also propose an extension to the « Planning Domain Definition Language » (PDDL) in order to modelize the knowledge of domain experts in the form of tasks decomposition methods that will be used to guide the HTN planning algorithm. Then, we integrate some mechanisms to GTOHP for collecting statistics and information about the tests results carried out during the plans search and integrate them into the MIP which provides several features of mixed-initiative interaction. We demonstrate the high performance of the GTOHP planner and the contributions of the instantiation and simplification algorithm, by comparing them to a state-of-the-art HTN planner through a series of experiments on planning domains from the international planning competitions. Finally, we propose a panel of evaluation criteria of mixed-initiative systems that serve as a basis for the discussion about the performances and contributions of the MIP system.; Le concept de systèmes informatisés complexes rassemble tous les systèmes constitués d’un grand nombre de composantes inter-connectées et gérées par ordinateur. La configuration et la gestion de ces systèmes passe par une multitude de tâches critiques à leur bon fonctionnement et leur évolution. La problématique de la mise en place et la maîtrise des procédures de gestion et de configuration de tels systèmes devient un point critique au vu de la complexité croissante et du besoin d’évolution de ces derniers. L’objectif de cette thèse est de répondre à cette problématique, à travers le développement d’un outil de planification en mixed-initiative pour la co-génération automatique d’actions de gestion et de configuration, indépendamment du domaine d’application. Dans cette perspective, nous développons « Grounded Totally Ordered Hierarchical Planner » (GTOHP), un planificateur automatique hiérarchique, en « Hierarchical Task Network » (HTN), qui présente des performances élevées nécessaires à une interaction en mixed-initiative. Pour cela nous proposons un algorithme d’instanciation et de simplification des problèmes de planification HTN qui réduit de manière très significative leur complexité et améliore de ce fait les performances des algorithmes de planification. Nous proposons aussi une extension au langage de définition des domaines de planification automatique PDDL afin de modéliser les connaissances des experts du domaine d’application sous forme de méthodes de décomposition des tâches qui serviront à guider l’algorithme de planification HTN. Ensuite, nous intégrons au planificateur GTOHP des mécanismes de récolte de statistiques et d’in- formations sur les résultats des tests réalisés lors de la recherche de plans et nous l’intégrons dans le système « Mixed-Initiative Planner » (MIP) qui fournit plusieurs fonctionnalités d’interaction en mixed-initiative. Nous démontrons les performances élevées du planificateur GTOHP et les apports de l’algorithme d’instanciation et de simplification en le comparant à un planificateur HTN de l’état de l’art à travers une série d’expérimentations sur des domaines de planification issues de la compé- tition internationale de planification automatique. Enfin, nous proposons des critères d’évaluation pour les systèmes en mixed-initiative qui servent de base à la discussion du système MIP.

The concept of complex IT systems includes all systems consisting of a large number of inter-connected and computer-managed components. The configuration and management of these systems involves a multitude of tasks that are critical to their proper functioning and their evolution. The problem of defining procedures for managing and configuring such systems becomes very critical in view of their increasing complexity and their rapid evolution. The aim of this thesis is to develop a mixed-initiative planning tool for the automatic co-generation of a set of management and configuration actions, regardless of the application domain. In this perspective, we develop GTOHP, a hierarchical automatic planner, with HTN, that present the high performance needed for a mixed-initiative interaction. We propose an algorithm for the instantiation and the simplification of HTN planning problems, which significantly reduces their complexity and improves the performance of the planning algorithms. We also propose an extension to the « Planning Domain Definition Language » (PDDL) in order to modelize the knowledge of domain experts in the form of tasks decomposition methods that will be used to guide the HTN planning algorithm. Then, we integrate some mechanisms to GTOHP for collecting statistics and information about the tests results carried out during the plans search and integrate them into the MIP which provides several features of mixed-initiative interaction. We demonstrate the high performance of the GTOHP planner and the contributions of the instantiation and simplification algorithm, by comparing them to a state-of-the-art HTN planner through a series of experiments on planning domains from the international planning competitions. Finally, we propose a panel of evaluation criteria of mixed-initiative systems that serve as a basis for the discussion about the performances and contributions of the MIP system.; Le concept de systèmes informatisés complexes rassemble tous les systèmes constitués d’un grand nombre de composantes inter-connectées et gérées par ordinateur. La configuration et la gestion de ces systèmes passe par une multitude de tâches critiques à leur bon fonctionnement et leur évolution. La problématique de la mise en place et la maîtrise des procédures de gestion et de configuration de tels systèmes devient un point critique au vu de la complexité croissante et du besoin d’évolution de ces derniers. L’objectif de cette thèse est de répondre à cette problématique, à travers le développement d’un outil de planification en mixed-initiative pour la co-génération automatique d’actions de gestion et de configuration, indépendamment du domaine d’application. Dans cette perspective, nous développons « Grounded Totally Ordered Hierarchical Planner » (GTOHP), un planificateur automatique hiérarchique, en « Hierarchical Task Network » (HTN), qui présente des performances élevées nécessaires à une interaction en mixed-initiative. Pour cela nous proposons un algorithme d’instanciation et de simplification des problèmes de planification HTN qui réduit de manière très significative leur complexité et améliore de ce fait les performances des algorithmes de planification. Nous proposons aussi une extension au langage de définition des domaines de planification automatique PDDL afin de modéliser les connaissances des experts du domaine d’application sous forme de méthodes de décomposition des tâches qui serviront à guider l’algorithme de planification HTN. Ensuite, nous intégrons au planificateur GTOHP des mécanismes de récolte de statistiques et d’in- formations sur les résultats des tests réalisés lors de la recherche de plans et nous l’intégrons dans le système « Mixed-Initiative Planner » (MIP) qui fournit plusieurs fonctionnalités d’interaction en mixed-initiative. Nous démontrons les performances élevées du planificateur GTOHP et les apports de l’algorithme d’instanciation et de simplification en le comparant à un planificateur HTN de l’état de l’art à travers une série d’expérimentations sur des domaines de planification issues de la compé- tition internationale de planification automatique. Enfin, nous proposons des critères d’évaluation pour les systèmes en mixed-initiative qui servent de base à la discussion du système MIP.

The work described in this document has been carried out in the frame of the @LIS TechNET project, which aims to create a live network across Europe and Latin America as a new, virtual, and interactive learning environment, based on software-agent technology. The purpose of this document is to describe a visualization tool developed for the TechNET's planning system. As background, this document also briefly describes what mixed-initiative planning is.

The University of Edinburgh and research sponsors are authorised to reproduce and distribute reprints and on-line copies for their purposes notwithstanding any copyright annotation hereon. The views and conclusions contained herein are the author’s and shouldn’t be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of other parties. The teamwork research defines several important concepts regarding the design of agents so that they are in fact able to play as members of a collaborative group. Currently such research has been focused on multiagent domains, where agents have full autonomy to take decisions. However this model is not common in real applications where humans may wish to be in control for critical decisions. This paper discusses the use of a constraint-based ontology to create models of mixed-initiative interaction for teamworks. Furthermore we show a practical application on how hierarchical users can use this approach during operations in critical domains.