Multi-robot sensor-based coverage path planning using capacitated arc routing approach

Abstract

In this study, a novel sensor-based coverage algorithm is proposed for multi-robots considering energy capacities of the mobile robots. Firstly, the environment is modeled by a Generalized Voronoi diagram-based graph to guarantee complete sensor based coverage. Secondly, depending on required arc set, an initial complete coverage route is created by using Chinese postman problem (CPP) and/or rural postman problem (RPP). Then this initial route is partitioned among robots using Ulusoy's algorithm, which was developed for basic capacitated arc routing (CARP), by considering robot energy capacities. Although the multi-robot sensor-based coverage problem resembles CARP, there are some differences. Therefore, Ulusoy's algorithm is modified and used for this problem. The developed algorithm is coded in C++ and implemented on P3-DX mobile robots in MobileSim simulation environment.