Show simple item record

Real-Time Planning : Reducing Complexity for Scaling Up

Planification Temps-Réel : Réduction de la Complexité pour un Passage à l'Échelle

dc.contributor.advisorCazenave, Tristan
dc.contributor.advisorJacopin, Éric
dc.contributor.authorPrevost, Guillaume
dc.date.accessioned2023-05-16T09:18:05Z
dc.date.available2023-05-16T09:18:05Z
dc.date.issued2022-12-15
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/24730
dc.description.abstractfrCette 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.fr
dc.language.isoen
dc.subjectIntelligence Artificiellefr
dc.subjectPlanificationfr
dc.subjectTemps-Réelfr
dc.subjectJeu vidéofr
dc.subjectArtificial Intelligenceen
dc.subjectPlanningen
dc.subjectReal-Timeen
dc.subjectVideo gameen
dc.subject.ddc006.3
dc.titleReal-Time Planning : Reducing Complexity for Scaling Upen
dc.titlePlanification Temps-Réel : Réduction de la Complexité pour un Passage à l'Échellefr
dc.typeThèse
dc.contributor.editoruniversityotherUniversité Paris sciences et lettres
dc.contributor.editoruniversityotherÉcole nationale supérieure des mines (Paris ; 1783-....)
dc.description.abstractenThis 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.en
dc.identifier.theseid2022UPSLD045
dc.subject.ddclabelIntelligence artificielle
hal.author.functionaut


Files in this item

Thumbnail
Name:
2022UPSLD045.pdf
Size:
3.733Mb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record