Approximation Algorithms for Tours of Orientation-Varying View Cones

Nikolaos Stefas; Patrick A. Plonski; Volkan I Isler

doi:10.1109/ICRA.2018.8462908

Approximation Algorithms for Tours of Orientation-Varying View Cones

Nikolaos Stefas
, Patrick A. Plonski
, Volkan I Isler

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 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 language	English (US)
Title of host publication	2018 IEEE International Conference on Robotics and Automation, ICRA 2018
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	3910-3915
Number of pages	6
ISBN (Electronic)	9781538630815
DOIs	https://doi.org/10.1109/ICRA.2018.8462908
State	Published - Sep 10 2018
Event	2018 IEEE International Conference on Robotics and Automation, ICRA 2018 - Brisbane, Australia Duration: May 21 2018 → May 25 2018

Publication series

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

Conference

Conference	2018 IEEE International Conference on Robotics and Automation, ICRA 2018
Country/Territory	Australia
City	Brisbane
Period	5/21/18 → 5/25/18

Bibliographical note

Publisher Copyright:
© 2018 IEEE.

Publisher link

10.1109/ICRA.2018.8462908

Find It

Find It at U of M Libraries

Cite this

Stefas, N., Plonski, P. A., & Isler, V. I. (2018). Approximation Algorithms for Tours of Orientation-Varying View Cones. In 2018 IEEE International Conference on Robotics and Automation, ICRA 2018 (pp. 3910-3915). Article 8462908 (Proceedings - IEEE International Conference on Robotics and Automation). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICRA.2018.8462908

Approximation Algorithms for Tours of Orientation-Varying View Cones. / Stefas, Nikolaos; Plonski, Patrick A.; Isler, Volkan I.
2018 IEEE International Conference on Robotics and Automation, ICRA 2018. Institute of Electrical and Electronics Engineers Inc., 2018. p. 3910-3915 8462908 (Proceedings - IEEE International Conference on Robotics and Automation).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Stefas, N, Plonski, PA & Isler, VI 2018, Approximation Algorithms for Tours of Orientation-Varying View Cones. in 2018 IEEE International Conference on Robotics and Automation, ICRA 2018., 8462908, Proceedings - IEEE International Conference on Robotics and Automation, Institute of Electrical and Electronics Engineers Inc., pp. 3910-3915, 2018 IEEE International Conference on Robotics and Automation, ICRA 2018, Brisbane, Australia, 5/21/18. https://doi.org/10.1109/ICRA.2018.8462908

@inproceedings{392b348f0ed04e0197f92c879ef50a52,

title = "Approximation Algorithms for Tours of Orientation-Varying View Cones",

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.",

author = "Nikolaos Stefas and Plonski, \{Patrick A.\} and Isler, \{Volkan I\}",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 2018 IEEE International Conference on Robotics and Automation, ICRA 2018 ; Conference date: 21-05-2018 Through 25-05-2018",

year = "2018",

month = sep,

day = "10",

doi = "10.1109/ICRA.2018.8462908",

language = "English (US)",

series = "Proceedings - IEEE International Conference on Robotics and Automation",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "3910--3915",

booktitle = "2018 IEEE International Conference on Robotics and Automation, ICRA 2018",

}

TY - GEN

T1 - Approximation Algorithms for Tours of Orientation-Varying View Cones

AU - Stefas, Nikolaos

AU - Plonski, Patrick A.

AU - Isler, Volkan I

PY - 2018/9/10

Y1 - 2018/9/10

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85063134945

UR - https://www.scopus.com/pages/publications/85063134945#tab=citedBy

U2 - 10.1109/ICRA.2018.8462908

DO - 10.1109/ICRA.2018.8462908

M3 - Conference contribution

AN - SCOPUS:85063134945

T3 - Proceedings - IEEE International Conference on Robotics and Automation

SP - 3910

EP - 3915

BT - 2018 IEEE International Conference on Robotics and Automation, ICRA 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2018 IEEE International Conference on Robotics and Automation, ICRA 2018

Y2 - 21 May 2018 through 25 May 2018

ER -

Approximation Algorithms for Tours of Orientation-Varying View Cones

Abstract

Publication series

Conference

Bibliographical note

Publisher link

Find It

Other files and links

Fingerprint

Cite this