Approximation Algorithms for Tours of Height-varying View Cones

Patrick A. Plonski, Volkan Isler

Research output: Chapter in Book/Report/Conference proceedingChapter


We introduce a novel coverage problem which arises in aerial surveying applications. The goal is to compute a shortest path which visits a given set of cones. The apex of each cone is restricted to lie on the ground plane. The common angle 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 Salesperson 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 times the length of the optimal solution where and are the heights of the tallest and shortest input cones, respectively. We demonstrate the use of our algorithm in a representative precision agriculture application. We further 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)
Title of host publicationSpringer Proceedings in Advanced Robotics
PublisherSpringer Science and Business Media B.V.
Number of pages16
StatePublished - 2020

Publication series

NameSpringer Proceedings in Advanced Robotics
ISSN (Print)2511-1256
ISSN (Electronic)2511-1264

Bibliographical note

Funding Information:
★ P. A. Plonski and V. Isler are with the Department of Computer Science and Engi-neering, University of Minnesota, 200 Union Street SE, Minneapolis MN 55455 USA email: {plonski, isler} This material is based upon work supported by the National Science Foundation under grant numbers 1111638 and 1317788.

Publisher Copyright:
© 2020, Springer Nature Switzerland AG.


Dive into the research topics of 'Approximation Algorithms for Tours of Height-varying View Cones'. Together they form a unique fingerprint.

Cite this