Probabilistic Roadmap Methods (PRMs) are one of the most used classes of motion planning methods. These sampling-based methods generate robot configurations (nodes)
and then connect them to form a graph (roadmap) containing representative feasible pathways. A key step in PRM roadmap construction involves identifying a set of candidate
neighbors for each node. Traditionally, these candidates are chosen to be the k-closest nodes based on a given distance metric. This work proposes a new neighbor selection policy
called LocalRand(k, k'), that first computes the k' closest nodes to a specified node and then selects k of those nodes at random. Intuitively, LocalRand attempts to benefit
from random sampling while maintaining the higher levels of local planner success inherent to selecting more local neighbors. A methodology for selecting the parameters k and
k' is provided, and an experimental comparison for both rigid and articulated robots show that LocalRand results in roadmaps that are better connected than the traditional k-closest or a purely random neighbor selection policy. The cost required to achieve these results is shown to be comparable to the cost of k-closest.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/148341 |
| Date | 14 March 2013 |
| Creators | Boyd, Bryan 1985- |
| Contributors | Amato, Nancy M |
| Source Sets | Texas A and M University |
| Detected Language | English |
| Type | Thesis, text |
| Format | application/pdf |
Page generated in 0.0018 seconds