Search

La planification automatique est un domaine de recherche de l’Intelligence Artificielle qui vise à calculer automatiquement une séquence d’actions menant d’un état initial donné à un but souhaité. Cependant, résoudre des problèmes réalistes est généralement difficile car trouver un chemin solution peut demander d’explorer un nombre d’états croissant exponentiellement avec le nombre de variables. Pour faire face à cette explosion combinatoire, les algorithmes performants ont recours aux heuristiques ou à des solutions hiérarchiques, décomposant le problème en sous-problèmes plus petits et plus simples. Dans une grande majorité des cas, le planificateur doit prendre en compte un certain nombre de contraintes telles que des phases d’actions prédéfinies ou des protocoles. Ces contraintes aident à résoudre le problème en élaguant un grand nombre de branches de l’arbre de recherche. Nous proposons alors une nouvelle méthode pour modéliser et résoudre des problèmes de planification déterministe en se basant sur une approche hiérarchique et heuristique. Nous nous sommes inspirés des formalismes de programmation structurée afin de fournir à l’utilisateur un cadre de travail plus intuitif pour la modélisation des domaines de planification hiérarchique. D’autre part, nous avons proposé un algorithme de planification capable d’exploiter ce formalisme et composer des stratégies à différents niveaux de granularité, ce qui lui permet de planifier rapidement une stratégie globale, tout en étant en mesure de pallier aux difficultés rencontrées à plus bas niveau. Cet algorithme a fait ses preuves face au principal planificateur HTN, SHOP2, sur des problèmes de planification classique. Automated planning is a field of Artificial Intelligence which aims at automatically computing a sequence of actions that lead to some goals from a given initial state. However, solving realistic problems is challenging because finding a solution path may require to explore an exponential number of states with regard to the number of state variables. To cope with this combinatorial explosion, efficient algorithms use heuristics, which guide the search towards optimistic or approximate solutions. Remarkably, hierarchical methods iteratively decompose the planning problem into smaller and much simpler ones. In a vast majority of problems, the planner must deal with constraints, such as multiple predefined phases or protocols. Such constraints generally help solving the planning problem, because they prune lots of search paths where these constraints do not hold. In this thesis, we assume that these constraints are known and given to the planner. We thus propose a new method to model and solve a deterministic planning problem, based on a hierarchical and heuristic approach and taking advantage of these constraints. We inspired ourselves from structured programming formalisms in order to offer a more intuitive modeling framework in the domain of hierarchical planning to the user. We also proposed a planning algorithm able to exploit this formalism and build strategies at various levels of granularity, thus allowing to plan quickly a global strategy, while still being able to overcome the difficulties at lower level. This algorithm showed its performances compared with the main HTN planner, SHOP2, on classical planning problems.