Acta Polytechnica CTU Proceedings doi:10.14311/APP.2016.6.0034 Acta Polytechnica CTU Proceedings 6:34–39, 2016 © Czech Technical University in Prague, 2016 available online at http://ojs.cvut.cz/ojs/index.php/app THE DUBINS TRAVELING SALESMAN PROBLEM WITH CONSTRAINED COLLECTING MANEUVERS Petr Váňa∗, Jan Faigl Dept. of Computer Science, Czech Technical University in Prague, Technická 2, 166 27 Prague, Czech Republic ∗ corresponding author: vanapet1@fel.cvut.cz Abstract. In this paper, we introduce a variant of the Dubins traveling salesman problem (DTSP) that is called the Dubins traveling salesman problem with constrained collecting maneuvers (DTSP-CM). In contrast to the ordinary formulation of the DTSP, in the proposed DTSP-CM, the vehicle is requested to visit each target by specified collecting maneuver to accomplish the mission. The proposed problem formulation is motivated by scenarios with unmanned aerial vehicles where particular maneuvers are necessary for accomplishing the mission, such as object dropping or data collection with sensor sensitive to changes in vehicle heading. We consider existing methods for the DTSP and propose its modifications to use these methods to address a variant of the introduced DTSP-CM, where the collecting maneuvers are constrained to straight line segments. Keywords: Dubins vehicle, DTSP, non-holonomic vehicle, path planning, collecting maneuver. 1. Introduction The Dubins traveling salesman problem (DTSP) [1] has been subject of studies for many years. The problem is to find a shortest tour visiting a given set of target locations by the Dubins vehicle [2] that models a fix-wing aircraft (or car-like vehicle) with a limited minimal turning radius and a constant forward velocity. The herein studied path planning problem is moti- vated by surveillance and rescue missions to visit a set of target locations by a fix-wing aerial vehicle. Such a problem can be formulated as the variant of the combi- natorial optimization the Traveling salesman problem (TSP) where the target locations have to be connected by Dubins maneuvers. The problem is to determine a sequence of visits to the targets together with the most suitable heading of the vehicle at each target location such that the total tour length is minimized. Dubins proved that the optimal path between two configurations of the Dubins vehicle can be found an- alytically by enumerating six possible maneuvers [2]. However, it is necessary to determine the optimal headings to find the optimal maneuver analytically, which in fact depend on the optimal sequence of visits to the targets. Therefore, this challenging problem is called the Dubins traveling salesman problem (DTSP) rather than just the TSP to distinguish computational challenges arising from the constrained turning radius. The DTSP is NP-hard [3] as for zero minimal turning radius, the problem becomes the TSP. Even though an ordinary formulation of the DTSP provides a solution of the problem to visit a set of target locations by an aircraft, the problem considered in this paper requires to perform specific collecting maneuvers to reliably accomplish the mission. Such a requirement is arising from the need to get a visual contact with the drop-off location. Then, the vehicle Figure 1. An example of the DTSP-CM instance with straight collecting maneuvers in a cargo airdrop mission. Target locations are depicted as small green disks, maneuvers are the red straight line segments, and particular trajectories for a reliable cargo drop-off are in green. The blue curves stand for the Dubins maneuvers which connect the determined collecting maneuvers into the closed tour. is required to move straight ahead during the dropping phase itself. An example solution of such an object dropping mission is depicted in Fig. 1. In this paper, we propose a novel extension of the ordinary DTSP to address the requirement of specific maneuvers for target accomplishment. The introduced problem is called the Dubins traveling salesman prob- lem with collecting maneuvers (DTSP-CM). Further, we study a special case of the DTSP-CM where col- lecting maneuvers are straight line segments (denoted as the DTSP-SCM) and we propose modifications of the existing approaches to the DTSP to solve this constrained variant of the DTSP-CM. The paper is organized as follows. An overview of the related work with various DTSP approaches 34 http://dx.doi.org/10.14311/APP.2016.6.0034 http://ojs.cvut.cz/ojs/index.php/app vol. 6/2016 Dubins Traveling Salesman Problem is provided in Section 2. The proposed problem is formally introduced in Section 3 and modifications of the existing DTSP approaches are proposed in Section 4. Evaluation of the proposed modifications of the existing approaches is presented in Section 5. Finally, conclusion remarks are in Section 6. 2. Related work Various approaches have been proposed to address the DTSP that can be broadly divided into three main classes: 1) decoupled approaches, 2) sampling-based approaches, 3) and evolutionary-based approaches. In this section, a brief overview of representative ap- proaches of each particular class is provided to clarify the context for the introduced DTSP-CM and pro- posed modifications of the particular approaches to solve the constrained variant of the DTSP-CM with straight line collecting maneuvers. Probably the first approach to the DTSP is the Alternating algorithm (AA) introduced in [1] which can be categorized as a decoupled approach, since it addresses the DTSP in two consecutive steps. First, a sequence of visits to the targets is determined, e.g., by a solution of the underlying Euclidean TSP with- out considering the vehicle motion constraint. In the second step, headings at the target locations are es- tablished by applying straight line segments for even segments followed by closing the tour with Dubins maneuvers for odd segments. A similar decoupled strategy has been utilized also in the receding horizon based approach [4] with the horizont of two or three target locations ahead which significantly outperforms the original AA in terms of the solution quality. Sampling-based approaches [5, 6] represent the sec- ond class of existing solutions for the DTSP. These approaches are based on sampling of possible headings into a finite discrete set and the DTSP is transformed into the Generalized Asymmetric TSP (GATSP) and further into the ATSP by Noon-Bean transforma- tion [7]. The resulting ATSP can be then solved by existing solvers such as Concorde [8] or LKH [9]. The third class of the DTSP approaches are evolu- tionary based algorithms [10]. They encoded solutions into individuals in the population and used similar crossover and mutation operators like for the standard TSP. Although evolutionary based approaches can be computationally demanding, their main advantage is the ability to search for a global optima. In [11], au- thors proposed a novel memetic algorithm to improve performance of the evolutionary based approach by utilizing a local optimization method. Recently, the evolutionary multi-objective algo- rithm NSGA-II [12] has been deployed in [13] to ad- dress path planning for data collection in a wireless sensor network that is formulated as the DTSP. The authors consider a bi-objective optimization criterion where the first objective is to minimize the tour length and the second objective is to maximize the time when the vehicle is in the vicinity of the sensor. The prob- lem formulation [13] is similar to the herein proposed DTSP-CM in the considering an influence of the exe- cuted maneuver type at the target locations; however, the authors of [13] do not explicitly constraint the type of the maneuver and rather optimize a bi-objective function. On the other hand, the proposed DTSP-CM problem formulation explicitly restricts the collecting maneuver to be one of the specified type with the aim to improve robustness of the solution execution and the mission accomplishment. 3. Problem Statement The proposed formulation of the Dubins traveling salesman problem with collecting maneuvers (DTSP- CM) is motivated by surveillance missions with fix- wing aerial vehicles where the goal is not only to visit the target locations but also to execute a prescribed maneuver for each target. Similarly to the DTSP, also in the DTSP-CM, the Dubins vehicle [2] is constrained to move only forward at the constant speed v and has the minimum turning radius restricted to ρ. The motion of the vehicle can be described as:  ẋẏ θ̇   = v   cos θsin θ u ρ   , |u| ≤ 1, (1) where u is the control input. The state of the Dubins vehicle q is represented as a triplet q = (x,y,θ) and q ∈ SE(2), where (x,y) ∈ R2 is the vehicle position in a plane and θ ∈ S1 is the vehicle heading at (x,y). The DTSP-CM stands to determine a closed short- est curvature-constrained tour for which all targets are accomplished by executing a maneuver from a specified set of acceptable collecting maneuvers. Each target i is defined by its position pi in the plane and a set of collecting maneuvers Ti. The DTSP-CM is for- mally defined for n target locations P = (p1, . . . ,pn) where pi ∈ R2, corresponding collecting maneuvers T = {T1, . . . ,Tn}, and the minimal turning radius of the vehicle ρ. In the DTSP-CM, the Dubins vehicle is requested to accomplish all given targets by the particular collect- ing maneuvers joined in a single closed tour satisfying the vehicle motion constraints (1). Therefore, it is necessary to determine both the collecting maneuvers M = {τi, . . . ,τn}, τi ∈ Ti, and the sequence of the visits to the targets Σ = {σ1, . . . ,σn}. Notice, a set of possible collecting maneuvers Ti can be infinite, e.g., as an arbitrary selection of the heading angle θ from the set θ ∈ (0, 2π〉 in the ordinary DTSP. The final closed tour consists of the particular collecting maneuvers that are connected to a closed tour by the shortest possible paths respecting the vehicle motion (1), i.e., Dubins maneuvers. Therefore the total tour 35 Petr Váňa, Jan Faigl Acta Polytechnica CTU Proceedings - (a) . Crossing maneuver (b) . Dropping maneuver Figure 2. Examples of straight collecting maneuvers of the DTSP-SCM length L given M and Σ can be computed as: L(M, Σ) = n−1∑ i=1 D(g(τσi ),f(τσi+1 )) + D(g(τσn ),f(τσ1 )) + n∑ i=1 L(τi), (2) where the function f(τi) represents the starting point of the maneuver τi, and g(τi) is the end point of the maneuver, D(g(τi),f(τj)) stands for the length of the Dubins maneuver connecting collecting maneuvers τi and τj, and the symbol L(τi) stands for the length of the τi maneuver. The aim is to minimize the tour length in the DTSP-CM, and therefore, the problem is formulated as the optimization problem formalized in Problem 3.1. Based on the set of collecting maneuvers, the opti- mization problem can be both discrete or piecewise continuous. The problem is not always fully continu- ous, since the length of the Dubins maneuver is also only piecewise continuous [14]. Problem 3.1 (DTSP-CM). minimizeM,Σ L(M, Σ) subject to ∀i : τi ∈Ti 3.1. DTSP-CM with Straight Collecting Maneuvers (DTSP-SCM) Based on the proposed formulation of the DTSP-CM we further investigate its special variant with collect- ing maneuvers limited to straight line segments with a prescribed length and its relative position to the particular target location. Such limited maneuvers are motivated by real scenarios where the vehicle needs to stay at its course while data from sensors are mea- sured or a cargo is dropped to the particular target location. We call this problem the DTSP with straight collecting maneuvers and denote it as the DTSP-SCM in the rest of this paper. Having the possible fulfill- ing maneuver as a straight line segment for which the supporting line is passing the target location, the problem is to find the segment orientation for each target, i.e., we need to determine the vehicle heading at each target location as in the ordinary DTSP. The considered straight collecting maneuver can be specified by two parameters that determine its relative position to the target location: 1) the parameter α represents a distance of the maneuver starting point to the target location; 2) and the parameter β that specifies the end of the collecting maneuver from the target location. For both parameters we can consider positive or negative values according to their relative location to target location defined by the vehicle mo- tion. Thus, positive values denote the positions of the maneuver endpoints that are on the approaching side to the target locations (the vehicle is approaching the target), while the negative values denote the position of the endpoints for which the vehicle recedes the target location. The length of the maneuver L(τ) is always positive, and therefore, we define it as L(τ) = |α−β|, L(τ) > 0. (3) We consider two types of straight collecting maneu- vers. The first type represents a situation where the target location lies directly on the collecting maneu- ver. Such a maneuver is called the crossing maneuver (α > 0 and β < 0) and it is motivated by robotic sce- narios to precisely measure some location and where the vehicle cannot change its heading during the sens- ing phase. An example of the crossing maneuver is depicted in Fig. 2a. The second type of straight collecting maneuvers is a so-called dropping maneuver. In this case, the target location is at the maneuver direction, but not necessary on the maneuver itself, α > 0 and β > 0. This type of maneuver can be used for planning object dropping, since the vehicle is required to focus the target while moving on the straight line segment to ensure a precise airdrop location [15]. After the object dropping, the vehicle can continue in an arbitrary direction and does not need to achieve the target location itself. An example of the dropping maneuver is depicted in Fig. 2b. Formally, the DTSP-SCM is a variant of the op- timization Problem 3.1. In contrast to the general DTSP-CM, the straight collecting maneuvers have a constant length, since the parameters α and β are fixed for the particular problem instance. Therefore, the total length L(M) of all collecting maneuvers can be determined L(M) = n∑ i=1 L(τi) = n∑ i=1 |α−β| (4) and its value is constant that can be computed before solving the particular instance of the DTSP-SCM. This property enables to consider only Dubins maneuvers length while minimizing the tour length, which significantly simplifies possible methods address- ing the DTSP-SCM. Furthermore, it is possible to modify approaches for the DTSP to address the pro- posed DTSP-SMC due to the constant length of the collecting maneuver. Proposed modifications for ex- isting DTSP approaches are presented in the next section. 36 vol. 6/2016 Dubins Traveling Salesman Problem 4. Solution of the DTSP-SCM The main advantage of the proposed DTSP-SCM over more general the DTSP-CM is that it is possible to solve the DTSP-SCM in a relatively straightforward way by approaches developed for the DTSP with only slight modifications. This is possible because the length of the individual collecting maneuver is con- stant, and thus the sum of all collecting maneuvers (4) is a constant value and it is not needed to consider indi- vidual lengths during the optimization process. Hence, we can build solvers for the DTSP-SCM on the existing methods for the DTSP. The proposed modifications of the selected representative approaches for each of three classes of the DTSP approaches introduced in Section 2 are presented in this section. For decoupled approaches, we can still utilize a solu- tion of the Euclidean TSP to determine the sequence of visits to the targets. However, we can expect that such a sequence can be farther from the optimum when the collecting maneuvers are getting longer. A modification of the original AA [1] to utilize collecting maneuvers is straightforward. In solving the ordinary DTSP, vehicle headings are determined for each target location. Instead of that, we can determine directions of collecting maneuvers using the direction in odd segments. Then, we can connect even segments by the Dubins maneuvers to create a closed tour, and thus solve the DTSP-SCM. The sampling-based approach [5] is another option how to address the proposed DTSP-SCM. Instead of sampling the vehicle heading at each target location, we need to sample a set of collecting maneuvers cor- responding to each particular target location in the DTSP-SCM. In [5], the authors propose to create a distance graph which is an instance of the GATSP. For the proposed DTSP variant with collecting ma- neuvers, the resulting instance of the GATSP has twice the number of vertices. However, the size of the GATSP instance can be reduced back to the original size by a simple transformation as follows. The length of the utilized collecting maneuver is added to the length of the Dubins maneuver which together form a continuous path. Similarly the evolutionary-based algorithms [10, 11] are also suitable for a straightforward extension to address the proposed DTSP-SCM. Here, the chromo- some representing the individual needs to be modified to contain the collecting maneuver instead of the vehi- cle heading only. In addition, the evaluation function needs to be modified to respect the total tour length according to (2). 5. Evaluation Results Several problem instances of the DTSP-SCM have been solved to demonstrate usability of the newly proposed variant of the DTSP with straight collecting maneuvers. A small quadrotor helicopter has been simulated in the realistic Gazebo simulator [16] with a physical model based on the Pixhawk flight controller. Figure 3. Simulated quadrotor helicopter dropping red ball object. An example of graphical output from the simulator is depicted in Fig. 3. The helicopter has been requested to fly at the altitude 20 m with the speed 5 m.s-1 and the minimal turning radius has been set to ρ = 7 m to imitate realistic conditions of a real aircraft. The dropping distance has been set to approximately 9.5 m and the used straight collecting maneuvers have the parameters: α = 12 m and β = 8 m. We have conducted two types of evaluation sce- narios. The first scenario is designed to validate a precision of the airdrop maneuvers without and with the explicit consideration of the straight collecting maneuvers in the proposed DTSP-SCM. The second scenario is designed to evaluate performance of the proposed modifications of the existing solutions for the DTSP in solving instances of the introduced DTSP- SCM. 5.1. Precision of the Airdrop First, we found solutions of the ordinary DTSP and the proposed DTSP-SCM using the sampling based approach with the LKH solver [17]. The evaluation instance is generated for 10 target locations (n = 10) with the relative density d = 0.3 defined as: d = ρ √ n s , (5) where s is the size of the bounding box where all target locations are positioned. We consider solution of 10 random instances with n = 10 solved by each particular approach (DTSP and DTSP-SCM) to obtain statistically significant results. Hence, 100 simulated intersection of the dropped ob- ject with ground have been recorded. In the used simulated environment, a limited precision of the GPS and all the motors were considered except of air resis- tance. The obtained locations of the dropped object are visualized in Fig. 4 where a direction of all drop- ping maneuvers is rotated to the same orientation to draw all locations within the same figure. It can be easily seen that objects dropped without explicit consideration of the straight collecting maneuvers (i.e., a solution of the ordinary DTSP) are often dropped with a longer distance error from the desired target 37 Petr Váňa, Jan Faigl Acta Polytechnica CTU Proceedings ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ●● ● ● ●● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●● ● −10 −5 0 5 −5 0 5 10 xerror [m] y e rr or [ m ] Method ● DTSP DTSP−SCM Airdrop Target Figure 4. Locations of the dropped object to the target location as a result of the performing DTSP solution and a solution of the newly introduced DTSP- SCM. All measurements are normalized by the position of the airdrop and the target location. 0.0 2.5 5.0 7.5 10.0 12.5 0255075100 Percent of dataset [%] E rr or d is ta nc e [m ] Solver DTSP DTSP−SCM Figure 5. Precision of the airdrop maneuver obtained by solution of the DTSP and the newly proposed formulation of the DTSP-SCM location than for the case when the trajectory is found as a solution of the DTSP-SCM. The distance of the real position of the dropped object to its expect posi- tion at the target location is depicted in Fig. 5. The error for the solutions of the DTSP-SCM is almost half of the error for the DTSP. 5.2. Performance of DTSP Approaches in the DTSP-SCM The proposed modifications of the existing approaches for the DTSP to address the introduced DTSP-SCM have been evaluated in a series of DTSP-SCM in- stances according to the number of target locations n and their density d determined by (5). Six algo- rithms for the DTSP-SCM has been compared. In particular, the proposed modifications of approaches: Alternating Algorithm (AA) [1], Local Iterative Op- timization [18], Genetic algorithm [10], Memetic al- gorithm [11], and sampling-based approach [6] with the LKH solver [17] (denoted as the Sampling+LKH) and with the optimal Concorde solver [8], denoted as the Sampling+Concorde. Due to high computational requirements of the genetic, memetic, and sampling- ● ● ● ● ● ● ● ● ● ● ●● ● ● ● ● ● ● ● ● ● ● ● ● 0 1 2 3 10 20 50 100 Number of target positions R at io o f so lu ti on l en gt h to t he r ef er en ce l en gt h Method ● ● ● ● ● ● AA LIO Genetic Memetic Sampling+LKH Sampling+Con. Figure 6. Average ratios of the solution length to the reference length of the best found solution depending on the number of target locations with the relative density d = 0.3 ● ● ● ● ●● ● ● ● ● ●● ● ● ● ● ● ● 0 1 2 0.2 0.3 0.4 Density of target positions R at io o f so lu ti on l en gt h to t he r ef er en ce l en gt h Method ● ● ● ● ● ● AA LIO Genetic Memetic Sampling+LKH Sampling+Con. Figure 7. Average ratios of the solution length to the reference length of the best found solution depending on the density of n = 20 target locations based algorithms, their computational time has been limited to 1 hour. For sampling based approach, a series of solutions is found with iteratively increasing number of samples until the time limit is reached [19]. Therefore, all the algorithms provide a solution, al- beit more demanding approach (i.e., based on the Concorde solver) for less samples than faster heuristic LKH solver, which solves more iterations within the same time limit. The considered number of target locations n has been selected from the set n ∈ {10, 20, 50, 100} and the density d has been selected from the set d ∈ {0.2, 0.3, 0.4}. For each particular scenario defined by the n and d, 20 random instances were generated. For each problem instance, the best found solution (among all solutions found by all approaches) has been selected as a reference solution that allows to aggregate the results into a single solution quality indicator as the ratio of the length of the found tour to the length of the reference solution. Average ratios and standard deviations (shown as error bars) are presented in Fig. 6 and Fig. 7 depend- ing on the number of target locations n and for the particular density of the target locations d, respec- tively. The results indicate that superior solutions 38 vol. 6/2016 Dubins Traveling Salesman Problem are found by the sampling-based approaches. The LKH heuristic approach provides better results than the Concorde solver because of limited computational time, and thus solutions with finer discretizations are not computed within the dedicated time limit by the optimal Concorde solver. 6. Conclusion In this paper, we propose a new variant of the DTSP formulation to address specific requirements of the collecting maneuvers to accomplish visitation of each target location. The proposed variant of the DTSP is called the Dubins traveling salesman problem with collecting maneuvers (DTSP-CM). Further, we con- sidered collecting maneuvers restricted to straight line segments with fixed length and its specified relative position to the target that is denoted as the DTSP with straight collecting maneuvers (DTSP-SCM). For the DTSP-SCM, we propose modifications of the exist- ing approaches to the DTSP to address the prescribed constrained collecting maneuvers. The proposed mod- ifications of the algorithms have been evaluated in several scenarios including evaluation of the proposed problem formulation to the precision of the cargo delivery in airdrop maneuvers. The presented re- sults indicate that the proposed formulation improves the reliability of the mission accomplishment. More- over, the presented evaluation results also provide an overview of the performance of particular approaches to the DTSP in the DTSP-SCM formulation, where the sampling based methods provide the best found solution among the evaluated approaches. Acknowledgements The presented work has been supported by the Czech Science Foundation (GAČR) under research project No. 16-24206S. The support of grant No. SGS16/235/OHK3/3T/13 to Petr Váňa is also gratefully acknowledged. References [1] K. Savla, E. Frazzoli, F. Bullo. On the point-to-point and traveling salesperson problems for Dubins’ vehicle. In Proceedings of the American Control Conference, pp. 786–791. IEEE, 2005. doi:10.1109/ACC.2005.1470055. [2] L. E. Dubins. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. American Journal of Mathematics pp. 497–516, 1957. doi:10.2307/2372560. [3] J. Le Ny, E. Frazzoli, E. Feron. The curvature-constrained traveling salesman problem for high point densities. In 46th IEEE Conference on Decision and Control, pp. 5985–5990. 2007. doi:10.1109/CDC.2007.4434503. [4] X. Ma, D. A. Castanon. Receding horizon planning for Dubins traveling salesman problems. In 45th IEEE Conference on Decision and Control, pp. 5453–5458. 2006. doi:10.1109/CDC.2006.376928. [5] J. T. Isaacs, D. J. Klein, J. P. Hespanha. Algorithms for the traveling salesman problem with neighborhoods involving a dubins vehicle. In American Control Conference (ACC), pp. 1704–1709. IEEE, 2011. doi:10.1109/ACC.2011.5991501. [6] K. J. Obermeyer, P. Oberlin, S. Darbha. Sampling- based path planning for a visual reconnaissance unmanned air vehicle. Journal of Guidance, Control, and Dynamics 35(2):619–631, 2012. doi:10.2514/1.48949. [7] C. E. Noon, J. C. Bean. A lagrangian based approach for the asymmetric generalized traveling salesman problem. Operations Research 39(4):623–632, 1991. doi:10.1287/opre.39.4.623. [8] D. Applegate, R. Bixby, V. Chvátal, W. Cook. CONCORDE TSP Solver, 2003. [cited 31 Oct 2016]. [9] K. Helsgaun. An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic. European Journal of Operational Research 126(1):106–130, 2000. doi:10.1016/S0377-2217(99)00284-2. [10] X. Yu, J. Hung. A genetic algorithm for the dubins traveling salesman problem. In IEEE International Symposium on Industrial Electronics, pp. 1256–1261. 2012. doi:10.1109/ISIE.2012.6237270. [11] X. Zhang, J. Chen, B. Xin, Z. Peng. A memetic algorithm for path planning of curvature-constrained uavs performing surveillance of multiple ground targets. Chinese Journal of Aeronautics 27(3):622–633, 2014. doi:10.1016/j.cja.2014.04.024. [12] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE transactions on evolutionary computation 6(2):182–197, 2002. doi:10.1109/4235.996017. [13] D. G. Macharet, J. W. Monteiro, G. R. Mateus, M. F. Campos. Bi-objective data gathering path planning for vehicles with bounded curvature. Computers & Operations Research 2016. doi:10.1016/j.cor.2016.07.004. [14] X. Goaoc, H.-S. Kim, S. Lazard. Bounded-curvature shortest paths through a sequence of points using convex optimization. SIAM Journal on Computing 42(2):662–684, 2013. doi:10.1137/100816079. [15] C. W. Hewgley, O. Yakimenko. Precision guided airdrop for vertical replenishment of naval vessels. In Proceedings of the 20th AIAA Aerodynamic Decelerator Systems Technology Conference, pp. 4–7. 2009. doi:10.2514/6.2009-2995. [16] Gazebo robot simulator. [cited 31 Oct 2016]. [17] K. Helsgaun. LKH solver 2.0.7. www.akira.ruc.dk/~keld/research/LKH. [cited 31 Oct 2016]. [18] P. Váňa, J. Faigl. On the Dubins Traveling Salesman Problem with Neighborhoods. International Conference on Intelligent Robots and Systems (IROS) pp. 4029–4034, 2015. doi:10.1109/IROS.2015.7353945. [19] P. Váňa, J. Faigl. On sampling based methods for the dubins traveling salesman problem with neighborhoods. Acta Polytechnica CTU Proceedings 2(2):57–61, 2015. doi:10.14311/APP.2015.1.0057. 39 http://dx.doi.org/10.1109/ACC.2005.1470055 http://dx.doi.org/10.2307/2372560 http://dx.doi.org/10.1109/CDC.2007.4434503 http://dx.doi.org/10.1109/CDC.2006.376928 http://dx.doi.org/10.1109/ACC.2011.5991501 http://dx.doi.org/10.2514/1.48949 http://dx.doi.org/10.1287/opre.39.4.623 http://dx.doi.org/10.1016/S0377-2217(99)00284-2 http://dx.doi.org/10.1109/ISIE.2012.6237270 http://dx.doi.org/10.1016/j.cja.2014.04.024 http://dx.doi.org/10.1109/4235.996017 http://dx.doi.org/10.1016/j.cor.2016.07.004 http://dx.doi.org/10.1137/100816079 http://dx.doi.org/10.2514/6.2009-2995 www.akira.ruc.dk/~keld/research/LKH http://dx.doi.org/10.1109/IROS.2015.7353945 http://dx.doi.org/10.14311/APP.2015.1.0057 Acta Polytechnica CTU Proceedings 6:34–39, 2016 1 Introduction 2 Related work 3 Problem Statement 3.1 DTSP-CM with Straight Collecting Maneuvers (DTSP-SCM) 4 Solution of the DTSP-SCM 5 Evaluation Results 5.1 Precision of the Airdrop 5.2 Performance of DTSP Approaches in the DTSP-SCM 6 Conclusion Acknowledgements References