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

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

摘要/Abstract

摘要：

基于多机器人系统的区域覆盖中的区域划分问题, 分析现有区域覆盖任务发现, 在任务区域中存在危险区域或优先级更高的特殊区域。针对特殊区域需要分配给最少的机器人的情况, 设计了一种基于Morse分解的离散区域划分方法。该方法用放射状Morse分解来定义离散任务区域的空间结构, 并提出一种改进回溯法来确定最优分割线, 以避免分割特殊区域并保持多机器人工作量均衡。仿真给出了在特殊区域分布不同、机器人数量不同的场景下的区域划分结果, 并与两种现有算法进行了比较。结果表明, 所提方法能够生成稳定的解, 有效减少特殊区域的分割, 合理分配多机器人的工作量。

关键词: 多机器人, 区域划分, 特殊区域, Morse分解, 回溯法

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

中图分类号:

TP242

蔡畅, 陈建峰, 闫青丽, 刘芬. 考虑特殊区域的离散区域划分方法[J]. 系统工程与电子技术, 2024, 46(5): 1656-1664.

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.

图/表 15

图1

图2

图3

图4

图5

图6

图7

表1

图8

图9

图10

表2

图11

图12

图13

参考文献 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]	高春庆, 寇英信, 李战武, 徐安, 李游, 常一哲. 小型无人机协同覆盖侦察路径规划[J]. 系统工程与电子技术, 2019, 41(6): 1294-1299.
[2]	卫恒, 吕强, 林辉灿, 张洋, 梁建. 多机器人SLAM后端优化算法综述[J]. 系统工程与电子技术, 2017, 39(11): 2553-2565.
[3]	阮丽华, 李勇, 程伟. 一种空时二维联合频谱感知区域划分方案[J]. 系统工程与电子技术, 2016, 38(5): 1146-.
[4]	奔粤阳, 郭妍, 李敬春, 李倩, 霍亮. 基于联合分布状态信息滤波的机器人协同定位[J]. 系统工程与电子技术, 2015, 37(2): 385-393.
[5]	李京书，许江宁，何泓洋，查峰. 严格逆向过程的罗经回溯对准方法[J]. 系统工程与电子技术, 2014, 36(2): 348-353.
[6]	尹逊和, 樊雪丽, 张红. 基于异步动态的多机器人系统的一致性[J]. 系统工程与电子技术, 2014, 36(12): 2426-2434.
[7]	王晓文，赵宗贵，汤磊. 一种新的红外与可见光图像融合评价方法[J]. Journal of Systems Engineering and Electronics, 2012, 34(5): 871-875.
[8]	吴晓琳，宋萌，苑晶，孙凤池，陶通. 通讯范围受限条件下的多机器人主动SLAM[J]. Journal of Systems Engineering and Electronics, 2012, 34(10): 2121-2128.
[9]	苏鸿明, 陈雄, 韩建达. 多机器人的改进型边界探索算法[J]. Journal of Systems Engineering and Electronics, 2009, 31(4): 901-904.