苏州科技学院学报（工程技术版） 第 !, 卷 第 ! 期 4$ 56 789:;<=9>? 56 @A9;8A; B8C ’;AD85E5F? 56 @GHD5G I5E$ !, J5$ ! "&&) 年 # 月 LB<$ "&&) （K8F98;;<98F B8C ’;AD85E5F?） 基于子区域的机器人全覆盖 路径规划的环境建模 王 俭 !， 赵鹤鸣 "， 陈卫东 # （!$苏州科技学院 电子与信息工程系，江苏 苏州 "!%&!!；"$苏州大学 电子信息学院，江苏 苏州 "!%&&!；#$上海 交通大学 自动化系，上海 "&&&#&） 摘 要：研究了移动机器人在含障区域内完成全覆盖行走的优化环境建模。将子区域内行走路线、 区域分割和子区域衔接顺序三方面 结 合 ，进 行 总 体 优 化 的 考 虑 。 提 出 用“双 线 扫 法 ”完 成 区 域 的 分 割，选择“向内螺旋式”行进作为子区 域 内 部 行 进 路 径 ，构 造 整 个 待 覆 盖 区 域 全 连 通 图 模 型 ，用 旅 行 商问题解法求最优的有向全连通图，取得了令人基本满意的结果。 关键词：全覆盖；路径规划；子区域；分割；连通图 中图分类号：’( ")"$* 文献标识码：+ 文章编号：!*,"-&*,.（"&&)）&!-&&,"-&) 所谓全覆盖，是指机器人走遍区域内除障碍物以外的全部地方，其典型应用如吸尘器、收 割机、清扫车、搜索机器人等。优化的全覆盖路径规划描述为：机器人从起点出发，以尽可能短 的路程（或时间）完成整个区域的覆盖工作并返回出发点。关于含障区域全覆盖路径规划问题 的研究实际上分为子区域分解、子区域内部行走路径和子区域衔接顺序三个问题并已有一些 分别的探讨/!0)1。本文研究基于子区域的含障区域全覆盖路径规划优化建模。笔者认为，全覆盖 路径规划问题的优化解决不仅依赖于上述三个问题的分别优化，更取决于着眼于全局考虑的 优化。在确定子区域内部最优行走路线为“向内螺旋式”的基础上，提出子区域分割的“双线扫 法”，并在此基础上构造全连通图，从而建立整个区域的环境模型。对一个简单含障区域建立模 型后，用计算机对样本进行的全覆盖路径规划初步仿真结果表明，本文方法是可行的。 ! 基于全局优化考虑的建模方案概述 !$! 子区域内部行进路径 子区域内部行进路径采用从长边开始的“向内螺 旋 式 ”（图 !），其 路 程 最 短 ，转 弯 次 数 最 少 ，还 可 避 免 “向外螺旋式”和“往复前进式”的边缘效应（图 "），易 于无遗漏地完成覆盖。同时，“向内螺旋式”的终点位于子区域重心附近，远离障碍物，从而在多 子区域覆盖问题上，显出利于机器人在子区域间的衔接行走。 ——————————————————— /收稿日期1 "&&)-&"-"% /基金项目1 苏州科技学院科研基金资助项目2&#&#)&* /作者简介1 王 俭（!.%*-），男，安徽蚌埠人，副教授，硕士。 

