2.3.3   全覆盖待解决的问题13

3   子区域行走方式 15 

3.1  往复式行走15

3.2  内螺旋式行走16

3.3  往复和内螺旋比较17

4  具体路径规划步骤18

4.1  问题阐述18

4.2  参考算法描述19

4.3 实际的算法步骤22

4.4 算法有效性23

5  仿真结果24

结论 28

致谢 29

参考文献30

1  引言

随着科学技术水平的不断提高，各种机器人和传感器技术开始进入突飞猛进的发展时代，越来越多的技术被运用到实际生活之中，使人们的生活越来越便捷。在诸多的前沿科学之中，路径规划[1]对于移动机器人和传感器是十分重要的，为它们能顺利的到达目标地点完成任务提供的前提和基础。其中又有一类全覆盖路径规划，对于实际生活中的很多技术实现都有很重要的作用，具体的应用领域有室内清洁机器人、灾后救援机器人、扫雷机器人、矿藏探测机器人等等[2-5]。

由于此种技术有着广阔的科技价值和市场前景，许多领域的学者都在研究着全覆盖路径规划的课题，众人的智慧碰撞产生出了许多的规划思维和方法。

清洁机器人是较早应用全覆盖路径规划算法的且实践较多的机器人，研究这个领域的专家总结了许多全覆盖路径规划的优缺点，如无环境模型的规划中的随机工作和随机加局部遍历规划；有环境模型的路径规划中的栅格法、基于生物激励的路径规划算法、模板模型法；并对全局路径规划需要解决的问题进行了总结和展望[6]。

    最近几年，设计能够通过划分工作给不同执行器来完成复杂的任务的多智能系统引起了学者们的广泛研究[7][8][9]。这些任务之一就是覆盖控制，它要求多功能机器或小车在短时间内覆盖或扫描一个给定的区域。

在参考文献[10]中我们解决了在机器人在有限信息交互下动态覆盖的问题，它的目标是在有限的时间里覆盖一个给定的一个平面 上的多边形区域。解决方案包括让机器人沿着初始多边形分割而得的小多边形的质心移动。在本文中我们解构多边形的结构是为了能解决持续覆盖控制的问题，当有N个机器人同时周期性重复覆盖一个给定的区域，平面上的每一个点都应当在 时间内至少被一个机器人覆盖。假设所有机器人初始时是连通的。一个机器人的邻居是那些位于其检测半径之内的机器人。因此机器人能接收一连串的交互计划用来不断达成任务的分配，移动到它们的子任务的出发点，再重复完成子任务。这提供了一种很容易实现的确定性的解决方案，例如持久区域拒绝[11]，出现的目标在大多数T*的时间单位后才被检测到。

（1）静态覆盖或部署：在这种方法中首先给出一个密度函数，表明一些领域比另一些更重要。传感器/代理在梯度攀登方法的基础上确定最佳的位置，直到达到的优化配置能最大限度地提高一些集体反馈函数的值[12][13]。在文献[12]中，作者提供了一种利用Voronoi分区以使既定势函数的值最大化的覆盖方案。机器人把给定的区间分成很多子区域，每一个机器人向子区域的质心移动，增加传感半径以保证区域的完全覆盖。如此重复直到形成一个稳定状态的分区。在文献[13]中，提出一种最佳部署方案，其中机器人只用本地传感器信息来使一个势反馈函数最大化。

（2）动态覆盖：在这个方法中机器人移动是为了增加在规定时间内区域的覆盖度直到区域内的每一个点都以预设的平均覆盖水平 覆盖，在文献[14]和[15]中称为有效覆盖。代理尝试使误差函数最小化，该函数表示在时间t内，通过沿负梯度移动该地区已被覆盖。