Path planning for unmanned aerial vehicles in surveillance tasks under wind fields

Abstract

The optimal path planning for fixed-wing unmanned aerial vehicles (UAVs) in multi-target surveillance tasks (MTST) in the presence of wind is concerned. To take into account the minimal turning radius of UAVs, the Dubins model is used to approximate the dynamics of UAVs. Based on the assumption, the path planning problem of UAVs in MTST can be formulated as a Dubins traveling salesman problem (DTSP). By considering its prohibitively high computational cost, the Dubins paths under terminal heading relaxation are introduced, which leads to significant reduction of the optimization scale and difficulty of the whole problem. Meanwhile, in view of the impact of wind on UAVs’ paths, the notion of virtual target is proposed. The application of the idea successfully converts the Dubins path planning problem from an initial configuration to a target in wind into a problem of finding the minimal root of a transcendental equation. Then, the Dubins tour is derived by using differential evolution (DE) algorithm which employs random-key encoding technique to optimize the visiting sequence of waypoints. Finally, the effectiveness and efficiency of the proposed algorithm are demonstrated through computational experiments. Numerical results exhibit that the proposed algorithm can produce high quality solutions to the problem.

Keywords

unmanned aerial vehicle / path planning in wind field / Dubins traveling salesman problem / terminal heading relaxation / differential evolution

References

[1] PengZ-h, WuJ-p, ChenJie. Three-dimensional multi-constraint route planning of unmanned aerial vehicle low-altitude penetration based on coevolutionary multi-agent genetic algorithm [J]. Journal of Central South University of Technology, 2011, 18(5): 1502-1508

[2] ZhangX, BaiY-q, ChenJ, XinBin. Differential evolution based receding horizon control for UAV motion planning in dynamic environments [J]. Robot, 2013, 35(1): 107-114

[3] YuH L, BeardR W, ArgyleM, ChamberlainC. Probabilistic path planning for cooperative target tracking using aerial and ground vehicles [C]. Proceedings of the American Control Conference, 2011, Piscataway, NJ, USA, IEEE: 4673-4678

[4] DubinsL E. On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents [J]. American Journal of Mathematics, 1957, 79(3): 497-516

[5] TangZ-j, Özgüner. Motion planning for multiagent surveillance with mobile sensor agents [J]. IEEE Transactions on Robotics, 2005, 21(5): 898-908

[6] MacharetD G, Alves NetoA, da Camara NetoV F, CamposM F M. Nonholonomic path planning optimization for Dubins’ vehicle [C]. Proceedings of the IEEE International Conference on Robotics and Automation, 2011, Piscataway, NJ, USA, IEEE: 4208-4213

[7] SavlaK, FrazzoliE, BulloF. On the point-to-point and traveling salesperson problems for Dubins’ vehicle [C]. Proceedings of the American Control Conference, 2005, Piscataway, NJ, USA, IEEE: 786-791

[8] le NyJ, FeronE, FrazzoliE. On the Dubins travelling salesman problem [J]. IEEE Transactions on Automatic Control, 2012, 57(1): 265-270

[9] HelsgaunK. An effective implementation of the Lin-Kernighan traveling salesman heuristic [J]. European Journal of Operational Research, 2000, 126(1): 106-130

[10] le NyJPerformance optimization for unmanned vehicle systems [D], 2008, Cambridge, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology

[11] YuX, HungJ Y. A genetic algorithm for the dubins traveling salesman problem [C]. Proceedings of the IEEE International Symposium on Industrial Electronics. IEEE, 20121256-1261

[12] BoissonnatJ D, BuiX NAccessibility region for a car that only moves forward along optimal paths [R], 1994, France, INRIA

[13] RathinamS, SenguptaR, DarbhaS. A resource allocation algorithm for multivehicle systems with nonholonomic constraints [J]. IEEE Transactions on Automation Science and Engineering, 2007, 4(1): 98-104

[14] McneelyR L, IyerR V. Tour Planning for an unmanned air vehicle under wind conditions [J]. Journal of Guidance, Navigation and Control, 2007, 30(5): 1299-1306

[15] McgeeT G, SpryS, HedrickJ K. Optimal path planning in a constant wind with a bounded turning rate [C]. Proceedings of AIAA Guidance, Navigation, and Control Conference, 2005, San Francisco, AIAA: 3456-3466

[16] McgeeT G, HedrickJ K. Path planning and control for multiple point surveillance by an unmanned aircraft in wind [C]. Proceedings of the American Control Conference, 2006, Piscataway, NJ, USA, IEEE: 4261-4266

[17] TechyL, WoolseyC A. Minimum-time path planning for unmanned aerial vehicles in steady uniform winds [J]. Journal of Guidance, Control and Dynamics, 2009, 32(6): 1736-1746

[18] MendesJ J M, GonçalvesJ F, ResendeM G C. A random key based genetic algorithm for the resource constrained project scheduling problem [J]. Computers & Operations Research, 2009, 36(1): 92-109

[19] DasS, SuganthanP N. Differential evolution: A survey of the state-of-the-art [J]. IEEE Transactions on Evolutionary Computation, 2011, 15(1): 4-31