扫地机路径优化数模论文一等奖

扫地机路径优化数模论文

一等奖

Prepared on 21 November 2021

第八届大学生数学建模竞赛

（）

主办：东南大学教务处

承办：东南大学数学系

东南大学数学建模竞赛组委会

论文题目：扫地机器人的路径优化

参赛队员信息：

扫地机器人的路径优化

【摘要】

本文将扫地机在区域中的路径抽象为栅格化模型，并采用线性规划的方法计算估计扫地机扫过的单元格数。建立可随机0-4赋值或是给定参数的垃圾指标矩阵Q[60*50]作为数据基库，根据扫地机不同的性能运用循环嵌套、线性规划等方法综合求解，最终方案通过matlab运行并进行可视化演示。实验的结果通过规划清扫路径示意图以及清扫结束后的垃圾指标矩阵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 所能到达的边界点作为终点，进而决定每次与墙壁发生碰撞下一时刻可能的转弯方向，计算各个方向的垃圾总指标k C 并进行比较得出下一时刻转弯方向。 ? 问题三

设计智能扫地机的路径，保证扫地机以最短时间清扫完该区域。第三问实际上是对第二问的优化。主要优化方向，我们分为两点：①提高单位长度上清扫垃圾指标的数量②考虑折线行驶，转换方向不必在与墙面发生碰撞。

?比较问题1与问题2

我们从经济、生活、节能、开发等多个方面说明问题1中方案的合理性。另外，通过比较问题1与问题2，发现其中的联系——T S的取值影响。通过改变T S大小进而提升低端扫地机的性能。

关键词：分区比较栅格化碰撞参考点线性规划实时路径判定

目录

1 问题重述-------------------------------------------------------------------------------------------3

2 问题分析-------------------------------------------------------------------------------------------3

3 模型假设-------------------------------------------------------------------------------------------4

4 符号系统-------------------------------------------------------------------------------------------4

5 基础模型-------------------------------------------------------------------------------------------5

清扫区域抽象化

扫地机清扫区域栅格化

路径线性规划

6分区间隔扫描模型（问题一）-----------------------------------------------------------------7 区域的划分

间隔扫描时间的确定

模型I的分析与建立

对于扫描发生在扫地机工作在整个区域内（在或不在边界上）的情况

对于扫描未发生，而扫地机到达墙壁（在边界点上）的情况

运算思路框图

运算结果与分析

7 实时扫描模型（问题二）--------------------------------------------------------------------12

区域的简单划分

时刻扫描的抽象处理方法

模型II的分析与建立

优化路径选取

最优化路径选取

运算思路框图

运算结果与分析

8 实时扫描折线模型（问题三）--------------------------------------------------------------15

区域的划分

间隔扫描时间的确定

模型III的分析与建立

最优路径选取

扫地机清扫区域栅格化

运算思路框图

运算结果与分析

9 模型I与模型II的比较----------------------------------------------------------------------18

10 模型的优缺点---------------------------------------------------------------------------------19

优点

缺点

参考文献--------------------------------------------------------------------------------------------20

附录

1 问题重述

随着科学技术的不断发展，扫地机逐步走入平常百姓家，并被越来越多的人所接受，扫地机（也称扫地机器人）将在不久的将来像白色家电一样成为每个家庭必不可少的清洁帮手。产品也会由现在的初级智能向着更高程度的智能化程度发展，逐步取代人工清洁。

扫地机是通过电动机的高速旋转，在主机内形成真空，利用由此产生的高速气流，从吸入口吸进垃圾。扫地机一般为半径0.2米圆盘，运行速度一般在每秒0.25米左右，只走直线，且碰到墙壁等障碍才可转弯。与传统的扫地机不同，智能扫地机可以通过微处理器进行现场环境分析，自动选择运行路线。遇到障碍发生碰撞后将重新随机地选择路线，逐步进行清扫。智能扫地机具有记忆、存储功能。利用传感器扫描现场环境，设计运行路径并存储。一般不能100%的清扫指定区域（如墙角部分）。清扫后的垃圾装进机子尾部的集尘盒，再通过人工清倒垃圾。机器在工作电压不足时会自动回到充电站充电。

