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

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

Abstract

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

CLC Number:

U676.8

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.

Figures/Tables 10

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Table 1

Fig.9

References 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]	PANG Qiangwei, HU Yongjiang, LI Wenguang. UAV coverage track planning based on decomposition along the direction of perpendicular to the width of the area [J]. Systems Engineering and Electronics, 2019, 41(11): 2550-2558.
[2]	ZHANG Ru-bo，ZOU Qi-jie，YANG Ge，SU Hang. Adaptive autonomy control structure and algorithm for USV under uncertainty [J]. Systems Engineering and Electronics, 2014, 36(1): 128-135.

Optimization of USV area coverage path planning based on confidence ellipsoid

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 33

Related Articles 2

Recommended Articles

Metrics

Comments