We are interested in realistic planning problems to model the behavior of Non-Playable Characters (NPCs) in video games. Search-based action planning, introduced by the game F.E.A.R. in 2005, has an exponential time complexity allowing to control only a dozen NPCs between two frames. A close study of the plans generated in first-person shooters shows that: (1) actions are unary, (2) actions are contextually post-unique and (3) there is no two instances of the same action in an NPC’s plan. By considering (1), (2) and (3) as restrictions, we introduce new classes of problems with the Simplified Action Structure formalism which indeed allow to model realistic problems and whose instances are solvable by a linear-time algorithm. We also experimentally show that our algorithm is capable of managing millions of NPCs per frame.

Scheduling under uncertainty is an area of interest in artificial intelligence. We study the problem of Dynamic Controllability (DC) of Disjunctive Temporal Networks with Uncertainty (DTNU), which seeks a reactive scheduling strategy to satisfy temporal constraints in response to uncontrollable action durations. We introduce new semantics for reactive scheduling: Time-based Dynamic Controllability (TDC) and a restricted subset of TDC, R-TDC. We present a tree search approach to determine whether or not a DTNU is R-TDC. Moreover, we leverage the learning capability of a Graph Neural Network (GNN) as a heuristic for tree search guidance. Finally, we conduct experiments on a known benchmark on which we show R-TDC to retain significant completeness with regard to DC, while being faster to prove. This results in the tree search processing fifty percent more DTNU problems in R-TDC than the state-of-the-art DC solver does in DC with the same time budget. We also observe that GNN tree search guidance leads to substantial performance gains on benchmarks of more complex DTNUs, with up to eleven times more problems solved than the baseline tree search.

We investigate the capability of Goal Oriented Action Planning (GOAP) to perform a double-objective: (1) to control the Non-Player Character (NPC) behaviors, and (2) to generate dungeon levels. We demonstrate its application for a 2D custom platformer roguelike game. Our first results show GOAP's ability to generate a wide range of playable and stable dungeon levels while producing unpredictable NPC actions.

We present a hybrid planning architecture that combines both Goal-Oriented Action Planning (GOAP) and Hierarchical Task Network (HTN) planning to avoid the enemies' predictable behaviors and dynamically adapt their actions according to the game-play context. The proposed approach is assessed and illustrated through a 3D custom brawler game where the player character fights invaders by controlling fluid material. Although the planning is computationally expensive, the first results show that our planner is efficient/fast and the game session has enjoyable playability.

As music tempo can influence human actions pace, we use tempi variations to vary the difficulty in gaming situations based on the synchronization of events, like actions on moving objects in arcade games or waves of enemies in FPS. In this work, musical tempi are exploited to hinder or help Tetris players. Over the first phase of this work involving 44 players and more than 230 Tetris games we discovered surprising interactions between different tempo characteristics influencing the player’s performance. The positive or negative effects of specific tempi settings we discovered were validated in a second phase involving 19 players and 50 Tetris games. Once the effect was chosen, it was dynamically triggered according to certain conditions that were validated during the first phase of this work. Results show that a transition from a staircase increase to a more gradual increase in tempo significantly hinders Tetris players when both tempi are synchronous with the gameplay whereas the same transition help players when both tempi are not synchronized with game actions. Our approach provides new and valuable insight to varying video-game difficulty when gaming situations ask the player to increasingly synchronize with the pace of the game.

Game Artificial Intelligence Engines of commercial games run on CPUs and not on GPUs. With more and more powerful GPUs and Cloud gaming, our vision is that GPUs will become the dedicated Game AI hardware, just as it now provides computing power for Game Physics (e.g. nVidia PhysX). In particular, we believe GPUs can run Game AI Planning, which computes plans in order to control the behaviors of Non-Player Characters (NPCs) in video-games. Our objective is an efficient online GPU-based Game AI Planning component with Cloud gaming as a target. We here report on our most recent implementation which can control thousands of NPCs each frame with only one GTX 1080 on the AI server, pushing thousands of plans to the client (PC or console).

It has been shown that music influences human behavior and that it can influence the sports endurance or cognitive performance (memory, reflexes) of individuals. However, little research exists on its influence on the performance of video game players. Music is used to create a particular atmosphere in a game but can it be used to change the difficulty of the game? In this paper, we examine the effects of musical tempo on the performance of players in the Tetris game. By experimenting with different tempo settings for the same music -perfectly synchronous with the game, gradually accelerating to prepare for speed steps, slightly out of sync or in total opposition to the tension of the game- we have shown a significant influence of tempo on the performance of novice Tetris players and even more so for those who have a neutral evaluation of the music. By increasing the tension of the game, a synchronous and increasing tempo can increase the player's stress and degrade his performance, while a tempo that is out of sync with the actions of the game or slowed down regularly can defuse this stress.

In this demo paper, we present Sonotris, a Tetris game with a dynamic soundtrack specifically designed to experiment with the influence of musical tempo on player performance. The different stages of the game use music whose tempo is either perfectly synchronous with the game, or accelerates progressively to prepare the speed steps, or is slightly out of sync, or in total opposition to the tension of the game. Our first tests on a group of 41 players showed a significant influence of tempo on the performance of novice players in Tetris and even more for those with a neutral evaluation of the music.

Learning-based methods are growing prominence for planning purposes. However, there are very few approaches for learning-assisted constrained path-planning on graphs, while there are multiple downstream practical applications. This is the case for constrained path-planning for Autonomous Unmanned Ground Vehicles (AUGV), typically deployed in disaster relief or search and rescue applications. In off-road environments, the AUGV must dynamically optimize a source-destination path under various operational constraints, out of which several are difficult to predict in advance and need to be addressed on-line. We propose a hybrid solving planner that combines machine learning models and an optimal solver. More specifically, a graph convolutional network(GCN) is used to assist a branch and bound(B&B) algorithm in handling the constraints. We conduct experiments on realistic scenarios and show that GCN support enables substantial speedup and smoother scaling to harder problems.