Topological Planning with Post-unique and Unary Actions
Guillaume Prévost, Stéphane Cardon, Tristan Cazenave, Christophe Guettier, Éric Jacopin
Abstract
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.
BibTeX
@inproceedings{ijcai2023p603,
title = {Topological Planning with Post-unique and Unary Actions},
author = {Prévost, Guillaume and Cardon, Stéphane and Cazenave, Tristan and Guettier, Christophe and Jacopin, Éric},
booktitle = {Proceedings of the Thirty-Second International Joint Conference on
Artificial Intelligence, {IJCAI-23}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Edith Elkind},
pages = {5429--5436},
year = {2023},
month = {8},
note = {Main Track},
doi = {10.24963/ijcai.2023/603},
url = {https://doi.org/10.24963/ijcai.2023/603},
}