考虑图1的工作现场，其中点A（1,5）为扫地机充电站，区域的垃圾指标见附件1.不考虑再充电情况，请你们解决如下问题：

（1）有些低档的扫地机因为价格低廉，智能程度不高。其工作时的路径选择方案是将现场分成若干区域（例如上下左右4个区域），并通过传感器间隔一段时间扫描现场一次，选择垃圾最多区域清扫。假设每次扫过的区域垃圾指标值减少1。针对附件1，

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

（2）智能程度高的扫地机每次可以选择清扫垃圾指标值最大的地方清扫，每次扫过的区域垃圾指标值减少1。该机器人需多长时间才能保证清扫完该区域（区域内指标值不超过1）。比较问题1与问题2，说明问题1中方案的合理性。

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

2 问题分析

低档扫地机和智能程度高的扫地机有一个共同的特点：路径在扫地机与墙壁碰撞之后朝向扫描计算出的垃圾指标最高点行驶。两者的不同点：低档扫地机需要对区域进行分区且不能时刻扫描计算垃圾指标值，总是在一段规定时间间隔之后对区域进行再扫描，重新规划下一条清扫路线。没有到扫描时间，则在前一次判断出的垃圾指标值最高的区域随机行驶；智能程度高的扫地机具有实时扫描的功能，在每一个与墙壁碰撞的瞬间其都会重新扫描。所以如何设计机器人的清扫路线是本题的关键。

第一问中，我们需要将区域分成几个小区域。低端扫地机在扫描后到达垃圾总指标最高的区域内进行清扫。在该区域内进行一段时间的不偏移扫描（即路径尽量保持在选定的分区内），且清扫为随机选取的。

第二问中，扫地机每次与墙壁发生碰撞的瞬间，扫描整个区域计算出各个方向上的垃圾指标值，并从中选择出一条垃圾总指标值最高的路径（路径的出发点为碰撞点）。由于机器人的转弯方向是任意的，如何简化问题使得机器人在有限的方向（0-180°）上计算垃圾的总数是我们所需要考虑的。在这里我们把扫描此刻的碰撞点作为固定的参考点，连接碰撞点与除去碰撞点所在的墙壁以外的另外三面墙壁上的分割间断点，做出直

线并计算各个直线上的垃圾总指标。比较各个方向上的垃圾总指标的大小，判断出最大值进而得出转弯方向。

关于设计扫地机的路径保证其以最短的时间清扫完该区域（问题三）的关键在于提高单位长度上清扫垃圾指标的数量。

3 模型假设

[1] 假设除了墙壁没有其他的障碍物；

[2] 假设扫地机不会发生故障，并严格按照给定指令行走；

[3] 假设点A(充电站)为扫地机每次工作的出发点；

[4] 假设扫地机遇到墙壁发生碰撞没有能量损失，即速率不发生改变；

[5] 假设扫地机工作从开始到结束电量充足，即工作途中不需要回充电站；

[6] 假设扫地机扫描垃圾计算指标值的过程不额外占用时间且扫描范围为整个区域空间；

[7] 假设智能程度高的扫地机扫描垃圾计算指标值的过程发生在与墙壁发生碰撞的瞬间；

[8] 假设当每个点的垃圾指标不超过1时扫地机本次工作结束；

[9] 假设扫地机碰到某个单位的面积比上单元面积的值大于就算清扫成功，即有一半以上的区域被扫地机覆盖，此时单位内的垃圾指标值减少1；

[10] 假设扫地机的垃圾容量足够大，在完成清扫之后才再通过人工清倒垃圾；

4 符号系统

5 基础模型

清扫区域抽象化

首先我们建立一个60*50的矩阵Q，并将各个单元里的垃圾指标赋入与二位矩阵组合形成一个三维数组。

