Multi-UAV Path Planning Algorithms: Comparison
View Latest Version
Please note this is a comparison between Version 3 by Lindsay Dong and Version 2 by Lindsay Dong.

While several developments have taken place in the field of autonomus guidance and navigation techniques for Unmanned Aerial Vehicle (UAV) systems, obtaining an optimal path planning algorithm remains elusive. With multiple UAVs involvement in missions, these difficulties increase significantly leading to the need for collision free navigation routes from the UAVs' initial positions to target points. Consequently, this entry focuses specifically on Multi-UAV Path Planning Algorithms utilizing Bio -Inspired Algorithms. The findings indicated that bio-inspired algorithms possess substantial potential in addressing multipoint path planning issues and delineate new prospects and implications for the enhancement of this active research domain.

  • unmanned aerial vehicle
  • UAV
  • Path Planning

1. Introduction

The need for small autonomous unmanned aerial vehicles (UAVs) has significantly increased since such UAVs can handle dull, dirty, and dangerous tasks for humans. They are applied in many fields [1] including firefighting, precision agriculture, and asset inspection. UAV operational experience proves that their technology offers great advantages, such as performing at superior precision, acquiring high-quality data, maneuvering with extreme capabilities, and reducing operational risk. On the other hand, limited battery lifetime, slow speed, and light payload are among the main concerns that deter wider adoption of UAVs by more public and private sectors [2].
To overcome the above limitations, the focus is shifting to collaborative UAV systems. In fact, most of the UAV applications, such as reconnaissance and disaster response, are better handled by a multiple UAV (multi-UAV) system. A multi-UAV system is more efficient and capable to accomplish difficult missions and cover wider areas than a single UAV system [3]. Additionally, in a single-UAV system, a UAV going down during the mission represents a failure, while an out-of-control UAV is not a problem for multi-UAV systems. Thus, a multi-UAV system is more reliable than a system with a single robot, as multiple robots provide additional redundancy. Furthermore, using sizable UAVs to augment a single-UAV system extends area coverage only to a point. Conversely, multi-UAV systems may quickly expand their operational range [4][5]. Despite these advantages, multi-UAV systems are associated with more challenges due to the need for coordination and communication between the fleet members especially while navigating through the environment to ensure collision-free area coverage [6].
Although the UAV flight control architecture is well established, there are still many challenges in designing autonomous navigation systems for UAVs that can find the shortest path between two points while optimizing a set of performance measures. The trade-offs between feasibility, safety, power consumption, and the computation limitation and highly non-linear dynamics that characterize these devices are what make the UAV path planning problem a daunting task [7]. Therefore, a plethora of path-planning algorithms for UAVs has been proposed, e.g., [8][9][10][11][12][13], based on classical and bio-inspired approaches.
Bio-inspired approaches are showing a remarkable increase in utilization to overcome the multi-UAV path planning problem, with a counterpart decrease in classical algorithms’ popularity [9][14]. Classical path planning approaches, such as the cell decomposition approach [15] and artificial potential field [16], are limited by their high processing cost, long running time, and inability to respond to environmental uncertainty [9][14]. On the other hand, bio-inspired heuristics have demonstrated the capacity to overcome these shortcomings [17][18] since they can learn and adapt similar to biological systems, enabling them to handle environmental uncertainty [8][9][11], especially in parallel processing environments [14]. 

2. The Multi-UAV Path Planning Problem

