【巡检机器人路径规划的几种常用算法的简介和比较报告4300字】

巡检机器人路径规划的几种常用算法的简介和 1 4 7 1一.简介狄克斯特拉算法(Dijkstra)是一种贪心算法，它是通过搜索局部的最优路学家Dikstra在1959年提出，如今在于诸多领域被广泛地应用。例如，王乙斐等使用Dijkstra算法创立了一种最优解列断面搜索方法；沃尔索(Wongso)等使等人基于Dijkstra算法，提出了一种适用于对电网的故障做行波定位的方法，从如图2-1所示，设G=(V,E)是一个带有权重的有向图，把图中集合V中节点分成两组，第一组为已经考察过并寻得最短路径的节点集合(用集合S表示),初始时S中只有一个起点v,往后每求得一个节点的最短路径，就将该节点加入到S中，直到全部节点都加入到S中，结束算法；第二组是未考察过的，即最短路径未知的其他节点的集合(用U表示),按照最短路径长度递增的顺序将第二组2最短路径长度不超过从起点v到U中的任意节点的最短路径长度。除此之外，每个节点对应一个最短距离，即S中任一节点的距离就是从起点v到该节点的最短路径长度，而U中的任一节点的距离是v到该节点的当前最短路径长度，并且路程中仅包括S中的节点作为中间节点。邻节点B/F/GA/CFB/D/E/FC/EC/D/F/GA/B/C/E/GA/E/F字母节点ABCDEFG数字节点12345671.选择离U距离最短的节点k,将该节点从U中移除并添加到S中；3.更新每个节点之间的距离在U和起点sU中的节点距离的原因是更新是k前一步中确定最短路径的节点被发现，所以k是可以用来更新其他节点的距离的。4.重复步骤(2)和(3),直到遍历完所有的节点。2344选取节点F,S={D(0),C(3),E(4)7S={D(0),C(3),E(4),F7S={D(0),C(3),E(4),F88S={D(0),C(3),E(4),F(6),G(12)S={D(0),C(3),E(4),F(6),G(12)图2—2并求得最短距离为22。1.2蚁群算法蚁群算法(AntColonyAlgorithm,A蚂蚁觅食行为的优化算法，最早在1991年由意大利学者DorigoM等人提出，并首次用于求解TSP(TravelingSale蚁群算法的基本思想如图2—3所示：米米米BNestAC喘崇蚂蚁的这种寻路方式可用来寻找一些待优化问题的最优解，把整个蚂蚁种群的所有路径看作是待优化问题的解的集合。蚂蚁会不断地在较短的路径上释放出更多的信息素以吸引同伴。随着时间的推移，在较短路径上积累的信息素浓度会逐渐增加，选择这条路径的蚂蚁数量也随之增加。最后，在这种循环的正反馈作用下，整个蚁群就会集中在最优路径上，这条路径也就是对应于待优化问题的最优解。蚂蚁的这种极具智慧而又简单的合作行为，带给了它多样性和积极的反馈。在觅食时，多样性使得蚂蚁不易走入死胡同甚至无休止地重复，这是蚁群智慧的一种体现。积极的反馈保留了积极的信息，这是一种强化学习的能力。两者的巧妙结合使得蚁群能够完成更具智慧的寻路工作，但同时也伴随着有一些相应的缺点。例如，如果多样性溢出，整个蚁群系统过于活跃，蚂蚁们随机运动就会变得愈发频繁，从而导致整个蚁群陷入混乱的状态。反之，如果没有足够的多样性，或者说有太多的正面反馈，这会导致整体机械化，当环境变化时，蚁群便不能适应去适应新的环境。设在理想情况下，某个蚁群中蚂蚁的数量为j之间的距离为d,(i,z,(t),…,n6在t时刻，蚂蚁k从节点i移动到节点j的概率，其计算公式如下：其中，n.(t)为启发函,它表示蚂蚊从节点i转移到节点j的信息素的重要因子.它的值越高.就说明信息素浓度对蚂蚁移动的反馈作用越大。其中，表示第k只蚂蚁在城市i与城市j连接路径上释放的信息素浓度，△T表示所有蚂蚁在城市i与城市j连接路径上释放的信息素浓度之和。A*(A-star)算法是一种被广泛应用于室内机器人的路径规划、游戏动画路径搜索等的寻路算法，也是解决许多搜索问题的有效算法，它也是求解静态环境中的最短路径的最有效的直接寻路方法。二、原理A*算法是一种常用的启发式搜索算法。它从初始节点(即父节点),搜索和初始节点相邻节点(子节点),通过评价函数计算成本移动8子节点，并选择一个函数点，并终止搜索，结束算法。由于A*算法每次选择父节点都选择函数值最小的节点，所以最终物体移动的路径替换值也是最低的。A*算法中最关键的内容是“估值函数”,其公式如下所示：f(n)+g(n)=h(n)式中，f(n)为从初始状态到目标状态，经过状态n的代价估算，即物体的总移动代价；G(n)是状态空间中从初始状态到状态n的实际代价，即物体从初始位置移动到当前位置的代价估计；H(n)为状态n到目标状态的最优路径的估计代价，即对象从当前位置到最终目标位置的估计代价。下面将介绍A*算法在实际应用中的一整套完整流程。三、流程如图2—5所示，将地图栅格化，每一个正方形格子的中心称为节点；将所有格子划分为两种状态：可通过和不可通过(图中蓝色部分，实际应用中体现为障碍物);8图2—5组成，而closeList表则由已经考察过的节点组成。类似Dijkstra算法中的集合U和集合S。2.确立初始节点(A)和目标节点(T);3.在初始状态下，定义A为父节点，其距离自身的距离为0,无需进行考察，故移入closeList列表中；4.如图2—6所示，节点A周围共有8个节点，定义为字节点。将这些子节点作为待考察的节点放入openList列表中；需要注意的是，如果一个节点即未在openList列表中，也未在closeList列表中，则代表该节点还未被搜索到。5.路径优劣的判断依据是移动代价。我们采用Manhanttan(曼哈顿)距离计量法来定义单步移动代价，即把单次横向或纵向10。单步的斜向移动代价参考等腰直角三角形斜边的计算方式并取近似值，定义为14。6.如图2—7所示，以节点I为例，首先考察g,由于从A移动到I只需要做一次斜向移动，故g=14;7.然后考察h。“估计”的涵义是忽略路径中的一切障碍物，并且完全按照Manhattan距离计量法，计算只做横向或纵向移动的总的代价。从图中不难看出，从节点I到目标节点T只需移动四步(三步横向移动和一步纵向移动),故h=40。至此可得从节点A移动到节点I的总移动代价为：f=54。8.以此类推，分别计算当前openList中余下的7个子节点的移动代价，选出所需代价最小的节点F并移到closeList中。因此现在openList=9.如图2—8所示，从openList中选择f值最小的节点I,将其放入到F5G5IJKJ10.以此类推，不断重复上述步骤，直到搜索到目标节点T,完成路径搜索，如图2—9所示是A*算法的一个简易流程图。搜索区域划分网格搜索区域划分网格将初始节点放入为这些点的父网格图2—9A*算法流程图较高的空间和时间复杂度。A*算法不仅记录其到源点的代价，还计算当前点到目标点的期望代价。作为一种启发式算法，A*算法也可以被认为是一种广度优种特殊情况，它是启发式为0的A搜索。Dijkstra算法是计算从初始点到所有其路径所需的时间长，所以效率不高；2。局部最优的问题。在蚁群算法中，理论联，容易相互影响。虽然蚁群算法在很多领域都得到了广泛的应用，但参数的选择更多地依赖于经验和试错，初始参数不当会削弱算法的优化能力。进行路径规划