Skip to main content
Kent State University Home

Open Access Kent State (OAKS)

  • About
    • About
    • Frequently Asked Questions
    • Rights and Reuse
  • Browse
    • Authors
    • Collections
    • Communities
    • Subjects
  • Login

A 2-Approximation Algorithm for the Online Tethered Coverage Problem

Division of Research and Sponsored Programs
  1. Open Access Kent State
  2. Conferences & Events
  3. Undergraduate Research Symposium
  4. 2019 - Kent State University Undergraduate Symposium on Research, Scholarship and Creative Activity
  5. A 2-Approximation Algorithm for the Online Tethered Coverage Problem
Author(s)
  • Vala Zeinali
Abstract

We consider the problem of covering an unknown planar environment possibly containing obstacles using a robot of square size

D × D attached to a fixed point S by a cable of finite length L. The

environment is structured as a cell layout with resolution proportional to the robot size D × D, imposed on it. Starting at S, the task

for the robot is to visit each cell of the environment (not occupied by obstacles) and return to S with the cable fully retracted. In a single time step, the robot can move from one cell to one of its four adjacent cells. The cable length of L allows the robot to visit a cell that is at distance at most L (i.e., ⌊L/D⌋ cells in the environment at increasing distance) from S. Our goal is to minimize the total

distance traveled by the robot to fully cover the unknown environment avoiding tangling the cable. In this paper, we present the first

online tethered coverage path planning algorithm that achieves 2- approximation for the total distance traveled by the robot compared to the distance traveled using an optimal offline algorithm. Our algorithm guarantees that the cable never tangles. Moreover, our algorithm significantly improves the 2L/D-approximation achieved by the best previously known algorithm designed for this problem.

Furthermore, we show that there are instances for which no on- line algorithm achieves better than 2-approximation, which implies

that our algorithm is essentially optimal. Simulation experiments illustrate the usefulness and efficiency of our proposed algorithm.

Format
Conference Proceeding
Publication Date
2019-04-09
Contributor(s)
Faculty Mentor
Dr. Gokarna
Subject
  • Artificial Intelligence and Robotics
Community
Division of Research and Sponsored Programs
Modified Abstract

We consider the problem of covering an unknown planar environment possibly containing obstacles using a robot of square size

D × D attached to a fixed point S by a cable of finite length L. The

environment is structured as a cell layout with resolution proportional to the robot size D × D, imposed on it. Starting at S, the task

for the robot is to visit each cell of the environment (not occupied by obstacles) and return to S with the cable fully retracted. In a single time step, the robot can move from one cell to one of its four adjacent cells. The cable length of L allows the robot to visit a cell that is at distance at most L (i.e., ⌊L/D⌋ cells in the environment at increasing distance) from S. Our goal is to minimize the total

distance traveled by the robot to fully cover the unknown environment avoiding tangling the cable. In this paper, we present the first

online tethered coverage path planning algorithm that achieves 2- approximation for the total distance traveled by the robot compared to the distance traveled using an optimal offline algorithm. Our algorithm guarantees that the cable never tangles. Moreover, our algorithm significantly improves the 2L/D-approximation achieved by the best previously known algorithm designed for this problem.

Furthermore, we show that there are instances for which no on- line algorithm achieves better than 2-approximation, which implies

that our algorithm is essentially optimal. Simulation experiments illustrate the usefulness and efficiency of our proposed algorithm.

  • Facebook
  • Linkedin
  • Twitter
  • Pinterest
  • Email
Open Access Kent State
University Libraries

Street Address

1125 Risman Dr.
Kent, OH 44242

Mailing Address

P.O. Box 5190
Kent, OH 44242-0001

Contact Us

  • oaks [at] kent [dot] edu

Quick Links

  • About
  • Frequently Asked Questions
  • Rights and Reuse

Information

  • Accessibility
  • Annual Security Reports
  • Emergency Information
  • For Our Alumni
  • For the Media
  • Health Services
  • Jobs & Employment
  • May 4th, 50th Commemoration
  • Privacy Statement
  • Website Feedback
Kent State University Home
© 2021 Kent State University All rights reserved.