Approximation algorithms for tours of orientation-varying view cones

Nikolaos Stefas, Patrick A. Plonski, Volkan Isler

Research output: Contribution to journalArticlepeer-review

Abstract

This article considers the problem of finding a shortest tour to visit viewing sets of points on a plane. Each viewing set is represented as an inverted view cone with apex angle α and height h. The apex of each cone is restricted to lie on the ground plane. Its orientation angle (tilt) ϵ is the angle difference between the cone bisector and the ground plane normal. This is a novel variant of the 3D Traveling Salesman Problem with Neighborhoods (TSPN) called Cone-TSPN. One application of Cone-TSPN is to compute a trajectory to observe a given set of locations with a camera: for each location, we can generate a set of cones whose apex and orientation angles α and ϵ correspond to the camera’s field of view and tilt. The height of each cone h corresponds to the desired resolution. Recently, Plonski and Isler presented an approximation algorithm for Cone-TSPN for the case where all cones have a uniform orientation angle of ϵ = 0. We study a new variant of Cone-TSPN where we relax this constraint and allow the cones to have non-uniform orientations. We call this problem Tilted Cone-TSPN and present a polynomial-time approximation algorithm with ratio (Formula presented.), where H is the set of all cone heights. We demonstrate through simulations that our algorithm can be implemented in a practical way and that by exploiting the structure of the cones we can achieve shorter tours. Finally, we present experimental results from various agriculture applications that show the benefit of considering view angles for path planning.

Original languageEnglish (US)
Pages (from-to)389-401
Number of pages13
JournalInternational Journal of Robotics Research
Volume39
Issue number4
DOIs
StatePublished - Mar 1 2020

Bibliographical note

Funding Information:
A preliminary version of this article, was presented at the International Conference on Robotics and Automation (ICRA 2018). This submission extends the conference version by presenting the full details of the proofs, a revised implementation and field experiments. We thank Dr. Forest Isbell for allowing us to perform experiments at Cedar Creek Ecosystem Science Reserve. The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by the NSF (award numbers 1525045, 1617718 & 1849107) and a grant from Minnesota State LCCMR Program.

Funding Information:
https://orcid.org/0000-0002-4940-1716 Stefas Nikolaos https://orcid.org/0000-0002-7978-4586 Plonski Patrick A Isler Volkan University of Minnesota, Minneapolis, MN, USA Nikolaos Stefas, Department of Computer Science and Engineering, University of Minnesota, 200 Union Street SE, Minneapolis, MN 55455, USA. Email: stefa125@umn.edu 1 2020 0278364919893455 © The Author(s) 2020 2020 SAGE Publications This article considers the problem of finding a shortest tour to visit viewing sets of points on a plane. Each viewing set is represented as an inverted view cone with apex angle α and height h . The apex of each cone is restricted to lie on the ground plane. Its orientation angle (tilt) ϵ is the angle difference between the cone bisector and the ground plane normal. This is a novel variant of the 3D Traveling Salesman Problem with Neighborhoods (TSPN) called Cone-TSPN. One application of Cone-TSPN is to compute a trajectory to observe a given set of locations with a camera: for each location, we can generate a set of cones whose apex and orientation angles α and ϵ correspond to the camera’s field of view and tilt. The height of each cone h corresponds to the desired resolution. Recently, Plonski and Isler presented an approximation algorithm for Cone-TSPN for the case where all cones have a uniform orientation angle of ϵ = 0 . We study a new variant of Cone-TSPN where we relax this constraint and allow the cones to have non-uniform orientations. We call this problem Tilted Cone-TSPN and present a polynomial-time approximation algorithm with ratio O ( 1 + tan α 1 − tan ϵ tan α ( 1 + log max ( H ) min ( H ) ) ) , where H is the set of all cone heights. We demonstrate through simulations that our algorithm can be implemented in a practical way and that by exploiting the structure of the cones we can achieve shorter tours. Finally, we present experimental results from various agriculture applications that show the benefit of considering view angles for path planning. Path planning view planning approximation algorithms geometric algorithms euclidean traveling salesman problem traveling salesman problem with neighborhoods minnesota state colleges and universities https://doi.org/10.13039/100004966 LCCMR program National Science Foundation https://doi.org/10.13039/100000001 1525045 edited-state corrected-proof typesetter ts1 A preliminary version of this article, was presented at the International Conference on Robotics and Automation (ICRA 2018). This submission extends the conference version by presenting the full details of the proofs, a revised implementation and field experiments. We thank Dr. Forest Isbell for allowing us to perform experiments at Cedar Creek Ecosystem Science Reserve. Funding The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by the NSF (award numbers 1525045, 1617718 & 1849107) and a grant from Minnesota State LCCMR Program. ORCID iDs Nikolaos Stefas https://orcid.org/0000-0002-4940-1716 Patrick A Plonski https://orcid.org/0000-0002-7978-4586

Publisher Copyright:
© The Author(s) 2020.

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 orientation-varying view cones'. Together they form a unique fingerprint.

Cite this