基于模型约束的覆盖规划算法研究

李 宁， 高建峰， 何亚丽， 罗 涛， 郭 文， 赵洪雷， 陶 进

(中国北方车辆研究所， 北京100072)

覆盖规划算法[1]广泛应用于自动农耕、室内清扫、战场排雷、自动割草等自主作业机器人领域，旨在解决设定区域内的机器人的自主遍历问题，保证区域覆盖和最小遍历等要求.在国外，以具体应用为导向的相关赛事，在一定程度上推动了覆盖规划算法相关的自主技术的发展.如，美国为了促进智能割草机器人的研发，从2004年起，每年都要举行一次自动割草机器人比赛(Annual Autonomous Lawnmower Competition)，在比赛中给定规则的作业区域，完成割草机的自主作业，目的在于实现智能割草机器人的全自主运行，进而提高自主导航在无人化农业领域的应用.

在目前商业化中具体应用的智能割草机器人或者扫地机器人，通常为小型平台，以万向轮底盘设计为主，可以灵活转动.此类平台在设计覆盖规划算法的过程中，不涉及复杂的车辆运动学约束，路径规划算法只需要解决区域内完全遍历和最小遍历即可.然而，对于大型的户外作业场景，如机场草坪的自主割草作业、农作物自主收割等，考虑到安全性和实用性，一般选用大中型轮式车辆平台作为底盘，传统的不考虑车辆运动学模型约束的覆盖规划算法存在一些明显未考虑因素，如车辆最小转弯半径约束、连续转向及大角度转向等问题，都会对实际作业覆盖率和可操作性产生影响.特别是车辆本身的最小转弯半径问题，需要考虑在路径规划中，路线中小于最小转弯半径的区域，在实际作业中无法遍历到.

本研究正是基于户外场景的大中型自主平台的覆盖式路径规划展开.在覆盖规划算法设计中，将车辆模型约束作为一个重要的考虑因素，在尽量保证最小遍历的情况下，实现对于区域内的覆盖式遍历.本研究仅对相对独立的一个作业区域进行覆盖式遍历，对于存在大型建筑物分割的场景，默认已经采用胞元法[2]进行了区域划分，同时在规划路线时，不考虑内部障碍物的存在.

1 算法概述

本研究以大型户外遍历作业为覆盖规划算法的应用场景，如机场草坪的自主割草作业，以车辆模型作为约束，展开覆盖规划算法研究.对于规则区域内不考虑车辆运动学模型约束的平台(如基于万向轮设计的扫地机器人)而言，像一般的直线循环推进、中心辐射扩展等路径覆盖算法即可以满足实际作业的需要，如图1(a)和(b)所示.对于稍复杂一些的场景，如室内扫地机器人，通过地图重建技术[3]将障碍物分布信息保存在先验地图中，利用基于生成树的覆盖式路径规划算法[4]完成遍历，如图1(c)所示.

图1 常见覆盖规划算法

然而，本研究面向大型户外作业场景，以基于车辆运动学模型的大中型自主平台作为底盘控制系统，需要考虑车辆运动学模型约束，同时算法需要对不规则作业区域具有通用性.因而，在算法设计中，通过对作业区域外围的几何分析，采用先螺旋式收缩遍历，将大部分区域遍历，如图2(a)所示.当内部区域受车辆模型约束，难以继续遍历时，如图2(a)中粗线圈出的区域，结合优化的直线循环推进覆盖算法，完成内部区域遍历，如图2(b)所示.完整的覆盖规划结果如图2(c)所示.

图2 基于模型约束的组合覆盖规划算法

2 基于模型约束的组合覆盖规划算法

图3 组合覆盖规划算法流程图

图4 不规则多边形区域覆盖规划算法对比

法，对内部未遍历区域采取优化的直线循环推进覆盖法，从而完成整个作业区域的遍历，结果如图4(c)所示.遍历过程中规划路线的生成受车辆模型约束，最大程度保证实际作业遍历的有效性.具体算法如下文所述.

2.1 作业区域几何特征分析

根据序列点的排序η，结合向量积法对作业区域各个顶点的凹凸性进行判别，如公式(1)所示.

(1)

2.2 螺旋式收缩遍历

(2)

ω=Pnew-P1，

(3)

(4)

图5 螺旋式收缩覆盖法

,

(5)

,

(6)

.

(7)

(8)

(9)

2.3 优化的直线循环推进覆盖法

以上一步骤中最后一次有效遍历点向前回溯4个规划点形成内圈遍历区域Qs1s2s3s4，如图6(a)中粗线区域所示，图6(b)为其放大显示.为减少车辆的频繁大角度转向，以四边形的最长边为基准，进行直线循环推进，完成内部区域遍历.具体算法如下所述.

图6 直线循环推进覆盖法及结果

(10)

其中，Δd=w.

(11)

(12)

(13)

其中，PD'为满足式(11)和式(12)的非问题解.

顺次连接外圈点和内圈点，即得到组合式全覆盖路径规划结果，如图6(c)所示.

图7 规划路线平滑处理

3 试 验

本研究提出的基于模型约束的覆盖规划算法在图8所示的自主割草机平台上进行了算法测试与应用.该平台底盘为六轮设计，六轮独立驱动，前后轮均能转向，中间两轮随动，车辆平台的相关具体参数如表1所示.

图8 自主割草机平台

表1 自主割草机平台参数

参数名称参数值物理尺寸 (长×宽)/m3.4×1.7作业宽度 (割草盘宽度)/m2.8轴距/m1.15最大曲率/m-1±0.25最小转弯半径/m2.3最大转向角/(°)±30转向控制精度/(°)±1最大作业速度/(km·h-1)10

根据车辆平台参数，设定的收缩幅度ω=

2.5 m.由于在路线规划中考虑了车辆模型的约束，避免了大角度转向和连续转向问题，区域内的覆盖规划问题简化为按照覆盖规划路线进行跟踪控制的问题.本试验中采用简易二自由度汽车模型作为轨迹跟踪控制的预测模型，并利用纯跟踪算法[6]进行轨迹跟踪控制，原理如图9(a)所示.

图9 轨迹跟踪控制

图10 组合覆盖规划的实际遍历效果

4 结 论

本研究提出的基于模型约束的覆盖规划算法，以面向实际工程应用的算法为开发依据，可以有效应用于基于大中型轮式车辆模型的自主作业场景，如自主割草机、谷物收割机等，能够有效适应不同几何形状作业区域的路径规划，理论上具有完备性，可以满足覆盖式作业的实际需求.

由于添加了车辆模型约束及采用的组合式覆盖规划策略，在两种覆盖规划算法相结合时，造成了部分区域的重复作业，如图4(c)所示.另外，本研究未将已知障碍物的避障规划控制考虑在内.对于作业区域内的已知固定障碍物，可以作为先验信息，与路径规划相结合，进一步优化作业路线，减轻实际作业过程中的障碍物检测和避障控制方面的传感器配置和算法设计负担.在后续的研究中，我们将结合以上存在的问题，进行进一步的深入研究.