改进A*算法的智能车路径规划研究

由于A*算法所规划的路径存在着转折次数多,路径不平滑,路径贴合障碍物和初始时刻转折角度过大等不符合车辆运动学的问题。为了解决上述问题,获得适用于智能车的优化路径,本文通过对车辆运动学建模得到车辆的约束,同时在估价函数中加入车身轮廓代价和障碍物距离代价,并将车辆约束加入到A*算法的启发函数和路径优化中,再使用贝塞尔曲线拟合转折点,使A*算法所生成的路径更加符合车辆的运动学。通过分析改进A*算法可知,改进后的算法所规划的路径更加平滑、合理且符合车辆的运动特性。     

基于改进A*算法和lattice算法的路径规划方法

针对A*算法缺乏动态性、不够平滑、计算量大,且不满足具体的非完整约束等问题,提出一种融合改进A*算法和lattice算法的路径规划方法.一方面消除传统A*算法中的冗余点,同时考虑物体的方向属性和实际运动约束,优化启发式函数最终生成全局路径.另一方面lattice根据改进A*算法生成的全局路径作为参考线,采样并结合障碍物信息和其他代价信息选出平滑的、无障碍的包含位置、移动速度、移动加速度等信息的局部轨迹.使用栅格地图进行车辆路径规划的实验仿真,该算法能够兼顾全局与局部,快速规划出一条平滑且满足车辆非完整性约束的运动路径.     

基于方向引导的智能车VFH+路径规划算法研究

针对矢量场直方图（VFH+）算法在路径规划过程中容易陷入环境死区,生成的路径不能满足车辆运动学限制的问题,提出方向引导的VFH+路径规划算法。首先在双向快速随机树（Bi-RRT）节点扩展中引入车辆的运动学约束,在去除路径上冗余节点的基础上,使用三次B样条曲线得到平滑引导路径。其次,在VFH+算法中引入车辆的最大转角约束与引导路径的离散点方向,来限制VFH+的候选方向范围,并修改代价函数获取合适的前进方向。最后,在MATLAB软件上进行算法的仿真对比以及基于ROS平台的实验验证。结果表明,改进后的VFH+算法能够在满足车辆运动学约束的情况下,生成一条避开环境死区的有效路径。     

基于B-RRT*FND算法的移动机器人路径规划

针对RRT*FN算法获取路径解的速度慢,且无法应用于动态环境等问题,提出固定节点数的动态双向渐近最优快速随机扩展树算法(bidrectional RRT* fix-node dynamic, B-RRT*FND),用于解决移动机器人在二维空间内快速实时获取无碰撞路径的问题.所提出算法基于RRT*FN算法,采用双向贪婪搜索方法加快路径搜索速度,解决单向RRT算法由于随机采样的盲目性造成的搜索速度慢、在狭窄环境下难以搜索到解的问题;利用固定节点算法在规划过程中不占用过多计算量的特点,在路径迭代优化过程中,实时更新地图信息,并对被破坏的原始路径进行修复重连,以完成算法的动态规划.将所提出算法与RRT、RRT*FN等算法在3种环境下进行对比仿真,验证结果表明,所提出算法在规划速度、路径解长度以及动态规划性能方面具有较好效果.     

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

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

基于变步长A*与车身稳态转向模型的UGV路径规划

针对A*算法寻路时间长、生成的路径存在冗余折点的问题,本文提出一种基于车身稳态转向模型的变步长A*算法,首先通过设置子目标点的方式调节A*算法的搜索步长,减少寻路时间;其次在全局路径的折点处根据车身转向运动学约束进行局部重规划,从而得到一条易于跟踪的平滑路径;此外考虑到UGV (Unmanned Ground Vehicle,无人地面车辆)的实际宽度,改进后的算法还引入了障碍物延伸策略,使规划出的路径满足实际工程应用;最后通过仿真实验验证了本文改进算法的有效性,并与3种寻路算法进行对比,结果表明,本文改进的算法寻路时间更短、生成的路径更平滑,且与障碍物之间保持了安全距离.     

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

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

改进A*算法融合自适应DWA的移动机器人动态路径规划

