Position Paper: Incremental Search Algorithms Considered Poorly Understood

Abstract

In this paper, we investigate real-time path planning instatic terrain, as needed in video games. We introduce thegame time model, where time is partitioned into uniformtime intervals, an agent can execute one movement duringeach time interval, and search and movements are done inparallel. The objective is to move the agent from its startlocation to its goal location in as few time intervals as possible. For known terrain, we show experimentally that Time-Bounded A* (TBA*), an existing real-time search algorithmfor undirected terrain, needs fewer time intervals than twostate-of-the-art real-time search algorithms and about thesame number of time intervals as A*. TBA*, however, cannot be used when the terrain is not known initially. Forinitially partially or completely unknown terrain, we thuspropose a new search algorithm. Our Time-Bounded Adaptive A* (TBAA*) extends TBA* to on-line path planningwith the freespace assumption by combining it with Adaptive A*. We prove that TBAA* either moves the agent fromits start location to its goal location or detects that this isimpossible – an important property since many existing real-time search algorithms are not able to detect efficiently thatno path exists. Furthermore, TBAA* can eventually movethe agent on a cost-minimal path from its start location toits goal location if it resets the agent into its start locationwhenever it reaches its goal location. We then show experimentally in initially partially or completely unknown terrainthat TBAA* needs fewer time intervals than several state-of-the-art complete and real-time search algorithms and aboutthe same number of time intervals as the best comparedcomplete search algorithm, even though it has the advantage over complete search algorithms that the agent startsto move right away.