针对传统蚁群算法在移动机器人路径规划中存在搜索盲目性、收敛速度慢及路径转折点多等问题,提出了一种基于改进蚁群算法的移动机器人路径规划算法。首先,利用跳点搜索(Jump Point Search,JPS)算法不均匀分配初始信息素,降低蚁群前期盲...针对传统蚁群算法在移动机器人路径规划中存在搜索盲目性、收敛速度慢及路径转折点多等问题,提出了一种基于改进蚁群算法的移动机器人路径规划算法。首先,利用跳点搜索(Jump Point Search,JPS)算法不均匀分配初始信息素,降低蚁群前期盲目搜索的概率;然后,引入切比雪夫距离加权因子和转弯代价改进启发函数,提高算法的收敛速度、全局路径寻优能力和搜索路径的平滑程度;最后,提出一种新的信息素更新策略,引入自适应奖惩因子,自适应调整迭代前、后期的信息素奖惩因子,保证了算法全局最优收敛。实验仿真结果表明,在不同地图环境下,与现有文献结果对比,该算法可以有效地缩短路径搜索的迭代次数和最优路径长度,并提高路径的平滑程度。展开更多
针对跳点搜索(jump point search,JPS)算法在寻路过程中所存在的路径拐点多、中间搜索跳点数多、寻找跳点的过程中扩展节点数多和寻路时间较长等问题,提出改进双向动态JPS算法。改进算法动态定义正、反扩展方向上的目标点,动态定义启发...针对跳点搜索(jump point search,JPS)算法在寻路过程中所存在的路径拐点多、中间搜索跳点数多、寻找跳点的过程中扩展节点数多和寻路时间较长等问题,提出改进双向动态JPS算法。改进算法动态定义正、反扩展方向上的目标点,动态定义启发函数,并利用动态约束椭圆对算法的扩展区域加以限制,以区分椭圆内、外区域的扩展优先级。在算法从起点和目标点两个方向上分别向对方进行扩展的过程中,以寻找到的新的代价最小点为新椭圆的焦点,椭圆的方位和约束区域也随之动态调整。仿真结果表明,经过优化改进的双向动态JPS算法在一般地图中有一定的表现,在障碍物较少且目标点距离起点较近的室内环境地图中表现尤为良好。展开更多
为解决传统A^(*)寻路算法在搜索过程中会产生大量冗余节点,导致算法整体搜索效率低,运算内存消耗大等问题,从A^(*)算法的两个重要决策点出发,改进算法的代价评估函数与邻节点搜索策略,提出一种改进融合算法。首先,采用向量叉积与尺度平...为解决传统A^(*)寻路算法在搜索过程中会产生大量冗余节点,导致算法整体搜索效率低,运算内存消耗大等问题,从A^(*)算法的两个重要决策点出发,改进算法的代价评估函数与邻节点搜索策略,提出一种改进融合算法。首先,采用向量叉积与尺度平衡因子相结合的方法优化传统A^(*)算法的启发函数,减少A^(*)算法寻路过程中在最优路径周围产生的具有相同代价值的冗余节点,减少了对称路径的搜索;其次,融合跳点搜索(Jump point search, JPS)策略,通过逻辑判断实现路径的变步长跳跃搜索,避免了A^(*)算法逐层搜索效率低的弊端。在不同尺寸的栅格地图中进行仿真分析,发现改进融合算法相比于传统A^(*)算法,在路径长度基本相等的情况下,节点搜索数量约减少95%,且与传统JPS寻路算法相比,有效过滤了路径周围复杂形状障碍物产生的大量冗余跳点。最后,将改进融合算法应用于ROS移动机器人并进行对比实验以验证算法的可行性。实验结果表明:改进融合算法在获得高效安全的路径基础上,搜索效率相比于A^(*)算法可提高约94%。展开更多
在静态栅格地图中,针对传统蚁群算法进行AGV(Automated Guided Vehicle,自动引导车)路径规划收敛慢且搜索结果容易陷入局部最优的问题,提出一种融合跳点搜索(Jump Point Search,JPS)和双向并行蚁群搜索的改进算法.首先,对实际研究环境...在静态栅格地图中,针对传统蚁群算法进行AGV(Automated Guided Vehicle,自动引导车)路径规划收敛慢且搜索结果容易陷入局部最优的问题,提出一种融合跳点搜索(Jump Point Search,JPS)和双向并行蚁群搜索的改进算法.首先,对实际研究环境进行栅格化建模,使用改进的跳点搜索算法生成双向搜索的初始次优路径,为双向蚁群搜索提供初始搜索方向参考.其次,在双向并行蚁群搜索过程中采用改进的转移概率启发函数,该函数在确定下一个转移节点时考虑了避免AGV与障碍物碰撞的因素,同时通过设计信息素共享机制并结合改进的信息素增量及浓度两种融合模型,共享和更新全局信息素浓度,以更好地探索和优化路径,保证双向路径连结.最后,与传统蚁群算法进行实验结果对比,验证了改进算法的全局搜索能力、效率和安全性.展开更多
为了解决采用遗传算法解析最优路径中存在的转折点较多、易陷入局部最优解、迭代次数较多以及寻优时间过长等问题,引入自适应交叉算子和变异算子,将改进后的跳点搜索(jump point search)算法与改进遗传算法融合,得到跳点搜索-遗传(jump ...为了解决采用遗传算法解析最优路径中存在的转折点较多、易陷入局部最优解、迭代次数较多以及寻优时间过长等问题,引入自适应交叉算子和变异算子,将改进后的跳点搜索(jump point search)算法与改进遗传算法融合,得到跳点搜索-遗传(jump point search-genetic,JPSG)算法。JPSG算法利用JPS算法的高效局部搜索能力来提高整体搜索能力,加速算法整体收敛趋势;利用改进遗传算法的全局搜索能力改变JPS算法不能在复杂障碍物状况下解析最优路径的状态,提高算法对动态环境的适应性。在栅格矩阵中的路径规划仿真表明,相比于改进遗传算法、传统遗传算法,JPSG算法可以有效缩短寻优执行时间,提高寻优准确率,减少运算执行次数,在稳定性、准确性、快速性上具有明显的优势。展开更多
给出了跳点搜索（Jump Point Search，JPS）算法的原理，分析了邻居裁剪规则，并试着用图来解释该算法而不诉诸于其原始研究论文中提出的基本数学证明．通过3个实验综合分析了JPS的性能优势，实验结果表明：同等地图尺寸下JPS扩展的节...给出了跳点搜索（Jump Point Search，JPS）算法的原理，分析了邻居裁剪规则，并试着用图来解释该算法而不诉诸于其原始研究论文中提出的基本数学证明．通过3个实验综合分析了JPS的性能优势，实验结果表明：同等地图尺寸下JPS扩展的节点数与障碍物密度成正比，与查看的邻居数成反比；随着地图尺寸的增加，JPS相比于其他典型寻路算法，在时间效率上优势更加显著；地图环境的对称性越高，JPS较之于A＋的优势越明显．总之，JPS保持了A＊的最优性，可将A＊提速一个数量级甚至更多，该算法更适合需要快速寻路的领域．展开更多
文摘针对传统蚁群算法在移动机器人路径规划中存在搜索盲目性、收敛速度慢及路径转折点多等问题,提出了一种基于改进蚁群算法的移动机器人路径规划算法。首先,利用跳点搜索(Jump Point Search,JPS)算法不均匀分配初始信息素,降低蚁群前期盲目搜索的概率;然后,引入切比雪夫距离加权因子和转弯代价改进启发函数,提高算法的收敛速度、全局路径寻优能力和搜索路径的平滑程度;最后,提出一种新的信息素更新策略,引入自适应奖惩因子,自适应调整迭代前、后期的信息素奖惩因子,保证了算法全局最优收敛。实验仿真结果表明,在不同地图环境下,与现有文献结果对比,该算法可以有效地缩短路径搜索的迭代次数和最优路径长度,并提高路径的平滑程度。
文摘针对跳点搜索(jump point search,JPS)算法在寻路过程中所存在的路径拐点多、中间搜索跳点数多、寻找跳点的过程中扩展节点数多和寻路时间较长等问题,提出改进双向动态JPS算法。改进算法动态定义正、反扩展方向上的目标点,动态定义启发函数,并利用动态约束椭圆对算法的扩展区域加以限制,以区分椭圆内、外区域的扩展优先级。在算法从起点和目标点两个方向上分别向对方进行扩展的过程中,以寻找到的新的代价最小点为新椭圆的焦点,椭圆的方位和约束区域也随之动态调整。仿真结果表明,经过优化改进的双向动态JPS算法在一般地图中有一定的表现,在障碍物较少且目标点距离起点较近的室内环境地图中表现尤为良好。
文摘为解决传统A^(*)寻路算法在搜索过程中会产生大量冗余节点,导致算法整体搜索效率低,运算内存消耗大等问题,从A^(*)算法的两个重要决策点出发,改进算法的代价评估函数与邻节点搜索策略,提出一种改进融合算法。首先,采用向量叉积与尺度平衡因子相结合的方法优化传统A^(*)算法的启发函数,减少A^(*)算法寻路过程中在最优路径周围产生的具有相同代价值的冗余节点,减少了对称路径的搜索;其次,融合跳点搜索(Jump point search, JPS)策略,通过逻辑判断实现路径的变步长跳跃搜索,避免了A^(*)算法逐层搜索效率低的弊端。在不同尺寸的栅格地图中进行仿真分析,发现改进融合算法相比于传统A^(*)算法,在路径长度基本相等的情况下,节点搜索数量约减少95%,且与传统JPS寻路算法相比,有效过滤了路径周围复杂形状障碍物产生的大量冗余跳点。最后,将改进融合算法应用于ROS移动机器人并进行对比实验以验证算法的可行性。实验结果表明:改进融合算法在获得高效安全的路径基础上,搜索效率相比于A^(*)算法可提高约94%。
文摘在静态栅格地图中,针对传统蚁群算法进行AGV(Automated Guided Vehicle,自动引导车)路径规划收敛慢且搜索结果容易陷入局部最优的问题,提出一种融合跳点搜索(Jump Point Search,JPS)和双向并行蚁群搜索的改进算法.首先,对实际研究环境进行栅格化建模,使用改进的跳点搜索算法生成双向搜索的初始次优路径,为双向蚁群搜索提供初始搜索方向参考.其次,在双向并行蚁群搜索过程中采用改进的转移概率启发函数,该函数在确定下一个转移节点时考虑了避免AGV与障碍物碰撞的因素,同时通过设计信息素共享机制并结合改进的信息素增量及浓度两种融合模型,共享和更新全局信息素浓度,以更好地探索和优化路径,保证双向路径连结.最后,与传统蚁群算法进行实验结果对比,验证了改进算法的全局搜索能力、效率和安全性.
文摘为了解决采用遗传算法解析最优路径中存在的转折点较多、易陷入局部最优解、迭代次数较多以及寻优时间过长等问题,引入自适应交叉算子和变异算子,将改进后的跳点搜索(jump point search)算法与改进遗传算法融合,得到跳点搜索-遗传(jump point search-genetic,JPSG)算法。JPSG算法利用JPS算法的高效局部搜索能力来提高整体搜索能力,加速算法整体收敛趋势;利用改进遗传算法的全局搜索能力改变JPS算法不能在复杂障碍物状况下解析最优路径的状态,提高算法对动态环境的适应性。在栅格矩阵中的路径规划仿真表明,相比于改进遗传算法、传统遗传算法,JPSG算法可以有效缩短寻优执行时间,提高寻优准确率,减少运算执行次数,在稳定性、准确性、快速性上具有明显的优势。
文摘给出了跳点搜索（Jump Point Search，JPS）算法的原理，分析了邻居裁剪规则，并试着用图来解释该算法而不诉诸于其原始研究论文中提出的基本数学证明．通过3个实验综合分析了JPS的性能优势，实验结果表明：同等地图尺寸下JPS扩展的节点数与障碍物密度成正比，与查看的邻居数成反比；随着地图尺寸的增加，JPS相比于其他典型寻路算法，在时间效率上优势更加显著；地图环境的对称性越高，JPS较之于A＋的优势越明显．总之，JPS保持了A＊的最优性，可将A＊提速一个数量级甚至更多，该算法更适合需要快速寻路的领域．
