Three or more dimensional digital tangential graph and itsmotion-planning

摘要

A tangential graph has been widely used for selecting an optimal(shortest) path in a 2D environment with polygonal obstacles. Thesearching is very efficient because the size of a tangential graph isextremely small. However, it is difficult to design a smart method forconstructing the graph in a 2D or 3D environment with free shapedobstacles. We firstly define a configuration space of a roboticmanipulator as a 2D or 3D digital map, secondly construct a digitaltangential graph in the map, and finally, select an optimal path fromthe graph by an A* algorithm. The size of a digital tangential graph andthe speed of its A* search are ascertained by 2D and 3D graphicssimulations