论文总字数：20840字

目 录

第一章 绪论 1

1.1课题研究背景及意义 1

1.2国内外研究现状 1

1.3 论文安排及主要内容 3

第二章 扫地机器人路径规划技术 3

2.1 全覆盖路径规划技术 4

2.2 全局路径规划与局部路径规划 4

2.3 路径规划方法 5

2.3.1 遗传算法 5

2.3.2 人工势场法 5

2.3.3 A-Star算法 6

第三章 路径规划算法设计 6

3.1环境建模 6

3.2 栅格法改进与设计 8

3.3　算法设计 8

3.4　局部路径规划 9

3.4.1 严格Z字形遍历 9

3.4.2 改进的Z字形遍历 10

3.4.3 死结点问题 11

3.5 基于局部路径规划的探索算法 12

3.6 全局路径规划 14

第四章 算法仿真与实验 15

4.1 开发环境 15

4.2 栅格算法仿真 16

4.3 算法实现 17

4.3 仿真结果与分析 18

4.4 总结与展望 21

第五章 结束语 22

参考文献 23

致谢 24

第一章 绪论

1.1课题研究背景及意义

扫地机器人已经成为人类最伟大的发明之一。自发明以来，发生了巨大变化。现在，服务扫地机器人有了更大的创新，朝着多功能，智能，独立，多领域的发展。随着人们购买力的逐渐提高，居民的消费观念也在悄然变化，这表现为对服务扫地机器人等智能产品的需求明显增加。在这种环境下，城市化与现代化不可避免的带来了生活节奏快速化与家务劳时劳力的矛盾。于是新的需求便产生了，人们亟需可以解放这种低效率劳动的机器人，而扫地机器人便应运而生。在如今这个环境下，移动技术，物联网技术的蓬勃发展使得人们通过使用更加智能的移动手机作为移动的智能客户端，并进一步控制扫地机器人进行自主清扫，极大的提升了智能产品的用户体验，从而开创了家庭服务扫地机器人产业与物联网和智能家居生活。紧密的关系在一起。近年来，中国家庭服务扫地机器人的市场需求迅速增长。中国服务扫地机器人的市场规模迅速扩大，已成为扫地机器人市场应用的一个亮点。技术的发展促使“互联网 扫地机器人”步入家庭。伴随着我国城乡居民老年人口不断地增多，社会压力不断增大，以及我国各种科技战略，创新政策的不断实施与推进，自主扫地机器人同其他服务型机器人日益融入人们生活中，并不断推进生活质量的提高与人们生活的智能化，互联网 扫地机器人将完美解决居民的实际需求，并推动社会的智能化与现代化。

传统的清扫工作是费时劳力的工作，即使如今越来越多的清扫工具被运用到了扫地工作中，例如吸尘器，全自动拖把，然而仍未将人类从这种低效率劳动中解放出来。扫地机器人就可以完美的解决这一问题，它能在各种复杂的环境下工作，代替人工来实现清扫功能，节省人们的时间。扫地机器人可以以一种极高的效率重复这种低效率的清扫工作，将人们从繁重劳动中解放出来，并运用到更具效率的工作中。扫地机器人可以完美的契合现实状况的需要。本文重点研究了扫地机器人中最重要的路径规划算法，对探索扫地机器人、探索机器人、收割机器人等领域具有十分重要的意义。

1.2国内外研究现状

德国斐纳TOMEFON是世界上第一家将人工智能运用到扫地机器人公司，斐纳TOMEFON凭借着独特的眼光以及专业的技术，在扫地机器人的研制以及创新上始终领先于行业。斐纳TOMEFON是专门从事室内净化领域40多年的专业人士。它在目前扫地机器人领域提出了许多开创性的思路。它的智能清扫机器人具有内置的无线载波定位导航系统，可以实现自动扫瞄和自动规划路径，并通过精确的算法实现清扫轨迹。规划没有盲区。与此同时，斐纳 TOMEFON扫地机器人具有吸尘、清扫、拖曳等多种清洗方法。，可以一次清理地面灰尘。近期旗下推出了智能扫地机器人TF-880S，见图1.1，它采用红外扫描探测系统，单扫描面积可以达到150平方，覆盖一个屋子，更准确的进行数据采集。清扫机器人采用规划式清扫，可根据地图自动分区，对单个分区进行清扫时采用Z字形清扫，并记住以清扫的区域，做到智能不重复清扫。

