基于同步可视图构造和a算法的全局路径规划-吕太之.pdf

《基于同步可视图构造和a算法的全局路径规划-吕太之.pdf》由会员分享，可在线阅读，更多相关《基于同步可视图构造和a算法的全局路径规划-吕太之.pdf（9页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第41卷第3期2017年6月南京理工大学学报Journal of Nanjing University of Science and TechnologyVol.41 No.3Jun.2017收稿日期:2016-05-22 修回日期:2016-10-09基金项目:国家自然科学基金(61101197);江苏省高校优秀中青年教师和校长赴境外研修项目(201121)作者简介:吕太之(1979-),男,博士生,高级工程师,主要研究方向:全局路径规划、同时定位与地图创建、机器人自主导航,E-mail:lvtaizhi163. com。引文格式:吕太之,赵春霞,夏平平.基于同步可视图构造和A算法的全局路径

2、规划J.南京理工大学学报,2017,41(3):313-321.投稿网址:http:/ / zrxuebao. njust. edu. cn基于同步可视图构造和A算法的全局路径规划吕太之1,2,赵春霞1,夏平平2(1.南京理工大学计算机科学与工程学院,江苏南京210094;2.江苏海事职业技术学院信息工程学院,江苏南京211170)摘要:为提高全局路径规划的效率,在路径搜索的过程中同步构造可视图,提出了1种新的算法。在搜索过程中,使用A算法确定待扩展的节点。根据节点状态,构造上一节点到当前节点或者当前节点到目标点的连线。如果该连线没有穿越障碍物,则将其添加到可视图中,否则将被穿越障碍物远离连线

3、的2个顶点添加到待扩展列表中。仿真结果表明,与完整可视图+A算法、导向可视图(OVG)+A算法、简化可视图+A算法比较,该文算法在能够搜索到最优路径的前提下,降低了路径规划的耗时。关键词:全局路径规划;可视图;A算法;路径搜索中图分类号:TP301.6 文章编号:1005-9830(2017)03-0313-09DOI:10.14177/ j. cnki.32-1397n.2017.41.03.007Global path planning based on simultaneous visibility graphconstruction and A algorithmLv Taizhi1,

4、2,Zhao Chunxia1,Xia Pingping2(1. School of Computer Science and Engineering,Nanjing University of Science and Technology,Nanjing 210094,China;2. School of Information Engineering,Jiangsu Maritime Institute,Nanjing 211170,China)Abstract:A novel algorithm is proposed by constructing a visibility graph

5、(VG)in the process of pathsearch to improve the efficiency of global path planning. In the search process,a node is selected byA algorithm for expansion. According to the status of the node,a through line from the preview nodeto the node or from the node to the destination is drawn. If the line is c

6、ollision-free,it is added to theVG as a visible edge,or the 2 vertices of obstacles are added to the list for expansion. Simulationresults show that compared with complete visibility graph+A ,oriented visibility graph(OVG)+Aand simplified visibility graph+A ,the proposed algorithm can search the opt

7、imal path and decrease万方数据南京理工大学学报第41卷第3期the time for path planning.Key words:global path planning;visibility graph;A algorithm;path search具有智能特性的移动机器人已经在军用和民用多个领域得到了广泛应用,涉及众多学科的尖端技术1。导航是移动机器人的核心,研究的是:我在哪?我要去哪?我怎么去?分别对应的是定位、任务规划和路径规划问题。从机器人路径规划的目标范围看,路径规划分为全局路径规划和局部路径规划。全局路径规划就是移动机器人在有障碍的环境中,寻找一定指标下

8、(如距离、时间、能量等)尽可能优化的避障路径2。路径规划的研究始于20世纪70年代,但迄今为止尚无1种算法适用于所有环境,处于绝对领先的地位。所以目前这一领域的研究仍然十分活跃,不仅对于传统的环境地图建模和搜索算法做了进一步的改进,而且还提出了许多新的算法。当前主要使用的环境模型包括栅格分解图、四叉分解图、可视图、沃罗诺伊图(Voronoi diagram)。这些环境地图模型都存在改进的空间,如文献3,4提出了扇形栅格地图和基于四叉树的自适应栅格地图等栅格模型的改进方法。张琦等人5设计了1种忽略与路径无关障碍物的简化规则,通过该规则构建了1种可视边数量足够少的简化可视图环境模型。文献6提出了1

