非结构化场景下基于改进JPS算法的移动机器人路径规划

针对移动机器人在大范围非结构化场景下的路径规划问题,在改进跳点搜索(JPS)算法的基础上结合A*搜索,提出一种基于分层栅格地图的Jump A*(JA*)路径规划算法.该算法对三维点云地图进行栅格化分层处理,将环境信息划分为结构层与非结构层,并建立搜索策略切换规则,依据图层信息使用不同的搜索策略,从而有效减少计算量.为了验证JA*算法的有效性,在图层比例不同的三维地图中进行仿真,仿真结果表明,JA*算法相比于传统的A*算法遍历节点更少,搜索效率更高;相比于双向A*算法,具有更高的鲁棒性.最后将JA*算法应用在公开数据集中,实验结果表明,JA*算法能有效解决移动机器人在大范围非结构化场景下的路径规划问题.     

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

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

结合Bresenham与JPS的静态栅格地图的路径搜索算法

路径规划问题一直是人工智能及游戏的研究重点,现在使用较为广泛的启发式算法是A*算法,其缺点在于动态扩展节点过多,会占用大量计算机内存,影响寻路速率。通过改良提出JPS跳点算法,减少内存的消耗,该算法存在跳点数量多,计算冗余等问题。论文将Bresenham算法和JPS跳点算法结合,在使用JPS跳点算法之前,首先用Bresenham算法求出起点和终点之间的直线路径,并记录该直线路径中碰到障碍物节点的前一节点,其次用JPS跳点算法求出两个点的路径,最后将路径加以拼接,以达到减少跳点的数量和离线搜索的节点数量。仿真结果表明该算法可以有效减少跳点数量的生成,减少离线搜索的节点数量。     

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

针对跳点搜索（jump point search,JPS）路径规划算法在大尺度复杂场景下存在内存资源消耗较大、路径结果平滑度较低且路径过于靠近障碍物等问题,提出融合安全势场等级函数与优化Floyd算法的改进JPS算法。首先建立了安全等级函数对栅格地图中的栅格状态进行重新赋值构建安全等级地图;然后改进了启发式函数,引入目标与主方向两项偏置函数项结合安全等级函数项,进一步减少对称性搜索带来的时间消耗,改善了所规划路径的安全程度。其次通过添加二次平滑算法流程优化了Floyd算法;最后结合B-spline样条插值法,进一步提高了改进算法所规划路径的平滑程度。仿真实验验证了改进优化算法在内存资源消耗、路径长度、路径平滑程度以及路径安全程度都有显著提升。     

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

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

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

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

基于A*改进算法的四向移动机器人路径搜索研究

在由栅格法构建的环境地图中,利用A*算法进行路径搜索时存在搜索范围广、搜索速度慢、路径曲折等问题.针对栅格地图及具有四向移动机器人的特点,从搜索方向、启发函数构建、机器人加减速以及转向成本等几个方面对A*算法进行研究和改进,提出一种基于启发信息的扩展节点算法,降低偏离最佳路径节点的扩展数量.改进后的A*算法平均可降低67.1%的搜索面积、49.2%的计算时长、24.9%的路径成本及减少51.1%的转向次数,提高了路径的搜索速度和平滑度.     

基于BIM的地图构建与导航研究

为了提高移动机器人在作业过程中获得现场环境地图的效率,提出了利用BIM技术建立导航地图的方式,获取IFC信息映射到二维栅格,从而快速构建地图;对于室内移动机器人在移动过程中能更快更好的到达目标点的问题,首先对传统A*算法做改进,将原有的8邻域搜索扩展为48邻域搜索,增加了搜索方向,优化了搜索角度;同时考虑了机器人的安全性,对规划路径进行了改进,使得规划的路径与障碍物保持了一定距离;其次,为了避开场地出现的动态障碍物,采用将改进的A*算法与动态窗口法融合,在保证全局路径最优的基础上,实现避障效果;通过实验仿真,表明了改进的A*算法比传统A*的算法在运行时间上快了2倍以上,路径转折点的角度差比原来减少了28%以上,路径长度上更短且不再紧贴障碍物;而融合算法比改进的A*算法在路径平滑性上有所提高,能及时避开随机障碍物,更加适用于环境变化的室内场景。     

基于JPS策略的ACS移动机器人全局路径规划

针对蚁群系统（ACS）算法收敛速度慢、易陷入局部最优、路径转折点数量过多等问题,提出了一种基于跳点搜索（JPS）策略的ACS全局路径规划算法．该算法在迭代前加入一只特殊蚂蚁,利用方向因子引导该蚂蚁始终朝着目标方向前进,并查询是否存在最简路径;在蚂蚁查询下一个节点时,利用JPS算法思想舍去大部分不需要计算的节点．最后,为验证该方法的有效性,使用不同规格的栅格地图进行了仿真实验,仿真结果表明,改进的ACS算法相比于ACS算法,收敛速度加快、收敛时间缩短,且路径更优．最后将算法应用到实际的基于机器人操作系统（ROS）的移动机器人导航实验中,实验结果表明,改进的ACS算法能够有效地解决移动机器人全局路径规划问题,且能明显提升机器人全局路径规划的效率．     

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

A*算法广泛应用于移动机器人路径规划中，而传统A*算法在寻路时，普遍存在搜索时间较长、效率低下等问题，因此，采用双向搜索的方式，对传统A*算法加以改进，该算法在路径规划过程中，可同时进行正反向路径搜索，同时采用正反向搜索交替机制，保证了最终目标节点搜索在连线中点区域内相遇，从而缩短了寻路计算时间。在MATLAB平台上，针对改进后的A*算法进行仿真实验，结果证明，双向A*算法减少了规划时间，且可生成最优路径。最后，将该算法应用到基于开源机器人操作系统的Turtlebot2移动平台上，进行现场实验，实验结果表明，双向A*算法减少了寻路计算时间，从而使得路径搜索效率得到显著提升，且规划路径合理，满足路径规划要求。