随机碰撞式扫地机器人是最早采用的技术，规划式技术清扫是近几年才提出的技术，此技术一经提出就得到广泛关注，美国的各大扫地机器人厂商都将其运用到自身产品中，这种规划式清扫技术已经得到无数家庭使用的验证。

图 1.1 智能扫地机器人TF-880S

国外三大品牌代表性作品：

iRobot （全线系列）

随机碰撞型：iRobot Roomba 880 （随机碰撞型最高款，价格8999元）

扫描规划型：iRobot Roomba 980 （规划型最高款，价格8999元）

Neato （主打规划型）

扫描规划型1：Neato Botvac D75 （规划清扫最基本入门款，价格3999元）

扫描规划型2：Neato Botvac Connected （规划清扫最高款，价格7980元）

福维克 （主打规划型）

扫描规划型：福维克 VR200 （规划型目前实力最强代表作品之一，价格7280元）

2015年我国开始大力发展人工智能，自此以后，我国各大高科技公司都将目光投入到智能机器人领域。如今，几个互联网巨头都已建立了有关人工智能的研究机构。现如今我国最火的扫地机器人就是米家扫地机器人，米家扫地机器人自主研发了浮刷设计，浮刷可以根据地面高度接近地面,上下浮动。米家扫地机器人也采用了规划式清扫。然而我国大多数厂商仍然采用随机式运动算法。

图 1.2 米家扫地机器人

目前在扫地机器人扫地算法上有两类，分别是随机式清扫算法与规划式清扫算法。

随机式清扫：现在大多数扫地机器人都存在的问题是乱扫问题，扫地机器人在某些地方多次往复清扫，而在另一些地方则根本不闻不问，这是由于现在出售的扫地机器人很多是随机式清扫算法的扫地机器人。随机式扫地机器人是基于随机碰撞算法，即遇到障碍物就以一个随机生成的角度转向，覆盖率依靠不断地重复清扫来实现，效率大打折扣。

规划式清扫：规划式清扫四要素：定位-建模-规划-清扫 （缺少任意一个要素都无法完成规划式清扫）。规划式清扫的原理：首先用定位技术和传感器技术对环境进行扫描和建模，生成电子地图，再根据电子地图运用算法计算出合理的清扫路线，并驱动扫地机器人进行清扫，同时利用定位技术确保扫地机器人可以到达预定的位置。（目前市场上许多扫地机器人采用了优化的Z字形清扫算法，但是缺少定位和建模技术，其本质还是随机式清扫）

图 1.3 规划式与随机式算法

由此可见，规划式算法无论是清扫效率还是覆盖率都远远优于随机式算法，故此，本文讨论规划式清扫算法。由于规划式算法的核心是路径规划算法与地图建模，本文将在下面重点讨论。

1.3 论文安排及主要内容

本文主要是以室内扫地机器人为目标讨论路径规划算法，而路径规划算法中的核心内容是地图建模和局部清扫和死结点问题（扫地机器人进入死路问题）。本文主要研究了扫地机器人路径规划算法的仿真与研究，并对其进行改进，分析讨论了该算法的改进方向与可行性研究，本论文的主要章节安排如下：

第一章 阐述了国内外室内扫地机器人的发展情况，分析该领域的技术发展趋势，为本文算法提供现实依据与背景支持。

第二章 分析与讨论了当前扫地机器人领域较为热门的几种技术，比较各自的优劣性，为本文算法提供技术支持，并分析了算法的构思思路。

第三章 详细阐述了路径规划算法的设计：对环境地图进行了栅格法建模，设计了局部Z字形覆盖算法，改进的Z字形覆盖算法，未知环境探索算法，全局路径最优规划算法。重点讨论了遇到障碍物或边界避障算法和遇到死结点问题的处理。并将A-Star算法运用到全局路径规划中。讨论了在全局环境已知和未知情况下的算法。

第四章 根据设计的算法形成Java程序在Eclipse环境下进行仿真，对路径规划算法进行可行性分析，并对比了改进前后算法效率问题。

第五章对于本文的研究过程进行了总结，并指出了后期工作的研究方向。

第二章 扫地机器人路径规划技术

2.1 全覆盖路径规划技术

