考虑特殊区域的离散区域划分方法

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

Abstract

Abstract:

Based on the problem of area partitioning in multiple robot system area coverage, analyzing existing area coverage tasks, it is found that there are special areas or special areas with higher priority in the task area. A discrete area partitioning method based on Morse decomposition is designed for the case where special areas require the allocation of the least number of robots. The method uses radial Morse decomposition to define the spatial structure of discrete task areas and proposes an improved backtracking method to determine the optimal partitioning line, in order to avoid segmenting special areas and maintain workload balance among multiple robots. The simulation provides the results of region partitioning in scenarios with different distributions of special areas and different numbers of robots, and compares them with two existing algorithms. The results show that the proposed method can generate stable solutions, effectively reduce the partitioning of special regions, and allocate the workload of multiple robots reasonably.

Key words: multi-robot, area partitioning, special zone, Morse decomposition, backtracking method

CLC Number:

TP242

Chang CAI, Jianfeng CHEN, Qingli YAN, Fen LIU. Discrete area partitioning method considering special regions[J]. Systems Engineering and Electronics, 2024, 46(5): 1656-1664.

Figures/Tables 15

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Table 1

Fig.8

Fig.9

Fig.10

Table 2

Fig.11

Fig.12

Fig.13

References 29

1	李冠男, 董凌艳, 徐红丽, 等. 群机器人区域覆盖方法研究[J]. 机器人, 2017, 39 (5): 670- 679.
	LI G N , DONG L Y , XU H L , et al. Research on region coverage approach with swarm robots[J]. Robot, 2017, 39 (5): 670- 679.
2	YAO P , QIU L Y , QI J P , et al. AUV path planning for coverage search of static target in ocean environment[J]. Ocean Engineering, 2021, 241, 110050. doi: 10.1016/j.oceaneng.2021.110050
3	CHO S W , PARK H J , LEE H , et al. Coverage path planning for multiple unmanned aerial vehicles in maritime search and rescue operations[J]. Computers & Industrial Engineering, 2021, 161, 107612.
4	AI B , JIA M X , XU H W , et al. Coverage path planning for maritime search and rescue using reinforcement learning[J]. Ocean Engineering, 2021, 241, 110098. doi: 10.1016/j.oceaneng.2021.110098
5	WU C M , DAI C K , GONG X X , et al. Energy-efficient coverage path planning for general terrain surfaces[J]. IEEE Robotics and Automation Letters, 2019, 4 (3): 2584- 2591. doi: 10.1109/LRA.2019.2899920
6	POPOVICM , VIDAL-CALLEJA T , HITZ G , et al. An informative path planning framework for UAV-based terrain monitoring[J]. Autonomous Robots, 2020, 44 (6): 889- 911. doi: 10.1007/s10514-020-09903-2
7	KRISHNA L A , ELARA M R , RAMALINGAM B , et al. Complete coverage path planning using reinforcement learning for Tetromino based cleaning and maintenance robot[J]. Automation in Construction, 2020, 112, 103078. doi: 10.1016/j.autcon.2020.103078
8	VAZQUEZ-CARMONA E V , VASQUEZ-GOMEZ J I , HERRERA-LOZADA J C , et al. Coverage path planning for spraying drones[J]. Computers & Industrial Engineering, 2022, 168, 108125.
9	王伟, 张彦斐, 宫金良. 基于蚁群-BFS算法的复杂环境下农业机器人全区域覆盖研究[J]. 华南农业大学学报, 2019, 42 (3): 119- 125.
	WANG W , ZHANG Y F , GONG J L . Study on the whole area coverage of agricultural robot in complex environment based on ant colony-BFS algorithm[J]. Journal of South China Agricultural University, 2019, 42 (3): 119- 125.
