《典型航路规划方法的基本原理例题展示44135.pdf》由会员分享，可在线阅读，更多相关《典型航路规划方法的基本原理例题展示44135.pdf（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 1 1.简要论述典型航路规划方法的基本原理（任选方法之一，且选择该方法中的一种具体方法。）并举例说明。（1）路标图法；（2）单元分解方法；（3）人工势场法 答：选择（1）路标图法。概略图(Skeleton)也称路标图(Roadmap)。在基于概略图空间的路径规划方法中，首先根据一定的规则将自由的 C 空间（Configuration Space)表示成一个由维的线段构成的网络图，然后采用某一搜索算法在该网络图上进行航迹搜索。这样，规划问题被转化为一个网络图的搜索问题。概略图必须表示出 C 空间中的所有可能的路径，否则该方法就是不完全的，即可能丢失最优解。常用的概略图方法包括通视图法(Visi
2、bility Graph)、Voronoi 图法、轮廓图法(Silhouette)、子目标网络法(Subgoal Network)和随机路线图法(Probabilistic Roadmap,PRM)。通视图法 通视图由规划空间中的障碍物的相互可见的顶点间的连线构成。图 1-1 给出了包含三个多边形障碍物的二维规划空间的通视图，其中较粗的线表示起始点 S和目标点 G 之间的一条最短路径。1989 年，Asano 等证明在具有 n 个顶点的二维规划空间中，其通视图的边数具有数量级 0(n2)，构造通视图所需时间的数量级也为 0(n2)。图 1-1 通视图 通视图法可用于求解二维规划空间中的最短路径
3、问题。尽管它也可用于高维 1 规划空间，但此时生成的路径将不再是最短的。由于通视图不能表达物体运动的方向性约束，除非运动物体可以按任何方向以任意角度转弯，通常很少用通视图法求解实际的路径规划问题。Voronoi 图法 如果运动物体要求与障碍(或威胁)的距离越远越好，可以采用 Voronoi 图方法。Voronoi 图由与两个或多个障碍(或威胁)的给定特征元素距离相等的点的集合构成。图 1-2 给出了以多边形障碍物自身作为特征元素生成的 Voronoi 图。如果以多边形的边作为特征元素则可以得到不同的 Voronoi 图。对于只包含有威胁的规划空间来说，可以将威胁源的中心点作为特征元素。Voro
4、noi 图将规划空间分为多个区域，每个区域只包含一个特征元素。对于区域中的每一点，该区域的特征元素是所有特征元素中最近的。图 1-2 Voronoi 图 与通视图比较，Voronoi 图具有明显的优点，Voronoi 图的边数只有数量级0(n)，构造 Voronoi 图所需时间的数量级为 0(nlogn),其中 n 为所选特征元素数目。如果将多边形的边作为特征元素，则 Voronoi 图一般都包含有曲线段。1987 年，Canny 和 Donald 通过使用一种不同于欧氏距离的度量方法，构造出了一种只包含直线段的 Voronoi 图。对于维数大于 2 的高维空间，通视图与 Voronoi 图将
5、变得非常复杂，而且一般没有确定的特征元素选择方法。例如，多面体间的 Voronoi 图由二维曲面构成，它不再是一维的轮廓线。尽管通视图仍然可以由多面体的各项点间的连线组成，但此时最短路径不再存在于通视图之中(如图 1-3 所示)。因此，Voronoi 1 图一般只应用于二维路径规划。图 1-3 最短路径不经过多面体的顶点 轮廓线法 对于高维空间，Canny 于 1987 年给出了另一种构造概略图的方法。该方法先将高维空间中的物体投影到一个较低维的空间中，然后在低维空间中找出其投影的边界曲线，称为轮廓。该轮廓又投影到一个更低维的空间中，如此继续下去，直到轮廓变成一维的轮廓线。对于同一障碍物其轮廓
6、不相连的部分，需用连接线将它们连接起来(如图 1-4(b)所示)。这样得到的一维轮廓线图比原始的高维空间简单得多，可以从中找到一条可行的路径。该方法通常在理论上用于分析问题的复杂性，而很少用于实际中的路径规划。使用轮廓线方法得到的路径，运动物体总是沿着障碍物边缘移动。图 1-4 轮廓线 子目标网络法 子目标网络方法不直接构造明显的概略图，而是保存一个可以从起始点达到的节点列表。如果目标点出现在该表中，则规划成功结束。规划空间中两点之间 1 的可达性由一个简单的局部规划算法来判断，该局部规划算法称为局部算子。局部算子的选择一般根据具体问题确定，例如，可以简单地在两节点之间按直线运动。开始的时候，
7、该算法在起始节点与目标点之间选取一个由称为子目标的中间节点组成的候选序列，并运用局部算子依次连接这些子目标。在选取子目标候选 序列时可以采用某些启发式信息，也可以随机选取。如果连接过程不能到达目标点，则将已经连接的子目标保存在列表中。然后任取一个已到达的子目标，并在该子目标与目标节点之间选取一个候选序列，如此反复，直至到达目标节点。在该算法中，可到达的节点间的运动路径可以由局部算子非常容易地重新得到，因此不用保存。该算法的一个主要优点是节省内存空间。通视图可以看作是一个子目标网络，其子目标为障碍物的顶点，局部算子为“直线运动”。图 1-5 显示了一个“沿对角线方向运动”的局部算子生成的子目标网
8、络。图 1-5 子目标网络 局部算子的选择确定了规划算法的实现。一种极端的情形是采用“直线运动”，但当两个节点之间的距离很远时，该方法通常很难找到可行的路径。因此，相邻的两个子目标间的距离一般很近，这势必增加子目标的数目，从而增加内存空间。另一个极端就是采用一种精确的全局规划算法作为局部算子，此时仅有一个包含有起始点和目标点的候选序列需要连接。这种方法将一个全局规划问题分解成若千个比较简单的局部规划问题。随机路线图法 随机路线图法是近年发展起来的一种针对多自由度问题的路径规划方法，由 1 Overmars 等于 1992 年率先提出。该方法通过在规划空间中随机进行采样生成路线图，然后在该路线图
9、中搜索路径。随机路线图的构造如下:如果最新的采样点与路线图中的某节点间存在可行路径，则将该采样点加入到路线图中，同时找出该节点与路线图中的近邻节点间可能存在的路径，并将可行路径作为节点间的边加入到路线图中。该方法的优点之一就是可以在规划时间和路径的质量之间进行权衡，构造随机路线图的时间越长，得到最优路径的可能性就越大。在确定环境下，随机路线图一般可以事先构造。然而，如果规划环境一日发生变化，随机路线图并不能通过局部更新以适应新的环境，因此，该算法-般不适于在线实时应用。2.简要论述航路规划启发式搜索算法 A*，.D*，anytime algorithms(ARA*)，anytime re-pl
10、anning algorithms(AD*)的特点。A*A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。和 Dijkstra一样，A*能用于搜索最短路径。和 BFS 一样，A*能用启发式函数引导它自己。它把 Dijkstra 算法（靠近初始点的结点）和 BFS 算法（靠近目标点的结点）的信息块结合起来。有点不同的是，类似 BFS 的启发式方法经常给出一个近似解而不是保证最佳解。然而，尽管 A*基于无法保证最佳解的启发式方法，A*却能保证找到一条最短路径。在讨论 A*的标准术语中，g(n)表示从初始结点到任意结点 n 的代价，h(n)表示从结点 n 到目标点的启发式评估代价（he
11、uristic estimated cost）。当从初始点向目标点移动时，A*权衡这两者。每次进行主循环时，它检查 f(n)最小的结点 n，其中 f(n)=g(n)+h(n)。保证找到最短路径（最优解的）条件，关键在于估价函数 h(n)的选取：估价值 h(n)n 到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。如果估价值实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。估价值 1 与实际值越接近，估价函数取得就越好。A*算法的搜索过程实际上是被选节点扩展的过程，它存在一种潜能，可以采用最少的估价源找到最近的优化路径。在确定优化路径后，要进行航
12、路回朔，计算是否满足任务系统中设定的燃油、时间、速度等约束条件(这些约束条件有一定的次序)。如果不能满足所有的约束条件，则计划就失败，必须重新计划并修改有关参数。启发式函数 h(n)告诉 A*从任意结点 n 到目标结点的最小代价评估值。例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即 f=g(n)+sqrt(dx-nx)*(dx-nx)+(dy-ny)*(dy-ny)；这样估价函数 f在 g 值一定的情况下，会或多或少的受估价值 h 的制约，节点距目标点近，h 值小，f 值相对就小，能保证最短路的搜索向终点的方向进行。A*算法的关键是对评价函数的定义，从找到一条最小代
13、价路径的思路出发，在计算时可以把评价函数值分为从初始节点到节点n 的代价，和从节点 n 到达目标节点的代价两个部分来进行计算和分析。估价函数的正确选取将直接关系到 A*算法的成功与否，而函数的确定却与实际情形有着密切的关系。所选择的启发式函数的好坏是很重要的。一个不恰当的启发式函数反而会减慢 A*算法，导致其产生出不好的路径来。如果启发式估值是精确的，则 A*将不会偏离最佳路径。当然，很难得到一个精确的启发式估值，但知道当给 A*一个正确的信息，它会正确地进行操作，这是非常有用的。另外，如果启发式估值趋向于精确值，则 A*搜索操作就会越少。因此，f 值的增加是与搜索的多少相关。当启发式估值是精
14、确的，则 f 将不会变化。当启发式估值低于实际值太多，f 值就会迅速地增加。启发式越好，搜索的地方就越少。当探测器检测到实际的环境和已知的环境信息存在差异时,则更新原有的环境地图信息,那么原先规划的路径也许就是不可通的或者不是最优的。此时,可以根据更新的环境信息重新规划一条从当前所在位置到目标点的新的路径,但是代价很大。据于此,Anthony Stentz 提出的动态 A*算法或者叫 D*算法。D*1 A*在静态路网中非常有效，但不适于在动态路网，环境如权重等不断变化的动态环境下。D*是动态 A*（D-Star,Dynamic A Star）。相对于 A*算法，D*算法的主要特点是可以应用于环
15、境仅为部分已知或环境不断变化的情况下的路径寻优。该算法根据当前已知环境状况沿最有启发性的节点搜索，如探测到下一节点将会发生阻塞，则适时调整估价函数，改变方向继续搜索，从而最终得到整个路径。D*算法弥补了 A*算法必须事先知道全部环境信息的缺点，且具有与 A*算法一样的高效特征。在环境信息是静态的时候，D*的搜索方法和 Dijkstra 算法的搜索过程是一样的。D*算法的主要过程分为离线和在线两个部分。离线部分主要是指在已有的部分环境信息下规划出一条机器人的行进路径;而在线部分主要指移动机器人在沿着离线部分规划出的路径行进，当遇到和己知的部分环境不相同的情况或者说接受到新的环境信息的时候，重新规
16、划一条从机器人当前位置到目标的路径的过程。D*算法的作用相当于静态情况下，信息完全己知的情况下的路径规划算法。此时它的执行过程和 Dijksart 搜索算法相同，在离线情况下，基本的 D*算法的效能是不及 A*算法的。但是，A*算法利用启发信息限制了搜索扩展到的状态，而其中一些没有扩展到的状态很有可能是在后面的在线规划中所需要用到的，因而 D*必须使用这种离线的规划方法。对于在线规划部分，此时算法的执行时间和很多因素直接相关，比如，预先己知的环境信息量，实际环境中障碍物密度，机器人环境传感器感知范围等。因此根前面的一般的重规划方法相比，在相同的障碍物密度，相同的已知部分信息量，相同的感知范围情
17、况下，D*算法所重新规划的环境中的状态只是环境中的一部分，而一般的重规划策略则需要在整个更新的环境中重新规划。从这一点来说，该算法是很有优势的。并且随着环境大小的增加，算法比普通的最优重规划方法所节约的时间也成倍的增加。环境信息部分未知的情况下全局规划部分很明显需要一个重规划的过程。这里的重规划是指当遇到已知环境与原有实际环境存在差异时，使得原有的全局规划路径无法通过而必须重新进行的规划。按照重规划与原规划的起点相同与否可以划分为完全重规划与不完全重规划。所谓完全重规划，是指重规划路径的起点与原规划的起点相同，而不完全重规划或部分重规划则是指重规划路径的起点与 1 原规划的起点不同。动态的 D
18、*算法是不完全的重规划，但是利用了原有的规划信息，在一定程度上实现了最优性和实时性的结合。D*算法做到全局规划和局部信息相结合、离线的规划和在线的规划相结合。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.机器人沿最短路开始移动，在移动的下一节点没有变化时，无需计算，利用
19、上一步 Dijstra 计算出的最短路信息从出发点向后追述即可，当在 Y 点探测 到下一节点 X 状态发生改变，如堵塞。机器人首先调整自己在当前位置 Y 到目标点 G 的实际值 h(Y)，h(Y)=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*算法在
20、动态环境中寻路非常有效，向目标点移动中，只检查最短路径上下一节点或临近节点的变化情况，如机器人寻路等情况。对于距离远的最短路径上发生的变化，则感觉不太适用。anytime algorithms(ARA*)在很多情况下，最短路径不一定就是我们想要的，还需要考虑时间等因素。在有限的时间内得到好的、可行的结果才是我们想要的。ARA*算法就是解决这类问题的。Anytime 算法是 80 年代末期 Dean 和 Boddy 在关于时间依赖规划(Time-dependent planning)研究中提出的，其核心思想是使解的质量随计算时间的增加而不断提高。它具有在求解质量和求解时间之间折中的能力，被广泛应
21、用于时间约束条件下复杂问题的近寸以求解。同时也提出了一种问题元级控制的方法，使得智能系统具有高层调度的能力，且扩充了传统算法的输入一处理一输 1 出的计算过程，提供了运行中动态输出结果的功能。Anytime 算法把每一组输入和特定的计算时间映射为一组输出结果，这一特征使得该算法可以在任何时候被中断，返回特定质量的解，因此被称为 Anytime 算法。从某种意义上说，具有如下特征的近以算法都可以称为 Anytime 算法:1.在算法执行的任何时候都能给出问题的一个解;2.解质量随计算时间的增加而提高。可以看出 Anytime 算法是一个逐步求精的过程。在这一点上，许多现有的算法都可视为 Anyt
22、ime 算法。如:计算方法中的迭代算法、迭代加深的启发式搜索算法、各种贪心算法、利用随机原理的蒙特卡岁方法、遗传算法。这些传统的Anytime算法是被动式的，缺乏完善的元级调度机制。研究者公认，作为完善的Anytime算法，还应该具有如下特征:1.质量的度量Anytime算法用多值度量模型代替了传统的二值度量模型，因此解的质量是可以度量的;它反映了近似解和真实解的质量差距。2.可预言性Anytime算法本身包含许多关于输入、执行时间和解质量映射关系的统计信息，侠得算法可预言在一定计算时间内输出解的质量，以便做高层的调度和控制。3.单调性 Anytime算法具有解质量随执行时间增加而单调增加的特
23、性。这一点是以解质量可以度量为前提的。只有这样，Anytime 算法才能随计算时间的增加返回一个质量更好的解，而不仅是最新产生的解。4.递减性 Anytime 算法的解质量在运行的早期提高较快，随着计算时间的增加，解质量提高的速率会逐渐减小。中断及可恢复性是 Anytime 算法最本质的特性。它能在运洲于的任何时候停止，同时也能够恢复执行，且利用 Anytime 算法的系统能够在运行中重新分配计算资源。anytime algorithms(ARA*)算法在每次搜索中,根据新的因子的值,只处理在上次处理中可能不是有效的节点。首先,根据因子0 的值通过 A*算法来搜索路径,只不过每个节点最多处理一
24、次。在某次搜索过程中,如果某个节点已经扩展过,但是由于周围于周围节点之间边的代价的改变需要再次处理时,不是将其再放入 OPEN 表中处理,而是放入 INCONS 表中,当本次搜索结束后,再将 INCONS表中的节点全部插入OPEN表中用于下次搜索。这里 INCONS表是用来保存这类已 1 扩展过但是需要再次处理的节点。这个算法在两个方面提高了每次搜索效率。首先,由于对每个节点最多只扩展一次,所以路径可以很快产生。其次,由于每次处理中,只处理在 ICONS 表中的节点,所以以前搜索的结果可以重用。因此,当因子的值在每次连续的搜索中减少时,一个相对较少计算量就可以产生新结果。在 A*算法时我们了解
25、到：f(n)=g(n)+h(n)，用 d(n)表达状态 n 到目标状态的距离，那么 h(n)的选取大致有如下三种情况：如果 h(n)d(n)，搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。当 h(n)d(n)的时候，会搜索较少的点，快速的产生一个解。ARA*算法就是用到了这一点。anytime re-planning algorithms(AD*)AD*算法就是结合了 D*算法中的一升级版 D*Lite 算法和 ARA*算法提出的一种新算法，兼顾 D*Lite 算法和 ARA*算法的优点。在 AD*算法之前已经存在了很多算法，如 A*，D*，稀疏 D*。由于它们有效的启发函数和动态数
26、据更新而被广泛应用。D*已经被证明效率更高于 A*，而稀疏 D*在某些方面效率要高于 D*。D*和稀疏 D*都保证了最优路径并且是动态的算法，并且都适用于导航规划。但总体说来，稀疏 D*效率要高于 D*而且容易理解。但是当同时面对复杂规划和动态环境时，将稀疏D*和 ARA*结合起来，得到一种更高效的算法，即 AD*算法。当边缘代价和膨胀因子发生变化时，AD*都能处理。当出发点也不断变化时，AD*略作修改即可适应这种情况。AD*比稀疏 D*和 ARA*更有优势，因为 AD*仅仅在当前搜索路径或即将导致搜索路径矛盾时作出修改，这使得它效率更高。AD*在计算过程中尽可能的使用已经计算好的路径，当遇到
27、环境改变时，适当的选择次优解，以此来提高计算速度。当环境的改变不可避免时，AD*有能力修改以往的路径。最新的试验结果证明，在启发式搜索算法这个大家庭中，AD*是一种在工程应用中十分有效的算法。1 在动态路网，环境如权重等不断变化的动态环境下，考虑时间等因素，在有限的时间内得到好的、可行的结果。3.对下面的路标图，采用 Greedy Best-First 或 A*搜索从 Arad 到Bucharest 的路径，给出搜索过程结果。采用 A*搜索 搜索结果 AradSibiuRimnicu VilceaPitestiBucharest 总长度 418 实验代码:class A_Star privat
28、e:int MaxWeight=10000;stack s,ss;public:void A_Search(Graph g,int v0,int vg,int H)bool flag=true;1 int x;22212121(,)100(1)F x xxxx22212121(,)100(1)F x xxxx221212(,)F x xxx1220 xx12ox 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;plot(x1,
29、x2,*);结果：1 分析：最优点为图 2 中等高线与约束条件投影曲线相切点，此时约束条件满足x1=-1,x2=-1;目标函数最优值为 2，也即目标函数的最小值。1 8.设函数()94ln(7)f xxx，函数的定义域为|7Xx x。（1）利用牛顿法计算初值分别为和的叠代序列。（2）给出牛顿法叠代的准确公式。答：（1）序列 （舍去）序列 （舍去）（2）XK+1=XK-9Xk4ln(Xk7)(9Xk67)/(Xk7)10.对图 1 最短路径问题，利用动态规划原理求从点 A 到点 B 的最短路线。图 1 最短路径问题 程序代码：ab=1 1 2 2 3 3 4 4 5 5 6 6 7 8 8 9
30、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 16 16;w=5 7 6 8 7 9 10 6 10 8 10 6 7 5 9 5 12 7 8 6 7 9 10 11;R=sparse(ab,bb,w);%得到稀疏矩阵 R(16,16)=0;1 h=view(biograph(R,ShowWeights,on);%生成图对象 d,p=graphshortestpath(R,1,16)%求出最短路径 set(p),Color,1 );%上色 edges=getedgesbynod
31、eid(h,get(p),ID);set(edges,LineColor,1 0 0);%上色 程序运行结果：d=40 p=1 2 4 8 11 14 16 最短路径如下图所示：Node1 为 A 点，Node16 为 B 点。红色标出路径为最短路径，长度 d=40。11.设惯性坐标系矢量3RR的导数为R，其角速度为，分别表示为：xyz R，xyz R，xyz 已知R、R，证明：1（1）221xyzyzyzzxzxRRxyxyRR，其中222Rxyz（2）设惯性坐标系角速度矢量的欧拉角分别为yq（方位角）和pq（高低角），给出pq和yq与分量的关系式。备注：（1）矢量叉积满足 ijkyzyzx
32、yzzxzxxyzxyxyRR（2）任一矢量可表示为 RRRu 解：证明：（1）由RRRu可知 R=RRu+RRu 其中222Rxyz 用R叉乘式可得 RR=RRRu+RRRu 又由RRRu可知，式可化为 RR=RRuRRu+RRuRRu 代入=RuRu，RuRu=0 式可写为 RR=2RRuRu=2R 即：1 221xyzyzyzzxzxRRxyxyRR 得证。（2）由题意：xyz R，xyz R，xyz 则有：tanyxqarcz 222sinpyqarcxyz 对求导得：22yxzxzqxz 2222222()()pyy xxyyzzqxzxyzxz 又2yzxzxR，将22cospxz
33、qR代入得:2cosyypqq 1 可以化简为 22222()()()px xyyxz zyyzqxyzxz 代入2xyzyzR，2zxyxyR，另有 22sinyxqxz，22cosyzqxz，则：sincospzyxyqqq 15.在惯性坐标系，飞行器运动状态方程为 xxxxVVau 选择指标函数2211220()ftffJa x txu dt，其中ft固定，a为常数。求u使得J最小。解：根据题意可知，,fta及fx均为常数，设00(0),(0)xxx VV。令,TxXx V，则状态方程可表示为 .(,)Xf X u t。指标函数可表示为：22112200()(),(),(),ffttff
34、ffJa x txu dtx ttL X tu tt dt 构造哈密顿函数：2121(),(),(,)2TxHL X t u t tf X u tuVu 由最优控制理论可得，状态方程为.(,)Xf X u t，即 xxxxVVau (1)伴随方程为Hx，即 1210 (2)1 控制方程为0Hu，即 20u (3)横截条件为()|fft ttx，即 12()()()0ffffta x txt (4)由(2)可得，11212cctc，其中，12,c c均为待定常数。由(3)可得，12uctc。由(1)可得，3212342123116212xxctc tc tcVctc tc，其中34,c c均为待定常数。由假设00(0),(0)xxx VV可知，3040,cV cx。由(4)可得，3211123421211()()()620()ffffffffcta x txactc tc tctctc，解得 所以，能使 J 达到最小的控制输入为：0000*1233()()111133fffffa V txa V tx tuctctatat 00130023()113()113fffffa V txcata V tx tcat