Adaptive CGF Commander Behavior Modeling Through HTN Guided Monte Carlo Tree Search

Abstract

Improving the intelligence of virtual entities is an important issue in Computer Generated Forces (CGFs) construction. Some traditional approaches try to achieve this by specifying how entities should react to predefined conditions, which is not suitable for complex and dynamic environments. This paper aims to apply Monte Carlo Tree Search (MCTS) for the behavior modeling of CGF commander. By look-ahead reasoning, the model generates adaptive decisions to direct the whole troops to fight. Our main work is to formulate the tree model through the state and action abstraction, and extend its expansion process to handle simultaneous and durative moves. We also employ Hierarchical Task Network (HTN) planning to guide the search, thus enhancing the search efficiency. The final implementation is tested in an infantry combat simulation where a company commander needs to control three platoons to assault and clear enemies within defined areas. Comparative results from a series of experiments demonstrate that the HTN guided MCTS commander can outperform other commanders following fixed strategies.

Keywords

Monte Carlo Tree Search / Hierarchical Task Network / Computer generated force / Behavior modeling

References

[1] Auer P., Cesa-Bianchi N., Fischer P.. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 2002, 47(2-3): 235-256.

[2] Balla R., Fern A.. UCT for tactical assault planning in real-time strategy games. 21st International Joint Conference on Artificial Intelligence, 2009 40-45.

[3] Barriga N. A., Stanescu M., Buro M.. Magerko B., Rowe J.P.. Combining strategic learning with tactical search in real-time strategy games. Proceedings of the Thirteenth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment (AIIDE-17), 2017 9-15.

[4] Browne C., Powley E. J., Whitehouse D., Lucas S. M., Cowling P. I., Rohlfshagen P., Tavener S., Liebana D. P., Samothrakis S., Colton S.. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in Games, 2012, 4(1): 1-43.

[5] Churchill D., Buro M.. Portfolio greedy search and simulation for large-scale combat in starcraft. 2013 IEEE Conference on Computational Inteligence in Games (CIG), 2013 1-8.

[6] Churchill D., Saffidine A., Buro M.. Riedl M., Sukthankar G.. Fast heuristic search for RTS game combat scenarios. Proceedings of the Eighth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, Stanford, 2012

[7] Cowling P. I., Buro M., Bida M., Botea A., Bouzy B., Butz M. V., Hingston P., Munoz-Avila H., Nau D., Sipper M.. Lucas S. M., Mateas M., Preuss M., Spronck P., Togelius J.. Search in real-time video games. Artificial and Computational Intelligence in Games, 2013 1-19.

[8] Juarez-Espinosa O., Gonzalez C.. Situation awareness of commanders: a cognitive model. 2004 Conference on Proceedings of Behavior Representation in Modeling and Simulation, 2004

[9] Justesen N., Bontrager P., Togelius J., Risi S.. Deep learning for video game playing, 2017

[10] Justesen N., Tillman B., Togelius J., Risi S.. Script-and cluster-based UCT for starcraft. 2014 IEEE Conference on Computational Intelligence and Games (CIG), 2014 1-8.

[11] Kocsis L., Szepesvári C.. Bandit based monte-carlo planning. 17th European Conference on Machine Learning, 2006 282-293.

[12] Kovarsky A., Buro M.. Kégl B., Lapalme G.. Heuristic search applied to abstract combat games. 18th Conference of the Canadian Society for Computational Studies of Intelligence, 2005 66-78.

[13] Nau D. S., Cao Y., Lotem A., Munoz-Avila H.. Dean T.. SHOP: simple hierarchical ordered planner. Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, 1999

[14] North M. J., Collier N. T., Ozik J., Tatara E. R., Macal C. M., Bragen M., Sydelko P.. Complex adaptive systems modeling with repast simphony. Complex Adaptive Systems Modeling, 2013, 1(1): 3.

[15] Ontanon S., Buro M.. Yang Q., Wooldridge M.. Adversarial hierarchical-task network planning for complex real-time games. Proceedings of the 24th International Joint Conference on Artificial Intelligence, 2015 1652-1658.

[16] Pew R. W., Mavor A. S.. Modeling Human and Organizational Behavior: Application to Military Simulations, 1998, Washington, DC: The National Academies Press

[17] Sokolowski J. A.. Human behavior modeling: A real-world application. Handbook of Real-World Applications in Modeling and Simulation, 2012 26-92.

[18] Stanescu M., Barriga N. A., Buro M.. Horswill I., Jhala A.. Hierarchical adversarial search applied to real-time strategy games. Proceedings of the Tenth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2014

[19] Stanescu M., Barriga N. A., Hess A., Buro M.. Evaluating real-time strategy game states using convolutional neural networks. IEEE Conference on Computational Intelligence and Games, 2016 1-7.

[20] Straatman R., Verweij T., Champandard A., Morcus R., Kleve H.. Hierarchical AI for multiplayer bots in killzone 3. In Rabin, S. (ed), Game AI Pro: Collected Wisdom of Game AI Professionals, 2013 377-390.

[21] Vakas D., Prince J., Blacksten H. R., Burdick C.. Rohrer M. W., Medeiros D. J., Grabau M. R.. Commander behavior and course of action selection in JWARS. Proceedings of the 33rd Conference on Winter Simulation, WSC 2001, Arlington, 2001

[22] Xu X., Yang M., Li G., Huang K.. HTN guided game tree search for adaptive CGF commander behavior modeling. IEEE 2nd International Conference on Agents, 2017

[23] Zhuo H. H., Munoz-Avila H., Yang Q.. Learning hierarchical task network domains from partially observed plan traces. Artificial Intelligence, 2014, 212: 134-157.