数学建模小组作业——扫地机器人的路径优化二〇一四年七月二十三日第10组组员：+++扫地机器人的路径策略【摘要】我们将扫地机在房间内扫垃圾的路径策略问题抽象为方格化模型，用原始给定数据做出垃圾指标矩阵Q[300*251],根据扫地机需要的行走路径进行程序嵌套，并用线性规划的方法来进行最优解的求取，然后根据建立的模型，用Matlab 进行仿真演示。

最终可以观察到扫地机在每种情况下的清扫路径。

由于墙角也会存在垃圾，因此一般情况下我们不能实现100%的清扫，所以我们在此规定清扫完95%的区域即作为合格的条件。

下面我们根据题目要求进行如下考虑：问题一经过分析我们可以将整个清扫区域划分成如图4.1.1所示的小区域，通过运用矩阵整合函数，将矩阵Q[300*251]整合成一维数组T[5]，经过固定时间间隔所对应的区域，在区域边沿随机选的扫描判断{T（1），T(2),T(3),T(4),T(5)}MAX取坐标作为运行起始点，如果检测到的最大的元素的所在区域发生了变化，则根据当前位置与随机选好的碰撞点进行路径转移，按照这种方式运行，直到达到扫地机的结束条件停止。

问题二这时扫地机每次只选择垃圾总指标最多的路径，并且每次扫描发生在扫地机与墙壁发生碰撞的时。

扫描过后，机器人可以任意选择方向，选择方向的合适程度将成为扫地机扫地效率的关键，所以我们设定某一点作为扫地机扫描的起点每次碰撞时的扫描决定下一时刻可能的转弯方向，即某个方向上的垃圾总指标Ck 最大的即为下一时刻的转弯方向。

问题三设计智能扫地机路径，保证扫地机以最短时间达到清扫要求，我们可以选取以下两种优化方向：（1）避免与墙壁进行碰撞，提高机器的灵活性；（2）提高单位长度上清扫垃圾指标总量，即提高清扫效率。

比较问题1与问题2问题1中的方案存在其合理性，问题2中则显得较为高效，比较两者发现：改变S大小可以改变地段扫地机性能。

T关键词：线性规划路径转移划分区域清扫效率目录一、问题重述 (3)二、模型假设 (4)三、符号说明 (4)四、模型建立与求解 (4)4.0 问题分析 (4)4.0.1 基本模型 (5)4.1 问题一：低端扫地机的工作路径 (6)4.1.1 模型:分区扫描模型 (6)4.2 问题二：智能扫地机的工作路径 (10)4.2.1模型：实时扫描模型 (11)4.3 问题三：扫地机的优化路径 (13)4.3.1 模型：实时扫描折线模型 (13)4.4 模型I与模型II的比较 (17)五、模型的检验 (18)六、模型的评价 (18)参考文献 (20)附录 (21)一、问题重述1.1问题背景随着科学技术的不断发展，扫地机逐步走入平常百姓家，并被越来越多的人所接受，扫地机（也称扫地机器人）将在不久的将来像白色家电一样成为每个家庭必不可少的清洁帮手。

产品也会由现在的初级智能向着更高程度的智能化程度发展，逐步取代人工清洁。

扫地机是通过电动机的高速旋转，在主机内形成真空，利用由此产生的高速气流，从吸入口吸进垃圾。

扫地机一般为半径0.2米圆盘，、运行速度一般在每秒0.25米左右，只走直线，且碰到墙壁等障碍才可转弯。

与传统的扫地机不同，智能扫地机可以通过微处理器进行现场环境分析，自动选择运行路线。

遇到障碍发生碰撞后将重新随机地选择路线，逐步进行清扫。

智能扫地机具有记忆、存储功能。

利用传感器扫描现场环境，设计运行路径并存储。

一般不能100%的清扫指定区域（如墙角部分）。

清扫后的垃圾装进机子尾部的集尘盒，再通过人工清倒垃圾。

机器在工作电压不足时会自动回到充电站充电。

1.2目标任务考虑图1的工作现场，其中点A（1,5）为扫地机充电站，区域的垃圾指标见附件1.不考虑再充电情况，有以下问题：问题一：有些低档的扫地机因为价格低廉，智能程度不高。

