关于扫地机路径最优化问题(数学建模论文).pdf

扫地机器人路径优化问题 1 2 3 杨补园 倪鸿仪 鲍小雨 摘要：随着科学技术的迅猛发展，智能化扫地机越来越受到消费者的青睐，并逐步取代人 工清洁，而研究智能化扫地机的工作原理并最优化其路径和时间是推动产品高度智能化的核 心课题。 本论文中，通过建立分区域模型、非线性规划模型和分层次改进模型讨论扫地机器人路 径最优化问题，并用 excel 软件进行统计分析，用MATLAB 软件进行编程求解。分区域模 型研究表明，区域数越小时，扫地机为了清理该区域单个最大指标值花费的无效时间越多； 区域数越大时，单个垃圾指标值“几点独大”的耗时影响越小，扫地机越能够高效地工作。 非线性规划模型比较各可能通道内的指标值之和，并选择指标值和最大的路径行走，能够减 小分区域模型的盲目性，提高了工作效率。分层次模型是建立在线性规划模型上的改进模型， 该模型中考虑了可能通道内单个指标最大值和所有指标值之和两个影响因子的影响，采用层 次化模型，在之前模型上更进一步地提高了扫地机的工作效率。 本论文建立的三个模型各有优势，实际生活中，可根据场所的面积大小、清洁度要求、 清洁时间要求等因素综合考虑选择哪种模型的智能扫地机。 关键词：单个指标最大值 智能扫地机 分区域 碰撞边界线点  本论文是东南大学第八届大学生数学建模竞赛二等奖论文，版权归作者所有，严禁抄袭本论文内容。文 责自负。 1 东南大学仪器科学与工程学院，电子邮箱：buyuanyang93@; 2 东南大学仪器科学与工程学院; 3 东南大学仪器科学与工程学院. 1 问题重述： 随着科学技术的不断发展，扫地机逐步走入平常百姓家，并被越来越多的人所接受，扫 地机（也称扫地机器人）将在不久的将来像白色家电一样成为每个家庭必不可少的清洁帮手。 产品也会由现在的初级智能向着更高程度的智能化程度发展，逐步取代人工清洁。 扫地机是通过电动机的高速旋转，在主机内形成真空，利用由此产生的高速气流，从吸 入口吸进垃圾。扫地机一般为半径0.2 米圆盘，、运行速度一般在每秒0.25 米左右，只走直 线，且碰到墙壁等障碍才可转弯。与传统的扫地机不同，智能扫地机可以通过微处理器进行 现场环境分析，自动选择运行路线。遇到障碍发生碰撞后将重新随机地选择路线，逐步进行 清扫。智能扫地机具有记忆、存储功能。利用传感器扫描现场环境，设计运行路径并存储。 一般不能 100%的清扫指定区域（如墙角部分）。清扫后的垃圾装进机子尾部的集尘盒，再 通过人工清倒垃圾。机器在工作电压不足时会自动回到充电站充电。 考虑图 1 的工作现场，其中点A （1,5）为扫地机充电站，区域的垃圾指标见附件1.不 考虑再充电情况，请你们解决如下问题： 1.有些低档的扫地机因为价格低廉，智能程度不高。其工作时的路径选择方案是将现场 分成若干区域（例如上下左右4 个区域），并通过传感器间隔一段时间扫描现场一次，选则 垃圾最多区域清扫。假设每次扫过的区域垃圾指标值减少1。针对附件1，估计清扫完给定 区域大致需要的时间（尽量保证每个点的垃圾指标不超过1）。 2. 智能程度高的扫地机每次可以选择清 扫垃圾指标值最大的地方清扫，每次扫过的区 域垃圾指标值减少 1。该机器人需多长时间才 能保证清扫完该区域（区域内指标值不超过 1）。比较问题1 与问题2 ，说明问题1 中方案 的合理性。 3.其他条件同2 ，如何设计扫地机的路径， 保证扫地机以最短时间清扫完该区域。 问题分析：扫地机路径选择的原理是依靠 其智能扫描功能，记忆清扫现场的垃圾指标分布及其值大小，从而通过比较分析，选择行走 路径。每走过一个地方，其垃圾指标值减 1。扫地机是沿直线行走的，仅当圆盘碰撞障碍边 界线才会改变方向。所以建立数学模型的核心思想是统计并计算各个区域或者通道的指标值 分布情况，按不同的要求比较并选择最优的路径，从而达到预定目的。 模型假设： ①在整个区域清扫任务完成之前，扫地机不需要充电。 ②某局部区域清扫完毕后，扫地机扫描并选择下一个需要清扫的局部区域所需的时间忽略不 计。 ③清扫同一局部区域时，在区域内部每一处所需的时间相同，不会因为某一处垃圾量较大而 增加时间。 ④扫地机遇到障碍物时能够以任意角度改变方向，并且改变方向的时间不计。 ⑤扫地机在某一轮