# DARP: Divide Areas Algorithm for Optimal Multi-Robot Coverage Path Planning

 dc.contributor.author Kapoutsis, Athanasios Ch. dc.contributor.author Chatzichristofis, Savvas A. dc.contributor.author Kosmatopoulos, Elias B. dc.date.accessioned 2017-10-24T10:43:00Z dc.date.available 2017-10-24T10:43:00Z dc.date.issued 2017 dc.identifier.issn 0921-0296 dc.identifier.uri http://hdl.handle.net/11728/10138 dc.description.abstract This paper deals with the path planning problem of a team of mobile robots, in order to cover an area of interest, with prior-defined obstacles. For the single robot case, also known as single robot coverage path planning (CPP), an 𝓞(n) optimal methodology has already been proposed and evaluated in the literature, where n is the grid size. The majority of existing algorithms for the multi robot case (mCPP), utilize the aforementioned algorithm. Due to the complexity, however, of the mCPP, the best the existing mCPP algorithms can perform is at most 16 times the optimal solution, in terms of time needed for the robot team to accomplish the coverage task, while the time required for calculating the solution is polynomial. In the present paper, we propose a new algorithm which converges to the optimal solution, at least in cases where one exists. The proposed technique transforms the original integer programming problem (mCPP) into several single-robot problems (CPP), the solutions of which constitute the optimal mCPP solution, alleviating the original mCPP explosive combinatorial complexity. Although it is not possible to analytically derive bounds regarding the complexity of the proposed algorithm, extensive numerical analysis indicates that the complexity is bounded by polynomial curves for practical sized inputs. In the heart of the proposed approach lies the DARP algorithm, which divides the terrain into a number of equal areas each corresponding to a specific robot, so as to guarantee complete coverage, non-backtracking solution, minimum coverage path, while at the same time does not need any preparatory stage (video demonstration and standalone application are available on-line http://tinyurl.com/DARP-app). en_UK dc.language.iso en en_UK dc.publisher Springer en_UK dc.relation.ispartofseries Journal of Intelligent and Robotic Systems;Volume 86, Issue 3–4 dc.rights © Springer Science+Business Media Dordrecht 2017 en_UK dc.rights.uri http://creativecommons.org/licenses/by-nc-nd/4.0/ en_UK dc.subject mCPP en_UK dc.subject Multi-robots en_UK dc.subject Complete coverage en_UK dc.subject Minimum coverage paths en_UK dc.subject Terrain sub-division en_UK dc.title DARP: Divide Areas Algorithm for Optimal Multi-Robot Coverage Path Planning en_UK dc.type Article en_UK dc.doi 10.1007/s10846-016-0461-x en_UK
﻿

### This item appears in the following Collection(s)

• #### Articles69

Άρθρα
Except where otherwise noted, this item's license is described as © Springer Science+Business Media Dordrecht 2017