【《移动机器人路径规划算法研究》18000字（论文）】

移动机器人路径规划算法研究目录TOC\o"1-3"\h\u2247移动机器人路径规划算法研究 131711第一章绪论 2171451.1研究背景及意义 3295681.2移动机器人概况 417811.2.1机器人起源与发展 4210641.2.2国内机器人研究现状 659961.3路径规划研究方法 7271551.3.1栅格法 714321.3.2环境地图法 8193441.3.3智能算法 8305291.4本论文主要研究内容及章节安排 1026069第四章为总结展望。 10178732.1路径规划问题 11247452.1.1路径规划特点和研究方向 11260922.1.2移动机器人路径规划基本步骤 115572.2路径规划问题数学模型建立 12248293.1.１BFS算法 15170953.1.２Dijkstra算法 1861183.2针对传统A*算法的改进研究 2224353.2.1传统A＊算法 2236983.2.2蚁群算法 25198603.2.3基于蚁群算法的改进A*算法 26287993.3本章小结 28320554.1传统A*算法仿真实验 2929527４.1.１实验结果分析 3015474.2.１对A＊算法进行改进以及优化实验 3120711４.2.2实验结果对比分析 37219４.３本章小结 3913075５.1论文总结 3915134５.2研究展望 40第一章绪论摘要随着当今社会的现代化、工业化以及自动化建设的快速发展，机器人的研究领域已涉及到人类日常生活中的方方面面。工业方面，由于工厂环境较为简单，地图构建和路径规划容易实现，机器人已经代替人工进行重复而繁重的工作。为实现机器人的智能化标准，并实现以最大化无障碍碰撞路径，研国内外研究人员研究出了适用于不同场合的路径规划算法，规划算法的性能与环境的复杂程度有关。其中A*算法是一种广泛使用的路径规划算法，它是一种基于启发式的路径规划算法。通过计算每个节点的启发函数值，在相邻节点中选择启发函数值最小的节点作为子节点，从起始点向目标点搜索优化路径。A*算法存在的问题是计算时间长、占用存储空间大，传统A*算法获取的路径往往有路径较长、转角过大、路面不能平滑等缺点。所以，单独用传统A*算法在路径规划时得到的路径并非最优路径。为克服这些缺点，本文将针对A*算法存在的缺点进行改进优化，获得新的改进A*算法进行全局路径规划。本文主要工作在如下几个方面：首先，第一部分主要介绍机器人研究的发展趋势、移动机器人的定义和来源，主要考察日本及国外移动机器人路径规划的研究现状及其研究意义和重要性。路线规划相关技术及常用路线规划方法在第2部分进行了分析，如各种常用的全局路线规划方法的原理、优缺点等。最后得出A*算法，比较并合适选择的。第三部分分析了传统A*算法在全局路径规划中存在的路径过长、旋转角度过大、路径不够平滑等缺点。使用蚁群算法。优化改进，并通过对比和仿真验证改进A*算法的优点关键词：移动机器人；地图构建；A*算法；蚁群算法；路径规划；研究背景及意义移动机器人代表了机电一体化的最佳成果，包括机械、自动控制等多种学科。机器人研究刚刚起步时，受传感器技术和计算机技术发展的制约，发展相对缓慢，但从21世纪开始，随着传感器和计算机科学的发展和不断进步，机器人研究逐渐进入了高速发展期。机器人的出现，帮助人们从一些危险中解脱出来。比如机器人在国防、工农业生产、应急救援、救灾等领域具有先天优势，可以代替士兵去完成一些危及士兵生命的任务，以减少士兵伤亡。一些国家早期对机器人研究的兴趣主要集中在军事方面的用途，用机器人可以代替人类进行探索、采集数据等工作，协助人类更好的探索未知空间，尤其是在太空、水下等人类无法到达的领域，如美国的“机遇号”和“勇气号”在火星上，至今已工作了十多年，并向科研人员反馈了许多有价值的信息。由于人类生活水平的提高和劳动力成本的上升，人类希望机器人能够为自身服务，因此，情节、购物、送餐、物流机器人等各种服务型机器人应运而生，这些机器人能够代替人类做一些简单的工作。如今，机器人也逐渐集成了神经网络、语音技术、大数据等技术，变得越来越智能，新型机器人可以跟小朋友讲故事，辅导小朋友做作业等等。总而言之，人类在生活中对机器人的应用越来越广泛。无论是哪种类型的机器人，人类最大的期望就是机器人能够实现自主性，无论有无人类指令，都能完成多项工作。著名机器人学专家杜兰特-怀特提出机器人研究主要内容包括三个问题：“我在哪儿？”、“我要去哪儿？”、“我怎么去那儿？”，这其中，第一是机器人定位技术，第二是路线规划与决策技术，第三是如何控制机器人到达目标点，即导航技术。而路径规划便是机器人人工智能化的最基础指标。为了实现路径规划，机器人需要具备环境搜索功能，随着机器人的工作环境从结构空间扩展到复杂环境，从室内环境扩展到室外环境，需要处理大量的数据，因此提高路径规划算法效率十分重要。移动机器人概况1.2.1机器人起源与发展1920年，小说《罗森的通用机器人》出版于世，随此，出现了一个让人们陌生的名词—“机器人”Robota（捷克文）小说里描述道“机器人”可以不分昼夜的持续工作，并完全按照人的指示，结合波兰文Robotnik（工人之意）创造出了Robot。Robot的字面含义是：具有类似类人或者生物智能的自动化机器，例如，有感知环境的能力、任务规划的能力、移动能力和协同作用能力，具有较高的灵活性，能够半自主或全自主工作。1960年以来，科学家们一直致力于机器人技术的研究，一些发达国家如：英国、美国、日本、韩国等率先将工业机器人引入工厂，用机器人代替工人完成高度重复的任务。随着科技发达，生产现代化水平也不断提高，种类繁多的机器人走进人们的日常生活中并对人们的生活行为和思想方式产生了重大的影响，如服务机器人、工业机器人、特种机器人等等。其中，值得注意的是移动机器人，它是包含了感知，规划，控制，执行机构等环节的综合系统。它是机械技术的一个重要领域。它代表了集机械、电子、计算机、自动控制、人工智能于一体的最佳成果。机器人发展可分为三个阶段：存在于大量工厂车间的工业机器人阶段、具有一定灵活自主能力的离线编程机器人阶段、可以在日常生活中与人交互的智能机器人阶段。1959年，世界上第一台自动化的工业机器人美国人英格伯格和德沃尔共同制造出，并宣告机器人从科学幻想变成了现实。由此，他们分别被誉为是“工业机器人之父”和“美国发明家名人堂”，二者共同奠定了未来机器人发展的基础。最初，机器人只能根据预先编写的程序重复作一系列动作，没有传感器，无法接受外界信息，无法感知环境也无法随着环境的变化作出相应的应激反映。第二代机器人是配备特定传感器，具有特定传感能力和适应性的机器人。这种机器人能够随着环境信息、估计自身位姿的变化而改变工作内容。第三代机器人是一种能够集成触觉等多传感器信息的智能机器人。如能够感知触摸的触觉传感器系统、感知压力变化的压力传感器系统、感知可见光的视觉传感器系统、敏感速度大小的速度传感器系统、敏感加速度大小的加速度传感器系统、敏感角速度大小的陀螺仪系统等。机器人具有较高的适应环境的能力，具有一定自主性的学习能力。1968年，移动式机器人—Shakey（如图1.1所示）由美国斯坦福研究所的研制小组成功开发研制，它可以感知环境、模拟环境、规划动作、执行任务、响应变化，它可以随着环境变化对压力作出反应。然而控制其运行的计算机的大小大约有一间房子那么大，故其实际运行速率非常缓慢。图1.1Shaky机器人随着传感器和计算机技术的发展，移动机器人发展迅速。根据机器人的各种运动方式，可分为类似车辆的轮式机器人、类似坦克的履带式机器人、类似人类的腿式机器人和类型鱼类的水下推进机器人。移动机器人的应用涉及到非常广泛的领域，如军事、工农业生产、民用等，引起了各国家的密切关注。20世纪80年代，美国国防高级研究计划局（DARPA）相关小组制定了有关地面无人作战平台的战略计划；同时，日本启动了欧洲尤里卡机器人计划，该计划旨在解决机器人在一个在极端环境中运行的问题。这些计划的实施促进了机器人研究和加速了机器人的发展。美国、日本以及欧洲国家在尖端技术方面也取得到了长足的进步，并确保了这些国家在世界格局状态下的政治地位。90年代，机器人集成了先进的感知系统、信息处理技术和规划系统，以提高其适应性。例如，德国成功研制了一款轮椅机器人，并对该机器人的适应性在一个火车站进行了测试，测试火车站具有极其复杂的客流环境；在1998年，该款机器人在汉诺威工业贸易博览会的一个展厅中现场表演了它的各项功能。以上实验证明了其对环境的高度适应性。丹麦乐高（Lego）机器人20世纪出现了大量的机器人公司，机器人开始正式进入各个行业领域。机器人市场正在一前所未有的速度发展，其中最为广泛使用的是仓储和物流机器人（AGV），而诸如招待机器人、清洁机器人、康复机器人、伤残机器人和娱乐机器人等服务则已出现在人们视野和生活中。比如双足机器人Atlas如图1.2所示-被认为是世界上最具活力的人形机器人、最有可能取代人类。因为软银旗下波士顿动力公司将其设计得十分灵活，Atlas可以做出跳跃旋转、后空翻等复杂的动作，从而有效改变了人们对机器人笨重、缓慢的固有印象。丹麦乐高（Lego）机器人公司生创造出了机器人套件，这一套件使机器人的制造变得更容易和更有趣，同时也推广了机器人教育，并把机器人概念传达给了青少年。图1.2Atlas机器人1.2.2国内机器人研究现状我国机器人研究起步较晚，从最初的引进国外机器人平台到后来的自主研发，目前已取得了显著的进步，特别是国家“863”计划设立智能机器人项目以来，许多高校研究机构都在开展智能机器人的研发工作，并取得了相应的成就。清华大学研制的智能机器人THMR—III在1994年通过了考核，移动机器人在全局地图信息已知的情况下实现了全局路径规划，这些研究是在一个结构化的环境中进行的；在全局地图信息未知的情况下，完成了多种传感器融合技术和全局以及局部路径规划得实现，包括GPS定位系统、电磁罗盘、超声波测距仪、视觉传感器等传感器信号融合技术，完成智能机器人THMR-III的设计与实现。中国科学技术大学研发的可佳机器人以及由哈尔滨工业大学研发的第一代智能导游机器人—DY-I型引导服务机器人具有里程碑意义。华南理工大学、北京航空航天大学等高校也展开了对移动机器人各方面功能的广泛研究，在路径规划及仿真、传感器信息融合技术等方面都取得了长足的发展。近年来，随着科技快速发展，大量的研究者们将更多的研究工作投入到了自动驾驶领域的发展，现在大部分车企都在开发自己的自动驾驶汽车，并趋于接近于实用化。自动驾驶汽车作为轮式移动机器人的一种典型类型，集成了人工智能技术、机器视觉系统、雷达探测系统、激光测距系统以及GPS定位等技术，随着科学技术和相关法律法规的发展和完善，自动驾驶技术将会显著地改变人类对汽车的认识，提高并改善人类的生活水平和环境。1.3路径规划研究方法目前为止，在路径规划领域已有多种路径规划算法提出，对于移动机器人面对的任务环境，根据环境的复杂程度可以选用不同的路径规划方法，对于简单的环境可以只用一种路径规划方法解决问题，对于复杂的任务环境，需要组合多种方法，结合每种方法的优势，才能很好的解决问题。常用的路径规划方法，包括以下几类方法：栅格法地图法、实时环境地图法、智能路径规划算法等。1.3.1栅格法栅格法(grid)是对环境地图进行离散化建模的一种方法。就是将障碍物模拟成小方格的集合，相当于将场景中的所有事物进行二值化替代，障碍物为1，非障碍物为0。栅格法是环境地图建模的一种常用方法，其实质上是将机器人的工作环境离散化为大小相同的单元，也就是将移动机器人所在的规划空间按照给定的标准分解成独立的单元格。每个栅格相互连接，但不重叠。栅格大小的选取影响了环境精细化表达的程度，它是影响规划算法精度以及时间效率的一个非常重要的因素，规划精度和计算量与划分精度成反比。栅格化后，每个栅格会有一个通过因子，这个因子可以将问题简化，因此，路径规划问题在栅格地图环境下变成了寻找节点之间最短路径的问题，栅格由其是否包含障碍物分为自由栅格和障碍栅格，没有包含障碍物的栅格为自由栅格，包含障碍物的栅格为障碍栅格。一般情况下，栅格法作为一种地图的构建方式，不会单独作为一种算法来解决路径规划问题，一般将栅格构图法与其他路径规划算法结合使用，以达到预期的效果。表2.1显示了如何识别栅格。表2.1栅格标识方法栅格标识方法具体实现序号法从左上角的第一个栅格开始，按左-右、上-下的顺序显示。每个栅格对应一个唯一的标签n。也就是说，所有栅格都可以显示为它们自己独有的标签。直角坐标法栅格图的横纵方向分别为直角坐标系x轴和y轴，交点为坐标原点，右上方为x轴和y轴正方向，每一个栅格块的边长设为直角坐标系坐标轴的一个单位长度，这样任意栅格都有唯一坐标(x,y)表示图2.130*30栅格环境地图一旦确定了栅格标识，移动机器人就可以根据坐标号和栅格节点的序列号开始搜索路径。这种方法常常用于近乎长方形的室内地图模型中。栅格法将在本文后续路径仿真算法中采用，即建立30*30的栅格环境地图，如图2.1所示。1.3.2环境地图法在移动机器人路径规划的研究过程中，环境图法可以说是最为普遍的，经常被用于研究和分析，涵盖了方面极为广泛。通常，此类建模分析方法用于SLAM研究、土木工程建设、智能移动机器人定位和建筑工程等。移动机器人在导航研究中主要通过集成可感知环境信息得多种类型的传感器、具备一定计算功能的计算机处理器、结合各种数据处理算法进行信息采集。因此，对感知到的各种环境信息进行有效处理，选择环境地图的建模方法是非常有效且直接的。SLAM可以同时进行定位和环境构建，通过从传感器获取周围环境信息，通过计算处理，便可以准确得到当时的位置，也就是定位。在考察路线规划时，需要得到一个能够准确描述环境空间位置和属性的地图模型，即机器人工作环境地图。而环境地图的设置精度会直接影响到移动机器人定位的精度，因为在导航和规划路径过程中，移动机器人在环境中获取的信息或直接反映在环境地图中。也因为定位是移动机器人导航和路径规划的基础，因此，建立准确的环境地图尤为重要。1.3.3智能算法所谓“智能算法”，是在工程实践中普遍存在的一种“新”算法或理论。通常是指基于有机体的某些行为特性或某些自然过程。这些算法一般在工程学中的实践中使用居多，会有效解决许多复杂问题。有遗传算法（GeneticAlgorithm，GA）、蚁群优化算法(AntcolonyOptimzation,ACO)、粒子群算法(ParticleSwarmoptimization,PSO)、神经系统算法等，都属于智能算法。智能优化算法通常用于解决诸如局部优化之类的问题。蚁群算法：蚁群优化算法本质上是一种概率算法，常用来寻找优化路径的。最早由Dorigo、Maniezzo于1992年在他的博士论文中提出.文中提出蚁群算法的灵感来源于他在观测蚂蚁寻找食物的过程中，发现蚂蚁会自觉地发现觅食路径的行为。经过对蚂蚁觅食过程的研究表明，虽然通过观察一只蚂蚁我们无法查寻到其觅食的规律，但通过观察一群蚂蚁，我们可以概率性地得出蚁群觅食过程中路径规划的方法。通过观察蚁群觅食，得知蚂蚁在觅食的路径上会留下一定的信息素，随着通过的蚂蚁数量增加，随之留下的信息素的浓度也越高。这样一来，剩下的蚂蚁也会跟着信息素浓度高的路径往前走，直到找到食物。因此，环境和信息素在蚁群觅食过程中起着决定性的作用。而整个蚂蚁在觅食过程中留下的信息素类似于正反馈机制。通向食物的最短最优路径上往往留下的信息素最多。通过对这一现象的深入研究与分析，Drigo，Maniezzo等人提出了目前广为人知的蚁群算法。目前，蚁群算法经过大量学者的不断深究，得到了完善和改进，并成功应用于移动机器人路径规划。虽然蚁群算法在路径规划方面具有一定的优势，但也存在一些缺陷。蚂蚁简单如一的行为让其富有智能化多样性和正反馈。因为这种正反馈机制，使得移动机器人在规划路线时具有非常快的收敛速度、以及非常高的并行性和较强的对环境变化动态适应的鲁棒性。然而，正反馈机制是蚁群算法的主要优点的同时，也是它的主要缺点来源。虽然蚂蚁群觅食过程中，信息素浓度最高的路径肯定通往目标地点，但并不能确定这一路径就是最优路径。因为信息素浓度会随着时间的推移，慢慢减少，故最优路径可能会是其他路径。作为一种智能算法，它具有智能优化的效果，可以利用蚁群算法的迭代优化效果对其他路线规划算法进行改进和优化。本课题就是对传统A*算法的缺点进行迭代优化，兼顾蚁群算法的智能优化能力。此处不再赘述，将在第3章进行详细研究。遗传算法：遗传算法主要对达尔文提出的遗传进化过程进行了计算模拟，于20世纪70年代由美国的Johnholland提出。遗传算法着重模拟了生物在进化过程中的自然选择现象和遗传机理因素，是一种描述生物进化过程的计算模型。遗传算法在路径规划中使用的表达式并非完整形状，这会导致编码过程中出现较多无效路径。因此，遗传算法面临搜索效率低，最后搜索得到的路径不能有保障是最优路径。很多研究学者对这个缺点进行了研究，提出并通过引入自适应功能等改进措施对其进行改进。粒子群算法：粒子群算法,或者叫做粒子群优化，是通过观测鸟类觅食的行为而提出的一种仿生智能随机搜索算法，借鉴了鸟类群体协作的特性。粒子群优化算法最开始由J.Kennedy博士和R.C.Eberhart博士于1995年首先提出。PSO算法是一种并行算法，算法的初始化为一群随机粒子，通过反复迭代找到最优解。粒子群算法也可以理解为一种通过跟踪当前粒子群中具有最优值的粒子的状态以寻找全局范围内最优值状态的进化算法。这使得该算法所具有的很高的精度、易于编程实现以及求解过程收敛快等优点。因此，吸引了许多研究者和科研人员大量的时间和精力对粒子群算法进行更深入的研究和探索。但他们不仅在理论上进行了改进，同时也在探索将其应用到实际中。1.4本论文主要研究内容及章节安排A*算法由于其易用性已广泛应用于机器人路径规划问题的求解，A*算法常作为一种全局路径方法，适用于全局环境地图信息已知的全局路径规划问题。A*算法进行路径规划是建立在环境地图信息已知的基础上进行的，因此，第一步先要获取环境地图，然后再此地图上进行路径规划，因此本文主要分两部分：地图模型选取和路径规划，本文对这两部分分别进行了理论阐述和比较，路径规划部分对全局路径规划进行了阐述，最后对A*算法进行了改进，以提高规划效率：减少规划时间、缩短路径长度、对路径进行光滑处理。本文章节安排如下：第一部分主要介绍机器人研究的发展趋势、移动机器人的定义和来源，主要考察日本及国外移动机器人路径规划的研究现状及其研究意义和重要性。第二部分分析了路线规划相关技术及常用路线规划方法，如各种常用的全局路线规划方法的原理、优缺点等。最后得出A*算法，比较并合适选择的。第三部分分析了传统A*算法在全局路径规划中存在的路径过长、旋转角度过大、路径不够平滑等缺点。使用蚁群算法。优化改进，并通过对比和仿真验证改进A*算法的优点第四章为总结展望。路线规划问题是移动机器人研究领域的主要问题之一。所谓路线规划，就是在有障碍物的机器人工作环境中，规划一条从机器人起始状态到机器人目标状态的最优或次优路径，该路径要避开环境中存在的所有障碍物，并具备一定的最优性。移动机器人的路线规划方法按照规划方式可分为在全局地图中的全局最优路线规划方法和在部分地图中的局部实时路线规划，全局路线规划方法通常可以找到最优解，但需要提前准确地了解全局规划的环境信息，国内外学者有关于这个问题进行了大量的研究，并据此创造了许多方法。传统的路径规划算法包括A*算法、人工势场和可视图法等等。在本章中，将通过分析和比较各种路线规划算法选择合适的路线规划方法，并建立路径规划问题的基本模型，为接下来的工作奠定基础。2.1路径规划问题2.1.1路径规划特点和研究方向移动机器人路线规划技术的评价标准是路线长度和所需时间都做到尽可能的短。在建立的地图模型中，智能化移动机器人被要求具有自主规划路线，避开障碍物，同时能够完成给定的任务。随着人们对开发更高性能的移动机器人的要求越来越高，进而对移动机器人的路线规划精度要求也不断提高。但由于整个社会的科学技术水平和工业生产制造能力的发展受限，移动机器人的硬件在一段时间内无法得到显着提升，因此，需要研究、改进和优化路线规划算法，或者提高组合路线规划算法是一种提升精度的非常有效的手段。在环境地图中搜索最优路径的算法设计和研究是目前移动机器人全局路径规划研究的重点。如今，许多机器人研究领域的专家将路径规划算法作为他们研究的重点。这不仅包括各种传统算法，还包括生物技术开发的各种智能算法等。算法的探索和研究取得了非常大成功。不管哪种算法在解决一个特征问题上都有优势，也会有或多或少相应的缺点，而且每种算法的适用范围也不一样，所以在实际应用中考虑选择哪种算法是需要根据具体情况来进行选取的。此外，还有几种不同学科领域中常用的路径规划算法，这些算法是在不同时期被发现的，通过对这些算法基本原理的探索和考察，主要分为四大类，可以分为：传统算法和图形方法、智能仿生算法等等。在接下来的章节中，将主要介绍获取先验环境信息的全局路径规划。在第3章中重点探讨了对全局路径规划A*算法，并在此基础上进行了改进。2.1.2移动机器人路径规划基本步骤在环境地图中的移动机器人路径规划方法包括三个主要步骤：机器人工作环境建模、使用路径搜索算法搜索路径和结合机器人模型约束进行路径平滑。当然，对于离散区域的路线规划，可以省略路线平滑步骤。（1）环境建模。对于路线规划来说，这个过程是路线规划的一个重要环节，通过建立环境地图模型，在路线规划的过程中，有一些场景可以被计算机处理，在这个抽象的环境中模拟真实的环境。顺利进行移动机器人的路线规划。（2）路径搜索。环境地图模型建立后，模型中采用合适的路径规划算法进行路径搜索，得到对应约束函数的最优解，规划移动机器人到达目标位置的最佳路线。（3）路径平滑。在路线规划中，通常可以通过路线规划算法得到理论上的最优路线，但在现实中，移动机器人可能无法到达目标位置，也可能无法到达目标位置。理论计算的到的路径不一定是最优路径，可能会存在一些问题，如路径较长，旋转角度过大，线路不平滑等。这时候就需要使用特定的优化算法和数学方法进行优化。缩短路径，减小旋转角度，使路径更平滑，以适应实际需要。移动机器人路线规划技术是利用多种路线规划算法和各种传感器技术为移动机器人规划最佳路线。移动机器人可以根据规划的路线快速准确地到达目标位置。一般来说，评估路径规划可以基于以下几点：(1)如果起点和目标点之间存在最优路线，则需要相应的智能算法才能到达目标点。换句话说，能否实现最优路线的能力是由选择合适的算法决定的。..(2)所采用的路线规划算法应尽可能简单，以便根据外部环境实时调整路线，减少计算量，提高机器运行效率。(3)适当的地图环境信息，通过收集周围环境信息（通过激光雷达等传感器），根据收集到的信息进行路线规划和处理，避免出现各种情况，可以建立地图环境模型。(4)起点位置和终点位置的确定，两者之间有一条路线，即为最优路线。(5)获得最佳路径后，如果移动机器人要遵循该路径并到达指定位置，则必须满足相应的条件。这通常意味着避开中间的障碍物。2.2路径规划问题数学模型建立路径规划问题可表述为在一个给定地图中，规划出一条从起点到终点的最优路径，路径不与环境中的障碍物发生碰撞，并且满足机器人模型的相关约束，并具有一定的最优性，例如路径长度最短，能量最省等，如下图所示。图1.3机器人路径规划问题示意图在实际使用中，机器人一般具有其自身的约束条件，在规划路径时要满足这些约束条件，规划出满足机器人约束的路径。例如，旋翼无人机的运动学模型可如下表示： 式中，表示无人机的三维坐标，以及表示无人机的水平速度以及水平指令速度，为无人机速度指令响应的一阶惯性时间常数。旋翼无人机的约束可表示如下： 式中，第一项约束表示无人机的最大速度约束，第二项以及第三项约束表示无人机的最大加速度约束。在无人机路径规划问题中，规划的路径需要考虑以上约束条件。无人车是一种常见的机器人类型，其运动形式具有一定的曲率约束，因此，无人车模型常常建模为一个Dubins模型，如下所示： 式中，表示无人车的位置，表示无人车的前进方向，以及表示无人车的速度大小以及速度大小指令，和表示无人车的角速度以及角速度指令，和为无人车线速度以及角速度指令响应的一阶惯性时间常数。无人车的约束可表示为其线速度以及角速度大小约束： 因此，在无人车路径规划问题中，需要考虑无人车的线速度以及角速度大小约束。综合以上约束条件的路径规划问题可以表示为如下的最优问题： 式中，表示和环境地图，机器人模型，起点以及终点相关的目标函数，为在环境地图中的可行路径。通常，根据相应的任务需求设计对应的目标函数，而最优路径的获得需要设计相应的路径规划算法求解。因此，本文的重点是设计路径规划算法，在给定地图中求解最优路径。2.3本章小结在本章中，分析了移动机器人路径规划问题的特点和研究方向，描述了解决机器人路径规划问题的基本步骤。同时，通过对路径规划问题数学模型的建立，明确了路径规划问题中各部分的具体定义，清晰的表述了求解的问题，重点提出了需要求解的核心问题，即路径规划问题。对此，更具体的研究将在接下来的章节进行阐述。全局路径规划算法设计全局路径规划包括三个步骤：地图建模、根据算法在地图上选取相应的点以及创建基于点的路径。全局路径规划方法有很多，每种方法都有其自身的优缺点，其使用范围也不同。本章将主要介绍全局路径规划里的几种路径规划方法：BFS算法、Dijkstra算法、传统A＊算法以及蚁群算法。通过描述这几种的算法的原理，各自的优缺点和适用场景，比较得出适合后续文章中使用的路径规划算法。通过比较分析，可以得出传统A*算法的原理简单易懂、搜索路径时的速率较快、可实现性较强的特点。基于传统A*算法的这一系列优点，考虑用蚁群算法将A*算法进行迭代优化，克服传统A*算法路径长度过长、转角不平滑等缺点。以获得改进的优化A*算法，为后续仿真实验做准备。3.1基于传统A*算法的路径规划研究3.1.１BFS算法BFS算法,其英文全称是BreadthFirstSearch,又叫宽度优先搜索算法，也是A*算法的特殊形式，当g(n)为0时，BFS搜索算法进化为A*算法。BFS算法是最简洁的图搜索算法之一，因为其原理简单，计算量小。BFS算法属于一种盲从搜寻法，在搜寻目标位置时，它并不会考虑具有可能性的位置节点，而是展开整个地图彻底的检查每个节点并进行搜索，一直到最后找到目标位置才会中止搜罗。因此，BFS算法又拥有易于实现的特点。基于这些特点，以A*算法为例，很多以图为基础的算法都是基于BFS算法的基础上发展来的。Dijkstra算法和Prime算法具有相同的思想和原理，并且充分利用了图搜索方面的优良特性以及宽度优先搜素的思想。上文提及过，BFS算法属于盲目搜寻法，系统地检查所有的节点，搜寻结果。因此，该算法效率低下，因为它会漏掉可能存在的目标点的位置，它只是在搜索地图过程中停下来，直到找到目标。图3.1所示为BFS算法的流程图。图3.1BFS算法流程图为了更好的理解BFS算法的原理以及运行过程，通过一仿真案例展示BFS算法的执行过程，如下图所示：（a）仿真环境（b）已访问节点500个（c）已访问节点1000个（d）已访问节点1500个（d）已访问节点1582个（e）找到规划路径（红色所示）图3.2Dijkstra算法执行过程如上图所示，图3.2（a）所示为BFS算法仿真环境，蓝点为起点，绿点为终点，黑色区域表示障碍物，白色区域为可行区域。图3.2（b）所示为BFS算法访问节点数到达500个时已访问的节点，图3.2（c）所示为BFS算法访问节点数到达1000个时已访问的节点，图3.2（c）所示为BFS算法访问节点数到达1500个时已访问的节点,图3.2（d）所示为BFS算法访问节点数到达1582个时已访问的节点，此时，BFS算法已找到路径，如图3.2（e）所示。如上图BFS算法搜索过程可知，BFS算法在搜索路径时需要搜索大量的节点，因此将消耗大量的时间，故BFS算法不宜作为实际使用的路径规划方法。3.1.２Dijkstra算法迪杰斯特拉算法（Dijkstra）是由荷兰计算机科学家狄克斯特拉于1959年提出的，该算法的原理是从一个顶点到其余各顶点的是最短路径搜索法。这种算法的特点是，从起始开始，从内向外跟踪搜索，每次遍历到开始节点距离最近且未访问过的顶点的连接节点，直到扩展搜索到最终目标位置为止。图３.１为迪杰斯特拉算法流程图。图3.1Dijkstra算法流程图图3.２Dijkstra算法原理图表3.1Dijkstra算法原理注解迭代SUdist[2]dist[3]dist[4]dist[5]初始{1}/10maxint301001{1，2}21060301002{1，2，4}4105030903{1，2，4，3}3105030604{1，2，4，3，5}510503060Dijkstra算法实际上属于A*算法的一种特殊情况。本章小结将主要分析Dijkstra算法的原理和应用。图3.1为Dijkstra算法的原理图，表3.1为其注解。综合观察图3.1及表3.1：起始位置用数字1表示，S中储存的是已搜寻过的节点，其余所有未开始搜寻的节点用U来表示。从起始位置１到带搜寻节点U的最短路径长度储存在数组dist中做记录。S中存放由起始位置开始，具有能达到目标位置可能性的附近节点，然后将dist数组更新一遍，在其余节点中选取dist值最小的节点，在放入S中。一直循环，直到最后S包含了所有节点，此时，经过不断更新数组dist，就可以得到从起始点到剩余所有节点的最优路径的长度。所以，起点到终点的最优路径长度便可以根据dist数组来判断。在研究Dijkstra算法时，需要特别注意节点的选择，因为这是整个算法中最为关键也是难度最高的部分。节点的选择直接决定了路径规划得到的最短路径的精度。一般来说，选择的节点越多，划分得越细，寻找的路径就越有可能是最佳路径。反之，节点数越少，粒度越粗。在很多情况下，它可能不是最佳路径，但可能是次最佳路径。当然，也不能盲目选取过多节点，否则只会会增加计算量，提升算法的复杂度。Dijkstra算法执行过程可如下图所示：（a）已访问节点500个（b）已访问节点1000个（c）已访问节点1292个（d）找到规划路径（红色所示）图3.3Dijkstra算法执行过程如上图所示，图3.3（a）所示为Dijkstra算法访问节点数到达500个时已访问的节点，图3.3（b）所示为Dijkstra算法访问节点数到达1000个时已访问的节点，图3.3（c）所示为Dijkstra算法访问节点数到达1292个时已访问的节点，此时，Dijkstra算法已找到路径，如图3.3（d）所示。和BFS算法执行过程相比，可见Dijkstra算法在执行的过程中，访问的节点数降低，可以更快的找到路径，但任然存在路径搜索过程中访问大量节点的问题，故同样不宜实际使用。3.2针对传统A*算法的改进研究3.2.1传统A＊算法A*搜索算法，又称A星算法，是启发式搜索算法中的一种，算法满足下列公式：F(n)=g(n)+h(n)(3-1)(3-2)(3-3)在上式中：F(n)是每个可能节点的估值；g(n)表示从起始点到当前点的代价；h(n)表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值。h(n)直接影响着具有此种启发式函数的启发式算法是否为A*算法。A*算法首先要建立两个列表：OPEN表和CLOSE表，简称O列表和C列表，分别用来存储相关的节点信息。OPEN表保存所有已生成而未考察的节点，其余已访问过的节点记录在CLOSE表中。比较各节点函数值的大小，按照从大到小的次序将其进行排列，并将这些节点储存到OPEN表中。OPEN表中的初始节点放入CLOSE表中，最终的最优路径可通过连接这些节点得到。比较所有节点的估计评价函数，评估最终要生成的节点。直到最后OPEN表不再有存放的任何节点，就可以停止所有搜索过程，或者最终找到了所需点目标点，也停止搜索过程。图3.2A*算法原理流程图从起始位置开始，使用A*算法搜索附近的八条路径，具体方法如下：（1）使用栅格法创建栅格地图，为障碍物栅格和自由栅格赋值，标记栅格，并定义起始和目标位置；（2）创建一个OPEN表，储存当前栅格搜索路径时需要考虑的栅格，包括当前栅格和可能在它周围路径上的任意栅格；（3）创建一个CLOSE表，储存搜索路径时不需要重新考虑的栅格，包括障碍栅格和已经搜索过的栅格；（4）将其作为从起始位置开始需待处理的栅格，存入OPEN表中；（5）判断路径起点周围的可行性栅格，将障碍栅格存入CLOSE表中，将自由栅格存入OPEN表中。视当前栅格作邻近栅格的父节点；（6）删除OPEN表中的初始节点，存入CLOSE表中，如式(3-1)建立启发函数所示。A*算法具体原理流程图如图3.2所示。A*算法执行过程可如下图所示：（a）已访问节点500个（b）已访问节点746个（c）找到规划路径（红色所示）图3.3A*算法执行过程如上图所示，图3.3（a）所示为A*算法访问节点数到达500个时已访问的节点，图3.3（b）所示为A*算法访问节点数到达746个时已访问的节点，此时，A*算法已找到路径，如图3.3（c）所示。和BFS算法以及Dijkstra算法的执行过程相比，A*算法在执行的过程中，访问的节点数显著降低，可以更快的找到路径，因此，可以在实际应用中使用。故本文以A*算法为基础，研究机器人路径规划算法。虽然A*算法可以快速的找到路径，但是其规划出的路径有较大的转角，不满足无人机、无人车等机器人的运动约束，故下文利用蚁群优化算法对A*算法规划出的路径进行优化，以期减小路径转角以及路径长度。3.2.2蚁群算法蚁群优化算法是一种基于自然界生物行为的仿生智能算法。它具有迭代特性，常用于其他算法的路径规划和迭代优化。蚁群算法是一种启发式算法，其原理来源于蚂蚁在寻找食物的过程中用分泌的信息素标记路线，它们用此方法提醒其配偶沿途寻找食物。在信息素分泌以后，会随着时间推移而减弱，如果沿着这条通路走的蚂蚁越来越少，信息素浓度逐渐降低，直到最后，没有蚂蚁再经过，这条路线将会消失。相反，如果沿着这条路径的蚂蚁数量的增加和信息素浓度的增加，那么随之而来的蚂蚁也越来越多，最后形成一条觅食的最优路径。图3.7展示了蚁群算法模型。由于蚂蚁在寻找物体时经常成群结队地移动，因此蚂蚁的巢穴和食物之间有多条路线。不同的蚂蚁也会有不同的路径选择，通过选择不同的路径，蚂蚁可以沿着不同的线路到达食物，将这些不同的线路用集合表达，例如{}、{}。蚂蚁每次沿路行走时都会留下信息素。几个循环后，蚂蚁逐渐集中在最短的路径上。由于蚁群算法是根据信息素选择路径，因此需要为算法提供启发式信息。换句话说，我们首先需要确定可能的道路信息的基线集中度，这样蚂蚁便可以根据信息继续前进。初始信息浓度用C（C>0，常量）来表示。图3.7蚂蚁寻路模型假设有如下等式成立：(3-4)在随后的迭代中，蚂蚁群沿不同路径释放的信息素浓度会随着时间的推移而降低，从而导致信息素浓度不同。这种变化将导致不同的路径具有不同的权重，因此，以下蚂蚁在选择路径时将具有确定的基础。每只蚂蚁在经过路段时都会释放特定的信息素作为标记，计算信息素增量的公式如下：(3-5)＝(3-6)式中：Q为信息素的总量，为固定值；AntNum为蚂蚁种群数量；表示蚂蚁k(1，2，3，…AntNum)从i到j的这一过程释放的信息素量；—t周期循环后路段第ij节上增加的总信息素浓度。当蚁群优化算法在重复进行迭代时，路线上信息素会在不同的周期结束时刻挥发一次，，用式(3-7)所示，代表信息素蒸发系数，取0-1之间的值；为t周期的信息素量；为t+1的信息素量。蚂蚁算法的本质是在选择转移概率时模拟蚂蚁的行为。基于信息素值和启发式函数计算转移概率。一旦计算出转移概率，随后的蚂蚁就可以根据它选择一条路线。其中，启发式信息为,为i到j之间的长度，其主要功能是让蚂蚁根据自己的大小决定走哪条路线。转移概率公式如式(3-8)所示。(3-7)(3-8)3.2.3基于蚁群算法的改进A*算法用蚁群算法优化A*算法时，算法流程如图3.3所示，具体步骤如下：第１步：首先创建栅格地图（栅格法），进行初始化。确定坐标点位置，定义起点和终点。第２步：在经过处理的栅格环境地图中寻找中心坐标，作为路径搜索节点。第３步：采用A*算法初步搜索出一条移动机器人从起始位置到目标位置的初始路径；第４步：初始化蚁群相关参数；第５步：用蚁群算法搜索路径，根据式3-8，根据蚂蚁当前所处节点i确定下一位置j；（３-９）其中：代表蚂蚁会选择从节点i到节点j进行路径的概率，代表与距离相关的启发式系数，为（i,k）上的信息素，代表蚂蚁搜索路径时可以选择的下一个节点总合，i代表连接线上设定的一组子节点集合，q是为随机变量，是可调整参数，；第６步：更新经过的路径(i,j)上留存的信息素，并确定下一个节点ｊ；第７步：评估蚂蚁是否找到了目标位置，如果找到了，则进行下一步骤，否则转跳至第５步；第８步：比较分析所有路径，挑选出最短最优路径，并带入等式(3-10)以和（3-11）中，以更新全局信息素。（３－１０）（３－１１）在方程(3-10)和(3-11)中，代表进行全局路径更新时，沿路径(i,j)上的信息素增量。代表本次迭代中找到的最短路径长度；第９步：判断迭代优化是否完成。如果是，则停止程序，并输出最终结果；否则再次转到第５步继续循环。图3.3基于蚁群算法的改进A*算法流程3.3本章小结4.1传统A*算法仿真实验使用A*算法进行路径规划时，起始点为左方格，目标点为右方格，中心为障碍物，目标是在起点和终点之间规划出一条可行的路线。起点和它周围的g值、h值、F值如图４.１所示，每一格子中左侧上角是F值，左侧下角是g值，右侧下角是h值。图４.１起止位置以及邻域相关值如果相邻栅格已添加到C表中，则不再考虑；如果相邻栅格是障碍栅格，则也不再考虑；如果相邻栅格是一个可执行网格并且不在O列表中，则将其添加到O表中，并将当前节点作为次neighbour的父节点；如果neighbour在O表中，则需要比较对该邻接的基于当前和上一个的父节点F值的大小。若前者小，则继续进行搜罗；若后者小，则用使用上一个父节点的F值，再继续搜罗。由图４.２可知，在搜索结果中，起点右侧方栅格的Ｆ值最小，因此右侧的栅格被识别为新的父节点。在寻找新的父节点时，发现其下侧方栅格的F值大于基于上一个父节点的F值，所以更新父节点，并选择起始位置右侧下方栅格作为第二父节点进行搜索，图４.２中红色小圆形线即为搜索的路径。图４.２A*算法路径搜索结果实验与仿真：实验环境是一个三十乘三十的栅格网地图。每个栅格长三十五厘米，自由的白色栅格坐标(x,y)满足，的。可自由设置起点、终点、障碍物位置。在第一组实验中，起始点设置为(4,3)，目标位置点设置为(16,3)。如图3.5，障碍物以各种形状自由分布在栅格地图中；在第二组实验中，起始点设置为(4,3），目标位置点设置为(2１.５,20)，如图４.6，障碍物同样以各种形状自由分布在栅格地图中。图3.5A*算法仿真结果一图3.6A*算法仿真结果二４.1.１实验结果分析实验结果表明：在第１组实验中得出数据：A*算法搜索路径长度75.1342，耗时20.8s，总转折角度为989°；在第2组实验中得出数据：A*算法搜索路径长度48.0126，耗时15.1s，总转折角度为496°。虽然A*算法成功搜出了从起始位置到目标位置的无碰撞路径，但是路径较长，总转角度过大，路径不够平滑。这意味着在实际应用中机器人将消耗更多的能量和需要更长的时间才能到达目标位置。换句话说，规划的路线并非最优路线，而是次优路线。本文在传统A*算法的基础上，利用蚁群算法的迭代优化，弥补了A*算法的不足。４.2改进A*算法的优化实验4.2.１对A＊算法进行改进以及优化实验在使用蚁群优化算法对A*算法规划的初始路径进行迭代时，蚁群算法各化参数的物理意义为：InterNum表示迭代次数；AntNum表示种群数量；表示信息素挥发系数；表示启发式信息weights；表示信息素weights；p表示信息素选择thresholdvalue。使用蚁群算法迭代优化A*算法初始路径时，设置蚁群数量AntNum为十、信息素挥发系数在0.10~0.00030之间。迭代次数可调整，迭代次数从五十到一千次中选择，每增加五十来进行调整，然后进行实验。本文仅提及三组：分别为二百次，五百次和七百次，以演示实验。具体的参数见表４.2。表3.2蚁群算法迭代优化时参数设置InterNumAntNumP50－100010【0.1，0.0003】1020.8实验环境依然设置成三十乘三十栅格地图环境。实验分为２组，有不同的障碍物。每组起点与终点以及其他物体的分布与进行传统A*算法的仿真实验环境相同。模拟实验环境，在进行迭代时，只改变InterNum的数值，不改变蚁群算法中所有其他参数。第３组实验起点与前两组实验起点相同，只是在远离起点一定位置的地方，用障碍物将目标点围绕起来。这么做的目的是为了验证在算法可以在地图中无可到达路径的环境下，通过执行路径规划过程可以提前检测到没有可到达路线，并按照路线规划流程提前作出提醒，这样在进行实际应用的时候可以缩短因为没有合适的路线，路线规划不准确而花费的时间及精力。第一组实验：图第１组二百次迭代优化后规划路径图图第１组七百次迭代优化后规划路径图第二组实验：图3.11第二组200次迭代优化后规划路径图图第２组五百次迭代优化后规划路径图图第２组七百次迭代优化后规划路径图第三组实验：图3.14第３组优化后A*算法规划路径图上述３组实验中，实验模拟环境和障碍物的设置都是任意的。但由于限制，可供模拟的实验数量较少，只能选择三组实验，有一定的局部限定性，不能完全反映优化后的A*算法对多种环境包括一些复杂的环境的适用程度。而实际情况下移动机器人在路径规划中，经常会遇到各种不确定的复杂环境，因此本课题在环境优化前后进行随机A*算法路径规划对比的仿真实验。本次进行两组实验：第４组、第５组实验。由于障碍物环境是随机生成的，所以很难比较同一环境下的迭代次数，因为随机生成的障碍物环境每次都不一样。因此将迭代次数统一设置为InterNum=500参数，其他参数和进行任意环境下实验参数相同，不将其改变、如表3.2中所示，进行了两组实验。在同一个环境中会规划出由传统A*算法和利用蚁群算法对其迭代优化后的２条路径。第４组实验：图3.15第四组任意环境优化后A*算法规划路径图第５组实验：图3.16第五组任意环境优化后A*算法规划路径图４.2.2实验结果对比分析由图４.8、４.9、４.10所示，从第１组实验仿真结果来看，A*算法的初始路径重复二百、五百、七百次运行蚁群算法，然后最终得到的路径各项性能指标如表４.3所示；如图４.11、４.12、４.13所示，从第二组实验仿真结果来看，通过蚁群算法对A*算法初始路径分别进行的二百、五百、七百次迭代优化以后最终得到的路径各项性能指标如表３.4所示。在４.1节模拟了传统的A*算法路径设计，对传统A*算法路径规划进行了仿真实验，两组实验规划出来的路径性能为：长度75.1342，总转折角989°，时间20.8S；长度48.0126，总转折角496°，时间15.1S。表3.3第一组实验性能对比性能指标迭代次数0200500700路径长度75.134273.681571.995872.5634总转折角度（°）989805779761时间（S）20.824.327.732.1表3.4第二组实验性能对比性能指标迭代次数0200500700