10	NAIR V G , GURUPRASAD K R . MR-SimExCoverage: multi-robot simultaneous exploration and coverage[J]. Computers & Electrical Engineering, 2020, 85, 106680.
11	ALMADHOUN R , TAHA T , SENEVIRATNE L , et al. A survey on multi-robot coverage path planning for model reconstruction and mapping[J]. SN Applied Sciences, 2019, 1 (8): 847. doi: 10.1007/s42452-019-0872-y
12	李娟, 张秉健, 杨莉娟, 等. 未知环境下基于感知自适应的多AUV目标搜索算法[J]. 系统工程与电子技术, 2018, 40 (8): 1839- 1845.
	LI J , ZHANG B J , YANG L J , et al. Multi-AUV target search algorithm with cognitive-based adaptive optimization in unknown environment[J]. Systems Engineering and Electronics, 2018, 40 (8): 1839- 1845.
13	HASSAN M , LIU D . Simultaneous area partitioning and allocation for complete coverage by multiple autonomous industrial robots[J]. Autonomous Robots, 2017, 41 (8): 1609- 1628. doi: 10.1007/s10514-017-9631-3
14	NAIR V G , GURUPRASAD K R . GM-VPC: an algorithm for multi-robot coverage of known spaces using generalized voronoi partition[J]. Robotica, 2020, 38 (5): 845- 860. doi: 10.1017/S0263574719001127
15	VIET H H , DANG V , CHOI S , et al. BoB: an online coverage approach for multi-robot systems[J]. Applied Intelligence, 2015, 42 (2): 157- 173. doi: 10.1007/s10489-014-0571-8
16	KAPOUTSIS A C , CHATZICHRISTOFIS S A , KOSMATOPOULOS E B . DARP: divide areas algorithm for optimal multi-robot coverage path planning[J]. Journal of Intelligent & Robotic Systems, 2017, 86 (3/4): 663- 680. doi: 10.1007%2Fs10846-016-0461-x
17	BALAMPANIS F , MAZA I , OLLERO A . Area partition for coastal regions with multiple UAS[J]. Journal of Intelligent & Robotic Systems, 2017, 88 (2/4): 751- 766.
18	COOMBES M , FLETCHER T , CHEN W , et al. Optimal polygon decomposition for UAV survey coverage path planning in wind[J]. Sensors, 2018, 18 (7): 2132. doi: 10.3390/s18072132
19	KIM J . Multi-robot global sonar survey in the presence of strong currents[J]. Ocean Engineering, 2019, 188, 106316. doi: 10.1016/j.oceaneng.2019.106316
20	DONG W , LIU S S , DING Y , et al. An artificially weighted spanning tree coverage algorithm for decentralized flying robots[J]. IEEE Trans.on Automation Science and Engineering, 2020, 17 (4): 1689- 1698. doi: 10.1109/TASE.2020.2971324
21	GUASTELLA D C , CANTELLI L , GIAMMELLO G , et al. Complete coverage path planning for aerial vehicle flocks deployed in outdoor environments[J]. Computers & Electrical Engineering, 2019, 75, 189- 201.
22	SUN R C , TANG C H , ZHENG J Y , et al. Multi-robot path planning for complete coverage with genetic algorithms[M]. Cham: Springer International Publishing, 2019: 349- 361.
23	YEHOSHUA R , AGMON N , KAMINKA G A . Robotic adversarial coverage of known environments[J]. The International Journal of Robotics Research, 2016, 35 (12): 1419- 1444. doi: 10.1177/0278364915625785
24	魏潇龙, 姚登凯, 谷志鸣, 等. 基于分割法的无人机路径规划研究[J]. 计算机仿真, 2016, 33 (1): 90- 94.
	WEI X L , YAO D K , GU Z M , et al. UAV path planning method based on split method[J]. Computer Simulation, 2016, 33 (1): 90- 94.
