Ziebarth – Computer Science Student Portfolios

I am interested in completing research related to the use of machine learning to generate decision trees which control non-player character behavior in video games. Decision trees are relatively interpretable and have a high-level correspondence to behavior trees, which are used in the most common approach to AI for video games (Świechowski, 2022). I also enjoyed working with them when I took Artificial Intelligence and Machine Learning. The two environments I would propose using for testing is the Micro-Game Karting template in the Unity Asset Store, which is available for free and was used for testing by Mas’udi (2021).

Annotated Bibliography

Chan, M. T., Chan, C. W., & Gelowitz, C. (2015). Development of a Car Racing Simulator Game Using Artificial Intelligence Techniques. International Journal of Computer Games Technology, 2015.

Has focus on emulating human behavior
Use of waypoint system combined with conditional monitoring system
Uses trigger detection because it detects objects within the trigger area, where ray-casting can only detect collisions in one direction
Unity’s waypoint system and built-in gravity and vector calculations minimize development effort

This paper argues that Unity, as a development platform for a racing game, has advantages over the use of traditional AI search techniques for implementation of path-finding. These points could help to justify a decision to utilize Unity as an environment for testing.

Fairclough, C., Fagan, M., Mac Namee, B., & Cunningham, P. (2001). Research Directions for AI in Computer Games. Department of Computer Science, Trinity College, Dublin.

Covers the role of AI in action games, adventure games, role-playing games, and strategy games
Describes the status of AI within the game industry at the time of its publication
Lists a wide range of benefits to exploring the field of game AI
Discusses the TCD Game AI Project

This article gives a number of reasons for the simplicity of AI used by game developers in comparison to that used in academic research and industrial applications, and mentions a number of well-understood techniques in wide use at the time of its publication, including FSMs and A*. It also offers a number of reasons why research into AI for computer games is a worthwhile endeavor.

French, K., Wu, S., Pan, T., Zhou, Z., & Jenkins, O. C. (2019, May). Learning Behavior Trees from Demonstration. In 2019 International Conference on Robotics and Automation (ICRA) (pp. 7791-7797). IEEE.

Focuses on how a behavior tree can be learned from demonstration
Understands behavior trees as modular, transparent, reactive, and readily executable
The control nodes of behavior trees are Sequence, Fallback, Parallel, and Decorator
Algorithm 1 naively converts a decision tree to a behavior tree, while BT-Express takes advantage of the properties of a decision tree in doing so
Robot uses behavior tree to execute task without human input
Task executed is dusting with a micro fiber duster, requiring six distinct steps

This article gives advantages of behavior trees and describes two methods by which a decision tree can be converted to a behavior tree. This could be helpful in understanding the relationship between the decision trees which I intend to work with and the behavior trees that are prevalent in video game AI.

Guo, X., Singh, S., Lee, H., Lewis, R. L., & Wang, X. (2014). Deep Learning for Real-Time Atari Game Play Using Offline Monte-Carlo Tree Search Planning. Advances in Neural Information Processing Systems, 27.

Environment used is the Arcade Learning Environment (ALE), a class of benchmark reinforcement learning (RL) problems
Results for Deep Q-Network used as a basis
Repeated incremental planning via the Monte Carlo Tree Search method UCT
Combines UCT-based RL with deep learning by using a UCT agent to provide training data
Tests three methods, the most successful of which trains a classifier-based convolutional neural network (CNN) through interleaving of training and data collection to obtain data for an input distribution bearing a closer resemblance to that which would be encountered by the trained CNN

This paper presents results from game-playing agents whose performance was tested on the ALE, an environment which includes a variety of games for the Atari 2600 and thus would allow for testing the performance of decision trees on a range of different games, as well as permitting straightforward evaluation of the agent’s performance through scores achieved on the seven games used to evaluate Deep Q-Network. It also offers an example of the use of a method that would be infeasible for real-time play to generate training data for a faster agent, which, similar to the use of machine learning to generate a decision tree, uses a time-intensive process to create a classifier which can make decisions in real time.

