黄月琴，罗兵，邓辅秦,，李伟科，杨勇

（1.五邑大学 智能制造学部，广东 江门 529020；2.深圳市杉川机器人有限公司，广东 深圳 518000）

扫地机器人是目前应用较广泛的机器人产品，对全部清扫区域的全覆盖路径规划，是扫地机智能化研究的内容之一.该优化问题在遥感拍摄、大面积对象自动检测、自动喷涂等自动控制技术应用中是共性问题，统称为全覆盖路径规划（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路径转弯次数更少.最近，Vasquez-Gomez等人[5]提出了旋转卡壳路径规划方法（Rotating Calipers Path Planner，RCPP），可以快速找到凸多边形的最佳BFP，比其他方法更为高效.RCPP方法算法复杂度低，适合在嵌入式设备中使用.

在单元间的转移路径规划方面，文献……