Report Number: CS-TR-94-1533
Institution: Stanford University, Department of Computer Science
Title: Randomized Query Processing in Robot Motion Planning
Author: Raghavan, L. Kavraki, J-C. Latombe, R. Motwani, P.
Date: December 1994
Abstract: The subject of this paper is the analysis of a randomized preprocessing scheme that has been used for query processing in robot motion planning. The attractiveness of the scheme stems from its general applicability to virtually any motion-planning problem, and its empirically observed success. In this paper we initiate a theoretical basis for explaining this empirical success. Under a simple assumption about the configuration space, we show that it is possible to perform a preprocessing step following which queries can be answered quickly. En route, we pose and give solutions to related problems on graph connectivity in the evasiveness model, and art-gallery theorems.
http://i.stanford.edu/pub/cstr/reports/cs/tr/94/1533/CS-TR-94-1533.pdf