Approximation algorithms for tours of orientation-varying view cones

Nikolaos Stefas, Patrick A. Plonski, Volkan Isler

Research output: Contribution to journalArticle

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 (Formula presented.) 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)
JournalInternational Journal of Robotics Research
DOIs
StateAccepted/In press - Jan 1 2020

Fingerprint

Approximation algorithms
Cones
Approximation Algorithms
Cone
Traveling salesman problem
Travelling salesman problems
Angle
Apex
Tilt
Camera
Cameras
Bisector
Agriculture
Path Planning
Motion planning
Field of View
Set of points
Polynomial-time Algorithm

Keywords

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

Cite this

Approximation algorithms for tours of orientation-varying view cones. / Stefas, Nikolaos; Plonski, Patrick A.; Isler, Volkan.

In: International Journal of Robotics Research, 01.01.2020.

Research output: Contribution to journalArticle

@article{3daef74ab9bf4fa9b99b78b3b02cc991,
title = "Approximation algorithms for tours of orientation-varying view cones",
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 (Formula presented.) 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.",
keywords = "approximation algorithms, euclidean traveling salesman problem, geometric algorithms, Path planning, traveling salesman problem with neighborhoods, view planning",
author = "Nikolaos Stefas and Plonski, {Patrick A.} and Volkan Isler",
year = "2020",
month = "1",
day = "1",
doi = "10.1177/0278364919893455",
language = "English (US)",
journal = "International Journal of Robotics Research",
issn = "0278-3649",
publisher = "SAGE Publications Inc.",

}

TY - JOUR

T1 - Approximation algorithms for tours of orientation-varying view cones

AU - Stefas, Nikolaos

AU - Plonski, Patrick A.

AU - Isler, Volkan

PY - 2020/1/1

Y1 - 2020/1/1

N2 - 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 (Formula presented.) 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.

AB - 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 (Formula presented.) 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.

KW - approximation algorithms

KW - euclidean traveling salesman problem

KW - geometric algorithms

KW - Path planning

KW - traveling salesman problem with neighborhoods

KW - view planning

UR - http://www.scopus.com/inward/record.url?scp=85077608653&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85077608653&partnerID=8YFLogxK

U2 - 10.1177/0278364919893455

DO - 10.1177/0278364919893455

M3 - Article

AN - SCOPUS:85077608653

JO - International Journal of Robotics Research

JF - International Journal of Robotics Research

SN - 0278-3649

ER -