Coverage path planning considering the cell number and starting position
The coverage tasks of mobile robots are evolving towards large-scale and intelligent directions, demanding urgent requirements for the coverage efficiency and environmental adaptability of coverage path planning. To address the inadequate adaptability of the traditional boustrophedon cellular decomp...
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | zho |
| Published: |
Editorial Office of Journal of XPU
2024-08-01
|
| Series: | Xi'an Gongcheng Daxue xuebao |
| Subjects: | |
| Online Access: | http://journal.xpu.edu.cn/en/#/digest?ArticleID=1477 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849727326714068992 |
|---|---|
| author | MA Mingyan HUANG Sirong DENG Renhui WU Lei HE Li |
| author_facet | MA Mingyan HUANG Sirong DENG Renhui WU Lei HE Li |
| author_sort | MA Mingyan |
| collection | DOAJ |
| description | The coverage tasks of mobile robots are evolving towards large-scale and intelligent directions, demanding urgent requirements for the coverage efficiency and environmental adaptability of coverage path planning. To address the inadequate adaptability of the traditional boustrophedon cellular decomposition in complex maps and to improve coverage efficiency, a complete coverage path planning method is proposed. Firstly, based on the boustrophedon cellular decomposition method, a strategy of area-descending traversal and monotone polygon judgment was proposed to merge cells, reducing approximately half of the cell quantity. Finally, by establishing the mapping relationship between the starting and ending positions of cells, a genetic algorithm was employed to optimize the selection of cells′ starting positions and the global access order. The research results show that: 1) when processing maps with dimensions of 1 300 pixels, the algorithm in this paper can obtain calculation results within 10 s, and compared with the boustrophedon method, neural network method, and contour line method, the growth rate of calculation time is smaller with the increase of map area; 2) compared with the boustrophedon method, contour line method, neural network method, and energy-optimal method, the total operation time of robots in this paper is reduced by 5.4% to 47.0%, and the ineffective operation time is reduced by 5.8% to 29.2%; 3) the average coverage rate of this algorithm on 1 800 test maps reaches 99.91%; 4) the tests further confirm the significant coverage efficiency advantages of the algorithm proposed in this paper. |
| format | Article |
| id | doaj-art-e56a293c8f5d4db3a2974dc9bf552310 |
| institution | DOAJ |
| issn | 1674-649X |
| language | zho |
| publishDate | 2024-08-01 |
| publisher | Editorial Office of Journal of XPU |
| record_format | Article |
| series | Xi'an Gongcheng Daxue xuebao |
| spelling | doaj-art-e56a293c8f5d4db3a2974dc9bf5523102025-08-20T03:09:52ZzhoEditorial Office of Journal of XPUXi'an Gongcheng Daxue xuebao1674-649X2024-08-013841810.13338/j.issn.1674-649x.2024.04.001Coverage path planning considering the cell number and starting positionMA Mingyan0HUANG Sirong1DENG Renhui2WU Lei3HE Li4School of Mechatronic Engineering, Guangdong University of Technology, Guangzhou 510006, ChinaSchool of Mechatronic Engineering, Guangdong University of Technology, Guangzhou 510006, ChinaSchool of Mechatronic Engineering, Guangdong University of Technology, Guangzhou 510006, ChinaChina Electronic Product Reliability and Environmental Testing Research Institute, Guangzhou 511370, ChinaDepartment of Electronic and Electrical Engineering, Southern University of Science and Technology, Shenzhen 518055, Guangdong, ChinaThe coverage tasks of mobile robots are evolving towards large-scale and intelligent directions, demanding urgent requirements for the coverage efficiency and environmental adaptability of coverage path planning. To address the inadequate adaptability of the traditional boustrophedon cellular decomposition in complex maps and to improve coverage efficiency, a complete coverage path planning method is proposed. Firstly, based on the boustrophedon cellular decomposition method, a strategy of area-descending traversal and monotone polygon judgment was proposed to merge cells, reducing approximately half of the cell quantity. Finally, by establishing the mapping relationship between the starting and ending positions of cells, a genetic algorithm was employed to optimize the selection of cells′ starting positions and the global access order. The research results show that: 1) when processing maps with dimensions of 1 300 pixels, the algorithm in this paper can obtain calculation results within 10 s, and compared with the boustrophedon method, neural network method, and contour line method, the growth rate of calculation time is smaller with the increase of map area; 2) compared with the boustrophedon method, contour line method, neural network method, and energy-optimal method, the total operation time of robots in this paper is reduced by 5.4% to 47.0%, and the ineffective operation time is reduced by 5.8% to 29.2%; 3) the average coverage rate of this algorithm on 1 800 test maps reaches 99.91%; 4) the tests further confirm the significant coverage efficiency advantages of the algorithm proposed in this paper.http://journal.xpu.edu.cn/en/#/digest?ArticleID=1477coverage path planningcellular decomposition methodgenetic algorithmmonotonic polygonstarting position optimization |
| spellingShingle | MA Mingyan HUANG Sirong DENG Renhui WU Lei HE Li Coverage path planning considering the cell number and starting position Xi'an Gongcheng Daxue xuebao coverage path planning cellular decomposition method genetic algorithm monotonic polygon starting position optimization |
| title | Coverage path planning considering the cell number and starting position |
| title_full | Coverage path planning considering the cell number and starting position |
| title_fullStr | Coverage path planning considering the cell number and starting position |
| title_full_unstemmed | Coverage path planning considering the cell number and starting position |
| title_short | Coverage path planning considering the cell number and starting position |
| title_sort | coverage path planning considering the cell number and starting position |
| topic | coverage path planning cellular decomposition method genetic algorithm monotonic polygon starting position optimization |
| url | http://journal.xpu.edu.cn/en/#/digest?ArticleID=1477 |
| work_keys_str_mv | AT mamingyan coveragepathplanningconsideringthecellnumberandstartingposition AT huangsirong coveragepathplanningconsideringthecellnumberandstartingposition AT dengrenhui coveragepathplanningconsideringthecellnumberandstartingposition AT wulei coveragepathplanningconsideringthecellnumberandstartingposition AT heli coveragepathplanningconsideringthecellnumberandstartingposition |