Web3D山地场景中多智能体mACO路径规划算法

山地场景数据量大,路径规划算法复杂,难以在网页上精确显示,通常采用的基于等高线的势能路径规划,往往得不到最优路径,且容易被隔断在悬崖下面。为解决以上问题,提出并实现了Web3D上的mACO(mountain ACO)路径规划算法,并在Web3D上实现了基于平面网格的pgACO(planar grid ACO)路径规划算法,以及一个Web3D上的A*路径规划算法。再以典型战斗场景为案例,针对mACO算法、pgACO算法以及A*算法,就实现效果、效率、网页刷新率(FPS)做了对比实验,结果显示,三种算法均可达到实时性,但mACO算法规划的路径更加精确。最后根据规划出来的最优路径,采用leader-follower思想,在Web3D上实现了实时高效的多智能体路径规划方案。

面向山地徒步应急救援路径规划的改进蚁群算法研究

当消防事故发生在无明显道路或道路稀疏的野外复杂山区时,如何在复杂山地环境中规划安全、快速通过的路线至关重要。针对蚁群算法在复杂山地路径规划中容易陷入局部最优以及搜索时间较长的问题,本文提出一种适用于细粒度野外山地环境的徒步应急救援路径规划算法。本文首先根据已有文献分析地表信息与人类运动速度之间的关系,综合地表灌木盖度与地形坡度因素设计寻优算法的目标函数和启发函数;接着采用定向范围视野的蚂蚁搜索方式,决定蚁群算法寻优过程中每一步的网格选择;最后采用拉普拉斯分布调整初始信息素、添加隔离信息素、融合遗传算子与分组更新常规信息素的方法改进蚁群算法。将算法应用到400×400、1000×1000、5000×5000、10000×10000网格数的野外山地环境进行实验对比,实验结果表明,采用定向范围视野与优化启发函数的各蚁群算法在四组实验中均能得到可行路径,验证了方法的有效性;本文算法求解的路径质量优于另外三种算法,在四组实验中分别提高了0.52%~4.95%、4.71%~5.39%、2.26%~13.11%、3.84%~9.16%;此外,在野外三维山地环境中,定向范围视野的搜索方式缩减了搜索空间,有效提高算法的计算效率,搜索速度比八连通结合禁忌表的搜索方式更快,平均耗时降低了90%以上。该算法适用于大型三维山地场景的徒步路径规划研究,降低规划时间,提高路径质量,为无路网三维山地徒步路径寻优工作提供技术支撑。