基于分区思想的两阶段RRT^(*)算法

Two stage RRT^(*)algorithm based on partition idea

针对RRT^(*)算法采样效率低、搜索时间长等问题,提出了一种基于分区思想的两阶段RRT^(*)算法(TP-RRT^(*))。在探索阶段,利用自适应采样限制采样点的随机性,根据平行四边形法则合成新的矢量节点,既提升了采样点的方向性,又增强了算法对地图的搜索能力。在寻找最近点时,遍历整个随机树的过程存在计算量大、耗时长的问题,因此采用分区存储和检索的方法提升搜索的效率,同时限定分区中的节点数量,避免同一区域过度搜索。并在此基础上,生成一个新的父节点来改进原始算法中的重选父节点环节,进一步减少路径长度。最终在优化阶段时,通过对全局区域进行随机采样,并构造评估函数,得到可以改善路径的节点。仿真实验结果表明,改进算法与原算法在3种不同地图下,路径长度均减少了10%以上、时间均缩短了61%以上、节点数量均降低了75%以上;TP-RRT^(*)算法在路径规划的长度、时间、节点数等方面都优于Q-RRT^(*)和informed-RRT^(*)。

Aiming at the problems of low sampling efficiency and long search time of RRT'algorithm,a two-stage RRT^(*)algorithm based on partition idea(TP-RRT')is proposed.In the exploration phase,adaptive sampling is used to limit the randomness of the sampled points and synthesize new vector nodes according to the parallelogram rule,which both improves the directionality of the sampled points and enhances the algorithm's ability to search the map.In finding the nearest point,the process of traversing the whole random tree has the problems of large computation and time consumption,so the method of partitioned storage and retrieval is used to improve the efficiency of the search;at the same time,the number of nodes in the partition is limited to avoid excessive search in the same region.And on this basis,a new parent node is generated to improve the reselection of parent nodes in the original algorithm,further reducing the path length.Finally,at the optimization stage,the nodes that can improve the path are obtained by randomly sampling the global region and constructing an evaluation function.The simulation results show that the path length,time and node number of the improved algorithm are reduced by more than 10%,more than 61%and more than 75%respectively under three different maps.The TP-RRT'algorithm is superior to Q-RRT'and informed-RRT"in the length,time and number of nodes of path planning.