Bootstrap planning: Theory and application

We identify a general framework for weak planning called bootstrap planning, which is defined as global planning using only a local planner along with some memory for learning intermediate subgoals. We present a family of algorithms for bootstrap planning, 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 of these algorithms. We also use it to provide some techniques for approximating the optimal resource bound on the local planner to achieve the best global planner. We validate our theoretical results with empirical demonstration on the 15-puzzle. We show how to reduce the planning cost of a global planner by 2 orders of magnitude using bootstrap planning. We also demonstrate a natural but not widely recognized connection between search costs and the lognormal distribution.