特别声明：在这里我们把区域分成50*60的单元是对任意一个模型而言。譬如附件给出的*㎡的单元我们也可以划归到*㎡的单元中考虑。具体方法如下：可以把*㎡的单元再分割为更小的单元如*㎡的单元。分割之后小单元的垃圾指标值可以对原来的大单元取平均值求得。下一步则是将*㎡的单元再组合成*㎡的单元，*㎡单元内的垃圾指标在通过组合区域内*㎡的单元的指标值求和得到（出现小数采取四舍五入的方法取整）。

如图为将题目给定的附录（更新）导入到60*50矩阵Q后的垃圾指标空间分布图。扫地机清扫区域栅格化

因为扫地机只走直线，且只有碰到墙壁才能转弯。而扫地机碰壁后转弯的方向（0°~180°）可以是任意的，为了使简化问题，我们做出了如下的说明：

如上图10*14的区域，假设此时扫地机器人位于如上图黄色的16个小方格，若我们以机器人的左上角（即图中的O点）作为参考，则机器人左上角下一步到达墙壁的终点只可能是1,2,3，……23这23个点中的一个，即机器人下一步的方向只可能是这23个方向中的一个。如机器人最终到达点4，则机器人的最终位置位于如上图蓝色的16个小方格。其余情况同理。对于这23个方向，分别计算沿着这23个方向所经过路径的垃圾总指标k C，其中k=1,2,……23。

如图，计算参考点到各个边界点上的连线上的垃圾总指标值。从图上我们可以看到各个边界点对应的与参考点连线上的垃圾总指标值。

另外要注意的是我们已经假设机器人在行进过程中只要碰到某个小方格就算是清扫到该方格。计算出每个方向的k C并进行比较,判断出最大的方向并选定其为下一次路径。如题目要求，机器人每次经过一个单位，则该方格垃圾指标值减1，即矩阵中的相应元素减1。

为了控制扫地机工作的结束，我们认为扫地机在每次与墙壁发生碰撞的瞬间都会计算此时所有单元垃圾指标值是否都不大于1直到碰到墙壁后计算出此时所有单元垃圾指标值都不大于1时，扫地机自行回到充电站并停止工作。否则再次进行判断继续向下一个k C值最大的路径行进。

路径线性规划

扫地机从碰撞点到下一个碰撞点所扫过的路径如图条状区域所示。我们将区域分割成了60*50的矩阵，每个单元（对应一个点坐标）存贮着垃圾指标值。我们可以通过判定点的坐标是否包含在条状区域内来决定是否对该单元的垃圾指标值减1.

根据图示，我们可以得出以下的线性约束条件：

44x a x A y b y B

≥??≤-??

≥-??≤? 且 ()()()(4)4B b y x a b A a

B b y x a b A a -?

≤-+??-?-?≥--+-?-? 6分区间隔扫描模型（问题一）

区域的划分

在这里我们暂且假设把区域划分为上下左右4个区域进行分析。由题意，低端扫地机通过传感器间隔一段时间扫描现场一次，选择垃圾最多区域清扫。我们可以理解为它不能对区域进行实时扫描，且在下一次扫描之前清扫区域始终保持在前一次扫描所判断出的垃圾总指标最高的区域内进行清扫。

由图可知，这样的分区方式显然不合理。为保证清扫路径覆盖整个选定的分割区域，路径必须扫过其他分割区域，与题设有所违背。

故我们采取如图所示的区域分割方式。这样的分割方式可以保证扫地机在扫垃圾指标值最大的分区过程中，路径不覆盖其他分区。可认为是比较合理。

但是，不可否认这样的分割区域方式不是最合理的。章节5我们仅仅是提供大概的模型分割思路，具体的优化区域分割模型将在章节9中给出讨论。 间隔扫描时间的确定

同理，该模型只是建立扫地机清扫路径规划的基本方案，而并非最优的。 由已知假设：