为解决传统A*算法和传统动态窗口法（Dynamic window approach,DWA）在移动机器人路径规划中存在的问题,提出一种改进A*算法和改进DWA相结合的动态路径规划方法。首先,采用16邻域16方向的路径搜索方式扩大路径搜索视野,减少节点访问量和转角度数;其次,对启发函数进行优化,增强路径搜索的目的性;接着,采用冗余点删除策略,减少转折点数目,路径平滑度进一步提高,再使用B样条曲线对路径拐角进行处理,得到的路径较为平滑;然后,在DWA的评价函数中对障碍物进行分类并区别对待以及添加速度自适应因子,能够提高避障灵敏度;最后,通过与其他算法进行三部分仿真实验以及优先级策略仿真实验,验证改进A*算法的有效性和融合方法避障的优越性。     

基于MB-RRT*的无人机航迹规划算法研究

随着小型无人机的广泛应用,提高无人机的自动巡航能力变得至关重要。无人机航迹规划是指其在已知环境地图信息下展开航迹规划,实现无碰撞的、平滑的、从初始点到达目标点的路径。针对现有算法依然存在收敛速度慢、内存消耗大、航迹规划固定步长和航迹平滑度无法满足实际无人机飞行等问题,提出了MB-RRT*(Modified B-RRT*)算法,通过懒惰采样方法加快算法收敛速度并减少内存占用;设计自适应步长来解决算法在障碍物附近生长树的局限性问题,从而提高了找到初始可行解的速度和质量;然后利用降采样和3次贝塞尔插值算法实现了曲线拟合的功能,使算法最终生成相对平滑的航迹,为无人机实际飞行提供可行的航迹规划方法。最后在多组不同环境复杂度的实验中,通过与其他算法相比较,验证了所提算法的有效性。     

融合环境信息和运动约束的改进A*算法研究

标准A*算法存在着无法考虑移动机器人运动特性及处理后的路径不利于移动机器人运动等问题。针对这一问题提出了一种新改进A*算法,通过环境信息引入障碍物权重系数来改进算法的启发函数并进行全局路径规划;优化搜索节点的选取方式和设定障碍物与路径之间的安全距离;基于对移动机器人的运动特性的考虑优化其路径,并在不同环境地图中与其他算法进行仿真实验对比分析。相关实验表明：基于新改进A*算法规划的路径始终与障碍物保持一定的安全距离;改进A*算法在时间上相比标准A*算法平均减少了80%,路径长度平均减少了2%,路径转角平均降低了82%。改进后算法相比其他算法在时间、搜索节点以及平滑度上有很大的改进,融合机器人环境信息和运动特性的规划路径算法可为移动机器人的路径规划提供一种新的方法。     

改进RRT的二阶段平滑搜索算法

在复杂的环境当中,智能车辆路径规划模块的职能是产生一条合适的路径让智能车路径跟踪模块进行跟踪。在路径规划模块中要考虑两个方面：第一个方面是算法能够快速地搜索出一条安全的路径;第二个方面是算法进行路径规划的同时能够考虑车辆自身模型的约束,即运动学约束限制。然而快速搜索随机树RRT算法进行大范围路径搜索的过程中存在收敛速度较慢、搜索路径曲折角度过大的问题,导致车辆跟随时转弯角度过大、转向不连续,不满足车辆运动学模型。二阶段RRT算法TSRRT（Two-Stage RRT）采用融合最大转向角度的三次Bezier曲线进行上边界曲率优化,使规划路径能够满足车辆运动的转向角度,让车辆在行驶过程中能够以不停车的方式进行连续平稳转向;同时为了加快算法的收敛速度,通过第一阶段的启发式函数采样搜索以及第二阶段Dubins曲线直接连接最终终点和第一阶段搜索终点,能够有效地提高算法的整体搜索效率。通过实验验证,改进的RRT算法TSRRT,相比于传统RRT算法搜索时间减少近43%,路径长度减少近25%,同时提高了路径的平滑性,使已搜索路径曲率能够满足连续,能够让车辆在不停止的情况下连续平稳转弯,以便车辆后续更好地进行路径跟踪。     

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

A*算法常用于二维地图的路径规划,但是在利用其进行室内移动机器人路径规划时,存在过多的冗余点和拐点,造成了内存消耗过大和路径不平滑。针对上述问题,提出了一种改进的A*算法。结合跳跃点搜索理论,利用先验信息,用选取的关键点代替了传统A*算法中Openlist和Closelist的点,减小了计算量,提高了运算速度。运用反向搜索策略,对路径进行二次规划,删除不必要的转折点,降低了路径长度。将路径在转折点处进行动态圆平滑处理,提高了路径的平滑性。为了验证改进A*算法的性能,将其应用于不同尺寸仿真栅格环境地图和处于真实室内环境的机器人中,实验结果表明,在相同环境下,改进算法相较于传统的A*算法,在运行时间、路径长度和平滑程度上均有明显的提高。     

