基于改进单元分解法的全覆盖路径规划.pdf
《基于改进单元分解法的全覆盖路径规划.pdf》由会员分享,可在线阅读,更多相关《基于改进单元分解法的全覆盖路径规划.pdf(9页珍藏版)》请在咨信网上搜索。
1、第45卷第12 期2023年12 月文章编号:10 0 1-50 6 X(2023)12-3949-09基于改进单元分解法的全覆盖路径规划吴靖宇1.2,朱世强2.3,宋伟2.3.*,施浩磊4,吴泽南4(1.浙江大学海洋学院,浙江舟山316 0 2 1;2.浙江大学机器人研究院,浙江宁波31540 0;3.之江实验室,浙江杭州31112 1;4.舟山市质量技术监督检测研究院,浙江舟山316 0 13摘要:传统的单元分解法在静态已知环境中进行全覆盖路径规划时,若障碍物分布不规则或具有较多的凹形障碍物,则所得的单元数量较多,这导致最终路径易出现较多的余和不必要的转向。首先,将栅格地图分解为若千个路径
2、片段,每个路径片段由位于同一行且左右相邻的栅格组成;然后,合并这些路径片段以生成单元;再基于贪心算法和拓扑地图三次求解单元间的遍历顺序,合并减少了单元数量,并对局部路径进行了优化,最终完成遍历路径的规划。仿真结果验证了所提算法的有效性,且规划的路径具有更少的余和转向次数。关键词:全覆盖路径规划;单元分解法;单元合并;贪心算法中图分类号:TP242Coverage path planning based on improved cellular decompositionWU Jingyul-2,ZHU Shiqiang3,SONG Wei?3.*,SHI Haolei,WU Zenan(1.O
3、cean College,Zhejiang University,Zhoushan 316021,China;2.Robotics Institute,Zhejiang University,Ningbo 315400,China;3.Zhijiang Lab,Hangzhou 311121,China;4.Zhoushan Institute ofCalibration and Testing for Qualitative and Technical Supervision,Zhoushan 316013,China)Abstract:When the traditional cellul
4、ar decomposition method is used for complete coverage path planningin a static known environment,if the obstacles are irregularly distributed or many concave obstacles exist in theenvironment,the number of cells obtained is large.This finally leads to much redundancy and unnecessarysteering in the f
5、inal path.Firstly,the grid map is decomposed into several path segments,each of the pathsegment is composed of grids located in the same row and adjacent to the left and right.Secondly,these pathfragment are merged for generating cells.Thirdly,based on greedy algorithm and topological map,the traver
6、salorder between cells is solved three times to merge and to reduce the number of cells,and the local path isoptimized.Finally,the planning of traversal path is completed.Simulation results show that the algorithm iseffective and the planned path has less redundancy and steering times.Keywords:compl
7、ete coverage path planning;cellular decomposition;cellular mergence;greedy algorithm0 引 言路径规划是影响移动机器人作业效率的重要环节。按照所得路径的特点,路径规划可分为“点到点”和“全覆盖”两类。其中,前者可应用于山地救援、自动驾驶2 、物流运输9等两点之间无碰撞的移动场景,现有方法包括A-5法、人工势场法6、快速扩展随机树7 等;后者则应用于地收稿日期:2 0 2 2-11-2 2;修回日期:2 0 2 3-0 4-0 6;网络优先出版日期:2 0 2 3-0 8-14。网络优先出版地址:https:/k
8、 n s.c n k i,n e t/k c m s/d e t a il/11.2 42 2.T N.2 0 2 30 8 14.10 51.0 0 2.h t m l基金项目:浙江省市场监督管理局维鹰计划培育项目(CY2022231)资助课题*通讯作者。引用格式:吴靖宇,朱世强,宋伟,等基于改进单元分解法的全覆盖路径规划。系统工程与电子技术,2 0 2 3,45(12):3949-3957.Reference format:WU J Y,ZHU S Q,SONG W,et al.Coverage path planning based on improved cellular decomp
9、ositionJJ.SystemsEngineering and Electronics,2023,45(12):3949-3957.系统工程与电子技术Systems Engineering and Electronics文献标志码:AVol.45No.12December 2023网址:www.sys-D0I:10.12305/j.issn.1001-506X.2023.12.25面清扫8、农业植保9、油罐底面清洗10 等需要遍历某一区域的场景,现有方法包括生物激励神经网络算法1-12、生成树覆盖算法13-14、单元分解法15等。当在静态已知环境中进行全覆盖路径的离线规划时,单元分解法是一种
10、常用的方法16-17。该方法的实现过程主要分为两个步骤,分别为划分单元和求解单元间遍历顺序。其中划分单元是指将待遍历的区域划分为若干个互不重3950:叠的子区域。传统的单元分解法在此步骤采用的是根据障碍物的形状和位置划分单元的方式,包括:Trapezoidal分解18 、Boustrophedon分解19-2 1和Morse分解2-2 3。而求解单元间遍历顺序则是一个旅行商问题,常用的方法包括深度优先搜索2 4、模拟退火法2 5、蚁群算法2 6、粒子群优化算法2 7、遗传算法2 8-2 9、强化学习30 1和深度强化学习31等。但传统的单元分解法在障碍物分布不规则和凹形障碍物较多的场景下却易出
11、现较多的?余路径和转向次数。其中分布不规则是指在栅格地图上,各个障碍物的几何中心一般位于不同的行和列。日常生活中椅子、凳子等物件即会因人们的使用而成为分布不规则的障碍物。凹形障碍物则可见于办公区域等场景,例如只有一扇门进出的房间,其四周墙壁即可视为凹形障碍物。在这两种场景中,待遍历区域的形状变得不规则,使得传统的单元分解法所得单元的数量较多。而单元数量的增加会使得每个单元的平均面积减少,造成传统的单元分解法难以在更大的范围内应用并优化局部路径,故易产生较多的穴余路径和转向次数。对此,本文提出一种改进的规划算法,目的是减少最终路径的穴余和转向次数。改进后的单元划分通过在栅格地图上合并路径片段来实
12、现(路径片段由位于同一行且左右相邻的栅格组成)。这样,单元的划分不再完全依赖于障碍物的形状和位置,而是兼顾了单元内的路径规划。同时,为了减少单元的数量,在求解单元间遍历顺序时,结合贪心算法和拓扑地图进行三次求解,不断合并单元,并对局部路径进行了优化。本文的结构安排如下:引言部分介绍了路径规划的研究现状和传统单元分解法存在的一些不足;第1节阐述了路径片段初步合并生成单元的过程;第2 节阐述了基于贪心算法和拓扑地图的单元间遍历顺序的求解过程;第3节进行了仿真实验,其结果验证了本文算法的有效性;第4节对全文进行了总结,指出当前本文算法存在的不足。本文的主要创新点在于:改进了传统单元分解法划分单元的方
13、式,并通过对单元的合并,降低了在障碍物分布不规则和凹形障碍物较多的场景下单元划分的数量,减少了穴余路径和转向次数。1单元初步合并生成本节通过合并路径片段初步生成单元,以实现对待遍历区域的单元划分。相关步骤包括:栅格地图初始化、生成路径片段、确定遍历起始单元和合并路径片段。1.1栅格地图初始化首先,建立平面直角坐标系,其原点O位于地图左上角,向下为X轴,向右为Y轴,则第行、第6 列栅格可以用坐标(a,b)表示。然后,建立与栅格地图对应的同维度矩阵,并将待遍历栅格以数字0 表示,将障碍物以数字1表示。为获取该矩系统工程与电子技术阵对应位置的数值,定义函数 F(a,b)如下:F(a,b)=1,障碍物
14、栅格或边界之外设地图上所有的栅格组成集合Cll,则其中待遍历栅格可以表示为Cov=(xi,y,)ECll/F(a,y,)=0)1.2生成路径片段定义路径片段如下:地图上位于同一行且未被障碍物阻隔的全部连通栅格的有序排列集合,则第R行的某一路径片段Cr=(aRy),(aRy2),.,(CR,y,)满足:F(R,yi-1)=1F(aR,y,+1)=1F(R,y)=o,1erJ/-yf-1=1,2fr设某一地图的待遍历区域通过划分共生成了n个路径片段,则它们组成的集合Cpath=(Ci,C2,,C.)满足:CiUC,U.UC,=CovCnCh=,1gn;lhn;gh图1所示为一个生成路径片段的示例(
15、图中黑色栅格为障碍物,白色栅格为待遍历区域,下同)其中属于同一路径片段的栅格以线段依次相连。显然,每条线段均可作为机器人的潜在移动路径,而单元则可通过合并这些路径片段来生成。图1生成路径片段Fig.1 Path fragments generation1.3确定遍历起始单元假定机器人的直线运动平行于坐标轴,且平均速度为u;机器人每转过9 0 视为一次转向,且所需时间为t。机器人在从坐标为(a,b)的栅格移动到坐标为(c,d)的过程中共转向M次,直线运动的总路程长度为L,则该次移动所需的总时间为T(a,b),(c,d)=+tM若在该时间内机器人始终以平均速度做直线运动,则可移动距离为L=.T(a
16、,b),(c,d)J=L+tM记P=ut,则机器人从栅格(a,b)移动到(c,d)的等效路径长度为第45卷0,待遍历栅格(1)(2)(3)(4)(5)(6)第12 期由于和t的值仅与机器人的自身性能有关,数值可由实验测出。当机器人的型号确定后,参数P即为一个常量。因此,由式(7)计算所得的等效路径长度L可作为评价路径优劣的评价指标。以式(7)计算机器人的初始位置所在栅格到每个路径片段首尾两个端点栅格的等效路径长度,根据最小值确定起始路径片段和起始栅格。若起始栅格位于起始路径片段的末端,则对起始路径片段中的栅格进行倒序排列。后续由起始路径片段合并生成的单元即是遍历起始单元,记为Cs。1.4合并路
17、径片段路径片段的合并流程如图2 所示。开始初始化集合CMe否存在集合C满足合并要求?是将Ca合并至Cm并调整C.内部排列集合C是否满足合并要求?将C.添加至CMer,并从Cpa中移除Cm剩余集合记为CMo2结束图2 路径片段合并流程图Fig.2Flowchart of path fragment mergency具体步骤如下:步骤1生生成空集合CMer,对合并完成的单元进行存储。步骤2 判断Cpath中是否存在某一路径片段C(1mn)且满足以下两个要求:(1)Cm在地图上的相邻路径片段Cacj属于Cpath;(2)C a 仅有一个端点栅格与Cm的某一端点栅格上下相邻。其中,两个路径片段相邻的定
18、义为:存在两个上下相邻的栅格分别属于这两个路径片段,即日(a,b)ECm,日(c,d)ECad,满足:(8)b=d此外,为避免起始栅格之前出现路径,将起始栅格视为与所有栅格均不相邻。若存在Cm满足要求,则将 Cai合并至Cm,并跳转至步骤3,否则跳转至步骤7。吴靖宇等:基于改进单元分解法的全覆盖路径规划L=L+PM(7)是a-cl=13951图3所示为本步骤中路径片段满足合并要求的两种情形。其中情形1表示两个路径片段除了一组端点栅格上下相邻,还存在其他栅格相邻;情形2 则与之相反。(a)情形1(b)情形2(a)Situation 1(b)Situation 2图3满足合并要求的两种情形Fig.
19、3Two situations meeting the mergency requirements步骤3对合并后的 Cm,调整其栅格排列顺序,确保以该顺序生成的移动路径连贯,如图4所示。(a)情形1路径(a)Path of Situation 1图4调整集合内栅格排列顺序后所生成的路径Fig.4Path generated after adjusting grid arrangementorder in the column步骤4对调整后的集合Cm重复步骤2 和步骤3,直至Cm不满足步骤2 中的要求。步骤5将Cm从Cpath中移除,并添加至CMer,以防止出现重复规划。步骤6 重复步骤2 步骤
20、5,直至Cpath中不存在集合满足步骤2 中的要求。步骤7 将Cpath中剩余的集合记为CMer2则CMer和CMer2中的每个元素即为初次合并后的单元。这些单元具有以下两个特点:(1)以栅格排列顺序所生成的路径可无重复地遍历该单元;(2)该路径的起点为排列在首末位置的两个栅格之一。这样,单元的生成除了考虑障碍物的形状和位置,也兼顾了单元内的路径规划。图5(a)所示为路径片段初步合并后的结果,图5(b)为合并形成的单元,共有13个(图中黑色圆点代表路径起点,下同)。后续单元的合并以及局部路径的优化需参照单元间的遍历顺序进行。(a)路径片段的合并结果(a)Mergency result of p
21、ath fragments(b)情形2 路径(b)Path of Situation 23952:系统工程与电子技术2第45卷开始?8(b)由路径片段所生成的单元(b)Cellular generated by path fragments图5单元初步合并生成的结果Fig.5Result of preliminary cellular mergence2基于贪心算法和拓扑地图的单元间遍历顺序求解本节求解单元间的遍历顺序,以生成最终路径。相关步骤包括:生成拓扑地图和执行3次基于贪心算法的求解。其中,拓扑地图根据单元间的相邻情况生成,用于求解过程中单元的再次合并。而在3次求解中,后一次求解均基于前
22、一次求解的结果,以使得局部路径不断得到优化,从而减少最终总体路径的穴余和转向次数。2.1生成拓扑地图依据各单元的相邻情况生成拓扑地图。图6 即是由图5所得的拓扑地图。1289:根节点;:通道节点;图6 生成拓扑地图Fig.6Generation of topology map其中,每个单元均可视为一个节点,而整个地图则可视为一个树形结构。为便于进一步合并单元,进行如下定义,从而将所有节点分为3类:(1)根节点:遍历起始单元Cs,以及相邻节点数之和大于2 的节点(一般为枢纽)。(2)通道节点:用于连接两个根节点的节点。(3)分枝节点:除以上节点的节点(一般为处于凹形区域的节点)。2.2第一次求解
23、第一次求解的流程图如图7 所示。初始化集合Covi是判断是否已遍历所有单元??否否判断上一个遍历单元及其相邻单元是否满足优先条件?是选择最近单元作为选择该相邻单元作为将该单元添加至下一个遍历单元下一个遍历单元判断下一个遍历单元存在已遍历的相邻单元?是计算该单元添加至CNav末端时的等效路径长度计算该单元添加至CNavi中间时的等效路径长度选择最优的添加方式以A*算法生成实际路径结束图7 第一次求解流程图Fig.7Flowchart of the first solution具体步骤如下:?步骤1生成集合CNavi=Cs,用于存储机器人先后经过的栅格,即导航点。其中,两个导航点之间的实际移动路1
24、3)径由A*算法获取。:分枝节点。步骤2 判断是否存在未遍历的单元,若不存在,则跳转至步骤11。步骤3判断上一个遍历的单元CLast和它的相邻单元CNear是否满足优先遍历的两个要求:(1)CLa s t 与CNear均为通道节点;(2)单元CNear未遍历。若是,则将CNear作为下一个待遍历的单元CNext;若否,则选择最近单元作为CNext(即贪心算法)。最近单元定义为:以式(7)计算当前排列在集合CNavl末端的栅格,其到某一单元的首端或末端栅格的等效路径长度即为所有未遍历单元中的最小值。执行此步骤的目的是,使得处于同一通道的单元优先集中完成遍历,否则遍历路径可能发生割裂,出现如图8(
25、a)CNaM末端否第12 期所示的规划,导致不必要的转向;而图8(b)所示则采用了优先遍历的规划路径,其路径长度和转向次数得到了降低。吴靖宇等:基于改进单元分解法的全覆盖路径规划3953图10 为第一次求解结果(图中黑色三角形代表路径终点,下同)。该路径的长度为116 个栅格,转向次数为48。图10 第一次求解结果(a)未采用优先遍历(a)Without priority traversal图8 优先遍历效果示意Fig.8Schematic diagram of priority traversal effect步骤4判断CNex是否存在已遍历的相邻单元。若否,则跳转至步骤5;若是,则跳转至步
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 改进 单元 解法 覆盖 路径 规划
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。