Optimal Multirobot Coverage Path Planning: Ideal-Shaped Spanning Tree

Chunqing Gao, Yingxin Kou, Zhanwu Li, An Xu, You Li and Yizhe Chang

Mathematical Problems in Engineering, 2018, vol. 2018, 1-10

Abstract:

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.

Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2018/3436429.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2018/3436429.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:3436429

DOI: 10.1155/2018/3436429

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().