Approximation Algorithms for Tours of Orientation-Varying View Cones

Nikolaos Stefas, Patrick A. Plonski, Volkan I Isler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

This paper considers the problem of finding the shortest tour to cover a given set of inverted cone views with apex angle alpha and height H when their apex points lie on a planar surface. This is a novel variant of the 3D Traveling Salesman Problem with intersecting Neighborhoods (TSPN) called Cone-Tspn. When the cones are allowed to tilt by an angle epsilon we have the tilted Cone-Tspn problem, to which we present an algorithm that returns a solution with an approximation ratio of Oleft(frac 1+tanalpha 1-tanepsilontanalpha left(1+logfrac max(H) min(H) right)right). We demonstrate through simulations that our algorithm can be implemented in a practical way and by exploiting the structure of the cones we can achieve shorter tours. Finally, we present results from covering a reflective surface (lake area) that shows the importance of selecting different view angles under strong sunlight specularities.

Original languageEnglish (US)
Title of host publication2018 IEEE International Conference on Robotics and Automation, ICRA 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages3910-3915
Number of pages6
ISBN (Electronic)9781538630815
DOIs
StatePublished - Sep 10 2018
Event2018 IEEE International Conference on Robotics and Automation, ICRA 2018 - Brisbane, Australia
Duration: May 21 2018May 25 2018

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)1050-4729

Conference

Conference2018 IEEE International Conference on Robotics and Automation, ICRA 2018
CountryAustralia
CityBrisbane
Period5/21/185/25/18

Fingerprint Dive into the research topics of 'Approximation Algorithms for Tours of Orientation-Varying View Cones'. Together they form a unique fingerprint.

Cite this