Real-Time Planning : Reducing Complexity for Scaling Up
Planification Temps-Réel : Réduction de la Complexité pour un Passage à l'Échelle
Prevost, Guillaume (2022), Real-Time Planning : Reducing Complexity for Scaling Up, doctoral thesis prepared under the supervision of Cazenave, Tristan; Jacopin, Éric, Université Paris sciences et lettres
Author(s)
Prevost, GuillaumeUnder the direction of
Cazenave, Tristan; Jacopin, ÉricAbstract (FR)
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.Abstract (EN)
This thesis address the problem of scaling the generation of plans in real-time to control the behaviors of several millions of Non-Player Characters (NPCs) in video-games and virtual worlds. Search-based action planning, introduced in the game F.E.A.R. in 2005, has an exponential time complexity managing at most several tens of NPCs per frame and with short plans. I carried out a close study of the plans generated in first-person shooters and this study shows that: (1) states are vectors of enumerated values,(2) both initial and final states can be totally defined, (3) actions are both post-unique and unary, (4) plans are totally ordered, and (5) actions occur only once in plans. (1) to (3) satisfy the Simplified Action Structure (SAS) polynomial time planning framework but neither (4) nor (5): I thus present new restrictions satisfying (5) to this SAS planning framework and a new linear-time algorithm satisfying (4). Using experiments involving planning problems modelled from existing commercial video games, I show that my planner outperforms previous SAS planners and that it is indeed capable of building longer plans for several millions of NPCs in real-time.Subjects / Keywords
Intelligence Artificielle; Planification; Temps-Réel; Jeu vidéo; Artificial Intelligence; Planning; Real-Time; Video gameRelated items
Showing items related by title and author.
-
Ardon, Roberto; Cohen, Laurent D.; Corréas, Jean-Michel; Mory, Benoît; Prevost, Raphaël (2012) Communication / Conférence
-
Ardon, Roberto; Mory, Benoît; Prevost, Raphaël; Somphone, Oudom (2012) Communication / Conférence
-
Rodriguez, Jacques; Caruso, M.; Scemama, Gérard; Balbo, Flavien; Tendjaoui, Mustapha (2000) Communication / Conférence
-
Prevost, Guillaume; Cardon, Stéphane; Cazenave, Tristan; Jacopin, Eric (2019) Communication / Conférence
-
Mathematical models for real-world production planning problems with sequence-dependent set-up costs Shen, Xueying; Focacci, Filippo; Furini, Fabio; Gabrel, Virginie; Godard, Daniel (2015-02) Communication / Conférence