融合插点和跳跃点改进A*算法的路径规划

为了解决传统A*算法在路径规划中存在的一些问题,提出了一种融合插值点跳跃搜索路径算法来改进A*算法。在对栅格环境图中具有特殊意义的多组数据进行预处理后,通过起始点和目标点确定目标函数,并搜索出一条最优路径。利用MATLAB软件平台对8组规格不同的环境图进行了路径规划仿真。实验结果表明,改进后的算法可以减少计算时间、搜索节点数量、内存占用和搜索路径长度。可见改进后的算法在搜寻最佳路径方面的效率更高。     

多约束最优路径算法比较研究

针对多弧权网络路径寻优及其效率问题,提出了4种多约束最优路径算法,并对其进行了比较研究.基于经典Dijkstra算法,提出了多约束最优路径问题的D_MCOP算法;引入启发式搜索思想,设计了A*_MCOP算法和迭代加深搜索的IDA*_MCOP算法;为克服IDA* _MCOP算法每次迭代都要回到起始节点重新搜索的缺陷,提出了一种多约束边沿搜索算法——Fringe_MCOP算法.实例研究表明:三种启发式搜索算法扩展的节点数、边数以及算法的执行时间都远小于D_MCOP算法,而且Fringe_MCOP算法在三种启发式算法中性能最优;当给定的约束条件与最优路径的权值向量越接近时,算法的执行效率越高,当网络规模较大时,这一趋势更加明显;当约束条件过于严格而得不到满足约束条件的路径时,A*_MCOP和Fringe_MCOP的算法速度比IDA*_MCOP的算法速度更快,D_MCOP的算法速度最慢.     

应急资源配送中Dijkstra改进算法的研究

路径规划问题是应急资源配送中的核心问题,最短路径算法在路径规划过程中起着决定性的作用,在众多路径规划算法中最经典且最具代表性的就是Dijkstra算法。以传统的Dijkstra算法分析为基础,从存储结构和算法过程两个方面进行一定程度的改进,目的是在节点数和边数较多的情况下,提高网络模型的处理效率。以真实道路交通数据为基础进行相关实验,结果证明,改进后的Dijkstra算法可以有效减少节点的计算量,提高算法的运行效率。     

果园移动机器人的全局最优路径规划研究

为了实现移动机器人在果园环境下自主行走,对果园移动机器人在复杂果园环境中的最优路径规划进行研究.首先,利用栅格法定义了移动机器人在栅格上的运动方向、障碍物及信息编码,模拟建立出果园的环境地图模型.然后分别编写Dijkstra算法、A*算法,对果园机器人进行全局最优路径规划.通过分析比较,得出A*算法所规划的最优路径更为方便,搜索效率更高,更加满足果园机器人的实际工作需求,提高其工作效率.     

基于Mapinfo的最短路径混合搜索算法

在迪杰斯特拉(Dijkstra)算法的基础上,针对有较多节点和道路的大网络在求解最短路径时计算时间慢、扩展节点多的缺点,采用基于局部最优方向和A*算法的混合算法,利用局部最优方向法的结果,对A*算法的启发函数加以改造,可以减少扩展的节点数量,快速的找到一条最短路径.通过实验仿真证实了该算法的快速有效性.     

智能疏散系统导向标志计算及疏散路径仿真

为了解决大型综合建筑中智能疏散系统在火灾等突发情况发生时可根据复杂建筑结构规划出合理、安全的疏散路径问题,提出了一种基于改进A~*算法的多起点、多出口路径规划方法。通过增加转弯惩罚值,结合火灾影响区域实时信息和火灾中心点的距离改进了估价函数,进而计算出最优疏散路径。依据搜索出的最优路径调整三维楼层地图中各个导向标志方向,从而引导不同位置人员从最优路径疏散逃生。仿真实验结果表明,在计算多起点、多出口疏散路径时,改进A~*算法与传统Dijkstra算法和A~*算法相比,搜索方向更加明确,路径更加平滑,搜索效率更高,运行时间更短,并能结合火灾信息保证疏散路径的安全性。该算法在求解大型综合建筑火灾安全疏散路径方面具有很好的应用前景。     

基于启发式策略的最短路径算法

