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

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