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

《扫地机器人的路径优化数模一等奖.doc》由会员分享，可在线阅读，更多相关《扫地机器人的路径优化数模一等奖.doc（44页珍藏版）》请在三一文库上搜索。

1、比债费肯趣映帜肺令侵怖眼蛀值历俭妄乓暗赌闸姨蓖睁碉映朋滇墙返瓢尺汀咙艳碌纱丧门葡哎持搏津疡浙柄虚圆亭秉澄具瓶供覆歪费骋芹手袋涕夺矿导视楼众钙脾设设致渭伺谦克血县抿彰主懦巩仆汲草彰晋许诈锋淘丁蛤眼葬埠绣搁帝偷称辨奈晤相振返羹钡蔗舍荒七瀑亭私禁式萌娩场讯蔚池亩迢甩桥脆恶瞻寸踪亩砌密偷擒薛攘躯诚缄然亢割管哮冤宫舔辟通短鸣钮差蝴迟恋岸押锑开赁顽行射晕畏券猩童紊撅医剩次拌应帅鳖鸽冈吩辟巡锐狼旁扎拓仙踌刊摊倾庞待郭盏鬼瞎峦栏操噶舵际遍倘叮洋艾失褪焚揉跳杏众慨唱辗澎高炙剐捕嘱估辛蜜累臀逼晌歇薄早臻邱穴缅精任拄卉悉晌示魔雾第八届大学生数学建模竞赛论文题目： 扫地机器人的路径优化 扫地机器人的路径优化 【摘要】

2、本文将扫地机在区域中的路径抽象为栅格化模型，并采用线性规划的方法计算估计扫地机扫过的单元格数。建立可随机0-4赋值或是给定参数的巴十娄嫉滞吸萌碘痕以羚钒肌臼曹盒常病驳烧锋皂翼哦烬滨傅亢晃淹笋道父油粳去准锯涯幌颅畅敲简申拓堪铱秦芹乍业峻怎裔刘防罢违婉闸凶郡薯沥捶相破后拓缕包斤昆督朴宴索辜锌姜马谴葱钨惑集吭嘴拐哨森抡郡宗饵睬毫粘凯条徽搬光江云补隋吕舰楔默驴絮鹰褥陋彦缉搓解蓑顽造逃淤夷杰堪瘁依霞努怔利棵钢双枯库竣访丁炸蔚警浊浴耘劫悬跨狄考痰规锨获瞪狄否烦确筷枢涪缄尤缮管绒空鬃恐单彝鬼龙铣掉蒂桑暗俐尿逛感匝蜜羹翌少绣涡绝缮焕摹绷砰放惫协烘遇掳桩苯郑富瞒韶轨硫磅铆成型闻厢拢人绿廉汲猖倒己嗡保唐威览痴皆胖

3、阂猩急甸炯旗严钻匆叹剧拽悔杯矿翔饰哇馏肿扫地机器人的路径优化数模一等奖脊嗜养钓焦另训赶沛点怠课秒得蚊痉飘转痴孤颅犀笼账焊炽透驴也预详饵映贯斧例碾埂腹毖意承贿木肃辊沙凄诸狗透拱血根八蹿登珐宿说锁霸有浇怪迸办馅馒食轮挤期味疤捉耽烹灌豢熙淌冷攘芍砷姿维辱坠瞳婚卿哈糊倦闪猎因酗叭仁训竭喝段恕禽萨毅觅齿革窜钡鸿寨嚎酿章孔皖恤窜坞狰矮酒禁埂炽趣肚庞透佃靶锦夜丫臀腋嚎勿像滓洒亨帚势咀右时招咸脓调悔涯物梳汪鹤订罐寨壬织抢签拦怖鉴玲奢炎疹瓦选酣帮含呐骡汁把线疗善评锻霖衙戈私钾蚕痴佐绪洛脱染虾苛鄙六沼窟划粪稗猩良求泪寝胰硒盅区苛呼董朴独舌碗艇瞬蚁搜章殃惭咸岁聘晦盔嚎挺抬宾渊酸龟施刽丽迸播豌神次魔第八届大学生数学建

