A*水算法在游戏寻径中的应用

图搜索技术能够从图中寻找一条从起点到目标点的路径.围绕游戏寻径问题,介绍了如何确定启发式函数进行启发式搜索,将A*算法进行分析,列举实例解决游戏中的寻径问题,并且对A*算法进行改进.     

基于改进A*算法的仓储物流移动机器人 任务调度和路径优化研究

为解决仓储物流中移动机器人执行订单任务过程中,调度系统难以快速准确地进行任务分配,且搬运路线并非最短最优路线的问题,根据移动机器人的运动方式和订单任务要求,构建具有可重构性的仓库空间模型和栅格地图模型,通过建立数学模型求解订单任务最短完工时间分配问题,改进传统A^*算法中3种常用距离算法的不足,并提出复杂对角线距离算法进行路径规划仿真。仿真结果表明,上述方法实现总任务完工时间最短的任务分配,使路径规划搜索节点数减少30%,路径长度缩短20%。     

基于地图预处理及改进A~*算法的路径规划

针对移动机器人路径规划中栅格地图建模及A~*算法搜索效率问题,设计了一种基于地图分区预处理及改进A~*算法的路径规划。首先,基于K-Means聚类算法对栅格地图进行分区并量化各局部区域的复杂度;然后,改进A~*算法的评价函数和子节点选择方式并依据地图区域的复杂度生成有效的搜索空间;最后,改进Floyd算法对路径进行双向平滑度优化处理,并通过添加防碰撞安全距离系数,使路径与障碍物保持安全距离。实验仿真结果表明,本文所设计的算法可提高A~*算法的搜索效率和灵活性,增加路径的平滑度和安全性。     

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

在栅格地图环境下,传统A~*算法搜索路径时选取的路径点受限于栅格中心,并且路径的转折角度固定为特定的离散值,因此存在长度非最优以及冗余转折较多的问题。为此,提出一种新启发搜索策略下的改进A~*算法。在探索当前节点的每个邻域节点时,将邻域点父节点的选取范围扩大到从当前点至起始点的整个支路,采用邻域点与支路上的点直接相连的方式,找到所需真实代价G最小的安全路径,此时支路上对应的点便为该邻域点的父节点。实验结果表明,改进算法能够有效提高路径质量,即规划的路径长度更短、转折更少。与此同时,真实代价G和预估代价F之间的偏差降低,启发函数的启发能力增强,寻路效率也有所提高。     

基于改进A算法的无人机三维航迹规划

针对传统的A*算法在无人机航迹规划问题中的局限性,提出一种改进的A*算法,并结合无人机的性能约束直接对三维空间进行航迹搜索。算法有效的减少搜索空间,缩短搜索时间。仿真结果证明改进算法的有效性。     

基于改进蚁群算法的码垛机器人路径规划应用研究

目的为解决蚁群算法在码垛机器人路径规划中存在的收敛速度慢、容易陷入局部最优等问题,提出一种人工势场和蚁群算法相结合的方法。方法首先,根据码垛机器人机械手在人工势场中不同节点所受到的合力,对初始信息素进行不均匀分布,以解决蚁群算法初期由于缺乏信息素导致的无效路径搜索。其次,在启发函数的设计中引入码垛机器人机械手在下一节点所受到的合力,以解决蚁群算法容易陷入局部最优的问题。最后,对信息素的更新策略进行改进。按照寻得路径的长度不同,对每次迭代完成后信息素的增量成比例进行更新,并设置最大、最小值,以解决迭代后期路径上信息素过大而使蚁群算法陷入局部最优的问题。结果改进后的蚁群算法收敛速度提升了约51%,寻找到的最短路径提升了约10%。和其他改进的蚁群算法相比,在综合性能上也有一定程度上的提高。结论改进后的蚁群算法收敛更快,寻找的最优路径更短。     

动态环境下基于自适应步长Informed-RRT*和人工势场法的机器人混合路径规划

为解决移动机器人在动态环境下的路径规划问题,将Informed-RRT*和人工势场法相融合,提出全局与局部规划算法相融合的路径规划方法。首先,针对Informed-RRT*算法采样效率低,以及得到路径不满足机器人运动学约束的问题,采用目标偏置法与自适应步长法,减少冗余搜索与不必要树的生长;同时,引入走廊优化与时间重分配法,优化路径节点,使路径更加平滑。其次,针对人工势场法易陷入局部极小值和目标点附近不可达的问题,采用平滑窗格策略,增设全局路径子目标点,使机器人能够逃离局部极小值,完成规划任务。仿真结果表明,静态环境中自适应步长Informed-RRT*算法相比于Informed-RRT*算法求解时间缩短了71.98%;动态环境中,混合算法相比于人工势场法,搜索时间缩短了15.4%,路径长度缩短了11.1%。     

