New Approaches in Randomized Preprocessing for Motion Planning,
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1995
- Accession Number
- ADA297173
Entities
People
- Deepti Suri
- Ichiro Suzuki
- Rama D. Puvvada
- Sumanta Guha
Organizations
- University of Wisconsin–Milwaukee