《障碍最短路径算法研究 - 邓俊辉 - junhui deng》由会员分享，可在线阅读，更多相关《障碍最短路径算法研究 - 邓俊辉 - junhui deng（21页珍藏版）》请在金锄头文库上搜索。
1、障碍最短路径算法研究 小组成员 陈 康 （2012311316）交叉研 2 班 冯立新 （2012210914）计研 123 班 应用背景 障碍最短路径问题是图论中最短路径问题的一个自然的推广，考虑的是在有 障碍情况下的最短路径问题。如工厂中机器人在工作间内如何规划运动的线路、 GIS 系统里地图上两点之间的最短距离、游戏设计中自动寻路、网络路由策略选 择、 电路板中线路设计等诸多问题都可归结为有障碍下的最短路径问题。解决这 个问题可以带来非常明显经济效益和社会效益。 同时这个问题是计算几何领域的 古老而经典问题之一，而且与它相关的子问题，如单起始点多终止点障碍最短路 径、最短链接、可见图等问
2、题也受到了持续的关注与研究。 问题定义 给定在平面中指定起始点 pStart、终止点 pEnd 和 N 个互不相交的多边形 障碍物 P1，P2，Pn，计算起始点 pStart 和终止点 pEnd 之间的最短路径。 相关工作 障碍最短路径问题在计算几何领域曾经得到了广泛的研究，但是由于一直缺 乏简单高效的算法，目前这个方向也逐渐冷却。在实际应用中，人们往往更愿意 使用简单高效的非精确算法（如 A*等） ，但我们这里只讨论精确算法。 目前求解障碍最短路径问题有两种基本思路：一种是直接构造全局可见性图， 把问题转化成无障碍图的最短路径求解问题；另外一种是通过区域分割，不断排 除不可能区域，最终构造出
3、最短路径地图。构造全局可见性图原理比较简单，但 由于需要为大量不可能经过的点构造可见性图，所以计算代价比较高。最短路径 地图的原理比较复杂，但算法效率显著提高。当前理论上的最优算法就是基于这 种思路，利用波浪线的方法对几何区域进行快速分割实现的。 通过构造可见性图求解最短路径问题直观上很容易理解，一旦构造出全局的 可见性图， 我们就从原问题中抽象出了一幅完全图， 每一条边都代表了一个可行 的路径，接下来要做的就是使用图论中经典的 Dijkstra 算法求解最短路径。事 实上构造可见性图本身就是一个相当基本的问题， 包括 Art Gallery Problem 在 内的一系列经典问题都依赖于该问
4、题， 所以单纯对可见性图构造算法有着大量的 研究3。 构造可见性图的一种经典的方法是旋转扫描线算法1，其复杂度为 O(n2logn)，其中 n 为障碍物顶点的数目。我们实现的也是这个算法，具体内容 我们会在下文中仔细分析。Ghosh 和 Mount 对该算法进行了改进2，使得复 杂度降至 O(nlogn+E)（n 是顶点数，E 是可见性图的边数） 。它的思路是以平面 扫描三角剖分形式给出了有障碍情况下可见图的构建。主要的思想是 Funnel Sequence（FNL）漏斗的分割和合并。漏斗可以看作覆盖所有障碍的多边形边 E 的两个顶点，按照顺时针或者逆时针顺序的所有可见顶点的序列，相连顶点形
5、成的边是最靠近 E 的左或者右的线段。 通过平面扫描的方式， 新加入的多边形的 边对应的新漏斗是从原多边凸内链上边的漏斗中分割得到。 最后得到的就是要求 的可见图。 同样在三维空间中也存在可见性图， 但由于 2 维可见性图的概念并不能简单 地直接推广到 3 维， 维数升高带来的代数难度和组合难度导致三维空间的可见性 图复杂度更高。Joseph 6回顾了 3 维可见图的发展历程，指出了 3 维可见图构 造的 NP-hard 性质。 障碍最短路径的另外一种求解思路是直接在几何域上进行运算。 Mitchell4 的算法考虑了移动物体的尺寸，将整幅地图划分成大小相等的小区域，计算哪些 小区域是可以通过
6、的，最终将每一个小区域抽象成一个节点，形成一个联通图， 在此基础上同样应用图论最短路径算法。 算法的主要代价在于决定哪些小区域是 可以通过的，该算法的时间复杂度为 O(kn)，k 为障碍的个数，n 为障碍多边形 的边的个数。目前理论上的最优的算法在此基础上由 Hershberger 和 Suri 改进 5 提出， 时间复杂度 O(nlogn)。他们采用的是 continuous Dijkstra 方法， 也就是形象的波浪线传播方法对最短路径地图进行计算， 算法通过对平面采用四 叉树划分加速波浪的事件传递， 对非近邻的波浪则采取近似处理从而得到最优的 构造算法。但与大多数理论最优算法类似，该算法
7、在实现上过于复杂，实用性不 高。 输入限定和衰退处理 计算几何的很多算法之所以停留在理论阶段,除了算法本身比较复杂以外， 还 有一个重要的原因就是算法的通用性比较差，对各种各样的奇异情况失效。 障碍 最短路径的算法也是如此，虽然理论上存在 O(nlogn)的算法，但是在需要精确 解时，比较常见的还是 Lee 的旋转扫描线算法。事实上，即使是旋转扫描线算 法同样面临着各种各样衰退情况的困扰。 在应用中求取障碍最短路径往往是使用 一些近似的启发式算法（如 A*） 。为了算法能够更高效的处理大多数正常情况， 我们对输入进行了严格的限定，主要包含以下几点： a) 所有障碍物必须为简单多边形 b) 障碍
8、物之间禁止重合 c) 源端点和目标端点不能出现在障碍物内部 d) 障碍物边界可以重叠，但只能有顶点重叠，边之间禁止重叠 前三个限定直观上是比较可以理解的，这里重点说明下第四个限定。这个限 定并不是算法必须的，也可以作为一种特殊情况进行处理，但是为了处理这个情 况， 我们不得不在一个基础的底层操作上加上很多判断， 导致算法整体性能下降。 权衡之后，我们决定将这种情况交给用户来处理，处理方法其实比较简单，比如 上图中左边的三个障碍物存在边相交的情况， 那么可以直接将这三个障碍物合并 成一个。 在这样的限定下，只可能出现三种衰退： a) 障碍物交与定点处（下图左） b) 源端点或目的端点于障碍物边界
9、相交（下图中） c) 一个障碍物的端点与另一个障碍物交与非断点处（下图右） 对于前两种情况， 我们在算法中进行了判断。 第三种情况我们同样交给用户， 如果用户发现存在这种情况，那么我们会在预处理中检测到交点，然后为相关障 碍物插入一些顶点 （如上面的情况，我们会为中间的矩形障碍物两边各插入一个 顶点） 。这样处理并不影响障碍物的形状，但是我们就可以在一个统一的框架下 处理所有的输入。 算法实现 主体思路 我们实现的是旋转式平面扫描算法，其核心思路就是对一组输入（源端点、 目的端点和一堆不相交的障碍物）首先构造可见性图，然后在可见性图的基础上 应用 Dijkstra 最短路径算法求解最短路径。
10、这算法主要基于一个事实：只要源端点和目的端点之间不直接可见，那么最 短路径一定沿着障碍物的边缘前进。对这个事实有一个比较直观的解释，假设源 端点和目的端点之间有一条路径，我们沿着这条路径放一根拉伸的橡皮筋， 橡皮 筋一定会收缩向障碍物的边缘，得到一条更短的路径。因此只需确定最短路径经 过哪些障碍物的顶点，问题也就可以做下面的抽象： 给定一幅图 Gvis，其定顶点是源端点，目的端点以及障碍物的所有端点，顶 点 Va, Vb如果直接可见，那么 Va, Vb之间就添加一条边，其权重是 Va, Vb的欧 式距离。这幅图就是可见性图，源端点跟目的端点在这幅图上的最短路径就是其 在原问题下的最短路径。 可
11、见性图 可见性图的构造是这个算法的核心部分，也是算法整体复杂度的主要来源。 构造方式简单的说就是对每一个顶点，确定所有跟其可见的顶点， 决定可见性图 上的边。暴力方法，在确定两个顶点是否可见时，需要遍历所有障碍物的边，判 断是否有遮挡，这样构造一个顶点的可见性图就需要 O(n2)的复杂度，整体复杂 度将达到 O(n3)。但采用了旋转扫描算法后，构造一个顶点的可见性图，复杂性 可以降到 O(nlogn),整体复杂性为 O(n2logn)。 Algorithm VISIBILITYGRAPH(S) Input: A set S of disjoint polygonal obstacles. Ou
12、tput: The visibility graph Gvis(S). 1. Initialize a graph G = (V,E) where V is the set of all vertices of the polygons in S and E = . 2. for all vertices v V 3. do W VISIBLEVERTICES(v,S) 4. For every vertex w W, add the arc (v,w) to E. 5. return G. Algorithm SHORTESTPATH(S, pstart, pgoal) Input: A s
13、et S of disjoint polygonal obstacles, and two points pstart and pgoal in the free space. Output: The shortest collision-free path connecting pstart and pgoal. 1. Gvis VISIBILITYGRAPH(Spstart, pgoal) 2. Assign each arc (v,w) in Gvis a weight, which is the Euclidean length of the segment vw. 3. Use Di
14、jkstras algorithm to compute a shortest path between pstart and pgoal in Gvis. 旋转扫描 这是整个算法的关键，其思想与 平面的扫描线算法相当类似， 都是按 一定顺序处理如入数据， 扫过的点是 已经处理结束的部分， 扫描线上的点 是当前正在处理的部分， 未进入扫描 曲线的点是未处理的部分。 与常见的 水平扫描先算法不同， 这里的扫描线算法是以当前点为中心的360度旋转扫描。 该算法含义上也比较直观， 相当于在原地转了一圈， 从而确定周围所有的可见点。 算法流程如下： Algorithm VISIBLEVERTICES(
15、p,S) Input: A set S of polygonal obstacles and a point p that does not lie in the interior of any obstacle. Output: The set of all obstacle vertices visible from p. 1. Sort the obstacle vertices according to the counter-clockwise angle that the halfline from p to each vertex makes with the positive
16、x-axis. In case of ties, vertices closer to p should come before vertices farther from p. Let w1, . . . ,wn be the sorted list. 2. Let be the half-line parallel to the positive x-axis starting at p. Find the obstacle edges that are properly intersected by , and store them in a balanced search tree T in the order in which they are intersected by . 3. W 4. for i1 to n 5. do if VISIBLE(wi) then Add wi toW. 6. Insert into T the obstacle edges incident to wi that
