<p>Traditional path planning algorithms based on sampling typically rely on random sampling to find an initial solution. However, because of the sensitivity of these methods to the distribution of obstacles, the initial solution discovery is slower in complex environments, and the convergence efficiency during the optimization phase is lower. This paper presents an improved RRT* algorithm based on intelligent sampling, specifically the RRT*-Connect with Multi-Strategy Sampling (MSSC-RRT*) to address these issues. In the initial solution finding phase, to mitigate the blind randomness, a dynamic adaptive constrained sampling region strategy is established to improve the efficiency of initial path generation. In particular, during the Connect* phase, when a collision with an obstacle is detected, the algorithm recalibrates the sampling region by excluding quadrants aligned with the collision vector, optimizing the path search. In the iterative search for suboptimal solutions, MSSC-RRT* combines acceptably informed sampling and locally informed sampling strategies for planning. Based on the initial path, the algorithm uses the triangle inequality to generate an informed path and creates a local informed set to guide local sampling. This effectively narrows the search space, improves sampling efficiency for optimal path cost improvement, and accelerates suboptimal solution convergence. Furthermore, the asymptotic optimality of the MSSC-RRT* algorithm is demonstrated. Finally, diversified environments are constructed for simulation experiments. Compared to other algorithms, the results show that MSSC-RRT* reduces the average initial solution search time by 29.98% and the average suboptimal solution search time by 65.23%, demonstrating superior convergence speed and applicability in complex environments.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Research on an efficient path planning algorithm based on adaptive sampling and dynamically constructed local informed sets

  • Guo Gui,
  • Pingqing Fan,
  • Xipei Ma

摘要

Traditional path planning algorithms based on sampling typically rely on random sampling to find an initial solution. However, because of the sensitivity of these methods to the distribution of obstacles, the initial solution discovery is slower in complex environments, and the convergence efficiency during the optimization phase is lower. This paper presents an improved RRT* algorithm based on intelligent sampling, specifically the RRT*-Connect with Multi-Strategy Sampling (MSSC-RRT*) to address these issues. In the initial solution finding phase, to mitigate the blind randomness, a dynamic adaptive constrained sampling region strategy is established to improve the efficiency of initial path generation. In particular, during the Connect* phase, when a collision with an obstacle is detected, the algorithm recalibrates the sampling region by excluding quadrants aligned with the collision vector, optimizing the path search. In the iterative search for suboptimal solutions, MSSC-RRT* combines acceptably informed sampling and locally informed sampling strategies for planning. Based on the initial path, the algorithm uses the triangle inequality to generate an informed path and creates a local informed set to guide local sampling. This effectively narrows the search space, improves sampling efficiency for optimal path cost improvement, and accelerates suboptimal solution convergence. Furthermore, the asymptotic optimality of the MSSC-RRT* algorithm is demonstrated. Finally, diversified environments are constructed for simulation experiments. Compared to other algorithms, the results show that MSSC-RRT* reduces the average initial solution search time by 29.98% and the average suboptimal solution search time by 65.23%, demonstrating superior convergence speed and applicability in complex environments.