其工作时的路径选择方案是将现场分成若干区域（例如上下左右4个区域），并通过传感器间隔一段时间扫描现场一次，选则垃圾最多区域清扫。

假设每次扫过的区域垃圾指标值减少1。

针对附件1，估计清扫完给定区域大致需要的时间（尽量保证每个点的垃圾指标不超过1）。

问题二：智能程度高的扫地机每次可以选择清扫垃圾指标值最大的地方清扫，每次扫过的区域垃圾指标值减少1。

该机器人需多长时间才能保证清扫完该区域（区域内指标值不超过1）。

比较问题1与问题2，说明问题1中方案的合理性。

问题三：其他条件同2，如何设计扫地机的路径，保证扫地机以最短时间清扫完该区域。

二、模型的假设1、假设扫地机有充足的电量行驶完全部的轨迹，并且不会发生任何障碍；2、假设路面平坦，不会产生较大程度的偏移或者是翻转；3、假设高端的和低端的扫地机有鲜明的特点，并严格按自己的特点运行；4、假设扫地机扫过单元格一半及以上的面积时，单元格内的垃圾指标减少1；5、假设题目中给的点A始终为扫地机工作的起点；6、假设由于种种环境因素不会对扫地机速率产生比较大的影响；7、假设扫地机工作时没有人为的影响改变扫地机的轨迹；8、假设当每个点的垃圾指标不超过1时扫地机的清扫任务结束；9、假设扫地机在扫描的过程中没有额外的占用移动时间，即扫描时间不会影响最终的运动时间。

三、符号说明Y(251，100) 初始垃圾指标矩阵J(251，300) 程序中的垃圾指标矩阵（a,b）发生碰撞时刻参考点坐标（A,B）下一次发生碰撞时刻参考点坐标S间隔扫描行驶路程TS 从（a，b）到（A,B）扫地机行驶的路程T(n) 从充电点到第n个碰壁点扫地机行驶的时间经过路径的垃圾总指标CK经过路径的垃圾指标分布律PK四、模型的建立与求解4.0问题分析由问题重述可知，智能的扫地机（不管是低档还是高档）都会按0.4米的宽度以0.25米每秒进行直线运行，并且路径上都选择与墙壁碰撞后扫描计算出的垃圾指标最高点行驶，这是所有问题的共同点。

4.0.1基本模型（1）清扫区域直观图首先我们建立一个300*251的矩阵Q，并将各个单元里的垃圾指标赋入与二位矩阵组合形成一个三维数组。

如图4.0.1所示为将题目中给定的附录1导入矩阵Q后的垃圾指标空间分布图。

（2）清扫区域方格化由于扫地机只走直线，碰到墙壁后才会转弯，所以，扫地机与墙壁碰撞之后，其中k 会有180o的方向选择。

每个指向都对应着一个所在方向的垃圾总指标CK每个方向的路线标志。

（3）路径的线性规划扫地机从碰撞点到下一个碰撞点所扫过的路程如图4.0.2所示。

我们将区域分割成300*251的矩阵，每个单元存储着垃圾指标值。

