摘 要

移动机器人自主导航是机器人智能化和人工智能（AI）的关键技术。其核心是精准的定位和实时路径规划，即依据某些最优准则，在变化的环境中规划出从起始状态到目标状态，并且能够避开障碍物的最优路径。移动机器人自主导航的运用极其广泛，小到高德地图的导航，游戏中角色的移动，以及无人机等，大到炙手可热的无人驾驶汽车，火星探测中的智能探测机器人等。目前的机器人路径规划方案中还存在着一些不足之处：全局规划中效率不高，局部规划中动态规避障碍的实时性较差。

D*算法，即动态A*算法（D-Star，Dynamic A Star），是一种启发式的路径规划算法，由卡内基梅隆机器人中心的Stentz于1994年和1995年在两篇发表的文章中提出^[1]。本文研究基于D*算法的动态环境路径规划算法。

本文对比了国内外移动机器人路径规划的研究现状，然后研究了A*算法和D*算法的基本原理和路径搜索过程。并且以Python语言作为仿真语言，利用栅格法建立环境模型，分别对A*算法和D*算法做了仿真。接着根据仿真结果，比较D*算法和A*算法的差异，分析基于D*算法的动态环境路径规划特点。最后总结和展望了移动机器人路径规划的发展。

关键词：移动机器人 D*算法 自主导航 路径规划

Abstract

Mobile robot autonomous navigation is the key technology of robot intelligence and artificial intelligence (AI). The core is accurate positioning and real-time path planning, which is to plan the optimal path from the initial state to the target state in a changing environment according to certain optimal criteria, and to avoid obstacles. Autonomous navigation of mobile robots is widely used, ranging from the navigation of Golden Map, the movement of characters in the game, and UAVs,to driverless cars, intelligent robots for Mars exploration , etc.

D* algorithm is dynamic A* algorithm (D-Star, Dynamic A Star), proposed by Stentz of Carnegie Mellon Robot Center in 1994 and 1995 in two articles. This paper studies the dynamic environment path planning algorithm based on D* algorithm.

This paper compares the research status of mobile robot path planning at home and abroad, and then studies the basic principles and path search process of A* algorithm and D* algorithm. And using Python language as the simulation language, the grid model is used to build the environment model, and the A* algorithm and D* algorithm are simulated respectively. Then, according to the simulation results, the differences between D* algorithm and A* algorithm are compared, and the characteristics of dynamic environmental path planning based on D* algorithm are analyzed. Finally, the development of mobile robot path planning is summarized and forecasted.

Key words：Mobile robot D* algorithm Autonomous navigation Path planning

目录

摘要 I

Abstract II

第一章 绪论 1

1.1 相关背景 1

1.2 国外研究现状 2

1.3 国内研究现状 4

第二章 路径规划D*算法 5

2.1 A*算法 6

2.1.1 A*算法简介 6

2.1.2 A*算法代价函数 6

2.1.3 A*算法基本原理 7

2.2 D*算法 7

2.2.1 D*算法简介 7

2.2.2 节点状态 7

2.2.3 D*算法基本原理 8

2.3 A*算法和D*算法的比较 9

2.3.1 相同点 9

2.3.2 不同点 9

第三章 路径规划仿真 9

3.1 仿真语言Python 9

3.2 环境建模方法 10

3.3 仿真结果 11

3.3.1 A*算法仿真结果 11

3.3.2 D*算法仿真结果 15

3.4 仿真结果分析 19

第四章 总结和展望 20

参考文献 22

致谢 24

第一章 绪论

1.1 相关背景

移动机器人是一种能够接受人类指挥，或者按照预先设定的程序指令，自动执行一定工作的机器装置或系统，其任务在于代替或协助人类执行某些危险性工作。

20世纪60年代末期，人们开始了对于移动机器人相关领域的研究，集中了自动控制科学，人工智能科学，自动化工程，计算机科学技术以及传感器检测技术等多种学科的研究成果，体现了现代社会人类各种先进的科学技术。

随着人类社会科技和经济的发展，移动机器人也逐渐走出实验室，开始运用于实际生产生活中，在太空勘探、海洋开发、能源开采等各种高风险、高精度、高要求、高工作量的各种生产工作中发挥着重要的作用，极大解放了人类的生产力，降低了人类的工作危险。

