摘 要

本文基于实际中无人船问题的需要，研究了无人船在水面行驶时如何做到更快，更安全。换句话说就是无人船在水面行驶时，如何规划一条避开障碍的最短路径。这就要提到本文的重点即算法上了。传统的路径规划算法有A*和迪杰斯特拉算法，这两者就是本文研究的重点。在实现这两个算法时，首先进行环境建模，将二维的环境模型栅格化，然后比对两个算法对同一环境下路径规划的不同，找到他们的缺点并改进

关键词：路径规划、A*算法、迪杰斯特拉算法

ABSTRACT

In this paper, based on the actual need of the unmanned ship problem, how to make the unmanned ship travel faster and safer on the water surface is studied. In other words, how to plan a shortest path to avoid obstacles when an unmanned ship is driving on the water surface? This will refer to the focus of this paper, that is,the algorithm. The traditional path planning algorithms are A* and Dijstro, which are the focus of this paper. In the implementation of these two algorithms, we first carry out environmental modeling, rasterize the two-dimensional environmental model, and then compare the differences between the two algorithms for path planning in the same environment, find out their shortcomings and improve them.

Key words:Path Planning,A*Algorithms,Dijkstra Algorithms

目 录

第一章绪论 1

1.1研究背景 1

1.2无人船国内外发展现状 1

1.2.1国内无人船发展现状 1

1.2.2国外无人船发展现状 2

1.3路径规划算法发展现状 4

1.4算法基础 5

1.4.1数据结构 5

1.4.2图论 5

1.5研究内容和结构 6

第二章A*路径规划算法 7

2.1A*路径规划算法介绍 7

2.2A*算法的一般步骤 7

2.3A*算法无人船应用仿真实验 10

2.3.1环境建模 10

2.3.2仿真结果和分析 12

第三章Djikstra算法 15

3.1Djikstra算法介绍 15

3.2Djikstra算法一般步骤 15

3.3Djikstra算法仿真实验 17

第四章A*和Djikstra算法改进 18

4.1对比分析A*和Djikstra算法 18

4.1.1基本原理对比 18

4.1.2实验结果对比 18

4.2扩大标准 A*算法节点搜索邻域 18

4.2.1优化思路和改进原理 18

4.2.2改进算法仿真和结果分析 22

4.3采用堆排序的Djikstra算法 23

4.3.1优化思路分析 23

4.3.2改进的Dijkstra算法 23

第五章总结 24

致谢 25

参考文献 26

第一章绪论

1.1研究背景

曾经,世界各地都有着幽灵船,鬼船的传说。现在,这些传说或许正在变成现实。无人船便是如同这些传说所描述的一般,无需人为操作就可以在水面行驶。而我所选择的课题是对无人船在湖面上航行的路径进行规划。首先，让我们做一个简单关于无人船的介绍。无人船是全自动水面机器人，有了精确的卫星定位和自我感知的帮助，可以根据预设的路线运行，而不需要人为的控制，英文缩写为USV。早在上世纪60年代，远程控制无人舰队被广泛的应用在军事领域。近年来，随着技术，如自动控制，物联网，大数据，环境感知技术及相关船舶通讯导航技术的快速发展也得到了广泛应用。无人船的出现，可以说是历史的必然。许多在水面上的危险工作促使着他们一直在进步。而无人船的发展自然离不开软件与硬件的研发。

我们需要有能支持无人船在水上行走的动力，同样的也需要为这些动力规划施展的方向。这次的研究就像是在为一个无人船注入灵魂，让它能在没有人操作的情况下能自动完成对路径的规划以及行驶。无人船的路径规划包括全局规划和局部规划两部分，这次我们主要研究的就是全局规划。在一个已知地形的区域内，无人船能完成对地形的感知并规划一个最短的路径同时避开所有已知的障碍。

1.2无人船国内外发展现状

纵观无人船的发展历史，自1898年尼古拉-特拉斯发明了无线机器人后，无人船首次在实战中的应用是在二战时期，被用作清除鱼雷和障碍物。[^[1]]这些早期的无人驾驶船基本上通过无线电完成向母舰的信号传输。如今，无人驾驶船舶已经在硬件和软件方面遇到了许多困难并不断的克服。它已经迎来了一个快速发展的时期。今天的无人船有更多的功能和更广泛的应用领域。而不同情况下,无人船的设计与路径的规划都不尽相同。

1.2.1国内无人船发展现状

2014年，”珠海造”无人船在国际创新论坛上惊艳亮相，至此开始国内智能无人船开始了高速的发展。2017年7月，中国船舶工业总公司，大连海事大学，中国船级社，交通运输部的水运科学研究院共同亮相"无人船技术与系统联合重点实验室"。国内企业，科研院所和高等教育机构携手合作，形成产学研结合，中国无人船发展进入快速发展阶段。无人船技术涉及的领域很多，在传感器方面，云洲技术团队研制出小型自动测绘无人机96中国船检中国船舶调查2018.5技术传感器。[^[2]]伴随着这些相关产业的发展，无人船的研究也在不断的进步。直至今日，无人船的发展仍然在不断向前。

图1.1 珠海造无人船