9、种改进的可视图方法,在损失一定路径规划质量的情况下,极大地提高了路径搜索的效率。对于多障碍物的环境,文献7提出了1种基于多边形聚合的改进可视图算法,通过对障碍物的简化,减少了可视图构造的耗时。文献8,9改进了可视图方法,使其具有较好的环境适应能力,可应用于未知或者动态的环境中。全局路径规划搜索算法主要分为启发式搜索算法和智能算法。 A算法是目前最有影响的、针对状态空间的启发式搜索算法。很多改进A算法被应用于路径规划中,如平滑A算法10,Theta算法11等。智能算法是1种借鉴、利用自然界中自然现象或生物体的概念、机理或原理开发的智能方法。近年来许多智能算法应用于全局路径研究中,取得了大量的成果

10、。遗传算法和蚁群算法是2种在路径规划中应用比较广泛的智能算法。量子遗传算法被用于路径规划中,具有更好的收敛性和更强的连续空间搜索能力2。蔡炯等人12提出了1种基于粗糙集和遗传算法的路径规划方法,从而有效地提高了路径规划的速度和精度。文献13将几何优化思想融入蚁群全局规划算法中,使得改进后的全局路径规划算法在地面移动机器人的全局路径规划中具有普遍适用性。赵娟平等人14针对蚂蚁双向并行搜索策略会丢失蚂蚁间的部分可行路径甚至最优路径的问题,提出了根据信息素判断蚂蚁是否相遇的判别法。上述改进算法都首先建立移动机器人所在的环境地图模型,然后在此模型下使用搜索算法获得最优路径。这些算法改进的重点不是环境地

11、图模型的简化,就是搜索算法的优化。本文提出了1种同步可视图构造和A算法(Simultaneous visibility graph construction and Aalgorithm,SVGCA )的全局路径规划算法,将环境地图的建立和路径搜索的过程融合在一起。基于可视图的骨架构造方法和A算法,在搜索最优路径的过程中同步生成可视图,提高了全局路径规划的效率。1全局路径规划算法描述全局路径规划是人工智能的1个基本问题 搜索问题。形式上,规划问题是1个四元X,Xinit,Xgoal,Xobst。其中X是搜索空间,Xinit是起始位置,Xinit X;Xgoal是目标位置,Xgoal X;Xob

12、st是障碍集合,Xobst X。如果路径序列u1,u2, ,uk是规划问题的1组解决方案,那么u1 =Xinit,uk =Xgoal,并且u1,u2, ,uk Xobst =。全局路径规划的目的就是根据给出的起始位置、目标位置和障碍集信息,在搜索空间寻找1组满足一定准则的路径序列。1.1可视图可视图法将起始点、目标点和障碍物的各顶点进行组合连接,并保证这些直线均不与障碍物相交,即保证这些连接线段是可视的5-7。这些线段构成了1张图G=V,E,称为可视图。 E为可视边的集合,点集V包含起点、目标点和障碍物各顶点。可视图建模结果如图1所示,S和G分别代表起始点和目标点,灰色多边形为障碍物。路径规划

13、问题转化为在可视图上使用某种搜索算413万方数据总第214期吕太之赵春霞夏平平基于同步可视图构造和A算法的全局路径规划 法查找经过可视边到达目标点的最短路径问题。图1完整可视图建模图1.2 A算法Dijkstra是最为经典、应用最为广泛的搜索算法。它采用的是广度优先搜索的策略,以起始节点为中心向外扩展,直到扩展到目标节点为止。A算法是1种启发式搜索算法,在Dijkstra扩展节点中加入了评价函数10。每个节点x定义1个评价函数f(x)= g(x)+h(x) (1)式中:f(x)表示从起始节点经过当前节点到目标节点最短路径的估计值,g(x)表示起始节点到当前节点的实际路径长度,h(x)是启发函数