移动机器人的应用范围越来越广，应用领域越来越多，人类也对移动机器人寄予厚望，希望移动机器人可以在更多的领域发挥更重要的作用，因此移动机器人的研究也愈加受到追捧，成为了社会科学技术发展最活跃的领域。经过将近半个世纪的发展，移动机器人取得了许多突破性的成果，但是在某些方向和问题上，还有待解决和完善。

移动机器人路径规划技术是移动机器人技术研究的核心和主要研究领域之一。所谓路径规划，指的是根据某种或多个优化条件，搜寻出一条从起点到终点，同时规避开所有障碍物，并且能够经过某些要求经过的点的最优或者近似最优的路径^[2]。

根据对工作环境信息的掌握程度不同，机器人路径规划可以分为局部路径规划和全局路径规划两种类型。局部路径规划则是在工作环境信息完全未知或者部分已知的情况下，通过传感器对周围环境进行探测以获取机器人当前的局部环境信息，让移动机器人能够规避障碍物，并且对移动机器人路径规划结果进行反馈和校正。但是由于缺乏全局环境信息，无法构建完整的工作环境模型，因此无法确保规划路径是最优的，甚至可能无法保证找到完整的路径^[3]。

全局路径规划，则是在工作环境信息已知，例如工作环境中障碍物的具体位置、实际形状等，构建出完整的工作环境路径规划模型的情况下，规划出一条从起点到终点的最优路径。因此全局路径规划是一种事前规划，在工作环境信息精准掌握的前提下，可以找到最优解。但是当移动机器人工作环境发生变化，例如较为常见的出现新的障碍物的情况下，全局路径规划就无能为力了。

全局路径规划和局部路径规划主要差异在于对于工作环境信息的掌握程度，即局部路径规划的工作环境较全局路径规划而言是动态的，并且更为复杂，并没有实质上的差异。由于移动机器人工作环境建模程度上的差异，因此适用于局部路径规划的路径规划算法都可以适用于全局路径规划。同时许多适用于全局路径规划的算法经过改进也可以适用于局部路径规划。在实际生产生活应用中，两者结合，可以更好的进行移动机器人路径规划。

经过多年的研究和发展，移动机器人路径规划取得了许多让人可喜的进展，但是目前的机器人路径规划方案中还存在着一些不足之处：全局规划中效率不高，局部规划中动态规避障碍的实时性较差。

1.2 国外研究现状

美国是世界上第一个移动机器人的诞生地，在上个世纪60年代中期至70年代初期，斯坦福研究院(SRI)的Charles Rosen以及Nils Nilssen 等人为了研究人工智能研发出了取名为Shakey^[4]的自主移动机器人。Shakey首次全面应用了人工智能技术，装备有摄像机，传感器，伺服电机以及驱动电机等设备，能够自主进行导航、感知以及建模。移动机器人的研究从这里开始展开。

与实验室环境不同，在实际环境中，地面往往不平整，移动机器人的移动经常遇到问题。为了解决相应问题，关于步行移动机器人相关的研究也逐渐开始展开，并且逐渐取得了进展和突破，被命名为General Electric Quadruped^[5]的步行机器人是其中最为有名的。

除此之外，为了研究移动机器人在月球以及火星等星球的不平等的表面进行探索的可行性，美国NASA资助研究了被命名为“丹蒂”的八足行走机器人，并且与1994年在火山口成功进行理论演示，在移动机器人领域取得了让研究人员骄傲的成果。

2004年1月3日，美国宇航局发射的“勇气号”火星探测车在火星南半球成功着陆。

2011年11月，美国宇航局成功发射了“好奇号”火星探测车，并于2012年8月成功登陆火星表面。

20世纪70年代后期，日本经济发展迅速，随之而来的就是日本的劳动力不足的问题愈加明显。因此移动机器人被日本国内众多企业视作解决劳动力不足的有效途径，在日本国内得到快速发展。经过四十年的发展，日本国内移动机器人的数量位居世界第一。

西欧国家的经济发展面临着和日本一样的问题：劳动力不足，同时西欧国家经济和科技发展迅速，科技底蕴深厚，因此西欧国家成为了移动机器人发展的沃土。此外部分国家立法规定，对于一些高风险的工作，必须以机器人代替人工进行，这为移动机器人的发展开拓了广阔的应用前景，促进了移动机器人的发展。

