TBA*: time-bounded A*
Yngvi Björnsson, Vadim Bulitko, Nathan Sturtevant · 2009
Real-time heuristic search algorithms are used for planning by agents in situations where a constant-bounded amount of deliberation time is required for each action regardless of the problem size. Such al-gorithms interleave their planning and execution to ensure real-time response. Furthermore, to guar-antee completeness, they typically store improved heuristic estimates for previously expanded states. Although subsequent planning steps can benefit from updated heuristic estimates, many of the same states are expanded over and over again. Here we propose a variant of the A * algorithm, Time-Bounded A * (TBA*), that guarantees real-time re-sponse. In the domain of path-finding on video-game maps TBA * expands an order of magnitude fewer states than traditional real-time search algo-rithms, while finding paths of comparable quality. It reaches the same level of performance as recent state-of-the-art real-time search algorithms but, un-like these, requires neither state-space abstractions nor pre-computed pattern databases. 1