Les algorithmes permettant la création de stratégies efficaces pour la résolution d’ensemble de problèmeshétéroclites ont toujours été un des piliers de la recherche en Intelligence Artificielle. Dans cette optique,la planification de tâches a pour objectif de fournir à un système la capacité de raisonner pour interagiravec son environnement de façon autonome afin d’atteindre les buts qui lui ont été assignés. À partir d’unedescription de l’état initial du monde, des actions que le système peut exécuter, et des buts qu’il doit atteindre,un planificateur calcule une séquence d’actions dont l’exécution permet de faire passer l’état du monde danslequel évolue le système vers un état qui satisfait les buts qu’on lui a fixés. Le problème de planification esten général difficile à résoudre (PSPACE-difficile), cependant certaines propriétés des problèmes peuvent êtreautomatiquement extraites permettant ainsi une résolution efficace.Dans un premier temps, nous avons développé l’algorithme LMBFS (Landmark-based Meta Best-First Search).À contre-courant des planificateurs state-of-the-art, basés sur la recherche heuristique dans l’espace d’états,LMBFS est un algorithme qui réactualise la technique de décomposition des problèmes de planification baséssur les landmarks. Un landmark est un fluent qui doit être vrai à un certain moment durant l’exécutionde n’importe quel plan solution. L’algorithme LMBFS découpe le problème principal en un ensemble desous-problèmes et essaie de trouver une solution globale grâce aux solutions trouvées pour ces sous-problèmes.Dans un second temps, nous avons adapté un ensemble de techniques pour améliorer les performances del’algorithme. Enfin, nous avons testé et comparé chacune de ces méthodes permettant ainsi la création d’unplanificateur efficace. / The algorithms allowing on-the-fly computation of efficient strategies solving aheterogeneous set of problems has always been one of the greatest challengesfaced by research in Artificial Intelligence. To this end, classical planningprovides to a system reasoning capacities, in order to help it to interact with itsenvironment autonomously. Given a description of the world current state, theactions the system is able to perform, and the goal it is supposed to reach, a plannercan compute an action sequence yielding a state satisfying the predefined goal. Theplanning problem is usually intractable (PSPACE-hard), however some propertiesof the problems can be automatically extracted allowing the design of efficientsolvers.Firstly, we have developed the Landmark-based Meta Best-First Search (LMBFS)algorithm. Unlike state-of-the-art planners, usually based on state-space heuristicsearch, LMBFS reenacts landmark-based planning problem decomposition. Alandmark is a fluent appearing in each and every solution plan. The LMBFSalgorithm splits the global problem in a set of subproblems and tries to find aglobal solution using the solutions found for these subproblems. Secondly, wehave adapted classical planning techniques to enhance the performance of ourbase algorithm, making LMBFS a competitive planner. Finally, we have tested andcompared these methods.
| Identifer | oai:union.ndltd.org:theses.fr/2014ESAE0050 |
| Date | 12 December 2014 |
| Creators | Vernhes, Simon |
| Contributors | Toulouse, ISAE, Verfaillie, Gérard, Vidal, Vincent |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0036 seconds