Accession Number:

ADA326821

Title:

Randomized Query Processing in Robot Motion Planning.

Descriptive Note:

Research rept.,

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Kavraki, Lydia
• Latombe, Jean-Claude
• Motwani, Rajeew
• Raghavan, P.

Report Date:

1994-12-01

Pagination or Media Count:

18.0

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.

Descriptors:

• *MOTION
• *PLANNING
• *INTERROGATION
• *PREPROCESSING
• RANDOM VARIABLES
• GRAPHS
• ROBOTS

Subject Categories:

• Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE