自动寻路A＊算法的应用及优化设计

自动寻路A＊算法是富互联网应用（RIA）游戏制作过程中的核心算法,解决了地图中两点之间寻路的问题,应用于很多游戏中.对A＊寻路算法的实现方法进行了研究和探讨,并对该算法进行了优化设计,体现了该算法的功能,最后对其应用前景进行了展望.     

A~＊路径规划算法的改进及实现

针对A＊算法在路径规划过程中因遍历节点多而导致搜索时间长和路径规划距离长的问题,对A＊算法进行了改进.改进算法采用两点间的欧氏距离作为估价函数,并以前向搜索和后向搜索交替进行的方式来减少路径规划时间.仿真结果表明,改进算法在搜索时间和距离上分别比A＊算法减少了0.0184s和42m,在搜索得到的路径长度和算法运行时间上明显优于A＊算法.     

VB环境下A＊算法的实现

A＊算法是一种典型的启发式搜索算法,应用于很多问题的求解中．在分析A＊算法思想的前提下,给出其编程实现的方法．并获得了在VB地图中一个顶点到另一个顶点的绕过障碍的最佳路径．     

基于自适应步长策略的A*算法路径规划优化

针对A*算法求解路径轨迹耗时长、内存占用大等问题,本文提出一种基于自适应步长策略改进A*算法.首先,根据当前点与终点的位置关系,设定寻路方向的优先级顺序,减少不合理方向上的冗余规划计算量;其次,修改到达终点的判断条件,可在轨迹规划时实现路径的跳跃;再次,针对A*算法轨迹规划效率低的问题,提出自适应步长策略;最后,针对内存占用大,以及面对大地图时可能出现的内存溢出问题,提出了八方向搜索法.实验结果表明,相较于原始的A*算法,改进的A*算法在轨迹规划效率上获得了极大的提升,同时内存占用大的问题也得到了很好的解决     

基于记忆机制的动态交通路径优化算法

在对经典路径优化算法性能进行分析的基础上,指出了现有路径优化算法在大规模路网条件下实时性差的问题。通过比较道路交通网络路径优化和机器人寻路过程的异同点,基于智能机器人寻路的D*Lite算法和记忆规则,提出一种新的道路网络动态路径优化算法,并对其性能进行了测试和对比分析。结果表明,该方法在保证路径优化结果相近的情况下可以减少优化计算时间26%~50%。     

游戏编程中的寻路算法研究

探讨了游戏开发中的一些寻路算法,提出了如何在游戏中使用遗传算法实现路径探索的基本思路,分析了遗传算法实现寻路的优点及其存在的问题。     

复杂数据流多项式新模型K*TDG及搜索算法

提出了一种新的多项式模型K＊TDG解决复杂数据流的分解搜索问题，其边权值K表明了系统参数之间的紧密程度．对K＊TDG、紧密K＊TDG和松散K＊TDG等概念进行了定义；对K＊TDG模型的基本加法运算和乘法运算进行了讨论、在此基础上提出了一种复杂数据流的分解匹配算法．为了降低算法的复杂度，还提出了一种根据复杂元件多项式次数分组的策略、实验结果表明所提出的K＊TDG模型能有效地用于复杂数据流的分解和匹配，所提出的算法和策略能使元件的搜索空间平均减少了49％．     

游戏编程中的寻路算法研究

探讨了游戏开发中的一些寻路算法,提出了如何在游戏中使用遗传算法实现路径探索的基本思路,分析了遗传算法实现寻路的优点及其存在的问题.     

基于双向蚁群算法的路径规划研究

针对蚁群算法存在的搜索精度不足以及收敛速度缓慢等问题，本文提出了一种加入角度参数的双向蚁群算法用于解决机器人路径搜索问题。与传统蚁群算法不同，该算法首先对蚁群的起始位置进行改进，使其根据蚂蚁编号从地图中的一系列起点集合中选择适当节点出发，增加解的多样性同时并获得全局最优解。同时改进了信息素更新规则，对当前迭代次数寻找到的最优路径进行信息素奖励，使其对下次迭代蚂蚁的寻路过程起到引导作用。最后，为提高算法的收敛速度，提出了角度参数并将其加入到蚂蚁的转移概率中，使得蚂蚁在根据转移概率选择下一行走节点时能够优先选择与目标节点角度差较小的节点，从而提高获取最优解的概率，并在算法后期加快收敛速度。大量仿真实验结果表明本文所提出算法的路径搜索能力和迭代收敛效果显著提高。     

基于ROS的移动机器人自主建图与路径规划

为了提高机器人的自主导航性能,设计了基于ROS的移动机器人自主建图与路径规划系统.通过2D激光雷达获取周围环境信息,利用姿态传感器(IMU)获取机器人的姿态和加速度信息,利用Gmapping算法实现机器人的自主定位与建图,利用基于头尾双向搜索的A~*算法进行全局路径规划,采用DWA算法完成局部避障工作.结果表明,所提算法可使机器人完成构建地图以及自主导航任务,提高导航系统的自主性能以及工作效率.     

