Hierarchical oriented genetic algorithms for coverage path planning of multi-robot teams with load balancing

摘要

Multi-robot coverage path planning problems require every point in a given area to be covered by at least one member of the robot team using their sensors. For a time-efficient coverage, the environment needs to be partitioned among robots in a balanced manner. So the problem can be modeled as task assignment problem with load balancing. In this study, we propose two oriented genetic algorithms working in a hierarchical manner to deal with this problem. In the first phase, a previously proposed oriented genetic algorithm is used to find a single route with minimum repeated coverage. In the following phase, a directed genetic algorithm is used to partition the route among robots considering load balancing. The algorithm is coded in C++, simulations and experiments are conducted using P3-DX mobile robots in the MobileSim environment. The hierarchical oriented genetic algorithm (HOGA) is also compared to the multi-robot spanning tree coverage (STC) approach in terms of load balancing. The comparison indicates competitive results over multi-robot STC.