典型航路规划方法的基本原理例习题展示

1、典型航路规划方法的基本原理例题展示典型航路规划方法的基本原理例题展示PAGE19典型航路规划方法的基本原理例题展示简要论述典型航路规划方法的基本原理（任选方法之一，且选择该方法中的一种具体方法。）并举例说明。（1）路标图法；（2）单元分解方法；（3）人工势场法答：选择（1）路标图法。概略图( Skeleton)也称路标图( Roadmap )。在基于概略图空间的路径规划方法中，首先根据一定的规则将自由的C空间（Configuration Space)表示成一个由维的线段构成的网络图，然后采用某一搜索算法在该网络图上进行航迹搜索。这样，规划问题被转化为一个网络图的搜索问题。概略图必须表示出C空间

2、中的所有可能的路径，否则该方法就是不完全的，即可能丢失最优解。常用的概略图方法包括通视图法( Visibility Graph)、Voronoi图法、轮廓图法( Silhouette)、 子目标网络法(Subgoal Network )和随机路线图法( Probabilistic Roadmap, PRM)。 通视图法通视图由规划空间中的障碍物的相互可见的顶点间的连线构成。图1-1给出了包含三个多边形障碍物的二维规划空间的通视图，其中较粗的线表示起始点S和目标点G之间的一条最短路径。1989 年，Asano等证明在具有n个顶点的二维规划空间中，其通视图的边数具有数量级0 (n2)，构造通视图所

3、需时间的数量级也为0 (n2)。图1-1通视图 通视图法可用于求解二维规划空间中的最短路径问题。尽管它也可用于高维规划空间，但此时生成的路径将不再是最短的。由于通视图不能表达物体运动的方向性约束，除非运动物体可以按任何方向以任意角度转弯，通常很少用通视图法求解实际的路径规划问题。 Voronoi图法如果运动物体要求与障碍(或威胁)的距离越远越好，可以采用Voronoi图方法。Voronoi 图由与两个或多个障碍(或威胁)的给定特征元素距离相等的点的集合构成。图1-2 给出了以多边形障碍物自身作为特征元素生成的Voronoi 图。如果以多边形的边作为特征元素则可以得到不同的Voronoi 图。对

4、于只包含有威胁的规划空间来说，可以将威胁源的中心点作为特征元素。Voronoi图将规划空间分为多个区域，每个区域只包含一个特征元素。对于区域中的每一点，该区域的特征元素是所有特征元素中最近的。图1-2 Voronoi 图与通视图比较，Voronoi 图具有明显的优点，Voronoi 图的边数只有数量级0 (n)， 构造Voronoi图所需时间的数量级为0(nlogn),其中n为所选特征元素数目。如果将多边形的边作为特征元素，则Voronoi图一般都包含有曲线段。1987 年，Canny 和Donald通过使用一种不同于欧氏距离的度量方法，构造出了一种只包含直线段的Voronoi 图。对于维数大

5、于2的高维空间，通视图与Voronoi图将变得非常复杂，而且一般没有确定的特征元素选择方法。例如，多面体间的Voronoi 图由二维曲面构成，它不再是一维的轮廓线。尽管通视图仍然可以由多面体的各项点间的连线组成，但此时最短路径不再存在于通视图之中(如图1-3 所示)。因此，Voronoi图一般只应用于二维路径规划。图1-3最短路径不经过多面体的顶点 轮廓线法对于高维空间，Canny 于1987 年给出了另一种构造概略图的方法。该方法先将高维空间中的物体投影到一个较低维的空间中，然后在低维空间中找出其投影的边界曲线，称为轮廓。该轮廓又投影到一个更低维的空间中，如此继续下去，直到轮廓变成一维的轮廓

