### 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 language | English (US) |
---|---|

Journal | International Journal of Robotics Research |

DOIs | |

State | Accepted/In press - Jan 1 2020 |

### Fingerprint

### Keywords

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

### Cite this

*International Journal of Robotics Research*. https://doi.org/10.1177/0278364919893455

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

Research output: Contribution to journal › Article

}

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 -