面向3D场景智能寻路技术综述

智能寻路技术是人工智能的一个重要应用,该技术被应用到许多领域,其中在大型3D场景游戏中的应用尤为广泛。对现有智能寻路技术包括场景地图表示法、路径搜索技术分别进行了研究对比,分析每种方案的优劣势,总结了智能寻路技术的发展趋势。     

游戏地图中的分层动态路径搜索算法

在大型游戏地图环境中,玩家必须对动态地形做出即时反应,而动态寻路算法对改变节点的位置非常敏感。为此,结合增量路径搜索(LPA*)算法和分层路径搜索(HPA*)算法,提出一种分层动态路径搜索(HPLPA*)算法。对地图分层形成抽象图,并在动态环境中及时更新,采用LPA*搜索,找到抽象路径再细化,以此形成本地路径。实验结果证明,与LPA*和HPA*相比,该算法更有效。     

基于陷阱层次的预处理寻路算法

针对当前寻路算法不能很好满足某些实时性应用中需要快速找到最短路径的要求,提出一种基于陷阱层次预处理的寻路算法。通过在预处理阶段探测出陷阱,即在实际搜索中并不需要的区域,在进行路径搜索时削减掉这些区域,使得无用空间的探索大幅度减少,提高了搜索效率。实验结果表明,该算法不但显著地减少了节点数的扩展,节约了搜索时间,而且保证了路径寻找的最优化,对于提高寻路算法的性能是一个切实可行的解决方案。     

即时战略游戏的智能流场寻路算法设计与实现

针对即时战略游戏中多智能体寻路时间长和移动碰撞阻塞的问题,提出一种基于组合式改进的流场寻路算法。首先,采用红黑树存储数据,提高数据的存取速度;其次,采用惩罚函数将非线性的偏微分方程问题转化为线性的无约束问题,简化完整代价值的计算方式;最后,引入前置邻接点关联节点,生成流场方向。该算法与改进前的流场寻路算法相比,路径计算时间减少20%,平均移动时间稳定在20 s。实验结果表明,在即时战略游戏中采用改进后的流场寻路算法能够有效缩短寻路时间,提高智能体移动速度,提升游戏人工智能水平。     

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

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

基于定位点和路径复用的大型多人在线游戏寻路算法

针对当前寻路算法不能很好满足大型多人在线游戏对于可靠性和低消耗的要求,提出一种基于定位点和路径复用的大型多人在线游戏寻路算法。通过定位点的使用和路径复用,使得无用空间的探索大幅减少,降低了服务器的负载,最终探索出一条接近最优的路径。实验结果表明,该算法具有更高的效率,对于大型多人在线游戏寻路是一个切实可行的解决方案。     

游戏开发中智能路径搜索算法的研究

在游戏软件中,人工智能是一个重要而又复杂的模块,而寻路算法是人工智能运用于电子游戏中的最基本问题之一。针对游戏中路径搜索的特点,在对一般搜索算法、常见搜索算法和启发式搜索技术进行详细地分析与研究的基础之上,结合实际应用情况,对A*算法进行了一些优化与改进。     

规则网格数字高程模型中基于距离与坡度的路径规划算法

针对A^*算法在数字高程模型（DEM）路径规划中的低效问题,提出一种基于距离与坡度的改进A^*寻路算法。该算法面向规则网格DEM,以距离和坡度作为路径搜索评估指标,设计新的评价函数,并以地表障碍评判路径的可通行性。在寻路过程中,根据实际场景DEM数据计算相匹配的参数,使得改进算法能自适应不同场景下DEM数据分辨率的变化;采用动态权值调整完备性函数和启发性函数对评价结果的影响,优化路径选择。仿真测试结果表明,改进算法能够通过参数调整适应DEM分辨率的变化,搜索出优化的路径,降低搜索时间,提高搜索效率。     

基于Silverlight网页游戏的寻径优化算法

为了解决A*路径搜索算法在Silverlight网页游戏中的搜索费时和路径曲折等问题,在结合光线跨越算法和引入父结点指针的二叉堆存储开启列表的A*算法的基础上,提出了一种基于Silverlight网页游戏的寻径优化算法。该算法在现有研究的基础上使用光线跨越算法减小A*算法搜索规模,同时将动态关键点技术与光线跨越算法结合来优化算法返回的路径。将该算法在游戏所使用的网格地图中进行实验,实验结果表明,该算法能够有效地根据系统设定的通行条件寻找出一条最优的实际可行的路径,同时缩短寻路的时间消耗和所寻的路径长度,提高游戏的可玩性。     

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

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

游戏开发中智能路径搜索算法的研究

路径搜索是许多游戏特别是即时战略游戏的核心组成部分，首先介绍了游戏中路径搜索的相关概念。路径搜索的算法有很多，不同的搜索算法有其不同的搜索策略、时间效率、空间消耗与应用场合。分析对比了多种路径搜索算法的运行数据之后，详细讨论了A^＊算法。由于游戏中的路径搜索有其自身的特点，针对游戏中路径搜索的具体要求从搜索效率、路径的真实平滑性和动态变化状态空间的适应性等方面对A^＊算法进行了优化和改进。     

