A log-approximation for coverage path planning with the energy constraint

Minghan Wei, Volkan I Isler

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations

Abstract

We consider the problem of covering an environment with a robot when the robot has limited energy budget. The environment is represented as a polygon with a grid, whose resolution is proportional to the robot size, imposed on it. There is a single charging station in the environment. At each time step, the robot can move from one grid cell to an adjacent one. The energy consumption when moving in the environment is assumed to be uniform and proportional to the distance traveled. Our goal is to minimize both the total distance and the number of visits to the charging station. We present a coverage path planning algorithm which has O(lnD) approximation factor for both objectives, where D is the distance of the furthest cell in the environment measured on the grid.

Original languageEnglish (US)
Pages (from-to)532-539
Number of pages8
JournalProceedings International Conference on Automated Planning and Scheduling, ICAPS
Volume2018-June
StatePublished - Jan 1 2018
Event28th International Conference on Automated Planning and Scheduling, ICAPS 2018 - Delft, Netherlands
Duration: Jun 24 2018Jun 29 2018

Fingerprint Dive into the research topics of 'A log-approximation for coverage path planning with the energy constraint'. Together they form a unique fingerprint.

Cite this