RANDOMIZED QUERY-PROCESSING IN ROBOT PATH PLANNING

The subject of this paper is the analysis of a randomized preprocessin g scheme that has been used for query processing in robot path plannin g. The attractiveness of the scheme stems from its general applicabili ty to virtually any path-planning problem, and its empirically observe d success. In this paper we initiate a theoretical basis for explainin g this empirical success. Under a simple assumption about the configur ation space, we show that it is possible to perform preprocessing foll owing which queries can be answered quickly. En route, we consider rel ated problems on graph connectivity in the evasiveness model an dart-g allery theorems. (C) 1998 Academic Press.