基于置信椭圆的无人艇区域覆盖搜寻规划优化

doi:10.12305/j.issn.1001-506X.2022.07.22

摘要/Abstract

摘要：

为解决水上遇险目标搜寻存在搜寻区域过大、搜寻代价过高等问题, 提出一种基于置信椭圆的无人艇区域覆盖搜寻规划方法。首先, 利用高斯混合模型聚类算法划分搜寻区域, 再基于腐蚀膨胀的置信椭圆确定最佳搜寻区域边界, 实现目标包含概率和单位面积粒子数全局最优。然后, 构造适应椭圆搜寻区域边界特征的无人艇转向模型, 优化非工作路径。最后, 以搜寻探测概率和总路径为优化目标, 采用带精英策略的非支配排序的遗传算法(nondominated sorting genetic algorithm II, NSGA-II)优化得到最佳搜寻规划路径, 实现无人艇高效区域搜寻规划。与常规矩形区域覆盖搜寻规划对比, 能够在达到相同搜寻成功率下显著减少搜寻代价投入。

关键词: 无人艇, 非支配排序的遗传算法, 区域覆盖, 置信椭圆

Abstract:

To solve the issues of too-large search area and too-high search cost for distressed targets overboard, an unmanned surface vehicle(USV) area coverage path planning method based on confidence ellipsoid is proposed. Firstly, a Gaussian mixture model clustering algorithm is used to divide the search area. And then the optimal search area boundary is determined based on the confidence ellipsoid of corrosion expansion to achieve the global optimum of target containing probability and the number of particles per unit area. Then, the USVs steering model is built to adapt to the boundary characteristics of the ellipsoid search region, which could optimize the non-working distance. Finally, the nondominated sorting genetic algorithm II (NSGA-II) is used to optimize the optimal path planning with the target detection probability and total distance as the optimization objectives, which realizes the efficient area coverage path planning for USVs. Compared with conventional rectangular area coverage path planning methods, it can significantly reduce the search effort cost under the same successful searching probability.

Key words: unmanned surface vehicle (USV), nondominated sorting genetic algorithm II (NSGA-II), area coverage, confidence ellipsoid

中图分类号:

U676.8

杨少龙, 黄金, 向先波, 李伟超. 基于置信椭圆的无人艇区域覆盖搜寻规划优化[J]. 系统工程与电子技术, 2022, 44(7): 2263-2269.

Shaolong YANG, Jin HUANG, Xianbo XIANG, Weichao LI. Optimization of USV area coverage path planning based on confidence ellipsoid[J]. Systems Engineering and Electronics, 2022, 44(7): 2263-2269.

图/表 10

图1

图2

图3

图4

图5

图6

图7

图8

表1

图9

参考文献 33

1	AKBARI A , PELOT R , EISELT H A . A modular capacitated multi-objective model for locating maritime search and rescue vessels[J]. Annals of Operations Research, 2018, 267 (1): 3- 28.
2	BREIVIK Ø , ALLEN A A . An operational search and rescue model for the Norwegian Sea and the North Sea[J]. Journal of Marine Systems, 2008, 69 (1): 99- 113.
3	肖方兵. 海上搜救决策支持系统关键技术的研究[D]. 大连: 大连海事大学, 2011.
	XIAO F B. Research on the key technology of maritime search and rescue decision support system[D]. Dalian: Dalian Maritime University, 2011.
4	WAGNER W . A convergence proof for bird's direct simulation Monte Carlo method for the Boltzmann equation[J]. Journal of Statistical Physics, 1992, 66 (3): 1011- 1044.
5	MARTINS A, DIAS A, ALMEIDA J, et al. Field experiments for marine casualty detection with autonomous surface vehicles[C]//Proc. of the MTS/IEEE OCEANS, 2013.
6	江志. 基于群体智能算法的海上联合搜救[D]. 大连: 大连海事大学, 2020.
	JIANG Z. Joint maritime search and rescue based on group intelligence algorithm[D]. Dalian: Dalian Maritime University, 2020.
