One approach to sensor based planning employs a roadmap, a concise representation of a robot’s work space or configuration space. This approach is analogous to a network of freeways. Path planning is reduced to finding a route onto the roadmap, navigating within the roadmap to the vicinity of the goal, and then departing the roadmap to the goal. One advantage of the the roadmap approach is that a bulk of motion planning occurs in a one-dimensional space instead of a multi-dimensional search space.
Previous research includes the development of a roadmap, termed the hierarchical generalized Voronoi graph (HGVG), and its application to sensor based planning. Although the HGVG can be used when full knowledge of the world is known (e.g., in a CAD database), a key feature of the HGVG is that there is an incremental construction technique that generates the HGVG, using only line of sight local information. Unlike other sensor based planners, this incremental construction procedure rigorously has been proven to work in bounded environments. Simulations in three dimensions and experiments on a mobile robot have validated this approach where range sensor data is used.
The ultimate goal of this work is to enable highly articulated robots equipped with sensors to explore unknown environments. Most of the HGVG’s results are valid for robots that can be modeled as a point in spaces of arbitrary dimensions. Nevertheless, the focus of this work is in dimension three where workspace distance measurements are available via realistic sensors. Recent work includes the extension the definitions of the HGVG to the case of when the robot can be modeled as a line segment, sometimes called a rod. Although the rod HGVG is applicable to sensor based motion of robot blimps, it is just the first step towards the goal of sensor based motion planning for highly articulated robots. The next step is to extend the results of the rod roadmap to that of a convex set, which in turn will be extended to the development of a roadmap for a chain of convex sets which model a highly articulated robot.
