Three or more dimensional digital tangential graph and its motion-planning

摘要

A tangential graph has been widely used for selecting an optimal (shortest) path in a 2D environment with polygonal obstacles. The searching is very efficient because the size of a tangential graph is extremely small. However, it is difficult to design a smart method for constructing the graph in a 2D or 3D environment with free shaped obstacles. We firstly define a configuration space of a robotic manipulator as a 2D or 3D digital map, secondly construct a digital tangential graph in the map, and finally, select an optimal path from the graph by an A* algorithm. The size of a digital tangential graph and the speed of its A* search are ascertained by 2D and 3D graphics simulations.