五邑大学学报（自然科学版）
JOURNAL OF WUYI UNIVERSITY （Natural Science Edition ）
第35卷 第2期 2021年 5月
V ol.35 No.2 May 2021
文章编号：1006-7302（2021）02-0051-08
黄月琴1
，罗兵1
，邓辅秦
1,2
，李伟科1，杨勇2
（1.五邑大学 智能制造学部，广东 江门 529020； 2.深圳市杉川机器人有限公司，广东 深圳 518000）
摘要：全覆盖路径规划是智能扫地机器人重要的功能之一，但是基于单元分解方法的全覆盖路径规划对复杂的凹多边形环境分解过于细碎，规划的路径转弯多、调头多，优化效果常未达到最佳. 结合扫地机器人的实际应用，在代价函数中加入了转弯和调头的开销；在单元分解时保留可合并规划的凹区域不再分解；单元内路径优化考虑了相邻区域的统一规划和单元间转移，单元间采用全搜索结合蚁算法得到最佳转移路径，实现了可适用于复杂环境的全覆盖路径性能优化. 仿真实验结果表明该方法有效减少了路径的转弯、调头次数和合计总开销，提高了扫地机器人的全覆盖清扫效率. 关键词：全覆盖路径规划；单元分解；全局优化；代价函数；扫地机器人
中图分类号：TP242.6 文献标志码：A
Complete Coverage Path Planning for Intelligent Sweeping Robot
HUANG
Yue-qin 1
, LUO
Bing 1
, DENG
Fu-qin 1,2
, LI
Wei-ke 1
, YANG
Yong 2
(1. Faculty of Intelligent Manufacturing, Wuyi University, Jiangmen 529020, China;
2. Shenzhen 3irobotix Co Ltd, Shenzhen 518000, China)涂料用润湿分散剂
Abstract: Complete coverage path planning is one of the essential functions for intelligent sweeping robot. However, cell decomposition method excessively decomposes complex concave polygon environment and ignores turning degrade, so the optimization effect is often not the best. Considerin
g the practical application of sweeping robot, improvements in three aspects are proposed that the cost function is added with the cost of turning, concave areas which can be combined planning with adjacent area are retained no decomposition, and global planning of cell path with transfer between cells are considered by exhaustive search and ant colony algorithm, which can be applied to whole complex environment with better performance. Simulation experimental results show that the proposed approach can effectively reduce turning and total cost, make sweeping robot complete coverage more effectively.
Key words: Complete coverage path planning; Cell decomposition; Global optimization; Cost function; Sweeping robot加香
收稿日期：2020-12-09
基金项目：广东省教育厅重点领域专项项目（2019KZDZX1025）；江门市科技局重点项目（江科〔2020〕159
号）；深圳市科技计划资助项目（KQTD2016113010470345）
作者简介：黄月琴（1993—），女，河南驻马店人，在读硕士生，研究方向为机器视觉技术；罗兵，教授，博
士，硕士生导师，通信作者，研究方向为数字图像处理、人工智能.
五邑大学学报（自然科学版）2021年52
扫地机器人是目前应用较广泛的机器人产品，对全部清扫区域的全覆盖路径规划，是扫地机智能化研究的内容之一. 该优化问题在遥感拍摄、大面积对象自动检测、自动喷涂等自动控制技术应用中是共性问题，统称为全覆盖路径规划（Complete Coverage Path Planning，CCPP）[1-2]. 对CCPP 问题的解决方案主要分为3类：栅格地图法、单元分解法和两者相结合的方法[3-6]. 由于栅格地图法还有待解决移动死区问题，单元分解方法是目前解决CCPP问题效果最好的方法[7-9].
单元分解方法先将一个有界单元分解为一组互不重叠且不包含障碍物的单元，再进行单元内路径优化，最后进行单元间转移路径优化. 其中单元分解有梯形分解法、布氏单元分解法（Boustrophedon Cellular Decomposition，BCD）和莫尔斯分解方法等，BCD能有效减少分解后的单元数目[10-13]. 文献[7]使用BCD在矿区检测应用中分解矿区地图后再利用神经网络进行路径规划，得到优化的CCPP路径.
在单元内的路径规划中，往复式路径（Back and Forth Path，BFP）能适应任意凸多边形且计算简单而被广泛应用. 为了寻单元内最优BFP路径，Huang[3]提出了最小倾向和方法（Minimal Sum of Attitudes，MSA），通过寻平行于某一条边界的扫描线，使得BFP路径转弯次数更少. 最近，Vasqu
ez-Gomez等人[5]提出了旋转卡壳路径规划方法（Rotating Calipers Path Planner，RCPP），可以快速到凸多边形的最佳BFP，比其他方法更为高效. RCPP方法算法复杂度低，适合在嵌入式设备中使用.
在单元间的转移路径规划方面，文献[14]基于蚁算法和遗传算法的优化方法被采用，设计了玻璃幕墙清洁机器人的CCPP. 但现有的单元间转移路径优化方法没有考虑单元内路径优化，而且单元内BFP路径有多个较优解时未考虑不同单元起始点，这些缺点降低了全局优化效果.
vobu基于单元分解的CCPP在单元内、单元间路径规划时已取得了较好的效果. 但对于复杂形状的凹区域划分过于琐碎，未考虑相邻区域的总体规划[13]. 另一方面，在扫地机器人的实际应用中，机器人的转弯和调头都会影响其移动速度，需要额外能耗和时间[15]. 为此，本文将在3个方面进行改进：首先在路径规划代价函数中加入转弯和调头的代价；其次在单元分解时，对于可以和相邻区域统一规划的凹区域不再分解；单元内路径规划兼顾单元间的转移路径规划，全局优化结合全搜索和蚁算法.
1 路径代价函数和地图单元分解的改进
本文以深圳市杉川扫地机器人为研究对象，实验场地为室内封闭环境. 机器人直径34.5 cm，形状为圆形. 在此应用条件下设计了符合扫地机场景的实际代价函数，评估覆盖路径开销. 另外，在仿真地图环境中，单元分解数目过多时采用合并相邻且尺寸小的单元.
1.1 路径代价函数改进
传统路径优化目标只考虑路径长度最短，规划时代价函数是起点和终点之间欧氏距离[5-6]. 但在扫地机实际应用中，相同距离的直线移动和带转弯的移动所花时间和功耗均不相同，转弯前须减速，转弯后重新加速，转弯会带来更多的能耗和时间开销[15]. Theresa[4]提出综合转弯次数、机器人半径、路径偏移量和区域边界线角度的距离代价函数. 这一方法更符合实际情况，准确评估路径的总代价. 不同于无人机转弯时可以超越环境边界，扫地机工作空间是封闭环境，转弯时被限制在距离边界机器人半径的距离内. 因此，本文基于文献[4]的代价函数设计新的代价函数.
第35卷 第2期 53
黄月琴等：智能扫地机器人的全覆盖路径规划
通过实验测试发现，保持均速移动时，扫地机每次转弯的时间开销是大致相当的. 杉川扫地机移动速度为0.8 m/s ，同时移动两个扫地机器人，其中一个有一次直角转弯累计移动距离10 m ，另一个无转弯直线移动同样时间内移动了10.45 m . 类似的大量实验表明：对于0.8 m/s 移动速度的扫地机器人，每次转弯的开销可以折合为0.45 m . 类似条件下的测试也显示，调头的开销大约是0.49 m . 本文将一次转弯、调头的开销，线性折合为路径长度，折合系数分别是t 0.45 m c =/次、r 0.49 m c =/次. 系数值可根据不同扫地机器人进行调整.
通过将转弯次数、调头次数折合为移动距离的方法，将多目标优化方法转化为单目标优化方法. 代价函数如下：
暖墙t t r r in link Cost c N c N L L =⋅+⋅++， （1）
其中t c 为转弯代价系数，t N 表示转弯次数，r c 为调头代价系数，r N 表示调头次数，in L 是分解的n 个单元内的路径长度之和.
设转移路径是单元间访问路径顺序的集合{}=,1,2,3,,ij T t i j n i j =≠ 且，i 和j 代表单元序号，其中{}011223(1),,,,ij m m t -= ττττ是由m 个有向线段组成，转移路径距离就是多条转移直线路径ij t 距离之和，转弯一起合并到转弯代价中考虑.
每个单元的路径长度in ()L i 按欧氏距离计算：
in in 1()n
i L L i ==∑， （2）
link L 表示n 个单元之间的转移路径长度：
link
(1)1ij m i i t T i L -∈=⎛⎫
= ⎪⎝⎭
∑∑τ. （3） 通过代价函数的改进，在路径优化中，不仅追求路径长度最短，还会寻转弯、调头次数更少的路径.
1.2 地图单元分解的改进
传统单元分解原则是将凹多边形分解为多个凸多边形，然后在凸多边形内分别进行路径规划，最后在单元间规划转移连接路径[3,5]. 这样虽然可以实现路径长度优化，但会导致分解过于细碎、路径转弯多、调头多，难以达到总体最优，如图1-a. 实际上，很多凹多边形仍然是可以进行路径规划寻优的. 为此，我们改进为：对于存在一组平行线路径可以全覆盖的凹多边形，不再分解，这样将减少分解单元数量，原多个相邻单元总体进行路径规划将减少路径转弯、调头次数，连接路径也缩短，如图1-b.
a.传统单元分解方法及路径规划
b.本文单无分解方法及路径规划
图1 不同单元分解方法对比及路径规划效果
五邑大学学报（自然科学版） 2021年
54 图1中的虚线是单元分解线，传统方法将图1的凹多边形分解为3个矩形，各单元采用式（1）代价函数进行路径规划，如图1-a ，路径多了一段两个单元间的连接线，转弯次数为21次. 本文方案不再分解该凹多边形，路径如图1-b 所示，有一段重复路径，转弯次数为14，调头1次. 两种方案的代价计算结果见表 1. 可见，避免过于细碎的单元分解可以减少转弯、调头次数，路径规划效果更优.
表1 不同单元分解方案的路径规划结果对比
方案
路径长度/m
转弯次数
钢架桥调头次数
总代价/m 传统单元分解方法
72.1 21 0 81.55 本文方案
71.8
富氧设备14
1
78.59
2 路径优化
2.1 凸多边形区域的路径规划
对于凸区域路径规划，文献[5]中的RCPP 方法可以快速求得无人机场景中的最佳BFP ，但是不适用于扫地机场景，而且寻优时路径代价未计算转弯次数. 故本文采用RCPP 时，将路径点限制在边界内，并使用公式（1）作为代价函数选择最优路径.
被分解后的区域中包含凹、凸单元，记多边形{},Q =V E ，{}1,2,,V n = 是顺时针的凸多边形顶点集合，{}(1,2),(2,3),,(1,),(,1)E n n n =- 是由V 中元素组成的边. 多边形的区域为()A Q ，设扫地机的一条路径s 的覆盖区域为()C s . 对于2D 凸多边形的一条覆盖路径ρ需满足()(Q)C A ρ⊆. 具体算法步骤如下：
1）计算凸区域的顶点集合{}Q V =的对踵点集合{}11(,),,(,)n n A i j i j = ；2）对于步骤1）中A 中的每对对踵点，使用顺时针卡壳和逆时针卡壳分别计算出两条BFP ，返回总长度最短的路径；3）针对A 中对踵点下的路径，根据式（1）选择长度最短的路径作为凸区域的BFP ；4）获得全覆盖凸区域的路径ρ.
步骤1）中的对踵点对是凸多边形上的一对顶点，过这对点的一组平行线可以将凸多边形夹在这两条平行线中间，或落在平行线上. 图2展示了该凸多边形的6对对踵点和对应BFP. 图中的虚线表示穿过对踵点的平行线，图2-a 中路径起始于标号（0,4）的边，向垂直于（0,4）边往2顶点的方向移动.
步骤2）计算每对对踵点(,)n n i j 的BFP 长度，分别使用顺时针RCPP 和逆时针RCPP 方法，即过该对踵点的平行线对寻首次与多边形接触的边，这条边称为基线. 顺逆旋转得到的基线分别记为11(,1)b b +和22(,1)b b +，而路径远端的顶点为相应的对踵点1a 和2a . 因此一对对踵点有两种BFP. 尽管是同一个凸区域，不同方向的RCPP 方法得到的规划路径长度会有不同，在保证覆盖率的情况下，路径长度短的更适用于能量有限的扫地机. 因此，保证每一个分解后的单元内路径最优，比较1d 和2d 的大小. 两者距离点到直线公式和最短路径决策如式（4）和（5）. 计算图2的每对对踵点的路径总代价分别为948.48 m 、985.09 m 、1072.18 m 、1072.67 m 、995.82 m 、949.39 m ，选择代价最小的路径作为该凸边形的覆盖路径.
11112222
dist((,1),)
dist((,1),)d b b a d b b a =+⎧⎨
=+⎩， （4）
第35卷 第2期 55
黄月琴等：智能扫地机器人的全覆盖路径规划
12111222,(,1)
,(,1)
d d b b d d b b ≥+⎧⎨
<+⎩基线为基线为. （5）
2.2 凹多边形区域的全覆盖路径规划
凹多边形区域的覆盖路径规划采用直接法（Direct Method ，DM ），算法描述如下：
1）初始化凹多边形的上下边界点集1122{(,),(,),,(,)}n n C x y x y x y = 、1122{(,),(,),,(,)}n n F x f x f x f = 、运动方向向下和扫地机半径r ；
2）单元的最左端线段L 向右偏移r ，L 的横坐标为current lef t x x r =+. 运动方向向下，此时路径ρ中加入路径点current current current current (,),(,)x y r x f r -+，更改运动方向向上. 若方向向上路径ρ中加入路径点
current current current current (,),(,)x f r x y r +-，更改运动方向向下；
3）位于current x 的扫描线继续向右平移2d r =. 若向下运动，路径ρ加入路径点集合
current current current+1current+1{(,),(,),,x f r x f r ++ current+d current+d (,)}x f r +，更改运动方向向上. 若向上，路径ρ加
入current current current+1current+1{(,),(,),,x y r x y r -- current+d current+d (,)}x y r -，更改运动方向向下. 更新current x ；
4）重复步骤2）直至L 到达单元的最右端right x ；5）若为向右运动，路径为ρ. 若向左，逆序排列路径点；6）获得覆盖凹区域路径ρ. 2.3 单元间的统一优化及转移路径优化
通过以上两节可以获得单元内的优化路径，但各单元内路径优化没有考虑单元间的转移连接路径. 特别是当单元数目较多时单元间的转移路径长度对全覆盖的路径总长度影响更大. 图3展示了不同的路径组合产生不同的路径代价，图3-d 的路径代价最小，与代价最大的图3-a 相差141.99 m ，超过路径总长度的10%. 当单元间的转移路径选择最短的路径组合时，必然会缩短整体区域的覆盖路径长度.
d.对踵点
(0,4)
e.对踵点(1,4)
f.对踵点(2,4)
凸多边形；
路径； 起点； 终点
图2 凸多边形对踵点下的各种路径情况
a.对踵点(0,2)
b.对踵点(0,3) 0 4
1
2
3
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议