Distributed collaborative complete coverage path planning based on hybrid strategy

doi:10.23919/JSEE.2023.000118

Journal of Systems Engineering and Electronics ›› 2024, Vol. 35 ›› Issue (2): 463-472.doi: 10.23919/JSEE.2023.000118

• CONTROL THEORY AND APPLICATION • Previous Articles

Distributed collaborative complete coverage path planning based on hybrid strategy

Jia ZHANG¹^,²(), Xin DU¹^,²(), Qichen DONG¹^,²(), Bin XIN¹^,²^,*()

¹ School of Automation, Beijing Institute of Technology, Beijing 100081, China
² National Key Laboratory of Autonomous Intelligent Unmanned Systems, Beijing Institute of Technology, Beijing 100081, China

Received:2022-03-01 Online:2024-04-18 Published:2024-04-18
Contact: Bin XIN E-mail:zhangjia@bit.edu.cn;duxin_bit@163.com;dqc2416230654@163.com;brucebin@bit.edu.cn
About author:
ZHANG Jia was born in 1980. She received her Ph. D. degree from Beijing Institute of Technology in 2015. She is a senior experimentalist in Beijing Institute of Technology. Her research interests are multi-agent system and intelligent information processing. E-mail: zhangjia@bit.edu.cn

DU Xin was born in 1996. He received his M.S. degree from Beijing Institute of Technology in 2021. He is an engineer in China Aerospace Science and Industry Group now. His research interests are intelligence optimization algorithm, multi-agent system, and task planning method. E-mail: duxin_bit@163.com

DONG Qichen was born in 1998. He received his B.S. degree from Beijing Institute of Technology, Beijing, China in 2020. He is currently pursuing his M.E. degree in pattern recognition and intelligent system in Beijing Institute of Technology. His research interests are distributed multi-agent system, task assignment, and path planning. E-mail: dqc2416230654@163.com

XIN Bin was born in 1982. He received his Ph. D. degree from Beijing Institute of Technology in 2012. He is a professor in Beijing Institute of Technology. His research interests are multi-agent collaboration and intelligent optimization. E-mail: brucebin@bit.edu.cn
Supported by:
This work was supported by the National Natural Science Foundation of China (61903036, 61822304) and Shanghai Municipal Science and Technology Major Project (2021SHZDZX0100).

Abstract

Abstract:

Collaborative coverage path planning (CCPP) refers to obtaining the shortest paths passing over all places except obstacles in a certain area or space. A multi-unmanned aerial vehicle (UAV) collaborative CCPP algorithm is proposed for the urban rescue search or military search in outdoor environment. Due to flexible control of small UAVs, it can be considered that all UAVs fly at the same altitude, that is, they perform search tasks on a two-dimensional plane. Based on the agents’ motion characteristics and environmental information, a mathematical model of CCPP problem is established. The minimum time for UAVs to complete the CCPP is the objective function, and complete coverage constraint, no-fly constraint, collision avoidance constraint, and communication constraint are considered. Four motion strategies and two communication strategies are designed. Then a distributed CCPP algorithm is designed based on hybrid strategies. Simulation results compared with pattern-based genetic algorithm (PBGA) and random search method show that the proposed method has stronger real-time performance and better scalability and can complete the complete CCPP task more efficiently and stably.

Key words: multi-agent cooperation, unmanned aerial vehicles (UAV), distributed algorithm, complete coverage path planning (CCPP)

Jia ZHANG, Xin DU, Qichen DONG, Bin XIN. Distributed collaborative complete coverage path planning based on hybrid strategy[J]. Journal of Systems Engineering and Electronics, 2024, 35(2): 463-472.

Figures/Tables 15

Fig 1

Fig 2

Fig 3

Fig 4

Fig 5

Fig 6

Fig 7

Fig 8

Fig 9

Fig 10

Table 1

Fig 11

Table 2

Table 3

Fig 12

References 22

