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

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

系统工程与电子技术 ›› 2023, Vol. 45 ›› Issue (12): 3949-3957.doi: 10.12305/j.issn.1001-506X.2023.12.25

• 制导、导航与控制 • 上一篇

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

吴靖宇¹^,², 朱世强²^,³, 宋伟²^,³^,*, 施浩磊⁴, 吴泽南⁴

1. 浙江大学海洋学院, 浙江舟山 316021
2. 浙江大学机器人研究院, 浙江宁波 315400
3. 之江实验室, 浙江杭州 311121
4. 舟山市质量技术监督检测研究院, 浙江舟山 316013

收稿日期:2022-11-22 出版日期:2023-11-25 发布日期:2023-12-05
通讯作者: 宋伟
作者简介:吴靖宇 (1997—), 男, 硕士研究生, 主要研究方向为定位导航
朱世强 (1966—), 男, 教授, 博士, 主要研究方向为机械电子控制
宋伟 (1984—), 男, 副教授, 博士, 主要研究方向为壁面无人维护作业技术、非结构化环境自主决策技术
施浩磊 (1986—), 男, 高级工程师, 硕士, 主要研究方向为大宗油气计量测试、爬壁机器人装置及应用
吴泽南 (1989—), 男, 高级工程师, 本科, 主要研究方向为大宗油气计量测试、爬壁机器人装置及应用
基金资助:
浙江省市场监督管理局雏鹰计划培育项目(CY2022231)

Coverage path planning based on improved cellular decomposition

Jingyu WU¹^,², Shiqiang ZHU²^,³, Wei SONG²^,³^,*, Haolei SHI⁴, Zenan WU⁴

1. Ocean College, Zhejiang University, Zhoushan 316021, China
2. Robotics Institute, Zhejiang University, Ningbo 315400, China
3. Zhijiang Lab, Hangzhou 311121, China
4. Zhoushan Institute of Calibration and Testing for Qualitative and Technical Supervision, Zhoushan 316013, China

Received:2022-11-22 Online:2023-11-25 Published:2023-12-05
Contact: Wei SONG

摘要/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

中图分类号:

TP242

吴靖宇, 朱世强, 宋伟, 施浩磊, 吴泽南. 基于改进单元分解法的全覆盖路径规划[J]. 系统工程与电子技术, 2023, 45(12): 3949-3957.

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.

图/表 20

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

图11

图12

图13

图14

图15

图16

图17

图18

表1

表2

参考文献 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]	孙昱, 姚佩阳, 李明辉, 李凡. 兵力组织指挥控制结构适应性调整方法[J]. 系统工程与电子技术, 2016, 38(9): 2086-2092.
[2]	何志红, 李国君, 李曙光. 局部几乎正则多部竞赛图中的分量共轭圈[J]. Journal of Systems Engineering and Electronics, 2009, 31(10): 2513-2515.

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

Coverage path planning based on improved cellular decomposition

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 20

参考文献 31

相关文章 2

编辑推荐

Metrics

本文评价