伴随着移动机器人相关领域研究的不断深入，世界各国的科学家和学者针对移动机器人的路径规划做了大量的研究，提出了多种路径规划算法，其中较为有名的有：遗传算法，蚁群算法，模糊控制算法，神经网络算法等。

蚁群算法是在1991年由意大利学者M .Dorigo等人首先提出，它通过模拟蚂蚁社会分工与协作寻食^[6]的原理进行寻优。在觅食的过程中，每只蚂蚁都会在走过的道路上留下一定浓度的信息素，但是信息素的浓度在不同的地方实际上是并不相同的。每只蚂蚁释放出最多的信息素是在刚找到食物或者巢穴的时候，但是随着蚂蚁走的距离逐渐变远，它所留下的信息素只会逐渐变少。在相同时间内，蚂蚁在最短路径上遍历的次数最多，因此最短路径上信息素浓度高。其他的蚂蚁经过附近在选择路径时会以信息素浓度为依据，起到正反馈作用^[7]，因此信息素浓度高的最短路径很快就会被发现，进而其他蚂蚁根据信息素的指引可以很快找到食物。蚁群算法具有良好的全局优化性能，在移动机器人路径规划中表现良好，但是蚁群算法也有收敛速度慢，容易陷入局部最优的缺点。

遗传算法（Genetic Algorithm, GA）借鉴了孟德尔的遗传学说以及达尔文的生物进化论和自然选择学说，是模仿自然界生物进化机制，按照基因遗传原理而实现的一种迭代过程的随机全局搜索和优化算法，由美国Michigan大学的J.Holland教授于1975年首先提出。遗传算法的核心内容是初始群体的设定、控制参数设定、参数编码、遗传操作设计、适应度函数的设计等五个要素，是一种以某个群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效的随机搜索，并且广为应用的优化算法^[8]。遗传算法的优点之一在于直接对结构对象进行操作，在对于模型的表达式上没有什么特定的要求，例如适应度函数不受连续性、可微性等函数解析性质的限制，它的定义域也可以随意设置^[9]。同时遗传算法除了具有自组织、自适应和自学习性以及内在的隐并行性和更好的全局寻优能力之外，还具有操作简单以及稳健性等优点^[10] 。因此遗传算法应用广泛，例如寻路问题、找圆心问题、人工生命模拟等。除此之外遗传算法具有强大的学习能力，因此将其他算法与遗传算法进行结合成为了移动机器人路径规划领域的一个研究热点。

模糊逻辑算法参考了驾驶人的驾驶经验^[11]，根据传感器采集得到的精确的实时传感信息，通过参考模糊规则表得到规划信息来实现局部路径规划^[12]。模糊逻辑算法实时性较好，易做到边规划边跟踪，在势场法中容易出现的局部极小问题在模糊逻辑算法中也得到了解决，适合处理未知异变环境下的路径规划问题^[13]。

所谓神经网络算法，即模拟动物神经网络行为，进行分布式并行信息处理^[14]，在空间感知的基础上做出相应的空间行为。神经网络算法在移动机器人路径规划中的应用并不成功，但是具有良好的学习能力，因此经常与其他路径规划算法相结合来进行路径规划，例如将神经网络与模糊控制相结合可以实现移动机器人的局部路径规划。

欧美等西方发达国家和日本的经济和科技发展水平较高，在移动机器人领域的研究起步时间较早。经过半个世纪的进步和发展，随着经济发展和人们生产生活的需要，对于移动机器人不断提出新的要求，使得研发人员在这一领域积累了丰富的科研经验，建立了完整的移动机器人研究科学体系和应用需求市场。无论是软硬件结合，自主导航等性能方面，还是外观结构，实际应用等实用性方面，都走在了世界前沿。

1.3 国内研究现状

上个世纪八十年代中期，我国的移动机器人研究受到了当时国际上移动机器人研究热潮的影响，逐渐开始兴起。和国外相比，作为发展中国家，在经济和科学技术等方面不如日本、欧美等发达国家，国内在移动机器人的研究与其他国家相比而言起步较晚，与发达国家相比，国内大多数研究尚处于某个单项研究阶段^[15]，例如：