王 俭等：基于子区域的机器人全覆盖路径规划的环境建模 -$ 第 ! 期 !"# 区域分割 子区域分割采用适用于平行四边形障碍物且其边大多平行于 区域边沿的“双线扫法”：用两根想象中的交叉长线分别“扫”过整 个待覆盖区域，即分两次完成子区域分割任务（见图 $），不刻意追 求子区域本身覆盖的高效率，避免其它方法%$，&’限制内部行走为往 复前进式的局限或人为划分出过小的子区域。 !"$ 构造全连通图 图 $ 双线扫法 预先根据区域中障碍物位置情况把区域分为若干种模式。把子区域重心作为该子区域对 应节点的位置，把重心间的距离作为对应节点间连线的长度，识别分割结果所属模式从而确定 所有节点对之间的连线长度，最后构造出整个待覆盖区域的全连通图———距离矩阵模型。这 样，机器人对整个区域的覆盖任务就成了在覆盖各个子区域内部的同时走遍所有节点。 !"& 子区域衔接顺序 普遍的做法是试探法%#’：机器人离开已被覆盖的子区域前，任选一个紧邻的未覆盖子区域 作为目的地。当不存在紧邻的未覆盖子区域时，按原路退回，直到有紧邻的未覆盖子区域供选 择为止。显然，试探法效率低。 实际上，已建立的全连通图模型与旅行商问题（()*）%+，,’具有很大的相似，可用解决 ()* 的 方法求优化的有向连通图。 # 构造全连通图 这里以一个含两障碍物的简单矩形待覆盖区域为例，说明本文方法的应用。 #"! 建模步骤 （!）首先根据区域中障碍物的位置情况把区域分为九种模式（见图 &）。 （#）生成环境地图。由待覆盖区域（!! ，"$ !# 个数值生成坐标式环境地图（见图 +）。 ）、两个障碍物（!# ，!, ，"! ，", ，!$ ，"# ）和（!& ，!+ ，"& ，"+ ）共 图 & 九种分割模式 图 + 实例所用的待覆盖区域 （$）分割区域。先将待覆盖区域分成 + 个并肩直立的等高不等宽区域，如第四个等高不等 ，!+ ）；再将 + 个等高不等宽子区域进一步分割成 - 个 ）。当障碍物与区域边缘的距离小于机器人本体宽度 宽区域用其左右两边的横坐标表示为（!& ，"& 子区域，比如，第五个子区域为（!& $ 倍时，子区域个数会少 - 个。 ，!+ ，"! #、$、+、, 面积相对大小的一维向量（"! "&# ）比照，确定分割结果模式。 ，"+# （&）识别分割模式。对于具体的区域分割结果，判断其属于哪一个模式。用可表征子区域 ， ，"$# ）和表征九种模式的一维向量（"!# ，"## ，"$ ，"& ，"# ，"+ ，", ，",# （+）确定节点位置和节点间距离。由于机器人的终点总位于子区域重心附近，所以，节点位 

%# 苏州科技学院学报（工程技术版） !""# 年 置确定为子区域重心。节点间衔接顺序具有随机性，即每个节点的“前”和“后”是随机的，故取 重心间的距离为节点间的距离。 （$）确定不相邻但无阻隔节点。在实际问题中机器人可以从一个子区域路过与之相邻的子 区域，进入另一个与之并不相邻的子区域开始新的覆盖工作，而把路过的与之相邻子区域的覆 盖工作留在以后的顺序中。所以把不相邻但也没有被障碍物阻隔的节点也用两者之间距离长 度的线段连接起来。 （%）确定绝对不相邻节点之间距离。“绝对不相邻节点”指被障碍物完全阻隔的节点。用足 够大的数值来代替它们之间的距离，这里“足够大”含有两方面意义，一是该两节点的距离要大 到机器人不愿意选择这条路线行走，二是该两节点的距离不能太大到使旅行商问题发生衍变。 在本文中，挑选距离最远的两个节点间距离的 & 倍来作为完全不相邻节点之间距离值。 图 $ 是对一个模式九建立的全连通图———距离矩阵模型：’，!，(，#，&，$，% 共七个子区域， 其中子区域 ! 等于子区域 (，子区域 & 等于子区域 $。 !)! 主要数据结构 图 $ 模式九全连通图00距离矩阵 ） ’+$ ，&*’，!，…，,，表示九种模式的特征位置；’( ，表示区域及障碍物边界的横坐标；$ *（%# ，表示区域及障碍物边界的纵坐标； （") ），(*’，!，…，%，代表子区域；- ( ，%+ ，0 *’，!，…，%，1*’，!，…，%，表示子区域重心 ） ’+$ ，"* ，", !*（"# ） $ &*（%#& ’+$ （"-( ，%-( ），(*’，!，…，%，表示子区域重心；.*（/01 间距离；2*（3 01 ） %+% ） %+% ，0*’，!，…，%，1*’，!，…，%，表示行走顺序。 ( 仿真及结果 仿真样本取数值如图 $ 的一个模式九的模型。连续运行 仿真程序 (" 次，其中，!( 次收敛到合理解，% 次发散。合理解 有 图 % 中 的 四 种 。 路 径 4、5、6、/ 的 长 度 分 别 是 ,),&、’")’、 ’")%%&、’")##&。在 (" 次结果中，最优解 4 出现 ’& 次，占总次 数的 &")".，次优解 5 出现 ’! 次，占总次数的 #")".，最优解 和次优解总共占总次数的 ,")".；解 6 和解 / 总共只占总次 数的 ’")".。 图 % 模式十算法收敛的四种路径 运行仿真程序 ’" 遍，找出每遍中最优解最早在第几次 出现，得到表 ’。从表 ’ 可见，每一遍至少在前 ( 次 之内，肯定出现最优解。 实际仿真的在待覆盖区域中各子区域内部的行 走路线如图/。 图 / 各个子区域内部的行走路径 表 ’ 模式十算法最优收敛路径最早出现次 

