An Approximation Algorithm for Online Coverage Path Planning with the Energy Constraint
2019-06-17
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
An Approximation Algorithm for Online Coverage Path Planning with the Energy Constraint
Authors
Published Date
2019-06-17
Publisher
Type
Report
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.
Keywords
Description
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Wei, Ming; Isler, Volkan. (2019). An Approximation Algorithm for Online Coverage Path Planning with the Energy Constraint. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/216040.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.