| dc.description.abstract | Time-Bounded A* is a real-time, single-agent, deterministic search algorithm that expands
states of a graph in the same order as A* does, but that unlike A* interleaves search and action exe cution. Known to outperform state-of-the-art real-time search algorithms based on Korf’s Learning
Real-Time A* (LRTA*) in some benchmarks, it has not been studied in detail and is sometimes not
considered as a “true” real-time search algorithm since it fails in non-reversible problems even it
the goal is still reachable from the current state. In this paper we propose and study Time-Bounded
Best-First Search (TB(BFS)) a straightforward generalization of the time-bounded approach to any
best-first search algorithm. Furthermore, we propose Restarting Time-Bounded Weighted A* (TBR
(WA*)), an algorithm that deals more adequately with non-reversible search graphs, eliminating
“backtracking moves” and incorporating search restarts and heuristic learning. In non-reversible
problems we prove that TB(BFS) terminates and we deduce cost bounds for the solutions returned
by Time-Bounded Weighted A* (TB(WA*)), an instance of TB(BFS). Furthermore, we prove TBR
(WA*), under reasonable conditions, terminates. We evaluate TB(WA) in both grid pathfinding and
the 15-puzzle. In addition, we evaluate TBR (WA*) on the racetrack problem. We compare our
algorithms to LSS-LRTWA*, a variant of LRTA* that can exploit lookahead search and a weighted
heuristic. A general observation is that the performance of both TB(WA*) and TBR (WA*) im proves as the weight parameter is increased. In addition, our time-bounded algorithms almost
always outperform LSS-LRTWA* by a significant margin. | |
