摘 要

湖泊是自然生态系统的重要组成部分，也是我国重要的生态资源。我国湖泊众多，然而随着我国工业的快速发展，水环境污染问题日益严重。水质检测是改善水环境不可缺少的环节，传统的水质检测主要依靠人工采集样本，人力资源成本高。随着人工智能和科技的发展，对无人船的研究愈发成熟，无人船在水质检测方面的应用也越来越多。路径规划是无人船自主导航的关键技术之一，本文主要对静态湖泊环境中的全局路径规划进行了研究，主要内容包括：

首先对无人船的作业场景进行环境建模，通过图像的预处理建立便于计算的二值图，再建立与二值图像对应的栅格地图。其次是在栅格地图中对无人船航行路径的搜索，本文分别研究了基于A*算法的4领域和8领域的全局路径规划。然后对A*算法生成的路径进行了平滑处理，第一步删除初始路径中共线的冗余点，第二步删除多余的拐点。最后用C#语言进行了模拟仿真，验证了算法的可行性。

关键词：无人船，路径规划，栅格地图，A*算法，路径平滑

Abstract

Lakes are an important part of natural ecosystems and an important ecological resource in China. There are many lakes in China. However, with the rapid development of China's industry, the problem of water pollution has become increasingly serious. Water quality testing is an indispensable part of improving the water environment. Traditional water quality testing relies on manual sample collection and high human resource costs. With the development of artificial intelligence and technology, the research on unmanned surface vehicles has become more and more mature, and the application of unmanned surface vehicles in water quality testing is increasing. Path planning is one of the key technologies for unmanned navigation. This paper mainly studies the global path planning in static lake environment. The main contents include:

Firstly, the environment of the unmanned surface vehicles' work environment is modeled, and the binary map which is easy to calculate is established by image preprocessing, and then the grid map corresponding to the binary image is established. The second is the search of the unmanned surface vehicles ' driving path in the grid map. This paper studies the global path planning of 4 fields and 8 fields based on A* algorithm. Then the path generated by the A* algorithm is smoothed. The first step is to delete the redundant points in the original path, and the second step is to delete the extra inflection points. Finally, the simulation is carried out in C# language to verify the feasibility of the algorithm.

Key words: unmanned surface vehicles, path planning, grid map, A* algorithm, path smoothing

目录

第一章绪论 1

1.1课题背景和意义 1

1.2国内外研究现状 1

1.2.1无人船的研究现状 1

1.2.2路径规划的研究现状 3

1.3研究内容 4

第二章环境建模 5

2.1环境建模方法概述 5

2.2栅格法环境建模 6

2.2.1图像预处理 6

2.2.2栅格属性化 9

2.2.3坐标转换 10

第三章基于A*算法的路径规划 12

3.1 A*算法基本原理 12

3.1.1估价函数 12

3.1.2 A*算法的流程 14

3.2算法实现 16

3.2.1节点设置 16

3.2.2搜索方向 16

3.3路径平滑 18

第四章模拟仿真 20

4.1算法仿真 20

4.2可靠性和一致性验证 22

第五章总结与展望 25

参考文献 26

致谢 28

第一章绪论

1.1课题背景和意义

湖泊是自然生态系统的重要组成部分，在维护生物多样性方面具有至关重要的作用，也是我国居民生活用水的重要来源，超过50%的全国城镇饮用水源来自于湖泊^[1]。我国湖泊众多，然而随着我国工业的快速发展和生活水平的提高，各类污染物质随着各类途径流入河流或者湖泊等地表水系，水环境污染问题日益严重。据统计我国90%以上的水体都受到了不同程度的污染^[2]，这给社会、经济、文化以及生物多样性的健康和可持续发展带来了不同程度的影响。

为了打好污染防治攻坚战，改善湖泊水环境质量，确保水环境生态安全是当务之急，而水质检测是改善水环境不可缺少的环节。水质检测需要大量采集污染水质并进行水质分析，最早的水质采集主要依靠人工进行。近年来，随着人工智能和科技的快速发展，无人船逐渐走进人们的视野, 无人船在水质检测方面的研究与应用也越来越多^[3][4]。

无人驾驶船舶（Unmanned surface vehicles, USV）是直接通过自动导航系统控制的船舶的总称，没有船员的情况下也能维持正常的航行和操作^[5]。无人驾驶船舶涉及非常广泛的技术领域，其中主要技术包括路径规划技术、通信技术、自主决策与避障技术以及水面物体探测与目标自动识别技术等^[6]。

与传统船舶相比，水面无人船具有体积小、速度快、可航行范围广以及智能化程度高等优点。在军事方面能够灵活作战，并可以在不适合有人船艇的区域独立执行任务。除了军事方面，无人船还可应用于科学考察，环境监测、区域巡航等领域，在水质检测、污染治理、巡逻等方面也有着广阔的应用前景。

