Backward Real Time Heuristic Search in Grid World Pathfinding

The A * algorithm works well for problems where the solution can be computed offline. In the real time search paradigm, an algorithm must compute the solution online: computation time is not free. Real time heuristic search is search in which the goal is to calculate a plan as close to an optimal plan as possible with the constraint that the algorithm executes an action after each tick of computation time, so that the computation time does not inhibit the optimality of the path taken. In this paper, a new algorithm for real time heuristic search is proposed and examined in the domain of grid world pathfinding. This algorithm named Backward Real Time Search (BRTS) boasts similar performance to modern algorithms such as TBA * and, unlike many other modern algorithms, it does not require pre-computation of the search space and complicated state space abstractions. It beats TBA * by a small margin which is more noticeable at low computation limit values. BRTS also beats a classic variant of LRTA * by more than an order of magnitude. BRTS is a general approach to real time search that one can apply to many search algorithms from A * to Weighted A*