Journal of Aeronautical Engineering

Journal of Aeronautical Engineering

Integrated Task Assignment and Path Planning with Moving Targets Based on an Innovative Linear Programming Approach and Dubins Curves

Document Type : Original Article

Authors
1 Assistant Professor, Faculty of Aerospace Engineering, Shahid Sattari Aeronautical University of Science and Technology, Tehran, Iran
2 IRAN, Tehran
Abstract
Recent developments in mission implementation and agent control have drawn attention to the performing of cooperative missions. Decision-making systems are among the most important parts of such missions. The aim of these systems is efficient task assignment and path planning. This paper combines a task assignment approach and a path planning method to tackle collaborative problems. The task assignment approach, used in this paper, is based on an improved linear programming approach for its high accuracy. The path planning method is based on Dubins curve to handle the limitation movements of fixed-wing fighters, investigated in this paper. The proposed methods perform based on the utilized fighter’s performance characteristics and flight constraints in a dynamic environment with moving targets. The path planning approach is based on specific constraints, including certain output vectors of each point as well as input ones to the target points, minimum rotational angle, and performance factors of fighters. In the next step, Dubins path planning output is used as the necessary coefficient to solve the task assignment problem of cooperative fighters. By using a heuristic hierarchical approach based on linear programming, a comprehensive path planning and task assignment of a fleet of fighters is completed. The presented results show optimal performance and higher speed to solve rather than the classical approaches, which is capable to cover the dynamic environment as well.
Keywords

