摘 要

海洋目前作为在各个国家都是十分关键的一些条件资源，对海洋资源的开发利用过程中一定不可缺少的工具则是水下机器人。很多的难题由于水下复杂的自然环境需要适度进行解决，所以水下机器人必须在工作过程中根据机器人自身的形态、位置和运动姿态、求解精度与内存空间这些条件来从海洋（水下）这样的环境中寻出从设定好的起点到终点的最短且无碰撞路径。考虑到这些必须因素，本文决定采用差分进化算法进行该路径的规划，这种算法是由种群中每一个个体之间的相互合作与竞争所产生的群体进一步地进行进化并且优化搜索方向。在总体搜索过程中差分进化算法拥有着其他算法很多不可比拟的优点比如操作原理简单，鲁棒性强和寻找最优解的性能优秀等。在完成了应用于该问题的差分进化算法的编制与测试后，本文将其与传统遗传算法进行了仿真实验，通过数据实际对比了两种算法在水下机器人路径规划问题中的利弊。

关键字:海洋资源；水下机器人；差分进化算法；路径规划；鲁棒性

Absrtact

The ocean is a key resource in every country at present. Underwater vehicle is an indispensable tool in the development and utilization of ocean resources. Many difficult problems need to be solved moderately in the complex underwater natural environment, so the underwater vehicle must find the shortest and collision-free path from the set starting point to the end point in the working process according to its own shape, position and motion attitude, solution accuracy and memory space. Considering these necessary factors, this paper decides to use differential evolution algorithm to plan the path. This algorithm is generated by the cooperation and competition between each individual in the population to further evolve and optimize the search direction. Differential evolution algorithm has many incomparable advantages in the overall search process, such as simple operation principle, strong robustness and excellent performance in finding the optimal solution. After completing the compilation and testing of the differential evolution algorithm applied to this problem, this paper simulates it with the traditional genetic algorithm, and compares the advantages and disadvantages of the two algorithms in the underwater robot path planning problem through the actual data.

Key words: marine resources；underwater vehicles；differential evolution algorithm；path planning；robustness

目 录

第1章 绪论 1

1.1 设计的目的及意义（含国内外的研究现状分析） 1

1.1.1目的及意义 1

1.1.2国内外研究现状 1

1.2 课题研究内容、目标以及拟采用的技术方案 2

1.2.1 课题研究内容及目标 2

1.2.2 技术方案 2

第2章 水下机器人路径规划 4

2.1路径规划简述 4

2.2几种路径规划方法 5

2.2.1位置空间法 5

2.2.2地图搜索法 5

2.2.3人工势场法 6

2.2.4模糊逻辑算法 7

2.2.5蚁群算法 7

2.3本文所采用的路径规划方法(差分进化算法) 8

2.3.1 差分进化算法优势 8

2.3.2差分进化算法流程 8

2.3.3参数设置 11

第3章 环境地图构建 12

3.1环境的表示方法 12

3.1.1环境建模 12

第4章 问题模型的求解 16

4.1种群初始化 17

4.2变异操作 17

4.3交叉操作 17

4.4 选择操作 17

第5章 路径规划仿真及结果分析 19

5.1仿真环境 19

5.1.1 软件环境 19

5.1.2 硬件环境 19

5.2 仿真过程 19

5.2.1 环境1中求解的结果对比 19

5.2.2 环境2中求解结果对比 20

5.3 仿真结果分析 20

第6章 结论 21

6.1结论 21

6.2展望 21

参考文献 22

致 谢 24

第1章 绪论

1.1 设计的目的及意义（含国内外的研究现状分析）

1.1.1目的及意义