在讨论经典Dijkstra算法和启发式策略算法（A^＊，矩形算法等）的基础上，提出一种基于Dijkstra算法的动态方向限制搜索算法用于求解道路网络中两节点之间最短路径．该算法结合人类的搜索思路和动态灵活的处理方式，对最短路径算法的搜索策略进行改进，动态改变搜索限制区域，减少计算时间．该算法不仅可以单独提高计算最短路径的效率，而且与其他算法结合起来还可取得更好的效果．实际结果证明动态方向限制搜索算法比经典Dijkstra算法减少近50％的搜索节点数和搜索时间．     

基于加权A~*算法的服务型机器人路径规划

针对室内环境下的服务型移动机器人路径规划问题,分析并比较了两种经典算法--Dijkstra算法及基于Manhattan估计函数的A*算法,通过改变A*算法估价函数中参数的权值来优化路径轨迹,从而既满足A*算法的可接纳性,同时义实现两种算法的融合.在VC环境下编译出路径规划的仿真程序,通过变换起始点与目标点的坐标,比较运算时间和生成的路径轨迹.结果显示:加权A*算法优化了A*算法的路径轨迹,且在计算时间上优于Dijkstra算法,解决了服务型移动机器人的路径规划问题,满足实时性要求.     

车辆导航中一种改进的路径优化算法

针对车辆定位与导航系统中的最优路径规划中存在的问题,研究了最短路径搜索算法的快速实现技术,提出了一种启发式快速最优路径规划算法.在分析经典迪杰斯特拉最短路径搜索算法和A*启发式搜索算法的基础上,利用双向A*算法和地图分层搜索技术减小搜索空间,采用二叉堆结构来实现路径计算过程中优先级队列的一系列操作,从而提高了算法的执行效率.仿真试验的结果证明了该算法的优异性能.     

一种适于车辆导航系统的快速路径规划算法

针对城市道路网图节点数较多,经典的求解最短路径的Dijkstra算法存在计算时间较长的问题.对矢量化的城市道路网图的特点进行分析,给出了道路网图的计算机存储结构,提出一种快速求解城市道路网两节点间的最短路径近似算法.算法的实现采用双向式搜索法、投影法和夹角最小的方法.理论分析和实验结果表明,和Dijkstra算法相比,该算法尽管有时得不到最优解,但能大大减小搜索空间,提高搜索速度,时间复杂性不超过O(N),适用于车辆导航系统.     

健康投资对中国经济发展的影响研究——基于省级面板数据的空间计量检验

针对全局路径规划问题提出了一种改进的A*算法.首先,采用栅格方法建立环境模型,使用A*算法进行初步的路径规划.其次,针对A*算法规划的路径冗余点较多以及路径长度和转折角度较大的缺陷,提出将A*算法规划出的路径按较小的分割步长进行分割,得到一系列路径节点.最后,从起点开始依次用直线连接终点,当直线没有穿过障碍物时,则将中间路径点剔除,减小路径长度和转折角度.在仿真实验和实物实验中,分析和比较了本文算法与A*算法以及另一种改进A*方法.另外还研究了在不同障碍率、任务点数量和分割步长的情况下,本文算法与其他算法的优劣.结果表明,本文算法能有效地减小路径长度和转折角度.     

基于平滑A~*算法的移动机器人路径规划

栅格环境下A*算法规划出的移动机器人路径存在折线多、转折次数多、累计转折角度大等问题.为获得较优路径,提出平滑A*算法.在A*算法规划的路径基础上,遍历路径中的所有节点,当某一节点前后节点连线上无障碍物时,将延长线路的这一中间节点删除,建立平滑A*模型.仿真结果表明,平滑A*算法优于Ant(蚁群),Anyti me D*算法.平滑A*算法路径长度降低约5%,累计转折次数降低约50%,累计转折角度减少30%～60%.平滑A*算法能处理不同栅格规模下、障碍物随机分布的复杂环境下移动机器人路径规划问题.     

一种改进工业自动导引车路径规划算法