14、,是估计的当前节点到目标节点最短路径。2 SVGCA算法传统的基于可视图的全局路径规划算法在搜索之前根据障碍物的信息建立完整的可视图,然后使用某种搜索算法查找最优路径。建立完整可视图的时间复杂度为O(N3),N为障碍物顶点的数量。构造的可视图包含了M条可视边,路径规划问题转换为在M条可视边上找到1条从起始点到目标点的最优路径。当M很大的时候,无论采用何种搜索算法,获取路径所耗费的时间都不会太少。基于此,本文提出了1种在搜索过程中同步生成可视图的改进算法SVGCA 。 SVGCA算法不是在搜索之前建立完整的可视图,而是将可视图的建立过程融入A算法搜索中。搜索过程中只构造与最优路径可能有关的可视边

15、,而忽略了大部分的可视边,提高了全局路径规划的效率。首先通过对比图1和图2说明SVGCA算法的基本思想,然后给出它的详细实现流程。图1中构造了1个完整的可视图,包括107条可视边,然后在此基础上使用搜索算法寻找最优路径。图2中SVGCA算法仅通过3条穿越线和4条可视边就找到了最优路径S A1 B1 G。穿越线指的是可以穿越障碍物连接2点的连线。首先构造1条从起始点S到目标点G的穿越线,由于它穿越了障碍物O1,如果移动机器人想要穿越该障碍物到达目标点,必然要通过离穿越线最远的顶点A1和A2,因此将A1和A2添加到待扩展列表中。首先扩展评价值最小的节点A1,构造S到A1的穿越线。由于该穿越线没有穿

16、越任何障碍物,将它作为可视边添加到可视图中。继续扩展A1,构造从A1到目标点G的穿越线,该穿越线经过障碍物O2,将B1和B2添加到待扩展列表中。重复这样的流程直到搜索到达了目标点G,路径规划结束。图2 SVGCA算法图2.1算法描述由于SVGCA算法忽略了大部分的可视边,存储的可视边数量极其有限。为了节省存储空间,SVGCA算法使用邻接表存储可视图。与A算法类似,SVGCA算法使用OPEN表存储待扩展的节点,使用CLOSED表来提高搜索效率和存储路径。在A算法的OPEN表存储的条目基础上,SVGCA算法增加了节点状态和访问次数。OPEN(i)= index,prev,status,gn,hn,

17、visitedCount (2)式中:index是节点在可视图点集V中的编号,prev表示上一节点,status是节点状态,即从上一节点到此节点是否被探索过,0表示未被探索过或者2点之间的穿越线不是可视边,1表示2点之间的穿越线是可视边。 gn的值是上一节点gn值加上2节点之间穿越线的长度,hn表示此节点到目标点的估计值,visitedCount是节点的访问次数,用来避免重复访问相同的节点。CLOSED表中每个节点信息如下CLOSED(i)= index,prev,gn (3)式中:prev是上一节点在CLOSED表中的索引号,513万方数据南京理工大学学报第41卷第3期prev为0表示该节点

18、是起始点,gn是起始点到此节点的实际路径长度。SVGCA算法包含初始化和路径搜索2部分。在初始化时,将目标点G放入OPEN表中,将起始点S存放到CLOSED表中,将障碍物中相邻的边存入可视图中;在路径搜索的过程中,需要取出评估值最小的节点进行扩展。根据节点的状态构造穿越线,然后在此基础上完成可视图的构造和路径的搜索。具体步骤如下:(1)步骤1,初始化。将OPEN表初始化为OPEN(1)= G,S,0,DSG,0,0 (4)式中:DSG是起始点S到目标点G的欧氏距离。将CLOSED表初始化为CLOSED(1)= S,0,0 (5)(2)步骤2,取出最小节点。取出评价函数值最小的节点进行扩展。评价