水下智能机器人的应用领域在逐渐增加，包括军事，渔业，潜艇勘探和海上平台的监测。由于其在海洋开发和海底勘探领域的广泛应用前景，它引起了所有国家的关注。路径规划是主要的智能水下机器人技术之一，其任务是根据某些评估标准（如最短或最短路径）找到一种安全有效的方式从起点到达目标点，在有障碍的环境中寻找到一条无碰撞的通道。水下机器人工作环境复杂而又开放，对其进行规划的难度也大大增加。同时，机器人自身的运动形状，位置和姿态，解决方案的精度与记忆空间之间的矛盾也是规划路径时要考虑的必不可少的因素。规划水下机器人路径的主要目的如下：1）通过从当前位置移动到期望位置而不与水下障碍物碰撞来找到水下机器人的理想路径规划方式^[2-3]。2）算法找到的机器人路径必须符合机器人运动的真实特征，即在复杂空间运行所面临的现实问题。由于这些现实因素，本文决定使用差分进化算法来进行规划路径，差分进化算法是每一个组成种群的个体都即存在着合作又存在这竞争，在这种机制下会有优胜劣汰产生群体智能，根据这种方法来引导优化前进的方向或搜索的方向。这种方法的基本原理是在已有的群体中随机抽取两个个体与刚刚形成的群体中抽取的个体进行进行变异操作来生成一个全新的个体，然后在当代群体中生成新个体和相应个体。相比之下，如果新个体的适应性优于当前个体的适合性，则上一代的将被下一代的新个体所取代，否则上一代个体仍然被保存。 通过不断的进化，保持良好的个体，消除劣等个体，并指导寻求理想的解决方案。综上所述，差分进化算法使用起来比较简单，时间、空间复杂度较低，且鲁棒性比较好，在进行全面搜索的时候性能比较好^[1]。已成功帮助现代科学技术的发展多年。，如机械工程^[5-6]，通信^[7]和模式识别^[8]已经成为其研究热点。

1.1.2国内外研究现状

国内对于水下机器人相关问题的研究起步比较晚，大概在1970年代末期, 相比于欧美国家和日本处于比较落后的情况下, 当代我国比较先进的水下机器人是“海龙号”,以往国内研究的基础上进一步解决了深海运作时带缆容易断裂的问题。在二十一世纪初期年中科院自动化研究所成功研制出了国内第一个具有进行水下作业能力的水下机器人, 并在此基础上改进了实时避障路径优化方法，这种路径优化方法是将模糊垂直面路径优化和模糊水平面路径优化相融合，进而实现对路径的进一步优化。之后又有人提出了采用遗传算法生成栅格表对水下机器人的工作环境进行模拟，这种方法的基本原理是使用序号进行编码，然后在使用与序号对应的遗传算法，这样做可以有效的留下最优的遗传算法策略，该策略在进化过程中可以并行地对空间中的不同的区域进行并行搜索,之后在此基础上，为应对计算的过程中不会只得到局部的机制，加入了插入、删除算子优化进行全面搜索最优求解路径，这种方法的灵活性、鲁棒性比较好。

国外在水下机器人的研究起步比较早，技术比较先进。在1957年美国就已经研发CURV“开尔夫”水下机器人，之后开尔夫机器人在军事上完成了无数次任务，并在一次任务中从海底回收100颗鱼类这样的丰功伟绩。因为军事及海洋工程迫切的需要，电子技术、计算机技术、高分子材料等多种高科技技术得到了迅速的发展，得到了软硬件的支持，在上世纪的七八十年代水下机器人的发展也非常迅速，应用的功能领域也有了新的变化，例如在海底进行检查搜索，对特殊物质进行采样，完成海底试验、救援、工程建设等各种用途的水下机器人已经出现，工作效率越来越好，工作水深度也越来越大。西方国家掌握着较多先进技术，研发了较多不同领域、不同功能的水下机器人，在全球范围能处于领先地位。水下机器人应用最多领域是军事、经济，目前水下机器人在该领域的应用也是一个热点，开发更加强大的水下观测、水下作业机器人有着重大意义^[12]。因此学者们开始广泛关注其中甚为关键的水下机器人路径规划问题，路径规划是水下机器人应用的关键，也是一个难点，关于在水下怎样进行避障、轨迹控制Kaith等人提出了有效的解决办法，即人工势场法，但这种方法也有缺点，在对路径进行最优求解时容易产生死锁的情况，无法求求出全局最优解。另一种广泛使用的路径规划方法称为模糊集合论由Zadeh 建立,是一个可以被利用来解决各种路径规划问题的相应求解方法, 接下来又有人提出了^[16]这模糊控制算法。针对路径规划求解的时间、空间复杂度较高问题，很多学者提出了种群算法对路径规划进行优化，种群算法包括粒子群算法^[9]，蚁群算法^[10]，分布算法估计，遗传算法、动物迁移优化，萤火虫算法，差分进化算法^[1]等。

1.2 课题研究内容、目标以及拟采用的技术方案

1.2.1 课题研究内容及目标

1，对水下机器人的工作环境进行仿真模拟，包括建立障碍模型和工作区域的数学模型等。