1.2.2国外无人船发展现状

美国研究无人驾驶船相对较早。在第二次世界大战期间，美国军方在无人水面舰艇（USV）上设置了枪支和导弹。在20世纪70年代，USV被广泛用于美国军方的反鱼雷战舰体系。在21世纪初，沿着海岸形成了一个强力

图1.2 60年代美国改装无人船

的USV舰队。美国PEO LMW开发了一种具有可重新配置，高速和长续航能力的半自动USV，配备了支持ARPA的雷达，固定摄像头，红外传感器，麦克风，深度计，温度和风速传感器。英国普利茅斯大学研究了一艘具有进步意义的无人船，其主要目的是跟踪污染物，测量河流，水库和沿海地区等浅水区的环境和信息。这艘无人船的发明和创造解决了无人船在控制时，能进行定位到无人船的定位系统精确度不足的问题，并且使用了当前最先进的算法，确保了在无人监管的情况下能自己独立的完成对河流信息的采集。自2002年以来，

图1.3“斯巴达人”无人船

美国海军水下作战中心联合公司一直在共同开发SPARTAN SCOUTUSV。它被认为是一个高科技示范项目，其目标是开发具有模块化，可重新配置，多任务，高速，半自动导航的USV。2016年，美国发射了最新的海上猎人无人反舰船，并开始测试世界上最大的无人舰。在非军事方面，位于弗吉尼亚州的UOV开发了一种具有无限长电池寿命的UUV，适用于于海洋数据采集和测量。Navigate开发了水动力的USV，Owl MKII，它在隐藏和配重能力方面有显着改进，以及侧扫声纳和摄像功能。

1.3路径规划算法发展现状

路径规划即研究如何生成一个合理的路径,如今路径规划可分为全局路径规划和局部路径规划。前者是从开始到一个完整的端到端的路径，是这段路径中局部规划的总和。而局部路径规划则是通过一些装置实时进行当前路段的规划。这两者的关系是可以相互转化的,例如局部算法可以看做很短一段路径内的全局规划,同理全局规划也是如此。现在全局规划的算法大致有：可视图法、概率路径图法、栅格法等；局部路径规划算法有：人工势场法、遗传算法以及模糊逻辑算法等。[^[3]]这些都是启发式算法，而启发式算法也是如今路径规划算法的主流，与路径规划相关的启发式算法有:粒子群优化算法、蚁群优化算法、萤火虫算法以及布谷鸟算法等。

1.4算法基础

1.4.1数据结构

算法的提出在于我们需要解决一个计算机问题时，我们需要将这个问题分解为几个方面来解决。首先我们要将这个抽象的现实问题具体为一个计算机可以接受的数学模型，然后我们用数学的方法解决这个模型的问题，最后得到一个可以解决这个模型所指代的现实的问题的算法，并用程序的方式将他实现。例如，求解梁架结构中应力的数学模型为线形方程组；预报人口增长情况的数学模型为微分方程。[^[4]]但是有许多问题单纯使用数字是建立不了数学模型的，这时候就有了图，二叉树等等数据结构，不再局限于一个或多个数学方程。

1.4.2图论

在一些普通的数据表现方式不足以表达出所需要的数据时，图的出现解决了很多这方面的问题。在一个图中，有顶点和边。其中顶点被用来储存数据，而边则代表了顶点的数据之间存在的关系。图之所以能表达出更多的数据的原因就在于图的关系可以是错综复杂的，也就是说，一个顶点的元素可以和很多个其他顶点都有关系。因为图的这个优势，现在图已经被应用的相当广泛。

有向图及无向图:一个图中的顶点都是我们需要的数据元素。两个顶点之间用线段链接，这个线段便是这两个顶点元素之间的关系。如果这个关系是单向的，两个元素只有一个关系，即一个元素指向了另一个元素，而另一元素却不能指向这个元素时，这个图就是有向图。如果这两个元素的关系是互通的，即不管谁作为起始的元素，都能找到一个关系指向另一个节点，那这个图就是无向图。

图1.4 有向图示例

1.5研究内容和结构

随着无人船技术和路径规划算法的不断进步，为无人船进行路径规划是必然需要的。本文主要研究无人船在湖面行驶时需要用到的全局规划算法，目标是在一定范围内能通过算法得到最优的路线。

论文结构分为以下几个部分：

第1章： 绪论简单介绍无人船和无人船路径规划

第2章： A*路径规划算法的介绍和在无人船路径规划上的应用仿真

第3章： 迪杰斯特拉算法的介绍和仿真

第4章： 对比A*算法和迪杰斯特拉算法，分析他们的优缺点并提出解决缺点的办法

第5章： 总结

第二章A*路径规划算法

A*路径规格算法属于启发式算法中的典型算法，且发展历史较长，对后来的许多算法都有留下属于他的影响，所以成为了本文第一个研究的对象。

2.1A*路径规划算法介绍

