Intégration des ressources en planification temporelle optimale
Institution:
ArtoisDisciplines:
Directors:
Abstract EN:
In this thesis, we aim at introducing the management of consumable and renewable resources in temporal, parallel and domain-independent planning. As an application of our work, our purpose is to improve the temporal parallel planner named CPT which is not able to manage resources in its original version. In addition, we want to preserve all the original performances of this planner on temporal planning problems. We focus on the total duration of the plan as the optimization criterion. To express resource constrains, we develop a resource-based formalism in relation of the mutual-exclusion-based one introduced by Smith and Weld and used by the CPT planner to express temporal constraints. We propose two different methods to manage resources in the CPT planner: The first one, based on resource links, requires additional resource constraints which must be respected and can resolve temporal planning problems under resources within remarkable search delays. The second one is based on synchronization actions; it is less restrictive than the first method but it requires many additional propagation rules to speed up the search process. In many cases, the synchronization actions-based method finds temporal optimal parallel plans with better quality than the ones found by the resource links-based method.
Abstract FR:
Dans cette thèse, nous avons pour objectif d’intégrer la gestion des ressources consommables et renouvelables dans la planification temporelle en choisissant comme critère d’optimalité le temps d’exécution totale du plan trouvé. D’un point de vue pratique, nous cherchons à améliorer le planificateur CPT, qui ne gère pas les ressources dans sa version initiale. Nous tenons aussi à conserver les performances initiales de ce planificateur pour résoudre les problèmes de planification temporelle. Pour réaliser ce but nous avons établi un formalisme permettant d’exprimer les contraintes liées aux ressources dans le planificateur CPT. Ce formalisme est en relation étroite avec le formalisme utilisé par ce planificateur pour exprimer les contraintes temporelles. Nous avons proposé deux méthodes différentes pour la gestion des ressources dans le planificateur CPT. La première, basée sur les liens de ressources, exige des contraintes additionnelles pour les ressources qui doivent être respectées. Elle permet de résoudre des problèmes de planification temporelle avec ressources dans des délais très intéressants. La deuxième méthode est basée sur les actions de synchronisation. Elle est moins restrictive que la première méthode et les contraintes qu’elle exige sont moins sévères. Plusieurs règles de propagations des contraintes liées aux ressources ont été introduites avec cette méthode pour accélérer la recherche. Dans beaucoup de cas, cette méthode permet de calculer des plans valides optimaux d’une qualité meilleure que celle de la méthode basée sur les liens de ressources.