Path planning is an important task of any navigation system, which usually encompasses three functions: localization, mapping, and path planning [18][19]. In the robotics context, path planning involves finding a route that enables a robot to move from a starting location to a goal [9][19]. The problem is an NP-hard problem (nondeterministic polynomial-time) [18][20]. The multi-robot path planning problem can be defined as follows: given a set of m robots in a k-dimensional workspace, each with an initial starting configuration (e.g., position) and the desired goal configuration, determine the path each robot should take to reach its goal while avoiding collisions with obstacles and other robots in the workspace [5]. While single-robot path planning finds an optimal or suboptimal path for the robot from the initial position to the target position based on optimization criteria [21], multi-robot path planning aims to find a path for each robot, between specific start and goal locations, while optimizing the overall system global cost function [22]. The problem grows in complexity as more robots participate in the mission [22][23][24]. Furthermore, unlike single-robot path planning, multi-robot path planning needs to deal with the robot collision problem as a moving robot might be seen as a dynamic impediment [25].
Since a UAV is viewed as a flying robot, the discussion of multi-robot problems also applies to multi-UAV systems [26] but with an added layer of complexity due to their flying and limited resources features. The multi-UAV path planning problem is usually viewed as a form of the multiple Traveling Salesman Problem (TSP). The TSP with multiple UAVs can be seen as a task allocation problem to optimize a certain set of performance measures by assigning each target, or group of targets, to one UAV [27]. Performance can be measured based on the ability to find the shortest, cheapest, or safest paths to help achieve a system-wide goal [7]. Another well-known problem that has been extended to multi-UAVs is Vehicle Routing Problem (VRP). VRP is a generalization of the TSP problem [28]. The TSP and the VRP are both NP-Hard routing problems [29]. The primary distinction between a TSP and a VRP is that the salesperson must return to the initial location after visiting several points [30]. VRP is typically employed when delivering products from a central depot to consumers who have ordered those products [28]. Some applications consider a hybrid model that includes ground vehicles to support UAV routes [31] such as the study [32][33].
Figure 1 shows the main parameters that are usually used to describe the multi-UAV path planning problem which includes:
/media/item_content/202307/64a21d7624c1emathematics-11-02356-g001.png
Figure 1. The main factors of the multi-UAV path planning problem.
  • Origin/starting point/source: It is also known as the depot in the traveling salesman problem (TSP) [34][35]. It represents the current location of the UAV or the initial location from where the UAV should start traveling. A path planning problem for a single UAV system usually requires one starting location, however, for a multi-UAV system, there might be a shared starting location or several starting locations.