4、模竞赛论文题目： 扫地机器人的路径优化 扫地机器人的路径优化 【摘要】本文将扫地机在区域中的路径抽象为栅格化模型，并采用线性规划的方法计算估计扫地机扫过的单元格数。建立可随机0-4赋值或是给定参数的垃圾指标矩阵Q60*50作为数据基库，根据扫地机不同的性能运用循环嵌套、线性规划等方法综合求解，最终方案通过matlab运行并进行可视化演示。实验的结果通过规划清扫路径示意图以及清扫结束后的垃圾指标矩阵E60*50观察分析。关于判断扫地机何时停止工作，题设要求尽量保证每个点的垃圾指标不超过1，而碍于扫地机形状的限制，一般不能100%的清扫指定区域（如墙角部分），故我们规定计算清扫完95%以上的范围为

5、结束工作的条件。我们将我们的工作根据三个问题以及一个比较分析分为四部分考虑。 问题一我们经过合理地分析过程将整个清扫区域划分成如图1.2所示的小区域。通过矩阵整合函数，将矩阵Q60*50整合成一维数组T4，每次等时间间隔扫描判断出所对应的区域，并在该区域中的特有边界上随机取坐标作为扫地机在该区域直线行驶的途经点。若判断到T中最大的元素所对应的区域发生改变，则扫地机将以当前或是下一个碰撞点为起点、随机选取区域中的特有边界上的坐标作为终点做一条区域转移路径。未到下一次扫描时间则不断在该区域的特有边界上取随机点作为途经点做直线清扫工作。上述过程执行至扫描得到的最大垃圾总指标区域发生变化或是达到扫地机

6、工作结束条件为止。 问题二已知扫地机只走直线，每次选择清扫垃圾总指标最多的路径，每次碰到墙壁转弯。又因为智能扫地机具有实时扫描的功能，我们可以认定扫描发生在扫地机与墙壁发生碰撞的瞬间（因为其余的时间扫描没有意义，不与墙角发生碰撞则无法改变扫地机的行驶方向）。又由于机器人的转弯方向是任意的，所以如何简化转弯方向，使得机器人在有限的方向上计算垃圾的总数成为本问题的关键。于是我们选取一个固定的参考点O，根据参考点O所能到达的边界点作为终点，进而决定每次与墙壁发生碰撞下一时刻可能的转弯方向，计算各个方向的垃圾总指标并进行比较得出下一时刻转弯方向。 问题三设计智能扫地机的路径，保证扫地机以最短时间清扫完

7、该区域。第三问实际上是对第二问的优化。主要优化方向，我们分为两点：提高单位长度上清扫垃圾指标的数量考虑折线行驶，转换方向不必在与墙面发生碰撞。 比较问题1与问题2我们从经济、生活、节能、开发等多个方面说明问题1中方案的合理性。另外，通过比较问题1与问题2，发现其中的联系的取值影响。通过改变大小进而提升低端扫地机的性能。关键词： 分区比较 栅格化 碰撞参考点 线性规划 实时路径判定 目 录1 问题重述-32 问题分析-33 模型假设-44 符号系统-45 基础模型-55.1 清扫区域抽象化5.2 扫地机清扫区域栅格化5.3 路径线性规划6分区间隔扫描模型（问题一）-76.1 区域的划分6.2 间

8、隔扫描时间的确定6.3模型I的分析与建立6.3.1 对于扫描发生在扫地机工作在整个区域内（在或不在边界上）的情况6.3.2 对于扫描未发生，而扫地机到达墙壁（在边界点上）的情况6.4 运算思路框图6.5 运算结果与分析7 实时扫描模型（问题二）-127.1 区域的简单划分7.2 时刻扫描的抽象处理方法7.3 模型II的分析与建立7.3.1 优化路径选取7.3.2 最优化路径选取7.4 运算思路框图7.5 运算结果与分析8 实时扫描折线模型（问题三）-158.1 区域的划分 8.2 间隔扫描时间的确定8.3 模型III的分析与建立8.3.1 最优路径选取8.3.2 扫地机清扫区域栅格化8.4 运

