Heuristic tree search with nonparametric statistical inference methods

The computational complexity of widely-used heuristic search algorithm, A*, could be exponential in the length of the path from the start node to a goal node. In several interesting cases, for example in a tree model, we can improve the average-case performance of the search by making use of some global behavior of a suitable statistic derived from the heuristic estimator. Until now, only the utilization of parametric statistical inference methods has been studied. These methods assume that the probability distribution of the underlying statistic and also its parameters are precisely known. However, such a precise knowledge may not be available for some practical situations. In this paper, we propose an approach based on non-parametric statistical inference methods that do not require such precise information about the distribution. We develop search algorithms, NSA and Successive NSA, and analyze their performance using a uniform m-ary search tree G with a single goal located at an unknown location at depth N. Successive NSA has the mean complexity of O(N(logN)2), in terms of the average number of nodes expanded when the probability with which the most deviation of the heuristic from the actual value exceeds a specified constant, is bounded by another specified constant. The storage required is O((logN)2) and the average number of comparisons is O(N(logN)6loglogN).