[4] 假设扫地机遇到墙壁发生碰撞没有能量损失，即速率不发生改变；

[6] 假设扫地机扫描垃圾计算指标值的过程不额外占用时间且扫描范围为整个区域空间；

[7] 假设智能程度高的扫地机扫描垃圾计算指标值的过程发生在与墙壁发生碰撞的瞬间；

在这里我们不妨把间隔扫描时间抽象为间隔扫描行驶路程考虑。设定参数——间隔扫描行驶路程T S，并给T S赋初值（10m）。

举个例子，假设发生碰撞时刻参考点坐标为(,)

a b，扫地机下一次与墙壁发生碰撞时刻参考点的坐标为(,)

A B扫地机行驶的路程S有如下公式：

a b到(,)

A B，则从(,)

S=

故充电点到第n个碰壁点扫地机行驶的时间()

T n

模型I的分析与建立

在扫地机的行驶过程中，我们做出这样的假设。当扫地机碰到某个单位的面积比上单元面积的值大于时就算清扫成功，即有一半以上的区域被扫地机覆盖，此时单位内的垃圾指标值减少1；

根据区域所在的位置枚举出参考点可以到达的点（单元）。在这些点中随机选取一个作为下一次与墙壁的碰撞点。将这点与参考点相连，即为下一步可能的清扫路径。

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

在这里我们引入一个参数C，称为经过路径的垃圾总指标值。根据我们所建立的模型可以列出公式

（其中i m为直线路径所经过单元的垃圾指标值；N为经过区域的单位总数）

通过计算每条路径的C值的大小，判断出最大的C值所在路径的终点，进而得出碰撞后扫地的朝向。

由题意，低端扫地机通过传感器间隔一段时间扫描现场一次，选择垃圾最多区域进行清扫。我们可以理解为它不能对区域进行实时扫描，且在下一次扫描之前清扫区域始终保持在前一次扫描所判断出的垃圾总指标最高的区域内进行清扫。

为保证清扫路径保持在前一次扫描所判断出的垃圾总指标最高的区域内，我们已经给出了如图所示的区域分区方式。下面我们就路径规划的几种情况给出如下规定。

对于扫描发生在扫地机工作在整个区域内（在或不在边界上）的情况

首先可以明确一点，扫地机的行驶路径为一条直线。根据路径的初始条件以及当前位置可以判断出下一次扫地机与墙壁发生碰撞时参考点的坐标。当然可以不必这么麻烦。回溯到上一次的路径选择，我们知道下一次扫地机与墙壁发生碰撞时参考点的坐标（下一条选择路径的起点坐标）即为上一条选择路径的终点坐标。

下一条路径的起点坐标已经确定，下面我们来讨论由该起点引出的多条路径的优化选择方式。因为扫描发生在扫地机在区域内的行进途中，所以用于路径选择判断的数据为扫描时刻的数据。在这里，我们可以建立一个矩阵保存最新扫描时刻各个单元的垃圾指标值。

对于扫描未发生，而扫地机到达墙壁（在边界点上）的情况

对于低端扫地机来说，我们默认其只有在扫描后才能对区域的垃圾指标进行分析和计算垃圾总指标值最大的路径。不认为其有预测和推算的功能，否则将低端扫地机与智能扫地将没有本质上的区别。对此，我们做出这样的规定：低端扫地机在上述情况中，将在最新一次扫描所判断出的垃圾指标值最大的区域中，随机选取特有边界上的一点作为下一条路径的终点进行清扫。

关于特有边界的定义，我们可以根据图和图具体举例说明。如图中，右上区域的特有边界为我们所标定的蓝色粗线；又如图中，如橘色框线所划定的区域，其特有边界为上下两条橘色粗线。如蓝色框线所划定的区域，其特有边界为上下两条蓝色粗线。

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

运算思路框图

运算结果与分析

因为扫地机的清扫路径涉及随机选取的路径，故同样的实例模型肯定会产生不同的清扫路径，以及不同路径所对应的不同长短的时间。

