Approximation algorithms for tours of height-varying view cones
Patrick A. Plonski, Volkan Isler · The International Journal of Robotics Research · 2018
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 [Formula: see text] 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 most [Formula: see text] times the length of the optimal solution where [Formula: see text] and [Formula: see text] 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.