局部放电检测机器人巡检的重复路径问题研究

针对变电站局部放电故障检测(PDFD)的路径规划中存在的重复路径过多、巡检效率低等问题,本文在传统A*算法与蚁群(AC)算法融合解决旅行商问题(TSP)的基础上,提出了改进的A*算法与蚁群算法融合的算法。改进的融合算法通过蚁群算法计算巡检序列指导A*算法进行两两巡检点间的路径规划,增加了重复路径列表来提高已寻路径节点的步长代价,再次通过蚁群算法计算巡检序列,迭代计算直到连续两次得到一致的结果。为了验证改进算法的有效性,随机选取10个巡检点在二维栅格地图上进行了对比仿真。仿真结果表明,本文提出的改进算法与传统方法相比,在一定的巡检代价下,有效地增大了巡检路径的路径覆盖比,提高了局部放电故障巡检的效率和质量,对变电站局部放电故障巡检问题的研究具有重要意义。     

基于改进A*算法的家居服务机器人路径规划

由于家居环境空间占用率高,存在许多障碍在搜索空间中创造了局部最小值,对于机器人在家居环境下的路径规划来说依旧是一个挑战,迫使像A*这样的启发式规划者扩大搜索范围。本文在标准A*算法的基础上,提出了在基于加权A~*的次优性边界搜索的基础上使用不一致状态重构A*算法框架的改进方法,通过不重新计算在先前迭代中已经正确计算的状态成本,来减少计算量从而提高算法规划路径的速度,同时也确保了次优性边界。最后对改进前后的算法进行了路径规划对比试验,验证了改进后算法的稳定性和可靠性。     

单线超市车辆配置与路径问题优化研究

为解决工位对物料需求紧迫程度不同,进而影响配送优先顺序的问题,提出考虑工位配送优先级的单线超市车辆配置及配送路径优化模型和求解算法。首先,建立以物料需求紧迫系数表示配送优先顺序,以单线超市车辆配置最少与路径最短为目标的数学模型;其次,提出加入控制搜索因子的改进蚁群算法对该问题进行求解,通过在迭代不同时期设置不同大小的控制搜索因子来改变节点选择概率,提高最优解搜索速度的同时避免算法陷入局部最优;最后,通过算例分析,验证了模型的正确性,同时也证明了改进蚁群算法能够实现对物料需求紧迫程度高的工位优先配送,较基本蚁群算法在计算结果及算法运行时间上具有优势。     

基于Dijkstra-蚁群算法的泊车系统路径规划研究

针对智能停车库中自动导引运输车(automated guided vehicle,AGV)存取车路径规划问题,提出了一种基于Dijkstra-蚁群算法(Dijkstra-ACO)的泊车系统路径规划方法.首先利用链接可视图法建立环境模型,并在此环境模型下,采用Dijkstra算法规划出AGV的初始路径;其次,通过引入节点随机选择机制、调整信息素更新方式和限定信息素阈值策略等对基本蚁群算法进行优化改进;最后,选用改进的蚁群算法对初始路径进行优化.结果显示:Dijkstra算法和混合算法均能使AGV有效避开障碍物,然后搜索到一条从起点到终点的无碰优化路径;与Dijkstra算法相比,混合算法能有效提高路径搜索效率,缩短搜索路径长度,改善搜索路径质量,表明该算法正确、可行及有效,且具有较强的全局搜索能力和较好的收敛性能,能够满足AGV存取车路径规划的要求.     

定制家具板材搬运AGV路径规划

目的 针对应用在定制家具生产包装车间的板材搬运自动引导车存在的路径规划时间长以及规划出的路径转弯次数较多的问题,提出一种改进Q-learning算法的路径规划算法.方法 根据定制家具生产包装车间环境情况,使用栅格法对车间进行建模,建立车间模型的人工标量场,使用人工标量场给予Q-learning算法前期搜索的目的性;增加Q-learning算法的学习层,使得算法可以更快进入收敛;在奖励函数中加入转弯惩罚,使得算法规划出的路径具有更少的转弯次数.结果 仿真结果表明改进后的算法与标准Q-learning算法、增加学习层的Q-learning算法、引入人工势能场Q-learning算法、深度双Q网络算法相比,迭代次数减少了70.46％,64.40％,67.75％,30.49％,转弯次数减少了80％,80.95％,83.33％,73.33％.结论 板材搬运自动引导车利用改进后的Q-learning算法可以有效地提高路径的平滑性,降低了路径规划的时间,提高了板材搬运自动引导车的工作效率.     

竹林皆伐机路径规划系统设计及计算机仿真

