A Divide and Conquer Strategy for Sweeping Coverage Path Planning

Juan Irving Vasquez and Emmanuel Alejandro Merchán-Cruz ()
Additional contact information
Juan Irving Vasquez: Instituto Politécnico Nacional, Centro de Innovación y Desarrollo Tecnológico en Cómputo, Ciudad de México 07700, Mexico
Emmanuel Alejandro Merchán-Cruz: SIA Robotic Solutions, LV-1039 Riga, Latvia

Energies, 2022, vol. 15, issue 21, 1-15

Abstract: One of the main challenges faced by floor treatment service robots is to compute optimal paths that completely cover a set of target areas. Short paths are of noticeable importance because their length is directly proportional to the energy used by the robot. Such a problem is known to be NP-hard; therefore, efficient algorithms are needed. In particular, computation efficiency is important for mobile robots with limited onboard computation capability. The general problem is known as coverage path planning (CPP). The CPP has several variants for single regions and for disjoint regions. In this research, we are investigating the solutions for disjoint target regions (rooms) that have fixed connection points (doors). In particular, we have found effective simplifications for the cases of rooms with one and two doors, while the challenging case of an unbounded number of rooms can be solved by approximation. As a result, this work presents a divide and conquer strategy (DnCS) to address the problem of finding a path for a sweeping robot that needs to sweep a set of disjoint rooms that are connected by fixed doors and corridors. The strategy divides the problem into computing the sweeping paths for the target rooms and then merges those paths into one solution by optimising the room visiting order. In this strategy, a geometrical approach for room coverage and an undirected rural postman problem optimisation are strategically combined to solve the coverage of the entire area of interest. The strategy has been tested in several synthetic maps and a real scenario showing short computation times and complete coverage.

Keywords: sweeping robot; coverage path planning; genetic algorithm; divide and conquer (search for similar items in EconPapers)
JEL-codes: Q Q0 Q4 Q40 Q41 Q42 Q43 Q47 Q48 Q49 (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/1996-1073/15/21/7898/pdf (application/pdf)
https://www.mdpi.com/1996-1073/15/21/7898/ (text/html)

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:gam:jeners:v:15:y:2022:i:21:p:7898-:d:952210

Access Statistics for this article

Energies is currently edited by Ms. Agatha Cao

More articles in Energies from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().