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

1.简要论述典型航路规划方法的基本原理（任选方法之一，且选择该方法中的一种具体方法。）并举例说明。（1）路标图法；（2）单元分解方法；（3）人工势场法答：选择（1）路标图法。概略图(Skeleton)也称路标图(Roadmap)。在基于概略图空间的路径规划方法中，首先根据一定的规则将自由的C空间（ConfigurationSpace)表示成一个由维的线段构成的网络图，然后采用某一搜索算法在该网络图上进行航迹搜索。这样，规划问题被转化为一个网络图的搜索问题。概略图必须表示出C空间中的所有可能的路径，否则该方法就是不完全的，即可能丢失最优解。常用的概略图方法包括通视图法(VisibilityGraph)、Voronoi图法、轮廓图法(Silhouette)、子目标网络法(SubgoalNetwork)和随机路线图法(ProbabilisticRoadmap,PRM)。①通视图法通视图由规划空间中的障碍物的相互可见的顶点间的连线构成。图1-1给出了包含三个多边形障碍物的二维规划空间的通视图，其中较粗的线表示起始点S和目标点G之间的一条最短路径。1989年，Asano等证明在具有n个顶点的二维规划空间中，其通视图的边数具有数量级0(n2)，构造通视图所需时间的数量级也为0(n2)。图1-1通视图通视图法可用于求解二维规划空间中的最短路径问题。尽管它也可用于高维规划空间，但此时生成的路径将不再是最短的。由于通视图不能表达物体运动的方向性约束，除非运动物体可以按任何方向以任意角度转弯，通常很少用通视图法求解实际的路径规划问题。②Voronoi图法如果运动物体要求与障碍(或威胁)的距离越远越好，可以采用Voronoi图方法。Voronoi图由与两个或多个障碍(或威胁)的给定特征元素距离相等的点的集合构成。图1-2给出了以多边形障碍物自身作为特征元素生成的Voronoi图。如果以多边形的边作为特征元素则可以得到不同的Voronoi图。对于只包含有威胁的规划空间来说，可以将威胁源的中心点作为特征元素。Voronoi图将规划空间分为多个区域，每个区域只包含一个特征元素。对于区域中的每一点，该区域的特征元素是所有特征元素中最近的。图1-2Voronoi图与通视图比较，Voronoi图具有明显的优点，Voronoi图的边数只有数量级0(n)，构造Voronoi图所需时间的数量级为0(nlogn),其中n为所选特征元素数目。如果将多边形的边作为特征元素，则Voronoi图一般都包含有曲线段。1987年，Canny和Donald通过使用一种不同于欧氏距离的度量方法，构造出了一种只包含直线段的Voronoi图。对于维数大于2的高维空间，通视图与Voronoi图将变得非常复杂，而且一般没有确定的特征元素选择方法。例如，多面体间的Voronoi图由二维曲面构成，它不再是一维的轮廓线。尽管通视图仍然可以由多面体的各项点间的连线组成，但此时最短路径不再存在于通视图之中(如图1-3所示)。因此，Voronoi图一般只应用于二维路径规划。图1-3最短路径不经过多面体的顶点③轮廓线法对于高维空间，Canny于1987年给出了另一种构造概略图的方法。该方法先将高维空间中的物体投影到一个较低维的空间中，然后在低维空间中找出其投影的边界曲线，称为轮廓。该轮廓又投影到一个更低维的空间中，如此继续下去，直到轮廓变成一维的轮廓线。对于同一障碍物其轮廓不相连的部分，需用连接线将它们连接起来(如图1-4(b)所示)。这样得到的一维轮廓线图比原始的高维空间简单得多，可以从中找到一条可行的路径。该方法通常在理论上用于分析问题的复杂性，而很少用于实际中的路径规划。使用轮廓线方法得到的路径，运动物体总是沿着障碍物边缘移动。图1-4轮廓线④子目标网络法子目标网络方法不直接构造明显的概略图，而是保存一个可以从起始点达到的节点列表。如果目标点出现在该表中，则规划成功结束。规划空间中两点之间的可达性由一个简单的局部规划算法来判断，该局部规划算法称为局部算子。局部算子的选择一般根据具体问题确定，例如，可以简单地在两节点之间按直线运动。开始的时候，该算法在起始节点与目标点之间选取一个由称为子目标的中间节点组成的候选序列，并运用局部算子依次连接这些子目标。在选取子目标候选序列时可以采用某些启发式信息，也可以随机选取。如果连接过程不能到达目标点，则将已经连接的子目标保存在列表中。然后任取一个已到达的子目标，并在该子目标与目标节点之间选取一个候选序列，如此反复，直至到达目标节点。在该算法中，可到达的节点间的运动路径可以由局部算子非常容易地重新得到，因此不用保存。该算法的一个主要优点是节省内存空间。通视图可以看作是一个子目标网络，其子目标为障碍物的顶点，局部算子为“直线运动”。图1-5显示了一个“沿对角线方向运动”的局部算子生成的子目标网络。图1-5子目标网络局部算子的选择确定了规划算法的实现。一种极端的情形是采用“直线运动”，但当两个节点之间的距离很远时，该方法通常很难找到可行的路径。因此，相邻的两个子目标间的距离一般很近，这势必增加子目标的数目，从而增加内存空间。另一个极端就是采用一种精确的全局规划算法作为局部算子，此时仅有一个包含有起始点和目标点的候选序列需要连接。这种方法将一个全局规划问题分解成若千个比较简单的局部规划问题。⑤随机路线图法随机路线图法是近年发展起来的一种针对多自由度问题的路径规划方法，由Overmars等于1992年率先提出。该方法通过在规划空间中随机进行采样生成路线图，然后在该路线图中搜索路径。随机路线图的构造如下:如果最新的采样点与路线图中的某节点间存在可行路径，则将该采样点加入到路线图中，同时找出该节点与路线图中的近邻节点间可能存在的路径，并将可行路径作为节点间的边加入到路线图中。该方法的优点之一就是可以在规划时间和路径的质量之间进行权衡，构造随机路线图的时间越长，得到最优路径的可能性就越大。在确定环境下，随机路线图一般可以事先构造。然而，如果规划环境一日发生变化，随机路线图并不能通过局部更新以适应新的环境，因此，该算法-般不适于在线实时应用。2.简要论述航路规划启发式搜索算法A*，.D*，anytimealgorithms(ARA*)，anytimere-planningalgorithms(AD*)的特点。A*A*（A-Star)算法是一种静态路网中求解最短路最有效的方法。和Dijkstra一样，A*能用于搜索最短路径。和BFS一样，A*能用启发式函数引导它自己。它把Dijkstra算法（靠近初始点的结点）和BFS算法（靠近目标点的结点）的信息块结合起来。有点不同的是，类似BFS的启发式方法经常给出一个近似解而不是保证最佳解。然而，尽管A*基于无法保证最佳解的启发式方法，A*却能保证找到一条最短路径。在讨论A*的标准术语中，g(n)表示从初始结点到任意结点n的代价，h(n)表示从结点n到目标点的启发式评估代价（heuristicestimatedcost）。当从初始点向目标点移动时，A*权衡这两者。每次进行主循环时，它检查f(n)最小的结点n，其中f(n)=g(n)+h(n)。保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：估价值h(n)≤n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。如果估价值实际值,搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。估价值与实际值越接近，估价函数取得就越好。A*算法的搜索过程实际上是被选节点扩展的过程，它存在一种潜能，可以采用最少的估价源找到最近的优化路径。在确定优化路径后，要进行航路回朔，计算是否满足任务系统中设定的燃油、时间、速度等约束条件(这些约束条件有一定的次序)。如果不能满足所有的约束条件，则计划就失败，必须重新计划并修改有关参数。启发式函数h(n)告诉A*从任意结点n到目标结点的最小代价评估值。例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。A*算法的关键是对评价函数的定义，从找到一条最小代价路径的思路出发，在计算时可以把评价函数值分为从初始节点到节点n的代价，和从节点n到达目标节点的代价两个部分来进行计算和分析。估价函数的正确选取将直接关系到A*算法的成功与否，而函数的确定却与实际情形有着密切的关系。所选择的启发式函数的好坏是很重要的。一个不恰当的启发式函数反而会减慢A*算法，导致其产生出不好的路径来。如果启发式估值是精确的，则A*将不会偏离最佳路径。当然，很难得到一个精确的启发式估值，但知道当给A*一个正确的信息，它会正确地进行操作，这是非常有用的。另外，如果启发式估值趋向于精确值，则A*搜索操作就会越少。因此，f值的增加是与搜索的多少相关。当启发式估值是精确的，则f将不会变化。当启发式估值低于实际值太多，f值就会迅速地增加。启发式越好，搜索的地方就越少。当探测器检测到实际的环境和已知的环境信息存在差异时,则更新原有的环境地图信息,那么原先规划的路径也许就是不可通的或者不是最优的。此时,可以根据更新的环境信息重新规划一条从当前所在位置到目标点的新的路径,但是代价很大。据于此,AnthonyStentz提出的动态A*算法或者叫D*算法。D*A*在静态路网中非常有效，但不适于在动态路网，环境如权重等不断变化的动态环境下。D*是动态A*（D-Star,DynamicAStar）。相对于A*算法，D*算法的主要特点是可以应用于环境仅为部分已知或环境不断变化的情况下的路径寻优。该算法根据当前已知环境状况沿最有启发性的节点搜索，如探测到下一节点将会发生阻塞，则适时调整估价函数，改变方向继续搜索，从而最终得到整个路径。D*算法弥补了A*算法必须事先知道全部环境信息的缺点，且具有与A*算法一样的高效特征。在环境信息是静态的时候，D*的搜索方法和Dijkstra算法的搜索过程是一样的。D*算法的主要过程分为离线和在线两个部分。离线部分主要是指在已有的部分环境信息下规划出一条机器人的行进路径;而在线部分主要指移动机器人在沿着离线部分规划出的路径行进，当遇到和己知的部分环境不相同的情况或者说接受到新的环境信息的时候，重新规划一条从机器人当前位置到目标的路径的过程。D*算法的作用相当于静态情况下，信息完全己知的情况下的路径规划算法。此时它的执行过程和Dijksart搜索算法相同，在离线情况下，基本的D*算法的效能是不及A*算法的。但是，A*算法利用启发信息限制了搜索扩展到的状态，而其中一些没有扩展到的状态很有可能是在后面的在线规划中所需要用到的，因而D*必须使用这种离线的规划方法。对于在线规划部分，此时算法的执行时间和很多因素直接相关，比如，预先己知的环境信息量，实际环境中障碍物密度，机器人环境传感器感知范围等。因此根前面的一般的重规划方法相比，在相同的障碍物密度，相同的已知部分信息量，相同的感知范围情况下，D*算法所重新规划的环境中的状态只是环境中的一部分，而一般的重规划策略则需要在整个更新的环境中重新规划。从这一点来说，该算法是很有优势的。并且随着环境大小的增加，算法比普通的最优重规划方法所节约的时间也成倍的增加。环境信息部分未知的情况下全局规划部分很明显需要一个重规划的过程。这里的重规划是指当遇到已知环境与原有实际环境存在差异时，使得原有的全局规划路径无法通过而必须重新进行的规划。按照重规划与原规划的起点相同与否可以划分为完全重规划与不完全重规划。所谓完全重规划，是指重规划路径的起点与原规划的起点相同，而不完全重规划或部分重规划则是指重规划路径的起点与原规划的起点不同。动态的D*算法是不完全的重规划，但是利用了原有的规划信息，在一定程度上实现了最优性和实时性的结合。D*算法做到全局规划和局部信息相结合、离线的规划