2，使用仿真工具MATLAB对路径规划算法差分进化法进行实现。

3，完成相关的仿真实验，通过多个算例对本课题所设计的算法进行仿真验证和分析。

1.2.2 技术方案

1．水下下机器人必须在工作过程中根据机器人自身的形态、位置和运动姿态、求解精度与内存空间这些条件来从海洋（水下）这样的环境中寻出从设定好的起点到终点的最短且无碰撞路径。考虑到这些必须因素，本文决定采用差分进化算法对模拟有障碍物的水下环境，使用水下机器人进行实验，使水下机器人按照规定的路径行走越过障碍物，实验过程准备工作如下：

(1)限制水下机器人的活动范围。

(2)对水下机器人的活动环境进行限制，本文只研究静态环境下水下机器人路径规划问题，在空间中．对各种形状的障碍物进行简化，将障碍物用能进行大小及形状设定改变的不规则几何图形来表示。

2．建立目标函数:

目标函数的建立应考虑到具体问题的特征,即在寻求最短路径的同时还能完全避开障碍物。

3．利用差分进化算法进行路径求解，与其他算法类似，DE也有许多缺点。例如，首先，DE具有较好的勘探能力，但其局部开采能力较弱。其次，随着搜索空间维度的增加，DE性能下降^[13]。同时，DE对控制参数的选择很敏感，很难针对不同的问题进行调整。因此，为了成功解决复杂问题，参数设置和变异策略非常重要。因为差分进化算法在连续域的很多优点，这篇文章将利用它对水下机器人进行路径进行规划和优化。

4．进行仿真实验，并进行分析。为了验证本文设计的差分进化算法在水下机器人路径规划中的有效性，与传统的遗传算法进行对比分析，在相同的实验环境下进行两组实验，这样便可以得出差分进化算法在水下机器人路径规划问题中的运用是否有效的结论。

第2章 水下机器人路径规划

2.1路径规划简述

路径的规划在机器人学中占据了很重要的位置，路径规划是一个很关键的问题，这是一个关键词在国内外有不同的称呼，如Path Planning，Find-Path Problem，AvoidanceMotionPlanning等。水下机器人的种类也有很多，主要分为关节式、移动式机器人，这两种机器人各有优点，关节式机器人更加灵活，具有更多的自由度，移动式机器人可以获得更大工作范围。但这两种水下机器人都是路径规划的对象，在工作时都需要对路径上的障碍物进行规避，这种行为就被称作路径规划，这也是机器人在实际应用中一项关键技术。在机器人的实际应用中都需要机器人从起始点到终点的过程中按照规定的路线运动，并对障碍物进行规避。这种规避行为并不是要求取两点之间的最短路线，因此所使用的路径规划方法不同于动态规划方法的求解，而是对水下机器人的工作环境中的障碍物进行综合性的判断，考虑多种因素选择比较好的路线，完成任务。

关于机器人路径规划主要存在一下几个问题：

(1)工作环境模拟问题。对水下机器人工作环境的模拟主要表现在障碍物和空间的模拟，对工作空间的准确模拟，有助于更加准确的获取最优路径。对水下机器人进行环境建模是对其进行路径规划的前提，首先要将工作环境外在的表示形式、影响因素进行仿真处理，将其处理为有较好规划效果的空间模型，这一过程我们也称作环境建模。本文实验主要模拟水下机器人的避障能力，所以对障碍物的模拟在本实验中是比较重要的，越逼真越合理的环境模型，才能验证路径规划方法的最优性，到达路径搜索的时间、空间复杂度最小，得到最真实的结果。另外，不同的路径规划方法使用的模拟工作环境也是不一样的，如果需要验证不同的路径规划方法，我们需要建立多种环境模型。

(2)空间最优化问题：设置指定的区域R，设置指定物体A的起始位置，并使A与其它物体保持距离，不发生碰撞。

(3)路径最优化问题：在第二个问题中已经描述了区域R、物体A、物体B，在区域R内使物体A从起始点，按照规划的路径进行移动，确保物体A的运动路径是安全的不同物体B发生碰撞，物体A移动经过的位置所组成的路径被称作安全路径。上面已经介绍过路径规划的前提是水下机器人工作环境模型的建立，一个合理的环境模型，可以有效的表示机器人在运动过程中对每一个障碍物规避的概率，这种模型的表示形式是数据结构。按照数据结构构造的环境模型进行路线连通性的规划，并绘制成图，绘制出来的路径规划图要保证它是环境模型的一部分，没有环境模型之外的干扰因素和无关的路径信息，保证路径规划图的可靠性。最后按照路径图规划的空间，进行路径的搜索，最终可求解出一条最优的路径，将在这条最优路径进行转换，转换为模拟空间中的表示形式，用数据进行表示，就可得到该路径的坐标形式，这一系列的坐标信息就组成了水下机器人的无障碍路径。