关键节点和平滑处理的PRM路径优化方法

针对移动机器人路径规划采用的概率路图（Probabilistic Roadmap,PRM）算法存在路径拐点过多以及部分转角过陡的问题,提出一种PRM路径优化方法。PRM算法在构建路径网络图时采用随机采样,路径并非最优,路径节点过多,使用Douglas-Peucker（D-P）算法提取PRM算法生成初始路径节点中的关键节点,用关键节点代替原来的初始路径节点,以减少路径中拐点的个数。使用Clothoid曲线对新生成的路径进行平滑处理,达到路径优化的目的。仿真结果表明该优化方法能减少路径节点的个数,并使路径更加平滑。     

改进BIT*与DWA算法的动态路径规划

传统批通知树（batch informed trees,BIT*）算法结合了RRT*算法和A*算法的优势,但是该算法在复杂环境下无法躲避未知的动态障碍物,无法完成动态路径规划。针对该问题,提出了一种将改进的BIT*算法和改进的DWA算法相融合的算法。在传统BIT*算法的基础上对路径进行拉伸优化,提取关键转折点,减少路径长度;对传统DWA算法的距离评价函数进行改进、引入轨迹点评价函数,避免局部规划过分偏离,也减少了已知障碍物对路径的影响;将改进的BIT*算法与改进的DWA算法相融合,将提取的关键转折点作为DWA的中间目标点,弥补全局规划算法无法躲避动态障碍物的缺点以及局部规划算法全局能力低下的缺点。在动静态地图中对RRT*算法、BIT*算法、DWA算法、改进BIT*算法以及融合算法进行仿真实验,仿真结果表明：在复杂环境中,改进的BIT*算法具有更短的路径和更少的拐点;与传统的DWA算法相比,融合算法规划的路线更平滑,机器人既能实时动态避障抵达终点,又能更加贴近全局路径,保证路线全局最优。     

基于BIM的建筑机器人自主路径规划及避障研究

针对建筑机器人进入施工位置全局路径规划最优且可实时避障的要求,提出了一种新型的导航地图建立方法,通过建筑物BIM（Building Information Modeling）模型建立导航地图,通过优化A*算法搜索点选取策略,以及删除了路径上的冗余转折点,缩短算法运行时间,且规划出的全局路径不会紧贴着建筑物墙壁,有效降低了机器人与墙体发生碰撞的可能性。结合动态窗口算法进行局部路径规划,在全局路径关键点之间使用动态窗口法,且加入了新的刹车判定条件,使得机器人的运动连续化。实验结果表明改进后的A*算法运行时间相较于原始算法减少50%以上,每去除一个冗余转折点路径长度减少0.4?m,路径与障碍物之间的距离比原始算法增加了2倍,结合了动态窗口法之后能够较好地避开障碍且输出的控制参数连续化。     

Autonomous ground vehicle path tracking

Autonomous ground vehicle navigation requires the integration of many technologies such as path planning, position and orientation sensing, vehicle control, and obstacle avoidance. The work presented here focuses on the control of a nonholonomic ground vehicle as it tracks a given path. A new path tracking technique called “vector pursuit” is presented. This new technique is based on the theory of screws, which was developed by Sir Robert Ball in 1900. It generates a desired vehicle turning radius based on the vehicle's current position and orientation relative to the position of a point ahead on the planned path and the desired orientation along the path at that point. The vector pursuit algorithm is compared to other geometrical approaches, and it is shown to be more robust, resulting in more accurate path tracking. © 2004 Wiley Periodicals, Inc.     

基于改进A*算法的无人机三维空间避障路径规划

无人机在有障碍物的三维空间环境中飞行,采用常规A*算法进行避障航线的规划存在搜索节点多、搜索区域大、搜索时间长、搜索效率低、生成的航线拐角多且含有大量非必要冗余航点、没有考虑无人机自身体积与尺寸而引发的飞行中与障碍物边界碰撞的航线不安全等问题。因此，设计一种改进A*算法,首先,考虑无人机本身体积与尺寸,提出一种消除边界碰撞事故的子节点扩展方法；其次,改进评价函数,减少往复搜索次数,缩小搜索区域面积,提高搜索效率；然后,根据Floyd思想,对生成的航线进行简化处理,消除航线中的冗余航路点,减少航线转角数量,达到简化航线并改善航线平滑度的效果；最后,非线性仿真及飞行试验表明了改进的A*算法生成的航线更加安全、高效,并使无人机的飞行连续和顺畅。