Show simple item record

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

dc.contributor.authorKapoutsis, Athanasios Ch.
dc.contributor.authorChatzichristofis, Savvas A.
dc.contributor.authorKosmatopoulos, Elias B.
dc.description.abstractThis 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
dc.relation.ispartofseriesJournal of Intelligent and Robotic Systems;Volume 86, Issue 3–4
dc.rights© Springer Science+Business Media Dordrecht 2017en_UK
dc.subjectComplete coverageen_UK
dc.subjectMinimum coverage pathsen_UK
dc.subjectTerrain sub-divisionen_UK
dc.titleDARP: Divide Areas Algorithm for Optimal Multi-Robot Coverage Path Planningen_UK

Files in this item


This item appears in the following Collection(s)

Show simple item record

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