Proposal of tangent graph and extended tangent graph for path planning of mobile robots

Abstract

A tangent graph (T-graph) for path planning of mobile robots among polygonal and curved obstacles is proposed. In the T-graph, the nodes correspond to tangent points on obstacle boundaries and the edges represent collision-free common tangents of the obstacles or convex boundary segments between the tangent points. The T-graph requires O(K/sup 2/) memory, where K denotes number of convex segments of obstacle boundaries. Further, to avoid recomputation of configuration spaces of circular robots in a polygonal environment when their radii has changed, an extended tangent graph (ETG) is developed. The ETG does not depend on obstacles in configuration spaces of robots but on obstacles in real workspace. Consequently, it is possible to plan a path flexibly according to different robots' sizes and safety distances by the ETG.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>