Search

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.

International audience; Many Artificial Intelligence techniques have been developed for intelligent and autonomous systems to act and make rational decisions based on perceptions of the world state. Among these techniques, HTN (Hierarchical Task Network) planning is one of the most used in practice. HTN planning is based on expressive languages allowing to specify complex expert knowledge for real world domains. At the same time, many preprocess-ing techniques for classical planning were proposed to speed up the search. One of these technique, named grounding, consists in enumerating and instantiating all the possible actions from the planning problem descriptions. This technique has proven its effectiveness. Therefore, combining the expressiveness of HTN planning with the efficiency of the grounding preprocessing techniques used in classical planning is a very challenging issue. In this paper, we propose a generic algorithm to ground the domain representation for HTN planning. We show experimentally that grounding process improves the performances of state of the art HTN planners on a range of planning problems from the International Planning Competition (IPC).

International audience; De nombreuses techniques de planification ont eté développées pour permettrè a des syst emes autonomes d'agir et de prendre des décisions en fonction de leurs perceptions de l'environnement. Parmi ces techniques, la planification HTN (Hierarchical Task Network) est l'une des techniques les plus utilisées en pratique. Contrairement aux approches classiques de la planifi-cation, la planification HTN fonctionne par décomposition récursive d'une tâche complexe en sous tâches jusqu'` a ce que chaque sous-tâche puissê etre réalisée par l' exécution d'une action. Cette vision hiérarchique de la planification permet une représentation plus riche desprobì emes de planification tout en guidant la recherche d'un plan solution et en apportant de la connaissance aux algorithmes sous-jacents. Dans cet article, nous proposons une nouvelle approche de la planification HTN dans laquelle, comme en planification classique, nous instancions l'ensemble des opérateurs de planification avant d'effectuer la recherche d'un plan solution. Cette approche a fait ses preuves en planification clas-sique. Elle est utilisée par la plupart des planificateurs contemporains mais n'a, ` a notre connaissance, jamais eté appliquée dans le cadre de la planification HTN. L'instanciation des opérateurs de planifica-tion est pourtant nécessaire au développement d'heuristiques efficaces et a l'encodage deprobì emes de planification HTN dans d'autres formalismes tels que SAT ou CSP. Nous présentons dans la suite de l'article un mécanisme générique d'instanciation. Ce mécanisme implémente des techniques de simplification permettant de réduire la complexité du processus d'instanciation inspirées de celles utilisées en planification classique. Pour finir nous présentons des résultats obtenus sur un ensemble deprobì emes issus des compétitions internationales de planification avec une version modifiée du planificateur SHOP utilisant notre technique d'instanciation.