基于人工势场法和启发式采样的最优路径收敛方法

具有渐进最优性的快速搜索随机树（RRT^*）算法在路径规划过程中确保了其概率完备性和渐进最优性,然而仍存在收敛速度慢且产生大而密集的采样空间等问题。为了加快算法的收敛速度,提出了一种基于人工势场法和启发集合采样来快速获取最优路径的方法。首先,利用人工势场法构建出一条由起点到目标点的初始路径;然后,以起点和目标点的位置和之间的距离以及初始路径的路径代价作为参数来构建初始启发采样集合;最后,限定在启发集合内进行采样,并且在算法进行的过程中调整启发采样集合的范围,进而加快路径收敛速度。仿真实验中,获取相同路径代价的路径时,所提人工势场结合启发式采样的方法为基础的结合人工势场法和启发采样策略的快速获取最优路径的RRT^*（PI-RRT^*）算法相较于RRT^*算法,采样点数减少了约67%,算法运行时间平均缩短了约74.5%;相较于启发式RRT^*（Informed-RRT^*）算法,采样点数减少了约40~50%,算法运行时间平均缩短了约62.5%。所提出的最优路径收敛方法大量减少了冗余采样次数并缩短了算法运行时间,具有更高的算法效率,收敛到最优路径的速度更快。     

基于改进渐进最优的双向快速扩展随机树的移动机器人路径规划算法

针对带启发式的快速扩展随机树（RRT-Connect）算法路径生成的随机性以及渐进最优的双向快速扩展随机树（B-RRT^*）算法收敛速度的缓慢性，提出了一种基于B-RRT^*改进的高效路径规划算法（EB-RRT^*）。首先引入一种智能采样函数，使随机树的扩展更具方向性，从而减少寻路时间，并提高路径的平滑性；其次在B-RRT^*算法的基础上，在EB-RRT^*算法中加入了一种快速扩展策略，使改进后的算法在自由空间中使用RRT-Connect算法的扩展方式进行快速扩展，而在障碍物空间则使用改进的渐进最优的快速扩展随机树（RRT^*）算法进行扩展，在提高扩展效率的同时避免算法陷入局部最优。将EB-RRT^*算法分别与快速扩展随机树（RRT）、RRT-Connect、RRT^*和B-RRT^*算法进行仿真对比，仿真结果表明，改进后的算法在路径规划效率及路径平滑性方面均明显优于其他算法；且相对于B-RRT^*算法，其在路径规划时间上降低了68.3%，在迭代次数上减少了48.6%。     

基于采样点优化RRT算法的机械臂路径规划

针对基于随机采样的RRT机械臂路径规划算法在全局工作空间下采样效率低、随机性强等问题,提出一种基于采样点优化RRT算法的机械臂路径规划算法.相对于全局工作空间采样,优化算法首先基于非障碍物空间生成随机采样点,以降低算法碰撞检测概率与冗余节点的生成,再结合一定概率的人工势场法产生启发式采样点,使得机械臂臂体于路径规划采样过程中既能保证随机采样的概率完备,又能使采样点更具目标导向性.其次,为使得路径更加简洁平滑,使用冗余节点删除策略剔除路径中的冗余节点来优化最终路径.最后在二维、三维的仿真环境中对优化算法进行对比实验分析,以验证算法在随机采样路径规划算法中的良好性能,并在IRB 1200-7/0.7机械臂上进行避障规划算法实验.仿真和实验结果都表明,所提出的算法在机械臂路径规划中可以获得更高的规划效率和更优的路径.     

复杂环境下基于采样空间自调整的航迹规划算法

针对具有渐进最优性的快速扩展随机树（RRT^*）算法在面对高维、复杂环境时所表现出的寻路效率低、收敛速度缓慢的问题,在RRT^*的基础上,提出一种基于采样空间自调整的渐进最优快速扩展随机树（AS-RRT^*）无人机（UAV）航迹规划算法。该算法可以自适应调整采样空间,进而引导树更为高效地生长,而这些主要通过有偏采样、节点筛选和节点学习这三种策略来实现。首先,在采样空间中定义向光和背光区域来进行有偏采样,而向光和背光区域的概率权重由当前扩展失败率决定,从而保证算法在搜索初始航迹时同时具有探索性和方向性;然后,在完成初始航迹的搜索后,算法就开始周期性地筛选节点,高质量的节点作为学习样本来产生新的抽样分布,质量最低的节点在算法达到最大节点数量后被新节点替代。在多种不同类型的环境下进行了对比仿真实验,结果表明所提算法在一定程度上改善了采样算法固有的随机性,而且相较于传统的RRT^*算法,该算法在相同环境里使用了更少的寻路时间,在相同时间里生成了更低代价的航迹,且在三维空间里的改进更为明显。     

