Approximation algorithms for tours of height-varying view cones. (March 2019)

• Record Type: Journal Article
• Authors: Plonski, Patrick A; Isler, Volkan
• Is Part Of: International journal of robotics research. Volume 38:Number 2/3(2019)
• Page Start: 224
• Page End: 235
• Publication Date: 2019-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/0278364918784353
• Languages: English
• ISSNs: 0278-3649

Abstract

We introduce a novel coverage problem that arises in aerial surveying applications. The goal is to compute a shortest path that 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 salesman 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 mostO ( 1 + log ( h max / h min ) ) times the length of the optimal solution whereh max andh min 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.