Cette thèse explore l'application de la planification HTN afin d'animer une section d'infanterie dans un simulateur informatique temps réel. Afin de produire des plans en ligne pour près de 40 soldats, on montre qu'il est possible d'optimiser le planificateur pour un domaine HTN en compilant les éléments de planifications en structures statiques et en procédures C++. On montre ensuite que la structure du problème se prête à une combinaison de la planification HTN avec la planification par abstraction, obtenue en modélisant des effets abstraits aux tâches composées. Sous certaines conditions, la recherche de solutions est alors accélérée en détectant les réseaux de tâches pour lesquels aucune solution n'est exécutable. Enfin, on montre que la structure du problème permet aussi de formuler des fonctions d'évaluation exploitables dans un algorithme de recherche heuristique non admissible, capable de retourner rapidement des solutions presque optimales. / This thesis explores the application of HTN planning to the animation of an infantry platoon in a real-time simulation software. In order to achieve online planning for nearly 40 soldiers, we show that it is possible to optimize the planner for one HTN domain with a compilation of planning elements into C++ static structures and procedures. Then, we demonstrate that the problem structure lends itself to a combination of HTN planning with abstraction planning, achieved with the modelisation of abstract effects for compound tasks. In some conditions, we can detect those task networks that never lead to any executable solution, and therefore improve the search. Eventually, we show that the problem structure enables to formulate evaluation functions that can be input into a non admissible heuristic search algorithm, and that near optimal solutions can be obtained within a short run-time.
Identifer | oai:union.ndltd.org:theses.fr/2017PSLED004 |
Date | 11 January 2017 |
Creators | Menif, Alexandre |
Contributors | Paris Sciences et Lettres, Cazenave, Tristan, Jacopin, Éric |
Source Sets | Dépôt national des thèses électroniques françaises |
Language | French |
Detected Language | French |
Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0138 seconds