为使结果更客观，我们采用测取6组数据取平均值的方法来计算。具体实验记录如表1

表1 分区间隔扫描模型（模型I）数据记录

通过完成清扫后垃圾分布的结果。

根据实验结果，我们可以知道扫地机完成清洁工作的时间大约为，符合实际，认为是正确的。

7 实时扫描模型（问题二）

区域的简单划分

首先我们建立一个50*60的矩阵，并将各个单元里的垃圾指标赋入与二位矩阵组合形成一个三维数组。由于机器人的半径为米（面积为π/25≈㎡），我们可以将区域分成若干*㎡的方格。可以看出机器人可以覆盖大约16个方格（*㎡）。

特别声明：在这里我们把区域分成50*60的单元是对任意一个模型而言。譬如附件给出的*㎡的单元我们也可以划归到*㎡的单元中考虑。具体方法如下：可以把*㎡的单元再分割为更小的单元如*㎡的单元。分割之后小单元的垃圾指标值可以对原来的大单元取平均值求得。下一步则是将*㎡的单元再组合成*㎡的单元，*㎡单元内的垃圾指标在通过组合区域内*㎡的单元的指标值求和得到（出现小数采取四舍五入的方法取整）。

时刻扫描的抽象处理方法

根据问题重述我们可以知道智能扫地机可以通过微处理器进行现场环境分析，自动选择运行路线。遇到障碍发生碰撞后将重新随机地选择路线，逐步进行清扫。智能扫地

机具有记忆、存储功能。利用传感器扫描现场环境，设计运行路径并存储。

所以我们可以给出这样的假设：

[7] 假设智能程度高的扫地机扫描垃圾计算指标值的过程发生在与墙壁发生碰撞的瞬间；

模型II的分析与建立

在扫地机的行驶过程中，我们做出这样的假设只要碰到某个（单元方格）就算是清扫到了该区域，即认为垃圾指标值减1。

优化路径选取

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

在这里我们引入一个参数C，称为经过路径的垃圾总指标值。根据我们所建立的模型可以列出公式

（其中i m为直线路径所经过单元的垃圾指标值；N为经过区域的单位总数）

通过计算每条路径的C值的大小，判断出最大的C值所在路径的终点，进而得出碰撞后扫地的朝向。

最优化路径选取

在章节中我们采取的优化路径选取方式是计算出垃圾总指标数最大的路径进行清扫。但是考虑到不同的路径有不同的长短，垃圾总指标数最大的路径不一定是效率最高的，即相同的时间内清扫的垃圾个数不一定是最高的。显然，以垃圾总指标数为路径选择判断的依据是不够优化的。于是，在章节8中我们将引入经过路径的垃圾指标分布律

P进行进一步优化的路径选择。

k

运算思路框图

运算结果与分析

通过完成清扫后垃圾分布的结果。

根据实验结果，我们可以知道扫地机完成清洁工作的时间大约为7min，符合实际，认为是正确的。

表2 实时扫描模型（模型II）数据记录

8 实时扫描折线模型（问题三）

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

区域的划分

（同）

时刻扫描的抽象处理方法

时刻扫描区域现场，参考点每移动一个单元都要进行实时的监控扫描。

模型III的分析与建立——优化路径选取

在模型II中，我们选择C最大的路径作为下一步的清扫路径。再深一步考虑，我们可以猜想到会有以下几种情况的发生。

①存在两个以上的长度相等的路径同时为C的最大值所在路径

②存在两个以上的长度不等的路径同时为C的最大值所在路径

③存在一个长度较短的路径(1l)其垃圾总指标为1C、一个长度较长的路径（2l）其

垃圾总指标为2

C，而有

21

12

12

C C

C C

l l

≥

?

?

?

≥

??

的条件

为了提高清扫的效率，我们选择单位长度上垃圾指标值最高的路径。

