An Approximation Algorithm for Online Coverage Path Planning with the Energy Constraint

Abstract

In online coverage path planning, the objective is to plan paths for a robot to visit every point in an unknown environment as quickly as possible. We consider online coverage with an energy constraint which is modeled as the maximum distance B the robot can travel after a full recharge. There is a single charging station in the environment which needs to be revisited before the robot runs out of energy. Under this model, it has been proven that any algorithm for online coverage path planning with the energy constraint must have an approximation rate of ?(log B/4r) [1], where r is the robot diameter. In this paper, we present an optimal online algorithm whose worst-case performance matches this lower bound asymptotically. We present simulations and field experiments which demonstrate the applicability of our algorithm in real applications.