On-Line Coverage of Planar Environments by a Battery Powered Autonomous Mobile Robot

Abstract

Abstract This paper is concerned with on-line coverage of unknown planar en-vironments by a mobile robot of size D operating with a limited energy capacity battery. The battery capacity is represented by the path length L that the robot can travel under a full battery charge. Starting at S, the robot has to cover a planar environment containing unknown obstacles, and return to S upon task completion. During task execution the robot may return to S at any time to recharge its bat-tery. The paper first describes a battery powered off-line coverage methodology, then introduces the BPC (Battery Powered Coverage) algorithm that performs on-line battery powered coverage using position and local obstacle detection sensors. The performance of the BPC algorithm is measured by its competitiveness, determined by measuring its total on-line path length, l, relative to the optimal off-line solution lopt. The paper establishes that the BPC algorithm has a competitive performance of l ≤ LD lopt. The paper additionally establishes a universal lower bound of l≥log( L 4D)lopt over all on-line battery powered coverage algorithms. Execution example illustrates the usefulness of the BPC algorithm. 1