ATS-RRT*: an improved RRT* algorithm based on alternative paths and triangular area sampling

Abstract

AbstractThe Rapidly Exploring Random Tree Star (RRT*) is a probabilistically complete algorithm. It is recognized as a better path planning algorithm, but its path quality and path planning speed still have room for improvement. This paper proposes an improved RRT* algorithm based on alternative paths and triangular area sampling (ATS-RRT*). The alternative paths strategy generates multiple initial paths based on whether the sample points can communicate with the target points and set the path with the smallest cost as the final initial path, which can speed up the initial path planning and improve the initial path finding rate. The triangular area sampling strategy combines every three adjacent nodes to generate some triangle areas and corresponding half-triangle areas. The path quality can be improved quickly by limiting the sampling in these triangle areas. In addition, the direct connection strategy with triangle nodes and the tabu table using in the Rewire process also speeds up the algorithm. Experiments show that the speed of finding the initial path and the success rate of finding the suboptimal path are improved by 2.3 and 1.45 times respectively compared with RRT*, Quick-RRT*, and Informed + Quick-RRT*.KEYWORDS: RRT*path planningsampling-based algorithmsdirect connection strategy Disclosure statementNo potential conflict of interest was reported by the author(s).Additional informationFundingThis work was supported by the National Natural Science Foundation of China [grant number 61873188, No. 32171902]; Natural Science Foundation of Tianjin [grant number 18JCYBJC19300].Notes on contributorsZhi-wei ZhangZhi W. Zhang is a mechanical engineering student at Tianjin University of Technology.Yun-wei JiaYun W. Jia is with the Tianjin University of Technology.Qi-qi SuQi Q. Su is a mechanical engineering student at Tianjin University of Technology.Xiao-tong ChenXiao T. Chen is a mechanical engineering student at Tianjin University of Technology.Bang-peng FuBang P. Fu is with the Tiandy Technologies Co., Ltd.