Bienvenue sur ArTeMIS, la plate-forme d’archivage et de diffusion des thèses et mémoires de l’ISAE-SUPAERO.
Vous y trouverez les thèses soutenues à Supaero depuis 1979 et à l’ISAE-SUPAERO depuis 2007 ayant fait l´objet d´une numérisation ou d´un dépôt électronique et pour lesquelles nous avons obtenu l’autorisation de diffusion.
???menu.label.??? > ???menu.label..??? fr| en
Artemis
  • A propos
  • Contact
  • Recherche
  • simple
  • Tous les mots:
  • avancée
  • Consulter par
  • auteur
  • année
  • thématique
  • laboratoire
  • équipe de recherche
  • école doctorale
Version imprimable
Décomposition des problèmes de planification de tâches basée sur les landmarks
(Planning problem decomposition using landmarks)

Vernhes, Simon
2014-12-12

Institut Supérieur de l'Aéronautique et de l'Espace
Directeur(s) de thèse:  Verfaillie, Gérard; Vidal, Vincent
Laboratoire :  Département Commande des Systèmes et Dynamique du vol -DCSD (depuis 1997)
Ecole doctorale :  Systèmes -EdSys

Classification : Informatique
Accès : Texte intégral

Mots-clés : Planification de tâches, Landmarks, Algorithmes de recherche, Intelligence artificielle

Résumé : Les algorithmes permettant la création de stratégies efficaces pour la résolution d’ensemble de problèmes hé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 interagir avec son environnement de façon autonome afin d’atteindre les buts qui lui ont été assignés. À partir d’une description 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 dans lequel évolue le système vers un état qui satisfait les buts qu’on lui a fixés. Le problème de planification est en général difficile à résoudre (PSPACE-difficile), cependant certaines propriétés des problèmes peuvent être automatiquement 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és sur les landmarks. Un landmark est un fluent qui doit être vrai à un certain moment durant l’exécution de n’importe quel plan solution. L’algorithme LMBFS découpe le problème principal en un ensemble de sous-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 de l’algorithme. Enfin, nous avons testé et comparé chacune de ces méthodes permettant ainsi la création d’un planificateur efficace.

Résumé (anglais) : The algorithms allowing on-the-fly computation of efficient strategies solving a heterogeneous set of problems has always been one of the greatest challenges faced by research in Artificial Intelligence. To this end, classical planning provides to a system reasoning capacities, in order to help it to interact with its environment autonomously. Given a description of the world current state, the actions the system is able to perform, and the goal it is supposed to reach, a planner can compute an action sequence yielding a state satisfying the predefined goal. The planning problem is usually intractable (PSPACE-hard), however some properties of the problems can be automatically extracted allowing the design of efficient solvers. Firstly, we have developed the Landmark-based Meta Best-First Search (LMBFS) algorithm. Unlike state-of-the-art planners, usually based on state-space heuristic search, LMBFS reenacts landmark-based planning problem decomposition. A landmark is a fluent appearing in each and every solution plan. The LMBFS algorithm splits the global problem in a set of subproblems and tries to find a global solution using the solutions found for these subproblems. Secondly, we have adapted classical planning techniques to enhance the performance of our base algorithm, making LMBFS a competitive planner. Finally, we have tested and compared these methods.


Langue : Français
Exporter au format XML
© 2006-2010 ORI-OAI
thèses ISAE,theses ISAE,thèse ISAE,these ISAE, thèses Institut Supérieur de l'Aéronautique et de l'Espace,thèse Institut Supérieur de l'Aéronautique et de l'Espace,,theses Institut Supérieur de l'Aéronautique et de l'Espace,,these Institut Supérieur de l'Aéronautique et de l'Espace, thèses aéronautique,thèse aéronautique,these aéronautique,,theses aéronautique, Artemis,Arthemis, thèses DAEP,thèses DMIA,thèses DMSM, thèses DEOS,thèses CAS,thèses LACS, thèse DAEP,thèse DMIA,thèse DMSM, thèse DEOS,thèse CAS,thèse LACS, these DAEP,these DMIA,these DMSM, these DEOS,these CAS,these LACS, theses DAEP,theses DMIA,theses DMSM, theses DEOS,theses CAS,theses LACS, thèses toulouse,thèse toulouse,theses toulouse,these toulouse, thèses supaero,thèse supaero,theses supaero,these supaero, thèses école nationale supérieure d'aéronautique,thèse école nationale supérieure d'aéronautique,theses école nationale supérieure d'aéronautique,these école nationale supérieure d'aéronautique, thèses ingénieur,thèse ingénieur,theses ingénieur,these ingénieur, phd thesis ISAE, phd thesis Institut Supérieur de l'Aéronautique et de l'Espace, phd thesis aéronautics, phd thesis DAEP,phd thesis DMIA,phd thesis DMSM,phd thesis DEOS,phd thesis CAS,phd thesis LACS, phd thesis toulouse,phd thesis supaero,phd thesis école nationale supérieure d'aéronautique,