6、线。对于同一障碍物其轮廓不相连的部分，需用连接线将它们连接起来(如图1-4 (b)所示)。这样得到的一维轮廓线图比原始的高维空间简单得多，可以从中找到一条可行的路径。该方法通常在理论上用于分析问题的复杂性，而很少用于实际中的路径规划。使用轮廓线方法得到的路径，运动物体总是沿着障碍物边缘移动。图1-4轮廓线 子目标网络法子目标网络方法不直接构造明显的概略图，而是保存一个可以从起始点达到的节点列表。如果目标点出现在该表中，则规划成功结束。规划空间中两点之间的可达性由一个简单的局部规划算法来判断，该局部规划算法称为局部算子。局部算子的选择一般根据具体问题确定，例如，可以简单地在两节点之间按直线运动。

7、开始的时候，该算法在起始节点与目标点之间选取一个由称为子目标的中间节点组成的候选序列，并运用局部算子依次连接这些子目标。在选取子目标候选序列时可以采用某些启发式信息，也可以随机选取。如果连接过程不能到达目标点，则将已经连接的子目标保存在列表中。然后任取一个已到达的子目标，并在该子目标与目标节点之间选取一个候选序列，如此反复，直至到达目标节点。在该算法中，可到达的节点间的运动路径可以由局部算子非常容易地重新得到，因此不用保存。该算法的一个主要优点是节省内存空间。通视图可以看作是一个子目标网络，其子目标为障碍物的顶点，局部算子为“直线运动”。图1-5显示了一个“沿对角线方向运动”的局部算子生成的子

8、目标网络。图1-5 子目标网络局部算子的选择确定了规划算法的实现。一种极端的情形是采用“直线运动”，但当两个节点之间的距离很远时，该方法通常很难找到可行的路径。因此，相邻的两个子目标间的距离一般很近，这势必增加子目标的数目，从而增加内存空间。另一个极端就是采用一种精确的全局规划算法作为局部算子，此时仅有一个包含有起始点和目标点的候选序列需要连接。这种方法将一个全局规划问题分解成若千个比较简单的局部规划问题。 随机路线图法随机路线图法是近年发展起来的一种针对多自由度问题的路径规划方法，由Overmars等于1992年率先提出。该方法通过在规划空间中随机进行采样生成路线图，然后在该路线图中搜索路径

9、。随机路线图的构造如下:如果最新的采样点与路线图中的某节点间存在可行路径，则将该采样点加入到路线图中，同时找出该节点与路线图中的近邻节点间可能存在的路径，并将可行路径作为节点间的边加入到路线图中。该方法的优点之一就是可以在规划时间和路径的质量之间进行权衡，构造随机路线图的时间越长，得到最优路径的可能性就越大。在确定环境下，随机路线图一般可以事先构造。然而，如果规划环境一日发生变化，随机路线图并不能通过局部更新以适应新的环境，因此，该算法-般不适于在线实时应用。简要论述航路规划启发式搜索算法A*， .D*，anytime algorithms (ARA*)，anytime re-planning

10、 algorithms (AD*)的特点。A*A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。和Dijkstra一样，A*能用于搜索最短路径。和BFS一样，A*能用启发式函数引导它自己。它把Dijkstra算法（靠近初始点的结点）和BFS算法（靠近目标点的结点）的信息块结合起来。有点不同的是，类似BFS的启发式方法经常给出一个近似解而不是保证最佳解。然而，尽管A*基于无法保证最佳解的启发式方法，A*却能保证找到一条最短路径。在讨论A*的标准术语中，g(n)表示从初始结点到任意结点n的代价，h(n)表示从结点n到目标点的启发式评估代价（heuristic estimated co

11、st）。当从初始点向目标点移动时，A*权衡这两者。每次进行主循环时，它检查f(n)最小的结点n，其中f(n) = g(n) + h(n)。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。如果估价值实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。估价值与实际值越接近，估价函数取得就越好。A*算法的搜索过程实际上是被选节点扩展的过程，它存在一种潜能，可以采用最少的估价源找到最近的优化路径。在确定优化路径后，要进行航路回朔，计算是否满足任务系统中设定的燃油、时间、速