1994年，清华大学通过对于智能移动机器人的鉴定，其中涉及了基于传感器信息的局部路径规划技术研究，基于路径规划的仿真技术研究，信息融合技术和传感技术方面的研究，基于地图的全局路径规划技术研究以及智能移动机器人的设计和实现等五种关键技术。

2002年，戴晓明等研究人员为了解决遗传算法容易收敛到局部最优值的问题，应用了多种群遗传并行进化的思想。

2004年，赵宏立等研究人员提出了一种应用基因块编码的并行遗传算法来解决简单遗传算法在较大规模组合优化问题上搜索效率较低的问题。

虽然起步时间落后于欧美等发达国家，相关领域的研究时间较短，然而经过三十年的发展，在移动机器人研究领域，我国已经实现了后来居上，缩小了与欧美和日本等发达国家的差距。不仅建立了具有自主创新能力和自主研发能力的研发基地，而且取得了让世界震惊的成就，在国际移动机器人领域拥有一席之地。

2013年12月，中国第一个月球着陆器嫦娥三号发射成功。2013年12月15日，“玉兔号”月球巡视车成功在月球表面实现了软着陆，中国成为世界上第三个成功研发月球无人探测车的国家。

2014年，我国代替美国成为亚洲地区无人机出口第一大国，我国的无人机技术已经达到世界先进水平。

近十年来，伴随着人工智能热潮的兴起，移动机器人领域发展迅速，许多难题与壁垒纷纷被攻破。我国作为世界上最大的发展中国家，市场广阔，相关移动机器人领域的技术也会随着经济全球化进入我国。既会给我国移动机器人领域的发展带来新的挑战，但同时也会带来新的机遇，可以让我们看到移动机器人领域在世界科技前沿最新的发展。

我国应该在移动机器人领域向欧美、日本等发达国家学习，借鉴他们在该领域的发展经验，结合我国移动机器人应用的实际现状以迎合应用需要，同时要不断进行创新，真正将核心技术掌握在自己手里。

第二章 路径规划D*算法

2.1 A*算法

2.1.1 A*算法简介

A*算法是静态路网中求解最短路径最有效^[16]的路径规划算法，通过维护一个优先队列（OpenList）来对场景中的路径节点进行搜索。与其他采用直接搜索方式的算法不同的是，A*算法采用的是启发式的搜索方法。在搜索的过程中，A*算法并非是找到所有从起始点到目标点的路径，不做任何路径的处理，而是会选择最优最短的路径，从而尽可能地缩小了搜索的范围，进而就提高了路径规划的效率。

和BFS算法一样，A*算法能用启发式函数引导自己，从而提高搜索速度。与Dijkstra算法一样，A*算法能够用于搜索最短路径。从启发函数的角度来看，A*算法就是把常规方法如Dijsktra算法（计算从起始点到当前节点的代价）和启发式方法（heuristic approaches）如BFS算法（计算从当前节点到目标点的代价）结合在一起的算法^[17]。

2.1.2 A*算法代价函数

A*算法是一种典型的启发式搜索算法，如何评价节点的重要性从而确定要检查的下一个节点是A*算法搜索过程的一个重要环节。代价函数的一般形式可以表示为f(n) = g(n) h(n)，其用于对于节点进行过滤从而缩小搜索范围^[18]。其中用前者函数g(n)表示从起始点到当前节点n已经付出的实际代价，而从当前节点n到目标点估计的最小的代价^[19]则表示为函数h(n)。h(n)也被称为启发式函数，它体现了问题的启发式信息，可以控制A*算法的行为，其形式要根据问题的特性确定^[20]。

用函数d(n)表示从节点n到目标点的实际代价

（1）在h(n)为0的极端情况下，即只考虑从初始节点到节点n的实际代价，忽略从当前节点到目标点的实际代价。这种情况下，代价函数中只有函数2g(n)发挥作用，A*算法演变成Dijkstra算法，可以确保找到最短路径，但是运行速度会受到影响变的很慢。

（2）若h(n)lt;d(n)，这种情况下，h(n)越小，A*算法扩展的节点越多，运行速度越慢，但是可以确保找到一条最短路径

以上是毕业论文大纲或资料介绍，该课题完整毕业论文、开题报告、任务书、程序设计、图纸设计等资料请添加微信获取，微信号：bysjorg。

相关图片展示：