D'un plan optimal parallèle vers un plan optimal séquentiel

Résumé : En planification on distingue les plans optimaux en le nombre d'étapes (plans parallèles) et les plans optimaux en le nombre d'actions (plans séquentiels). Il est généralement admis que le calcul d'un plan séquentiel est plus couteux que le calcul d'un plan parallèle. Büttner et Rintanen ont proposé une procédure de recherche qui calcule des plans dont le nombre d'étapes est fixé et le nombre d'actions minimal. Cette procédure est utilisée pour le calcul d'un plan séquentiel optimal partant d'un plan parallèle optimal. Nous décrivons dans cet article une approche de ce type, développée à partir du système de planification FDP. L'idée consiste à maintenir deux structures, l'une représentant le plan parallèle et l'autre le plan séquentiel, en répercutant les choix effectués pendant la recherche simultanément dans les deux structures. Les techniques développées dans FDP pour le calcul de plans séquentiels ou de plans parallèles permettent de détecter les échecs dans les deux structures. Les résultats expérimentaux montrent que cette approche est très compétitive comparée au calcul de plans séquentiels optimaux obtenus avec FDP.