Multi-directional Rapidly Exploring Random Graph (mRRG) for Motion Planning

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.