Sensor-Based Path Planning for Two-Identical-Link Robot using the Generalized Voronoi Graph

Abstract

We present a new roadmap based on a generalized Voronoi graph (GVG) for two-identical-link (L2) robots to explore an unknown planar environment. It is called the L2 hierarchical generalized Voronoi graph (L2-HGVG). The L2 robot is formed by two equal length rods with a revolute joint between them. Although the condition of two identical links looks somewhat constraining, the L2-HGVG is still worth pursuing because the case is very common in the engineering environment. The body of L2 robot is covered by sensors, and that the sensors ranges is distributed pointing in 360°. The obstacles can be measured using a series of range sensors, and the number of obstacles can be determined by local minima directly. The information of the unknown environment can be reliably detected by a robot, resulting in building L2-HGVG. The L2-HGVG is defined in terms of workspace distance measurements using only sensor information without prior knowledge of the environment, with the robot having the maximum distance from obstacles, and is therefore optimum in a point of view for exploration and obstacle avoidance. The configuration of robot possesses four degree-of-freedom, two for position and two for orientation. This means that the configuration space is R 2 × T 2, and the L2-HGVG is one-dimensional in the robot’s configuration space. The L2-HGVG includes two structures: the L2 generalized Voronoi graph (L2-GVG) and the L2R-edge. The L2-GVG edge is a retraction of a partitioning of the robot’s configuration space, so the L2-GVG is not always connected. We propose an additional structure to connect L2-GVG called the L2R-edge, where the robot is tangent to a planar GVG structure with the same orientation of the two links. L2R-edge is able to be used to connect dispersive L2-GVG edges and guarantee the connectivity of the roadmap L2-HGVG in configuration space.