融合安全A*算法与动态窗口法的机器人路径规划

A^*算法通过启发信息指引搜索方向,被广泛应用于移动机器人的路径规划,但其规划出的搜索路径存在冗余节点且与障碍物相近,无法满足动态避障需求。对标准A^*算法进行改进,设计安全A^*算法并融合动态窗口法进行路径规划。定义安全距离因子引入A^*算法的启发函数中,提高算法规划路径的安全性,同时采用平面结构法对算法规划得到的路径进行优化,根据相邻节点与障碍物之间的位置关系判断该相邻节点间是否存在障碍物,由此减少路径拐点数,提高路径平滑度。由于当移动机器人处于未知环境时,仅靠A^*算法不能避开障碍物到达目标点,因此借助动态窗口法的局部避障功能。通过安全A^*算法规划全局最优路径节点坐标,设计融合子函数改进动态窗口法的评价函数,解决动态窗口法易陷入局部最优的问题。实验结果表明,在复杂环境中,该方法通过融合安全A^*算法和动态窗口法,能够确保在安全路径基础上实时随机避障,使机器人安全到达终点。     

基于改进A*算法的无人车路径规划

传统的A^*算法在无人车路径规划中存在规划时间较长和搜索范围较大的缺点。综合分析A^*算法的计算流程后,从四个方面对A^*算法进行改进：1）目标性拓展,即根据待扩展节点和目标节点的相对位置来有目标性地选择不同的象限进行节点拓展;2）目标可见性判断,即判断待扩展节点与目标点之间有无障碍物,若无障碍物则跳出A^*算法的探索过程,以此减少多余的搜索;3）改变A^*算法的启发函数,即增加待扩展节点的n辈父节点到目标点的代价估计,以此减少到目标点的代价估计的局部最优情况;4）改变扩展节点的选取方略,即改变传统的最小化启发函数来选择扩展节点的方式,通过引入模拟退火法来优化扩展节点的选择方式,使得搜索过程尽可能向靠近目标点的方向进行。最后通过Matlab仿真实验结果表明,在模拟的地图环境下,提出的改进A^*算法在运行时间上减少67.06%,经历的栅格数减少73.53%,优化路径长度浮动范围在±0.6%。     

一种基于改进A*算法的室内导航路径规划方法

路径规划是室内导航研究的关键技术之一。A^*算法是一种常见的路径规划算法,当区域的点数量较少时,找寻最优路径是最有效的直接搜索方法。但当路径点规模较大时,使用数值优化算法求解最佳路径的难度急剧增加,导致规划时间所需时间过长,不符合实时性要求。为提高路径规划方法中的效率和稳定性,在梳理室内导航路径规划已有算法和方案的基础上,分析了A^*算法的基本思想与实现步骤,并针对室内导航中A^*路径算法存在的问题,提出了一种改进型A^*算法优化的方案。利用用户对最短距离和直行路程的需求,在位置计算中,引入同时考虑方向和距离启发信息的启发函数,把POI点与寻路节点分开处理,以映射的方式建立联系。将该方案应用于室内导航中A^*算法实现伪代码,对算法改进前后进行算法效率测试。结果表明,改进后A^*算法的整体效率提升了近50%,改进型A^*算法在室内导航路径规划的效率和稳定性比较优,达到了加速导航算法的目的。     

基于改进A*算法的移动机器人路径规划