Mas’udi, N. A., Jonemaro, E. M. A., Akbar, M. A., & Afirianto, T. (2021). Development of Non-Player Character for 3D Kart Racing Game Using Decision Tree. Fountain of Informatics Journal, 6(2), 51-60.

Waypoint system and raycasting used for pathfinding
Decision trees used with waypoint system and raycasting to determine NPC actions
Performance tested through FPS (frames per second), lap time over ten laps, and a driving test based on collisions with walls over ten laps
Agent’s performance compared to that of the ML NPC provided with Karting Microgame

This article offers an example of the use of decision trees to control NPC behavior. The environment it uses, Micro-Game Karting, which is now known as Karting Microgame, also offers an accessible environment for testing the performance of decision trees.

Van Lent, M., Fisher, W., & Mancuso, M. (2004, July). An Explainable Artificial Intelligence System for Small-Unit Tactical Behavior. In Proceedings of the national conference on artificial intelligence (pp. 900-907). Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999.

Full Spectrum Command, a commercial platform training aid developed for the U.S. Army, includes an Explainable AI system
In the after-action review, a soldier within the game can answer questions about the current behavior of its platoon, and the AI system identifies key events
Gameplay resembles the Real Time Strategy genre most closely, though with a number of differences
NPC AI controls individual units, while Explainable AI works during the after-action phase
NPC AI is divided into Control AI, which handles immediate responses and low-level decision-making, and Command AI, which handles higher-level tactical behavior

This paper offers an example of one approach to transparency of video game AI, that of creating a distinct system to explain its action in retrospect, as well as a different context in which explainability is relevant. It could be compared with the use of behavior trees and decision trees to allow for transparency in video games.

I wish to complete research related to the use of databases in video games to improve the efficiency of computations by increasing data locality and taking advantage of the optimizations of database management systems. While the article and dissertation by O’Grady (2019, 2021) which are referenced below both appear to focus on the feasibility of that approach, it seems likely that additional exploration is warranted regarding demonstrable advantages. For this exploration, I would propose focusing on the execution of path-finding through a database management system, one of the main areas examined by O’Grady (2021). Specifically, I wish to focus on sub-optimal path-finding, since optimality is generally not essential in the context of video games (Botea, 2013), despite the widespread use of A* (Kapi, 2020).

Annotated Bibliography

Abd Algfoor, Z., Sunar, M. S., & Kolivand, H. (2015). A Comprehensive Study on Pathfinding Techniques for Robotics and Video Games. International Journal of Computer Games Technology, 2015.

Covers techniques for known 2D/3D environments and unknown 2D environments, represented through either skeletonization or cell decomposition
Grids can be divided into regular grids and irregular grids, both of which are widely used in video games
As an alternative to grids, hierarchical techniques are used to reduce memory space needed.

This article offers an overview of the various pathfinding techniques used for video games and robotics. It is organized by environment representation and could be helpful in comparing and evaluating path-finding algorithms in order to determine which to use with a specific representation. It might also assist in deciding on an environment representation.

Bendre, M., Sun, B., Zhang, D., Zhou, X., Chang, K. C., & Parameswaran, A. (2015, August). Dataspread: Unifying databases and spreadsheets. In Proceedings of the VLDB Endowment International Conference on Very Large Data Bases (Vol. 8, No. 12, p. 2000). NIH Public Access.

Data exploration tool called DataSpread
Relational database system used is PostgreSQL
Offers Microsoft Excel-based front end while managing all the data in a back-end database in parallel
Spreadsheet design focuses on presentation of data, while databases have powerful data management capabilities

This paper describes a system created by unifying relational databases and spreadsheets, with the goal of retaining the advantages of spreadsheets while taking advantage of the power, expressivity, and efficiency of relational databases. The objective and approach of this research bear significant resemblances to those of O’Grady’s 2021 dissertation, in that both seek to increase the efficiency of a system by handling costly computations in a relational database. However, this article differs from O’Grady’s work in that it is based on a spreadsheet interface and an underlying database, rather than focusing on the implementation of specific components of a system within a database management system.

