• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

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

View/Open
2022UPSLD045.pdf (3.733Mb)
Type
Thèse
Date
2022-12-15
Metadata
Show full item record
Author(s)
Prevost, Guillaume
Under the direction of
Cazenave, Tristan; Jacopin, Éric
Abstract (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 game

Related items

Showing items related by title and author.

  • Thumbnail
    Kidney detection and real-time segmentation in 3D contrast-enhanced ultrasound images 
    Ardon, Roberto; Cohen, Laurent D.; Corréas, Jean-Michel; Mory, Benoît; Prevost, Raphaël (2012) Communication / Conférence
  • Thumbnail
    Real-Time 3D Image Segmentation by User-Constrained Template Deformation 
    Ardon, Roberto; Mory, Benoît; Prevost, Raphaël; Somphone, Oudom (2012) Communication / Conférence
  • Thumbnail
    Real-time aid to decision system for bus operators 
    Rodriguez, Jacques; Caruso, M.; Scemama, Gérard; Balbo, Flavien; Tendjaoui, Mustapha (2000) Communication / Conférence
  • Thumbnail
    Planning in video games: What are actions costs used for? 
    Prevost, Guillaume; Cardon, Stéphane; Cazenave, Tristan; Jacopin, Eric (2019) Communication / Conférence
  • Thumbnail
    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
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo