- 280 views
- 518 downloads
Automatic Algorithm Selection in Videogame Pathfinding
-
- Author / Creator
- Sigurdson, Devon
-
Videogames often use artificial intelligence to control characters in the game world. In doing so, videogames require one or more agents to navigate from their current location to some desired goal location without collisions. We explore improving algorithm performance in both single and multi-agent pathfinding (MAPF) through the use of algorithm portfolios and machine learning algorithm selection. In the single agent setting we explore selecting from different versions of a parametrized real-time heuristic search algorithm focused on minimizing the distance the agent travels. In the MAPF setting we select from three contemporary MAPF algorithms, Windowed Hierarchical Co-operative A, Flow Annotated Replanning, and Bounded Multi-agent A focused on maximizing the number of agents which reach their goal. Algorithms will often have specific problem instance where their performance either excels or deteriorates, enabling another algorithm to out perform it even if this other algorithm is worse on average. Therefore, in this thesis, we investigate the use of deep learning to automatically select the best algorithm from a portfolio of algorithms for given problem instances. Empirical results show that an off-the-shelf convolutional neural network is able to improve performance over any single algorithm from our portfolio.
-
- Subjects / Keywords
-
- Graduation date
- Fall 2018
-
- Type of Item
- Thesis
-
- Degree
- Master of Science
-
- License
- Permission is hereby granted to the University of Alberta Libraries to reproduce single copies of this thesis and to lend or sell such copies for private, scholarly or scientific research purposes only. Where the thesis is converted to, or otherwise made available in digital form, the University of Alberta will advise potential users of the thesis of these terms. The author reserves all other publication and other rights in association with the copyright in the thesis and, except as herein before provided, neither the thesis nor any substantial portion thereof may be printed or otherwise reproduced in any material form whatsoever without the author's prior written permission.