Online Coverage of Planar Environments by a Battery Powered Autonomous Mobile Robot
Authors:
- 27 January 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automation Science and Engineering
- Vol. 13 (2) , 425-436
Abstract
This paper is concerned with online coverage of unknown planar environments 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 battery. This paper first describes a battery powered offline coverage methodology, then introduces the battery powered coverage (BPC) algorithm that performs online battery powered coverage using position and local obstacle detection sensors. The performance of the BPC algorithm is measured by its competitiveness, determined by measuring the mobile robot's total online path length, l, relative to the optimal offline solution lopt. This paper establishes that the BPC algorithm has a competitive performance of l ≤ ( L/ D) lopt. This paper additionally establishes a universal lower bound of l ≥ log( L/ 4 D) lopt over all online battery powered coverage algorithms. Execution example illustrates the usefulness of the BPC algorithm.Keywords
This publication has 21 references indexed in Scilit:
- A survey on coverage path planning for roboticsRobotics and Autonomous Systems, 2013
- Online algorithms for searching and exploration in the planeComputer Science Review, 2010
- CBUG: A Quadratically Competitive Mobile Robot Navigation AlgorithmIEEE Transactions on Robotics, 2008
- Optimal constrained graph explorationACM Transactions on Algorithms, 2006
- Autonomous coverage operations in semi-structured outdoor environments2003
- Competitive on-line coverage of grid environments by a mobile robotComputational Geometry, 2003
- Shortest path planning for a tethered robot or an anchored cable2003
- A solution to the simultaneous localization and map building (SLAM) problemIEEE Transactions on Robotics and Automation, 2001
- Terrain coverage of an unknown room by an autonomous mobile robot1995
- Searching in the PlaneInformation and Computation, 1993