搜索
论文题目：A题：扫地机器人的路径优化大学生数学建模竞赛2摘要本文研究的是一个基于环境模型的扫地机器人路径规划问题，其规划的目标是在封闭区域内实现智能扫地机器人移动路径对工作区域的最大覆盖率和最小重复率，最终实现最短路径完成最优清扫。首先，本问题的环境模型已经给出，垃圾分布栅格化和权值化已经完成，且机器人运行规则已经固定（只能走直线，且碰到墙壁后才能转弯）。我们利用C++编程，根据区域栅格化的结果建立二维数组，将区域各点的垃圾指标值存入数组中，数组下标经过转换与现实坐标一一对应，通过编写程序对数组进行一定操作，从而完成对问题的数学求解。问题一：有些低档的扫地机的路径选择方案是将现场分成若干区域，并通过传感器间隔一段时间扫描现场一次，选择垃圾最多区域清扫，估计清扫完给定区域大致的时间。针对这个问题，我们提出了基于区域分解法的路径动态规划模型，对栅格地图进行区域划分，将整个区域分割成若干区域的集合，并将机器人行走路径简化为矩形（矩形宽为机器人的直接0.4米）。开始扫地机器人遍历垃圾分布，找出垃圾指标值之和最大的区域。然后从起点出发，对该区域进行扫描，寻找最优前往路径，最优表现在该区域与机器人矩形前往区域的重叠部分垃圾总量最大。接着，机器人前往路径上垃圾指标都减1。当扫地机碰到墙壁时，进行下一次扫描，以同样的依据选择出接下来的路径。直到区域内所有垃圾指标大于1的点的比例都小于0.5%，认为垃圾已基本清扫完。针对题目附件1所给垃圾分布数据，使用C++程序计算得出区域划分的数目与清扫时间的关系见下表：areasx*areasyNLg(N)time1*1106.872*240.606.674*280.908.445*5251.405.9310*5501.707.2310*101002.007.0750*502502.405.73100*125125004.106.57100*250250004.404.14当整个区域作为一个整体时，清扫完耗时6.87分钟；划分为四个区域时，耗时6.67分钟；根据题设数据，极限情况下每个点划分为一个区域，清扫完耗时4.14分钟；可见对于所给垃圾分布情况，划分的区域越多，清扫完毕用时越短。问题二：智能程度高的扫地机每次可以选择清扫垃圾指标值最大的地方清扫，需多长时间才能保证清扫完该区域。针对这个问题，我们提出了基于极值的路径动态规划模型，C++程序处理方法类似问题一，路径选择依据为：扫描从起点出发，每个以经过扫地机圆心的直线为轴，间距0.4米（扫地机直径）的平行线画出的平面，以覆盖垃圾指标值最大的点最多的平面为扫地机的路径面，进行清扫；当扫地机碰到墙壁时，进行下一次扫描，以同样的依据选择出接下来的路径。直到区域内所有垃圾指标都不超过1，保证清扫完该区域。针对题目先后两次所给垃圾分布数据，使用C++程序计算得出的使用该路径选择方法下清扫时间为：验证数据求解时间（/分钟）原始数据15.68更新数据25.49问题三：其他条件同2，如何设计扫地机的路径，保证以最短时间清扫完该区域。垃圾指标值越大的点需要扫地机扫过的次数越多，针对这个特点,提出了基于分散程度的路径动态规划模型。机器人起始及每一次碰壁转弯前，和基于极值的路径动态规划模型一样扫描出区域中垃圾指标值最大值，选择出覆盖垃圾指标值最大的点最多的路径，同时，所选路径还要满足该路径清扫区域中各最大指标值格点周边的格点方差最小。这样每次都集中清扫大指标的点，能够在最短时间清扫完该区域。关键词：环境模型路径规划栅格模型最大覆盖最小重复动态规划3一、问题重述随着科学技术的不断发展，扫地机逐步走入平常百姓家，并被越来越多的人所接受，扫地机（也称扫地机器人）将在不久的将来会由现在的初级智能向着更高程度的智能化程度发展，逐步取代人工清洁。扫地机是通过电动机的高速旋转，在主机内形成真空，利用由此产生的高速气流，从吸入口吸进垃圾。扫地机一般为半径0.2米圆盘，运行速度一般在每秒0.25米左右，只走直线，且碰到墙壁等障碍才可转弯。与传统的扫地机不同，智能扫地机可以通过微处理器进行现场环境分析，自动选择运行路线。遇到障碍发生碰撞后将重新随机地选择路线，逐步进行清扫。智能扫地机具有记忆、存储功能。利用传感器扫描现场环境，设计运行路径并存储。一般不能100%的清扫指定区域（如墙角部分）。机器在工作电压不足时会自动回到充电站充电。考虑图1的工作现场，其中点A（1,5）为扫地机充电站，区域的垃圾指标见附件1.不考虑再充电情况，我们需要解决如下问题：（1）有些低档的扫地机因为价格低廉，智能程度不高。其工作时的路径选择方案是将现场分成若干区域（例如上下左右4个区域），并通过传感器间隔一段时间扫描现场一次，选则垃圾最多区域清扫。假设每次扫过的区域垃圾指标值减少1。针对附件1，估计清扫完给定区域大致需要的时间（尽量保证每个点的垃圾指标不超过1）。（2）智能程度高的扫地机每次可以选择清扫垃圾指标值最大的地方清扫，每次扫过的区域垃圾指标值减少1。该机器人需多长时间才能保证清扫完该区域（区域内指标值不超过1）。比较问题1与问题2，说明问题1中方案的合理性。（3）其他条件同2，如何设计扫地机的路径，保证扫地机以最短时间清扫完该区域。二、问题分析这是一个典型的路径规划问题，面向对象是智能清扫机器人。在解决本问题之前，已完成了环境建模，即题中已给出房间环境和垃圾分布情况，我们只需要针对现有环境设计出最优路径，使得智能机器人能在最短时间内按一定指标清扫完给定区域。具体实现中，我们利用C++编程，根据坐标系上区域大小建立一个二维数组，数组数据与坐标值一一对应，编写程序对数组进行一定操作，从而完成对问题的数学求解。4三、模型假设与约定1)假设扫地机每次从A点开始出发。2)假设扫地机碰撞到墙壁后再进行下一次扫描，扫描与重新选择路线的时间花费忽略不计。3)假设扫地机运行速度恒定为匀速每秒0.25米。4)假设每次扫过的区域垃圾指标值减少1。5)假设扫地机每两次转弯间扫过的区域为两条平行线之间与给定房间区域的相交部分。6)约定扫地机只走直线，且碰到墙壁等障碍才可转弯。7)在第一问中，约定当垃圾指标值大于1的点数占总数的比例小于0.5‰时，认为清扫完成。在第二问中，约定区域内所有点指标值不超过1时，清扫完成。四、符号说明及名词定义正文及编程中用到的部分符号符号意义rubbish[col-1][row-1]垃圾分布数组start[]存储转弯点坐标count[]垃圾指标分别计数areasx列向划分数areasy横向划分数N划分区域数dx实际中x方向每两个格点间距离dy实际中y方向每两个格点间距离r扫地机实际半径rx扫地机半径在格点系中x向距离（取整）ry扫地机半径在格点系中y向距离（取整）dist实际中扫地机完成一次清扫总路程time实际中扫地机完成一次清扫总时间五、模型建立总体模型：根据房间尺寸和垃圾分布情况，运用“栅格法”将垃圾分布点阵化和权值化，建立一个平面直角坐标系，根据行列号转换成相应的坐标，每个坐标点上的数据代表栅格属性（即该栅格内垃圾指标值）。在坐标系上标出各转弯点，之间依次序连线。在每两个转弯点之间，以连线为中心直线，与中心直线距离为一个“扫地机半径”的两条直线间在区域内的格点上的坐标值（即垃圾指标值）减一。最后整个区域内每个格点上坐标值符合约定要求，认为清扫完成。坐标系上转弯点连线总长按一定比例换算后即为实际中机器人所走路程，继而算出本次清扫所需时间。要求在条件相同情况下，所得时间最短。在转换后的平面直角格点系中：中心直线方程：5y=kx+b0(1)斜率：k=yi+1−yixi+1−xi(2)b0=yi+1−kxi+1(3)其中点（xi+1，yi+1），（xi，yi）分别表示两个依次序相连的转弯点（即扫地机每次碰壁需重选路径转弯时的圆点）坐标。与中心直线距离为一个“扫地机半径”的两条直线方程：y=kx+b0+b(4)其中：b=r√(kdydx)2+1dy(5)r表示扫地机实际半径，dx、dy分别表示实际中x方向、y方向每两个格点间距离。扫地机完成一次清扫实际总路程：dist=∑√(yi+1−yi)2dy2+(xi+1−xi)2dx2n−1i=0(6)扫地机完成一次清扫实际时间：time=distv(7)在本题中假定扫地机以匀速率v=0.25m/s做直线运动。问题一模型（基于区域分解法的路径动态规划模型）：在总体模型的基础上，将总区域等分成N=areasx*areasy份区域（N=1,2,3,…,col*row），扫地机起始及每次碰撞后一次路径选择遵循以下两条原则：①前往垃圾指标值之和最大分区；②所选路径清扫区域与待前往分区域重叠部分垃圾指标值之和最大如此建立模型的依据：使扫地机一次经过垃圾指标值之和最大分区使其垃圾减少最多（如图1.）。图1.问题二模型（基于极值的路径动态规划模型）：在总体模型的基础上，起始及每一次碰壁转弯前，扫描出区域中垃圾指标值最大值，6而后一次路径选择遵循以下两条原则：①路径清扫区域中必须包含最大垃圾指标值所在格点。②路径清扫区域中最大垃圾指标值所在格点数最多。如此建立模型的依据：优先清扫最大垃圾指标值所在区域并尽量使其被快速清除（如图2.）。图2.问题三模型（基于分散程度的路径动态规划模型）基于模型一、二引入如下度量。首先对整个区域垃圾指标值最大的点进行计数标号，其次计算每一个指标值最大点在机器人直径大小的正方形区域内的方差，并根据其大小赋予一定权值（权值为：1，2），权值越大代表方差越大。机器人起始及每一次碰壁转弯前，扫描出区域中垃圾指标值最大值，而后一次路径选择遵循以下两条原则：①路径清扫区域中最大垃圾指标值所在格点数最多。②路径清扫区域中各最大指标值格点得权值之和最小。六、模型求解与检验问题一模型求解：根据本次竞赛中给出的第二组数据（即更新后附件）绘出垃圾分布图（用originlab9.0软件绘出）如图3.所示：7图3.图中深红色、红色、绿色、紫色区域垃圾指标值依次为4、3、2、1。从图中可以比较明显的看出该垃圾分布比较集中，即垃圾指标值空间极值区域（点）较少。根据该组数据，将其转化为平面直角格点系后，得出几个重要的变量数据如下：扫地机起始点坐标：A(17，240),行数：row=251（程序自动得出），列数：col=100（程序自动得出），实际中x方向每两个格点间距离：dx=0.06，实际中y方向每两个格点间距离：dy=0.02,扫地机半径在格点系中x向距离（取整）:rx=3,扫地机半径在格点系中y向距离（取整）:ry=10。根据本次竞赛中给出的第一组数据（即更新前附件）绘出垃圾分布图如图4.所示：图4.图中红色、橘红色、绿色、紫色区域垃圾指标值依次为3、2、1、0。从图中可以比较明显的看出该垃圾分布与上组数据对比比较分散，即垃圾指标值空间极值区域（点）较多。根据该组数据，将其转化为平面直角格点系后，得出几个重要的变量数据如下：扫地机起始点坐标：A(10，240),行数：row=251（程序自动得出），列数：col=301（程序自动得出），实际中x方向每两个格点间距离：dx=0.02，实际中y方向每两个格点间距离：dy=0.02,扫地机半径在格点系中x向距离（取整）:rx=10,扫地机半径在格点系中y向距离（取整）:ry=10。由于格点系可与C++程序语言中的二维数组相对应，故我们将该格点系中的数据导入到“data.txt”文件中，利用VisualStudio2010软件，在C++中调用所有数据，构建相应的二维数组。然后编写程序，将房间区域N等分（人为设定），根据建立的模型及约定的清扫结束条件，设计算法（简易）如下：8其中按模型路径选择原则找到单次清扫路径（即扫地机相临两次碰撞间路线）的算法为：判断上一次碰壁点位于哪条区域边界（内缩一个转换后“半径”单位）上，以此为路径起点，先将路径终点置于该条边的某个端点处，按顺时针方向沿边界逐个格点的移动路径终点，并比较清扫区域内模型选择条件，直至路径终点移至起点所在边界的另一端点处，找到符合条件的路径并记录终点坐标（作为下一次清