19、函数定义如下f(x)= gn+hn+visitedCountMAXDISTANCE (6)式中:MAXDISTANCE表示从起始点到目标点可能的最大距离。这样确保不会重复访问相同的节点。在未被访问过的节点中选择gn+hn值最小的,即估计路径最短的节点来扩展。(3)步骤3,判断节点访问次数。判断当前节点的访问次数是否等于1,如果等于1表示所有可行的路径已经探索过,查找不到1条达到目标点的路径,算法结束。(4)步骤4,根据节点信息查找路径。根据节点的状态分为2个不同分支执行。当节点状态为0时,执行步骤5,否则执行步骤6。(5)步骤5,探索上一节点到当前节点的路径。构造上一节点到当前节点的穿越线。如

20、果该线已存在于可视图中或与障碍物无冲突,更新节点状态为1,如果该穿越线不在可视图中,将其作为可视边添加到可视图中。如果穿越线与障碍物有冲突,穿越线将障碍物分为2个部分,分别取出2个部分中距离穿越线最远的顶点。如果这2个顶点不在CLOSED和OPEN表中,将其添加到OPEN表中。OPEN(size+1)= P,node. prev,0,node. prev. gn+DPP,DPG,0 (7)式中:P是被穿越障碍物的顶点,node表示当前扩展的节点,DPP表示的是上一节点到顶点P的欧式距离,DPG是顶点P到目标点G的欧式距离。最后将当前节点的访问次数加1。(6)步骤6,探索当前节点到目标点的路径。

21、构造当前节点到目标点G的穿越线。如果该线已在可视图中或者与障碍物没有冲突,表示已查找到路径,输出路径,算法结束。如果该线与障碍物有冲突,将该节点添加到CLOSED表中,同时从OPEN表中删除。与步骤5中添加障碍物顶点的方法一样,添加被穿越障碍物的Phigh和Plow节点到OPEN表中。OPEN(size+1)= P,node,0,node. gn+DCP,DPG,0 (8)式中:DCP是当前节点到障碍物顶点P的欧式距离。SVGCA算法伪代码如下:01: While(true)02: node FindMiniumNode(OPEN);/ /步骤2取出评价值最小的节点03: If(node. v

22、isitCount= =1) / /步骤3判断所有路径是否已经被探索过04: Print(“no path”);05: Break;06: End07: If(node. status= =0) / /步骤5探索上一节点到当前节点的路径08: line ConsturctThroughLine(node. prev,node);/ /构造上一节点到当前节点的穿越线09: If(line in E or line is Collision-Free)10: node. status=1;11: addToE(line);12: Else13: AddVertices(node,line);/ /

23、对于每个被穿越的障碍物,不超过2个顶点被添加到OPEN表中14: node. visitCount=1;15: End If16: Else If(node. status= =1) / /步骤6探索当前节点到目标点的路径17: line ConsturctThroughLine(node,G);/ /构造当前节点到目标点的穿越线18: If(line in E or line is Collistion-Free)19: PrintPath(CLOSED);20: Break;21: Else22: AddVertices(node,line);/ /对于每个被穿越的障碍物,不超过2个顶点被

24、添加到OPEN表中23: AddToCLOSED(node);24: DeleteFromOPEN(node);25: End If26: End If27:End While613万方数据总第214期吕太之赵春霞夏平平基于同步可视图构造和A算法的全局路径规划 2.2算法性能(1)完备性。在障碍物和顶点数量有限的环境中,SVGCA算法在经过若干次迭代后只可能出现2种情况:搜索到目标节点,算法终止;OPEN表中的节点访问次数都为1,表示所有路径已被探索过,没有查找到可通行的路径,算法终止。无论发生哪种情况,SVGCA算法都在有限步终止。(2)最优性。 SVGCA算法构造的非完整可视图包含了最优路