基于蚁群算法及博弈论的多Agent路径规划算法

针对多Agent路径规划问题,提出了一个两阶段的路径规划算法。首先,利用改进的蚁群算法来为每个Agent规划出一条从起始点到目标点,不与环境中静态障碍物碰撞的最优路径。在蚁群算法的改进中引入反向学习方法来对蚂蚁位置进行初始化分布,提高了算法的全局搜索能力;利用粒子群算法中的自适应惯性权重因子来调节信息素强度Q值,使其自适应地变化,避免陷入局部最优;对信息素挥发因子ρ进行调节,提高算法的迭代速度。其次,若多Agent之间存在动态碰撞,利用博弈论构建多Agent之间的动态避障模型,并利用虚拟行动法来解决博弈的求解问题及多Nash均衡的选择问题,确保每个Agent能够快速学习到最优Nash均衡。仿真实验结果表明改进蚁群算法与传统蚁群算法相比在搜索精度与搜索速度上有明显的提高,与Mylvaganam的多Agent动态避障算法相比,所提算法减小了路径总长度并提高了收敛速度。     

Research on navigation of bidirectional A* algorithm based on ant colony algorithm

To overcome the lengthy search time, massive space occupation, and overlong planned path of the traditional A* algorithm, this paper integrates the bidirectional search with the intelligent ant colony algorithm to obtain the heuristic function selection factor, and uses the factor to improve the evaluation function of the algorithm. The simulation results show that the improved algorithm achieved better dynamic navigation than the traditional A* algorithm both in search time and distance, featuring shorter path searching time and the algorithm running time. Therefore, the result of this research has effectively reduced the search time and enhanced the dynamic search.

     

融合改进哈里斯鹰和改进动态窗口的机器人动态路径规划

针对动态环境的移动机器人路径规划问题,提出了一种改进哈里斯鹰算法（IHHO）与改进动态窗口算法（IDWA）的融合算法（IHHO-IDWA）。首先,针对哈里斯鹰算法后期搜索性能不足等问题,提出了融合自适应混沌和核心种群动态划分策略、融合黄金正弦策略以及动态云最优解扰动策略来提高算法的性能。其次,针对动态窗口算法存在规划的路径长和易陷入死锁等问题,提出了三个改进策略：增加子函数,保证算法能够规划出更短的路径;提出自适应权重策略,平衡算法局部避障能力和全局搜索性能;设定初始航向角,避免路径冗余。最后,通过测试函数、CEC2014函数的数值实验和静态、动态路径规划实验,验证了IHHO和IDWA性能有明显提升;通过50×50大型动态地图验证了融合算法较对照组算法规划的路径缩短了11.51%,证明了该方法的优越性。     

基于改进的蚁群算法（ACO）的混合多目标AGV调度

蚁群算法是一种通过模拟蚁群的寻路行为对现实问题进行优化的现代智能仿生算法。针对实现AGV任务作业调度时,行驶路径最短的实际应用需求,本文将AGV的路径优化模型转化为旅行商问题,分析了多目标AGV优化中出现的冲突问题。在本文中,尝试了一种直接通信机制来进行改进传统算法,改进后的方法能够更好地维持种群的持久性,最终对于AGV调度规划起到积极的作用,有效地提高了AGV调度系统的效率。     

基于不完全信息多阶段博弈的入侵路径预测

随着入侵的推进入侵者掌握的信息会逐步增加,依据新信息入侵者会找到更好的入侵路径并作出调整。为了使防御方能准确预测入侵路径,首先基于超图理论建立动态防御图并提出动态防御图更新方法,对入侵者的信息更新进行预测;然后建立不完全信息多阶段博弈模型对不同阶段入侵者的入侵路径调整进行预测;最后设计基于博弈的动态防御图路径预测算法,对完整的入侵路径进行预测。实验给出对入侵路径进行预测的典型实例,对实例结果的分析说明了模型的合理性与准确性。     

路径约束下基于人工智能的智慧航空旅游动态寻径方法

为了提高智慧航空旅游动态寻优控制能力,提出一种基于人工智能的路径约束下智慧航空旅游动态寻径方法。采用多目标进化方法进行智慧航空旅游动态寻径的路径约束控制,结合粒子群方法进行智慧航空旅游动态寻径的路径优化选择,采用多目标Pareto映射方法进行智慧航空旅游的路径规划设计,结合信息素导引方法进行智慧航空旅游动态寻径的自适应控制,构建智慧航空旅游动态寻径的蚁群滤波模型,根据蚁群路径约束寻优方法构建智慧航空旅游动态寻径的人工智能算法,实现智慧航空旅游动态寻径的人工智能控制和自适应寻优。仿真结果表明,采用该方法进行智慧航空旅游动态寻径的自适应性能较好,路径优化控制能力较强。     

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

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