A*算法在1969年被提出，而且因为它运算效率远高于当时主流的D算法，所以得到了广泛的关注。学者们将它应用于路径规划当中，发现它的效率和结果完成度远高于其他算法，所以之后A算法便都被使用在了路径规划方面。在接下来的几十年，国内外许多学者都不断提高他的性能，并取得了不少成果。例如Koenig S[^[5]] 等提的LPA*(Long life Planning A*)算法在 A*算法的基础上融入了人工智能领域“增量搜索”(Elemental Search)思想。[^[6]]

A *算法是解决静态道路网络中最短路径的最有效的直接搜索方法。公式表示为f（n）= g（n） h（n），其中f（n）是从初始状态到状态n到目标状态的成本估算，g（n）是到达状态n所用的实际代价，h（n）是在选择不同路径时作为参考（对于路径搜索问题，状态是图中的节点，成本是距离）。最关键的地方就是选择估值函数f（n）。我们使用d（n）来表示从状态n到目标状态的距离，然后h（n）的选择大致如下：

如果h(n)lt; d(n)，这时就需要搜索更大的范围，花费更多的时间，但能得到最优解

如果h（N）= d（n），这时路径会按照最短路径完成规划，效率最高

如果 h(n)gt;d(n)，这时搜索范围小，搜索元素少，速度快但不一定是最优解

2.2A*算法的一般步骤

A*算法是借助两个独立的列表完成对路径的搜索的。在算法进行时，每搜索一个节点，算法就将这个节点进行分类放置。在所有节点完成搜索后应该得到一个放满的列表，这个列表中的元素按照放入的顺序输出就能得到A算法规划的最优路径

A算法运行流程：

第一步：设置开放列表和一个封闭列表中，起始节点S添加到开放列表，这时封闭列表是空的;

第二步：按照算法遍历开发列表中的所有待搜索节点直至所有待搜索节点遍历结束。如果不存在待搜索的节点则算法结束，输出显示没有可规划方案；

第三步：如果在上一步遍历到了待搜索节点，则计算所有待搜索节点到当前节点的距离代价，即f(n)值。取出其中最小的f(n)值对应的节点作为下一步搜索的节点m，并将他从开放列表中删除放入封闭列表中。

第四步:判断刚放入封闭列表的节点n是否是需要的节点，若不是,进行第五步;

第五步：重复以上步骤直至算法第四步时确定是需要的节点，计算f（m）并将值最小的节点作为下一步节点

第六步：确定节点m是否在开放列表和封闭列表中：（1）如果节点m不在开放列表和封闭列表中，则将节点m放入开放列表中，并基于它搜索节点。然后用一个指针将m节点和上一节点链接，m为起始。如果存在可行路径则根据指针一路找到起始节点，并更新最优路径; （2）节点m在开放列表中则比较f（m）和之前储存的节点的价值f（）的大小。如果f（m）比之前节点的价值小，则代表找到了更优的路径节点。之后使m放入封闭列表，并使指向空集。最后将m节点的父节点指向的下一节点。（3）节点m存在于闭合列表中，表示该节点已经在当前最优路径上，并返回上一步继续比较其他子节点；

第七步:循环以上步骤，直到第四步判断的节点为指定的终点，结束算法。

实验流程图：

图2.1 A*算法流程图

2.3A*算法无人船应用仿真实验

2.3.1环境建模

全局路径规划的环境建模环境建模是指将无人船的实际工作环境通过数学模型建立路径算法的计算机数据模型。[^[7]]路径规划中常用的环境建模方法有自由空间法[^[8]]和栅格法。[^[9]]

1．对输入信息预处理

在进行环境建模之前，我们需要将环境整个模拟到计算机当中，但是现实中的环境是一个抽象的概念，而计算机只能接受它可以识别的计算机语言。所以在进行环境建模之前，我们需要对环境进行处理，将这个抽象的信息转变为计算机可以识别的语言。

环境信息的预处理是指为了避免在无人船的实际移动期间无人船中的障碍物等的碰撞而执行的图像操作。首先设置无人船边界与障碍物边界之间的直线安全距离，记为Ds，Ds的取值根据无人船自身性能和实际工作需求确定。[^[10]] 无人船的长度和宽度分别为a和b，从质心位置到无人船体最远端的距离为D1，无人船体的尺寸为Sr = a×b 。

图2.2 环境模型

2．使用栅格法进行建模

使用栅格法生成环境建模时，有一个重要的指标就是单位栅格的大小即栅格颗粒大小。在选择栅格颗粒大小时我们需要考虑实际需要的环境建模精确到什么程度。栅格颗粒越小则，环境精度越大，能呈现的环境就越具体。反之则细节越粗糙。一般栅格颗粒生成步骤：

（1）首先，使用上述方法进行信息预处理，得到环境信息在计算机上表现出的模型。其中障碍物分布和因为无人船大小受限而不能通过的面积为，并统计环境中所有障碍物占的面积和非允许通过区域的面积。

（2）设为环境最大障碍物的长边长，表示环境最小障碍物的短边长， 表示环境建模模型最后生成的图的大小，颗粒的大小取决于障碍物在环境中所占的比例和最大障碍物的长边长，在某些情况下，同样可设定为基准，最后取这两个值中较大的那个作为基准，设为栅格颗粒大小l[^[11]];表示为：

（2.1）

（2.2）

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

相关图片展示：