《基于Dijkstra算法的清扫机器人最短路径规划及仿真实现》8600字（论文）

基于Dijkstra算法的清扫机器人最短路径规划及仿真实现摘要随着如今时代的快速发展，信息时代的来临，电能和机械已经离不开我们的日常，无论是哪种行业，都已经离不开机械的辅助。清扫机器人是能够代替人力进行人们日常所需的环境清理的一种机器，只需消耗一定的电能，就能代替人力完成烦杂的清扫任务。清扫机器人的路径规划是清扫机器人要求解的核心问题，其目的在于寻求无碰撞最优路径。Dijkstra算法是一种经典的求解最优路径的算法，计算一个顶点到其余各个顶点的最小移动代价，可解决清扫机器人运行路径的问题。本文设计实现了基于Dijkstra算法的清扫机器人的最短路径规划，计算较为复杂的地形，规划其最佳路径，并进行仿真实现。关键词：清扫机器人；路径规划；最优路径；Dijkstra算法 目录 TOC\o"1-3"\h\u1绪论 51.1课题研究背景及意义 51.2国内外研究现状 61.3课题研究的主要内容及组织结构 72开发软件简述 82.1python 82.2PythonIDLE 82.3Pycharm 93Dijkstra算法 103.1Dijkstra算法的基本原理 103.2Dijkstra算法原理的图解 103.3Dijkstra算法的优缺点 134基于Dijkstra算法的清扫机器人最短路径规划的设计 144.1搜寻路径的目标效果 144.2开始位置、目标位置、地图创建 154.3地图的初始化和障碍物的设置 164.4机器人的运动方式以及栅格编号 174.4.1机器人运动方式 174.4.2栅格编号 184.5搜寻路径 194.5.1搜寻流程 194.5.2判断边界、障碍物 204.6获得最短路径 205仿真实现 226总结与展望 24参考文献 251绪论1.1课题研究背景及意义用于生产的第一台机器人是在1959年由恩格尔伯格发明的，机器人这一新事物就逐渐成为科研人员研究的焦点[1]。尤其是随着科学的逐渐发展，人工智能行业的不断更新，机器人的重要性早已经发展成为人们生活中必不可少的一部分。世界上逐渐涌现出许多不同类型的机器人，比如应用于AI的机器人，服务于清洁机器人，工业领域的机器人，可以进行运输的机器人，在水下作业的机器人，目前，人们研究机器人的方向被分为三个部分：构建机器人周围环境的地图、规划机器人最短路径、搜索和导航机器人行动轨迹。1960年代后期，斯坦福的研究所开发出了能自己移动的机器人[1]。研究所表明，机器人的最短移动路径问题，是机器人最为核心的问题关键所在。在机器人的工作系统中，寻找从开始位置到目的地位置的最佳无碰撞行动路线。到了现代，清扫机器人的路径规划问题可以说是如今研究机器人的领域之中，最为核心的一个研究方向。路径的规划问题，它的本质就是对计算出清扫机器人最短路径的算法的一个研究问题。尤其是近几年来，随着互联网+的时代来临，国内外大量的学者专家对于机器的能源消耗最佳化的要求颇为急切。对于清扫机器人的最短路径的规划，也是最为直接的减少能源消耗的途径之一。有很多可以应用的规划路径，因为他们的优缺点的原因应用的领域范围也不同。根据不同领域的通路规划运算法则研究，按照不同的运算法则和运算法则的基本原理，运算法则大致可分为四大类:现有的运算法则、图形方法、智能生物工程运算法则和其他运算法则[2]。Dijkstra算法应用研究，将它应用到我们日常生活的各个部分，包括机器人的移动路径、农产品流通和城市运输系统等。如果是给定的乳腺图示，则应该用传统的Dijkstra算法适当地修改一个决定起点和终点之间最短路径的问题，让终点立即显示出来，并使之达到最短距离并输出各种存在的最短路径对于给定了一个有向图,确定起始点和结束点的最短路径问题，必须对Dijkstra算法做出适当的改变,当他搜寻的路径一旦到达最终标记的地点，就立即结束寻找,然后计算出开始点和最终点之间的最佳距离，并且输出。1.2国内外研究现状清扫机器人是一种家庭服务机器人，目前清扫机器人是使用最广泛的服务机器人类型。机器人多用于清洁室内地板，特别是在住宅、酒店、办公楼和其他地方。人们想要除去重复的、乏味的清洁工作，所以利用这个机器人就会达到人们的理想。清扫机器人的研究始于20世纪80年代。经过30多年的开发，国内外开发出了很多产品，在市场上取得了巨大成功。从技术角度来说，清扫机器人包含人工智能、电子技术、数学和机械设计等主题。它具有很强的实用性和自主性，集成了知识的各个方面。清扫机器人的工作环境通常是一个封闭的内部房间，需要足够的智能来检测周围的环境，并独立进行路径规划和完成清洁。有必要以较低的重复率完成整个区域的清理工作。因此需要一种能够实时的计算出最短路径的计算机算法，而Dijkstra算法就是其中一种可以满足这些需求的算法，当室内出现了需要清洁的污垢，系统可以自主的计算出最短的最佳路径，然后控制清扫机器人来到目标地区进行清洁。Dijkstra算法是E.W.Dijkstra在1959年提出的，也被称为Dijkstra算法[11]。他使用了一个贪心算法，现在被认为是最快的方法。最短路径的计算方法分为最短路径的静态计算和最短路径的动态计算。静态最短路径算法被设计成在不改变外部环境的情况下计算最短路径。它主要是迪杰斯特拉算法和A*(AStar)算法。动态路径的最短途径是指，持续变化的外部环境如果预测不能如期进行，则计算出最短途径。例如当敌人或障碍物持续运动的时候。Dijkstra的算法解决了从一个来源到另一个顶点的最短路径问题。它的主要特征是从一开始就使用贪心的算法，每次它转向接近起点的邻近节点时，最接近起点的节点直到到达终点才被访问。迪杰斯特拉算法基本应用于最短路径方向研究的。在许多工作流程中，具体的内容他以简明概要，主要是关于数据的结构、图表方面的理论、运行过程中数据的研究。特别值得令人注意的是此算法不需要对图形的负加权边不做特别的研究规划。经过这么多年来国内外学者的研究发现，最短路径的算法除了Dijkstra算法之外，还产生出了许多不同的算法，简单的列举出几种类型：Floyd运算法则(亦称扩散)是一种运用动态程序设计的运算法则，以在给定的权重图表中找到各源之间的最佳路径。使用动态编程算法来查找给定的最佳路径它的名字取自它的创始人之一RobertFreud[12],他是在1978年TuringAward获奖者和StanfordUniversity计算机科学学院的教授级别大师。动态的编程算法是描述Floyd算法的重要特征。与Dijkstra的算法相似核心的想法是在两个顶点之间插入一个或多个通过点，通过更短的通过点和不通过的距离进行比较。同时，相邻方阵中必须有两个D字行，利用已知条件计算相邻点之间的距离就是通过它来完成的，第二矩阵P是被称之为中间节点k的数值。Bellman-Ford算法通过反复迭代，反复调整边缘设备E的各个位置，使从调试点到彼此顶点u∈V的最短路径推定数逐渐接近最短距离。Bellman-Ford算法并不超过n-1。每一个步骤都需要在图表的边缘进行改进。完成第一个等级k后，从起点到最边缘查找最短的路径。n-1阶段结束后，最短的路线是从起点到终点。不包含循环葫芦的直接前往。因此通过n-1个边缘获得的最短途径是源代码。从一个点到另一个点的最短路径的特定值。SPFA算法是解决单源代码最短路径问题的算法。可以在图表中使用V-1放松，以便获得所有可能的最佳路劲方案。和迪杰斯特拉的算法相比，优点是边的权重值可能是负数，并且很容易体现出来。他的缺点更复杂，时间复杂性更高。但算法可以通过各种方式优化来提高效率。算法的思路：使用dis图来记录每个节点的给定值，并使用相邻列表或相邻行列保存图表G。实时动态近似模拟法是本算法主要运用的方法:规则规定为“先进先出”。为了支持优化节点，第一个u节点每次都从队列中移除，预留的工作使用当前规划值，在最短的路径点优化。当启动过程中最短端口改变时，v端口现在不在队列中。就会指定u节点v。就会安排点v在队列后面。因此节点不断从队列中移除，所以一直到队列空为止都会一直执行松弛操作。1.3专题研究的主要内容和组织架构本论文主要是以Dijkstra算法为核心，着重研究清扫机器人的最短路径的规划和仿真实现。将Dijkstra算法的基本原理，与清扫机器人的最短路径问题相结合，先模拟出清扫机器人工作地区的地图、障碍物和目标地点，再逐步将搜寻路径仿真出来，最终计算出清扫机器人的最佳最短路径。第一章绪论，这一章概述了Dijkstra算法和清扫机器人的背景以及意义，简单的介绍了除了Dijkstra算法以外的其他最短路径算法的相关知识。第二章开发软件简述，这一章讲述了编写基于Dijkstra算法的清扫机器人最短路径程序的编程程序语言、运行软件和运行环境。第三章Dijkstra算法，这一章主要讲述了运用图形、图表和文字详细的剖析了Dijkstra经典算法的基本原理和运算最短路径的过程，最后还分析了Dijjkstra算法的优缺点。第四章基于Dijkstra算法的清扫机器人最短路径规划的设计，这一章主要是通过流程图、程序还有图表讲述了清扫机器人最短路径程序设计方法和设计过程。第五章仿真实现，这一章主要是对清扫机器人最短路径程序的仿真测试。最后总结了本篇论文的主要研究方向，还有对清扫机器人最短路径计算程序的一些优缺点的总结和对于此程序未来的发展期望。2开发软件简述2.1pythonPython是ABC语言的替代品，它设计于90年代初由荷兰数学与计算机科学研究协会GuidovanRossum研发[13]。有效的数据结构不仅通过Python提供，面向对象的编程也被引出。由于动态输入语言的特性和Python的句法分析，它成为了应用语言，他让更多的软件平台和应用他的企业可以快速地开发脚本和程序。版本的不断更新和新的语言功能正在被逐步使用于一个独立的大应用程序开发项目。Python是一个容易扩展的机器语言，新的函数和数据类型可以通过c或c++开发和扩展。Python也可以用作可调软件中的扩展编程语言。丰富的Python标准库为每个基本系统平台提供源代码或机器代码。自上世纪90年代初Python出现以来，它逐渐被广泛用于系统管理和网页设计。与其他语言相比，被开发成这种语言的读写输入和解释能力和功能都很优秀，有关它本身的标点符号语言比其他语言更加特别。Python是一种解释型语言：说明编译的步骤在研发阶段被取缔。类似于PHP和Perl语言。Python是交互式语言:说明了，通过在Python的符号“>>>”的后方可以直接运行代码Python是面向对象语言:说明了python代码的封装程度已经很成熟了和python是标准面向对象的语言。Python是初学者的语言:Python代码小白而言，是易上手易开发的语言，大部分的应用程序都可以通过此语言进行开发，无论是前端后端还是游戏开发都能使用此语言。2.2PythonIDLEIDLE是Python的集成开发环境。这是通过代码包装的可选部分组成的Python，很多版本的Linux都包含在内。它完全用Python和TkinterGUI工具包编写（Tcl/Tk的包装函数）。通过基本的IDE进行基于Python软件开发的。常规的IDE功能他都具备，是Python非营利开发的一个优质的选择。一旦安装了python,就会自动配置IDLE，所以没有必要单独下载安装它。与此同时，使用IDLE框架Eclipse也可以很方便地调整Python软件。主要功能:句法分离，段落分离，文本编辑，表键控制，程序调试。Idle是GuidovanRossum制作的标准Python发布版[14]。可以在任何情况下都运行Python和TK在闲置的状态环境。打开Idle会显示已提升的对话框命令行接口窗口(这是比删除和粘贴基本对话框命令前端更好的功能)。它还有Python的编辑器(虽然没有整合代码，但具有自动输入代码的功能)，类浏览器和调试器。点击下面菜单的虚线，菜单将会更新到永久窗口。值得注意的是编辑”菜单在基础画面边缘的边角处倾斜是很有用的。中断点可由IDLE提供变量检测功能但没有存储内存地址和可变内容的存储或同步等分析功能。2.3PycharmPyCharm是很成熟的应用于python的软件平台，Python的开发失效率和速度都有很大的提升。除了调试、报告语句错误、项目管理、代码提示、自动操作、代码测试、单一控制等IDE，还特别提供支持网络开发的Django构件各高级功能。是JetBrains制作的PyCharmIDE软件,同时VS2010的重叠插件Resharper也是由JetBrains研发出来的[16]。同时我们支持GoogleAppEngine来y应用于高级代码相关的分析程序。这个功能是PyCharm转换为Python项目的开发者和初学者的强有力的研发工具。一般IDE拥有的功能PyCharm应有尽有，即调试、加亮词组、管理项目、代码报错、自动操作、代码测试、智能控制等。同时Django的开发引擎的功能还受PyCharm所提供，来支持GoogleAppEngine。IronPython由PyCharm开发的是很具有优势性的。3Dijkstra算法3.1Dijkstra算法的基本原理3.2Dijkstra算法原理的图解首先，closelist与openlist集合有我们提出：1、闭集closelist：记录已求出最短路径的节点。2、开集openlist：记录找不到最短路径的节点。。3、集合1：记录源节点到各节点的距离。4、集合2：记录节点对应的父节点。算法操作步骤：最后，我们重复上面两个步骤，直到遍历所有的节点。首先，源点被添加到closelist集合中，其他节点被添加到openlist中，分析从A到另外剩余节点的距离。不能通过源节点直接到达的距离将被记录为∞。接着从开放列表中选择“最短距离的顶部N”，并将顶部N添加到禁用列表中，同时将顶部N从禁用列表中移除。然后计算从开源列表中的每个节点到a的距离(从开源列表中的每个节点的距离)的距离因为前面的步骤确定了N是最短路径的顶点，因此N可以用来更新到其他顶点的距离。例如，从A到B到C的距离可能小于A到C的距离，从A到C的距离必须在此期间改变，父点C也会随之变换。)最后需要反复进行以上步骤，直到我们通过所有的节点。举个例子，寻找到A到G点的最短距离：图:3-1示例有向图图首先，我们将起点A存入在封闭集合列表中，将未完成的节点放在开放集合中，如下所示:图:3-2示例表格图图:3-3起点A变化图选择最小距离的节点。很明显可以获取点B，把B从一个开放的集合中移除，然后把它添加到一个封闭的集合中。图:3-4搜寻节点表格图图:3-5搜寻节点B图图:3-6更新距离表格图图:3-7更新节点图根据上述方法的类比，直到所有节点都被发现，终点出现在封闭的集合中:图:3-8计算路径表格图最终得到最短路径：G—>F—>E—>C—>B—>A。3.3Dijkstra算法的优缺点4基于Dijkstra算法的清扫机器人最短路径规划的设计4.1搜寻路径的目标效果假定有如下的地图：图:4-1目标地图图左下角为清扫机器人目前的所在位置，而右上角的位置为检测到的需要清理的地区。当我们用Dijkstra算法来寻找最佳路径，最终的效果为：图:4-2目标仿真效果图程序会以我们定义的机器人起点，逐渐向四周进行扩展，直到搜寻到我们定义的需要清扫的目标地点。4.2初始位置，终点位置，绘制地图我们需要创建一个房间地形的模拟图形，包括障碍物的创建，还有清扫机器人的初始点和清扫目标地区：图:4-3地图定义程序图以上程序段主要是对模拟地图的创建，首先用定义了机器人的起点、终点、栅格的大小、还有机器人的半径。然后需要设置地图中障碍物的位置，前面的四个For循环用来设置四周的障碍物，用来模拟房间的四面墙。后面两个For循环用来设置地图内的障碍物，模拟房间中的物品。最终通过plt.plot()指令在格栅地图中画出地图的形状。图:4-4地图描绘程序图以上都只是栅格地图之上模拟地图的创建，最重要的还是对栅格地图的创建，程序段如下：图:4-5格栅地图创建程序图在之前的程序中，我们已经定义了地图的大小，通过提取障碍物的边界值来设置栅格地图的最大值和最小值。接着我们需要得出栅格具体的个数，例如通过（x的最大值-x的最小值）/栅格的大小就能得出x方向上的栅格具体数量。Y方向通过相同方式得出。4.3地图的初始化和障碍物的设置上文只是对障碍物的具体位置和形状进行了描述，但并没有将其设置成障碍物，以此需要以下程序：图:4-6地图初始、障碍物设置程序图先是遍历每个栅格，将其初始化为False，这就是地图的初始化。接着通过前面两个For循环来遍历每个栅格，寻找到障碍物，然后通过另一个For循环遍历每个障碍物，并且膨胀每个障碍物，将其设置为Ture：图:4-7地图假象模型图格栅地图的构建如上所示，R就是格栅地图中机器人的所在位置，o则是膨胀后的障碍物，机器人的半径小于障碍物时，则判定为无法通行。4.4机器人的运动方式以及栅格编号4.4.1机器人运动方式创建好地图之后就是对机器人运动方式的定义了，程序如下：图:4-8机器人运动方式程序图这里定义了机器人向周围八个方向运动的轨迹，以及运动后的花费。4.4.2栅格编号为了能够更快的搜寻到最短路径，我们要对每个栅格进行特定的标号，方便能够最快速的寻找到我们需要的栅格:图:4-9格栅Key的构建程序图这里采用哈希表的方式：Key-Value，将每个栅格进行不同的编号，产生不同的Key，在后面方便将其放入到开集合和闭集合中。效果如下所示：图:4-10格栅Key的效果图4.5搜寻路径4.5.1搜寻流程搜寻路径的流程为将起点放在openlist中，然后进入循环中，把openlist里路径花费g（n）最小的节点加入到closedlist中，然后判断这个路径是否为终点，如果不是就以从这个节点开始，遍历它周围没在closedlist中的邻接节点，然后计算每个邻接节点的路径花费(n)，接着再进入下一个循环，直到搜寻到终点后，循环停止。其流程图如下图4-11所示。图:4-11搜寻流程图4.5.2判断边界、障碍物查看每个节点的搜索过程中，需判别是否有机器人触及了地图边界和障碍物。程序部分代码如下。图:4-12碰撞判定程序图px、py为机器人当前所在的具体位置，前面四个判断的是查看机器人撞到边界，接触到会返回False。后面一个判断是查看机器人是否碰撞到障碍物接触到会返回False，反之会生成一个true。4.6获得最短路径通过上文对路径的搜寻，我们找到了目标点。图:4-13最短路径搜寻程序图这段代码可以用图文来解释：图:4-14最短路径搜寻示意图从起点v1一直到终点v6。在获取最终路径时，我们需要从终点出发寻找。在搜寻完路径后，代码中会记录最短的路径来自于那个节点，比如v6的最短节点来自于v7，v7来自于v4，一直搜寻到起点v1。而v1我们记录的是一个-1的数据，当程序获取的数据为-1时，就判断这段路径已经获取完毕，程序就会停止，最后就能计算出最短路径。5仿真实现这是创建的初始地图：图:5-1地图仿真图如上图5-1中，左下角的点是清扫机器人所在的初始点，而右上角是我们定义的被检测到的需要清扫的目标地点。四周的边框是我们定义的模拟墙面，中间竖着的两条线这是我们定义的模拟障碍物。这是运行程序后的结果：图:5-2结果仿真图如上图5-2所示，图中布满的X，表示的是机器人从起点开始搜寻目标终点的搜寻路径，当寻找到目标终点后，程序就会算出最短路径，然后通过线段显示出来。6总结与展望以上便是对于Dijkstra算法实现清扫机器人路径规划的全部内容。本文主要讲述的就是基于Dijkstra算法的清扫机器人的路径规划以及仿真的实现，首先就是对于Dijkstra经典算法的原理的仔细剖析，再了解了基本原理的基础上，将这种运算最短路径的算法进一步结合到现实生活的问题中来。进一步解决了清扫机器人最短路径搜寻的问题，能减少清扫机器人能量的损耗，节省能源的使用率。Dijkstra算法是目前所熟知的最为方便的一种机器人最短路径的算法，其可以搜寻到地图的每一个角落，直到搜寻到目标位置之后才会停止，因此是一种搜索范围很广的算法。也正是因为Dijkstra算法搜寻范围较广，会将地图的每个点都搜寻一遍，因此可能会造成较大的计算量，会降低机器的运行效率。本文程序里的地图是事先编程给出的，因此，希望在未来能够实现清扫机器人运作和实时地图探测的结合，能够实时的反映出地图上清扫机器人自身的位置和需要清扫的目标地点位置，随时的更新以便随时进行清扫。当然，本文使用的程序只针对出现一个目标地点的情况，希望未来能发展出对多个目标地点进行搜寻计算，能更加贴近生活中的问题然后去解决。参考文献陈智康1,刘佳1,2,王丹丹3,张运喜1,2.改进Dijkstra机器人路径规划算法研究[A].（1.天津职业技术师范大学天津市信息传感与智能控制重点实验室，天津;2.天津职业技术师范大学自动化与电气工程学院,天津;3.青岛市技师学院，青岛），2020梁波,杨新民.一种基于改进型Dijkstra算法的路线规划方法研究[A].南京:中国电子科技集团公司第28研究所，2020耿振余,陈治湘,黄路炜,李德龙,刘思彤，周宏升，王立华编著．软计算方法及其军事应用[M].国防工业出版社，2015.12秦丽园.简析BP神经网络算法[A].四川成都:成都理工大学，2016丁艳,管燕明.粒子群算法优化研究[A].广东广州，2018郑树泉.工业智能技术与应用[M].上海:上海科学技术出版社，2019张海涛,程荫杭.基于A*算法的全局路径搜索[A].《CNKI;WanFang》，2007夏正东,卜天明,张居阳.SPFA算法的分析及改进[A].上海;华东师范大学上海市可信重点实验室，2014.王超,高武奇.基于AHP与Bellman-Ford算法的停车规划方法[A].陕西西安：西安工业大学电子信息工程学院,2017郭志军.Floyd-Warshall算法的C语言实现[A].辽宁:辽宁对外经贸学院信息技术系，2008刘小玲,李辉,郭治国.基于狄克斯特拉算法的车间动态生产能力评估与实现[J].微计算机信息，2006(12):96-98郝自军,何尚录.最短路问题的Floyd算法的若干讨论[J].重庆工学院学报(自然科学版),2008,(05):156-159.[2017-09-02].黄海涛.Python3破冰人工智能从入门到实战.北京:人民邮电出版社，2019KennethReitz,TanyaSchlusser著.Python漫游指南影印版英文版:东南大学出版社，2017.10：第35页百度百科.Pycharm.[EB/OL].[2014