A genetic algorithm for task completion time minimization for multi-robot sensor-based coverage

摘要

Minimizing the coverage task time is important for many sensor-based coverage applications. The completion time of a sensor-based coverage task is determined by the maximum time traveled by a robot in a mobile robot group. So the environment needs to be partitioned among robots considering their travel times. Most of the coverage algorithms results in sharp turns which require the robot to slow down, turn and accelerate. So the actual travel time of a mobile robot is depending on the traveled distance and number of turns both. In this study, previously proposed hierarchical oriented genetic algorithm (HOGA) is extended to consider the travel time rather than just the traveled distances. The HOGA consists of two phases. In the first phase, a previously proposed oriented genetic algorithm is used to find a single route with minimum repeated coverage. Then, in the second phase, a directed genetic algorithm is used to partition the route among robots considering actual travel time costs. The algorithms are coded in C++ and simulations are conducted using P3-DX mobile robots in the MobileSim environment.