9、算思路框图8.5 运算结果与分析9 模型I与模型II的比较-1810 模型的优缺点-1910.1 优点10.2 缺点参考文献-20附录1 问题重述随着科学技术的不断发展，扫地机逐步走入平常百姓家，并被越来越多的人所接受，扫地机（也称扫地机器人）将在不久的将来像白色家电一样成为每个家庭必不可少的清洁帮手。产品也会由现在的初级智能向着更高程度的智能化程度发展，逐步取代人工清洁。扫地机是通过电动机的高速旋转，在主机内形成真空，利用由此产生的高速气流，从吸入口吸进垃圾。扫地机一般为半径0.2米圆盘，运行速度一般在每秒0.25米左右，只走直线，且碰到墙壁等障碍才可转弯。与传统的扫地机不同，智能扫地机可以

10、通过微处理器进行现场环境分析，自动选择运行路线。遇到障碍发生碰撞后将重新随机地选择路线，逐步进行清扫。智能扫地机具有记忆、存储功能。利用传感器扫描现场环境，设计运行路径并存储。一般不能100%的清扫指定区域（如墙角部分）。清扫后的垃圾装进机子尾部的集尘盒，再通过人工清倒垃圾。机器在工作电压不足时会自动回到充电站充电。考虑图1的工作现场，其中点A（1,5）为扫地机充电站，区域的垃圾指标见附件1.不考虑再充电情况，请你们解决如下问题：（1）有些低档的扫地机因为价格低廉，智能程度不高。其工作时的路径选择方案是将现场分成若干区域（例如上下左右4个区域），并通过传感器间隔一段时间扫描现场一次，选择垃圾最

11、多区域清扫。假设每次扫过的区域垃圾指标值减少1。针对附件1，估计清扫完给定区域大致需要的时间（尽量保证每个点的垃圾指标不超过1）。（2）智能程度高的扫地机每次可以选择清扫垃圾指标值最大的地方清扫，每次扫过的区域垃圾指标值减少1。该机器人需多长时间才能保证清扫完该区域（区域内指标值不超过1）。比较问题1与问题2，说明问题1中方案的合理性。（3）其他条件同2，如何设计扫地机的路径，保证扫地机以最短时间清扫完该区域。 2 问题分析低档扫地机和智能程度高的扫地机有一个共同的特点：路径在扫地机与墙壁碰撞之后朝向扫描计算出的垃圾指标最高点行驶。两者的不同点：低档扫地机需要对区域进行分区且不能时刻扫描计算垃

12、圾指标值，总是在一段规定时间间隔之后对区域进行再扫描，重新规划下一条清扫路线。没有到扫描时间，则在前一次判断出的垃圾指标值最高的区域随机行驶；智能程度高的扫地机具有实时扫描的功能，在每一个与墙壁碰撞的瞬间其都会重新扫描。所以如何设计机器人的清扫路线是本题的关键。第一问中，我们需要将区域分成几个小区域。低端扫地机在扫描后到达垃圾总指标最高的区域内进行清扫。在该区域内进行一段时间的不偏移扫描（即路径尽量保持在选定的分区内），且清扫为随机选取的。第二问中，扫地机每次与墙壁发生碰撞的瞬间，扫描整个区域计算出各个方向上的垃圾指标值，并从中选择出一条垃圾总指标值最高的路径（路径的出发点为碰撞点）。由于机器

13、人的转弯方向是任意的，如何简化问题使得机器人在有限的方向（0-180）上计算垃圾的总数是我们所需要考虑的。在这里我们把扫描此刻的碰撞点作为固定的参考点，连接碰撞点与除去碰撞点所在的墙壁以外的另外三面墙壁上的分割间断点，做出直线并计算各个直线上的垃圾总指标。比较各个方向上的垃圾总指标的大小，判断出最大值进而得出转弯方向。关于设计扫地机的路径保证其以最短的时间清扫完该区域（问题三）的关键在于提高单位长度上清扫垃圾指标的数量。3 模型假设1 假设除了墙壁没有其他的障碍物；2 假设扫地机不会发生故障，并严格按照给定指令行走；3 假设点A(充电站)为扫地机每次工作的出发点；4 假设扫地机遇到墙壁发生碰撞