2.2几种路径规划方法

做为机器人的关键问题路径规划，已经经过了五十年的研究历程，同时在某些方面也取得了一些突破性的进展，针对不同的问题和应用情况也提出了很多行之有效的路径规划方法。下面对几种常见的路径规划方法进行介绍。

2.2.1位置空间法

位置空间法采用的是模拟一个指定的点对模拟工作环境模型的位姿空间的水下机器人所在的点和所在的方向进行表示，这种方法简化对机器人路径规划研究的过程，逐渐成为研究该问题的一个基本工具，也被称作无碰撞路径规划方法。这种方法是由R．A．Book等人提出的，它的基本原理是将模拟空间的运动的物体进行简化，将其假设成一个运动的点，并对它的体积和位置进行一定的膨胀，即将障碍物的周边进行一定距离的扩张，形成扩张障碍，这样就可以形成一个新的空间，该空间被称作位置空间，在这个空间中运动物体的空间位置同样是一个点，这个位置点就可以代表运动的物体。模拟的障碍物形成障碍区域，即扩张障碍区，在模拟空间中占据一定的位置，在物体运动时位置空间法就将这一过程简化为一个点的路径最有问题。它的实质就是使用数据虚拟化了运动目标、障碍物，采用数学和几何形式对路径问题进行求解，简化的问题的复杂度和求解过程。位置空间法将复杂的运动物体避障路径规划的问题简化为了点的路径优化问题或路径安全问题，大大减少路径规划的时间、空间复杂度，因此该方法的应用比较广泛。目前位置空间法的表示形式主要有两种，一种数数据可视化法，另一种是几何空间法，即在一个规定的空间环境中，在环境中规定指定的起始点、终点和行走路线，并将其以坐标点的形式进行表示，进而机器人行走的安全路径就可以采用与障碍物没有交集的线段连线进行表示。考虑到实际的机器人是由体积和形状的，在实际实验中要将其考虑进行，避免机器人靠近障碍物时，出现离障碍物的距离比较近或者发生碰撞，和在出现障碍物比较密集的时候搜索的时间、空间复杂度比较高的情况，后采用Voronoi Diagrams法和Tangent Graph法对数据可视化方法进行优化。数据可视化方法对路径进行求在一定程度上是可行的，但存在组合爆炸问题，缺乏灵活性，只能适用在二维空间中，不适合在三维空间中使用。

2.2.2地图搜索法

地图搜索法一般采用的是提前建立好的空间结构，然后对建立好的再划分为独立的单元。如果空间结构中含有大量的障碍物，则会被叫做障碍物单元；如果空间中只含有少量的的障碍物，则会把这些单元规定为混合单元。如果划分的空间中一个障碍物都没有，则此单元为最理想的单元，也被叫做自由化单元。地图搜索法这种方法主要是通过把这些单个单元连接起来构成一个整体的地图，然后根据这个构成的新的整体地图上，再运用一些特定的算法进行路径规划。主要应用为栅格法。栅格法主要是把实际的空间环境划分成了一系列的网格单元，每个网格中含有自己特有的环境特征，主要通过四叉树或者八叉树来代表实际的环境状况，最后通过采用相对应的优化算法在这些网格中找出适合自己的路径。这种方法主要是通过里面最小的单元栅格来展示各自位置对应的实际环境，这些栅格各自具有自己特有的分辨率，因此可以看出栅格单元的大小对实际环境特征的展示有直接影响，同时对后续做路径规划模块运作时也有很大的影响。如果单元划分太小则会对实际环境状况不能做详细的展示；如果太大，则会导致路径规划时花费大量的时间。A．Elfst对确定的全局关规划网络做了提出； Faverjon采用了八叉树的方法来展示实际空间环境状况，并且做了相应的路径规划； Subbarao Kambhampati采用了不完全四叉树的表示方法展示了空间环境。从本质上来看，位置空间法也是采用单元网格的方法来做环境特征表示，因此也属于地图搜法。

2.2.3人工势场法