Sensor-based construction of a retract-like structure for a planar rod robot

Sensor-based planning for rod-shaped robots is necessary for the realistic deployment of noncircularly symmetric robots into unknown environments. Whereas circularly symmetric robots have two-dimensional Euclidean configuration spaces, planar rod robots posses three degrees-of-freedom, two for position and one for orientation, and hence have a three-dimensional configuration space, SE(2). In this work, we define the rod hierarchical generalized Voronoi graph (rod-HGVG) which is a roadmap of the rod´s configuration space. Prior work in Voronoi-based roadmaps use a retraction of the robot´s free space to define the roadmap; here, we break apart the robot´s free space into regions where fragments of the roadmap are defined and then connect the fragments. The primary advantage of the rod-HGVG is that it is defined in terms of workspace distance measurements, which makes it amenable to sensor-based planning. This paper also includes a numerical procedure that generates the rod-HGVG edge fragments using only information that is within line of sight of the rod robot. It is worth noting that this procedure does not require an explicit definition of configuration space, i.e., this procedure constructs a roadmap of rod configuration space without ever constructing the configuration space itself