In this work, we consider the motion planning of a convex shaped robot to explore an unknown planar workspace, i.e., an unknown configuration space diffeomorphic to SE(2) with holes removed from it. This new algorithm actually has two control laws (i.e., behaviors) and an arbitration scheme among the laws. These laws, as well as the arbitration scheme, are derived from a new roadmap called the convex hierarchical generalized Voronoi graph (convex-HGVG), which is the central contribution of this paper. This roadmap is defined in terms of workspace distance information that is within line of sight of the convex body. The challenge in defining the roadmap is that punctured SE(2) does not have, in general, a one-dimensional retract.

Therefore, we decompose the punctured SE(2) into contractible regions in which we define convex generalized Voronoi graph (convex-GVG) edges and then connect these regions with R-edges. The convex-GVG edges and the R-edges together form the convex-HGVG. We show that the convex-HGVG is indeed a roadmap and then we demonstrate the control laws that a robot can invoke that incrementally constructs it.

The definition of GVG-edge is rather straighfoward, i.e., it is defined as the set of three-way equidistant configuration. As in the case of the planar rod, the convex-GVG edges are not necessarily connected.

As in the case of the rod, we try to connect the GVG-edges using the connectivity of the workspace, i.e. using point-GVG. However, for the convex shape, there is no natural way to align the robot along the point-GVG edge. In the case of the rod, the R-edge is defined as the set of double equidistant configurations that are tangent to the point GVG edge. From this condition, actually it follows that the R-edge are the edge which attains the maximum value of the minimum distance along the edge among all the two-way equidistant path (or actually among all the path that connects two GVG-edges). To generalized the notion of ``tangency'' used in the rod-HGVG, we use the height function and the principal axes, which are the orientations of the robot where the robot attains the local minima of the height function. Note that for the case of the rod, the two principal are the rod itself. The convex-R-edge is then defined as the set of double equidistant configuration such that one of the principal axes is normal to the vector Ci - Cj, where Ci, Cj are the closest point on the two closest obstacles. Then it can be shown that the path defined in this way is the two-way equidistant path that attains the maximum value of the minimum distance along the path.