Improving Efficiency in Path Planning: Tangent Line Decomposition Algorithm

Abstract

This paper introduces a tangent line decomposition (TLD) algorithm that efficiently finds collision-free paths close to optimal in both 2D and 3D environments. Compared with the existing visibility line-based algorithms, the proposed algorithm innovatively proposed the concept of tangent line decomposition, which decomposes complicated planning into many simple steps. For each step, only one key obstacle is taken into consideration. Besides, instead of constructing a complete graph, a best-first search algorithm is used to avoid searching redundant edges. The path planned by the algorithm is not the optimal path. However, following the idea of the informed RRT* algorithm, the path length planned by TLD can be used as a precondition for other optimal algorithms. In this way, the overall efficiency can be significantly improved. The simulations show that the proposed methods outperform existing methods regarding planning efficiency and solution quality.