Gaspard Quenard

Résumé:

La planification automatique est le processus de raisonnement qui organise des actions en anticipant leurs résultats attendus, à partir d’une connaissance a priori
des dynamiques de l’environnement, permettant ainsi aux systèmes autonomes de fonctionner sans intervention humaine. Parmi les différentes approches, la planification
par Réseau de Tâches Hiérarchiques (HTN) est un paradigme puissant pour structurer la résolution de problèmes complexes. En décomposant des tâches abstraites en actions
exécutables, l’approche HTN offre transparence et interprétabilité, des qualités essentielles pour les applications critiques telles que les missions de secours, l’exploration
spatiale ou les opérations sous-marines.
Récemment, il y a eu un regain d’intérêt pour les approches HTN-SAT qui transforment le problème hiérarchique en problème de satisfiabilité propositionnelle (SAT)
de telle sorte qu’une solution satisfiable corresponde à une solution du problème, permettant ainsi d’exploiter les progrès considérables des solveurs SAT modernes.
Toutefois, les planificateurs HTN-SAT actuels souffrent d’une exploration "brute force" en largeur qui entraîne une croissance exponentielle de l’espace de recherche, limitant
leur efficacité pratique face aux méthodes heuristiques traditionnelles. À ce jour, aucune recherche n’a exploré comment associer la puissance des planificateurs HTN-SAT à
des heuristiques pour mieux explorer l’espace de recherche.
L’objectif de cette thèse est d’expliquer comment nous pouvons intégrer des approches heuristiques directement dans le cadre SAT pour la planification HTN. En
utilisant des codages SAT relaxés comme modèles heuristiques, les travaux présentés ici permettent d’évaluer anticipativement les décompositions prometteuses et de ré-
duire drastiquement l’espace de recherche. Les travaux présentés proposent plusieurs approches permettant de trouver des plans rapidement ou de manière optimale pour
la planification hiérarchique. Les évaluations expérimentales démontrent la supériorité de nos méthodes en termes d’efficacité et de qualité des plans générés par rapport aux
planificateurs actuels.