Analyzing Behaviors of Artificial Intelligence Methods for a Search Game
Abstract
Monte Carlo Tree Search (MCTS) is a branch of stochastic modeling that utilizes decision trees for optimization. So far, the method has largely been applied to artificial intelligence (AI) game players. This project imagines a "game" in which an AI player searches for a stationary target within a 2-D grid. We define specific constraints for this search problem and adapt the MCTS method to solve for an efficient path. We analyze its behavior with different target distributions and constraints, including the decision time and domain size. This paper covers both a single searcher scenario and the multi-searcher case. The MCTS player is compared to a simple random walk, a nearly self-avoiding random walk, and the Levy Flight Search, a model for animal foraging behavior. We provide data from simulations and prove theoretical results regarding the convergence of the MCTS when computational constraints disappear. Overall, we conclude that a searcher (or multiple) using MCTS is effective against targets with delta-like distributions but quickly loses its strength when the a priori knowledge becomes more vague.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 12, 2021
- Accession Number
- AD1149675
Entities
People
- Elana P. Kozak
Organizations
- United States Naval Academy