25、径,同时使用A算法可以搜索到最优路径,所以SVGCA算法可以搜索到最优路径。首先证明在SVGCA算法中,A算法搜索可以找到最优路径。在A算法搜索中,如果沿着任何路径的f(x)是非递减的,那么搜索将按照非递减的f(x)顺序扩展节点序列,因此最先被选中扩展的目标节点就是最优解,所有后面的节点路径耗散都不小于它15。SVGCA算法搜索中的f(x)是非递减的。假设xn是x的后继节点,可以得出f(xn)= g(xn)+h(xn)= g(x)+Dx_xn+h(xn) (9)式中:Dx_xn表示x和xn之间的欧式距离。本文中欧式距离作为启发函数使用策略,x、xn和目标节点构成三角形。三角形中任何1条边的长度

26、不大于另外2条边之和,即f(x)是非递减的。h(x) Dx_xn+h(xn) f(x) f(xn) (10)下文证明SVGCA算法中构造的非完整可视图中包含了最优路径。 SVGCA算法通过穿越线添加到OPEN表中的某些顶点必然构成最优路径,而构成最优路径的边也会添加到可视图中。证明如下:当起始点S和目标点G可见时,穿越线不穿越任何障碍物,根据2点之间线段最短的原理,此时穿越线就是最短路径,将穿越线添加到可视图中;当S点和G点不可见时,即2点之间存在障碍物,机器人需要绕过一系列障碍物到达G点。假定障碍物Oi被S和G的连线穿越,穿越线将障碍物分为2个部分,设Phighi和Plowi分别为2个部分最

27、远离穿越线的顶点。机器人要以最优路径绕过障碍物Oi,必然经过该障碍物Phighi和Plowi顶点中的1个,或者在比这2个顶点更远离穿越线的位置绕过此障碍物。如果最优路径从障碍物Oi的Phighi和Plowi中的1个顶点通过,假定该顶点为Pi,SVGCA算法在构造S和G之间的穿越线时会将该顶点添加到OPEN表中以待扩展。由于Pi在最优路径上,必然会被取出扩展。构造S和Pi之间的穿越线,如果2点之间可视,将穿越线添加到可视图中。如果S和Pi之间不可视,构造S和Pi之间的穿越线,移动机器人绕过这些障碍物后将到达Pi。接着以Pi为起始点,构造Pi到G的穿越线,以此类推,可视图中包含了最优路径。如果最优

28、路径从比障碍物Oi的Phighi或Plowi顶点更远离穿越线的位置通过,只能基于以下2种情况。某个被穿越障碍物Oj的Phighj或Plowj顶点比障碍物Oi的Phighi和Plowi更加远离S和G之间的穿越线,最优路径从远离障碍物Oi的位置直接到达障碍物Oj上的顶点。所有被穿越障碍物的Phigh和Plow顶点都会添加到OPEN表中以待扩展,如果Phighj或Plowj在最优路径上,一定会被取出扩展。假定最优路径从Phighj和Plowj中的1个顶点通过,参照前文,构造S和该顶点以及该顶点和G的穿越线。另一种情况是在起始点S和顶点Pi之间或者顶点Pi和G点之间有障碍物存在,并且这些被穿越障碍物的

29、Phigh或Plow顶点比Pi更远离S和G之间的穿越线,最优路径将会不经过障碍物Oi上的顶点,而是经过这些更远离S和G之间穿越线的顶点。在扩展顶点P之后,构造S和Pi以及Pi和G之间的穿越线,所有被穿越的障碍物的Phigh和Plow顶点都会被添加到OPEN表中以待扩展,这些顶点包含了最优路径经过的顶点。以此类推可视图中包含了最优路径。(3)算法复杂度。 A算法的时间复杂度与Dijkstra算法数量级相同,是O(N2)。但是A算法采用启发式搜索,性能明显优于Dijkstra算法的毫无方向的向四周搜索。如果选取h(x)为0,A算法退化为Dijkstra算法。 SVGCA算法使用A算法搜索最优路径,

