Multi-directional Rapidly Exploring Random Graph (mRRG) for Motion Planning
Loading...
Date
2013-08-27
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The motion planning problem in robotics is to find a valid sequence
of motions taking some movable object from a start configuration to a
goal configuration in an environment.
Sampling-based path planners are very popular for high-dimensional
motion planning in complex environments. These planners
build a graph (roadmap) by generating robot configurations (vertices), and connecting
nearby pairs of configurations according to their transition
feasibility. Tree-based sampling-based
planners (e.g., Rapidly-Exploring Random Tree, or RRT) start growing a
tree outward from an initial configuration of the robot.
In this work, we propose a multi-directional
Rapidly-Exploring Random Graph (mRRG) for robotic motion planning,
a variant of the Rapidly-Exploring Random Graph (RRG).
Instead of expanding a vertex in the tree in a single random direction
during each iteration, mRRG expands in m random directions.
Our results show that growing in multiple directions in this way
produces roadmaps with more topologically distinct paths
than previous methods. In an environment with dynamic obstacles,
moving or new obstacles may invalidate a path from the start to the goal.
Hence, roadmaps containing alternative pathways can be beneficial as they may
avoid recalculation of new valid paths.
One of the important phases in sampling-based methods involves
finding candidate nearest neighbors to attempt to connect to a node. Generally,
the entire graph is considered to search for the nearest neighbors.
In this thesis, we propose a heuristic method for finding nearest neighbors
based on the hop limit, i.e., the maximum number of edges allowed
in the path from a vertex to its neighbor. The candidate nearest neighbors
are found by considering only those vertices within the hop limit.
We experimentally show that our hop limit neighbor finder significantly
reduces neighbor searching time over the standard brute force approach when
constructing roadmaps.
Description
Keywords
Motion Planning, RRT, RRG, Protein Folding