Paper Summary: Time-Bounded Adaptive A*

Abstract

This paper summarizes our AAMAS 2012 paper on "Time-Bounded Adaptive A*," which introduces the game time model to evaluate search algorithms in real-time settings, such as video games. It then extends the existing real-time search algorithm TBA* to path planning with the freespace assumption in initially partially or completely unknown terrain, resulting in Time-Bounded Adaptive A* (TBAA*). TBAA* needs fewer time intervals in the game time model than several state-of-the-art complete and real-time search algorithms and about the same number of time intervals as the best compared complete search algorithm, even though it has the advantage over complete search algorithms that the agent starts to move right away.