为了解决较大场景下A^*寻路算法存在的内存开销大、计算时间长等问题,本文在A^*算法的基础上,结合跳点搜索算法,提出一种改进的A^*算法．该算法通过筛选跳点进行扩展,直到生成最终路径,扩展过程中使用跳点代替A^*算法中大量可能被添加到OpenList和ClosedList的不必要节点,从而减少计算量．为了验证改进A^*算法的有效性,分别在不同尺寸的2维栅格地图中进行仿真,仿真结果表明,相比A^*算法,改进A^*算法在寻路过程中扩展更少的节点,寻路速度更快,且加速效果随环境地图的增大更加明显．最后将改进A^*算法应用于移动机器人Turtlebot2进行对比实验．实验结果表明,在生成相同路径的基础上,改进A^*算法的寻路速度较A^*算法提高了约200%,能够满足移动机器人路径规划的要求．     

面向UAV的三维空间快速路径规划算法

无人机、无人水下机器人等工作在三维空间中的无人飞行器在进行路径规划时采用的路径规划算法多数为RRT*算法，但RRT*算法存在收敛速度较慢、迭代次数多、采样点利用率低、需要频繁进行碰撞检测等问题，针对现有算法采样的不足，提出双向自由化生长树算法（B-SOGT*）。该算法采用双向搜索、双引力场、试探性弹性扩张的方法来实现无人机在三维空间中的路径规划。双向搜索分别以起始点和目标点为根节点，构造出2棵随机树同时进行空间搜索，这样的方式提高了搜索效率；双引力场是分别以2颗随机树的根节点为中心生成的引力场，在引力场的作用下采样效率得到提升；试探性弹性扩张方法在生成路径时，引入父节点重选机制，并且去掉碰撞检测过程，提高了算法计算速度。仿真验证表明，B-SOGT*算法在取消碰撞检测过程后，拥有收敛速度更快、路径质量更优、迭代次数更少的优势。     

改进 Ｄ∗ｌｉｔｅ 和时间弹性带法的移动机器人路径规划

为解决D*lite算法在进行路径规划时搜索效率低,易受运动物体影响及路径贴近障碍物的问题,提出了一种结合改进D*lite算法和时间弹性带法的融合算法。首先,将改进的跳点搜索引入到D*lite算法中,让算法只对跳点进行访问,实现了规划时间和路径长度的双优化。之后,融合改进的时间弹性带法进行局部路径规划,提高算法动态规划能力的同时保证了规划路径的安全性。仿真结果表明,改进的D*lite算法比原始D*lite算法在路径长度、规划时长及路径节点数上分别平均优化了6.40％、49.13％和73.70％。在实际表现中,融合算法在动态情况下比原始D*lite算法可减少11.04％的路径长度、67.10％的规划时长及11.99％的运动时间,并且保证了机器人和障碍物间的最小距离。     

目标偏置双向RRT*算法的机器人路径规划

针对RRT*和B-RRT*算法在较复杂环境下路径规划时,存在搜索时间长、采样效率低和规划路径曲折的问题,提出一种目标偏置双向快速扩展随机树算法——GBB-RRT*(goal biased bidirectional RRT*).该算法每次迭代中两棵随机树都进行扩展,一次迭代能生成两个新节点,加快扩展速度.然后引入目标偏...     

基于改进RRT算法的无人车路径规划

针对无人车在复杂环境中进行全局路径规划时存在的盲目搜索、节点冗余、路径不光滑及不安全等问题,提出一种基于快速扩展随机树(RRT,rapidly-exploring random tree)的综合改进路径规划算法;首先引入目标动态概率采样策略和人工势场引导随机树扩展机制;其次根据汽车运动学模型,对规划的路径进行转角约束和碰撞检测,保证路径的安全性;然后引入Reeds-Sheep曲线用于直接与目标位姿进行连接,避免多余的位姿调整;最后对路径进行剪枝和平滑处理,得到一条更短更光滑的路径;在实验部分,针对不同仿真环境,以规划时间、路径长度和节点数目作为评价指标,对比了RRT算法、RRT*算法和文章算法的路径规划效果;实验结果显示,文章算法相比于RRT算法和RRT*算法,节点数目分别减少了58.94%和85.22%,规划时间分别缩短了61.20%和79.23%,且路径长度相比于RRT算法缩短了17.26%,并和RRT*算法规划的最优路径长度相近。     

基于动态变采样区域RRT的无人车路径规划

