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.|
|Number of pages||6|
|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
|Name||Proceedings - IEEE International Conference on Robotics and Automation|
|Conference||2018 IEEE International Conference on Robotics and Automation, ICRA 2018|
|Period||5/21/18 → 5/25/18|
Bibliographical noteFunding Information:
This work is supported in part by NSF Award #1525045 and a grant from Minnesota State LCCMR Program.
© 2018 IEEE.