AAAI Publications, Twelfth Artificial Intelligence and Interactive Digital Entertainment Conference

Font Size: 
Per-Map Algorithm Selection in Real-Time Heuristic Search
Vadim Bulitko

Last modified: 2016-09-19


Real-time heuristic search is suitable for time-sensitive pathfinding and planning tasks when an AI-controlled non-playable character must interleave its planning and plan execution. Since its inception in the early 90s, numerous real-time heuristic search algorithms have been proposed. Many of the algorithms also have control parameters leaving a practitioner with a bewildering array of choices. Recent work treated the task of algorithm and parameter selection as a search problem in itself. Such automatically found algorithms outperformed previously known manually designed algorithms on the standard video-game pathfinding benchmarks. In this paper we follow up by selecting an algorithm and parameters automatically per map. Our sampling-based approach is efficient on the standard video-game pathfinding benchmarks. We also apply the approach to per-problem algorithm selection and while it is effective there as well, it is not practical. We offer suggestions on making it so.


real-time heuristic search, video games, pathfinding, artificial intelligence

Full Text: PDF