Planification Temps-Réel : Réduction de la Complexité pour un Passage à l'Échelle.
15/12/2022 à 14h00
M.Guillaume PREVOST présente ses travaux en soutenance le 15/12/2022 à 14h00
À l'adresse suivante : Université Paris Dauphine-PSL Place du Maréchal de Lattre de Tassigny 75016 Paris - Salle des thèses - D520
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Planification Temps-Réel : Réduction de la Complexité pour un Passage à l'Échelle.
École doctorale
École doctorale Dauphine SDOSE
Équipe de recherche
UMR 7243 - Laboratoire d’Analyse et de Modélisation de Systèmes d’Aide à la Décision
Section CNU
27 - Informatique
Directeur(s)
M. Tristan CAZENAVE
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. Tristan CAZENAVE | Professeur des universités | Université Paris Dauphine - PSL | Directeur de thèse |
| M. Peter JONSSON | Professor | Université de Linköping | Rapporteur |
| Mme Aurélie BEYNIER | Maître de conférences | Université de la Sorbonne | Rapporteure |
| M. Eric JACOPIN | Senior AI Programmer | HAWKSWELL | Co-directeur de thèse |
| M. Stéphane CARDON | Maître de conférences | Centre de Recherche de Saint-Cyr | Co-encadrant de thèse |
| M. Sylvain LAGRUE | Professeur des universités | Université de Technologie de Compiègne | Examinateur |
| M. Christophe GUETTIER | Innovation Program Manager, Expert Emeritus | Safran Electronics & Defense | Invité |
| M. Gabriel ROBERT | PhD - Lead R&D Developer | Ubisoft La Forge | Invité |
Résumé
Cette thèse aborde le problème de la génération de plans en temps-réel permettant le contrôle de plusieurs millions de personnages non-joueurs (PNJs) dans les jeux vidéo et les mondes virtuels. La planification d’actions basée sur des algorithmes de recherche, introduite dans le jeu F.E.A.R. en 2005, a une complexité temporelle exponentielle. Elle ne permet de ne gérer qu'au maximum plusieurs dizaines de PNJs par image et avec peu d'actions par plan. J'ai mené une étude approfondie des plans générés dans les jeux de tir à la première personne et cette étude montre que : (1) les états sont des vecteurs de valeurs énumérées, (2) les états initiaux et finaux peuvent être totalement définis, (3) les actions sont à la fois post-uniques et unaires, (4) les plans sont totalement ordonnés, et (5) les actions n'apparaissent qu’une seule fois dans les plans. (1) à (3) correspondent à des problèmes de planification polynomiaux du cadre Simplified Action Structure (SAS), mais pas (4) ni (5) : je présente donc de nouvelles restrictions satisfaisant (5) pour ces problèmes SAS et un nouvel algorithme de complexité linéaire satisfaisant (4). A l'aide d'expériences mettant en œuvre des problèmes de planification modélisés à partir de jeu-vidéo commerciaux, je montre que mon planificateur surpasse de façon spectaculaire les planificateurs SAS précédents et qu'il est en effet capable de construire des plans plus longs et pour plusieurs millions de PNJs en temps-réel.