Local Randomization in Neighbor Selection Improves PRM Roadmap Quality
dc.contributor | Amato, Nancy M | |
dc.creator | Boyd, Bryan 1985- | |
dc.date.accessioned | 2013-03-14T16:21:50Z | |
dc.date.accessioned | 2017-04-07T20:03:23Z | |
dc.date.available | 2013-03-14T16:21:50Z | |
dc.date.available | 2017-04-07T20:03:23Z | |
dc.date.created | 2012-12 | |
dc.date.issued | 2012-08-27 | |
dc.description.abstract | 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. | |
dc.identifier.uri | http://hdl.handle.net/1969.1/148341 | |
dc.subject | Motion Planning | |
dc.subject | Robotics | |
dc.title | Local Randomization in Neighbor Selection Improves PRM Roadmap Quality | |
dc.type | Thesis |