30、每次迭代过程中需要构造穿越线,并判断穿越线是否可视,其时间复杂度是O(N)。可视图构造最内层循环需要判断2点之间是否可视,其时间复杂度是O ( N)。所以SVGCA算法的时间复杂度是O(N3),与构造可视图的时间复杂度数量级相同。可视图的构造涉及障碍物的全部顶点,SVGCA算法忽略了与路径无关的顶点,涉及的顶点数量远远小于可视图构造中的顶点数量,如图1和2所示。图2中有3个障碍物与最优路径无关,这3个障碍物的顶点不需要参与SVGCA算法。在与SVGCA算法有关的障碍物中,也只有6个顶点添加到OPEN713万方数据南京理工大学学报第41卷第3期表中。在涉及的障碍物顶点中,SVGCA算法也没有全部

31、判断这些顶点两两之间是否可视。图1中顶点数量为26个,需要判断2点之间是否可视262次,而SVGCA算法只判断2点之间是否可视7次,由此可以看出SVGCA算法所花费的时间要远远少于构造完整可视图的时间。但是算法效率的提升与地图环境、机器人所在的位置以及目标点有关。在SVGCA算法搜索中忽略的顶点数量越多,算法时间效率提高越大。3仿真实验分析为了测试算法的性能,将SVGCA算法与其他3种基于可视图的全局路径规划算法进行对比。第1种算法为完整可视图+A算法,是在建立完整可视图后,使用A算法搜索最优路径;第2种算法为导向可视图(Oriented visibility graph,OVG)8 +A算法

32、,是在使用OVG方法建立可视图后,使用A算法搜索最优路径;第3种算法为简化可视图+A算法,是在使用文献5的方法建立简化可视图后,使用A算法搜索最优路径。4种算法在有障碍物的二维环境中进行仿真实验对比,并均在MATLAB R2013a上实现。仿真实验使用的计算机CPU型号为Intel(R)Core(TM)i5-3230M,主频为2.60 GHz,RAM容量为8 GB。(1)实验1,在简单环境下4种算法的对比,结果见图3和表1。首先使用文献5中的仿真环境进行4种算法的实验对比。环境如图3(a)所示,包含了6个障碍物,移动机器人起始点和目标点分别为(43,101)和(476,425)。完整可视图+A

33、算法结果如图3(b)所示,构造了106条可视边。 OVG+A算法结果如图3(c)所示,构造了55条可视边。简化可视图+ A算法结果如图3(d)所示,构造了38条可视边。 SVGCA算法结果如图3(e)所示,通过6条穿越线和4条可视边查找到最优路径。图3简单环境下4种算法实验结果对比图表1简单环境下4种算法实验结果对比表算法可视边数穿越线数最优路径长度算法执行时间/ s OPEN表长度可视图构造时间/ s路径查找时间/ s完整可视图+A 106 574.61 0.65 67 0.60 0.05OVG+A 55 574.61 0.47 16 0.44 0.03简化可视图+A 38 574.61 0

34、.39 13 0.36 0.03SVGCA 4 6 574.61 0.09 4813万方数据总第214期吕太之赵春霞夏平平基于同步可视图构造和A算法的全局路径规划 在简单环境下,与其他3种算法相比较,SVGCA算法耗时分别减少86%、80%和76%,可以看出SVGCA算法大大提高了全局路径规划的效率。仅对比可视图的构造时间,SVGCA算法耗时也远小于其他3种算法,同时SVGCA算法空间复杂度也低于其他3种算法。(2)实验2,在复杂环境下4种算法的对比,结果见图4和表2。采用文献6的复杂环境进行4种算法的对比。环境地图如图4(a)所示,环境中包括了15个障碍物,165个顶点,障碍物占环境地图面积

