Accession Number : ADA297173

Title :   New Approaches in Randomized Preprocessing for Motion Planning,

Corporate Author : WISCONSIN UNIV-MILWAUKEE DEPT OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE

Personal Author(s) : Guha, Sumanta ; Puvvada, Rama D. ; Suri, Deepti ; Suzuki, Ichiro

PDF Url : ADA297173

Report Date : 1995

Pagination or Media Count : 18

Abstract : A powerful new method based on randomization has emerged recently with great success in robot motion planning. Firstly, this consists of preprocessing, in which valid configurations (nodes) of the robot are generated randomly and a local planner is used to join some pairs of nodes, to form a configuration graph. Subsequently, path planning is executed by connecting the given initial and final configurations of the robot to two nodes of the graph, and finding a path joining these two nodes. Our contributions in this paper are two: We describe and implement a new heuristic for node generation, termed cell division, based on iterative, but controlled, splitting of the configuration space into smaller cells. The heuristic tends to generate more nodes in harder regions of the configuration space, thus allowing the planner a greater choice of nodes in such regions during path planning. We next describe and implement an entirely different approach in randomized preprocessing, termed ray shooting, in which we randomly generate rays (instead of configurations) in the configuration space along which we intend to transport the robot, and join some pairs of rays (viewed as nodes) using a local planner, to form a segment graph. Path planning then proceeds as before. Our implementation verifies that the planner performs efficiently even with minimal preprocessing, since each node in the graph represents a track that may transport the robot a relatively large distance through the configuration space. (AN)

Descriptors :   *ROBOTICS, *HEURISTIC METHODS, ALGORITHMS, SCENARIOS, OPTIMIZATION, RANDOM VARIABLES, COMPUTER PROGRAMMING, ROBOTS, PATHS, MOTION, THREE DIMENSIONAL, NAVIGATION, PLANNING, LONG RANGE(DISTANCE), CONFIGURATIONS, PREPROCESSING.

Subject Categories : Cybernetics

Distribution Statement : APPROVED FOR PUBLIC RELEASE