障碍最短路径算法研究 - 邓俊辉 - Junhui Deng

《障碍最短路径算法研究 - 邓俊辉 - Junhui Deng》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、障碍最短路径算法研究小组成员陈康（2012311316）交叉研2班冯立新（2012210914）计研123班应用背景障碍最短路径问题是图论中最短路径问题的一个自然的推广，考虑的是在有障碍情况下的最短路径问题。如工厂中机器人在工作间内如何规划运动的线路、GIS系统里地图上两点之间的最短距离、游戏设计中自动寻路、网络路由策略选择、电路板中线路设计等诸多问题都可归结为有障碍下的最短路径问题。解决这个问题可以带来非常明显经济效益和社会效益。同时这个问题是计算几何领域的古老而经典问题之一，而且与它相关的子问题，如单起始点多终止点障碍最短路径、最短链接、可见图等问题也受到了持续的关注与研究。问题定义给定在

2、平面中指定起始点pStart、终止点pEnd和N个互不相交的多边形障碍物P1，P2，…，Pn，计算起始点pStart和终止点pEnd之间的最短路径。相关工作障碍最短路径问题在计算几何领域曾经得到了广泛的研究，但是由于一直缺乏简单高效的算法，目前这个方向也逐渐冷却。在实际应用中，人们往往更愿意使用简单高效的非精确算法（如A*等），但我们这里只讨论精确算法。目前求解障碍最短路径问题有两种基本思路：一种是直接构造全局可见性图，把问题转化成无障碍图的最短路径求解问题；另外一种是通过区域分割，不断排除不可能区域，最终构造出最短路径地图。构造全局可见性图原理比较简单，但由于需要为大量不可能经过的点构造可见

3、性图，所以计算代价比较高。最短路径地图的原理比较复杂，但算法效率显著提高。当前理论上的最优算法就是基于这种思路，利用波浪线的方法对几何区域进行快速分割实现的。通过构造可见性图求解最短路径问题直观上很容易理解，一旦构造出全局的可见性图，我们就从原问题中抽象出了一幅完全图，每一条边都代表了一个可行的路径，接下来要做的就是使用图论中经典的Dijkstra算法求解最短路径。事实上构造可见性图本身就是一个相当基本的问题，包括ArtGalleryProblem在内的一系列经典问题都依赖于该问题，所以单纯对可见性图构造算法有着大量的研究[3]。构造可见性图的一种经典的方法是旋转扫描线算法[1]，其复杂度为O

4、(n2logn)，其中n为障碍物顶点的数目。我们实现的也是这个算法，具体内容我们会在下文中仔细分析。Ghosh和Mount对该算法进行了改进[2]，使得复杂度降至O(nlogn+E)（n是顶点数，E是可见性图的边数）。它的思路是以平面扫描三角剖分形式给出了有障碍情况下可见图的构建。主要的思想是FunnelSequence（FNL）漏斗的分割和合并。漏斗可以看作覆盖所有障碍的多边形边E的两个顶点，按照顺时针或者逆时针顺序的所有可见顶点的序列，相连顶点形成的边是最靠近E的左或者右的线段。通过平面扫描的方式，新加入的多边形的边对应的新漏斗是从原多边凸内链上边的漏斗中分割得到。最后得到的就是要求的可见

5、图。同样在三维空间中也存在可见性图，但由于2维可见性图的概念并不能简单地直接推广到3维，维数升高带来的代数难度和组合难度导致三维空间的可见性图复杂度更高。Joseph[6]回顾了3维可见图的发展历程，指出了3维可见图构造的NP-hard性质。障碍最短路径的另外一种求解思路是直接在几何域上进行运算。Mitchell[4]的算法考虑了移动物体的尺寸，将整幅地图划分成大小相等的小区域，计算哪些小区域是可以通过的，最终将每一个小区域抽象成一个节点，形成一个联通图，在此基础上同样应用图论最短路径算法。算法的主要代价在于决定哪些小区域是可以通过的，该算法的时间复杂度为O(kn)，k为障碍的个数，n为障碍多

6、边形的边的个数。目前理论上的最优的算法在此基础上由Hershberger和Suri改进[5]提出，时间复杂度O(nlogn)。他们采用的是continuousDijkstra方法，也就是形象的波浪线传播方法对最短路径地图进行计算，算法通过对平面采用四叉树划分加速波浪的事件传递，对非近邻的波浪则采取近似处理从而得到最优的构造算法。但与大多数理论最优算法类似，该算法在实现上过于复杂，实用性不高。输入限定和衰退处理计算几何的很多算法之所以停留在理论阶段,除了算法本身比较复杂以外，还有一个重要的原因就是算法的通用性比较差，对各种各样的奇异情况失效。障碍最短路径的算法也是如此，虽然理论上存在O(nlog

7、n)的算法，但是在需要精确解时，比较常见的还是Lee的旋转扫描线算法。事实上，即使是旋转扫描线算法同样面临着各种各样衰退情况的困扰。在应用中求取障碍最短路径往往是使用一些近似的启发式算法（如A*）。为了算法能够更高效的处理大多数正常情况，我们对输入进行了严格的限定，主要包含以下几点：a)所有障碍物必须为简单多边形b)障碍物之间禁止重合c)源端点和目标端点不能出现在障碍物内部d)障碍物边界可以重叠，