Approximation algorithms for tours of height-varying view cones

Patrick A. Plonski, Volkan Isler

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

We introduce a novel coverage problem that arises in aerial surveying applications. The goal is to compute a shortest path that visits a given set of cones. The apex of each cone is restricted to lie on the ground plane. The common angle (Formula presented.) of the cones represent the field of view of the onboard camera. The cone heights, which can be varying, correspond with the desired observation quality (e.g. resolution). This problem is a novel variant of the traveling salesman problem with neighborhoods (TSPN). We name it Cone-TSPN. Our main contribution is a polynomial time approximation algorithm for Cone-TPSN. We analyze its theoretical performance and show that it returns a solution whose length is at most (Formula presented.) times the length of the optimal solution where (Formula presented.) and (Formula presented.) are the heights of the tallest and shortest input cones, respectively.We demonstrate the use of our algorithm in a representative precision agriculture application. Wefurther study its performance in simulation using randomly generated cone sets. Our results indicate that the performance of our algorithm is superior to standard solutions.

Original languageEnglish (US)
Pages (from-to)224-235
Number of pages12
JournalInternational Journal of Robotics Research
Volume38
Issue number2-3
DOIs
StatePublished - Mar 1 2019

Bibliographical note

Funding Information:
The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is based upon research supported by the National Science Foundation (grant numbers 1111638, 1317788, and 1525045). Patrick A Plonski is supported by a Doctoral Dissertation Fellowship from the University of Minnesota.

Publisher Copyright:
© The Author(s) 2018.

Keywords

  • Path planning
  • approximation algorithms
  • euclidean traveling salesman problem
  • geometric algorithms
  • traveling salesman problem with neighborhoods
  • view planning

Fingerprint

Dive into the research topics of 'Approximation algorithms for tours of height-varying view cones'. Together they form a unique fingerprint.

Cite this