通过判断点坐标是否在路径中来判断单元垃圾指标值是否减1.图4.0.1 垃圾指标分布图图4.0.2 线性规划推导条件根据图示，可以得到以下约束条件：⎪⎪⎩⎪⎪⎨⎧≤-≥-≤≥By b y A x a x 44 且 ⎪⎪⎩⎪⎪⎨⎧-+--⎪⎭⎫ ⎝⎛--≥+-⎪⎭⎫ ⎝⎛--≤4)4()(b a x a A b B y b a x a A b B y4.1问题一：低端扫地机的运行路径对于问题一，低端扫地机需要对区域进行分区且不能时刻扫描计算垃圾指标值，总是经过一段规定的时间后，才会重新规划路线，没有进行下次扫描，则在当前判断垃圾指数最高的区域随机清扫，我们需要将区域分成几个小的区域，低端扫地机在扫描后达到垃圾总指标最高的区域清扫，清扫随机选取。

4.1.1模型：分区扫描模型（1）区域的划分通过分析问题一的工作特点，我们得到了一个相对比较合理的分割方式，如图4.1.1所示，我们进行的是五等分的条形分割，这样的分割方式可以保证扫地机在扫垃圾指标值最大的分区过程中，路径不覆盖其他分区。

图4.1.1 分区分析示意图（2）间隔扫描时间的确定在这里我们不妨把间隔扫描时间抽象为间隔扫描行驶路程考虑。

设定参数——间隔扫描行驶路程S T ，并给S T 赋初值（12.5m ）。

举个例子，假设发生碰撞时刻参考点坐标为(a ,b )，扫地机下一次与墙壁发生碰撞时刻参考点的坐标为(A ,B )，则从(a ,b )到(A ,B )扫地机行驶的路程S 有如下公式：22)()(B b A a S -+-=（勾股定理）故充电点到第n 个碰壁点扫地机行驶的时间T (n ) ⎪⎩⎪⎨⎧+-=025.0)1()(S n T n T 01=≥n n （3）模型的建立在扫地机的行驶过程中，根据假设4的条件；根据区域所在的位置枚举出参考点可以到达的点（单元）。

在这些点中随机选取一个作为下一次与墙壁的碰撞点。

将这点与参考点相连，即为下一步可能的清扫路径。

为了提高清扫的效率，我们选择清扫垃圾总数量最多的路径。

在这里我们引入一个参数C ，称为经过路径的垃圾总指标值。

根据我们所建立的模型可以列出公式：∑==Ni i m C 1（其中i m 为直线路径所经过单元的垃圾指标值；N 为经过区域的单位总数） 通过计算每条路径的C 值的大小，判断出最大的C 值所在路径的终点，进而得出碰撞后扫地的朝向。

由题意，低端扫地机通过传感器间隔一段时间扫描现场一次，选择垃圾最多区域进行清扫。

我们可以理解为它不能对区域进行实时扫描，且在下一次扫描之前清扫区域始终保持在前一次扫描所判断出的垃圾总指标最高的区域内进行清扫。

为保证清扫路径保持在前一次扫描所判断出的垃圾总指标最高的区域内，我们已经给出了如图 1.2 所示的区域分区方式。

下面我们就路径规划的几种情况给出如下规定。

①对于扫描发生在整个工作区域，当次扫描先于碰撞的情况回溯到上一次的路径选择，我们知道下一次扫地机与墙壁发生碰撞时参考点的坐标（下一条选择路径的起点坐标）即为上一条选择路径的终点坐标。

下一条路径的起点坐标已经确定，下面我们来讨论由该起点引出的多条路径的优化选择方式。

因为扫描发生在扫地机在区域内的行进途中，即扫描的过程先于碰撞，所以用于路径选择判断的数据为扫描时刻的数据。

因此，我们可以建立一个矩阵保存各个单元的垃圾即时的指标值。

②碰撞先于扫描的情况对于低端扫地机来说，我们默认其只有在扫描后才能对区域的垃圾指标进行分析和计算垃圾总指标值最大的路径。

相比于智能度比较高的扫地机，低端扫地机不具有预测和推算的功能。

对此，我们做出这样的规定：低端扫地机在上述情况中，将在最新一次扫描所判断出的垃圾指标值最大的区域中，随机选取特有边界上的一点作为下一条路径的终点进行清扫。

综上所述，划分情况的要点是低端扫地机对区域进行扫描不是实时的，而是间隔一段时间。

（4）程序框图（5）运算结果与分析因为扫地机的清扫路径有一定的随机性，故同样的实例模型进行多次试验肯定会产生不同的清扫路径，所用时间的不同。

为使结果更具有说服力，我们采用测取6 组数据取平均值的方法来计算。

具体实验记录如表1通过Matlab 对实验进行可视化演示，得到表1、图4.1.2区域行驶路径示意和图4.1.3运行路程/m 运行时间/sS T=12.5m 1 290.7133 1162.92 374.6146 1498.53 370.7776 1483.1平均值345.3685 1381.5表1 模型I数据记录图4.1.2 模型I扫地机区域行驶路径示意图图4.1.3 模型I区域完成清扫后垃圾分布完成清扫后垃圾分布的结果。