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

巡检机器人路径规划的几种常用算法的简介和比较报告目录TOC\o"1-3"\h\u148711.1Dijkstra算法 1199181.2蚁群算法 3223741.3Astar（A*）算法 6324021.4算法的比较和选择 81.1Dijkstra算法简介狄克斯特拉算法（Dijkstra）是一种贪心算法，它是通过搜索局部的最优路径，进而求出全局最优路径，去解决已知环境中的最优路径问题，即从一个节点开始依次逐步经过其余各个节点的最短路径算法。该算法最初是由荷兰计算机科学家Dikstra在1959年提出，如今在于诸多领域被广泛地应用。例如，王乙斐等使用Dijkstra算法创立了一种最优解列断面搜索方法；沃尔索（Wongso）等使用Dijkstra算法对城市公共汽车行驶的最短路径求解进行了估测和分析；李泽文等人基于Dijkstra算法，提出了一种适用于对电网的故障做行波定位的方法，从而解决了对故障定位和网络求解的复杂问题。思路如图2—1所示，设G=(V,E)是一个带有权重的有向图，把图中集合V中节点分成两组，第一组为已经考察过并寻得最短路径的节点集合（用集合S表示），初始时S中只有一个起点v，往后每求得一个节点的最短路径,就将该节点加入到S中，直到全部节点都加入到S中，结束算法；第二组是未考察过的，即最短路径未知的其他节点的集合(用U表示)，按照最短路径长度递增的顺序将第二组节点加入S中。在加入的过程中,我们始终保持让从起点v到S中的任意节点的最短路径长度不超过从起点v到U中的任意节点的最短路径长度。除此之外，每个节点对应一个最短距离,即S中任一节点的距离就是从起点v到该节点的最短路径长度,而U中的任一节点的距离是v到该节点的当前最短路径长度，并且路程中仅包括S中的节点作为中间节点。图2—1算法详述1.如图2—2所示，在开始时，S中只包含起点D，U中则包含节点S以外的节点，节点的距离U是“距起点D的距离节点”(例如，节点的距离是UV(S，V)的长度，则S和V不相邻，然后V的距离是无限的。1.选择离U距离最短的节点k，将该节点从U中移除并添加到S中；3.更新每个节点之间的距离在U和起点sU中的节点距离的原因是更新是k前一步中确定最短路径的节点被发现,所以k是可以用来更新其他节点的距离的。例如，(s,v)的距离可能大于(s,k)+(k,v)的距离之和。4.重复步骤(2)和(3)，直到遍历完所有的节点。图2—2最终我们可以得到从D移动到A的最短路径依次经过的点为：D、E、F、A，并求得最短距离为22。1.2蚁群算法简介蚁群算法（AntColonyAlgorithm，ACA），顾名思义，是一种效仿自然界中蚂蚁觅食行为的优化算法，最早在1991年由意大利学者DorigoM等人提出，并首次用于求解TSP(TravelingSalesmanProblem)问题，随后其在原有的基础上又系统地研究整理出了蚁群算法的数学模型和基本原理，大致如下：蚂蚁可以通过它们在行驶路途中所释放的一种名为“信息素”的化学物质去感知同类在寻找食物源时所释放的信号。通常情况下，信息素的浓度大小标志着路径的远近——浓度越高的地方，意味着路过的蚂蚁数量越大，则对应路径的距离就越短。这样在通常情况下，蚂蚁就更倾向于选择信息素浓度更高的路径行走，并且不断地释放信息素来增强该路径上的信息素浓度，以便吸引其他蚂蚁靠近。通过这样的一种正向循环的交流方式，在蚁群之间就形成了一种正反馈。最终，蚁群就能找到一条从巢穴到食物源位置的最优路径，也就是距离最短的路径。思路蚁群算法的基本思想如图2—3所示：蚂蚁觅食行为示意图图2—3蚂蚁觅食行为示意图蚂蚁的这种寻路方式可用来寻找一些待优化问题的最优解，把整个蚂蚁种群的所有路径看作是待优化问题的解的集合。蚂蚁会不断地在较短的路径上释放出更多的信息素以吸引同伴。随着时间的推移，在较短路径上积累的信息素浓度会逐渐增加，选择这条路径的蚂蚁数量也随之增加。最后，在这种循环的正反馈作用下，整个蚁群就会集中在最优路径上，这条路径也就是对应于待优化问题的最优解。蚂蚁的这种极具智慧而又简单的合作行为，带给了它多样性和积极的反馈。在觅食时，多样性使得蚂蚁不易走入死胡同甚至无休止地重复，这是蚁群智慧的一种体现。积极的反馈保留了积极的信息，这是一种强化学习的能力。两者的巧妙结合使得蚁群能够完成更具智慧的寻路工作，但同时也伴随着有一些相应的缺点。例如，如果多样性溢出，整个蚁群系统过于活跃，蚂蚁们随机运动就会变得愈发频繁，从而导致整个蚁群陷入混乱的状态。反之，如果没有足够的多样性，或者说有太多的正面反馈，这会导致整体机械化，当环境变化时，蚁群便不能适应去适应新的环境。算法详述蚁群算法的原理可以简单地分为3个步骤：1.单个可选择行驶节点的转移概率；1.距离启发函数；3.信息素浓度的更新。设在理想情况下，某个蚁群中蚂蚁的数量为m，节点数为n，节点i和节点j之间的距离为d，(i,j=1,2，…，n)时，节点i与节点j在t时刻的连接路径上的信息素浓度为。在初始时刻，每个节点之间互通路径上的信息素浓度均相同，可以设为。依据每个节点之间互通路径上的信息素浓度，确定其访问的下一个节点。在t时刻，蚂蚁k从节点i移动到节点j的概率，其计算公式如下:其中，为启发函数

，它表示蚂蚊从节点i转移到节点j的期望程度（k=1,2，...,m)，为蚂蚊k待访问的节点的集合。开始时，中有(n-1)个元素，即包括除了蚂蚊k初始节点外的其它所有节点。随着时间的推进,中的元素不断减少，直至为0，即表示所有的节点均访问完毕。α是信息素的重要因子，它的值越高，就说明信息素浓度对蚂蚁移动的反馈作用越大。β是启发式函数的重要因子，它的值越大，就说明启发式函数在迁移中的作用越大，即蚂蚁往距离越短的城市进行迁移的概率越大。当蚂蚁释放信息素时，各节点间互通路径上的信息素逐渐消失，因此，当所有蚂蚁完成一次循环时，还需要实时更新各节点间互通路径上的信息素浓度。具体公式如下:其中，表示第k只蚂蚁在城市i与城市j连接路径上释放的信息素浓度，表示所有蚂蚁在城市i与城市j连接路径上释放的信息素浓度之和。1.3Astar（A*）算法一、简介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所示，将地图栅格化，每一个正方形格子的中心称为节点；将所有格子划分为两种状态：可通过和不可通过（图中蓝色部分，实际应用中体现为障碍物）；图2—5定义两个列表集合：openList和closeList。openList列表由未考察的节点组成，而closeList表则由已经考察过的节点组成。类似Dijkstra算法中的集合U和集合S。确立初始节点（A)和目标节点（T)；在初始状态下，定义A为父节点，其距离自身的距离为0，无需进行考察，故移入closeList列表中；如图2—6所示，节点A周围共有8个节点，定义为字节点。将这些子节点作为待考察的节点放入openList列表中；需要注意的是，如果一个节点即未在openList列表中，也未在closeList列表中，则代表该节点还未被搜索到。图2—6路径优劣的判断依据是移动代价。我们采用Manhanttan（曼哈顿）距离计量法来定义单步移动代价，即把单次横向或纵向移动一个节点的代价定义为10。单步的斜向移动代价参考等腰直角三角形斜边的计算方式并取近似值，定义为14。如图2—7所示，以节点I为例，首先考察g，由于从A移动到I只需要做一次斜向移动，故g=14；然后考察h。“估计”的涵义是忽略路径中的一切障碍物，并且完全按照Manhattan距离计量法，计算只做横向或纵向移动的总的代价。从图中不难看出，从节点I到目标节点T只需移动四步（三步横向移动和一步纵向移动），故h=40。至此可得从节点A移动到节点I的总移动代价为：f=54。图2—7以此类推，分别计算当前openList中余下的7个子节点的移动代价，选出所需代价最小的节点F并移到closeList中。因此现在openList={B,C,D,E,G,H,I},closeList={A,F}。如图2—8所示，从openList中选择f值最小的节点I，将其放入到closeList中并作为新的父节点。检查节点I的所有子节点，忽略闭合列表中已经存在的不可行走节点和节点(F)，将剩余的子节点(J,K,L)放入闭合列表中。如果开放列表中已经存在一个相邻节点，我们将检查这条路径是否更优越，也就是说，如果当前节点(我们所选择的节点)到达该节点时g值更小。如果没有，就什么也不做。图2—8以此类推，不断重复上述步骤，直到搜索到目标节点T，完成路径搜索，结束算法。如图2—9所示是A*算法的一个简易流程图。图2—9A*算法流程图1.4算法的比较和选择根据第二章前面部分对三种常见算法的阐述，此节将对三种算法做了一个横向地对比，并最终确定了本文设计最终所采用的A*算法。Dijkstra算法是基于抽象图论的，本质上是广度优先搜索和发散搜索，具有较高的空间和时间复杂度。A*算法不仅记录其到源点的代价，还计算当前点到目标点的期望代价。作为一种启发式算法，A*算法也可以被认为是一种广度优先算法和一种快速搜索以遍历目标的深度算法。Dijkstra可以看作是A*算法的一种特殊情况，它是启发式为0的A搜索。Dijkstra算法是计算从初始点到所有其他点的最短路径长度，而A*算法更注重“从点到点”的最短路径长度。蚁群算法的主要缺点有:1。收敛速度问题。蚁群算法的计算量大，求解最短路径所需的时间长，所以效率不高；2。局部最优的问题。在蚁群算法中，理论上要求所有蚂蚁选择同一条，即最优路径。但在实际计算中，给定一定的循环次数时，很难达到这种理想状态。我们并不要求所有的蚂蚁都找到最优路径，而是只要求其中一部分蚂蚁找到最优路径。如果所有蚂蚁都找到最优路径，将影响计算效率。3.优化能力。蚁群算法中用到的参数较多，并且它们之间存在一定的关联，容易相互影响。虽然蚁群算法在很多领域都得到了