Publications Details

On bootstrapping local search with trail-markers

Chen, Pang C.

We identify a general framework for search called bootstrap search, which is defined as global search using only a local search procedure along with some memory for learning intermediate subgoals. We present a simple algorithm for bootstrap search, and provide some initial theory on their performance. In our theoretical analysis, we develop a random digraph problem model and use it to make some performance predictions and comparisons. We also use it to provide some techniques for approximating the optimal resource bound on the local search to achieve the best global search. We validate our theoretical results with empirical demonstration on the 15-puzzle. We show how to reduce the cost of a global search by 2 orders of magnitude using bootstrap search. We also demonstrate a natural but not widely recognized connection between search costs and the lognormal distribution. To further illustrate our algorithm`s generality and effectiveness, we also apply it to robot path planning, and demonstrate a phenomenon of over-learning.