目的设计一种中幼竹林皆伐机路径智能规划系统,实现伐竹机伐竹的路径规划功能,使伐竹机可以遍历需要伐竹的全部节点并避开障碍。方法针对中幼竹林皆伐的特点,探讨一种迪杰斯特拉及A*混合算法,用于解决伐竹机路径规划中的路径优化问题。通过C语言编程,来建立一种基于改进的迪杰斯特拉及A*混合算法的中幼竹林皆伐机路径智能规划系统仿模型,并使用C++编程,实现系统模型的仿真,并调用Windows GDI实现仿真结果的显示。结果仿真结果显示,采用文中建立的中幼竹林皆伐机路径规划系统进行伐竹机的路径规划,实现了伐竹路径规划的目标,且相较直接采伐的路径,伐竹机伐竹总里程降低了47.6%,节省了伐竹机伐竹总里程,大大提升了伐竹效率。结论文中所讨论的改进的迪杰斯特拉及A*混合算法可以实现伐竹路径规划的功能,路径规划系统可以求得最优伐竹路径的一个近似解。     

A Novel Improved Bat Algorithm in UAV Path Planning

Path planning algorithm is the key point to UAV path planning scenario. Many traditional path planning methods still suffer from low convergence rate and insufficient robustness. In this paper, three main methods are contributed to solving these problems. First, the improved artificial potential field (APF) method is adopted to accelerate the convergence process of the bat’s position update. Second, the optimal success rate strategy is proposed to improve the adaptive inertia weight of bat algorithm. Third chaos strategy is proposed to avoid falling into a local optimum. Compared with standard APF and chaos strategy in UAV path planning scenarios, the improved algorithm CPFIBA (The improved artificial potential field method combined with chaotic bat algorithm, CPFIBA) significantly increases the success rate of finding suitable planning path and decrease the convergence time. Simulation results show that the proposed algorithm also has great robustness for processing with path planning problems. Meanwhile, it overcomes the shortcomings of the traditional meta-heuristic algorithms, as their convergence process is the potential to fall into a local optimum. From the simulation, we can see also obverse that the proposed CPFIBA provides better performance than BA and DEBA in problems of UAV path planning.     

改进麻雀搜索算法求解多目标低碳冷链物流车辆路径问题

目的 在传统冷链物流的车辆路径问题模型基础上,考虑服务节点和车辆运输过程中产生的碳排放,并加入客户满意度,在有限资源情况下最小化路径成本和最大化客户满意度。方法 构建多目标低碳冷链物流车辆路径问题模型,将爬山算法局部搜索思想应用到麻雀搜索算法中,形成改进麻雀搜索算法,并用其对上海市某区域内的冷链物流配送路径优化问题算例进行求解。结果 通过与改进前及其他2种智能优化算法运行结果进行对比发现,改进后的麻雀搜索算法具有更快的寻优速度和更好的寻优能力,且改进后的算法对模型的碳排放效用性更高。结论 基于国家的低碳政策,设计出符合当下实情的低碳冷链物流运输模型,通过改进优化算法设计运输方案,验证了爬山算法局部搜索思想对麻雀搜索算法进行改进的有效性及所构建低碳冷链物流车辆路径模型的合理性。     

基于烟花混合蚁群的移动机器人路径规划研究

目的 以应用于包装车间的移动机器人的路径规划作为研究对象,解决蚁群算法收敛速度慢、寻找到的路径不优等缺陷。方法 引入改进烟花和蚁群融合的方法进行搜索,首先建立移动机器人的栅格地图,其次采用改进烟花算法进行路径粗搜索,将得到的路径作为信息素增量,再运用蚁群细搜索求解。结果 文中方法与传统方法相比,收敛速度得到提高,并寻找到了更优的路径。结论 通过采用融合算法,弥补了烟花寻优的不足,加快了蚁群的收敛,可以对2种算法互相取长补短。     

基于改进萤火虫算法的有限元模型修正

针对标准萤火虫算法后期收敛速度慢、收敛精度低、易陷入局部最优解的问题,提出了参数自适应策略的改进萤火虫算法,建立了基于改进萤火虫算法的有限元模型修正方法。通过隔代随机吸引度因子扩大了算法搜索路径,提升了算法遍历性,避免计算陷入局部最优;通过自适应步长因子使得算法寻优过程中能随迭代次数逐渐减少随机搜索范围,从而提高收敛速度。单、多峰测试函数计算结果表明,改进算法显著提高了收敛速率与收敛精度;简支梁数值算例与某刚构桥实桥有限元模型修正结果表明,简支梁参数最大误差由初始的66.7%降低至修正后的1.08%,刚构桥频率最大误差由14.47%降低至3.25%。所提方法具有良好的更新精度,适用于大型复杂结构的有限元模型修正。