The open challenges related to time efficiency and computational burden associated with the multi-UAV path planning problem have attracted researchers to set up different approaches that encompass traditional and bio-inspired techniques. These techniques differ mainly in the choices of how these techniques implement coordination scheme, planning mode, navigation scope, and objective function, as shown in Figure 3:
/media/item_content/202307/64a21da2d9cfbmathematics-11-02356-g003.png
Figure 3. Taxonomy of bio-inspired multi-UAV path planning algorithms.
  • Mode: The path planning mode can be offline or online. An offline planner constructs the path before motion begins. In contrast, an online planner incrementally constructs the plan while the UAV is in motion [48][49]. Typically, it is recommended to combine the two approaches to maximize their strengths [17].
  • Goal/end point/destination/target: It represents the final location where the UAV should stop. There can be one or more goals. Goals can be known or unknown in advance. They can be static, i.e., stationary throughout the mission, or dynamic. i.e., change their locations over time [4]. The schemes of goals can be one following:
    • One shared goal for all UAVs: There is one goal, and all UAVs will have to visit this goal.
  • Coordination: The coordination process in a multi-UAV system describes the control structure and communications scheme between the vehicles.
    • Control can occur in a centralized or decentralized manner [50][51]. In centralized planning approaches, a single control agent acts as a leader to ensure coordination among the entire team of UAVs [18][51]. This central agent (e.g., a control station) usually has global knowledge about network status and each robot’s interactions [18][50]. Decentralized architectures can be further divided into distributed architectures and hierarchical architectures. In hierarchical coordination, multiple-leader robots operate as central nodes for smaller groups of robots. Then, each leader coordinates with other leaders’ space [50][52].
    • Multiple goals, one for each UAV(One-for-each): Each UAV is allowed to visit exactly one goal.
    • On the other hand, distributed approaches lack a central agent; instead, the individual agents plan and adjust their paths. The decisions are distributed on the robot team’s side, not determined by a base station [18][51][52][53]. Hence, distributed systems are more robust and fault-tolerant than centralized approaches [18]. Specific applications follow a hybrid approach to leverage the advantages of both centralized and distributed methods [53].
      Multiple goals for each UAV (Multi-for each): There are multiple sets of goals, and each set can be visited by precisely one UAV. In this case, the sets are assigned at an initial phase for each UAV [24]. or each UAV searches for its goals set [36][37]. Alternatively, sets of goals can be overlapping, as shown in Figure 2.
    • It is worth noting that the terms decentralized and distributed are used interchangeably in the literature (e.g., the study
    • [53]), although referring to distinct elements of the decision-making policy of the system: authority and responsibility. As a result, we can have a decentralized system in which the responsibility is not distributed equally but in a hierarchal scheme, as illustrated before.
    • Communications allow sharing of information between robots to enhance their perception of the environment and inform the decision-making required for motion planning [4]. Communications can be categorized based on how the robots exchange information to direct/explicit and indirect/implicit communications. In explicit communications, robots share information directly, which might take the form of unicast or broadcast messages, while in implicit communications a robot learns about other robots in the system by observing its environment [50].
  • UAVs: A multi-UAV system can be composed of homogenous vehicles, i.e., with identical features and capabilities, or heterogeneous vehicles, i.e., with different capabilities [38]. A key feature, especially for a multi-UAV system, is collision avoidance (CA). CA is an important capability when there are obstacles or multiple UAVs in the environment. However, CA adds a layer of complexity and challenges, hence, sometimes it is ignored based on certain assumptions [39]. In 3D environments, in particular, CA is an issue that should be explicitly handled either by an altitude layering approach which means that each UAV flies at a different altitude
  • Scope: Based on the information scale considered while generating the path, planners can be classified as global, local, or hybrid/mixed [19][48][40][. If information about the entire environment is used to plan the path, the planners are considered global. Global planners are known for their efficiency when the environment map is perfectly known and the environment is static, therefore, they are also known as static planners. In contrast, local path planners only consider the area surrounding the vehicle, they are essential when no environment map is available or when the environment is dynamic, thus they are known as dynamic or reactive planners [3]41], or through a safe distance approach where the distance between any two UAVs should not exceed a safe distance [10].
  • [4][8][9][42]. In hybrid path planning, both types are used together; a local planner takes the path from a global planner and then dynamically adjusts it according to obstacles in the environment [54].
  • Environment (Env.): It is the workspace in which a UAV navigates which can be embodied in two-dimensional (2D) or three-dimensional (3D) planes. A map representation is usually developed for the environment which can be known, unknown, or partially known [10][42]. A known map accurately represents the environment and encapsulates all of its details, such as the surrounding area and obstacles, while a map with approximate or uncertain information is considered partially known. On the other hand, in an unknown environment, where a UAV can only acquire further knowledge about the surroundings during navigation, the map is considered unknown
  • Objective function: An optimization criterion that is defined by the objective function is required for finding a path. An objective function can be a multi-objective, single-objective, or single-objective with weights (where multi-objective weights are balanced and transformed to single-objective weights) function that should be maximized or maximized [55]
    [43]. Another primary characteristic of the environment affecting path planning problems is its evolution which can be static or dynamic
    . There are many standard optimization objectives in cooperative path planning, and the common ones: are cost minimization, payoff optimization, performance optimization, and risk minimization, such as threats or flight altitude. The objective function may have different formulations in different scenarios [
    [4]. A static environment comprises unchanging settings while a dynamic environment includes moving objects, usually obstacles or other UAVs
    10]
    [44], which change the environment geometry [45]. Dynamicity of the environment can be handled by either replanning the initial path or calculating the probability of the target position in different cells or time frames. However, replanning the initial path can encounter limitations when certain thresholds have been exceeded, such as in [46][47].
/media/item_content/202307/64a21d8ab3ea8mathematics-11-02356-g002.png
Figure 2. Possible goal schemes in multi-UAV path planning system.

3. Multi-UAV Path Planning Algorithms

  • .

