Multi-UAV Path Planning Algorithms: Comparison
Please note this is a comparison between Version 1 by Heba Kurdi and Version 3 by Lindsay Dong.

While several developments have taken place in the field of autonomus guidance and navigation techniques for Unmanned Aerial Vehicle (UA V) 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 entrypaper conducts a systematic literature review focusesing specifically on Multi-U AV Path Planning Algorithms utilizing Bio -Inspired Algorithms. The By offering a Taxonomy of existing algorithms, the authors aim to provide both structure and accessibility for researchers interested in this topic since no prior research exists within the same context. Their 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][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][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][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][9,14]. On the other hand, bio-inspired heuristics have demonstrated the capacity to overcome these shortcomings [17][18][17,18] since they can learn and adapt similar to biological systems, enabling them to handle environmental uncertainty [8][9][11][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][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][9,19]. The problem is an NP-hard problem (nondeterministic polynomial-time) [18][20][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][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][32,33].
Figure 1 shows the main parameters that are usually used to describe the multi-UAV path planning problem which includes:
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][34[35],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.
  • 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.
    • Multiple goals, one for each UAV(One-for-each): Each UAV is allowed to visit exactly one goal.
    • 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 [
Figure 2.
Possible goal schemes in multi-UAV path planning system.

3. Multi-UAV Path Planning Algorithms

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
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].
    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].
  • 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][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][18,51]. This central agent (e.g., a control station) usually has global knowledge about network status and each robot’s interactions [18][50][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][50,52].
    • 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]][18[51],51[52][53,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].
    • 36][37][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 [40][41][40,41], or through a safe distance approach where the distance between any two UAVs should not exceed a safe distance [10].
  • Scope: Based on the information scale considered while generating the path, planners can be classified as global, local, or hybrid/mixed [19][48][19,48]. 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][4][8][9]9[42][3,4,8,,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][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 [43]. Another primary characteristic of the environment affecting path planning problems is its evolution which can be static or dynamic [4]. A static environment comprises unchanging settings while a dynamic environment includes moving objects, usually obstacles or other UAVs [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 [
  • 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]. 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 [1046][47][46,47].].


Video Production Service