基于数据驱动的遗传算法的无人艇路径规划研究
1
2
Study on path planning of unmanned surface vessel based on data-driven genetic algorithm
1
2
通讯作者:
修回日期: 2017-05-25 网络出版日期: 2019-06-20
基金资助: |
|
Revised: 2017-05-25 Online: 2019-06-20
Fund supported: |
|
作者简介 About authors
辛峻峰(1982-),男,山东青岛人,中国海洋大学博士生,主要研究方向为智能无人艇设计研究、港口航道及近海工程、船舶与海洋工程等 , E-mail:jf.xin@163.com
张永波(1981-),男,山东烟台人,中国海洋大学博士生,主要研究方向为海洋结构物水动力分析 。
伯佳更(1995-),男,主要研究方向为智能无人艇路线规划研究 。
赵博文(1998-),男,山东济南人,主要研究方向为船舶性能在CFD中的应用 。
范世缘(1998-),女,山东济南人,主要研究方向为机械设计、神经网络、认知神经科学等 。
遗传算法(GA)是无人艇路径规划系统中的一种有效方法,为了克服该算法易陷入局部最优早熟和收敛速度慢等缺陷,在不增加算法复杂度的前提下,基于数据驱动线性动态交叉策略提出了一种能够在最短时间内自适应动态调整控制参数的改进遗传算法(LCPGA)。与传统的遗传算法相比,LCPGA增加了种群多样性,能更有效地避免陷入局部最优,并提高了路径规划的精度、稳健性和收敛速度。仿真实验和无人艇现场试验验证了该算法具有更优良的性能,该算法可为无人艇路径规划提供一定的应用价值。
关键词:
The genetic algorithm (GA) is an effective method for the path planning system of unmanned surface vessel (USV),but it is easy to fall into local optimal precocity and converges slowly.For this,without increasing the complexity of the algorithm,a data-driven linear changing parameters genetic algorithm (LCPGA) was proposed,which can adjust adaptively control parameters in the shortest time.Compared with the traditional genetic algorithm,the LCPGA increases the diversity of the population,avoids falling into local optimum more effectively,and improves the accuracy,robustness and convergence speed of path planning.Then simulation experiments and field tests verify the more excellent performance of the LCPGA.This algorithm can be helpful in path planning for unmanned surface vessel.
Keywords:
本文引用格式
辛峻峰, 张永波, 伯佳更, 赵博文, 范世缘.
XIN Junfeng.
1 引言
人工智能就是让机器能够像人一样学习、思考并理解,即用计算机模拟人的智能,它涵盖认知与推理(包含各种物理常识和社会常识)、计算机视觉、自然语言理解与交互(包含听觉)、机器学习等广泛的学科领域。人机协同的混合增强智能是新一代人工智能的典型特征,当AI进入新的时代——后深度学习时代,各国都将处于同一起跑线上,谁能跑到最前面并引领AI的发展,完全取决于其创新能力,特别是原始创新能力[3,4],而USV 的主要配备系统包括运动控制系统、传感器系统、通信系统和武装系统。运动控制系统分为导航定位子系统、路径规划子系统和航迹跟踪子系统,其中路径规划子系统的路径规划算法是USV 研究的核心问题之一,代表无人艇的智能化水平。算法在智能控制中起着至关重要的作用,如基于 UWB 定位技术的多移动机器人编队控制算法能够使多机器人系统达成速度一致性,并且能够按照给定轨迹实现编队队形[5]。20 世纪中后期Holland和Bagley[6,7,8,9]提出的遗传算法直接对结构对象进行操作,不存在求导和函数连续性的限定,具有内在的隐并行性和更好的全局寻优能力,且该算法采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应调整搜索方向,不需要确定的规则,求解速度快、质量高,更适用于欠驱动无人艇的路径规划。但传统遗传算法存在收敛速度慢和种群早熟等问题。
针对上述缺点,本文在文献[6]的基础上不增加算法复杂度,提出了一种数据驱动线性遍历控制参数的遗传算法,继而通过蒙特·卡罗实验和现场试验对比改进算法与传统遗传算法,验证改进算法的优良性能。
2 遗传算法
2.1 传统遗传算法
图1
① 根据实际问题,确定实际问题的参数值,并确定所选用的编码方式;
② 在论域空间U上定义一个适应度函数f(x);
③ 给定种群规模N、交叉概率Pc和变异概率Pm等参数;
④ 随机产生U中的N个染色体组成初始种群,置代数计数器g=1;
⑤ 计算S中每个染色体的适应度f(x);
⑥ 根据遗传算法的方法(即选择、交叉、变异)生成下一代群体;
⑦ 如果生成的新群体满足某个性能指标,或者满足已经设定的代数规定,结束操作;否则返回第⑥步,重新进行选择、交叉、变异的操作。
利用传统遗传算法求解实际问题时,第③步的控制参数主要是凭经验给定的:种群大小N为20~100,交叉概率 Pc为 0.60~0.90,变异概率 Pm为0.001~0.01[9]。
2.2 改进的遗传算法
首先设定Pc和Pm的选取范围分别为0.9~0.1和0.001~0.1,继而使用式(1)逐步迭代线性更新Pc和Pm,随着迭代次数的增加,Pc从0.9线性递减到0.1,同时Pm从0.001线性递增到0.1。最终遍历更新获取全局最优值。
其中,Pce、Pcs分别是 Pc的终值和初值,Pme、Pms分别为Pm的终值和初值;gen是由0以1的步长逐渐递增的迭代次数;MAXGEN 是最大迭代次数。改进过程如图2所示。
理论上的改进使遗传算法具备了以下两个更优异的性能:
① 交叉概率Pc和变异概率Pm两个控制参数不再需要人为设定,避免了初始参数选择的盲目性;
② 随着待规划点矩阵维数的增加,交叉概率和变异概率两个参数的自适应线性变化组合在搜索初期使种群尽可能地扩大搜索空间以获取更多的信息便于自身做出相应的调整,从而增加群体的多样性,尽可能摆脱局部极值的干扰,提高传统遗传算法向全局最优点收敛的能力,提高算法的计算效率以及路径规划的稳健性。
图2
3 仿真实验
本节设置了5种工况,即分别随机选取10、20、30、40、50个待规划点,全面科学地对比改进算法与传统算法的性能。
3.1 对比方案一(路径规划长度和计算精度)
参数选定如下:传统遗传算法种群大小N设置为100,交叉概率Pc设置为0.9,变异概率Pm设置为0.1;改进遗传算法种群大小N同样设置为100,交叉概率Pc和变异概率Pm不需要设置(见表1)。
选定参数后分别进行蒙特·卡罗仿真实验获取两种算法的路径规划性能,实验结果如图3所示。
为了对比两种算法的稳健性,继续对比计算结果的离散情况(如图5所示),其方差如式(2)所示。
其中,σ2为总体方差,x为变量,μ为总体均值,N为总体例数。
从图5中可见:
① 当待规划点数<20个时,虚线和实线间的间隙比较小,说明两种算法的稳定性相差不大;
② 当待规划点数>20个时,虚线明显位于实线下方且两条线的间隙非常大,说明改进算法比传统算法稳定性强。
为更进一步验证传统算法和改进算法的优劣,表2展示了量化结果。
从表2可以更清晰地看到:
① 当待规划点数<20个时,两种算法的最短路径平均值相对误差最大仅为8.444%,相差不大,但方差却高达93.478%;
② 当待规划点数>20个时,两种算法规划的路径长度最大误差高达30.07%,方差的误差始终处于80%以上,改进算法的优势非常明显,显然改进算法更加可靠稳定。
总体上,改进算法不受规划点数的影响,有更好的性能。
3.2 对比方案二(计算效率)
本节将从计算时间和收敛速度两方面分别比对传统算法与改进算法的计算效率。
图4
3.2.1 计算时间对比
图6是5种工况下两种算法路径规划过程所消耗时间的对比结果,可以看出,实线明显高于虚线且间隙较大,说明改进算法的路径优化用时更短。
进一步用量化结果探究两种算法的差异,见表3。
由表3可以看出:改进算法在寻找最优解的过程中比传统方法节省了13.04%~20.874%的时间,而且随着待规划点数的增加,相对误差逐步增大,说明待规划点数越多,改进算法节省的时间越多,优势越明显。
图5
表2 结果对比
点数(个) | 平均值(m) | 方差(m2) | ||||
传统算法 | 改进算法 | 相对误差 | 传统算法 | 改进算法 | 相对误差 | |
10 | 2.705 | 2.705 | 0.000 | 0.000% | 0.000 | 0.000% |
20 | 4.879 | 4.467 | -8.444 | 0.092% | 0.006 | -93.478% |
30 | 6.198 | 5.223 | -15.73 | 0.166% | 0.031 | -81.325% |
40 | 7.598 | 5.937 | -21.86 | 0.312% | 0.035 | -88.782% |
50 | 8.414 | 5.884 | -30.07 | 0.491% | 0.054 | -89.002% |
注:相对误差=(改进算法-传统算法)/传统算法。
图6
表3 消耗时间对比
点数(个) | 传统算法(s) | 改进算法(s) | 相对误差 |
10 | 18.645 | 16.214 | -13.040% |
20 | 19.665 | 16.691 | -15.123% |
30 | 20.112 | 16.865 | -16.145% |
40 | 21.044 | 17.139 | -18.556% |
50 | 23.206 | 18.362 | -20.874% |
注:相对误差=(改进算法-传统算法)/传统算法。
3.2.2 收敛速度对比
图7所示为传统算法和改进算法单次计算的优化过程,随着迭代次数的增加,路径长度减小,曲线趋于水平并保持不变时即为找到最优解,该水平线对应的数值越小,寻优效果越好,找到最优解的最小迭代次数越小,收敛速度越快。
图7
综上,本节验证了改进算法无论是在消耗时间还是收敛速度的计算效率上都具有明显优势。
表4 最小迭代次数对比
点数(个) | 传统算法(次) | 改进算法(次) | 相对误差 |
10 | 52 | 20 | -61.538% |
20 | 83 | 62 | -25.301% |
30 | 98 | 154 | 57.143% |
40 | 723 | 386 | -46.611% |
50 | 869 | 587 | -32.451% |
注:相对误差=(改进算法-传统算法)/传统算法。
4 现场试验
本节将使用无人艇实船海上路径规划数据验证上文的分析结论。
4.1 试验设备
4.1.1 试验船型
本次海上实测使用的是实验室自主研发的新型智能五体无人艇,它配备一整套完整的电气控制系统,主要包括电源模块、检测单元、输出控制单元、存储单元、时间单元、通信和人机接口。其中,存储单元可实时存储无人舰艇 GPS 位置、航行日志、状态信息等;通信单元使用Wi-Fi通信和GPRS通信等多种可选通信方式,通信距离为5 km,传输速率为1~100 Mbit/s,实船如图8所示。
图8
4.1.2 试验数据采集仪器——多功能传感器
传感器采用英国 AIRMAR 多参数传感器,如图9所示。
图9
4.1.3 试验数据采集系统
图10
图11
4.2 数据采集
图12
4.3 实验对比
本节设置了3种工况,即随机选取10个、25个和35个待规划点,分别验证改进算法的性能优势。其中两种算法的参数选取方案为:传统遗传算法种群大小取100,交叉概率Pc设为0.9,变异概率Pm设为0.1;改进遗传算法种群大小取100,交叉概率Pc和变异概率Pm不需要设置。
4.3.1 对比方案一(10个待规划点)
选取10个待规划点,坐标见表6。
表6 待规划点坐标
坐标序号 | 纬度 | 经度 |
1 | N36°03′ 22.38′′ | E120°22′ 57.06′′ |
2 | N36°03′ 21.94′′ | E120°23′ 11.96′′ |
3 | N36°03′ 9.95′′ | E120°23′ 6.15′′ |
4 | N36°03′ 38.43′′ | E120°22′ 55.51′′ |
5 | N36°03′ 11.26′′ | E120°22′ 56.27′′ |
6 | N36°03′ 9.76′′ | E120°23′ 5.38′′ |
7 | N36°03′ 20.26′′ | E120°22′ 58.45′′ |
8 | N36°03′ 2.14′′ | E120°23′ 17.12′′ |
9 | N36°03′ 6.57′′ | E120°23′ 24.70′′ |
10 | N36°03′ 8.45′′ | E120°23′ 10.63′′ |
图 13 中,深蓝色线位于浅蓝色线的上方且深蓝色线出现的折点明显比浅蓝色线多,说明改进算法规划的路径更短且迭代次数更少、收敛速度更快。
图13
待规划点为 10 个时,传统算法和改进算法规划路径的轨迹如图14所示。
从统计结果(见表 7)可以更清晰地看出,改进算法规划的路径比传统算法规划的路径短2.631%,消耗时间少15.16%,验证了前文的研究结果。
图14
注:相对误差=(改进算法-传统算法)/传统算法。
4.3.2 对比方案二(25个待规划点)
选取的25个待规划点的坐标见表8。
表8 待规划点坐标
坐标序号 | 纬度 | 经度 |
1 | N36°03′22.38″ | E120°22′57.06″ |
2 | N36°03′21.94″ | E120°23′11.96″ |
3 | N36°03′9.95″ | E120°23′06.15″ |
4 | N36°03′38.43″ | E120°22′55.51″ |
5 | N36°03′11.26″ | E120°22′56.27″ |
6 | N36°03′09.76″ | E120°23′05.38″ |
7 | N36°03′20.26″ | E120°22′58.45″ |
8 | N36°03′02.14″ | E120°23′17.12″ |
9 | N36°03′06.57″ | E120°23′24.70″ |
10 | N36°03′08.45″ | E120°23′10.63″ |
11 | N36°03′12.20″ | E120°23′08.70″ |
12 | N36°03′11.14″ | E120°23′12.10″ |
13 | N36°03′09.95″ | E120°23′00.67″ |
14 | N36°03′27.69″ | E120°23′13.90″ |
15 | N36°03′17.70″ | E120°23′08.02″ |
16 | N36°03′16.82″ | E120°23′13.03″ |
17 | N36°03′16.26″ | E120°23′18.20″ |
18 | N36°03′31.62″ | E120°23′11.66″ |
19 | N36°03′25.82″ | E120°23′08.26″ |
20 | N36°03′15.32″ | E120°23′04.92″ |
21 | N36°03′44.86″ | E120°23′54.46″ |
22 | N36°03′28.53″ | E120°23′47.99″ |
23 | N36°03′24.43″ | E120°23′59.50″ |
24 | N36°03′27.32″ | E120°23′54.61″ |
25 | N36°03′24.44″ | E120°23′59.50″ |
图 15 中,浅蓝色线位于深蓝色线的下方且浅蓝色线达到水平明显比深蓝色线早得多,说明改进算法规划的路径更短且收敛时的迭代次数更少、收敛速度更快。
图15
待规划点为 25 个时,传统算法和改进算法规划路径的轨迹如图16所示。
图16
从统计结果(见表 9)可更清晰地看出,改进算法规划的路径比传统算法规划的路径短6.557%,消耗时间少12.779%。
注:相对误差=(改进算法-传统算法)/传统算法。
4.3.3 对比方案三(35个待规划点)
选取的35个待规划点的坐标见表10。
表10 待规划点坐标
坐标序号 | 纬度 | 经度 |
1 | N36°03′22.38″ | E120°22′57.06″ |
2 | N36°03′21.94″ | E120°23′11.96″ |
3 | N36°03′09.95″ | E120°23′06.15″ |
4 | N36°03′38.43″ | E120°22′55.51″ |
5 | N36°03′11.26″ | E120°22′56.27″ |
6 | N36°03′09.76″ | E120°23′05.38″ |
7 | N36°03′20.26″ | E120°22′58.45″ |
8 | N36°03′02.14″ | E120°23′17.12″ |
9 | N36°03′06.57″ | E120°23′24.70″ |
10 | N36°03′08.45″ | E120°23′10.63″ |
11 | N36°03′12.20″ | E120°23′08.70″ |
12 | N36°03′11.14″ | E120°23′12.10″ |
13 | N36°03′09.95″ | E120°23′00.67″ |
14 | N36°03′27.69″ | E120°23′13.90″ |
15 | N36°03′17.70″ | E120°23′08.02″ |
16 | N36°03′16.82″ | E120°23′13.03″ |
17 | N36°03′16.26″ | E120°23′18.20″ |
18 | N36°03′31.62″ | E120°23′11.66″ |
19 | N36°03′25.82″ | E120°23′08.26″ |
20 | N36°03′15.32″ | E120°23′04.92″ |
21 | N36°03′44.85" | E120°23′54.46" |
22 | N36°03′28.52" | E120°23′47.98" |
23 | N36°03′24.43" | E120°23′59.49" |
24 | N36°03′27.32" | E120°23′54.61" |
25 | N36°03′24.44" | E120°23′59.49" |
26 | N36°03′25.98" | E120°24′19.16" |
27 | N36°03′24.44" | E120°23′59.49" |
28 | N36°03′34.67" | E120°23′54.48" |
29 | N36°03′26.06" | E120°24′15.69" |
30 | N36°03′36.45" | E120°23′41.22" |
31 | N36°03′28.29" | E120°23′42.87" |
32 | N36°03′27.26" | E120°23′55.84" |
33 | N36°03′37.42" | E120°23′43.61" |
34 | N36°03′24.64" | E120°24′04.51" |
35 | N36°03′28.05" | E120°24′07.45" |
图 17 中,浅蓝色线位于深蓝色线的下方且浅蓝色线达到水平明显比深蓝色线早得多,说明改进算法规划的路径更短且收敛时的迭代次数更少、收敛速度更快。
图17
待规划点为 35 个时,传统算法和改进算法规划路径的轨迹如图18所示。
图18
从统计结果(见表11)可更清晰地看出,改进算法规划的路径比传统算法规划的路径短16.867%,消耗时间短7.635%。
综上,本节试验验证了改进算法不但规划的路径短而且计算效率更高。
5 结束语
本文针对传统遗传算法易早熟和全局收敛慢等不足,基于数据驱动控制参数线性动态遍历策略对其进行了改进,并通过蒙特·卡罗实验和现场试验验证了改进算法的优势:① 改进算法能在很大程度上避免早熟现象,且全局规划的路径更短,精度、稳健性更高,收敛速度更快;② 待规划点数越多,改进算法的坐标分布特征提取效率越高,优势越明显;③ 改进算法的控制参数自适应选定,操作更便捷,智能化程度更高,通用性和实用性更好,更适用于欠驱动无人艇的路径规划。
参考文献
Genetic algorithms in search,optimization and machine learning
[M].
Adaptive probabilities of crossover and mutation in genetic algorithms
[J]. ,
人工智能新时代
[J]. ,
The new era of artificial intelligence
[J].
人工智能进入后深度学习时代.智能科学与技术学报
[J].
Artificial intelligence is entering the post deep-learning era
[J].
基于 UWB 定位技术的多移动机器人编队控制.智能科学与技术学报
[J].
Formation control of mobile robots with UWB localization technology
[J].
A genetic algorithm for shortest path routing problem and the sizing of populations
[M].
Parallel elite genetic algorithm and its application to global path planning for autonomous robot navigation
[J]. ,
Dynamic path planning of mobile robots with improved genetic algorithm
[J]. ,
Genetic algorithm for dynamic path planning
[C]//
Unmanned surface vehicles,15 years of development
[C]//
Development of the USV multi-mission surface vehicle III
[C]//
Research on the path planning algorithm for the surface of the surface
[D]. ,
Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients
[J]. ,
Some common problems in the application of genetic algorithm
[J]. ,
Global path planning for autonomous mobile robot using genetic algorithm
[C]//
An effective initialization method for genetic algorithm-based robot path planning using a directed acyclic graph
[J]. ,
/
〈 | 〉 |