在这里我们引入一个参数P，称垃圾指标分布律。根据我们所建立的模型可以列出公式。

（其中i m为直线路径所经过单元的垃圾指标值；N为经过区域的单位总数）

通过计算每条路径的P值的大小，判断出最大的P值所在路径的终点，进而得出碰撞后扫地的朝向。

计算出每个方向的k P并进行比较,判断出k P最大的方向并选定其为下一次路径。如题目要求，机器人每次经过一个单位，则该方格垃圾指标值减1，即矩阵中的相应元素减1。

为了控制扫地机工作的结束，我们认为扫地机在每次与墙壁发生碰撞的瞬间都会计算此时所有单元垃圾指标值是否都不大于1直到碰到墙壁后计算出此时所有单元垃圾指标值都不大于1时，扫地机自行回到充电站并停止工作。否则再次进行判断继续向下一个k P 值最大的路径行进。

运算思路框图

运算结果与分析

通过Matlab对实验进行可视化演示，得到表3、示意和图完成清扫后垃圾分布的结果。

根据实验结果，我们可以知道扫地机完成清洁工作的时间大约为6min，符合实际，认为是正确的。

表3 实时扫描折线模型（模型III）数据记录

9 模型I与模型II的比较

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

表4 模型I与模型II的比较分析表格

很显然，低端扫地机是拼不过智能扫地机。那为何还有低端扫地机的存在那必然就有其的优越性。首先，可以知道两者工作完成的时间相距也不是太大。

①从经济生活着想

根据智能扫地机与低端扫地机关于扫描时间的区别，我们可以知道低端扫地机相较于智能扫地机来说是较为省电的。虽然在代码的编写中我们给出这样的假设“智能程度高的扫地机扫描垃圾计算指标值的过程发生在与墙壁发生碰撞的瞬间”，但是事实上，智能扫地机是时刻都在扫描的，扫描仪工作又是十分耗电。另外，我们注意到一点扫地机是充电式的。虽然我们在考虑上诉问题中始终认为是扫地机是保持电量的，即不需要返回充电站充电。若是相同的毫安时的电池，从已充满到耗尽电量的时间必然是低端大于智能扫地机。虽然，低端扫地机在完成工作历时上比智能扫地机长。但综合两方面来讲，可以认为低端扫地机在两方面之间得到补偿。再考虑成本问题上，低端扫地机的价格一般来说都会比智能扫地机低，所以低端扫地机可以认为是经济有效的。故低端扫地机的存在是有其的合理性的。

②从开发编程着想

通过对整个区域进行划分，即对区域内的单元进行分区，将多个单元合并成一个小区域进行考虑大大减少了运算是的数据总量，进而缩短运算运行时间，达到提高效率的目的。

另外，一方面若是要提高低端扫地机的效用，可以通过优化计算出最合理的扫描时间。进而达

表5 研究改变T

S对运行时间的影响

图9研究改变T

S对运行时间的影响曲线

以T

S为横坐标，平均运行时间的大小为坐标作图，如图9所示。

根据点图我们可以发现，当

30

4

T

S≤时运行路程、运行时间几乎不发生改变。

而当10

T

S≤是运行路程、运行时间发生显着改变。

10 模型的优缺点

优点

①在扫描机中选取左上点为参考点，以终点为各个方向的区分，简化了问题

②采用矩阵方法对该问题进行分析，对矩阵元素进行计算，简单明确

缺点

①扫地机栅格化之后，使得本该扫不到的地方（如墙角）也乃入清扫范围。这样的后果是使得清扫率的计算存在误差。但是，由于题设的要求是尽量保证每个点的垃圾指标不超过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. Al-Ghazi World of Computer Science and Information Technology Journal

[5] 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=zeros(60,50);

a1=0;

b1=0;

sum0=sum(sum(out));

sum_goal=sum0*;

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+4 && x>=a )

if(y>=b-4 && y<=50)

if(y<=(B-b)*(x-a)/(A-a)+b && 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