三维场景中角色自动寻径算法研究

以大规模三维场景中角色自动寻径为研究背景,提出一种基于A*算法的高效自动寻路的方法。针对常见三维网络游戏地图,采用RSG结构模型对三维场景的地形数据进行组织,用于实现大规模场景的平原、高山等自然地形地貌的仿真。同时,在RSG结构的地形数据基础上,生成一种基于可编辑的更细致的导航网格数据,用于辅助实现高效的寻径。在A*算法的基础上,对A*算法的启发性进行了扩展,重点研究了在导航网格数据辅助下的全局寻路算法。将该文的算法应用于大规模三维场景的角色自动寻径中,实验结果表明,文中提出的三维场景中角色自动寻径算法,方法简单、导航网格数据编辑方便,适用范围广,具有很好的应用价值。     

移动机器人路径动态规划有向D*算法

针对传统D*路径规划算法搜索效率低、成本较高的问题,提出有向D*算法. 该算法考虑目标点与障碍物信息,引入关键节点概念,逐级扩展确定可行路径,并且引入导向函数以控制单次搜索的节点搜索范围来提高搜索效率;在原欧几里得评价指标的基础上引入路径平滑度函数对偏移路径进行惩罚,避免机器人无效转弯而增加移动成本;通过路径平滑度函数中的“转弯因子”协调路径长度与平滑度之间的关系,给出路径平滑度函数的分段原理与转弯因子的确定方法,并对算法收敛性进行证明. 在不同环境下的仿真实验表明,该算法较传统算法能更好地兼顾局部搜索与全局最优性,尤其适用于障碍物较多的复杂环境.     

Path planning method for cable harness considering complex constraints

Aiming at the problem that the existing path planning method cannot be used in the path planning of multiple electric aircraft airborne equipment cable harness which considers complex engineering rules constraints,a route planning method considering complex constraints is studied and proposed based on the Quasi-Physical and Quasi-Human algorithm and improved A* algorithm.First,the calculation method for the total wiring cost considering the path length cost and the material cost,process cost and weight cost of the bending groove is proposed,with the evaluation function of the traditional A* algorithm improved.Then,the equivalent radius of the cable harness is calculated based on the Quasi-Physical and Quasi-Human algorithm,and the search space automatic processing algorithm and the corner node reasonableness judgment algorithm considering the constraints of engineering rules are proposed.Finally,an example of cable harness laying in an airborne equipment shows that the routing path obtained by using the improved A* algorithm can not only meet the complex constraints,but also reduce the total wiring cost by 5.1% compared with the existing algorithm.     

复杂环境下移动机器人路径规划与跟随

提出了一种基于改进A*算法和PID控制算法的新型移动机器人路径规划与路径跟随控制方法,该方法适用于复杂的迷宫环境。在所提出的方法中,解决了A*算法转折点过多的问题,并且通过拓展障碍物和四阶三次均匀B样条优化的方法使生成的预期路径安全且平滑;之后基于前视点的两轮差速机器人运动学模型设计了PID控制器。在专门设计的框架中测试了所提出方法的性能。作为验证,分别从路径规划与路径跟随两个方面做了详尽的实验,结果表明,规划路径转折点少且平滑,设计的PID控制器能够控制移动机器人实现较好的路径跟随效果。最后,在复杂的迷宫环境中验证了本文提出的方法,结果表明,所提出的方法能够使机器人无碰撞穿越迷宫。     

A*算法改进及其在动态最短路径问题中的应用

动态最短路径搜索算法是智能交通系统技术应用的关键问题之一．为了解决这一问题,提出以一致性原则动态形式为基础的动态A*算法(dynamic A* algorithm,DA* algorithm)并证明了在两节点间动态下界满足一致性原则动态形式前提下,该算法能够求解满足先进先出原则的动态网络中两节点间最短路径问题．在以广州市交通路网为基础的动态网络上对DA*算法进行试验．试验结果表明,Dijkstra算法的和A*算法的平均计算时间分别是DA*算法的6．55和1．43倍．     

一种改进蚂蚁算法的无人机多目标三维航迹规划

传统的标准蚂蚁算法及A*算法求解无人机多目标三维航迹规划存在需设置导航节点及构建VORONOI图等缺陷,针对这一问题,提出了一种改进的蚂蚁算法.该算法将导引因子引入到状态转移策略中,减少了蚂蚁局部搜索的盲目性,确保蚂蚁形成有效航迹,解决了将该算法应用于航迹规划的两个构造难题,即航迹节点不固定和局部搜索难以到达目标节点这两个难题.将雷达、导弹、高炮及大气威胁模型的最大作用距离和有效作用距离等约束条件引入代价函数及启发因子计算中,解决了航迹规划多约束求解困难等问题.仿真结果表明,该算法构造合理,蚂蚁算法无需导航节点及VORONOI图便可自主寻找到目标节点,且收敛速度满足航迹规划要求,生成的航迹代价较小.