栅格法

摘自《避障路径规划的算法》2．2．1有障碍物的环境表示合理的环境表示有利于建立规划方法和选择合适的搜索算法，最终实现较少的时间开销而规划出较为满意的路径。不同的路径规划方法正是基于不同的环境建模。图2．1给出的是一个原始的工作空间的实例。针对这个实例分析几种常用的环境表示方法。图2．2是用栅格法来表示环境。它使用大小相同的栅格划分环境空间，并用栅格数组来表示环境。每个栅格点或者在自由空间中，或者在障碍物空间中。对于混合栅格点(即一部分是自由空间另一部分是障碍物)，依据其自由空间和障碍物占有的比例，将其归属于自由空间或障碍物空间。黑格代表障碍物，在栅格数组中标为1；白格代表自由空间，在栅格数组中标为0。最短路径是通过搜索这张栅格图得到的。为了提高搜索的效率，栅格通常按粒度分成若干个层次。这种方法的特点是简单、易于实现，它同时具有表达不规则障碍物的能力。其缺点是表示效率不高，存在着时空开销与求解精度之间的矛盾。单元树法正是为了克服栅格法的缺点而设计的。这种方法同栅格法相比较，不同之处在于单元树法将环境空间划分成大小不同的单元。通常的做法是：将环境空间划分成几个较大的单元(一般来说，二维空间划分成4部分，称为四叉树；三维空间划分成8部分，成为八叉树)，如图23。划分得到的每个单元所占用的工作空间可能是下面三种情况之一：都为自由空间；都为障碍物空间；混合型空间，既包含了障碍物区域，又包含了自由区域。对于最后一种类型的单元按照前面的方法继续进行划分，直到一个预先设定好的精度为止。该方法的优点是自适应性较好。主要缺点是计算单元之间的邻接关系时的损失较大。图2．4是多边形表示法，这也是常用的方法之一。该方法用多边形来逼近障碍物，并使用了很多成熟了的诸如求交叉点和测距的解析几何算法。图2．5用CSG法来表示环境，同CAD表示部件的方法相似。图2．6所示的B—rep是用障碍物的边缘函数来表示环境的方法。应用这两种环境表示方法的路径规划算法较少。2．2．2规划方法为了解决路径规划问题，人们已探索出很多有效的求解方法。这些方法包括几何法、单元分解法、人工势场法和数学分析法等引伸出来的其它方法。路径规划领域中的很多问题都可以用这4种基本方法来解决。它们也不是互相排斥的，而常常结合起来共同地实现路径规划。下面简单的介绍一下这四种方法。2．2．2．1几何法几何法抽取的是环境的几何特征㈨。利用其几何特性将环境空间映射到一个加权(权值可以是两顶点间的几何距离)图上，这样就把避障路径规划问题转换为一个简单的图搜索问题。基于几何法的路径规划方法一般分为三步：l、在搜索图中找到起始点；2、在搜索图中找到目标点；3、把这两个点用图中的不穿过障碍物的折线(或曲线)连接起来，就得到了一条无碰路径。所构造的加权图必须能表示在环境空间中所有拓朴结构独立的不同的可行路径，否则该路径规划算法是不完备的。几何法包括：1、可视图法(VisibilityGraph)f34】f35】[361：该方法将所有障碍物的顶点(设vo是所有障碍物的顶点构成的集合)、起始点S及目标点g用直线组合相连，同时要求三者(即障碍物的顶点、起始点s及目标点g)之间连线均不能穿越障碍物，即直线是“可视的”，给图中的边赋权值，构造图GⅣE)，结点集V=VoU{s,g)，E为所有弧段(pi，n)即边集合，其中连接G中第i和第J个结点的线段与任何障碍物均不相交。因为图中相邻的顶点能相互看到，GⅣE)称为可视图。然后采用某种方法搜索从起始点S到目标点g的最优路径。规划最优路径的问题就转化为从起始点到目标点经过这些可视直线的最短距离问题。如图2．7。可视图方法是在1979年由Lozano和Wesley{”3提出的，其最大的特点是障碍物由多边形(二维空间)或多面体(三维空间)进行表达。2、Voronoi图法：出于安全等因素的考虑(如机器人路径规划中对机器人碰撞的安全性考虑)，要求规划路径与障碍物之间有一定的距离，便可使用Voronoi图法。如图2．8，该图是用一系列的节点来定义的，这些节点到附近的两个或多个障碍物的边缘是等距离的。Voronoi图把规划空间划分成若干个区域，每个区域只包含一个障碍物的边缘。对于一个区域中的任何一点，它到该区域所包含的障碍物的边缘的距离要比到工作空间中任何一个其它的障碍物的边缘都近。Voronoi图法的特点是计算速度快。Voronoi图法是由S．Kirkpatfickt381等人于1983年提出了用Retraction方法来解决平面上的路径规划问题。而后，0．Takahashi实现了该方法【391。Voronoi图法的算法原理可描述为：假设O是多边形障碍物的集合，已知平面上两点X和Y，d(x，y)表示两点问的Euclid距离。若Y是一个非空点集，则Hausdroff距离d(x，Y)定义为inf{d(x，y)：y∈Y)，若x是另一个非空点集，d(X，Y)=inf{d(x，Y)：x∈x)。对每一点X定义Clearance(x)为x到O的Hausdroff距离。假设所有障碍物之并为一闭集，用Q表示它的有界补集，由此可知对Q中任何一点X，存在某个障碍物边界上的点P，使得d(x，P)=Clearance(x)。如果定义Near(x)为O中到x中距离为最短距离Clearance(x)上点的集合，则Near(x)非空。定义2．1(标准)VoronoiDiagramV。。(O)为{Q中的x：Near(x)至少包含两点)。定义2．2对Q中每一点X，设Y为Near(x)@唯一元素，X的映象hn(x)为从Y到X的射线与VoronoiDiagram相交的第一点；对vo,o(o)3r的x，定义Im(x)---x。定理2．1映射hIl为已定义的从Q到VoronoiDiagramV。。(0)上的连续回缩(ContinuousRetraction)。进一步说，Clearance(+)在从X到hn(X)的射线上的严格递增。定理2．2从自由位置P到q存在一条路径当且仅当在V。(O)上存在一条从Un(p)到Ira(q)的路径。有关GeneralizedVoronoiDiagram(GVD)问题存在许多算法…，设n为障碍物顶点数，则算法复杂性可减少到0(n／ogn)，这为应用GVD进行路径规划提供了实用条件。3、自由空间法：把环境空间划分成两部分，即自由空间和障碍物空间。用某种搜索策略在自由空间中找到一条路径。在某些情况下，路径偏离前进目标太远；另外，规划出的路径形态复杂，因此该方法仅适用于路径精度要求不高，运动速度不快的场合。按照划分自由空间方法的不同又可分为：凸区法、三角形法、广义锥法。几何法在二维工作空间下的性能很好，但引伸到三维工作空间后，其复杂性和计算时间都会大为增加。2．2．2．2单元分解法这种方法把自由空间划分成一个由简单的单元所构成的集合，各单元之间的连续的邻接关系也同时被计算。首先标识出起始点和目标点所在的单元，再连接它们之间的连续的单元格，就得到了从起点到终点之间的一条无碰路径。单元的划分可以是依赖于障碍物的，也可以是独立于障碍物的。对于前者，障碍物的边界用于生成单元格的边界，所得自由单元的集合精确地定义自由空间，如图2．9所示。这种方法最后所得的单元格虽少，但单元分解和计算单元之间的邻接关系的开销较大。对于独立于障碍物的单元分解，环境空间被划分成一些有规则形状的单元。单元分解法是由Brooks和Lozano在1983年提出的【47】，算法的思想很简单。即将环境空间切分为单元，在所有单元中，若没有包含障碍，称为空单元，简称为E；若全部为障碍所充满，为满单元，记为F：若部分包含障碍，为混合单元，记为M。把单元视为节点，其间的相邻关系用弧连接起来，得到一个网络连通图，于是寻找安全路径问题变为图的搜索。单元分解法的典型特征是划分空间与搜索是交叉进行的。该方法对高维情况，计算量大。由于单元的形状和位置独立于障碍物的形状和位置，这种方法不一定能精确在表示障碍物。然而这种表示的误差可以通过增加单元的数量，即提高划分精度的办法来解决。独立于障碍物的单元分解法的例子如2．2．1中所述的栅格法、单元树法。