基于改进单元分解法的全覆盖路径规划

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

Abstract

Abstract:

When the traditional cellular decomposition method is used for complete coverage path planning in a static known environment, if the obstacles are irregularly distributed or many concave obstacles exist in the environment, the number of cells obtained is large. This finally leads to much redundancy and unnecessary steering in the final path. Firstly, the grid map is decomposed into several path segments, each of the path segment is composed of grids located in the same row and adjacent to the left and right. Secondly, these path fragment are merged for generating cells. Thirdly, based on greedy algorithm and topological map, the traversal order between cells is solved three times to merge and to reduce the number of cells, and the local path is optimized. Finally, the planning of traversal path is completed. Simulation results show that the algorithm is effective and the planned path has less redundancy and steering times.

Key words: complete coverage path planning, cellular decomposition, cellular mergence, greedy algorithm

CLC Number:

TP242

Jingyu WU, Shiqiang ZHU, Wei SONG, Haolei SHI, Zenan WU. Coverage path planning based on improved cellular decomposition[J]. Systems Engineering and Electronics, 2023, 45(12): 3949-3957.

Figures/Tables 20

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

Fig.11

Fig.12

Fig.13

Fig.14

Fig.15

Fig.16

Fig.17

Fig.18

Table 1

Table 2

References 31

1	伍跃飞, 李建微, 毕胜, 等. 面向山地徒步应急救援路径规划的改进蚁群算法研究[J]. 地球信息科学学报, 2023, 25 (1): 90- 101.
	WU Y F , LI J W , BI S , et al. Research on improved ant colony algorithm for mountain hiking emergency rescue path planning[J]. Journal of Geo-information Science, 2023, 25 (1): 90- 101.
2	HUANG G H , MA Q L . Research on path planning algorithm of autonomous vehicles based on improved RRT algorithm[J]. International Journal of Intelligent Transportation Systems Research, 2022, 20 (1): 170- 180. doi: 10.1007/s13177-021-00281-2
3	CUI J Y, WU D Q, MANSOUR R F. Research on EVRP of cold chain logistics distribution based on improved ant colony algorithm[C]// Proc. of the 8th International Conference on Artificial Intelligence and Security, 2022: 537-548.
4	HONG Z H , SUN P F , TONG X H , et al. Improved A-star algorithm for long-distance off-road path planning using terrain data map[J]. ISPRS International Journal of Geo-Information, 2021, 10 (11): 785. doi: 10.3390/ijgi10110785
5	ZHANG Y , LI L L , LIN H C , et al. Development of path planning approach using improved A-star algorithm in AGV system[J]. Journal of Internet Technology, 2019, 20 (3): 915- 924.
6	RASEKHIPOUR Y , KHAJEPOUR A , CHEN S K , et al. A potential field-based model predictive path-planning controller for autonomous road vehicles[J]. IEEE Trans.on Intelligent Transportation Systems, 2016, 18 (5): 1255- 1267.
7	WANG J , LI B , MENG Q H . Kinematic constrained bi-directional RRT with efficient branch pruning for robot path planning[J]. Expert Systems with Applications, 2021, 170, 114541. doi: 10.1016/j.eswa.2020.114541
8	PHAM H V , LAM T N . A new method using knowledge reasoning techniques for robot performance in coverage path planning[J]. International Journal of Computer Applications in Technology, 2019, 60 (1): 57- 64. doi: 10.1504/IJCAT.2019.099503
9	刘洋成, 耿端阳, 兰玉彬, 等. 基于自动导航的农业装备全覆盖路径规划研究进展[J]. 中国农机化学报, 2020, 41 (11): 185- 192. doi: 10.13733/j.jcam.issn.2095-5553.2020.11.028
	LIU Y C , GENG D Y , LAN Y B , et al. Research progress of agricultural equipment full coverage path planning based on automatic navigation[J]. Journal of Chinese Agricultural Mechanization, 2020, 41 (11): 185- 192. doi: 10.13733/j.jcam.issn.2095-5553.2020.11.028
10	代峰燕, 高庆珊, 陈家庆, 等. 储油罐清洗机器人全覆盖路径规划研究[J]. 机械设计与制造, 2020, 58 (2): 263- 266. doi: 10.19356/j.cnki.1001-3997.2020.02.066
	DAI F Y , GAO Q S , CHEN J Q , et al. Research of full covered path planning for oil tank cleaning robot[J]. Machinery Design and Manufacture, 2020, 58 (2): 263- 266. doi: 10.19356/j.cnki.1001-3997.2020.02.066
11	ZHU D Q , TIAN C , SUN B , et al. Complete coverage path planning of autonomous underwater vehicle based on GBNN algorithm[J]. Journal of Intelligent and Robotic Systems, 2019, 94 (1): 237- 249. doi: 10.1007/s10846-018-0787-7
12	ZHU D Q , ZHOU B , YANG S X . A novel algorithm of multi-AUVs task assignment and path planning based on biologically inspired neural network map[J]. IEEE Trans.on Intelligent Vehicles, 2021, 6 (2): 333- 342. doi: 10.1109/TIV.2020.3029369
13	VAN P H , ASADI F , ABUT N , et al. Hybrid spiral STC-hedge algebras model in knowledge reasonings for robot cove-rage path planning and its applications[J]. Applied Sciences, 2019, 9 (9): 1909. doi: 10.3390/app9091909
14	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
15	JANCHIV A , BATSAIKHAN D , KIM B S , et al. Time-efficient and complete coverage path planning based on flow networks for multi-robots[J]. International Journal of Control, Automation and Systems, 2013, 11 (2): 369- 376. doi: 10.1007/s12555-011-0184-5
16	胡诗宇. 清洁机器人的定位与全覆盖路径规划研究[D]. 南京: 东南大学, 2019.
	HU S Y. Research on the localization and full coverage path planning for a cleaning robot[D]. Nanjing: Southeast University, 2019.