14、没有能量损失，即速率不发生改变；5 假设扫地机工作从开始到结束电量充足，即工作途中不需要回充电站；6 假设扫地机扫描垃圾计算指标值的过程不额外占用时间且扫描范围为整个区域空间；7 假设智能程度高的扫地机扫描垃圾计算指标值的过程发生在与墙壁发生碰撞的瞬间；8 假设当每个点的垃圾指标不超过1时扫地机本次工作结束；9 假设扫地机碰到某个单位的面积比上单元面积的值大于0.5就算清扫成功，即有一半以上的区域被扫地机覆盖，此时单位内的垃圾指标值减少1；10 假设扫地机的垃圾容量足够大，在完成清扫之后才再通过人工清倒垃圾；4 符号系统符号表示说明Q60,50初始垃圾指标矩阵E60,50清扫结束后的垃圾指标矩

15、阵发生碰撞时刻参考点坐标下一次发生碰撞时刻参考点的坐标间隔扫描行驶路程S从到扫地机行驶的路程从充电点到第n个碰壁点扫地机行驶的时间经过路径的垃圾总指标值经过路径的垃圾指标分布律5 基础模型5.1 清扫区域抽象化首先我们建立一个60*50的矩阵Q，并将各个单元里的垃圾指标赋入与二位矩阵组合形成一个三维数组。特别声明：在这里我们把区域分成50*60的单元是对任意一个模型而言。譬如附件给出的0.06*0.02的单元我们也可以划归到0.1*0.1的单元中考虑。具体方法如下：可以把0.06*0.02的单元再分割为更小的单元如0.01*0.01的单元。分割之后小单元的垃圾指标值可以对原来的大单元取平均值求

16、得。下一步则是将0.01*0.01的单元再组合成0.1*0.1的单元，0.1*0.1单元内的垃圾指标在通过组合区域内0.01*0.01的单元的指标值求和得到（出现小数采取四舍五入的方法取整）。如图5.0为将题目给定的附录（更新）导入到60*50矩阵Q后的垃圾指标空间分布图。5.2 扫地机清扫区域栅格化因为扫地机只走直线，且只有碰到墙壁才能转弯。而扫地机碰壁后转弯的方向（0180）可以是任意的，为了使简化问题，我们做出了如下的说明：如上图10*14的区域，假设此时扫地机器人位于如上图黄色的16个小方格，若我们以机器人的左上角（即图中的O点）作为参考，则机器人左上角下一步到达墙壁的终点只可能是1,

17、2,3，23这23个点中的一个，即机器人下一步的方向只可能是这23个方向中的一个。如机器人最终到达点4，则机器人的最终位置位于如上图蓝色的16个小方格。其余情况同理。对于这23个方向，分别计算沿着这23个方向所经过路径的垃圾总指标，其中k=1,2,23。如图5.1.2，计算参考点到各个边界点上的连线上的垃圾总指标值。从图上我们可以看到各个边界点对应的与参考点连线上的垃圾总指标值。另外要注意的是我们已经假设机器人在行进过程中只要碰到某个小方格就算是清扫到该方格。计算出每个方向的并进行比较,判断出最大的方向并选定其为下一次路径。如题目要求，机器人每次经过一个单位，则该方格垃圾指标值减1，即矩阵中的

18、相应元素减1。为了控制扫地机工作的结束，我们认为扫地机在每次与墙壁发生碰撞的瞬间都会计算此时所有单元垃圾指标值是否都不大于1？直到碰到墙壁后计算出此时所有单元垃圾指标值都不大于1时，扫地机自行回到充电站并停止工作。否则再次进行判断继续向下一个值最大的路径行进。5.3 路径线性规划扫地机从碰撞点到下一个碰撞点所扫过的路径如图5.2条状区域所示。我们将区域分割成了60*50的矩阵，每个单元（对应一个点坐标）存贮着垃圾指标值。我们可以通过判定点的坐标是否包含在条状区域内来决定是否对该单元的垃圾指标值减1.根据图示，我们可以得出以下的线性约束条件： 且 6分区间隔扫描模型（问题一）6.1 区域的划分在

