扫地机器路径优化数模方案#40;一等奖#41;.doc

第八届大学生数学建模竞赛 论文题目: 扫地机器人的路径优化 扫地机器人的路径优化 本文将扫地机在区域中的路径抽象为栅格化模型,并采用线性规划的方法计算估计扫地机扫过的单元格数?建立可随机0-4赋值或是给定参数的垃圾指标矩阵Q[60*50]作为数据基库,根据扫地机不同的性能运用循环嵌套?线性规划等方法综合求解,最终方案通过matlab运行并进行可视化演示?实验的结果通过规划清扫路径示意图以及清扫结束后的垃圾指标矩阵E[60*50]观察分析? 关于判断扫地机何时停止工作,题设要求尽量保证每个点的垃圾指标不超过1,而碍于扫地机形状的限制,一般不能100%的清扫指定区域(如墙角部分),故我们规定计算清扫完95%以上的范围为结束工作的条件? 我们将我们的工作根据三个问题以及一个比较分析分为四部分考虑? 问题一 我们经过合理地分析过程将整个清扫区域划分成如图1.2所示的小区域?通过矩阵整合函数,将矩阵Q[60*50]整合成一维数组T[4],每次等时间间隔扫描判断出所对应的区域,并在该区域中的特有边界上随机取坐标作为扫地机在该区域直线行驶的途经点?若判断到T中最大的元素所对应的区域发生改变,则扫地机将以当前或是下一个碰撞点为起点?随机选取区域中的特有边界上的坐标作为终点做一条区域转移路径?未到下一次扫描时间则不断在该区域的特有边界上取随机点作为途经点做直线清扫工作?上述过程执行至扫描得到的最大垃圾总指标区域发生变化或是达到扫地机工作结束条件为止? 问题二 已知扫地机只走直线,每次选择清扫垃圾总指标最多的路径,每次碰到墙壁转弯?又因为智能扫地机具有实时扫描的功能,我们可以认定扫描发生在扫地机与墙壁发生碰撞的瞬间(因为其余的时间扫描没有意义,不与墙角发生碰撞则无法改变扫地机的行驶方向)?又由于机器人的转弯方向是任意的,所以如何简化转弯方向,使得机器人在有限的方向上计算垃圾的总数成为本问题的关键?于是我们选取一个固定的参考点O,根据参考点O所能到达的边界点作为终点,进而决定每次与墙壁发生碰撞下一时刻可能的转弯方向,计算各个方向的垃圾总指标并进行比较得出下一时刻转弯方向? 问题三 设计智能扫地机的路径,保证扫地机以最短时间清扫完该区域?第三问实际上是对第二问的优化?主要优化方向,我们分为两点:①提高单位长度上清扫垃圾指标的数量②考虑折线行驶,转换方向不必在与墙面发生碰撞? 比较问题1与问题2 我们从经济?生活?节能?开发等多个方面说明问题1中方案的合理性?另外,通过比较问题1与问题2,发现其中的联系——的取值影响?通过改变大小进而提升低端扫地机的性能? 关键词: 分区比较 栅格化 碰撞参考点 线性规划 实时路径判定 目 录1 问题重述-------------------------------------------------------------------------------------------3 2 问题分析-------------------------------------------------------------------------------------------3 3 模型假设-------------------------------------------------------------------------------------------4 4 符号系统-------------------------------------------------------------------------------------------4 5 基础模型-------------------------------------------------------------------------------------------5 5.1 清扫区域抽象化 5.2 扫地机清扫区域栅格化 5.3 路径线性规划 6分区间隔扫描模型(问题一)-----------------------------------------------------------------7 6.1 区域的划分 6.2 间隔扫描时间的确定 6.3模型I的分析与建立 6.3.1 对于扫描发生在扫地机工作在整个区域内(在或不在边界上)的情况 6.3.2 对于扫描未发生,而扫地机到达墙壁(在边界点上)的情况 6.4 运算思路框图 6.5 运算结果与分析 7 实时扫描模型(问题二)--------------------------------------------------------------------12 7.1 区域的简单划分