Visual coverage path planning for urban environments

Cheng Peng, Volkan Isler

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

View planning for visual coverage is a fundamental robotics problem. Coverage for small objects (e.g. for inspection) or small scale indoor scenes have been studied extensively. However, view planning to cover a large scale urban environment remains challenging. Algorithms that can scale up to the size of such environments while providing performance guarantees are missing. In this letter, we model urban environments as a set of surfaces with k distinct surface normals whose viewing cones must be visited by a robot. We model the resulting coverage problem as a novel variant of Traveling Salesman Problem with Neighborhoods (TSPN). The neighborhoods are defined as cones, which constrain the path coverage quality. We present a polynomial time algorithm which admits an approximation factor of O(k/tan (α)max [LB,WB,HB]), where α is the maximum viewing angle, and LB,HB,WB are respectively the length, width, and height of a minimum enclosing box of a city scene B. In addition to the analytical upper bounds, we show in simulations that our method outperforms three baseline methods in both trajectory length and run-time. We also demonstrate our method and evaluate the coverage quality of a city containing more than 70 buildings in a photo-realistic rendering software.

Original languageEnglish (US)
Article number9145689
Pages (from-to)5961-5968
Number of pages8
JournalIEEE Robotics and Automation Letters
Volume5
Issue number4
DOIs
StatePublished - Oct 2020

Bibliographical note

Publisher Copyright:
© 2016 IEEE.

Keywords

  • Motion and path planning
  • computational geometry

Fingerprint

Dive into the research topics of 'Visual coverage path planning for urban environments'. Together they form a unique fingerprint.

Cite this