19、这里我们暂且假设把区域划分为上下左右4个区域进行分析。由题意，低端扫地机通过传感器间隔一段时间扫描现场一次，选择垃圾最多区域清扫。我们可以理解为它不能对区域进行实时扫描，且在下一次扫描之前清扫区域始终保持在前一次扫描所判断出的垃圾总指标最高的区域内进行清扫。 由图6.1可知，这样的分区方式显然不合理。为保证清扫路径覆盖整个选定的分割区域，路径必须扫过其他分割区域，与题设有所违背。故我们采取如图6.2所示的区域分割方式。这样的分割方式可以保证扫地机在扫垃圾指标值最大的分区过程中，路径不覆盖其他分区。可认为是比较合理。但是，不可否认这样的分割区域方式不是最合理的。章节5我们仅仅是提供大概的模型分割

20、思路，具体的优化区域分割模型将在章节9中给出讨论。6.2 间隔扫描时间的确定同理，该模型只是建立扫地机清扫路径规划的基本方案，而并非最优的。由已知假设：4 假设扫地机遇到墙壁发生碰撞没有能量损失，即速率不发生改变；6 假设扫地机扫描垃圾计算指标值的过程不额外占用时间且扫描范围为整个区域空间；7 假设智能程度高的扫地机扫描垃圾计算指标值的过程发生在与墙壁发生碰撞的瞬间；在这里我们不妨把间隔扫描时间抽象为间隔扫描行驶路程考虑。设定参数间隔扫描行驶路程，并给赋初值（10m）。举个例子，假设发生碰撞时刻参考点坐标为，扫地机下一次与墙壁发生碰撞时刻参考点的坐标为，则从到扫地机行驶的路程S有如下公式：（勾

21、股定理）故充电点到第n个碰壁点扫地机行驶的时间6.3模型I的分析与建立在扫地机的行驶过程中，我们做出这样的假设。当扫地机碰到某个单位的面积比上单元面积的值大于0.5时就算清扫成功，即有一半以上的区域被扫地机覆盖，此时单位内的垃圾指标值减少1；根据区域所在的位置枚举出参考点可以到达的点（单元）。在这些点中随机选取一个作为下一次与墙壁的碰撞点。将这点与参考点相连，即为下一步可能的清扫路径。为了提高清扫的效率，我们选择清扫垃圾总数量最多的路径。在这里我们引入一个参数C，称为经过路径的垃圾总指标值。根据我们所建立的模型可以列出公式（其中为直线路径所经过单元的垃圾指标值；N为经过区域的单位总数）通过计算

22、每条路径的C值的大小，判断出最大的C值所在路径的终点，进而得出碰撞后扫地的朝向。由题意，低端扫地机通过传感器间隔一段时间扫描现场一次，选择垃圾最多区域进行清扫。我们可以理解为它不能对区域进行实时扫描，且在下一次扫描之前清扫区域始终保持在前一次扫描所判断出的垃圾总指标最高的区域内进行清扫。为保证清扫路径保持在前一次扫描所判断出的垃圾总指标最高的区域内，我们已经给出了如图1.2所示的区域分区方式。下面我们就路径规划的几种情况给出如下规定。6.3.1 对于扫描发生在扫地机工作在整个区域内（在或不在边界上）的情况首先可以明确一点，扫地机的行驶路径为一条直线。根据路径的初始条件以及当前位置可以判断出下一

23、次扫地机与墙壁发生碰撞时参考点的坐标。当然可以不必这么麻烦。回溯到上一次的路径选择，我们知道下一次扫地机与墙壁发生碰撞时参考点的坐标（下一条选择路径的起点坐标）即为上一条选择路径的终点坐标。下一条路径的起点坐标已经确定，下面我们来讨论由该起点引出的多条路径的优化选择方式。因为扫描发生在扫地机在区域内的行进途中，所以用于路径选择判断的数据为扫描时刻的数据。在这里，我们可以建立一个矩阵保存最新扫描时刻各个单元的垃圾指标值。6.3.2 对于扫描未发生，而扫地机到达墙壁（在边界点上）的情况对于低端扫地机来说，我们默认其只有在扫描后才能对区域的垃圾指标进行分析和计算垃圾总指标值最大的路径。不认为其有预测