35、50%左右。移动机器人的起始点和目标点分别为(62,12)、(357,486)。如图4(b)所示,可以看出完整可视图+A算法可视图的构建过程耗费大量的时间,而其中很多可视边与查找的路径无关。同时可视边数量的增加也导致A算法查找空间和时间效率的低下。如图4(c)所示,由于OVG+A算法需要对障碍物之间的可视边进行判断,确定是否加入可视图中,虽然构造的可视边减少,但是可视图构造时间并没有明显减少。同时OVG+A算法无法保证在非全部凸形障碍物的环境下找到最优路径,所以该算法在此环境中找到的不是最优路径。如图4(d)所示,由于在本实验环境中,大部分障碍物都与查找的路径有关,所以使用简化可视图对于全局路

36、径规划效率改进有限。如图4(e)所示,SVGCA算法虽然搜索的迭代次数高于其中2种算法,但由于扩展的节点数量和OPEN表长度远低于其他3种算法,所以SVGCA算法的执行时间低于其他3种算法在可视图构建后的查找时间。仅对比可视图构造时间,SVGCA算法耗时远远低于其他3种算法,不到他们可视图构造耗时的5% 。文献6采用的是1种并行的可视图构造算法,该算法比完整的可视图构造算法效率提升约50% ,但是获得的不是最优路径。无论从时间复杂度还是空间复杂度来看,在复杂的环境地图中,SVGCA算法仍然远远优于其他3种算法,也优于文献6中的并行可视图构造算法。图4复杂环境下4种算法实验结果对比图表2复杂环境

37、下4种算法实验结果对比表算法可视边数算法执行时间/ s可视图构造时间/ s路径查找时间/ s迭代次数OPEN表长度CLOSED表长度完整可视图+A 790 24.69 23.59 1.20 61 325 61OVG+A 273 23.45 22.47 0.98 119 125 119简化可视图+A 663 21.35 20.13 1.18 61 310 61SVGCA 0.94 65 43 12913万方数据南京理工大学学报第41卷第3期(3)实验3,随机地图环境下的测试。为了进一步验证算法的效率,在100100的环境中随机生成最大边长不超过30,顶点数量不超过10个的若干障碍物环境。构造了4

38、类不同的环境地图进行测试,4类地图中障碍物的数量分别为6、9、12、15。每类环境地图随机测试100遍,测试结果如表3所示。从表3可以看出无论在哪种环境下,SVGCA算法执行效率远比其他3种算法高。即使在有15个障碍物、平均95个顶点的环境中,SVGCA算法在大部分情况下能在1s内搜索到最优路径,而用完整可视图+A算法的平均查找时间已经达到5.9 s,在最坏的情况下查找时间达到了42.37 s。可以看出SVGCA算法在能够搜索到最优路径的前提下,大大降低了路径规划的耗时。表3随机障碍物环境下的实验结果表障碍物数量平均顶点数量算法平均执行时间/ s最快执行时间/ s最差执行时间/ s OPEN表

39、平均长度6 41完整可视图+A 0.63 0.294 1.77 976 41 OVG+A 0.37 0.007 1.76 266 41简化可视图+A 0.21 0.002 1.49 436 41 SVGCA 0.02 0.002 0.43 119 60完整可视图+A 1.83 0.768 5.58 2759 60 OVG+A 1.17 0.169 5.39 759 60简化可视图+A 0.72 0.022 3.57 1339 60 SVGCA 0.11 0.014 0.79 3512 79完整可视图+A 3.74 1.971 27.32 42012 79 OVG+A 2.87 0.927 23

40、.54 10312 79简化可视图+A 1.96 0.432 21.64 18212 79 SVGCA 0.21 0.013 0.85 5315 95可视图+A 5.96 2.757 42.37 57815 95 OVG+A 5.32 2.475 36.00 13215 95简化可视图+A 4.18 2.233 29.45 34115 95 SVGCA 0.51 0.042 2.17 874结束语本文结合可视图和A算法,提出了1种同步可视图构造和路径搜索的算法。通过连接2点之间的穿越线添加可扩展的节点,使用A算法确定待扩展的节点。每个节点有2个状态,扩展的时候根据节点状态确定构建从上一节点到当

