Approximation algorithms for tours of orientation-varying view cones

Abstract

This article considers the problem of finding a shortest tour to visit viewing sets of points on a plane. Each viewing set is represented as an inverted view cone with apex angle $α$ and height $h$ . The apex of each cone is restricted to lie on the ground plane. Its orientation angle (tilt) $ϵ$ is the angle difference between the cone bisector and the ground plane normal. This is a novel variant of the 3D Traveling Salesman Problem with Neighborhoods (TSPN) called Cone-TSPN. One application of Cone-TSPN is to compute a trajectory to observe a given set of locations with a camera: for each location, we can generate a set of cones whose apex and orientation angles $α$ and $ϵ$ correspond to the camera’s field of view and tilt. The height of each cone $h$ corresponds to the desired resolution. Recently, Plonski and Isler presented an approximation algorithm for Cone-TSPN for the case where all cones have a uniform orientation angle of $ϵ = 0$ . We study a new variant of Cone-TSPN where we relax this constraint and allow the cones to have non-uniform orientations. We call this problem Tilted Cone-TSPN and present a polynomial-time approximation algorithm with ratio $O (\frac{1 + \tan α}{1 - \tan ϵ \tan α} (1 + \log \frac{max (H)}{min (H)}))$ , where $H$ is the set of all cone heights. We demonstrate through simulations that our algorithm can be implemented in a practical way and that by exploiting the structure of the cones we can achieve shorter tours. Finally, we present experimental results from various agriculture applications that show the benefit of considering view angles for path planning.

Keywords

Path planning view planning approximation algorithms geometric algorithms euclidean traveling salesman problem traveling salesman problem with neighborhoods

Get full access to this article

View all access options for this article.

References

Applegate

Bixby

Chvatal

Cook

(2006) Concorde TSP solver. Available at: http://www.tsp.gatech.edu/concorde/.

Arora

(1998) Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. Journal of the ACM 45(5): 753–782.

Bodlaender

Feremans

Grigoriev

Penninkx

Sitters

Wolle

(2009) On the minimum corridor connection problem and other generalized geometric problems. Computational Geometry 42(9): 939–951.

Chan

THH

Elbassioni

(2011) A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics. Discrete & Computational Geometry 46(4): 704–723.

Cheng

Keller

Kumar

(2008) Time-optimal UAV trajectory planning for 3D urban structure coverage. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2008 (IROS 2008). IEEE, pp. 2750–2757.

Choset

(2001) Coverage for robotics—a survey of recent results. Annals of Mathematics and Artificial Intelligence 31(1): 113–126.

de Berg

Gudmundsson

Katz

Levcopoulos

Overmars

van der Stappen

(2005) TSP with neighborhoods of varying size. Journal of Algorithms 57(1): 22–36.

Dumitrescu

Mitchell

(2001) Approximation algorithms for TSP with neighborhoods in the plane. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, pp. 38–46.

Dumitrescu

Tóth

(2015) Constant-factor approximation for TSP with disks. arXiv preprint arXiv:1506.07903.

10.

Dumitrescu

Tóth

(2016) The traveling salesman problem for lines, balls, and planes. ACM Transactions on Algorithms 12(3): 43.

11.

Elbassioni

Fishkin

Sitters

(2006) On approximating the TSP with intersecting neighborhoods. In: International Symposium on Algorithms and Computation. Berlin: Springer, pp. 213–222.

12.

Englot

Hover

(2013) Three-dimensional coverage planning for an underwater inspection robot. The International Journal of Robotics Research 32(9–10): 1048–1073.

13.

Galceran

Carreras

(2013) A survey on coverage path planning for robotics. Robotics and Autonomous Systems 61(12): 1258–1276.

14.

Low

Dolan

Khosla

(2008) Adaptive multi-robot wide-area exploration and mapping. In: Proceedings of the 7th International Joint Conference on Autonomous Agents and Multiagent Systems, Vol. 1. International Foundation for Autonomous Agents and Multiagent Systems, pp. 23–30.

15.

Mitchell

(1999) Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM Journal on Computing 28(4): 1298–1309.

16.

Mitchell

(2007) A PTAS for TSP with neighborhoods among fat regions in the plane. In: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Philadelphia, PA: Society for Industrial and Applied Mathematics, pp. 11–18.

17.

Plonski

Isler

(2019) Approximation algorithms for tours of height-varying view cones. The International Journal of Robotics Research 38(2–3): 224–235.

18.

Reinelt

(1994) The Traveling Salesman: Computational Solutions for TSP Applications. Berlin: Springer-Verlag.

19.

Sadat

Wawerla

Vaughan

(2014) Recursive non-uniform coverage of unknown terrains for UAVs. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2014 (IROS 2014). IEEE, pp. 1742–1747.

20.

Safra

Schwartz

(2006) On the complexity of approximating TSP with neighborhoods and related problems. Computational Complexity 14(4): 281–307.

21.

Singh

Krause

Guestrin

Kaiser

(2009) Efficient informative sensing using multiple robots. Journal of Artificial Intelligence Research 34: 707–755.

22.

Stefas

Bayram

Isler

(2016) Vision-based UAV navigation in orchards. IFAC-PapersOnLine 49(16): 10–15.