扫地机器人的路径优化数模论文一等奖.doc

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