随着无人车、无人机等自主移动机器人的井喷式发展,寻路算法的重要性也一再提升。跳点搜索+(jump point search plus,JPS+)算法因其显著的高搜索效率而成为了经典的静态栅格化地图寻路算法。对JPS+算法的改进策略和应用场景层出不穷,但...随着无人车、无人机等自主移动机器人的井喷式发展,寻路算法的重要性也一再提升。跳点搜索+(jump point search plus,JPS+)算法因其显著的高搜索效率而成为了经典的静态栅格化地图寻路算法。对JPS+算法的改进策略和应用场景层出不穷,但对路径长度与路径节点数量的优化方法仍有待研究。提出了一种对于强制跳点按功能性的分类方式,并基于这一分类对JPS+算法的预处理和搜索流程进行改进,在提高单次搜索扩展效率的同时,减少路径的长度与节点数。通过仿真地图实验与真实采样地图实验,验证了改进算法的有效性。对比发现:改进JPS+算法在仿真地图中,所求路径长度最大减少5.92%,路径节点数最大减少46.15%,算法用时最大减少25.58%;在真实采样地图中,所求路径长度平均减少2.48%,路径节点数平均减少10.71%,算法用时平均减少17.08%。展开更多
为解决传统JPS(Jump Point Search)算法的拐点多和路径次优等问题,提出一种改进的跳点搜索算法。首先,根据地图可行率,对障碍物进行适应性膨胀,以保障安全距离;其次,结合方向性因素对启发函数进行调整,显著提高了路径搜索的目的性;最后...为解决传统JPS(Jump Point Search)算法的拐点多和路径次优等问题,提出一种改进的跳点搜索算法。首先,根据地图可行率,对障碍物进行适应性膨胀,以保障安全距离;其次,结合方向性因素对启发函数进行调整,显著提高了路径搜索的目的性;最后,提出了一种能剔除冗余节点的关键点提取策略,优化了初始规划后的路径,在保证路径最短的同时,显著减少了拓展节点和拐角。实验结果表明,与传统的JPS算法相比,所提算法能缩短路径长度并减少拐角数量,同时拓展节点数量平均减少19%,搜索速度平均提升21.8%。展开更多
针对跳点搜索算法(jump point search,JPS)在路径规划过程中出现的穿越墙角的不安全行为,提出了一种基于蜂窝栅格地图的跳点搜索算法(honeycomb raster map-JPS,H-JPS)。构建蜂窝栅格地图代替传统栅格地图,在JPS算法的基础上结合蜂窝栅...针对跳点搜索算法(jump point search,JPS)在路径规划过程中出现的穿越墙角的不安全行为,提出了一种基于蜂窝栅格地图的跳点搜索算法(honeycomb raster map-JPS,H-JPS)。构建蜂窝栅格地图代替传统栅格地图,在JPS算法的基础上结合蜂窝栅格修改了剪枝规则与跳点判断规则,再利用蜂窝栅格特点设计了新的启发式函数来提高搜索效率,通过找寻最远节点的节点更新规则来优化生成的轨迹。利用Matlab仿真平台验证算法的搜索效率和安全性,结果表明,相较于传统JPS算法,采用H-JPS算法进行路径规划能够完全消除危险节点,路径规划时间和长度分别缩短了41.9%和11.1%,显著提高了搜索效率。展开更多
针对传统全局路径规划中扩展节点多、寻路时间长等问题,提出一种基于JPS+(jump point search plus)算法的全局路径规划算法,旨在提高机器人在复杂环境的智能性、高效性的要求。首先引入了一种基于密度的判断障碍物角点规则,实现对于主...针对传统全局路径规划中扩展节点多、寻路时间长等问题,提出一种基于JPS+(jump point search plus)算法的全局路径规划算法,旨在提高机器人在复杂环境的智能性、高效性的要求。首先引入了一种基于密度的判断障碍物角点规则,实现对于主要跳点的识别数目,减少搜索路径过程中的可扩展节点,同时在路径求解过程中对目标跳点的判定规则进行了修改,最终实现了减少计算量、缩短计算时长的目标。为验证所提改进型JPS+算法的有效性,将A、JPS+算法在不同类型地图中与改进型JPS+算法进行了比较。仿真结果表明,改进型JPS+算法与A算法相比,在路径长度、寻路时间和扩展节点数量上都有明显改进;在生成相同路径的基础上,与传统JPS+算法相比,在障碍物占比33.25%的地图中搜索时间降低了7.58%,节点扩展数量减少了9.38%,能够满足移动机器人快速全局路径规划的要求。展开更多
通过构建正六边形栅格地图,并修改传统跳点搜索(jump point search,JPS)算法的邻居剪枝、强制邻居判断的规则和JPS策略,提出一种新的正六边形栅格JPS算法,并且利用该算法解决智能体在环境地图存在障碍物时的路径规划问题。利用Pycharm...通过构建正六边形栅格地图,并修改传统跳点搜索(jump point search,JPS)算法的邻居剪枝、强制邻居判断的规则和JPS策略,提出一种新的正六边形栅格JPS算法,并且利用该算法解决智能体在环境地图存在障碍物时的路径规划问题。利用Pycharm平台进行仿真研究,并与传统正方形栅格A*算法和JPS算法进行路径规划仿真比较,结果表明正六边形栅格JPS算法可更好地实现路径规划,所规划出的路径可避免穿越墙角的不安全行为、减少转向次数,且该算法可减少路径规划时间,提高了路径规划的质量和效率。展开更多
针对跳点搜索(JPS,jump point search)算法在障碍物位置随机的栅格地图中路径规划时间较长的问题,提出了并行-交替式双向跳点搜索(PA-BJPS,parallel alternate bidirectional jump point search)算法;首先,在起始点与目标点间确定一个...针对跳点搜索(JPS,jump point search)算法在障碍物位置随机的栅格地图中路径规划时间较长的问题,提出了并行-交替式双向跳点搜索(PA-BJPS,parallel alternate bidirectional jump point search)算法;首先,在起始点与目标点间确定一个中心热点区域;其次,采用改进了预计代价函数的并行式双向跳点搜索算法,分别规划从起始点抵达中心热点区域以及目标点抵达中心热点区域的路径;然后,采用交替式双向跳点搜索算法,规划中心热点区域内部的路径;最后,提出迭代式路径修正方法来改良危险路径,并采用3次B-样条曲线替代拐角来平滑路径;仿真结果表明,并行-交替式双向跳点搜索算法有效地缩短了路径规划时间,同时提高了路径的安全性和平滑性。展开更多
针对传统蚁群算法在移动机器人路径规划中存在搜索盲目性、收敛速度慢及路径转折点多等问题,提出了一种基于改进蚁群算法的移动机器人路径规划算法。首先,利用跳点搜索(Jump Point Search,JPS)算法不均匀分配初始信息素,降低蚁群前期盲...针对传统蚁群算法在移动机器人路径规划中存在搜索盲目性、收敛速度慢及路径转折点多等问题,提出了一种基于改进蚁群算法的移动机器人路径规划算法。首先,利用跳点搜索(Jump Point Search,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 plus,JPS+)算法因其显著的高搜索效率而成为了经典的静态栅格化地图寻路算法。对JPS+算法的改进策略和应用场景层出不穷,但对路径长度与路径节点数量的优化方法仍有待研究。提出了一种对于强制跳点按功能性的分类方式,并基于这一分类对JPS+算法的预处理和搜索流程进行改进,在提高单次搜索扩展效率的同时,减少路径的长度与节点数。通过仿真地图实验与真实采样地图实验,验证了改进算法的有效性。对比发现:改进JPS+算法在仿真地图中,所求路径长度最大减少5.92%,路径节点数最大减少46.15%,算法用时最大减少25.58%;在真实采样地图中,所求路径长度平均减少2.48%,路径节点数平均减少10.71%,算法用时平均减少17.08%。
文摘为解决传统JPS(Jump Point Search)算法的拐点多和路径次优等问题,提出一种改进的跳点搜索算法。首先,根据地图可行率,对障碍物进行适应性膨胀,以保障安全距离;其次,结合方向性因素对启发函数进行调整,显著提高了路径搜索的目的性;最后,提出了一种能剔除冗余节点的关键点提取策略,优化了初始规划后的路径,在保证路径最短的同时,显著减少了拓展节点和拐角。实验结果表明,与传统的JPS算法相比,所提算法能缩短路径长度并减少拐角数量,同时拓展节点数量平均减少19%,搜索速度平均提升21.8%。
文摘针对跳点搜索算法(jump point search,JPS)在路径规划过程中出现的穿越墙角的不安全行为,提出了一种基于蜂窝栅格地图的跳点搜索算法(honeycomb raster map-JPS,H-JPS)。构建蜂窝栅格地图代替传统栅格地图,在JPS算法的基础上结合蜂窝栅格修改了剪枝规则与跳点判断规则,再利用蜂窝栅格特点设计了新的启发式函数来提高搜索效率,通过找寻最远节点的节点更新规则来优化生成的轨迹。利用Matlab仿真平台验证算法的搜索效率和安全性,结果表明,相较于传统JPS算法,采用H-JPS算法进行路径规划能够完全消除危险节点,路径规划时间和长度分别缩短了41.9%和11.1%,显著提高了搜索效率。
文摘针对传统全局路径规划中扩展节点多、寻路时间长等问题,提出一种基于JPS+(jump point search plus)算法的全局路径规划算法,旨在提高机器人在复杂环境的智能性、高效性的要求。首先引入了一种基于密度的判断障碍物角点规则,实现对于主要跳点的识别数目,减少搜索路径过程中的可扩展节点,同时在路径求解过程中对目标跳点的判定规则进行了修改,最终实现了减少计算量、缩短计算时长的目标。为验证所提改进型JPS+算法的有效性,将A、JPS+算法在不同类型地图中与改进型JPS+算法进行了比较。仿真结果表明,改进型JPS+算法与A算法相比,在路径长度、寻路时间和扩展节点数量上都有明显改进;在生成相同路径的基础上,与传统JPS+算法相比,在障碍物占比33.25%的地图中搜索时间降低了7.58%,节点扩展数量减少了9.38%,能够满足移动机器人快速全局路径规划的要求。
文摘通过构建正六边形栅格地图,并修改传统跳点搜索(jump point search,JPS)算法的邻居剪枝、强制邻居判断的规则和JPS策略,提出一种新的正六边形栅格JPS算法,并且利用该算法解决智能体在环境地图存在障碍物时的路径规划问题。利用Pycharm平台进行仿真研究,并与传统正方形栅格A*算法和JPS算法进行路径规划仿真比较,结果表明正六边形栅格JPS算法可更好地实现路径规划,所规划出的路径可避免穿越墙角的不安全行为、减少转向次数,且该算法可减少路径规划时间,提高了路径规划的质量和效率。
文摘针对跳点搜索(JPS,jump point search)算法在障碍物位置随机的栅格地图中路径规划时间较长的问题,提出了并行-交替式双向跳点搜索(PA-BJPS,parallel alternate bidirectional jump point search)算法;首先,在起始点与目标点间确定一个中心热点区域;其次,采用改进了预计代价函数的并行式双向跳点搜索算法,分别规划从起始点抵达中心热点区域以及目标点抵达中心热点区域的路径;然后,采用交替式双向跳点搜索算法,规划中心热点区域内部的路径;最后,提出迭代式路径修正方法来改良危险路径,并采用3次B-样条曲线替代拐角来平滑路径;仿真结果表明,并行-交替式双向跳点搜索算法有效地缩短了路径规划时间,同时提高了路径的安全性和平滑性。
文摘针对传统蚁群算法在移动机器人路径规划中存在搜索盲目性、收敛速度慢及路径转折点多等问题,提出了一种基于改进蚁群算法的移动机器人路径规划算法。首先,利用跳点搜索(Jump Point Search,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与障碍物碰撞的因素,同时通过设计信息素共享机制并结合改进的信息素增量及浓度两种融合模型,共享和更新全局信息素浓度,以更好地探索和优化路径,保证双向路径连结.最后,与传统蚁群算法进行实验结果对比,验证了改进算法的全局搜索能力、效率和安全性.
