资源描述：
《基于拓扑的路径规划问题的图形解法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、机器夕珍90年基于拓扑的路径规划问题的图形解法艾海舟张孩(清华大学计算机系,北京).摘:要本文提出一个解决基于拓扑的路径规划问题的新途径图形法介绍一个用图形法建立起来的适合于矩形形状的移动机器人在以线段和回弧为边界的障碍物环境下运动的路径规划算法.该算法考虑了环境发生局部变化时在不改变或者仅仅对拓扑网络进行局部修改后进行路径规划的间题.图形法比较普遍地解决了二维拓扑路径规划算法的实现问题.,,..:关键词路径规划拓扑算法图形法移动机器人1引言,〔”在解决路径规划间题的两种方法即几何法和拓扑法中几何法由于没
2、有考虑环境的拓扑特征,因而搜索空间是相当庞大的,需要比较复杂的搜索策略,而且这种方法一般没有考虑移动物体的几何特点,在解决方向因素很重要的路径规划问题时,如一个杆状物的路径规划问题,有一定的局限性.拓扑法,是针对几何法的这一局限性提出来的它根据环境和运动物体的几何特,,,点将组成空间划分成若干拓扑特征一致的子区域根据彼此的连通性建立一个拓扑网在该图中搜索一条拓扑路径.这种方法的优点在于利用拓扑特征大大缩小了搜索空间,其算法复杂性仅,、,仅依赖于障碍物的数目在理论上是完备的;缺点在于表示的复杂性特殊性建立拓
3、扑网的过,比较难以实现.,,程是相当复杂而费时的但是针对一种环境拓扑网只需建立一次因而在实际中能,。大大提高效率显示其优越性.,本算法是针对矩形形状的移动机器人设计的对于长L宽甲的移动机器人我们通过将障碍物扩展甲/.2的方式把问题简化成一个长L的杆在扩展后的环境中运动的路径规划问题2理论基础拓扑法的基本理论是降维法,即将在高维九何空间中求路径的问题转化为低维拓扑空间中判别连通性的问题.在[21、[3]中有详细的阐述,这里不再赘述,只引用其基本结论以便于理解.·杆的运动是用其一端点尸的平移及其绕该点的旋转角
4、度来表示的.杆的每个状态用p点的=,.坐标x(x,y)及其方向角q来表示即(X,q)定义:旋转映射图(RMG):图G(月=f(x,F(刀):x,,,尸,.〔D}x是尸点的坐标D是x的定义域月刀是点的无碰方向角的集合即方向分支,定理:设G(月是杆A在障碍物环境中的旋转映射图RMG给定一个起始状态S和一个目,.标状态G从S到G存在无碰路的充分必要条件是S和G属于G(月某个连通支这样路径求解问题在拓扑空间中就转化成了图G(月的连通性问题.3拓扑空间拓扑空间的复杂程度取决于环境的复杂程度.对于一般形式的环境,几乎
5、无法建立这一空问,因而适当地简化环境中的障碍物的边界形状是必要的.这里考虑的是以线段和圆弧为边界的,.障碍物环境因为比较容易生成这种环境的扩展边界拓扑空间是借助于图形方法建立起来的.通过一些简单的过程,诸如在屏幕上描述边界,扫,,.描图象以及边界跟踪等用图解法建立拓扑网避开了几何表示与计算的复杂性3.1方向分OB)支(,;对于一个长度为的杆它在任意一点P的方向分支是指当杆绕该点旋转时扫描过的无碰,.方向角的集合如图2所示12R一扩展边界一;,.R扩展边界是指将障碍边界向自由空间扩展长度后得到的边界如图1所
6、示生成扩展收到本文的时jhl是1989年11月25日.12卷5期基于拓扑的路径规划间题的图形解法边界是图形解法的基础.生成扩展边界的复杂性限制了拓扑方法应用的环境范围.3。3分割、R,以原来的边界一扩展边界以及它们之间的支撑线段为边缘整个平面空间被分割成若干,,.子区域每个子区域的内部点具有相同的方向分支结构即具有相同的拓扑特征这些子区域又,,.,可以划分为两类一类是无碰子区域另一类是可碰子区域在无碰子区域中移动机器人可以,,.当成点来处理;而在可碰子区域中它只能作为杆来处理如图2所示这里的分割方法有别于
7、,,,原理论中的划分原则引人了支撑线段概念使得每个子区域中的点不仅具有相同的拓扑特征而且具有相似的几何特征.在这种分割下,我们不再考虑原理中的消失线在划分中的作用问题,从而避开了拓扑方法的另一难点.,用图形法实现分割是通过扫描环境空间逐个跟踪每个子空间的边界并且记录其中的任意一点以计算其方向分支结构的过程进行的.3.4特征网络(拓扑网络),,:区域结点经过分割每个子区域对应于旋转映射图的一种方向分支结构记作.,,=(o刀D认DF(t)一般而言F(户可以是若干方向分支的并集即F(D‘)一F,:)FZ(D,)
8、⋯F,(D‘)(DUUU一oBI‘)oBZ‘)⋯oB.(D,)(DU(DUU..,·,:区域=i’D因此它可以表示成若干个区域分支集合的并集记作分支结点心(D习t)=认U吓特征网络是根据如下规划建立起来的.对于两个不同的区域结点,,,U‘一y‘,一(D‘F、(D,))(D,FZ(D‘))⋯U(D,F.(D‘))UUU**,,,..2*,,..U一U犷一(DF(D))U(D尸(D))U⋯U(DF(D))·*D,和。D两个区域分支
