BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-94-1533
       ENTRY:: December 08, 1994
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Randomized Query Processing in Robot Motion Planning
        TYPE:: Technical Report
      AUTHOR:: Raghavan, L. Kavraki, J-C. Latombe, R. Motwani, P.
        DATE:: December 1994
       PAGES:: 16
    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.
       NOTES:: [Adminitrivia V1/Prg/19941208]
         END:: STAN//CS-TR-94-1533