17	GURUPRASAD K R , RANJITHA T D . CPC algorithm: extra area coverage by a mobile robot using approximate cellular decomposition[J]. Robotica, 2021, 39 (7): 1141- 1162. doi: 10.1017/S026357472000096X
18	LATOMBE J C . Exact cell decomposition robot motion planning[M]. Boston: Springer, 1991.
19	CHOSET H . Coverage of known spaces: the boustrophedon cellular decomposition[J]. Autonomous Robots, 2000, 9 (3): 247- 253. doi: 10.1023/A:1008958800904
20	张毅, 施明瑞. 基于单元分解的改进D^* lite路径规划算法[J]. 重庆邮电大学学报(自然科学版), 2021, 33 (6): 1007- 1013.
	ZHANG Y , SHI M R . Improved D^* lite path planning algorithm based on cell decomposition[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2021, 33 (6): 1007- 1013.
21	MISINO F. Development of a multi-UAS coverage planning algorithm based on the ant colony optimization[D]. Turin: Polytechnic University of Turin, 2022.
22	ACAR E U , CHOSET H , RIZZI A A , et al. Morse decompositions for coverage tasks[J]. International Journal of Robotics Research, 2002, 21 (4): 331- 344. doi: 10.1177/027836402320556359
23	HAN Y L , SHAO M , WU Y Z , et al. An improved complete coverage path planning method for intelligent agricultural machinery based on backtracking method[J]. Information, 2022, 13 (7): 313. doi: 10.3390/info13070313
24	TANG G , TANG C Q , ZHOU H , et al. R-DFS: a coverage path planning approach based on region optimal decomposition[J]. Remote Sensing, 2021, 13 (8): 1525. doi: 10.3390/rs13081525
25	KHOSRAVANI M E , VAHDANJOO M , JENSEN A L , et al. An arable field for benchmarking of metaheuristic algorithms for capacitated coverage path planning problems[J]. Agronomy, 2020, 10 (10): 1454. doi: 10.3390/agronomy10101454
26	MAJEED A , LEE S . A new coverage flight path planning algorithm based on footprint sweep fitting for unmanned aerial vehicle navigation in urban environments[J]. Applied Sciences, 2019, 9 (7): 1470. doi: 10.3390/app9071470
27	PHUNG M D , QUACH C H , DINH T H , et al. Enhanced discrete particle swarm optimization path planning for UAV vision-based surface inspection[J]. Automation in Construction, 2017, 81, 25- 33. doi: 10.1016/j.autcon.2017.04.013
28	SHIVGAN R, DONG Z. Energy-efficient drone coverage path planning using genetic algorithm[C]//Proc. of the IEEE 21st International Conference on High Performance Switching and Routing, 2020.
29	LE A V , ARUNMOZHI M , VEERAJAGADHESWAR P , et al. Complete path planning for a tetris-inspired self-reconfigurable robot by the genetic algorithm of the traveling salesman problem[J]. Electronics, 2018, 7 (12): 344. doi: 10.3390/electronics7120344
30	LAKSHMANAN A K , MOHAN R E , 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
31	KYAW P T , PAING A , THU T T , et al. Coverage path planning for decomposition reconfigurable grid-maps using deep reinforcement learning based travelling salesman problem[J]. IEEE Access, 2020, 8, 225945- 225956. doi: 10.1109/ACCESS.2020.3045027

算法	单元数量/个	路径长度/个	路径重复率/%	转向/次	等效路径长度/个
本文算法	37, 25, 24	1 366	8.07	306	1 978
Boustrophedon 分解+贪心算法	37	1 446	14.40	338	2 122
Boustrophedon 分解+遗传算法	37	1 487	17.64	350	2 187
生物激励神经网络算法	-	1 461	15.59	434	2 329

算法	单元数量/个	路径长度/个	路径重复率/%	转向/次	等效路径长度/个
本文算法	47, 31, 31	1 457	13.39	334	2 125
Boustrophedon 分解+贪心算法	39	1 678	30.58	394	2 466
Boustrophedon 分解+遗传算法	39	1 614	25.60	388	2 390
生物激励神经网络算法	-	1 669	29.88	512	2 693

[1]	Jie HU, Fan BAO, Xiaozhu SHI. Airport gate assignment strategy based on greedy-genetic algorithm [J]. Systems Engineering and Electronics, 2023, 45(11): 3555-3564.
[2]	SUN Yu, YAO Pei-yang, LI Ming-hui, LI Fan. Adaptive adjusting method of command and control structure of army organization [J]. Systems Engineering and Electronics, 2016, 38(9): 2086-2092.
[3]	CHEN Pan, WU Xiao-feng, CHEN Yun. Method of call search for Markovian motion targets using UUV cooperation [J]. Journal of Systems Engineering and Electronics, 2012, 34(8): 1630-1634.
[4]	LI Yi-bing, ZHANG Xu, YE Fang, GAO Zhen-guo. Adjustable fairness dynamic subcarrier allocation algorithm for SC-FMDA systems [J]. Journal of Systems Engineering and Electronics, 2011, 33(6): 1377-1382.
[5]	HE Zhi-hong, LI Guo-jun, LI Shu-guang. Componentwise complementary cycles in locally almost regular multipartite tournaments [J]. Journal of Systems Engineering and Electronics, 2009, 31(10): 2513-2515.

Coverage path planning based on improved cellular decomposition

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 20

References 31

Related Articles 5

Recommended Articles

Metrics

Comments