Botea, A., Bouzy, B., Buro, M., Bauckhage, C., & Nau, D. (2013). Pathfinding in games. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

Explains A*, Manhattan distance, and Octile distance
Discusses alternative heuristics such as the ALT heuristic, the dead-end heuristic, and the gateway heuristic
Covers approaches involving hierarchical abstraction
Discusses symmetry elimination, triangulation-based path-finding, and real-time search
Covers compressed path databases and multi-agent path-finding
Discusses a range of potential areas for further research, including the generation of sub-optimal paths

This paper explains the logic and advantages of various approaches to path-finding in video games. It also recognizes that in video game contexts, suboptimal paths are acceptable

O’Grady, D. (2019). Database-Supported Video Game Engines: Data-Driven Map Generation. BTW 2019.

Constructs maps composed of tiles through use of rules applied at specific frequencies
Map generation implemented in SQL and run on PostgreSQL 10
OpenRA used for on-site demonstration

This paper provides a demonstration of how a portion of a game’s internals can be moved to a database system. Its goal is to show that the benefits of moving expensive computations to a database system can be obtained while still allowing straightforward modification of the process by game developers.

O’Grady, D. (2021). Bringing Database Management Systems and Video Game Engines Together (Doctoral dissertation, Eberhard Karls Universität Tübingen).

Implementing data-heavy operations on the side of the database management system (DBMS) increases data locality
DBMS benefit from decades worth of development and optimization
Explores how databases can be involved in the operation of video game engines beyond their role in data storage
Evaluates practicality of three video game engine components when implemented in SQL
The third of these components is path-finding
The path-finding algorithm investigated is A*.
Storing spatial information about the game world in a DBMS allows for easy implementation of additional constraints to avoid collisions upon planning, preliminary reduction of the search space, preparatory analysis of the search space, and performing the path search close to the data
The pgRouting extension, implemented in C++ is used as a baseline
Two other custom implementations are also explored, both of which expect vertex-weighted graphs
The map is assumed to already be in a relational representation, as is the ability of actors to pass over certain types of tiles
Finding unilaterally connected components allows path-finding to be sped up in some cases
An implementation of A* in pure SQL is included
An implementation of Temporal A*, designed to avoid collisions, in SQL is also included
An Iterative Path Finding implementation in SQL, which gradually finds paths for multiple agents, is also given
Path-finding has to be completed in a timely manner, but players are willing to accept higher latencies for it compared to other actions
Shorter paths were found faster using the native implementation of OpenRA
As paths increased in length, the time needed to find them in the native implementation gradually increased, while the time needed to find them using pgRouting remained about the same
57% of path searches were found to be within the range of lengths that resulted in agreeable time boundaries
The DBMS was found to offer means to find paths sufficiently fast

This dissertation is the main work which I intend to build on in my thesis. Specifically, I wish to further explore the advantages of implementing path-finding in a database management system, as covered in Chapter 4.

Kapi, A. Y., Sunar, M. S., & Zamri, M. N. (2020). A review on informed search algorithms for video games pathfinding. International Journal, 9(3).

Challenges are limited memory, time constraints, and path quality
Most prominent algorithm is A*
Popular graph representations are grid maps, waypoint graphs, and navigation meshes, each of which has advantages and disadvantages depending on the type of game
NavMesh is often used in optimization to reduce memory consumption
Heuristic functions are generally modified to reduce time usage
Hybrid path-finding algorithms have been used for optimization
Data structure used for implementation of an algorithm can also be changed for optimization

This paper provides an overview of various ways of optimizing informed search algorithms for path-finding in video games, presenting various factors which influence memory and time usage. It would be useful for considering potential consequences of different experiment designs, given its focus on approaches to improving the efficiency of path-finding which do not rely on the optimizations of a database management system.

Author: Ziebarth

CS 388 Proposal

CS 388 Literature Review

CS 388 Annotated Bibliographies

CS 388 Initial Pitches