针对快速搜索随机树*（RRT*）算法在三维状态空间寻找次优路径过程中收敛速度慢、规划的路径无法满足欠驱动水下无人潜航器实际航行约束等问题，建立考虑多约束的RRT*算法的改进算法。对于寻优过程速度慢的缺陷，改进算法通过增加随机树节点的概率引导措施，加大树扩展过程的目标趋向性，减少树节点随机拓展带来的冗余计算，从而加快随机树寻优的收敛过程；对于无人潜航器航行约束问题，利用潜航器的俯仰以及偏航角度约束结合原算法中的欧几里得距离进行节点间“伪距离”价值函数构建，从而使得规划路径进一步满足欠驱动水下无人潜航器的运动规律。经过Matlab仿真，在三维空间中相同迭代次数条件下，改进算法相比于传统的RRT*算法能够显著提高最优路径寻优的收敛速度，规划路径在俯仰和偏航角度变化符合水下无人潜航器的运动约束。
An improved algorithm for rapidly-exploring random tree* (RRT*) algorithm considering multiple constraints was established to address the slow convergence speed and inability of the planned path to meet the actual navigation constraints of underactuated underwater unmanned vehicles in the process of finding suboptimal paths in three-dimensional state space. For the defect of slow optimization process, the improved algorithm accelerates the convergence process of random tree optimization by increasing the probability guidance measures of random tree nodes, increasing the target tendency of tree expansion process, reducing redundant calculations caused by random expansion of tree nodes, and thus accelerating the convergence process of random tree optimization; For the navigation constraint problem of unmanned underwater vehicles, the pseudo distance value function between nodes is constructed by combining the pitch and yaw angle constraints of the vehicle with the Euclidean distance in the original algorithm, so as to further meet the operational laws of underactuated underwater unmanned vehicles in the planned path. After Matlab simulation, under the same number of iterations in three-dimensional space, the improved algorithm can significantly improve the convergence speed of the optimal path search compared to the traditional RRT* algorithm. The planned path conforms to the motion constraints of underwater unmanned vehicles in terms of pitch and yaw angle changes.
2024,46(8): 14-18 收稿日期：2023-4-18
DOI：10.3404/j.issn.1672-7649.2024.08.003
分类号：TP301
作者简介：曹园山(1992-),男,硕士,工程师,研究方向为水下无人潜航器导航与控制
参考文献：
[1] NASIR J , ISLAM F , MALIK U , et al. RRT*-Smart: A rapid convergence implementation of RRT*[J]. International Journal of Advanced Robotic Systems, 2013, 10(7): 299-310.
[2] GAMMELL J D, SRINIVASA S S, BARFOOT T D. Informed RRT*: optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic[C]//IEEE/RSJ International Conference on Intelligent Robots and Systems, 2014: 2997-3004.
[3] MASHAYEKHI R, IDRIS M, ANISI M H, et al. Informed RRT*-connect: an asymptotically optimal single-query path planning method[J]. IEEE Access, 2020(8): 1.
[4] 张兰勇, 韩宇. 基于改进的RRT*算法的AUV集群路径规划研究[J]. 中国舰船研究, 2023, 18(1): 43-51.
ZHANG L Y, HAN Y. Research on AUV cluster path planning based on improved RRT* algorithm[J]. Chinese Journal of Ship Research, 2023, 18(1): 43-51.
[5] 许万, 杨晔, 余磊涛, 等. 一种基于改进RRT~*的全局路径规划算法[J]. 控制与决策, 2022, 37(4): 829-838.
XU W, YANG H, YU L T, et al. A global path planning algorithm based on improved RRT~*[J]. Control and Decision-making, 2022, 37(4): 829-838.
[6] PEREZ A , JR R P , KONIDARIS G , et al. LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics[C]// IEEE International Conference on Robotics & Automation. IEEE, 2012: 2537-2542.
[7] WEBB D J , BERG J . Kinodynamic RRT*: optimal motion planning for systems with linear differential constraints: 10.48550/arXiv. 1205.5088[P]. 2012.