1.2国内外研究现状

1.2.1无人船的研究现状

在无人驾驶领域，无人船的发展相对滞后于无人机和无人驾驶汽车的发展，且大多应用在军事领域。2011年，内华达州立法委员会通过了美国首部允许测试无人驾驶汽车的法案^[7]。2013年12月，亚马逊提出了利用无人机进行递送服务的计划。对于无人船的研究则可追溯到二战时期，大多数早期的无人船都只能通过无线电信号控制，自主活动能力非常有限。二十世纪七十到八十年代，由于技术限制，无人船主要用于军事演习 ^[8]。进入二十一世纪，随着人工智能和通信技术的发展，世界各国都加大了无人船的研发投入，无人船

的用途也逐渐从军用走向了民用。

相比于国外，我国对于无人船的研究起步较晚，但该领域的研究受到越来越多的关注。已从最初的概念设计逐步过渡到实际的应用过程，并取得了一定的成果，如图1.1所示。2008年，国内研发的第一艘无人驾驶海上探测船“天象一号”问世^[9]。2012年，云洲智能科技有限公司推出了我国第一艘全自动无人采样船以及应急监测无人船等产品。2017年9月，深圳海斯比船艇公司和哈尔滨工程大学联合研制的无人快艇“天行一号”问世，其最高航速超过每小时92.6公里^[10]。

（a） （b）

（c）

图1.1无人船（a）天象一号 （b）ESM30采样船（c）天问一号

1.2.2路径规划的研究现状

路径规划技术是无人船实现自主导航的关键技术之一，也是人工智能的研究热点之一。目前对路径规划的研究主要集中于机器人、无人驾驶汽车和无人机等领域。路径规划是指在起点和终点位置已经给定，且两点间障碍物和可通行区域已知或未知的环境下，通过路径规划算法，规划出一条满足从起始位置到目标位置的安全可通行无碰撞最短路径。

根据对环境信息掌握程度的不同，可将路径规划分为两类：全局路径规划和局部路径规划，局部路径规划和全局路径规划在本质上而言并没有区别 ^[11]。全局路径规划是一种在静态环境中的路径规划，即在工作环境已知且不变的前提下，搜索从起点位置到目标位置的无碰撞最短路径。目前对于全局路径规划的研究已经取得了不错的成果，但仍有一定的局限性。

局部路径规划则侧重于路径规划的实时性，适用于处于变化状态或未知的工作环境，而要在未知或部分未知的环境找到一条可行无碰撞路径，无人船必须依靠传感器获取当前的环境信息，并以此为依据更新地图。局部路径规划具有较高的灵活性和实时性，但由于其依赖于环境的局部特征，其搜索的路径可能只是局部最优而非全局最优^[12]。

根据不同的运动目标，又可将其分为点到点的路径规划和完全遍历式路径规划两类。点到点的路径规划目标是搜索一条从起始节点到目标节点的无碰撞最优路径，而完全遍历式路径规划的目标是在工作区域内搜寻一条从起始节点到目标节点的无碰撞路径的同时，保证经过所有可航行节点，同时要满足低重复率和高覆盖率等指标。常用的完全遍历式路径规划算法包括单元分解法^[13]和模型模板法^[14]等。

随着人工智能的快速发展，国内外研究人员在路径规划问题上的研究也有了很大进展。从一开始的传统算法如广度优先算法、迪杰斯特拉算法^[15]等发展到后来的启发式以及仿生算法如遗传算法^[16]、人工神经网络算法^[17]、A*算法^[18]等，路径规划领域的算法已经愈发成熟。随着研究人员对路径规划的研究越来越深入，移动机器人、无人机、无人船等自主无人设备的应用也越来越广泛。

目前已知的路径规划算法都各有优缺点，其中A*算法是经典的路径搜索算法，吸收借鉴了迪杰斯特拉算法的优点，并引入了启发信息，具有效率高、扩展节点少、响应速度快且准确性高等优点，是一种在静态路网中求解最短路最有效的直接搜索算法，因此被广泛应用于路径规划问题，游戏中人物的自动寻路也常使用该算法^[19]。然而传统的A*算法生成的路径既不平滑也不连续^[20]，本文选题的目的在于，首先通过栅格法建立环境模型，然后通过A*算法生成一条最短的无碰撞路径，并对已生成的路径进行平滑处理以满足无人船的

机动性，最终实现无人船在静态环境中的全局路径规划。

1.3研究内容

研究内容主要从无人船的工作环境建模、路径搜索和路径平滑三个方面进行讨论，如图1.2所示。

1）首先对无人船的工作环境建模，环境建模是解决路径规划问题的首要工作，其目的是建立一个易于计算机识别和使用的环境模型。鉴于无人船实际作业环境的复杂程度和算法特性,本文拟采用栅格法进行环境建模。