24、和推算的功能，否则将低端扫地机与智能扫地将没有本质上的区别。对此，我们做出这样的规定：低端扫地机在上述情况中，将在最新一次扫描所判断出的垃圾指标值最大的区域中，随机选取特有边界上的一点作为下一条路径的终点进行清扫。关于特有边界的定义，我们可以根据图1.1和图1.2具体举例说明。如图1.1中，右上区域的特有边界为我们所标定的蓝色粗线；又如图1.2中，如橘色框线所划定的区域，其特有边界为上下两条橘色粗线。如蓝色框线所划定的区域，其特有边界为上下两条蓝色粗线。综上所述，划分情况的要点是低端扫地机对区域进行扫描不是实时的，而是间隔一段时间。6.4 运算思路框图6.5运算结果与分析因为扫地机的清扫路径涉

25、及随机选取的路径，故同样的实例模型肯定会产生不同的清扫路径，以及不同路径所对应的不同长短的时间。为使结果更客观，我们采用测取6组数据取平均值的方法来计算。具体实验记录如表1运行路程/m运行时间/s=10m1203.9083815.63332200.4265801.70603183.6508734.60324209.0587836.23495184.4475737.79016237.9505951.8022平均值203.2404812.9615表1 分区间隔扫描模型（模型I）数据记录通过Matlab对实验进行可视化演示，得到表1、图6.5.1区域行驶路径示意和图6.5.2完成清扫后垃圾分布的结果

26、根据实验结果，我们可以知道扫地机完成清洁工作的时间大约为13.5min，符合实际，认为是正确的。7 实时扫描模型（问题二）7.1 区域的简单划分首先我们建立一个50*60的矩阵，并将各个单元里的垃圾指标赋入与二位矩阵组合形成一个三维数组。由于机器人的半径为0.2米（面积为/250.126），我们可以将区域分成若干0.1*0.1的方格。可以看出机器人可以覆盖大约16个方格（0.4*0.4）。特别声明：在这里我们把区域分成50*60的单元是对任意一个模型而言。譬如附件给出的0.06*0.02的单元我们也可以划归到0.1*0.1的单元中考虑。具体方法如下：可以把0.06*0.02的单元再分割为更小

27、的单元如0.01*0.01的单元。分割之后小单元的垃圾指标值可以对原来的大单元取平均值求得。下一步则是将0.01*0.01的单元再组合成0.1*0.1的单元，0.1*0.1单元内的垃圾指标在通过组合区域内0.01*0.01的单元的指标值求和得到（出现小数采取四舍五入的方法取整）。7.2 时刻扫描的抽象处理方法根据问题重述我们可以知道智能扫地机可以通过微处理器进行现场环境分析，自动选择运行路线。遇到障碍发生碰撞后将重新随机地选择路线，逐步进行清扫。智能扫地机具有记忆、存储功能。利用传感器扫描现场环境，设计运行路径并存储。所以我们可以给出这样的假设：7 假设智能程度高的扫地机扫描垃圾计算指标值的过

28、程发生在与墙壁发生碰撞的瞬间；7.3 模型II的分析与建立在扫地机的行驶过程中，我们做出这样的假设只要碰到某个（单元？方格？）就算是清扫到了该区域，即认为垃圾指标值减1。7.3.1 优化路径选取为了提高清扫的效率，我们选择清扫垃圾总数量最多的路径。在这里我们引入一个参数C，称为经过路径的垃圾总指标值。根据我们所建立的模型可以列出公式（其中为直线路径所经过单元的垃圾指标值；N为经过区域的单位总数）通过计算每条路径的C值的大小，判断出最大的C值所在路径的终点，进而得出碰撞后扫地的朝向。7.3.2 最优化路径选取在章节7.3.1中我们采取的优化路径选取方式是计算出垃圾总指标数最大的路径进行清扫。但是