针对无人车传统RRT路径规划算法节点搜索盲目性、随机性以及路径曲折不连续等问题,提出一种动态变采样区域RRT路径规划算法(dynamic variable sampling area RRT, DVSA-RRT).首先,初始化地图信息,根据动态变采样区域公式划分采样空间,进而选择采样区域;在此基础上,利用基于安全距离的碰撞检测、概率目标偏置策略和多级步长扩展完成初始路径规划;最后,利用考虑最大转角约束的逆向寻优和3次B样条曲线对初始路径进行拟合优化.仿真结果表明,该算法相较于原始RRT算法在不同地图环境下的搜索时间和采样次数均降低50%以上,大大降低了节点搜索的盲目性和随机性,相较于其他算法搜索时间也减少30%以上,且优化后的路径平滑满足车辆运动动力学约束.     

基于PS-RRT算法的机械臂避障路径规划

针对应用快速搜索随机树（RRT）算法进行机械臂路径规划时,存在采样区域大、有效区域小、路径冗余节点多、剪枝时间长等问题,提出一种基于分区动态采样策略和重复区域节点拒绝机制的高效RRT路径规划算法PS-RRT（partitioned sampling RRT）。首先,通过PS-RRT快速规划机械臂末端初始路径;其次,分段检测机械臂跟随该路径时的连杆碰撞情况,对碰撞路段进行带臂形约束的第二次规划;最后,将初始路径和第二次规划的路径拼接后进行路径裁剪。将所提方法在多种场景中进行仿真验证,结果表明：基于PS-RRT算法的机械臂避障路径规划策略使得无效节点数大幅减少,可高效规划出机械臂的无碰路径,验证了算法的可行性。     

涡流人工势场引导下的RRT*移动机器人路径规划

为了解决快速扩展随机树(R RT)在障碍物密集、通道狭窄的环境中收敛速度缓慢、采样节点密集、路径曲折复杂等问题,围绕RRT的一种常见的变体算法RRT*,设计了一种由人工势场(APF)引导RRT*进行路径规划的方法.首先,使用涡流约束向外发散的斥力场,沿着切向梯度方向形成涡流场,并利用涡流人工势场(VAPF)在RRT*偏...     

Optimal path planning in cluttered environment using RRT*-AB

Rapidly exploring Random Tree Star (RRT*) has gained popularity due to its support for complex and high-dimensional problems. Its numerous applications in path planning have made it an active area of research. Although it ensures probabilistic completeness and asymptotic optimality, its slow convergence rate and large dense sampling space are proven problems. In this paper, an off-line planning algorithm based on RRT* named RRT*-adjustable bounds (RRT*-AB) is proposed to resolve these issues. The proposed approach rapidly targets the goal region with improved computational efficiency. Desired objectives are achieved through three novel strategies, i.e., connectivity region, goal-biased bounded sampling, and path optimization. Goal-biased bounded sampling is performed within boundary of connectivity region to find the initial path. Connectivity region is flexible enough to grow for complex environment. Once path is found, it is optimized gradually using node rejection and concentrated bounded sampling. Final path is further improved using global pruning to erode extra nodes. Robustness and efficiency of proposed algorithm is tested through experiments in different structured and unstructured environments cluttered with obstacles including narrow and complex maze cases. The proposed approach converges to shorter path with reduced time and memory requirements than conventional RRT* methods.     

基于改进双树RRT*算法的冗余机械臂末端路径规划

针对冗余机械臂的冗余特性与相关RRT*算法在规划机械臂末端路径的应用中存在的搜索效率较低、收敛性不稳定以及没有充分考虑到机械臂末端几何构型与自身运动特性对路径规划影响的问题,提出一种改进策略。首先,引入一种基于根尾节点连线夹角的采样点选择方式,并设置目标逼近区域。根据连续采样成功次数动态选择改进采样与随机采样。接着,将双树扩展策略与上述方法相结合。最后,将初始可行路径进行二次重连得到最终的优化路径。通过验证,改进双树RRT*方法能够有效地提升搜索效率、收敛性以及路径的优越性。虚拟碰撞体与胶囊碰撞体的引入也能较好地应对机械臂末端结构与运动特性带来的影响。使用Mujoco物理仿真引擎进行机械臂运动验证,证明该策略可以为冗余机械臂末端规划出一条较优的可行路径。