Randomized Query Processing in Robot Path Planning (Extended Abstract)

摘要

) LYDIA E. KAVRAKI JEAN-CLAUDE LATOMBE RAJEEV MOTWANI y PRABHAKAR RAGHAVAN z 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. 1 Introduction Planning obstacle-avoiding motion for a rigid or articulated robot from a given initial configuration to a goal configuration is an important problem in robotics [3, 8]. Typically, the environment is static and the robot must Robotics Lab...