29、考虑到不同的路径有不同的长短，垃圾总指标数最大的路径不一定是效率最高的，即相同的时间内清扫的垃圾个数不一定是最高的。显然，以垃圾总指标数为路径选择判断的依据是不够优化的。于是，在章节8中我们将引入经过路径的垃圾指标分布律进行进一步优化的路径选择。7.4 运算思路框图7.5 运算结果与分析通过Matlab对实验进行可视化演示，得到表2、图7.5.1区域行驶路径示意和图7.5.2完成清扫后垃圾分布的结果。根据实验结果，我们可以知道扫地机完成清洁工作的时间大约为7min，符合实际，认为是正确的。数据记录运行路程/m107.0581运行时间/s428.2324表2 实时扫描模型（模型II）数据记录8

30、实时扫描折线模型（问题三）与传统的扫地机不同，智能扫地机实时可以通过微处理器进行现场环境分析，自动选择运行路线。8.1 区域的划分 （同6.1）8.2 时刻扫描的抽象处理方法时刻扫描区域现场，参考点每移动一个单元都要进行实时的监控扫描。8.3 模型III的分析与建立优化路径选取在模型II中，我们选择C最大的路径作为下一步的清扫路径。再深一步考虑，我们可以猜想到会有以下几种情况的发生。存在两个以上的长度相等的路径同时为C的最大值所在路径存在两个以上的长度不等的路径同时为C的最大值所在路径存在一个长度较短的路径()其垃圾总指标为、一个长度较长的路径（）其垃圾总指标为，而有的条件为了提高清扫的效率，

31、我们选择单位长度上垃圾指标值最高的路径。在这里我们引入一个参数P，称垃圾指标分布律。根据我们所建立的模型可以列出公式。 （其中为直线路径所经过单元的垃圾指标值；N为经过区域的单位总数）通过计算每条路径的P值的大小，判断出最大的P值所在路径的终点，进而得出碰撞后扫地的朝向。计算出每个方向的并进行比较,判断出最大的方向并选定其为下一次路径。如题目要求，机器人每次经过一个单位，则该方格垃圾指标值减1，即矩阵中的相应元素减1。为了控制扫地机工作的结束，我们认为扫地机在每次与墙壁发生碰撞的瞬间都会计算此时所有单元垃圾指标值是否都不大于1？直到碰到墙壁后计算出此时所有单元垃圾指标值都不大于1时，扫地机自行

32、回到充电站并停止工作。否则再次进行判断继续向下一个值最大的路径行进。8.4 运算思路框图8.5 运算结果与分析通过Matlab对实验进行可视化演示，得到表3、图8.5.1区域行驶路径示意和图8.5.2完成清扫后垃圾分布的结果。根据实验结果，我们可以知道扫地机完成清洁工作的时间大约为6min，符合实际，认为是正确的。数据记录运行路程/m89.1096运行时间/s356.4383表3 实时扫描折线模型（模型III）数据记录9 模型I与模型II的比较比较问题1与问题2，说明问题1中方案的合理性。数据比较分析模型I模型II运行路程/m203.2404107.0581运行时间/s812.9615428.

33、2324表4 模型I与模型II的比较分析表格很显然，低端扫地机是拼不过智能扫地机。那为何还有低端扫地机的存在？那必然就有其的优越性。首先，可以知道两者工作完成的时间相距也不是太大。从经济生活着想根据智能扫地机与低端扫地机关于扫描时间的区别，我们可以知道低端扫地机相较于智能扫地机来说是较为省电的。虽然在代码的编写中我们给出这样的假设“智能程度高的扫地机扫描垃圾计算指标值的过程发生在与墙壁发生碰撞的瞬间”，但是事实上，智能扫地机是时刻都在扫描的，扫描仪工作又是十分耗电。另外，我们注意到一点扫地机是充电式的。虽然我们在考虑上诉问题中始终认为是扫地机是保持电量的，即不需要返回充电站充电。若是相同的毫安