7	BOUZID Y, BESTAOUI Y, SIGUERDIDJANE H. Quadrotor-UAV optimal coverage path planning in cluttered environment with a limited onboard energy[C]//Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2017: 979-984.
8	QUERALTA J P, RAITOHARJU J, GIA T N, et al. AutoSOS: towards multi-UAV systems supporting maritime search and rescue with lightweight AI and edge computing[J]. [EB/OL]. [2021-06-15]. https://arXiv.org/abs/2005.03409.
9	李亚南, 黄海滨, 庄宇飞, 等. 基于分布式反集群算法的无人水面艇区域覆盖方法[J]. 导航与控制, 2019, 18 (1): 60- 67. doi: 10.3969/j.issn.1674-5558.2019.01.008
	LI Y N , HUANG H B , ZHUANG Y F , et al. Area coverage of unmanned surface vehicle usingdistributed anti-flocking algorithm[J]. Navigation and Control, 2019, 18 (1): 60- 67. doi: 10.3969/j.issn.1674-5558.2019.01.008
10	CHOSET H, PIGNON P. Coverage path planning: the boustrophedon cellular decomposition[M]//ZELINSKY A. Field and Service Robotics. London: Springer, 1998: 203-209.
11	LI B X, MORIDIAN B, MAHMOUDIAN N. Underwater multi-robot persistent area coverage mission planning[C]//Proc. of the MTS/IEEE OCEANS, 2016.
12	彭辉, 沈林成, 霍霄华. 多UAV协同区域覆盖搜索研究[J]. 系统仿真学报, 2007, 19 (11): 2472- 2476. doi: 10.3969/j.issn.1004-731X.2007.11.022
	PENG H , SHEN L C , HUO X H . Research on multiple UAV cooperative area coverage searching[J]. Journal of System Simulation, 2007, 19 (11): 2472- 2476. doi: 10.3969/j.issn.1004-731X.2007.11.022
13	MATOS A, SILVA E, CRUZ N, et al. Development of an unmanned capsule for large-scale maritime search and rescue[C]//Proc. of the OCEANS-San Diego, 2013.
14	FERNANDEZ-PENA E , CASTELLANO J , AMATORI S , et al. A directional ellipse to describe directional behavior and player activity area in soccer[J]. Journal of Sports Engineering and Technology, 2021, doi: 10.1177/17543371211024792
15	WANG H Y , TAN L , SHI J Q , et al. An improved NSGA-Ⅱ algorithm for UAV path planning problems[J]. Journal of Internet Technology, 2021, 22 (3): 583- 592.
16	DEB K , PRATAP A , AGARWAL S , et al. A fast and elitist multi objective genetic algorithm: NSGA-Ⅱ[J]. IEEE Trans.on Evolutionary Computation, 2002, 6 (2): 182- 197. doi: 10.1109/4235.996017
17	JORGE V A M , GRANADA R , MAIDANA R G , et al. A survey on unmanned surface vehicles for disaster robotics: main challenges and directions[J]. Sensors, 2019, 19 (3): 702. doi: 10.3390/s19030702
18	LIKAS A , VLASSIS N , J. VERBEEK J . The global k-means clustering algorithm[J]. Pattern Recognition, 2003, 36 (2): 451- 461. doi: 10.1016/S0031-3203(02)00060-2
19	LU Y K , TIAN Z , PENG P , et al. GMM clustering for heating load patterns in-depth identification and prediction model accuracy improvement of district heating system[J]. Energy and Buildings, 2019, 190, 49- 60. doi: 10.1016/j.enbuild.2019.02.014
20	BIERNACKI C , CELEUX G , GOVAERT G . Choosing starting values for the EM algorithm for getting the highest likelihood in multivariate Gaussian mixture models[J]. Computational Statistics & Data Analysis, 2003, 41 (3): 561- 575.
21	JEMAI J , ZEKRI M , MELLOULI K . An NSGA-Ⅱ algorithm for the green vehicle routing problem[M]. Berlin Heidelberg: Springer, 2012.
22	LIU Y , BUCKNALL R . Path planning algorithm for unmanned surface vehicle formations in a practical maritime environment[J]. Ocean Engineering, 2015, 97, 126- 144. doi: 10.1016/j.oceaneng.2015.01.008
23	MA Y H, ZHANG H, ZHANG Y Z, et al. Coordinated optimization algorithm combining GA with cluster for multi-UAVs to multi-tasks task assignment and path planning[C]//Proc. of the IEEE 15th International Conference on Control and Automation, 2019: 1026-1031.
24	WEI F. Research on three-dimensional cooperative formation of sea and air for cruise and rescue[C]//Proc. of the MATEC Web of Conferences, 2017: 04006.
25	DU Z , WEN Y Q , XIAO C S , et al. Trajectory-cell based method for the unmanned surface vehicle motion planning[J]. Applied Ocean Research, 2019, 86, 207- 221. doi: 10.1016/j.apor.2019.02.005
26	DU Z , WEN Y Q , XIAO C S , et al. Motion planning for unmanned surface vehicle based on trajectory unit[J]. Ocean Engineering, 2018, 151, 46- 56. doi: 10.1016/j.oceaneng.2017.12.062
27	万明, 代忠, 褚文奎. 无人机扫描线区域覆盖中的转弯航迹规划[J]. 系统工程与电子技术, 2014, 36 (9): 1750- 1754.
	WAN M , DAI Z , CHU W K . Turning path planning for UAV in region coverage with scanline[J]. Systems Engineering and Electronics, 2014, 36 (9): 1750- 1754.