扫地机器人实现自主智能工作的关键技术是：传感技术，地图建模，定位技术，路径规划技术，吸尘技术和电源技术。考虑到本文知识算法仿真并不涉及实体设计，故在此只讨论探测、地图建模、路径规划。倘如扫地机器人存有地图，路径规划相对较简单，然而通常情况下，扫地机器人需要自主探索出环境地图，以此路径规划算法可以划分为为三大组成部分，它们分别是得知自身位置与探索周围环境、全局路径规划与局部路径规划。由上可知，路径规划算法主要解决的问题有：

（1）存储环境的信息的地图。

（2）扫地机器人的位置和探索周围环境信息。

（3）导向正确的运动路径。

“导航”是自主机器人在运动过程中确定路径的技术。导航需要扫地机器人测量并分析其传感器传入的环境参数，根据参数对自身进行定位，设计出达到目标地点的具体路径，并调节自身运动以保证按照预期路径到达任务地。在本文中不涉及硬件实施的问题，所以导航模块中的定位功能并未算入路径规划之中。

扫地机器人的核心技术上定位、环境建模与路径规划，也是判断其性能优劣的标准，路径规划算法更是其算法的核心内容。该算法主要任务是使扫地机器人顺利清扫完全部位置，并且在清扫的过程中扫地机器人不会碰到任何障碍物或边界，在此基础上，路径规划的任务也包括使扫地机器人覆盖效率尽可能高，重复率尽可能小，死结率尽可能小。

路径规划是扫地机器人主要研究内容之一，是指导扫地机器人行进的核心技术，指出了扫地机器人前进的路径。

路径规划问题有如下特点：

（1）复杂性：在现实情况下，扫地机器人所面临的环境往往复杂而多变。

（2）约束性：扫地机器人受到障碍物和边界的双重约束。

（3）目标性：扫地机器人在清扫过程中的目的是：尽可能覆盖所有清扫区域，高效率等目标，然而其往往存在这冲突。

（4）随机性：环境中往往有许多突发状况，因此存在很多随机因素。

路径规划问题基本可以分为四类：

（1）在已知环境中存在静态障碍物的规划。

（2）在未知环境中存在静态障碍物的规划。

（3）在已知环境中存在动态障碍物的规划。

（4）在未知环境中存在动态障碍物的规划。

本文将研究已知环境中静态障碍物或边界的路径规划和未知环境中静态障碍物或边界的路径规划。

2.2 全局路径规划与局部路径规划

根据对环境信息的需求程度可以把路径规划分为两种：需要局部环境信息的局部路径规划与需要全局环境信息的全局路径规划。如果从是否需要事先知道环境信息的角度来看，局部路径规划是动态实时规划，全局路径规划是静态预先规划。局部路径规划的实质是避障算法，即扫地机器人在遇到障碍物时的应对方法，通过转向已达到避开障碍物的目的，它只需要实时的运算，而全局路径规划必须事先知道全局的环境信息，要求了解传感器采集到的数据，确定自身与目的地的位置，与障碍物的分布情况，在行进之前就已经计算好所前进的路径，然后按路径行进，是一种提前规划的静态规划算法。

在全局规划中，清扫机器人必须首先检测到准确的全局环境信息，国内的全局路径规划已经取得了相对成熟的成果。然而，在未知的环境中，清扫机器人事先并不知道全局环境信息，因此全局路径规划不能正常工作。

局部路径规划在未知的环境中进行，虽然不知道全局的环境信息,然而,它可以更好的适应未知环境和探索,在局部路径规划,扫地是采用机器人避障算法,边缘的障碍或环境,使整个运动过程中,全面的机器人不遇到任何障碍或边界,所以机器人的运动大多是使用局部路径规划,这种方法依赖于传感器避障,环境未知或部分未知的情况下完全依靠传感器障碍或边界形状,位置,等。当我们发现一个静态障碍或边境清扫机器人前进道路上,计划的障碍或边界相交路径的至少两个机器人,机器人可以这个时候不再沿着预定的道路,而是走,边缘的边境障碍或请求机器人的行走而来定位自己的位置,一旦大规模机器人发现了一些点位于默认路径和障碍或边界在同一点,这个点应该按照默认路径行走。

剩余内容已隐藏，请支付后下载全文，论文总字数：20840字

相关图片展示：