1	XU Z, ZHANG E Z, CHEN Q W Rotary unmanned aerial vehicles path planning in rough terrain based on multi-objective particle swarm optimization. Journal of Systems Engineering and Electronics, 2021, 32 (6): 1450- 1462. doi: 10.23919/JSEE.2021.000123
2	QIN H L, MENG Z H, MENG W, et al Autonomous exploration and mapping system using heterogeneous UAVs and UGVs in GPS-denied environments. IEEE Trans. on Vehicular Technology, 2018, 68 (2): 1339- 1350.
3	LI J J, CHENG Y Y, ZHOU J, et al Energy-efficient ground traversability mapping based on UAV-UGV collaborative system. IEEE Trans. on Green Communications and Networking, 2021, 6 (1): 69- 78.
4	CANTELLI L, PRESTI M L, MANGIAMELI M, et al. Autonomous cooperation between UAV and UGV to improve navigation and environmental monitoring in rough environments. Proc. of the 10th International Symposium Humanitarian Demining, 2013.
5	LIU Y, LUO Z H, LIU Z, et al Cooperative routing problem for ground vehicle and unmanned aerial vehicle: the application on intelligence, surveillance and reconnaissance missions. IEEE Access, 2019, 7, 63504- 63518. doi: 10.1109/ACCESS.2019.2914352
6	HABIB M K, BAUDOIN Y. Robot-assisted risky intervention, search, rescue and environmental surveillance. International Journal of Advanced Robotic Systems, 2010, 7(1): 1−8.
7	HAKUKAWA T, UCHIYAMA K, KAI M. Cooperative system with UAV and UGV for disaster area exploration. Proc. of the 7th International conference on Systems and Control, 2018: 117−122.
8	TOKEKAR P, HOOK J V, MULLA D, et al Sensor planning for a symbiotic UAV and UGV system for precision agriculture. IEEE Trans. on Robotics, 2016, 32 (6): 1498- 1511. doi: 10.1109/TRO.2016.2603528
9	CONESA-MUNOZ J, BENGOCHEA-GUEVARA J M, ANDUJAR D, et al. Efficient distribution of a fleet of heterogeneous vehicles in agriculture: a practical approach to multi-path planning. Proc. of the IEEE International Conference on Autonomous Robot Systems and Competitions, 2015: 56−61.
10	ZHU D Q, TIAN C, SUN B, et al Complete coverage path planning of autonomous underwater vehicle based on GBNN algorithm. Journal of Intelligent & Robotic Systems, 2019, 91 (1): 237- 249.
11	DRISCOLL T M. Complete coverage path planning in an agricultural environment. Ames: Iowa State University, 2011.
12	SHIVASHANKAR V, JAIN R, KUTER U, et al. Real-time planning for covering an initially-unknown spatial environment. Proc. of the 24th International Florida Artificial Intelligence Research Society Conference, 2011: 63−68.
13	WOLEC A, CHENG S, GOSWAMI D, et al Cooperative mapping and target search over an unknown occupancy graph using mutual information. IEEE Robotics and Automation Letters, 2019, 5 (2): 1071- 1078.
14	ZHOU P, WANG Z M, LI Z N. Complete coverage path planning of mobile robot based on dynamic programming algorithm. Proc. of the 2nd International Conference on Electronic and Mechanical Engineering and Information Technology, 2012: 1837−1841.
15	PHAM H V, ASADI F, ABUT N, et al Hybrid spiral STChedge algebras model in knowledge reasonings for robot coverage path planning and its applications. Applied Sciences, 2019, 9 (9): 1909- 1925. doi: 10.3390/app9091909
16	PINKAM N, NEWAZ A, JEONG S Rapid coverage of regions of interest for environmental monitoring. Intelligent Service Robotics, 2019, 12 (4): 393- 406. doi: 10.1007/s11370-019-00290-x
17	CHOI Y, CHOI Y, BRICENO S, et al Energy-constrained multi-UAV coverage path planning for an aerial imagery mission using column generation. Journal of Intelligent and Robotic Systems, 2019, 97, 125- 139.
18	HAZON N, KAMINKA G A On redundancy, efficiency, and robustness in coverage for multiple robots. Robotics and Autonomous Systems, 2008, 56 (12): 1102- 1114. doi: 10.1016/j.robot.2008.01.006
19	YANG J, LIU H, YANG X K, et al Path planning of mobile robot based on genetic algorithm. Mechanical & Electrical Engineering Technology, 2020, 49 (12): 97- 117.
20	GUO X H, JI M J, ZHAO Z W, et al Global path planning and multi-objective path control for unmanned surface vehicle based on modified particle swarm optimization (PSO) algorithm. Ocean Engineering, 2020, 216 (1): 321- 342.
21	YAN Y, FU K C, JIANG T, et al AGV path planned with heuristic RRT. Computer Engineering and Applications, 2020, 56 (12): 125- 133.
22	XU M, XIN B, DOU L H, et al. Potential and motion pattern driven multi-robot coverage path planning algorithm. Proc. of the 14th International Conference on Bio inspired Computing: Theories and Applications, 2019: 468−483.

Method	Name	Framework
1	CCPP based on hybrid strategy	Distributed
2	PBGA [2]	Centralized
3	Random search algorithm	Distributed

Environment	Raster number	UAV number	Method 1		Method 2		Method 3
Environment	Raster number	UAV number	t/min	cr/%	t/min	cr/%	t/min	cr/%
Map 1	65×35	2	442.1	100	432.3	100	492.3	96
		3	291.15	100	296.4	100	324.5	96
		4	222.7	100	231.4	100	234.4	96
		5	177.4	100	171.3	100	201.3	96
Map 2	52×28	2	392.9	100	381.2	100	443.4	96
		3	220.3	100	205.4	100	245.7	96
		4	162.4	100	183.2	100	185.4	96
		5	123.6	100	132.3	100	162.4	96
Map 3	65×35	2	411.7	100	401.1	100	453.9	96
		3	291.5	100	304.2	100	353.2	96
		4	213.5	100	224.3	100	276.4	96
		5	169.1	100	151.2	100	201.3	96
Map 4	50×35	2	295.2	100	260.1	100	335.3	96
		3	205.0	100	201.3	100	232.3	96
		4	156.3	100	145.4	100	223.5	96
		5	125.5	100	167.4	100	156.9	96

Length/km	Width/km	Number of grids	Number of grids to be searched	Search radius/m	Number of UAVs	Coverage time/min
15	10	2560	2169	250	2	626.85
					3	423.23
					4	330.32
					5	257.65
					6	210.43
					7	180.00
					8	159.83
					9	146.15
18	12	5400	4975	200	2	1160.45
					3	814.82
					4	637.45
					5	498.54
					6	400.70
					7	337.92
					8	295.41
					9	268.32

[1]	Ronghua ZHOU, Hemin SUN, Hao LI, Weilin LUO. TDOA and track optimization of UAV swarm based on D-optimality [J]. Journal of Systems Engineering and Electronics, 2020, 31(6): 1140-1151.
[2]	Cui Xunxue, Shan Zhiguan & Liu Jianjun. Distributed localization for anchor-free sensor networks [J]. Journal of Systems Engineering and Electronics, 2008, 19(3): 405-418.

Distributed collaborative complete coverage path planning based on hybrid strategy

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 15

References 22

Related Articles 2

Recommended Articles

Metrics

Comments