28	PONNAMBALAM S G , JAGANNATHAN H , KATARIA M , et al. A TSP-GA multi-objective algorithm for flow-shop scheduling[J]. The International Journal of Advanced Manufacturing Technology, 2004, 23 (11): 909- 915.
29	李玉林. 大田作物机械化收运系统精益运作及关键问题研究[D]. 重庆: 重庆大学, 2015.
	LI Y L. Research on lean operation and key issues of mechanized crop harvesting-to-transport system[D]. Chongqing: Chongqing University, 2015.
30	赵德润. 无人船区域全覆盖路径规划与跟踪技术的研究[D]. 大连: 大连海事大学, 2020.
	ZHAO D R. Research on regional full-coverage path planning and tracking technology for unmanned vessels[D]. Dalian: Dalian Maritime University, 2020.
31	RAHMAN M M , ISHⅡ K , NOGUCHI N . Optimum harvesting area of convex and concave polygon field for path planning of robot combine harvester[J]. Intelligent Service Robotics, 2019, 12 (2): 167- 179. doi: 10.1007/s11370-018-00273-4
32	VAN VELDHUIZEN D A, LAMONT G B. Evolutionary computation and convergence to a pareto front[C]//Proc. of the Late Breaking Papers at the Genetic Programming Conference, 1998: 221-228.
33	HUANG W H. Optimal line-sweep-based decompositions for coverage algorithms[C]//Proc. of the IEEE International Conference on Robotics and Automation, 2001: 27-32.

区域类型	搜寻面积/(nmile)²	POD	POS	工作路径/nmile	总路径/nmile	遍历次序
椭圆区域	38.63	0.811	0.380	328.15	337.04	按序依次遍历
矩形区域	49.18	0.806	0.380	411.54	415.95	按序依次遍历

[1]	李文刚, 汪流江, 方德翔, 李玉玮, 黄郡. 联合A^*与动态窗口法的路径规划算法[J]. 系统工程与电子技术, 2021, 43(12): 3694-3702.
[2]	陈岱岱, 李玩幽. 带拖线阵的水面无人艇局部路径规划算法[J]. 系统工程与电子技术, 2020, 42(9): 1988-1994.
[3]	董蛟, 刘忠, 张建强, 陈霄, 周德超. 基于干扰观测的欠驱动无人艇自适应航迹跟踪控制算法[J]. 系统工程与电子技术, 2019, 41(7): 1606-1616.
[4]	庞强伟, 胡永江, 李文广. 基于垂直区域宽度分解的无人机覆盖航迹规划[J]. 系统工程与电子技术, 2019, 41(11): 2550-2558.
[5]	陈霄, 刘忠, 张建强, 董蛟. 基于非对称模型的欠驱动USV自适应路径跟踪控制[J]. 系统工程与电子技术, 2018, 40(1): 139-150.
[6]	万明，代忠，褚文奎. 无人机扫描线区域覆盖中的转弯航迹规划[J]. 系统工程与电子技术, 2014, 36(9): 1750-1754.
[7]	张汝波，邹启杰，杨歌，苏航. 不确定性下USV可变自主控制结构及算法[J]. 系统工程与电子技术, 2014, 36(1): 128-135.