12、度等约束条件(这些约束条件有一定的次序)。如果不能满足所有的约束条件，则计划就失败，必须重新计划并修改有关参数。启发式函数h(n)告诉A*从任意结点n到目标结点的最小代价评估值。例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt(dx-nx)*(dx-nx)+(dy-ny)*(dy-ny)；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。A*算法的关键是对评价函数的定义，从找到一条最小代价路径的思路出发，在计算时可以把评价函数值分为从初始节点到节点n的代价，和

13、从节点n到达目标节点的代价两个部分来进行计算和分析。估价函数的正确选取将直接关系到A*算法的成功与否，而函数的确定却与实际情形有着密切的关系。所选择的启发式函数的好坏是很重要的。一个不恰当的启发式函数反而会减慢A*算法，导致其产生出不好的路径来。如果启发式估值是精确的，则A*将不会偏离最佳路径。当然，很难得到一个精确的启发式估值，但知道当给A*一个正确的信息，它会正确地进行操作，这是非常有用的。另外，如果启发式估值趋向于精确值，则A*搜索操作就会越少。因此，f值的增加是与搜索的多少相关。当启发式估值是精确的，则f将不会变化。当启发式估值低于实际值太多，f值就会迅速地增加。启发式越好，搜索的地方

14、就越少。当探测器检测到实际的环境和已知的环境信息存在差异时,则更新原有的环境地图信息,那么原先规划的路径也许就是不可通的或者不是最优的。此时,可以根据更新的环境信息重新规划一条从当前所在位置到目标点的新的路径,但是代价很大。据于此,Anthony Stentz提出的动态A*算法或者叫D*算法。D*A* 在静态路网中非常有效，但不适于在动态路网，环境如权重等不断变化的动态环境下。D*是动态A*（D-Star,Dynamic A Star）。相对于A*算法，D*算法的主要特点是可以应用于环境仅为部分已知或环境不断变化的情况下的路径寻优。该算法根据当前已知环境状况沿最有启发性的节点搜索，如探测到下一

15、节点将会发生阻塞，则适时调整估价函数，改变方向继续搜索，从而最终得到整个路径。D*算法弥补了A*算法必须事先知道全部环境信息的缺点，且具有与A*算法一样的高效特征。在环境信息是静态的时候，D*的搜索方法和Dijkstra算法的搜索过程是一样的。D*算法的主要过程分为离线和在线两个部分。离线部分主要是指在已有的部分环境信息下规划出一条机器人的行进路径;而在线部分主要指移动机器人在沿着离线部分规划出的路径行进，当遇到和己知的部分环境不相同的情况或者说接受到新的环境信息的时候，重新规划一条从机器人当前位置到目标的路径的过程。D*算法的作用相当于静态情况下，信息完全己知的情况下的路径规划算法。此时它的

16、执行过程和Dijksart搜索算法相同，在离线情况下，基本的D*算法的效能是不及A*算法的。但是，A*算法利用启发信息限制了搜索扩展到的状态，而其中一些没有扩展到的状态很有可能是在后面的在线规划中所需要用到的，因而D*必须使用这种离线的规划方法。对于在线规划部分，此时算法的执行时间和很多因素直接相关，比如，预先己知的环境信息量，实际环境中障碍物密度，机器人环境传感器感知范围等。因此根前面的一般的重规划方法相比，在相同的障碍物密度，相同的已知部分信息量，相同的感知范围情况下，D*算法所重新规划的环境中的状态只是环境中的一部分，而一般的重规划策略则需要在整个更新的环境中重新规划。从这一点来说，该算

17、法是很有优势的。并且随着环境大小的增加，算法比普通的最优重规划方法所节约的时间也成倍的增加。环境信息部分未知的情况下全局规划部分很明显需要一个重规划的过程。这里的重规划是指当遇到已知环境与原有实际环境存在差异时，使得原有的全局规划路径无法通过而必须重新进行的规划。按照重规划与原规划的起点相同与否可以划分为完全重规划与不完全重规划。所谓完全重规划，是指重规划路径的起点与原规划的起点相同，而不完全重规划或部分重规划则是指重规划路径的起点与原规划的起点不同。动态的D*算法是不完全的重规划，但是利用了原有的规划信息，在一定程度上实现了最优性和实时性的结合。D*算法做到全局规划和局部信息相结合、离线的规

