Optimal Multirobot Coverage Path Planning: Ideal-Shaped Spanning Tree
Joint Authors
Li, You
Kou, Yingxin
Li, Zhanwu
Xu, An
Chang, Yizhe
Gao, Chunqing
Source
Mathematical Problems in Engineering
Issue
Vol. 2018, Issue 2018 (31 Dec. 2018), pp.1-10, 10 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2018-09-25
Country of Publication
Egypt
No. of Pages
10
Main Subjects
Abstract EN
The present paper attempts to find the optimal coverage path for multiple robots in a given area including obstacles.
For single robot coverage path planning (CPP) problem, an improved ant colony optimization (ACO) algorithm is proposed to construct the best spanning tree and then obtain the optimal path, which contributes to minimizing the energy/time consumption.
For the multirobot case, first the DARP (Divide Areas based on Robots Initial Positions) algorithm is utilized to divide the area into separate equal subareas, so much so that it transforms the mCPP problem into several CPP problems, degrading the computation complexity.
During the second phase, spanning tree in each subarea is constructed by the aforementioned algorithm.
In the last phase, the specific end nodes are exchanged among subareas to achieve ideal-shaped spanning trees, which can also decrease the number of turns in coverage path.
And the complete algorithms are proven to be approximately polynomial algorithms.
Finally, the simulation confirms the complete algorithms’ advantages: complete coverage, nonbacktracks, minimum length, zero preparation time, and the least number of turns.
American Psychological Association (APA)
Gao, Chunqing& Kou, Yingxin& Li, Zhanwu& Xu, An& Li, You& Chang, Yizhe. 2018. Optimal Multirobot Coverage Path Planning: Ideal-Shaped Spanning Tree. Mathematical Problems in Engineering،Vol. 2018, no. 2018, pp.1-10.
https://search.emarefa.net/detail/BIM-1206817
Modern Language Association (MLA)
Gao, Chunqing…[et al.]. Optimal Multirobot Coverage Path Planning: Ideal-Shaped Spanning Tree. Mathematical Problems in Engineering No. 2018 (2018), pp.1-10.
https://search.emarefa.net/detail/BIM-1206817
American Medical Association (AMA)
Gao, Chunqing& Kou, Yingxin& Li, Zhanwu& Xu, An& Li, You& Chang, Yizhe. Optimal Multirobot Coverage Path Planning: Ideal-Shaped Spanning Tree. Mathematical Problems in Engineering. 2018. Vol. 2018, no. 2018, pp.1-10.
https://search.emarefa.net/detail/BIM-1206817
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1206817