Path Planning Using a Tangent Graph for Mobile Robots Among Polygonal and Curved Obstacles

Abstract

This article proposes a tangent graph for path planning of mobile robots among obstacles with a general boundary. The tangent graph is defined on the basis of the locally shortest path. It has the same data structure as the visibility graph, but its nodes represent common tangent points on obstacle boundaries, and its edges correspond to collision-free common tangents between the boundaries and convex boundary seg ments between the tangent points. The tangent graph requires O(K ²) memory, where K denotes the total number of convex segments of the obstacle boundaries. The tangent graph in cludes all locally shortest paths and is capable of coping with path planning not only among polygonal obstacles but also among curved obstacles.