18、划和在线的规划相结合。D*的搜索步骤如下：1.先用Dijstra算法从目标节点G向起始节点搜索。储存路网中目标点到各个节点的最短路和该位置到目标点的实际值h,k（k为所有变化h之中最小的值,当前为k=h。每个节点包含上一节点到目标点的最短路信息1(2),2(5),5(4)，4（7）。则1到4的最短路为1-2-5-4。原OPEN和CLOSE中节点信息保存。2.机器人沿最短路开始移动，在移动的下一节点没有变化时，无需计算，利用上一步Dijstra计算出的最短路信息从出发点向后追述即可，当在Y点探测到下一节点X状态发生改变，如堵塞。机器人首先调整自己在当前位置Y到目标点G的实际值h(Y)，h(Y)=

19、X到Y的新权值c(X,Y)+X的原实际值h(X).X为下一节点(到目标点方向Y-X-G），Y是当前点。k值取h值变化前后的最小。3.用A*或其它算法计算，这里假设用A*算法,遍历Y的子节点，点放入CLOSE,调整Y的子节点a的h值，h(a)=h(Y)+Y到子节点a的权重C(Y,a),比较a点是否存在于OPEN和CLOSE中。D*算法在动态环境中寻路非常有效，向目标点移动中，只检查最短路径上下一节点或临近节点的变化情况，如机器人寻路等情况。对于距离远的最短路径上发生的变化，则感觉不太适用。anytime algorithms (ARA*)在很多情况下，最短路径不一定就是我们想要的，还需要考虑时间

20、等因素。在有限的时间内得到好的、可行的结果才是我们想要的。ARA*算法就是解决这类问题的。Anytime算法是80年代末期Dean和Boddy在关于时间依赖规划(Time-dependent planning)研究中提出的，其核心思想是使解的质量随计算时间的增加而不断提高。它具有在求解质量和求解时间之间折中的能力，被广泛应用于时间约束条件下复杂问题的近寸以求解。同时也提出了一种问题元级控制的方法，使得智能系统具有高层调度的能力，且扩充了传统算法的输入一处理一输出的计算过程，提供了运行中动态输出结果的功能。Anytime算法把每一组输入和特定的计算时间映射为一组输出结果，这一特征使得该算法可以在

21、任何时候被中断，返回特定质量的解，因此被称为Anytime算法。从某种意义上说，具有如下特征的近以算法都可以称为Anytime算法: 1.在算法执行的任何时候都能给出问题的一个解; 2.解质量随计算时间的增加而提高。可以看出Anytime算法是一个逐步求精的过程。在这一点上，许多现有的算法都可视为Anytime算法。如:计算方法中的迭代算法、迭代加深的启发式搜索算法、各种贪心算法、利用随机原理的蒙特卡岁方法、遗传算法。这些传统的Anytime算法是被动式的，缺乏完善的元级调度机制。研究者公认，作为完善的Anytime算法，还应该具有如下特征:1.质量的度量Anytime算法用多值度量模型代替了

22、传统的二值度量模型，因此解的质量是可以度量的;它反映了近似解和真实解的质量差距。 2.可预言性Anytime算法本身包含许多关于输入、执行时间和解质量映射关系的统计信息，侠得算法可预言在一定计算时间内输出解的质量，以便做高层的调度和控制。3.单调性Anytime算法具有解质量随执行时间增加而单调增加的特性。这一点是以解质量可以度量为前提的。只有这样，Anytime算法才能随计算时间的增加返回一个质量更好的解，而不仅是最新产生的解。4.递减性Anytime算法的解质量在运行的早期提高较快，随着计算时间的增加，解质量提高的速率会逐渐减小。中断及可恢复性是Anytime算法最本质的特性。它能在运洲于

23、的任何时候停止，同时也能够恢复执行，且利用Anytime算法的系统能够在运行中重新分配计算资源。anytime algorithms (ARA*)算法在每次搜索中,根据新的因子的值,只处理在上次处理中可能不是有效的节点。首先,根据因子0的值通过A*算法来搜索路径,只不过每个节点最多处理一次。在某次搜索过程中,如果某个节点已经扩展过,但是由于周围于周围节点之间边的代价的改变需要再次处理时,不是将其再放入OPEN表中处理,而是放入INCONS表中,当本次搜索结束后,再将INCONS表中的节点全部插入OPEN表中用于下次搜索。这里INCONS表是用来保存这类已扩展过但是需要再次处理的节点。这个算法在

24、两个方面提高了每次搜索效率。首先,由于对每个节点最多只扩展一次,所以路径可以很快产生。其次,由于每次处理中,只处理在ICONS表中的节点,所以以前搜索的结果可以重用。因此,当因子的值在每次连续的搜索中减少时,一个相对较少计算量就可以产生新结果。在A*算法时我们了解到：f(n)=g(n)+h(n)，用d(n)表达状态n到目标状态的距离，那么h(n)的选取大致有如下三种情况：如果h(n)d(n)，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。当h(n)d(n)的时候，会搜索较少的点，快速的产生一个解。ARA*算法就是用到了这一点。anytime re-planning algorithm

25、s (AD*)AD*算法就是结合了D*算法中的一升级版D*Lite算法和ARA*算法提出的一种新算法，兼顾D*Lite算法和ARA*算法的优点。在AD*算法之前已经存在了很多算法，如A*，D*，稀疏D*。由于它们有效的启发函数和动态数据更新而被广泛应用。D*已经被证明效率更高于A*，而稀疏D*在某些方面效率要高于D*。D*和稀疏D*都保证了最优路径并且是动态的算法，并且都适用于导航规划。但总体说来，稀疏D*效率要高于D*而且容易理解。但是当同时面对复杂规划和动态环境时，将稀疏D*和ARA*结合起来，得到一种更高效的算法，即AD*算法。当边缘代价和膨胀因子发生变化时， AD*都能处理。当出发点也

26、不断变化时，AD*略作修改即可适应这种情况。AD*比稀疏D*和ARA*更有优势，因为AD*仅仅在当前搜索路径或即将导致搜索路径矛盾时作出修改，这使得它效率更高。AD*在计算过程中尽可能的使用已经计算好的路径，当遇到环境改变时，适当的选择次优解，以此来提高计算速度。当环境的改变不可避免时，AD*有能力修改以往的路径。最新的试验结果证明，在启发式搜索算法这个大家庭中，AD*是一种在工程应用中十分有效的算法。在动态路网，环境如权重等不断变化的动态环境下，考虑时间等因素，在有限的时间内得到好的、可行的结果。对下面的路标图，采用Greedy Best-First 或 A*搜索从Arad到Buchares

27、t的路径，给出搜索过程结果。采用A*搜索搜索结果AradSibiuRimnicu VilceaPitestiBucharest总长度418实验代码:class A_Starprivate:int MaxWeight=10000;stack s,ss;public:void A_Search(Graph g,int v0,int vg,int H)bool flag=true;int x;:2);f=x1.2+x2.2;%优化目标函数figure(1);contour3(x1,x2,f,15);figure(2);contour(x1,x2,f,15);x2=-x1-2;%约束条件hold on

28、;plot(x1,x2,*);结果：分析：最优点为图2中等高线与约束条件投影曲线相切点，此时约束条件满足x1=-1,x2=-1;目标函数最优值为2，也即目标函数的最小值。设函数，函数的定义域为。（1）利用牛顿法计算初值分别为和的叠代序列。（2）给出牛顿法叠代的准确公式。答：（1）序列 （舍去）序列 （舍去）（2）XK+1=XK-9Xk-4ln(Xk-7).对图1最短路径问题，利用动态规划原理求从点A到点B的最短路线。图1 最短路径问题程序代码：ab=1 1 2 2 3 3 4 4 5 5 6 6 7 8 8 9 9 10 11 12 12 13 14 15;bb=2 3 4 5 5 6 7 8 8 9 9 10 11 11 12 12 13 13 14 14 15 15