[1]        R. G. Grant, Flight: The Complete History of Aviation: DK; Updated, Revised edition (May 2, 2017), 2017.
[2]        T. Shima and C. Schumacher, Assigning cooperating UAVs to simultaneous tasks on consecutive targets using genetic algorithms, Journal of the Operational Research Society, vol. 60, pp. 973-982, 2009.
[3]        D. W. Casbeer and R. W. Holsapple, Column generation for a UAV assignment problem with precedence constraints, International Journal of Robust and Nonlinear Control, vol. 21, pp. 1421-1433, 2011.
[4]        C. Schumacher, P. R. Chandler, M. Pachter, and L. S. Pachter, Optimization of air vehicles operations using mixed-integer linear programming, Journal of the Operational Research Society, vol. 58, pp. 516-527, 2007.
[5]        Y. NI, D.-Y. ZHOU, Y.-h. MA, and B.-c. HE, The Air-to-Ground Tasks Assignment for Multi-UAV based Mixed Integer Linear Programming [J], Fire Control and Command Control, vol. 11, 2008.
[6]        J. Bellingham, Y. Kuwata, and J. How, "Stable receding horizon trajectory control for complex environments," in AIAA Guidance, Navigation, and Control Conference and Exhibit, p. 5635, 2003.
[7]        M. Gendreau, G. Laporte, and J.-Y. Potvin, "Metaheuristics for the capacitated VRP," in The vehicle routing problem, ed: SIAM, 2002, pp. 129-154.
[8]        M. Alighanbari, Task assignment algorithms for teams of UAVs in dynamic environments, Massachusetts Institute of Technology, 2004.
[9]        M. A. Darrah, W. Niland, and B. Stolarik, "Multiple UAV Task Allocation for an Electronic Warfare Mission Comparing Genetic Algorithms and Simulated Annealing (Preprint)," INSTITUTE FOR SCIENTIFIC RESEARCH FARIMONT WV2006.
[10]      E. Edison and T. Shima, Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms, Computers & Operations Research, vol. 38, pp. 340-356, 2011.
[11]      V. Shaferman and T. Shima, Unmanned aerial vehicles cooperative tracking of moving ground target in urban environments, Journal of guidance, control, and dynamics, vol. 31, pp. 1360-1371, 2008.
[12]      X. Fu, P. Feng, and X. Gao, Swarm UAVs Task and Resource Dynamic Assignment Algorithm Based on Task Sequence Mechanism, IEEE Access, vol. 7, pp. 41090-41100, 2019.
[13]      K. A. Ghamry, M. A. Kamel, and Y. Zhang, "Multiple UAVs in forest fire fighting mission using particle swarm optimization," in 2017 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 1404-1409, 2017.
[14]      J. Gu, T. Su, Q. Wang, X. Du, and M. Guizani, Multiple moving targets surveillance based on a cooperative network for multi-UAV, IEEE Communications Magazine, vol. 56, pp. 82-89, 2018.
[15]      A. T. Hafez and M. A. Kamel, Cooperative task assignment and trajectory planning of unmanned systems via hflc and pso, Unmanned Systems, vol. 7, pp. 65-81, 2019.
[16]      Z. Jia, J. Yu, X. Ai, X. Xu, and D. Yang, Cooperative multiple task assignment problem with stochastic velocities and time windows for heterogeneous unmanned aerial vehicles using a genetic algorithm, Aerospace Science and Technology, vol. 76, pp. 112-125, 2018.
[17]      X. Jiang, Q. Zhou, and Y. Ye, "Method of task assignment for UAV based on particle swarm optimization in logistics," in Proceedings of the 2017 International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence, pp. 113-117, 2017.
[18]      M. Zhu, X. Du, X. Zhang, H. Luo, and G. Wang, Multi-UAV Rapid-Assessment Task-Assignment Problem in a Post-Earthquake Scenario, IEEE Access, vol. 7, pp. 74542-74557, 2019.
[19]      X. Hu, H. Ma, Q. Ye, and H. Luo, Hierarchical method of task assignment for multiple cooperating UAV teams, Journal of Systems Engineering and Electronics, vol. 26, pp. 1000-1009, 2015.
[20]      Z. Zhao, J. Yang, Y. Niu, Y. Zhang, and L. Shen, A Hierarchical Cooperative Mission Planning Mechanism for Multiple Unmanned Aerial Vehicles, Electronics, vol. 8, p. 443, 2019.
[21]      Liu, Wei, Z. Zheng, and K.-Y. Cai, Bi-level programming based real-time path planning for unmanned aerial vehicles, Knowledge-Based Systems, vol. 44, pp. 34-47, 2013.
[22]      B. D. Song, K. Park, and J. Kim, Persistent UAV delivery logistics: MILP formulation and efficient heuristic, Computers & Industrial Engineering, vol. 120, pp. 418-428, 2018.
[23]      S. Perez-Carabaza, E. Besada-Portas, J. A. Lopez-Orozco, and M. Jesus, Ant colony optimization for multi-UAV minimum time search in uncertain domains, Applied Soft Computing, vol. 62, pp. 789-806, 2018.
[24]      Y. Chen, D. Yang, and J. Yu, Multi-UAV Task Assignment With Parameter and Time-Sensitive Uncertainties Using Modified Two-Part Wolf Pack Search Algorithm, IEEE Transactions on Aerospace and Electronic Systems, vol. 54, pp. 2853-2872, 2018.
[25]      E. Adamey, A. E. Oğuz, and Ü. Özgüner, Collaborative multi-msa multi-target tracking and surveillance: a divide & conquer method using region allocation trees, Journal of Intelligent & Robotic Systems, vol. 87, pp. 471-485, 2017.
[26]      W. Meng, Z. He, R. Su, P. K. Yadav, R. Teo, and L. Xie, Decentralized multi-UAV flight autonomy for moving convoys search and track, IEEE Transactions on Control Systems Technology, vol. 25, pp. 1480-1487, 2016.
[27]      H. Ergezer and M. Leblebicioğlu, "3D path planning for UAVs for maximum information collection. Unmanned Aircraft Systems (ICUAS)," in 2013 International Conference on, 2013.
[28]      O. Souissi, R. Benatitallah, D. Duvivier, A. Artiba, N. Belanger, and P. Feyzeau, "Path planning: A 2013 survey," in Proceedings of 2013 International Conference on Industrial Engineering and Systems Management (IESM), pp. 1-8, 2013.
[29]      D. González, J. Pérez, V. Milanés, and F. Nashashibi, A review of motion planning techniques for automated vehicles, IEEE Transactions on Intelligent Transportation Systems, vol. 17, pp. 1135-1145, 2015.
[30]      K. Ok, S. Ansari, B. Gallagher, W. Sica, F. Dellaert, and M. Stilman, "Path planning with uncertainty: Voronoi uncertainty fields," in 2013 IEEE International Conference on Robotics and Automation, pp. 4596-4601, 2013.
[31]      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, vol. 79, p. 497, Jul 1957.
[32]      J. Reeds and L. Shepp, Optimal paths for a car that goes both forwards and backwards, Pacific journal of mathematics, vol. 145, pp. 367-393, 1990.
[33]      L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, Probabilistic roadmaps for path planning in high-dimensional configuration spaces, IEEE transactions on Robotics and Automation, vol. 12, pp. 566-580, 1996.
[34]      Y. Kuwata, A. Richards, T. Schouwenaars, and J. P. How, "Decentralized robust receding horizon control for multi-vehicle guidance," in 2006 American Control Conference, p. 6 pp., 2006.
[35]      T. R. Mehta and M. Egerstedt, An optimal control approach to mode generation in hybrid systems, Nonlinear Analysis: Theory, Methods & Applications, vol. 65, pp. 963-983, 2006.
[36]      G. Flores, I. Lugo-Cárdenas, and R. Lozano, "A nonlinear path-following strategy for a fixed-wing MAV," in 2013 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 1014-1021, 2013.
[37]      I. Lugo-Cárdenas, G. Flores, S. Salazar, and R. Lozano, "Dubins path generation for a fixed wing UAV," in 2014 International conference on unmanned aircraft systems (ICUAS), pp. 339-346, 2014.
[38]      ع. رودباری م. دهقانی محمدآبادی. ر. اسدی, اختصاص وظایف به تیم پهپادهای همکار با رویکرد ابتکاری برنامه­ریزی فازی خطی صحیح در محیط دینامیک با اهداف متحرک، مجله مهندسی مکانیک ایران، 1398
[39]      .Yan, Peng, et al. "A Fixed Wing UAV Path Planning Algorithm Based On Genetic Algorithm and Dubins Curve Theory." MATEC Web of Conferences. Vol. 179. EDP Sciences, 2018.
Volume 22, Issue 2
December 2020
Pages 197-210

  • Receive Date 18 April 2021
  • Revise Date 01 August 2021
  • Accept Date 28 September 2021