为了解决当前工业自动导引车(automated guided vehicle,AGV)栅格地图下路径规划算法存在路径转弯较多、弯曲度较大、搜路时间较长且距离障碍物近等问题,基于A?算法提出了一种改进路径规划算法.首先,通过在全局地图中设置路径关键节点,生成关键点拓扑地图,并利用Floyd算法进行最短路径规划,输出路径节点集合;其次,利用A?算法对集合中相邻节点进行路径规划,并将生成的路径进行拼接;最后,通过引入贝塞尔曲线对拼接路径进行平滑处理,以获取全局路径.实验结果表明:本文算法规划的路径转弯更少、弯曲度更小、搜索时间更短且能完全避开障碍物行走,更符合工业AGV的应用环境.     

Path planning based on sliding window and variant A*algorithm for quadruped robot

In order to improve the adaptability of the quadruped robot in complex environments , a path planning method based on sliding window and variant A * algorithm for quadruped robot is presen-ted .To improve the path planning efficiency and robot security , an incremental A*search algorithm ( IA*) and the A*algorithm having obstacle grids extending ( EA*) are proposed respectively .The IA* algorithm firstly searches an optimal path based on A * algorithm, then a new route from the current path to the new goal projection is added to generate a suboptimum route incrementally .In comparison with traditional method solving path planning problem from scratch , the IA* enables the robot to plan path more efficiently .EA* extends the obstacle by means of increasing grid g-value, which makes the route far away from the obstacle and avoids blocking the narrow passage .To navi-gate the robot running smoothly , a quadratic B-spline interpolation is applied to smooth the path . Simulation results illustrate that the IA* algorithm can increase the re-planning efficiency more than 5 times and demonstrate the effectiveness of the EA * algorithm.     

移动机器人全局动态路径规划融合算法

针对移动机器人全局动态路径规划效率较低的问题,提出一种基于安全A^*算法与双速度模型动态窗口法的全局动态路径规划融合算法.首先,通过安全A^*算法得到全局最优路径节点,将其作为临时目标节点,为动态规划提供全局信息,避免出现局部最优.然后,采用时间序列Bottom-Up算法减少路径节点数,从而减少迭代次数、计算代价和储存代价,提高算法效率.最后,采用双速度模型对动态窗口法进行改进,通过避障重规划机制,解决全局动态路径规划时移动机器人绕远甚至绕圈的问题,并通过MATLAB平台进行仿真实验.仿真结果表明:文中算法的规划效率可提高46.18%,保证了路径的安全性和移动机器人速度的平稳性,文中算法的路径质量和规划效率更佳.     

一种限制搜索区域的最短路径改进算法

最短路径算法效率是许多应用领域普遍关注和迫切需要解决的问题。该文在深入分析经典Dijkstra最短路径算法优化途径的基础上,从控制路网规模入手,提出了矩形限制搜索区域的最短路径算法。根据路网分布的特点,采取比值系数分段取值的方法,进一步提高了算法效率。原型系统实验显示了改进算法的高效性和可行性。     

室内移动机器人路径规划研究

路径规划是自主移动机器人的研究重点。针对传统的A*算法搜索出的路径存在途径危险区域,未考虑机器人外形尺寸、路径不平滑等问题,提出了一种改进A*算法的路径规划方法。在新的栅格化环境地图中,通过改进的搜索策略进行路径搜索;并对路径点删减和优化,通过分段多项式曲线平滑路径。实验仿真结果表明,新方法生成的路径满足移动机器人的动力学和运动学特性,且更符合室内移动机器人的轨迹跟踪和运动控制,该方法简单有效。     

基于Petri网与改进A星搜索算法的矿井机车调度优化

为了提高煤矿井下机车调度效率、防止机车碰撞、堵塞,根据井下调度特点建立了机车运行赋时Petri网模型。针对原有启发式A*搜索算法存在的易陷入局部最优的缺点,提出了基于petri网的并发变迁遴选算法,引入变迁并发度概念,与启发式A*搜索算法相结合,得到改进的A*搜索算法。经过改进后算法的回溯计算,得到Petri可达图上的最佳路径,从而得出最优调度策略。根据以上算法进行MATLAB建模,最终仿真结果表明,经过改进的启发式A*搜索算法有效的避免了陷入局部最优解,其计算得出的调度路径及调度策略资源消耗量最少,调度效率较高且未出现机车堵塞碰撞等问题。