Randomized query processing in robot path planning

Abstract

The subject of this paper is the analysis of a randomized preprocessing scheme that has beenused for query processing in robot path planning. The attractiveness of the scheme stems fromits general applicability to virtually any path-planning problem, and its empirically observedsuccess. In this paper we initiate a theoretical basis for explaining this empirical success. Undera simple assumption about the configuration space, we show that it is possible to performpreprocessing following...