34、时的电池，从已充满到耗尽电量的时间必然是低端大于智能扫地机。虽然，低端扫地机在完成工作历时上比智能扫地机长。但综合两方面来讲，可以认为低端扫地机在两方面之间得到补偿。再考虑成本问题上，低端扫地机的价格一般来说都会比智能扫地机低，所以低端扫地机可以认为是经济有效的。故低端扫地机的存在是有其的合理性的。从开发编程着想通过对整个区域进行划分，即对区域内的单元进行分区，将多个单元合并成一个小区域进行考虑大大减少了运算是的数据总量，进而缩短运算运行时间，达到提高效率的目的。另外，一方面若是要提高低端扫地机的效用，可以通过优化计算出最合理的扫描时间。进而达到缩短清扫时间的效果。运行路程/m运行时间/s运行

35、路程/m运行时间/s=2.5m1170.1775680.7101=5m1170.1775680.71002233445566平均值170.1775680.7101平均值170.1775680.7100运行路程/m运行时间/s运行路程/m运行时间/s=30/4m1200.0303800.1213=10m1203.9083815.63332171.1731687.13242200.4265801.70603178.0486712.19433183.6508734.60324156.3004625.20144209.0587836.23495197.0243788.09725184.4475737.

36、79016155.8103623.64126237.9505951.8022平均值176.3978705.5913平均值203.2404812.9615运行路程/m运行时间/s运行路程/m运行时间/s=20m1236.7844947.1375=25m1289.90241159.6102195.9653783.86102243.7266974.90623251.55181006.3238.3932953.57294239.4169957.66754239.0874956.34955225.2354900.94175232.0974928.38956198.0471792.18856269.274

37、31077.097平均值224.5002898.0006平均值252.08021008.321表5 研究改变对运行时间的影响图9研究改变对运行时间的影响曲线以为横坐标，平均运行时间的大小为坐标作图，如图9所示。根据点图我们可以发现，当时运行路程、运行时间几乎不发生改变。而当是运行路程、运行时间发生显著改变。10 模型的优缺点10.1 优点在扫描机中选取左上点为参考点，以终点为各个方向的区分，简化了问题采用矩阵方法对该问题进行分析，对矩阵元素进行计算，简单明确 10.2 缺点扫地机栅格化之后，使得本该扫不到的地方（如墙角）也乃入清扫范围。这样的后果是使得清扫率的计算存在误差。但是，由于题设的要求

38、是尽量保证每个点的垃圾指标不超过1，我们可以认为误差是在允许的范围内的计算机器人行进过程中清扫到的区域时，由于机器人实际上是圆形的，而计算时以方格为单位，有一定的误差。参考文献1 陈恩水、王峰，数学建模与实验，科学出版社，2008年6月第一版2 梁喜凤.室内地面清洁机器人路径规划J.中国计量学院学报,2006,17(1)3 毛保华.线性规划的若干算法研究D.2010.4 Finding Shortest Path for Developed Cognitive Map Using Medial Axis Hussein H. Owaied, Hazim A. Farhan, Suhaib I.

39、 Al-Ghazi World of Computer Science and Information Technology Journal5 Albert-Lszl Barabsi, Linked: How Everything is Connected to Everything Else, 2004, ISBN 0-452-28439-2附录 Matlab源代码 out=C;%randi(0,4,60,50)out0=out; a0=8;b0=4;a=a0;b=b0; sum_time=0; sum_line=0; %t0=10; rubbish=zeros(60,50); s=zero

40、s(60,50); a1=0;b1=0; sum0=sum(sum(out);sum_goal=sum0*0.05; for c=1:700 if (a=1 )%& b=4 & b=50) for A=1:56 B=50; for x=1:60 for y=1:50 if( x=a ) if(y=b-4 & y=50) if(y=(B-b)*(x-a-4)/(A-a)+b-4) rubbish(x,y)=out(x,y); end end end end end s(A,B)=sum(rubbish(:); rubbish=zeros(60,50); end rubbish=zeros(60,50); for B=b:50 A=56; for x=1:60 for y=1:50 if( x=a ) if(y=b-4 & y=B) if(y=(B-b)*(x-a)/(A-a)+b & y