Planification dans un espace de buts par stratégie de type meilleur d'abord / Xavier Clerc ; sous la direction de Humbert Fiorino

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Informatique -- Gestion

Traitement réparti

Fiorino, Humbert (Directeur de thèse / thesis advisor)

Institut national polytechnique (Grenoble ; 1900-....) (Organisme de soutenance / degree-grantor)

Relation : Planification dans un espace de buts par stratégie de type meilleur d'abord / Xavier Clerc ; sous la direction de Humbert Fiorino / Grenoble : Atelier national de reproduction des thèses , 2007

Résumé / Abstract : La plupart des systèmes de planification distribuée sont fondés sur des modèles qui ont été développés pour de 1 planification centralisée. Ces modèles ont ensuite été adaptés au contexte de la distribution et aux problèmes pécifiques qui en découlent. Notre objectif est au contraire de développer un modèle de planification qui intègre a priori les contraintes de la distribution. Pour cela, nous développons un modèle de planification utilisant une recherche de type meilleur d'abord (nous adaptons à cette fin des algorithmes de la famille proof-number search). Nous déclinons ce modèle pour la planification d'une part sur des structures de tâches utilisées dans les systèmes multi-agents et d'autres part sur le formalisme HTN. Dans ce second cas, nous montrons en particulier comment une recherche de type meilleur d'abord permet d'accumuler au plus vite des contraintes qui permettent de fermer certaines branches de l'espace de Ia recherche. Nous nous intéressons en outre à la robustesse des plans produits, c'est-à-dire à la capacité d'un groupe ki'agents planifiants à pallier l'absence d'une ressource ou la défaillance d'un agent

Résumé / Abstract : Most of distributed planning systems are based on models which were developped for centralized planning. These models have then been adapted to distribution and its specific contraints. Our goal is at the opposite to design a planning model that considers these constraints as premises. We have developped a planning model that uses a best-first search (as an adaptation of the proof-number search algorithm). We have applied this model to planning over task structures (from multiagent notations) as well as to HTN planning. ln this latter case, we have shown how a best-first search allows the planner to rapidly gather constraints that can prune branches from the search space. We have also defined plan robustness in order to mitigate the consequences of an agent failure or a resource unavailability