FDP : filtrage et décomposition pour le calcul de plans séquentiels optimaux

Résumé : Dans le domaine de la planification de nombreux systèmes utilisent une représentation de type CSP (problèmes de satisfaction de contraintes). Le planificateur FDP que nous présentons dans cet article, fait partie de cette famille. Mais plutôt que de faire appel à un résolveur de CSP indépendant, FDP travaille directement sur une structure similaire au graphe de planification de GRAPHPLAN, appelée fdp-structure, avec ses propres mécanismes de filtrage et de décomposition, adaptés au domaine spécifique de la planification. Ainsi pour déterminer s'il existe un plan solution, FDP développe itérativement une fdp-structure jusqu'à trouver une solution ou atteindre une taille limite donnée. A chaque extension de la structure un plan est recherché. Différentes stratégies de recherches ont été envisagées. Actuellement, FDP utilise une recherche avant combinée à une décomposition par partitionnement des ensembles d'actions. FDP produit des plans séquentiels optimaux. Il intègre diverses techniques pour réduire l'espace de recherche, notamment pour limiter l'énumération de séquences d'actions redondantes, ou pour détecter des situations déja rencontrées. Comparé à d'autres planificateurs séquentiels optimaux sur des jeux de problèmes connus, FDP apparaît compétitif et régulier.
Type de document :
Communication dans un congrès
Journées Francophones de Programmation par Contraintes, 2006, Nîmes - Ecole des Mines d'Alès, 2006
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00085770
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 08:51:38
Dernière modification le : jeudi 15 mars 2018 - 16:56:06
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:07:49

Fichier

Identifiants

  • HAL Id : inria-00085770, version 1

Collections

Citation

Stéphane Grandcolas, Cyril Pain-Barre. FDP : filtrage et décomposition pour le calcul de plans séquentiels optimaux. Journées Francophones de Programmation par Contraintes, 2006, Nîmes - Ecole des Mines d'Alès, 2006. 〈inria-00085770〉

Partager

Métriques

Consultations de la notice

115

Téléchargements de fichiers

88