VLSI-efficient schemes for high-speed construction of tangent graph

Tangent graph based data structure has been readily used in motion planning for mobile robots and robot manipulators. The complexity of the tangent graph grows exponentially as the robot's configuration space increases in dimension. The ability to construct larger number of tangents at high speed thus becomes crucial to facilitate dynamic motion planning where on-line avoidance is necessary. In this paper, we present efficient schemes for construction of tangent graphs for an environment consisting of both non-convex and convex obstacles. The proposed technique for tangent graph construction is based on a gradient computation approach that encompasses binary search, logarithmic approximation, and half-plane computation modules. The modules were ported to Very Large Scale Integration (VLSI) using commercial tools. Synthesis results show that each module has a latency of only 7.2 ns and a total chip area of about 7K NAND gates, thus demonstrating that the proposed techniques are highly appropriate for tangent graph computations in real-time applications. © 2005 Elsevier B.V. All rights reserved.