Approximation algorithms for tours of orientation-varying view cones. (March 2020)

• Record Type: Journal Article
• Authors: Stefas, Nikolaos; Plonski, Patrick A; Isler, Volkan
• Is Part Of: International journal of robotics research. Volume 39:Number 4(2020)
• Page Start: 389
• Page End: 401
• Publication Date: 2020-03
• Subjects: Path planning -- view planning -- approximation algorithms -- geometric algorithms -- euclidean traveling salesman problem -- traveling salesman problem with neighborhoods; Robots -- Periodicals; Robots, Industrial -- Periodicals; 629.89205
• DOI: 10.1177/0278364919893455
• Languages: English
• ISSNs: 0278-3649

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 heighth . 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 coneh 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 ratioO ( 1 + tan α 1 − tan ϵ tan α ( 1 + log max ( H ) min ( H ) ) ), whereH 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.