LEO: Liquid Exploration Online

This article introduces a novel approach to the online complete coverage path planning (CCPP) problem that is specifically tailored to the needs of skid-steer tracked robots. In contrast to most of the current state of the art algorithms for this task, the proposed algorithm reduces the number of turning maneuvers which are responsible for a large part of the robot's energy consumption. Nevertheless, the approach still keeps the total distance traveled at a competitive level. The algorithm operates on a grid-based environment representation and uses a 3×3 prioritization matrix for local navigation decisions. This matrix prioritizes cardinal directions leading to a preference of straight motions. In case no progress can be achieved based on a local decision, global path planning is used to choose a path to the closest known unvisited cell, also guaranteeing completeness of the approach this way. In an extensive evaluation using simulation experiments we show that the new algorithm indeed generates competitively short paths with largely reduced turning costs, compared to other state of the art CCPP algorithms. We also illustrate its performance on a real robot.