About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Computer and System Sciences
Paper
Randomized Query Processing in Robot Path Planning
Abstract
The subject of this paper is the analysis of a randomized preprocessing scheme that has been used for query processing in robot path planning. The attractiveness of the scheme stems from its general applicability to virtually any path-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 preprocessing following which queries can be answered quickly. En route, we consider related problems on graph connectivity in the evasiveness model and art-gallery theorems. © 1998 Academic Press.