Speeding up the Convergence of Real-Time Search

Abstract

Learning Real-Time A * (LRTA*) is a real-time search method that makes decisions fast and still converges to a shortest path when it solves the same planning task repeat-edly. In this paper, we propose new methods to speed up its convergence. We show that LRTA * often converges sig-nificantly faster when it breaks ties towards successors with smallest f-values ( a la A*) and even faster when it moves to successors with smallest f-values instead of only break-ing ties in favor of them. FALCONS, our novel real-time search method, uses a sophisticated implementation of this successor-selection rule and thus selects successors very dif-ferently from LRTA*, which always minimizes the estimated cost to go. We first prove that FALCONS terminates and converges to a shortest path, and then present experiments in which FALCONS finds a shortest path up to sixty percent faster than LRTA * in terms of action executions and up to seventy percent faster in terms of trials. This paper opens up new avenues of research for the design of novel successor-selection rules that speed up the convergence of both real-time search methods and reinforcement-learning methods.