英语原文共 5 页，剩余内容已隐藏，支付完成后下载完整资料
多变海域中自动水下航行器路径规划的发展
Alberto Alvarez, Andrea Caiti, and Reiner Onken
摘要：本文提出了一种基于强流和增强时空变异性的海洋环境下自主水下航行器的路径规划的遗传算法(GA)。我们的目标是找到一条安全的路径，将水下航行器从起始位置移动到指定的目的地，并且将能源成本降到最低。此遗传算法包含了新的遗传算子，即使在当前流场的结构(在空间和时间)中存在着不同的局部极小值的情况下，也可以确保全局最小值的收敛。讨论了这些算子的性能。该算法适用于水下航行器必须执行高能耗任务的情况。
关键词：自主水下车辆(AUVs)，遗传算法，海洋变异性，优化，路径规划。
- 简介
对航行器路径规划方面进行性能优化是自动无人航行器的基本要求。对于自动驾驶的水下航行器(AUVs)，优化的方面与航行时间和安全条件有关[17]。所规划路径应该一直障碍物和危险区域。当不考虑能源问题时，这是一个十分有效的方法。然而，当水下航行器必须在具有相对强劲的水流流和复杂的时空变化特征的环境中执行高能耗的任务时，就会产生很多困扰。在这种情况下，以最小的能源成本来规划安全路线是十分重要的。这种方法可以参见AUV任务计划的一个例子，以优化能耗，同时保证海洋采样的时间和空间覆盖[2]。在最短路径的优化问题上另一个已经研究过的问题是在给定区域使用声呐保证地形覆盖[11]。近年来，海洋学的研究方向已经转移到沿海水域，因为那里具有空间和时间上十分多变的海洋环境[23]。水下航行器经常在这些区域遇到强烈的水流。在这种情况下，优化能源成本的任务规划是非常值得的。
在文献中可以找到解决寻找路径的几种方法。在路径已经生成的基础上，寻路算法可以分为预生成和反应两种[14]。预生成方法中路径规划是在执行任务之前进行的，而反应方法中路径规划是航行器在环境中运行时生成的[7][16]。现有的路径规划算法采用了不同的计算方法。势场算法利用人工势场确定障碍物和目标位置，并利用由此产生的流场影响机器人的路径。这些方法是快速的并且可以扩展到更高的维度，但是容易受到局部最小值的影响[28]。图形搜索技术之所以如此命名，是因为它生成了一个图表或图形，显示了没有碰撞的自由空间，以及发生碰撞的空间。根据生成的图表，通过拼接自由空间或通过追踪禁行空间来选择路径[5]。图形搜索方法对于局部最小值解决方案是十分合适的，但是在高维问题中很难使用[4]。当一个路线和图表每一个弧线都相关的时候，图形搜索过程中通常使用动态编程的方法。虽然这样能够生成最优解，但是动态规划的时间和图中的节点成正比，这又取决于解空间的网格大小并且随着解空间的维度几何增长。AUV在时间和空间都在变化的环境下导航，解空间是一个四维空间，动态规划可能在计算上是不可行的，特别是在反应性路径规划的案例中，在这种情况下，每次更新环境的信息时都要重新计算最佳路径。诸如案例推理等技术也被应用于路径规划问题[27]。
基于达尔文自然选择和存活理论的程序路径规划的应用已经被大家所意识到了[10],[13],[19]。在这些被称为遗传算法(GAs)的策略中，可以生成一群可能的路径，并通过交叉和突变等遗传算子对路径进行迭代转换。遗传算法已经被用于地面和水下遥控机器人的路径规划问题中了[12],[19],[26],[9]。与动态规划不同，像遗传算法这种软计算的计算复杂度随着解空间的维数线性增加（例如以节点的数量为对数）[15]。但它的缺点是，在有限的时间内不能保证最佳解的收敛性，这样就只能得到一个次优解。因为之前提出的遗传算法水下航行器路径规划方案没有考虑到周围环境的时空变化特性。
在此研究中，我们介绍一种解决在时间和空间变化的海洋环境中运行水下航行器路径规划问题遗传算法。可以通过预测模型来预测海洋环境的时间演化，对于海洋环境随时间演化的预测可以通过预测模型，也可以通过新的测量方式和更新预测获取航行器导航信息。因此该规划算法可以在混合预先生成/反应性规划情况下无需修改就应用。该方法结合了在遗传算法规划过程中使用特殊算子的方法，从而提高了鲁棒的鲁棒性和收敛性。此外在三维空间并且时间和空间都在变化的情况下（解空间未四维空间）被提出的算法是一种混合动态规划减少维度和基因遗传算法的混合算法。这一研究仅限二维情况的初步结果已经被提出[1]。并在此基础上，我们结合在地中海的实际环境状况下的实际应用对该算法及其在三维空间和时间变化背景下的性能进行了详尽的描述。本文按如下方式组织，第二章提出了求解路径规划的问题并描述了所提出的遗传算法的主要特征。第三章展示了GA算法在不同代表性的情况下的不同配置得到不同的结果。情况包括在二维和三维的情况下，一个具有复杂的空间变量流场的静止海洋的情况和一个时间空间都在变化的情况。第四章描述了在真实的海洋环境中，应用GA算法对假想的AUV路径的能量成本进行优化的结果。第五章给出结语
- 路径规划问题
把水下环境描述为一个大小的离散空间，并建立笛卡尔坐标系，在海面位置z=0并且z轴指向海底。设Delta;x,Delta;y,Delta;z为x,y,z轴上网格的间距。网格中的任意一点定义为X=(h,k,j)，并且0le;hle;m，0le;kle;n，0le;jle;p。从起点S到终点D的路径Gamma;是由一系列的点组成，并且此路径是由两个相邻的点之间直线连接而成。在实践中，假定AUV导航路径是通过网格节点的路标来确定的。空间中的障碍（例如不同深度物体或者海岸线）可以通过在空间中加入不可行的点来标记。空间中的任意一点的速度矢量定义为。根据以上的条件，我们可以对路径规划问题做如下阐述：给定路径起始点S和路径终止点D，障碍和当前的流场，找到一条航行器以速度c匀速运行并且航行所需能量最低的路径，约束条件为此路径不与任何固体障碍物相交。对于AUV在最低恒定运行速度的假设相当于以更小的能量消耗找到满足任务要求的路径。关于其他的优化问题，例如在给定推力的情况下的最小时间路径，可以通过在本研究所开发的技术对相应函数进行适当的修改之后解决。为了简单起见，我们假设m=n=p并且假设起始点和终止点在x轴上例如s=(0,.,.)，d=(m-1,.,.)。所有的路径在x坐标上都是严格的单调的，这样任何两个相邻的点都能满足关系。这意味着每个允许路径是一个m个节点的序列。显然，不是所有的路径都是单调的。因此，这一假设暗示了在在具有极其拥挤的障碍的海洋区域排除一条最佳路径的可能性。然而，当空间网格不密集时，单调路径可以表达十分复杂的路径[26]。此外在一个多变的海洋环境中，限制路径的单调性和和恒定的巡航速度自然会避免不需要的解决方案，这种解决方案涉及由洋流导致航行器向后飘逸。解决上述路径规划问题的遗传算法以及一些简单的例子，如下所诉。
初始化：随机生成N个体的种群，每一个体对应一个候选解决方案的路径，这一群体代表潜在的解决方案的集合。种群对应的所有路径都随机的从起始点连接到终止点。
个体计算的要点：先添加种群中每条路径所需要用来克服当前流场阻力的能量再计算得出每条路径的能量成本。设任一路径中的第i段连接点和。用表示此段的长度，用作为此段的单位向量用来表示航行器在此段的运动方向.当航行器以额定速度c在此段行驶时在此段中的任意一点(x,y,z)的速度为。
(1)
设数量为
(2)
第i段的能量消耗为
(3)
其中rho;是与航行器大小和水的性质有关的定值。最终的总能量消耗为。那些带有不可行点的路径会有很大的多余能量消耗。特别要注意的是，为了简化过程，当只包含影响能量消耗成本的唯一变量时（例如、航行器的实际速度和路径段的长度），能量消耗可以通过将加在一起而不是通过来计算。在实际应用中，是通过该点网格上进行有限的求和计算的，但是这些点可能与路径点节点的网格是不一致的。路径的强度通过和其他路径的能量消耗成本来定义的。能量消耗最低的路径的强度最大。
选择：从当前种群中选出N/2个能量最低的路径。
交叉：新的个体（后文称为后代）是通过应用一个交叉算子产生的。每条路径的配对都是从n/2个体随机选择的。因此，总共形成了n/4对。每对的前两个后代和他们的父母是一样的。另外两个后代是通过父母的再组合而产生的。在前两个后代中，最好的潜在解决方案被保留，而改进的解决方案是在第二对后代中产生的。x坐标h1和h2是随机选择的，它们分别分布在开放的区间(0,m_1)和(h1,m)中。后代是由父母的个体之间的相互交换产生的，交换过程中将路径中x坐标在（h1,h2）之间的这些节点的y和z坐标进行变换。
突变：一小部分路径是随机突变的。具体而言，在突变期间，随机选择确定数量的路径。对于选择的路径，x坐标1和h2是分别在开放区间(0，m-1)和(h1，m)中随机选择的。把x坐标在(h1,h2)区间的点的y坐标和z坐标进行变换。具体来讲，这些点被变成，其中和是从区间和中随机选出的整数。排名靠前的路径可以免于突变，这样他们的信息不会无意中丢失。突变确保解决方案不会过早地收敛到一个稳定的局部最小值。每一代的突变数，被排除的路径的百分比，以及间隔大小的，都是必须在开始时指定的参数。
对于该算法的（2）-（5）部分会一直重复计算直到确定的代数或者满足了停止的条件。根据当前流场的结构，可以出现几个接近最佳的局部最小值。一般来说，当寻求全局最小值的时候，使用强选择策略和小变异率的标准遗传算法快速消除种群的多样性。种群多样性的丧失，与最初随机产生的种群中的各向同性统计偏差相结合，会使遗传算法趋向于次优解。为了避免这种情况，两个算子已被纳入执行的遗传算法。第一个遗传机制被称为迭代，包括在不同的初始条件和迭代次数的情况下运行遗传算法几次[19]。
图1,从左到右的流场和优化路径
每次运行的最佳个体被选择成为最终运行的初始种群的一部分。这里的迭算子的作用不是多模式优化，而是提供可能的最小值对初始种群的估计。第二种遗传机制已被纳入到所提出的算法中。这个算子是基于随机移民机制的，它最初用随机生成的值替换了每一代的部分人口[8]。在一定的世代后，这个算子被用来代替种群中个体随机扰动的最强烈的个人。随机性的程度是由不断变化的人口的多样性程度决定的。
- 结果
A:遗传算法的灵敏度和鲁棒性：
在二维固定环境中具有复杂的空间可变性。
首先研究了一种简单的情况，即在二维静止海洋环境中描述了复杂的空间变化，以评估其灵敏度和对不同参数的鲁棒性。所描述的遗传算法已经实现了在二维空间域上的路径规划，该域由网格为36 times; 36个点。网格点之间的距离对应20公里，因此总的系统大小为L=700公里。这个具有复杂空间变异性的固定流场[图1]是随机产生的，是由一个具有随机相位的各向同性能量谱产生。当前流场的速度被定为0.5。在这个区域没有任何障碍。作为参考，使用动态规划[图1]来计算最优解。
对遗传算法进行如下设置，它的种群大小是100个个体，而停止的标准是300代的上限和==3。图2(a)-(c)显示了每一代最佳路径的成本函数的演变，对于标准遗传算法配置，在10个仿真的整体上进行平均。在没有迭代和随机移民操作符的情况下，变异概率分别为0.05、0.25和0.75。结果表明，在所有情况下，能量成本函数的普遍下降。对于低突变率[图2(a)]，因为突变所代表的遗传算法的
图2，当突变率分别为(a)0.05(b)0.25(c)0.75时每一代最优路径的能量消耗函数，并与十次模拟平均值的比较，其中直线为动态规划算法的最小值
图3，当每代的随机移民数为(a)10(b)20(c)100时每一代最优路径的能量消耗函数，并与十次模拟平均值的比较，其中直线为动态规划算法的最小值
图4，当分别在5、10和20代之后选出最佳个体时每一代的最优路径能量消耗函数，并与十次模拟平均值的比较，其中直线时通过动态编程获得的最小值。
随机搜索分量相当有限，因此使用交叉机制搜索可能的解空间。交叉机制的确定性影响着最终结果对初始种群的主要依赖性以及对局部最小值存在的主要敏感性。这两个方法都转化为从总体统计中获得的标准偏差的高值。相反地，突变导致了遗传算法的搜索过程中的高突变概率[图2(c)]。该算法对局部最小值的存在具有鲁棒性，但其收敛较慢，类似于纯随机搜索过程。遗传算法的最佳性能在从0.15到0.5的变异率中得出。图2(b)显示了以0.25的突变率得到的结果。虽然结果大大改善了以前的情况，但算法达到的最小值仍然远离真正的最优解。从总体统计数据中获得的标准偏差的高值表明，算法的鲁棒性不强。不同的模拟情况会提供不同的路径，并且这些路径的能量消耗保持在平均值的plusmn;25%的范围内。下面的模拟中将会使用0.25的突变率。
每隔10代，20代和100代进行一次模拟统计[图3(a)-(c)]。随机移民的加入对标准版的算法性能有明显的
图5，(a)使用标准遗传算法与迭代和随机移民相结合的算法所得出的每一代的能量消耗的函数并与十次模拟的平均值相比较。(b)通过遗传算法（黑色）和动态规划算法（灰色）方法获得的最佳途径。
图6，(a)在有障碍的情况下，标准遗传算附加迭代和随机移民的运算所得的最优路径的能量消耗曲线吗，并与十次模拟的平均值相比较。(b)遗传算法（黑色）和动态规划（灰色）所得出的最优路线。
改进。具体来讲，在[图3(b)和(c)]中的能量成本函数的变化中，分别在第20代和100代的运算之后出现了明显的下降。同是我们还注意到在计算标准偏差中出现下降的趋势，这意味着算法的鲁棒性比在标准情况下要大。此后，每20代人将应用一次超级突变算子。与之间的模拟情况类似，我们将迭代操作加入到遗传算法中进行另外一组模拟，图4(a)-(c)显示当迭代运算应用于生成20个初始人口的种群时所得到的结果，并且分别在5、10和20代之后选出最佳个体。图4表示在标准的遗传算法中包含迭代计算大大改善了结果。该算法所获得的
全文共15885字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[9594]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