2）路径搜索，在环境建模的基础上应用A*算法在静态环境中寻找一条可行的，无碰撞的最短路径，实现初步的全局路径规划。

3）限于栅格地图的特性，传统A*算法只能向有限的方向进行搜索，最后生成的路径必然存在很多拐点，导致无人船实际航行时需要经常改变方向。考虑到无人船的机动性以及能耗，拐点较多的路径在实际作业环境中是不适用的，最后有必要对已经生成的路径进行平滑处理。

模拟仿真

图像预处理

栅格属性化

全局路径规划

路径规划算法设计

环境建模

图像灰度化

图像二值化

坐标属性

障碍物属性

自由属性

路径平滑

A*算法路径搜索

图像膨胀化

图1.2研究内容

第二章环境建模

2.1环境建模方法概述

无人船路径规划的第一步就是要建立恰当的环境模型，环境建模实际上就是用计算机语言对环境中障碍物和自由空间进行描述。准确的地图信息有利于之后进行的路径搜索，环境建模方法的选择必须虑到无人船实际作业环境的复杂程度和所用的路径搜索算法，主要且常用的建模方法有栅格法、可视图法和拓扑图法等。

栅格地图^[21]是通过对无人船的工作环境进行栅格化处理，将其分解为多个大小相同的矩形区域后得到的信息地图。栅格地图容易实现和维护，也是目前最常用的一种环境地图。栅格的尺寸大小会直接影响其性能，栅格尺寸越小，精确度越高，环境信息越完整，但同时栅格数量会大量增加，地图维护所占用的内存和时间也迅速增加，最终导致计算机处理难度的提高^[22]。

可视图法适用于只存在多边形障碍物的环境，该方法将环境中多边形障碍物的所有顶点、起始节点和目标节点用直线相连，同时要保证这些直线不会穿过障碍物，这些点之间的连线就是可视的，如图2.1所示。搜索最优路径的问题就转化搜索为从起点经由这些可视直线到目标点的最短路径的问题^[23]。然而大部分可视线对于路径搜索是无用的，而这些可视线占据的存储空间较大，直接影响了算法效率，而且只能处理多边形障碍物。

图2.1 可视图法

拓扑图最初是由Kuipers等人在1991年提出的，用于描述移动机器人的导航空间。拓扑地图由一系列的节点和连接线组成的拓扑结构图，根据环境的几何特点, 该方法将工作空间划分成具有相同拓扑特征的多个区域,并根据相互的连通性创建拓扑网络 ^[24]。拓扑地图可用公式2-1表示^[25]：

G=（V，E） （2-1）

式2-1中G表示拓扑地图，V表示节点的集合，对应于环境中的一些关键位置点，表

示无人船能够到达的地方，E 是边的集合，表示无人船可以行驶的路径。拓扑地图需要的存储空间小，重在描述环境的拓扑结构，缺点是容易产生定位错误，且定位精度较低，当环境中存在两个很相似的地方时，拓扑地图很难加以区分。

栅格图法和可视图法一般用于表示简单地图，而拓扑图法则表示全局环境的联通性，无人船的工作区域主要在湖面，地图简单，而且鉴于湖面轮廓的不规则性，本文拟选用栅格法进行环境建模。

2.2栅格法环境建模

2.2.1图像预处理

为便于区分障碍物和自由区域，栅格法环境建模首先要对环境地图进行预处理，预处理分为三步。第一步将图像转换成灰度图，第二步对灰度图进一步处理，将其二值化，最终转换成黑白图像，第三步对二值图进行膨胀处理。

第一步图像的灰度化处理，在RGB模式中，图像的颜色是由红、绿、蓝三原色的比例决定的。图像中的每个像素点的颜色取决于三个分量R、G、B的值，而每个分量的取值范围为0到255，因此每个像素点可以有超过1670万种颜色。要将彩色图转化成灰度图，必须使像素点的R、G、B三个分量值相等，其中R=G=B的值叫灰度值，取值范围为0到255。图像的灰度化处理一般有以下几种方法：

1. 分量法：将像素点的三个分量中的某一个分量值作为该像素点的灰度值，即灰度值=R或G或B，实际可根据应用需要选取一种灰度图像,如图2.2所示。

（a） （b） （c） （d）

图2.2分量法示意图（a）原图 （b）R分量 （c）G分量（d）B分量

1. 最大值法：把像素点的三个分量中值最大的分量值作为该像素点的灰度值，即灰度值=max{R,G,B}。
2. 平均值法：计算像素点的R、G、B三个分量的平均值，然后以这个平均值作为该像素点的灰度值，即灰度值=（R G B）/3。
3. 加权平均法：将像素点的三个分量赋以不同的权值进行加权平均，一般情况下灰度值= 0.229R 0.587G 0.114B。

（a） （b） （c）

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

相关图片展示：