41、前节点的穿越线或当前节点到目标节点的穿越线,如果穿越线没有穿越任何障碍物,即为可视边,添加到可视图中。 SVGCA算法只构建与最优路径可能有关的可视边,忽略了对于最优路径规划结果不会产生任何影响的可视边,提高了路径规划算法的效率。仿真结果证明了与传统的完整可视图+A算法、简化可视图+A算法5以及OVG+A算法8对比,SVGCA算法无论在时间复杂度还是空间复杂度上,都远优于其他3种算法。但是SVGCA算法在扩展节点时没有考虑穿越线经过障碍物的顺序,仅以欧式距离作为估计函数确定下一步扩展的节点,实际情况是可能有的障碍物顶点是必经点,如果先扩展该节点,算法执行效率将会更高。后续研究将充分利用穿越线经

42、过障碍物的几何特性来进一步提高算法的执行效率,以及将算法拓展到三维空间中。参考文献:1谭民,王硕.机器人技术研究进展J.自动化学报,2013,39(7):963-972.Tan Min,Wang Shuo. Research progress on roboticsJ. Acta Automatica Sinica,2013,39(7):963-972.2刘传领.基于势场法和遗传算法的机器人路径规划技术研究D.南京:南京理工大学计算机科学与工程学院,2012.3秦利超.基于扇形栅格地图的移动机器人地图创023万方数据总第214期吕太之赵春霞夏平平基于同步可视图构造和A算法的全局路径规划 建D.

43、天津:天津工业大学电气工程与自动化学院,2012.4郭利进,师五喜,李颖,等.基于四叉树的自适应栅格地图创建算法J.控制与决策,2011,26(11):1690-1694.Guo Lijin,Shi Wuxi,Li Ying,et al. Mapping algorithmusing adaptive size of occupancy grids based onquadtreeJ. Control and Decision,2011,26 (11):1690-1694.5张琦,马家辰,马立勇.基于简化可视图的环境建模方法J.东北大学学报(自然科学版),2013,34(10):1383-13

44、86.Zhang Qi, Ma Jiachen, Ma Liyong. Environmentmodeling approach based on simplified visibility graph J . Journal of Northeastern University ( NaturalScience),2013,34(10):1383-1386.6 Tran N, Nguyen D T, Vu D L, et al. Global pathplanning for autonomous robots using modifiedvisibility-graph C / / Pro

45、ceedings of IEEE Interna-tional Conference on Control, Automation andInformation Sciences. Nha Trang, Vietnam: IEEE,2013:317-321.7 Nguyet T T N,Hoai T V,Thi N A. Some advancedtechniques in reducing time for path planning based onvisibility graph C / / Proceedings of InternationalConference on Knowle

46、dge & Systems Engineering.Hanoi,Vietnam:IEEE,2011:190-194.8 Wooden D, Egerstedt M. Oriented visibility graphs:Low-complexity planning in real-time environments C / / Proceeding of the 2006 IEEE InternationalConference on Robotics and Automation. Orlando,USA:IEEE,2006:2354-2359.9刘罡,刘玉斌,赵杰.基于可视切线图的未知环

47、境建模新方法研究J.高技术通讯,2010,20 (5):505-510.Liu Gang, Liu Yubin, Zhao Jie. Research on a newmethod for unknown environment modeling based onvisual tangent graphsJ. High Technology Letters,2010,20(5):505-510.10 Xie Yang,Cheng Wushan. AGV path planning based onsmoothing A algorithm J. International Journal of

48、Software Engineering & Applications,2015,6(5):1-8.11 Nash A,Daniel K,Koenig S,et al. Theta :Any-anglepath planning on grids J. Journal of ArtificialIntelligence Research,2014,39(1):533-579.12蔡炯,汪小志.基于粗糙集与遗传算法的采摘机器人路径规划 J.农机化研究, 2016, 38 (8):189-193.Cai Jiong, Wang Xiaozhi. Path planning of pickingrobot based on rough set and genetic algorithmJ.Journal of Agricultural Mechanization Research,2016,38(8):189-193.13刘杰,闫清东,马越,等.