References

  1. Kurdi, H.; AlDaood, M.F.; Al-Megren, S.; Aloboud, E.; Aldawood, A.S.; Youcef-Toumi, K. Adaptive task allocation for multi-UAV systems based on bacteria foraging behaviour. Appl. Soft Comput. 2019, 83, 105643.
  2. Boukoberine, M.N.; Zhou, Z.; Benbouzid, M. A critical review on unmanned aerial vehicles power supply and energy management: Solutions, strategies, and prospects. Appl. Energy 2019, 255, 113823.
  3. Kurdi, H.A.; Aloboud, E.; Alalwan, M.; Alhassan, S.; Alotaibi, E.; Bautista, G.; How, J.P. Autonomous task allocation for multi-UAV systems based on the locust elastic behavior. Appl. Soft Comput. 2018, 71, 110–126.
  4. Khan, A.; Rinner, B.; Cavallaro, A. Cooperative robots to observe moving targets: A review. IEEE Trans. Cybern. 2016, 12, 187–198.
  5. Parker, L.E. Path Planning and Motion Coordination in Multiple Mobile Robot Teams. Encycl. Complex. Syst. Sci. 2009, 24, 5783–5800.
  6. Zhang, D.; Duan, H. Social-class pigeon-inspired optimization and time stamp segmentation for multi-UAV cooperative path planning. Neurocomputing 2018, 313, 229–246.
  7. Basiri, A.; Mariani, V.; Silano, G.; Aatif, M.; Iannelli, L.; Glielmo, L. A survey on the application of path-planning algorithms for multi-rotor UAVs in precision agriculture. J. Navig. 2022, 75, 364–383.
  8. Aggarwal, S.; Kumar, N. Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges. Comput. Commun. 2020, 149, 270–299.
  9. Patle, B.K.; Babu, L.G.; Pandey, A.; Parhi, D.R.K.; Jagadeesh, A. A review: On path planning strategies for navigation of mobile robot. Def. Technol. 2019, 15, 582–606.
  10. Zhang, H.; Xin, B.; Dou, L.; Chen, J.; Hirota, K. A review of cooperative path planning of an unmanned aerial vehicle group. Front. Inf. Technol. Electron. Eng. 2020, 21, 1671–1694.
  11. Zhao, Y.; Zheng, Z.; Liu, Y. Survey on computational-intelligence-based UAV path planning. Knowl. Based Syst. 2018, 158, 54–64.
  12. Israr, A.; Ali, Z.A.; Alkhammash, E.H.; Jussila, J.J. Optimization Methods Applied to Motion Planning of Unmanned Aerial Vehicles: A Review. Drones 2022, 6, 126.
  13. Ait Saadi, A.; Soukane, A.; Meraihi, Y.; Benmessaoud Gabis, A.; Mirjalili, S.; Ramdane-Cherif, A. UAV Path Planning Using Optimization Approaches: A Survey. Arch. Comput. Methods Eng. 2022, 29, 4233–4284.
  14. Del Ser, J.; Osaba, E.; Molina, D.; Yang, X.-S.; Salcedo-Sanz, S.; Camacho, D.; Das, S.; Suganthan, P.N.; Coello Coello, C.A.; Herrera, F. Bio-inspired computation: Where we stand and what’s next. Swarm Evol. Comput. 2019, 48, 220–250.
  15. Gonzalez, R.; Kloetzer, M.; Mahulea, C. Comparative study of trajectories resulted from cell decomposition path planning approaches. In Proceedings of the 21st International Conference on System Theory, Sinaia, Romania, 19–21 October 2017.
  16. Orozco-Rosas, U.; Montiel, O.; Sepúlveda, R. Parallel Bacterial Potential Field Algorithm for Path Planning in Mobile Robots: A GPU Implementation. In Fuzzy Logic Augmentation of Neural and Optimization Algorithms: Theoretical Aspects and Real Applications; Studies in Computational Intelligence; Springer: Berlin/Heidelberg, Germany, 2018.
  17. Mac, T.T.; Copot, C.; Tran, D.T.; De Keyser, R. Heuristic approaches in robot path planning: A survey. Robot. Auton. Syst. 2016, 86, 13–28.
  18. Koubaa, A.; Bennaceur, H.; Chaari, I.; Trigui, S.; Ammar, A.; Sriti, M.-F.; Alajlan, M.; Cheikhrouhou, O.; Javed, Y. Robot Path Planning and Cooperation; Studies in Computational Intelligence; Springer International Publishing: Cham, Switzerland, 2018; Volume 772, ISBN 978-3-319-77040-6.
  19. Lamini, C.; Benhlima, S.; Elbekri, A. Genetic Algorithm Based Approach for Autonomous Mobile Robot Path Planning. Procedia Comput. Sci. 2018, 127, 180–189.
  20. Raja, P. Optimal path planning of mobile robots: A review. Int. J. Phys. Sci. 2012, 7, 1314–1320.
  21. Zhang, H.; Lin, W.; Chen, A. Path Planning for the Mobile Robot: A Review. Symmetry 2018, 10, 450.
  22. Tang, B.; Xiang, K.; Pang, M.; Zhanxia, Z. Multi-robot path planning using an improved self-adaptive particle swarm optimization. Int. J. Adv. Robot. Syst. 2020, 17, 172988142093615.
  23. Turpin, M.; Mohta, K.; Michael, N.; Kumar, V. Goal Assignment and Trajectory Planning for Large Teams of Aerial Robots. In Proceedings of the Robotics: Science and Systems IX, Berlin, Germany, 24–28 June 2013.
  24. Zhang, L.; Zhu, Y.; Shi, X. A Hierarchical decision-making method with a fuzzy ant colony algorithm for mission planning of multiple uAVs. Information 2020, 11, 226.
  25. Fan, Y.; Deng, F.; Shi, X. Multi-robot Task Allocation and Path Planning System Design. In Proceedings of the 2020 39th Chinese Control Conference (CCC), Shenyang, China, 27–29 July 2020; pp. 4759–4764.
  26. Skorobogatov, G.; Barrado, C.; Salamí, E. Multiple UAV Systems: A Survey. Unmanned Syst. 2020, 8, 149–169.
  27. Oh, H.; Shin, H.-S.; Kim, S.; Tsourdos, A.; White, B.A. Cooperative Mission and Path Planning for a Team of UAVs. In Handbook of Unmanned Aerial Vehicles; Valavanis, K.P., Vachtsevanos, G.J., Eds.; Springer: Dordrecht, The Netherlands, 2015; pp. 1509–1545. ISBN 978-90-481-9706-4.
  28. Khoufi, I.; Laouiti, A.; Adjih, C. A Survey of Recent Extended Variants of the Traveling Salesman and Vehicle Routing Problems for Unmanned Aerial Vehicles. Drones 2019, 3, 66.
  29. Gonzalez-Bermejo, S.; Alonso-Linaje, G.; Atchade-Adelomou, P. GPS: A New TSP Formulation for Its Generalizations Type QUBO. Mathematics 2022, 10, 416.
  30. Dantzig, G.B.; Ramser, J.H. The Truck Dispatching Problem. Manag. Sci. 1959, 6, 80–91.
  31. Rojas Viloria, D.; Solano-Charris, E.L.; Muñoz-Villamizar, A.; Montoya-Torres, J.R. Unmanned aerial vehicles/drones in vehicle routing problems: A literature review. Int. Trans. Oper. Res. 2021, 28, 1626–1657.
  32. Li, J.; Liu, H.; Lai, K.K.; Ram, B. Vehicle and UAV Collaborative Delivery Path Optimization Model. Mathematics 2022, 10, 3744.
  33. Raivi, A.M.; Huda, S.M.A.; Alam, M.M.; Moh, S. Drone Routing for Drone-Based Delivery Systems: A Review of Trajectory Planning, Charging, and Security. Sensors 2023, 23, 1463.
  34. Corberán, Á.; Eglese, R.; Hasle, G.; Plana, I.; Sanchis, J.M. Arc Routing Problems: A Review of the Past, Present, and Future; Wiley Online Library: Hoboken, NJ, USA, 2020.
  35. Hong, Y.; Jung, S.; Kim, S.; Cha, J. Autonomous mission of multi-UAV for optimal area coverage. Sensors 2021, 21, 2482.
  36. Ergezer, H.; Leblebicioğlu, K. 3D Path Planning for Multiple UAVs for Maximum Information Collection. J. Intell. Robot. Syst. 2014, 73, 737–762.
  37. Hu, X.; Liu, Y.; Wang, G. Optimal search for moving targets with sensing capabilities using multiple UAVs. J. Syst. Eng. Electron. 2017, 28, 526–535.
  38. Sultan, L.; Anjum, M.; Rehman, M.; Murawwat, S.; Kosar, H. Communication among Heterogeneous Unmanned Aerial Vehicles (UAVs): Classification, Trends, and Analysis. IEEE Access 2021, 9, 118815–118836.
  39. Elmeseiry, N.; Alshaer, N.; Ismail, T. A Detailed Survey and Future Directions of Unmanned Aerial Vehicles (UAVs) with Potential Applications. Aerospace 2021, 8, 363.
  40. Wu, F.; Varadharajan, V.S.; Beltrame, G. Collision-aware Task Assignment for Multi-Robot Systems. arXiv 2019, arXiv:1904.04374.
  41. Yan, F.; Zhu, X.; Zhou, Z.; Chu, J. A Hierarchical Mission Planning Method for Simultaneous Arrival of Multi-UAV Coalition. Appl. Sci. 2019, 9, 1986.
  42. Melo, A.G.; Pinto, M.F.; Marcato, A.L.M.; Honório, L.M.; Coelho, F.O. Dynamic Optimization and Heuristics Based Online Coverage Path Planning in 3D Environment for UAVs. Sensors 2021, 21, 1108.
  43. Zear, A.; Ranga, V. Path Planning of Unmanned aerial Vehicles: Current state and future challenges. In First International Conference on Sustainable Technologies for Computational Intelligence; Luhach, A.K., Kosa, J.A., Poonia, R.C., Gao, X.-Z., Singh, D., Eds.; Advances in Intelligent Systems and Computing; Springer: Singapore, 2020; Volume 1045, pp. 409–419. ISBN 9789811500282.
  44. Nazarahari, M.; Khanmirza, E.; Doostie, S. Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm. Expert Syst. Appl. 2019, 115, 106–120.
  45. Mohanan, M.G.; Salgoankar, A. A survey of robotic motion planning in dynamic environments. Robot. Auton. Syst. 2018, 100, 171–185.
  46. Shen, L.; Wang, Y.; Liu, K.; Yang, Z.; Shi, X.; Yang, X.; Jing, K. Synergistic path planning of multi-UAVs for air pollution detection of ships in ports. Transp. Res. Part E-Logist. Transp. Rev. 2020, 144, 102128.
  47. Duan, H.; Zhao, J.; Deng, Y.; Shi, Y.; Ding, X. Dynamic Discrete Pigeon-Inspired Optimization for Multi-UAV Cooperative Search-Attack Mission Planning. IEEE Trans. Aerosp. Electron. Syst. 2021, 57, 706–720.
  48. Ghandi, S.; Masehian, E. Review and taxonomies of assembly and disassembly path planning problems and approaches. Comput.-Aided Des. 2015, 67–68, 58–86.
  49. Carbone, G.; Gomez-Bravo, F. Motion and Operation Planning of Robotic Systems; Springer International Publishing: Cham, Switzerland, 2015.
  50. Yan, Z.; Jouandeau, N.; Cherif, A.A. A Survey and Analysis of Multi-Robot Coordination. Int. J. Adv. Robot. Syst. 2013, 10, 399.
  51. Sarno, S.; D’Errico, M.; Guo, J.; Gill, E. Path planning and guidance algorithms for SAR formation reconfiguration: Comparison between centralized and decentralized approaches. Acta Astronaut. 2020, 167, 404–417.
  52. Kahng, A.B.; Meng, F. Cooperative Mobile Robotics: Antecedents and Directions. Auton. Robots 1997, 4, 7–27.
  53. Hilmi Ismail, Z.; Sariff, N. A Survey and Analysis of Cooperative Multi-Agent Robot Systems: Challenges and Directions. In Applications of Mobile Robots; Gorrostieta Hurtado, E., Ed.; IntechOpen: London, UK, 2019; ISBN 978-1-78985-755-9.
  54. Garrido, S.; Moreno, L.; Gómez, J.V. Motion Planning Using Fast Marching Squared Method. In Motion and Operation Planning of Robotic Systems; Carbone, G., Gomez-Bravo, F., Eds.; Mechanisms and Machine Science; Springer International Publishing: Cham, Switzerland, 2015; Volume 29, pp. 223–248. ISBN 978-3-319-14704-8.
  55. Gunantara, N. A review of multi-objective optimization: Methods and its applications. Cogent Eng. 2018, 5, 1502242.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/)
Video Production Service
Feedback