25	ACAR E U , CHOSET H , RIZZI A A , et al. Morse decompositions for coverage tasks[J]. The International journal of robotics research, 2002, 21 (4): 331- 344. doi: 10.1177/027836402320556359
26	CAI C , CHEN J F , YAN Q L , et al. A multi-robot coverage path planning method for maritime search and rescue using multiple AUVs[J]. Remote Sensing, 2023, 15 (1): 93.
27	SERKAN G, VERONICA B, SALEH A. N-Queens solving algorithm by sets and backtracking[C]//Proc. of the Southeast Conference, 2016.
28	GLOCK S , MUNHA C D , SUDAKOV B . The N-Queens completion problem[J]. Research in the Mathematical Sciences, 2022, 9, 41. doi: 10.1007/s40687-022-00335-1
29	沈梦珠. 基于回溯法的扫地机器人全区域覆盖规划算法研究[D]. 武汉: 华中科技大学, 2018.
	SHEN M Z. Research on full coverage algorithm of sweeping robot path based on backtracking[D]. Wuhan: Huazhong University of Science & Technology, 2018.

NR	S	θ^*/(°)
3	{1, 2, 3}	{54.79, 75.82}
4	{1, 3, 4, 2}	{45.29, 60, 74.56}
5	{1, 4, 3, 2, 5}	{38.64, 58.20, 67.05, 79.11}
6	{1, 2, 5, 4, 3, 6}	{35.82, 57.69, 66.89, 77.99, 85.87}
7	{1, 2, 3, 4, 5, 6, 7}	{32.20, 53.69, 60, 70.33, 79.10, 83.02}
8	{2, 4, 5, 8, 7, 6, 3, 1}	{28.26, 49.84, 58.20, 66.89, 72.89, 76.39, 82.17}
9	{8, 4, 3, 5, 2, 6, 7, 1, 9}	{23.41, 43.89, 53.11, 60, 67.31, 70.44, 75.61, 82.95}
10	{2, 9, 10, 1, 4, 6, 3, 5, 8, 7}	{22.68, 42.51, 53.10, 60, 66.58, 68.94, 73.43, 79.10, 85.69}

NR	S	θ^*/(°)
3	{1, 2, 3}	{54.79, 75.82}
4	{1, 2, 4, 3}	{46.58, 65.81, 81.30}
5	{4, 3, 5, 2, 1}	{40.74, 56.02, 66.93, 79.70}
6	{1, 4, 5, 2, 3, 6}	{37.52, 57.64, 67.45, 78.90, 87.59}
7	{1, 5, 6, 2, 7, 3, 4}	{34.21, 52.65, 57.82, 67.73, 74.76, 81.64}
8	{3, 1, 5, 2, 4, 8, 7, 6}	{21.96, 44.66, 56.867, 65.35, 73.58, 82.06, 88.91}
9	{3, 1, 5, 6, 9, 2, 4, 8, 7}	{18.54, 40.55, 52.96, 57.10, 64.61, 71.69, 79.58, 86.91}
10	{1, 2, 3, 6, 9, 4, 8, 5, 10, 7}	{24.25, 43.09, 51.04, 55.38, 62.86, 68.85, 75.04, 81.15, 87.39}

[1]	WEI Heng, L Qiang, LIN Huican, ZHANG Yang, LIANG Jian. Survey on multi-robot SLAM back-end optimization algorithm [J]. Systems Engineering and Electronics, 2017, 39(11): 2553-2565.
[2]	Wu Xiao-lin, Song Meng, Yuan Jing, Sun Feng-chi, Tao Tong. Multi-robot active SLAM under limited communication range [J]. Journal of Systems Engineering and Electronics, 2012, 34(10): 2121-2128.
[3]	SU Hong-ming, CHEN Xiong, HAN Jian-da. Improved frontier-based exploration algorithm for multi-robot [J]. Journal of Systems Engineering and Electronics, 2009, 31(4): 901-904.

Discrete area partitioning method considering special regions

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 15

References 29

Related Articles 3

Recommended Articles

Metrics

Comments