王 俭等：基于子区域的机器人全覆盖路径规划的环境建模 RN 第 ! 期 " 结论 （!）本文提出的分割区域的“双线扫法”，不刻意追求覆盖单个子区域在理论上的效率，而 是注意具有体积的实际机器人的覆盖行为的有效性。（#）把子区域内部行进路线与子区域间衔 接两者结合考虑，提出既要考虑子区域内部用时最短，又要便于完成子区域衔接的原则。依据 该原则，选择“向内螺旋式”行进作为子区域内部行进路径。（$）为得到类似于旅行商问题的全 连通图，将相邻节点和不相邻但无阻隔节点均按真实距离连接、有阻隔节点按最大距离适当倍 数连接的处理办法，被结果证明是合理的。（"）按照本文方法进行子区域分割后的整个待覆盖 区域模型，把旅行商问题的求解方法应用于全覆盖路径规划，能快速得到基本令人满意的解。 参考文献% &!’ ( )*+,-./0 1 2345678 95 :.;:5*6. <=:55-5> :5. 5:;->:/-35 :<<73:*+ 437 :?/353,3?@ *=6:5-5> 73A3/ 3<67:/-35@&B’8 C5 CDDD E F)B C5/675:/-35:= 13546765*6 35 C5/6==->65/ F3A3/@ :5. )G@/6,@0 !HHI0J#K%!#$LM!#$N8 &#’ 2 1+3@6/0 O O->5358 13;67:>6 <:/+ <=:55-5>% /+6 A3?@/73<+6.35 *6==?=:7 .6*3,<3@-/-35 &1’8 O73*66.-5>@ 34 /+6 C5/675:/-35:= 13546765*6 35 P-6=. :5. )67;-*6 F3A3/-*@0 Q6*6,A67 !HHR8 &$’ S6@=6G 2 2?:5>8 T6 :=>37-/+,@&1’8 O73*66.-5>@ 34 /+6 #LL! CDDD C5/67V 5:/-35:= 13546765*6 35 F3A3/-*@ :5. 9?/3,:/-358#RM$#8 &"’ F6@@6== F 90 W+-6= Q0 X:*Y:GM@-, 98 F6*7?-/-5> @U:7, 73A3/@ ?@-5> *3.6. 3.37 /7:-=@&1’8 O73*66.-5>@ 34 /+6 !@/ 13546765*6 35 P-6=. :5. )67;-*6 F3A3/-*@0 9Z[0 1:5A677:0 9?@/7:=-: Z3;0 !HHR0"R#M"R\8 &N’ 胡守仁，余少波，戴葵8神经网络导论&X’8长沙：国防科技大学出版社，!HH$8!$IM!"!8 &\’ 徐秉铮，张百灵，韦岗8神经网络理论与应用&X’8广州：华南理工大学出版社，!HH"8!N\M!\L8 9 )?AM76>-35 ]:@6. X6/+3. 34 ]?-=.-5> D5;-735,65/:= X3.6= 34 13,<=6/6 13;67:>6 O:/+ O=:55-5> 34 X3A-=6 F3A3/ S9Z( B-:5!， ^29T 26M,-5>#， 12DZ S6-M.35>$ （!8Q6-5667-5>0 [)W)0 )?_+3? #!NL!!0 1+-5:‘#813==6>6 34 D=6*/735-* C5437,:/-350 )?_+3? [5-;67@-/G0 )?_+3? #!NLL!01+-5:‘ $8 Q6+:- B-:3/35> [5-;67@-/G0 )+:5>+:- #LLL$L0 1+-5:） !"#$%&’$( W+-@ <:<67 @/?.-6. /+6 ,6/+3. 34 A?-=.-5> 65;-735,65/:= ,3.6= 34 ,3A-=6 73A3/ -5 : 76V >-35 U-/+ 3A@/:*=6@8 C/ /33Y /+6 U:=Y-5> <:/+0 76>-35 .-;-.-5> :5. @?AM76>-35 =-5Y-5> -5/3 :**3?5/ /3>6/+67 /3 :*+-6;6 /+6 38 C5 .6/:-=@0 /+6 <:<67 @?A,-//6. a.3?A=6M=-56M @U66-350 *+3@6 a-5567 @<-7:= <:/+a :@ U:=Y-5> <:/+ -5 @?AM76>-350 ,:.6 :.b:*65/ >7:<+ /3 .6@*7-A6 /+6 .-;-.6. 76>-350 :<<=-6. /+6 ,6/+3. 34 @3=;-5> /7:;6=-5> @:=6@,:5 <73A=6, /3 3A/:-5 36 <:/+ <=:55-5>8 )*+ ,-%.#( *3,<=6/6 *3;67:>6‘ <:/+ <=:55-5>‘ @?AM76>-35‘ .-;-.-5>‘ :.b:*65/ >7:<+