Patent ID: 12217611

DETAILED DESCRIPTION

In the drawings, like reference numerals designate identical or corresponding parts throughout the several views. Further, as used herein, the words “a”, “an” and the like generally carry a meaning of “one or more”, unless stated otherwise.

Furthermore, the terms “approximately,” “approximate”, “about” and similar terms generally refer to ranges that include the identified value within a margin of 20%, 10%, or preferably 5%, and any values therebetween.

Aspects of the present disclosure are directed to a method configured for unmanned aerial vehicles (UAVs) to optimize their operational capacity within a specified region while adhering to regulatory and terrain constraints. The method implements an optimization technique to determine the maximum number of UAVs that can safely operate within the region without colliding. The method further involves incrementally increasing the number of UAVs and monitoring for collisions until the maximum safe capacity is reached.

The method includes specific regulation constraints, such as maximum altitude and speed, and regional constraints including obstacles, threats, and no-fly zones (NFZs). The method employs the Improved Particle Swarm Optimization (IPSO) method to generate collision-free and energy-efficient flight paths for the UAVs. The method's optimization framework is defined by two objective functions, a local objective function that minimizes energy consumption for individual UAV paths and a global objective function that maximizes the total number of UAVs that can safely operate within the region.

The method results in the development of a safety system that enhances UAV operational safety by considering various operational constraints, and the application of the IPSO technique to ensure optimal path planning and capacity utilization. The ability of method to adjust to different altitudes and obstacle sizes further enhances its utility and adaptability in diverse operational environments.

FIG.1Aillustrates an exemplary three-dimensional (3D) map of an urban environment100having flying unmanned aerial vehicle(s) (UAVs)102, in accordance with certain embodiment of the present disclosure. The urban space is populated with various types of buildings and infrastructural elements designated, including residential units, commercial structures, and public amenities, such as parks and airport. The diversity in building types and their distribution across the urban landscape highlight the complex nature of urban environments where UAVs102may operate.

In addition to buildings, the urban environment is depicted with various transportation elements such as roads, which facilitate vehicular and pedestrian movement. The depiction of roads emphasizes the integration of UAVs102into environments where ground-based traffic must be considered to prevent disruptions and ensure safety.

A military airbase104, represents a sensitive area where UAV flights are strictly regulated. Such regulations include restrictions on flying close to such facilities to prevent interference with military operations and ensure national security.

Airport area106is another critical area shown in the environment. The airport area106is also subject to stringent regulations concerning operations of UAV102to prevent interference with commercial and private aircraft operations during take-off and landing phases. Such regulations include avoiding flight in close proximity to these areas to mitigate risks of collisions and disruptions to manned aircraft.

The environment also illustrates various obstacles108, such as trees, smaller buildings, residential complexes, commercial buildings, and other physical features that present navigational challenges for the UAVs102. These obstacles108necessitate sophisticated navigation and control systems to ensure the UAVs102can operate safely and efficiently without collision.

The illustrated 3D urban environment serves as a foundational representation for understanding the operational constraints and regulatory requirements imposed on the UAVs102in urban settings. Such visualization aids in the conceptualization of systems that must manage traffic of UAV102in such environments, taking into consideration safety, efficiency, and compliance with local regulations. The depiction further supports the development of management system of UAV102that can dynamically adapt to varied urban landscapes and their associated challenges.

Each feature illustrated in theFIG.1Aaligns with operational and safety considerations necessary for the integration of the UAVs102into densely populated urban environments. Various studies have been conducted to render effective operations of UAV102, focusing on safety, privacy, regulatory compliance, and overall management, particularly in view of use of drones in diverse environments.

Safety concerns are one of dominant challenges around the UAVs102, particularly in contexts where they operate near sensitive zones, such as airfields and military bases. Launching drones in these areas during critical flight operations poses a significant risk of catastrophic incidents, impacting not just the safety of the airspace but also the ground operations of these facilities. For example, a drone may collide with an aircraft during take-off and landing process of the aircraft. Additionally, privacy issues also arise in sensitive areas, such as the military airbase104, given the potential for drones to inadvertently or intentionally capture sensitive data. Diverse studies have highlighted these concerns, indicating comprehensive frameworks are necessary to address both the intentional and unintentional consequences of operation of UAV102. For instance, studies have compared the safety and privacy regulations across different regions, revealing variations in the way UAVs102are governed to protect both individuals and national interests. These studies underscore the complexity of managing the UAVs102in a manner that respects privacy while ensuring safety.

In addition to the safety concerns, regulatory studies have also been considered while configuring the UAVs102. The regulatory provide insights into how different nations have approached management of UAV102, focusing on aspects, such as behavioral privacy, public safety, and national security. For example, research examining New Zealand's drone policies indicates a general satisfaction with current regulations, with only a minority advocating for changes. These insights are critical as they highlight user perspectives on the effectiveness of existing regulations and their impact on operation of UAV102. Similarly, studies on the lawful use of drones, such as those conducted in the Slovak Republic, reveal gaps in current legislation that may not adequately address emerging challenges brought about by the increasing ubiquity of drones in commercial and public spaces.

Moreover, effective management of the UAVs102, particularly in urban environments, presents another critical area of focus. The introduction of drone-following models indicates various approaches to managing traffic of UAV102, aiming to prevent accidents and ensure efficient flow within the designated airspace. These models utilize parameters like drone acceleration and velocity adjustments to maintain safe distances between the UAVs102, highlighting the potential for technological advancements to enhance traffic management in urban air transport systems.

Each of these areas reveals the dynamic and complex nature of operations of UAV102, stressing the need for continuous evaluation and adaptation of regulatory frameworks to keep pace with technological advancements and societal needs. The increasing presence of the UAVs102in airspace may result in congestion, complicating the management and regulation of UAV102traffic. Furthermore, the risk of intra-collision among the UAVs102presents a significant safety challenge. As the number of UAVs102in an operational area rises, the likelihood of accidents also increases. It is therefore required to develop a robust system that enforces regulatory constraints and ensures the operational safety of the UAVs102within a specified region.

Additionally, a limitation of UAVs102is their restricted battery life, as these vehicles typically depend on rechargeable batteries for power. Enhancing the flight duration of the UAV102is essential. Enhanced flight duration can be achieved by equipping the UAVs102with an energy-efficient, collision-free path generator that is capable of producing flight paths that minimize energy consumption.

The various studies have focused on a global consensus on the importance of developing robust systems to manage the integration of the UAVs102into everyday life while ensuring public safety, privacy, and compliance with evolving regulatory landscapes. These studies collectively contribute to a deeper understanding of the challenges and opportunities presented by UAV technology, guiding the development of more effective management and regulatory approaches.

FIG.1Billustrates a method101for coordinating the UAVs102within a defined region under specific constraints. At step110, constraint data which is indicative of a set of constraints under which a group of UAVs102are configured to fly in a region is obtained. The set of constraints may include at least one of (a) an obstacle constraint, which is a constraint for avoiding collision of the UAVs with obstacles in the environment, (b) a UAV collision constraint, which is a constraint for avoiding collision between UAVs, (c) an altitude constraint, which defines the minimum or maximum altitude of the UAVs flight, or (d) a speed constraint, which defines the minimum or maximum speed of the UAVs flight. The constraint data may also include, but is not limited to, geographical boundaries, no-fly zones, and proximity to sensitive areas, such as airports or military bases.

At step112, a cost function is defined. The cost function includes a set of cost terms that correspond to the constraints identified in step110. One of the cost terms within this function is the energy consumption term of UAV102, which is indicative of the energy consumption of each UAV102as it travels from a source location to a destination location along a given flight path. The cost function is designed to quantify various operational metrics, such as fuel or energy usage, risk of violation of airspace regulations or other constraints, and efficiency of the flight path in terms of time or distance.

At step114, a capacity maximization function of UAV102is executed. This function performs two primary operations. First, at sub-step114-1, it generates flight paths for the group of UAVs102. In an example, the flight paths are generated using the PSO technique. A set of flight paths is obtained for each UAV of a group of UAVs102. Accordingly, a first set of flight paths is obtained for a first UAV of the group of UAVs102. The set of flight paths are determined by computing the cost function for each flight path of the first set of flight paths, with the objective of minimizing the energy consumed during flight. One of the first set of flight paths for which the cost function evaluates to the least value is selected as a best flight path of the first UAV. In some embodiments, determining a best flight path is an iterative process, where each iteration may include (a) determining a flight path (e.g., according to IPSO technique) based on certain path determination parameters (e.g., PSO parameters such as position and velocity of a particle, inertia weight parameter, acceleration coefficients, a speed parameter, etc.) (b) computing a cost function associated with the corresponding flight path, (c) comparing the value of the cost function with the value of the cost function associated with a best flight path (e.g., which is initialized to the cost function value associated with a flight path of the first iteration), (d) if the value of cost function is lesser than the value of the cost function of the best path, storing the flight path of the current iteration as the best flight path, else adjusting the path determination parameters and computing the flight path for the next iteration based on the adjusted path determination parameters. The flight paths are adjusted dynamically to optimize the cost function value, thereby ensuring that the UAVs102do not violate the predefined constraints. Thereafter, one of the first set of flight paths for which the cost function evaluates to the least value is selected as a best flight path of the first UAV.

Second, at sub-step114-2, the function determines the total number of UAVs102. The function can be configured to iteratively increase a number of UAVs in the group of UAVs102until a first cost term of the set of cost terms that is indicative of a distance between a pair of UAVs in the group of UAVs102violates the collision constraint. In one aspect, each iteration includes increasing the number of UAVs in the group of UAVs102by a specified quantity, obtaining the flight paths of the group of UAVs102using the cost function, computing the first cost term based on the flight paths, and determining whether first cost term satisfies the collision constraint. In some embodiments, the collision constraint may be satisfied when the distance between two UAVs is greater than the minimum distance or the “safety distance” to be maintained between two UAVs. The process may be continued by increasing the quantity to the total number of UAVs102until the first cost term violates the collision constraint. The sub-step114-2includes a calculation to ensure that adding any additional UAVs102would not lead to exceeding energy allowances or violating other constraints set forth in the cost function.

The present method allows for the efficient and safe operation of UAVs102within a specified region by ensuring that all operational constraints are adhered to, while optimizing the energy consumption and overall operational capacity of the fleet of UAVs102. The method101supports sustainable and compliant UAV operations, particularly in complex environments where multiple variables and restrictions must be managed simultaneously.

FIG.2illustrates a graphical representation of the standard Particle Swarm Optimization (PSO) algorithm, in accordance with certain embodiment. The graph200illustrates the movement dynamics of particles within the search space over time. InFIG.2, movement of each particle is driven by both personal and collective historical data, aiming to find optimal solutions in a multi-dimensional search space.

The swarm algorithm is a computational algorithm inspired by the swarming behavior of salps in the ocean. Salps move in a swarm in a chain-like formation, a behavior that is translated into an algorithmic context to solve optimization problems. In context with the present disclosure, the standard PSO algorithm is a computational method used to optimize a problem by iteratively trying to improve a candidate solution with regard to a given measure of quality. It solves a problem by having a population of candidate solutions, here dubbed particles, and moving these particles around in the search space according to simple mathematical formulae over the position and velocity of particles.

InFIG.2, the positions of a particle at three sequential time steps are marked as Xi(t−1), Xi(t), and Xi(t+1), corresponding to its location in the search space at times t−1, t, and t+1, respectively. These points represent the trajectory of the particle as the trajectory explores the search space to minimize or maximize the function it is tasked with optimizing.

The vector vi(t) denotes the velocity of the particle at time t, determining the direction and magnitude of movement of the particle from Xi(t) to Xi(t+1). The updated velocity vi(t+1) is calculated based on a combination of the previous velocity of the particle and the influences of its personal best position and the global best position found by the swarm.

The personal best position Pbest(1) represents the solution that the particle has found individually up to time t. The position serves as a local attractor for the particle, influencing its subsequent movements by pulling it towards this locally optimal point.

The global best position Gbest(t+1) represents the best solution found by particles in the swarm up to time t+1. This point acts as a global attractor, guiding the entire swarm toward this most promising area of the search space.

The graphical representation emphasizes the iterative process where each particle adjusts its trajectory based on both its own experience and the successes of its peers within the swarm. The adjustment is depicted by the dotted lines indicating the paths from the current position to the personal and global best positions, influencing the next position of the particle. The collective behavior modeled by the PSO algorithm is intended to balance exploration of the search space, avoiding local optima and premature convergence issues highlighted in the present disclosure.

To address the limitations encountered by the PSO algorithm, particularly issues of local optima entrapment and premature convergence, an enhanced variant, Improved Particle Swarm Optimization (IPSO), is proposed. The IPSO algorithm is implemented augmenting the diversity of the solution space and refining the update strategies for the swarm particles. The IPSO is a variant of the standard PSO algorithm designed to enhance its performance by addressing some of the common pitfalls associated with the basic PSO, such as premature convergence to local optima and insufficient exploration of the search space. The IPSO introduces modifications to the standard mechanism of updating particle velocities and positions with the intent to strike a better balance between exploration, for example, searching new areas in the search space, and exploitation, for example, fine-tuning current solutions.

The IPSO begins with a chaos-based initialization of the swarm particles utilizing the logistic map equation:
Xn+1=μXn(1−Xn)  (1)

where Xnis the nthchaotic variable and μ represents the bifurcation coefficient. Such initialization method serves to increase the variability and reach of the solution space, which is crucial for avoiding local optima.

In one aspect, the IPSO algorithm operates with two primary phases. The initial phase focuses on exploration or searching to maximize diversity, while the latter phase concentrates on convergence towards the optimal solution. The transition between these phases is managed through an adaptive mutation technique, which dynamically updates the position and velocity of the particles based on both local and global best-known positions.

Velocity update of each particle is governed by the equation:
vt+1=ωvt+c1r1(pBestt−xt)+c2r2(gBestt−xt)  (2)

Where, ω represents the inertia weight, crucial for balancing exploration and exploitation by modulating the influence previous velocity of the particle. c1 and c2 are acceleration coefficients that weigh cognizance of the particle of personal and swarm-wide best positions respectively, modulated by random vectors r1 and r2.

In optimization challenges, it is essential to achieve an equilibrium between exploration and exploitation, a critical function facilitated by the adjustment of inertia weight. Exploration is the process of searching for novel solutions, whereas exploitation concentrates on enhancing already discovered solutions. Appropriately balancing these aspects is critical because excessive exploration may delay convergence to the global optimum, whereas too much exploitation might cause the process to become entrapped in local optima.

Adjusting the inertia weight within the algorithm plays a pivotal role in managing the balance between exploration and exploitation. Initially setting a higher inertia weight encourages exploration, helping to prevent premature convergence. Over time, reducing the inertia weight gradually shifts the emphasis towards exploitation, allowing for the refinement of solutions. Such strategic adjustment of the inertia weight ensures that the exploration of the search space is thorough yet focused, thereby consistently moving towards the optimal solution and enhancing the overall efficiency and effectiveness of the optimization process.

Inertia weight (ω) is adaptively adjusted per iteration to fine-tune the trade-off between extensive exploration of the search space and intensive exploitation of known good solutions. In simple terms, a high value of ω promotes exploration of the search space, while a low value facilitates exploitation. To describe this aspect further, w is adjusted linearly based on a certain formula as follow:

ω⁡(t)=ωm⁢i⁢n+MaxIt-tMaxIt*(ωma⁢x-ωm⁢i⁢n)(3)

Where MaxIt is maximum simulation time and t is current simulation time, ωmin, ωmaxare minimum and maximum value of inertia, respectively.

The velocity update also involves the acceleration constants c1 and c2, which guide the particles towards their personal best and the global best positions found by the swarm. The settings for these constants are crucial for ensuring an effective balance between local searches by individual particles and their alignment towards overall best findings of the swarm.

The positional update of each particle is defined by, when these values are multiplied by random vectors r1 and r2, they can have a controlled stochastic effect on the velocity. Furthermore, the values represent the weight of information sharing among particles. For instance, if both c1 and c2 are set to zero, a particle relies solely on its own knowledge. However, if c1 is greater than c2, particles tend to move towards the local attractor, while if c2 is greater than c1, particles tend towards the global attractor. Therefore, c1 and c2 are selected based on running experiments within the range of cminto cmax. The objective is to choose values that achieve both exploration and exploitation. Finally, the position of particles is calculated using the following formula.
x(t+1)=x(t)+ϵv(t+1)  (4)

The value of ϵ determines the speed at which the particle moves. A high value of ϵ enables the system to quickly move towards the best-known regions but may make it difficult to perform fine-grained optimization. Conversely, a low value of ϵ fine-tunes the solution and accelerates convergence. To achieve a balance during the optimization process, the particle initially explores the search space and make large jumps towards better regions. In later iterations, the speed of particles is reduced to achieve faster convergence. Therefore, e needs to be adapted dynamically with each iteration and can be written as follow:

ϵ=ϵm⁢a⁢x-(ϵma⁢x-ϵm⁢i⁢n)⁢tMaxIt(5)

where ϵmax, ϵminare constant value and ϵmax>ϵmin, t is current simulation time and MaxIt is total simulation time.

Thus, the IPSO is designed to provide a robust mechanism for navigating complex optimization landscapes, ensuring that both broad explorative searches and targeted exploitative adjustments are effectively balanced, thereby optimizing the convergence towards the global optimum.

In the system described, the objective is to facilitate a safety path, including multiple way points, for maximum capacity of UAVs102, enabling them to travel from source locations to their destinations while navigating around potential obstacles such as mountains, buildings, radars, and other hazards that may be present in the environment. In one aspect, each way point is represented using 3D location coordinates. The system specifically considers formations of multiple UAVs102operating concurrently, necessitating the integration of path planning strategies that address both the terrain and the arrangement of formations of UAVs102to avoid obstacles effectively.

The configuration of the UAVs102within the formation is denoted by pairs of position and velocity values, represented as:
(p1,v1),(p2,v2), . . . (pN,vN)  (6)

To describe a three dimensional path planning problem, let N is the number of way points for each particle, then the ithposition and velocity vector of particle can be respectively written as follow:
pi=pi(x1,y1,z1),pi(x2,y2,z2), . . . ,pi(xN,yN,zN)  (7)
vi=vi(x1,y1,z1),vi(x2,y2,z2), . . . ,vi(xN,yN,zN)(8)
Optimization algorithms are utilized in path planning to determine a viable route for a drone to travel from a starting point to a destination point within a complex environment. The path should be suitable for use by the algorithm, and the flying space must be confined. In the context of 3D path planning, the boundary of the flying space can be described as:
(x,y,z)|xmin≤x≤xmax,ymin≤y≤ymax,zmin≤z≤zmax(9)
Where xmin, ymin, zminare the lower bounds of the flying space and xmax, ymax, zmaxare the upper bounds of the flying space.

In the present disclosure, the space boundaries and locations of obstacles are assumed to be known in advance. The obstacle is modeled as a half sphere as follows:
Ok=(xk,yk,zk,rk)  (10)
Where xk, yk, zkare the three-dimensional coordinate of Kthobstacle and rkis the corresponding radius of the obstacle.
xk=rkcos(θ)sin(ϕ)+xk0(11)
yk=rksin(θ)sin(ϕ)+yk0(12)
zk=rKcos(ϕ)+zk0(13)
where xk0, yk0, zk0is the center coordinate of kthobstacle, θ∈[0 2π], and φ∈[0 π/2].

The system and method of the present disclosure are designed to maximize the number of UAVs102operating in a target region while adhering to various regulations. The method determining the maximum safe operating speeds and collision avoidance rules to ensure UAVs102do not collide during flight. Collision avoidance is critical and is managed by maintaining a minimum safe distance between the UAVs102, which is defined by collision constraint, and between the UAVs102and obstacles, which is defined by obstacle constraint. Optimization of flight paths is performed through algorithms that take into account minimum safe distance of each UAV102, among other factors.

Monitoring and adjustment of the flight paths of UAVs102are continuously performed during operation to ensure that all UAVs102operate within the defined safety and regulatory constraints. Determining the most optimized path, i.e., the best flight path, includes computation of an initial position and initial velocity of the first particle of the group of particles in the search-space using a one-dimensional logistic map, prior to execution of the iterations of the flight path determination. The determination of the flight path further includes assignment of an initial flight path determined based on the initial position and initial velocity of the first particle as the best flight path for the first UAV. Safety and regulatory constraint involve dynamically adjusting the initial flight path (e.g., iteratively) to prevent any breaches of the collision constraint or other operational limits.

Obstacle avoidance is managed by a constraint model where trajectory of each UAV102is evaluated against known obstacles within the flight area. If a UAV path intersects with any obstacle as defined by the radius and position of the obstacles, the UAV path is penalized heavily to ensure it is discarded from consideration. Similarly, UAV member collision avoidance is managed by ensuring all the UAVs102in the formation maintain a prescribed safety distance from one another. If the calculated distance between any two UAVs102falls below this safety threshold, the paths are adjusted or discarded.

Moreover, altitude and speed constraints are rigorously enforced. The UAVs102are required to operate below a specified maximum altitude and speed, with any violation resulting in the reconfiguration or discarding of the flight path. Such constraint enforcement ensures that the UAVs102operate safely and efficiently within their operational environment.

One objective of the present embodiment is to establish a safe navigational path enabling the maximum capacity of the UAVs102to traverse from origin points to designated destinations. This requires careful consideration of various environmental hazards, such as mountains, buildings, radars, and other potential obstacles.

The constraints for obstacle avoidance are defined such that the system calculates an obstacle constraint.

Let N_Obs is the number of obstacles and NFZs, and Ndis a number of UAVs102. The obstacle constraint, Obc (i, j), i=1, 2, . . . , Ndand j=1, 2, . . . , N_Obs, can be obtained as follow:

=(Uxi-Oxj)2+(Uyi-Oyj)2+(Uzi-Ozj)2(14)

If a point of UAV102path goes through obstacles, the path is penalized by a high value to discard it. Thus, the cost of collision with obstacle can be formulated as follows:

J1={∞,if⁢Obc⁡(i,j)<R_obsj0,Otherwise(15)

where R_obsjis the minimum distance to be maintained between an UAV and the obstacle.

In some embodiments, the obstacle constraint may be satisfied when the distance between an UAV and an obstacle is greater than a minimum distance to be maintained between a UAV and an obstacle.

The collision constraint, or the UAV member constraint, is defined to avoid collisions among the UAVs102in the flying space. Therefore, a distance between a first UAV of the pair of UAVs102and a second UAV of the pair of UAVs102is determined based on location co-ordinates of the pair of UAVs102obtained from the flight paths. The distance between UAVs102is determined as follow:

Uc⁡(i,j)=(Uxi-Uxj)2+(Uyi-Uyj)2+(Uzi-Uzj)2(16)

The UAV member constraint keeps tracking the distance between a pair of UAVs102(e.g., using Eq. (15)). If the distance between the first UAV of the pair of UAVs102and the second UAV of the pair of UAVs102is smaller than a safety distance (SD), which is a threshold distance or minimum distance to be maintained between any two UAVs), the paths are discarded. The cost of collision with other members can be formulated as follows:

J2={∞if⁢Uc⁡(i,j)<SD0,Otherwise(17)

In some embodiments, the collision constraint may be satisfied when the distance between two UAVs is greater than the minimum distance or the “safety distance” to be maintained between two UAVs. An altitude constraint is defined to ensure that the UAVs altitude is within a range of altitude, greater than a minimum altitude or less than a maximum altitude. In an example, the altitude constraint of UAVs102should not exceed 120 m. So, the cost of altitude can be formulated as follows:

J3={∞,if⁢UAV_altitude>Maximum⁢altitude0,Otherwise(18)

In some embodiments, the altitude constraint may be satisfied when the altitude of the UAV is lesser than a maximum permissible or predefined threshold altitude of the UAV. The flight path may be adjusted or discarded if the cost term indicative of the altitude constraint violates the altitude constraint (e.g., greater than the safe distance).

A speed constraint is defined to ensure that the UAVs speed during flight is within a range, greater than a minimum speed, or less than a maximum speed. For example, the speed constraint can indicate that the maximum speed of the UVA102should not exceed 44 mps. So, the cost associated with speed constraint can be formulated as follows:

J4={∞,if⁢UAV_speed>Maximum⁢Speed0,Otherwise(19)

In some embodiments, the speed constraint may be satisfied when the speed of the UAV is lesser than a maximum permissible or predefined speed of the UAV. The flight path may be adjusted or discarded if the cost term indicative of the altitude constraint violates the altitude constraint (e.g., greater than the safe distance).

The objective function is a concept that determines how various variables contribute to a specific value, and the optimization algorithm either maximizes or minimizes this value. In one aspect of the present embodiment, the local objective function is designed and applied in the IPSO to obtain the paths of the UAVs102.

One of the objectives in the UAV path planning is the energy consumption, and the path with minimum energy required is desirable. Computation of the UAV energy consumption term for an UAV of the group of UAVs102is based on a calculated (a) distance and speed to be traveled in each of a horizontal and vertical direction, and (b) angular speed and angle of turn taken by the UAV for the given flight path of the flight paths. For example, the total energy consumed in a flight path may be represented as follows:
TE=f(Eh,Ev,Eturn)  (20)

where Eh, Ev, Eturnare energy consumed in horizontal flying, vertical flying, and in taking turns, respectively. The horizontal energy may be computed as:

Eh=Ph*vd)(21)

Where Phis power consumption due to flying d horizontal distance with v horizontal speed.

The vertical energy may be computed as:

Ev⁡(Δ⁢h)=Pv*Δ⁢hVv)(22)

Where Pvis power consumption due to flying vertical distance (e.g., difference in height when the altitude changes) with Vvvertical speed.

The turn energy may be computed as:

Eturn=Pturn*Δ⁢θωturn)(23)

Where Pvis power consumption due to flying vertical distance (e.g., difference in height when the altitude changes) with Vvvertical speed.

In the present embodiment, the applied energy model (e.g., Eq. (20)) is used to calculate the energy for path. In some embodiments, a flight path is determined such that the energy consumed by a drone is reduced (e.g., minimized).

The cost function or the objective function, CF, based on which the flight path is determined, adjusted or optimized, may be written as follows:
CF=TE+J1+J2+J3+J4(24)

Where TEis energy consumed in the path, and J1, J2, J3, and J4are violation costs of obstacle constraint, collision constraint, altitude constraint, and speed constraint. The aim in determining a flight path is to adjust or optimize the flight path to minimize these quantities.

For the problem formulation, the objective is to maximize the number of UAVs102that can operate within a specific airspace while adhering to all regulatory, obstacle avoidance, UAV102performance constraints and the constraints described above. The problem variables include the number of UAVs102and their respective flight paths, with the primary aim to optimize the capacity of UAV102within a defined region while avoiding collisions (e.g., with one another, or with obstacles) and adhering to speed and altitude restrictions and minimizing energy consumption.

Key assumptions for this formulation include uniformity in UAV types and flight characteristics and the exclusion of weather-related impacts. The model considers a region of interest comprising certain forbidden regions or NFZs and multiple obstacles, collectively referred to as N-Obs. The UAVs102are tasked with navigating from starting positions (SPs) to target positions (TPs), constrained by the stipulated altitude and speed limits.

Thus, the global objective function is formulated as maximizing the capacity of UAVs102subject to maintaining safe distances from obstacles and other UAVs102, adhering to maximum speed and altitude constraints. This optimization problem is tackled using the IPSO technique, aiming to determine the optimal number of UAVs102and their routes that satisfy all specified constraints while maximizing operational capacity within the airspace.

FIG.3illustrates a flow chart of a method300configured for optimizing (e.g., maximizing) number of UAVs102configured to operate in a designated area, and for optimizing the flight paths of UAVs102within specified constraints. The approach detailed inFIG.3, provides a method for determining (a) the maximum capacity of UAVs102that can operate safely within a specified area, and (b) their flight paths while adhering to regulatory and terrain constraints. The method utilizes an iterative process that begins with a predetermined number of UAVs102and gradually increases this number until a collision is detected. The maximum capacity of UAVs102is assessed by considering the number of UAVs102present just before a collision occurs. In some embodiments, the collision detection is managed by method300using a check-collision function that (a) verifies if the safety distance between any two UAVs102is maintained, and (b) checks for potential collisions with terrain obstacles. The check-collision function activates a collision flag (CF) to indicate a collision occurrence. Upon detecting a collision, the method ceases operation and returns the maximum UAV capacity.

In some embodiments, to optimize UAV flight paths, the method employs the IPSO (e.g., method350) technique, an enhancement of the traditional PSO. The IPSO introduces particle update rules to boost PSO performance, ensuring that UAVs102navigate their routes while maintaining safe distances from each other and complying with regulatory and terrain constraints. The process iteratively adjusts to meet safety thresholds and operational efficiency, demonstrating an application of particle swarm principles to real-world challenges in UAV navigation and management. The method, thus, ensures that each UAV102operates optimally within a controlled airspace, maximizing utility while minimizing risk. In some embodiments, the method300is similar to the method101ofFIG.1B. The following paragraphs describe the method300in detail.

At step302, input parameters, such as regulation constraints (RC) (e.g., altitude constraint, speed constraint, etc.), terrain constraints (TC) (e.g., obstacle constraint, etc.), UAV constraints (UC) (e.g., collision constraint, etc.) in the designated area where the UAVs are configured to operate are defined. This sets the framework for the UAV operation, ensuring all variables are tailored to specific operational limits and environmental factors.

At step304, an initial number of UAVs102are set and a collision flag (CF) is set to a particular value (e.g., to 0 indicating no collision) to monitor interactions among the UAVs102.

At step306, the CF is evaluated. The CF may take one of two values indicating a collision or no collision (e.g., “0” indicating collision or “1” indicating a collision).

If a collision is indicated it may imply that the maximum capacity of the UAVs is exceeded. Accordingly, at step308, the maximum capacity of UAVs is set to the number of UAVs determined in a previous iteration, or obtained by decreasing a specified quantity (e.g., “1”) from the number of UAVs102in the current iteration (e.g., Nd).

If a collision is not detected, at step310, the number of UAVs102is incremented by a specified quantity (e.g., “1” to obtain Nd+1) and the flight paths are obtained for the updated number of UAVs102(e.g., by executing method350, which returns the best flight paths for each of the UAVs as described below). In generating the flight paths, the method350may ensure that UAVs102navigate their routes without violating any of the defined set of constraints. For example, the method350may implement a cost function having a set of cost terms that correspond to the set of constraints (e.g., cost function defined using Eq. 24) and adjust the flight path such that the cost function is reduced (e.g., minimized) to avoid any violation of the set of constraints or to minimize the energy consumed by the UAVs in traveling from the source location to the destination location.

After the paths are generated, at step312, the check-collision function is executed to compute the CF, which is indicative of any collision between the UAVs for the generated paths. The method proceeds to step306, where the CF is evaluated for any collision between the UAVs. If the CF indicates no collision between the UAVs or between the UAVs and obstacles, the process continues to step310to further increase the number of UAVs and generate the paths for the updated number of UAVs. On the other hand, if the CF indicates a collision between the UAVs or between the UAVs and obstacles, the process stops by setting the maximum capacity of the UAVs to the number of UAVs determined in a previous iteration (e.g., Nd−1) and outputting their associated flight paths. This ensures that each UAV102operates within safe parameters without violating any pre-set constraints and by maximizing the capacity of the UAVs102that can be operated in the designated area.

Referring to method350, the method350generates or outputs the flight paths for a specified number of UAVs (e.g., determined in step310). At step314, the number of UAVs and the set of constraints are obtained as input (e.g., from step310or other steps of method300).

As mentioned above, in some embodiments, IPSO, which is an enhanced version of PSO, may be implemented to determine the flight paths of the UAVs102. The IPSO is an iterative method that determines or, adjusts or optimizes a flight path of the UAV in an iterative manner.

At step316, the IPSO is initialized. The initialization operation sets a number of variables such as a maximum number of iterations, and generates an initial particle population in a search space that represents the number of UAVs in the designated area. The initialization operation also determines an initial position and velocity of each particle of the swarm using a specific equation (e.g., using chaos-based initialization as prescribed by Eq. (1)). An initial flight path is generated for each of the number of UAVs based on the initial position and velocity of each particle. A flight path may be represented as a sequence of way points from a source location to a destination location, where each way point is represented using three-dimensional (3D) location coordinates (e.g., Pi(x,y,z)). The cost of the initial paths is evaluated based on position of each particle through a cost function (e.g., Eq. (24)) that assesses the energy value and other constraints of each solution. As described above, the cost function integrates energy costs with potential penalties from obstacle collisions, proximity violations among UAVs102, and breaches of altitude or speed limits. The current number of iterations is set to “1” indicating that this step is a first iteration of method350.

Following the initialization, the method350enters a loop (e.g., steps318-322) that continues until the maximum number of iterations is reached. In each iteration, either the flight paths from the previous iteration are further optimized (e.g., step320), or the best flight paths determined so far for all the UAVs are output (e.g., step322). For example, at step318, the current number of iterations is evaluated. If the current number of iterations is less than the maximum number of iterations, the method proceeds to step320to further optimize a flight path from the previous iteration (e.g., the initial path) to generate an adjusted flight path and determine a value of the cost function for the optimized path. The step320also stores a path from one of these iterations as a best flight path (e.g., a flight path which has the least value for the cost function). The best path is determined for each of the number of UAVs (e.g., ND obtained in step314). On the other hand, if the number of iterations is not less than the maximum number of iterations, the method proceeds to step322where the final flight paths (e.g., best flight paths) for all the UAVs are returned (e.g., to step310of method300). Each iteration of the method350refines the UAV102paths to optimize the operational efficiency and safety of the UAV102fleet.

During each iteration (e.g., step320), particle positions and velocities are updated (e.g., using Eqs. (2)-(5)), a new flight path is determined based on the position of the particles, the cost of the new population (e.g., new flight path) is evaluated based on energy consumption and other constraints (e.g., using Eq. (24)), and the best flight path found so far is tracked (e.g., a flight path which has the least value for the cost function). For example, in a first iteration, consider the value of the cost function of the initial paths (e.g., “Path 1”) for a first UAV, a second UAV, and a third UAV are [1.1, 1.3, 1.02], and the initial paths for the three UAVs are stored as the best paths for the respective UAVs. In subsequent iterations, the new path for each UAV is evaluated with respect to the best paths found so far. For example, in a second iteration, if the cost function of the new paths (e.g., “Path 2”) for the three UAVs evaluates to [1.02, 100.4, 1.015], while Path 2 for the first drone and the third drone are better than the best paths (e.g., 1.02<1.1 and 1.015<1.02), Path 2 for the second UAV is not collision-free compared with the best path (e.g., 100.4>1.3), and this path causes collision either with obstacles or with other drones, and therefore it may be neglected for the second UAV. Thus, the best path is updated to [1.02, 1.3, 1.015] for the three UAVs. Continuing with the example, in a third iteration, if the cost function of Path 3 for the three UAVs evaluates to [1.52, 1.2, 1.005], then the best path is updated to [1.02, 1.2, 1.005] while ignoring the Path 3 for the first UAV since the value of the cost function associated with Path 3 for the first drone is not lesser than that of the best path (e.g., 1.52>1.02). The same process is followed for subsequent iterations and their respective paths.

Several parameters such as inertia weight, a speed parameter, and acceleration coefficients, are determined in each iteration. The speed parameter is indicative of a speed at which the group of particles move in the search space. In some embodiments, a velocity of a first particle corresponding to a first UAV of the number of UAVs in the search space is determined based on (a) a velocity of the first particle, a first position of the first particle and a first position of the group of particles in a previous iteration, (b) the inertia weight parameter, and (c) the acceleration coefficients (e.g., using Eq. (2)). The inertia weight controls how much of the previous particle velocity influences its new velocity, while the acceleration coefficients impact how the particle's personal and the swarm's solutions affect trajectory of the particle. The IPSO parameters are adapted using Equations (3) and (5), dependent on the current iteration count and the maximum number of iterations, to allow for adaptive mutation of solutions. Particle velocities and positions are updated according to Equations (2) and (4), respectively, considering their current positions, velocities, personal bests, and global best solutions. In one aspect, the values of the inertia weight parameter and speed parameter are adjusted dynamically with each iteration.

Continuing with step320, new positions and velocities are calculated based on the distances to personal and global best solutions. The method350also monitors and replaces inactive particles to prevent stagnation in local optima. For example, during the iterations, certain particles may become stuck in local optima and are unable to contribute to improving the flight path. The method350monitors these particles and keeps track of the number of iterations in which particles do not contribute to path improvement. If any particle exceeds the selected limit (e.g., 20% of the maximum iteration), it may be re-initialized with a fresh particle (e.g., using Eq. (1)). The new population (e.g., new flight path) cost may be assessed by applying the cost function (e.g., Eq. (24)) to new position of each particle, and the best flight path is determined by selecting the path with the lowest energy consumption, known as the global best solution. The iteration counter increments, and the loop (e.g., steps318-322) concludes when the maximum iteration count is reached, at which point the best paths for all UAVs102are returned.

The IPSO algorithm effectively balances the exploration of new paths with the exploitation of known safe routes, ensuring a dynamic response to evolving conditions in the operating environment of the UAV102. The final output, at step322, provides optimized flight paths (e.g., best flight paths) that maximize the number of UAVs102within the set of constraints, highlighting capability of the system to adapt to complex operational scenarios.

The following are examples of algorithms for maximizing the UAVs capacity in a designated area under a set of constraints (e.g., algorithm 1) and optimizing a flight path for each of the UAVs under the set of constraints (e.g., algorithm 2). In some embodiments, the algorithms are similar to the flowchart ofFIG.3.

Algorithm 1—Maximum UAVs Capacity Under Regulation Constraints

Input:RC←Regulation ConstraintsTC←Terrain ConstraintsUC←UAVs Members' ConstraintsOutput:MC←Maximum UAVs Capacity Initialization:Nd←Initial number of UAVsCollision-Flag (CF)←0Formulation←Formulate the problem as a maximization optimization problemwhile CF==0 doNd←Nd+1UAVs-Paths←IPSO (Nd, RC, TC, UC, SD)% [algorithm 2]CF←Check-collision (UAVs-Paths)end whileMC←Nd−1Return Maximum allowable UAVs capacity (MC)
Algorithm 2: Improved PSO Algorithm for UAVs Path PlanningInput:Nd←number of UAVsRC←regulation constraintsTC←terrain constraintsUC←UAV self constraintsOutput: Optimal paths of all UAVsINITIALIZATION:MaxIter←maximum iterationInitSol←initialize positions and velocities with logistic map by Eq1Initial_EnergyCost+Evaluate (InitSol)Iter=1while Iter<MaxIter doUpdate IPSO parameters by Eq 3 and Eq 5Update the velocities of particles for all populations using Eq2Update the positions of particles for all populations using Eq4New_EnergyCost←Evaluate the energy cost of generated particlesBestSol←Select Best Solution so far Replace inactive particlesIncrement Iterend whileReturn Optimal paths for all UAVs

The simulation experiments of the method ofFIG.3are conducted under various conditions of fixed and variable altitudes. The simulations are performed using MATLAB software on a computer equipped with an Intel Core i7 CPU at 1.90 GHz, 8 CPUs, and 16 GB of RAM.

Three distinct scenarios were assessed in the simulation.

In a first scenario, the operational region was defined as a 1000 m by 1000 m area. This scenario included six obstacles and three NFZs, randomly positioned throughout the region. UAVs102were operated at fixed altitudes of 60 m, 100 m, and 120 m. A safety distance of 10 m was maintained between the UAVs102, and the dimensions of obstacles and NFZs vary between 50 m to 104.12 m.

In a second scenario, the region size was increased to 2000 m by 2000 m. It contained eighteen obstacles and five NFZs, distributed randomly. The fixed altitudes for UAV operation, safety distances, and obstacle/NFZ sizes were consistent with those in Scenario 1.

In a third scenario, a smaller region size of 500 m by 500 m was considered, containing five obstacles and three NFZs. Obstacles and NFZs in this scenario range in size from 15 m to 70 m. UAVs102fly at altitudes of 50 m, 60 m, 80 m, and 100 m. This scenario is simulated 30 times to ensure reliability, with the results being the average of these runs.

TABLE 1Parameters setting.ParameterValueOptimizationValueScenarioScenarioScenarioapproachIPSOParameter123Population200boundary1 Km ×2 Km ×500 m ×size1 Km2 Km500 mMax Iteration300Obstacles6185Altitude60, 100,NFZs353120 mObstacle andRanging from 50 m to 104.12 mRanging fromNFZs size5 m to 10 m

For all scenarios, the population size of the simulation was set to 200, and the maximum number of iterations is fixed at300. These parameter settings are summarized in Table 1. The metric for evaluating performance, termed as ‘region capacity’, is defined by the maximum number of UAVs that successfully reach their destinations without incident.

Each ofFIG.4A-FIG.4Cillustrates a progressive increase in the number of UAVs102until the maximum region capacity is reached, indicating a point at which any additional UAVs102would compromise safety due to potential collisions.

The capacity at 60 meters, as depicted by curve402ofFIG.4A, shows a gradual increase and a subsequent plateau, indicating a stable capacity before reaching a critical limit. At 100 meters, as depicted by curve404ofFIG.4B, the capacity initially rises but then slightly declines, reflecting a critical density that could lead to increased collision risks. In contrast, the capacity at 120 meters, as depicted by curve406ofFIG.4C, exhibits a steady ascent, followed by a sharp peak, denoting the optimal operation limit under given constraints.

FIG.5A-FIG.5Cindicate the impact of increased obstacles and NFZs on UAV capacity. Each ofFIG.5A-FIG.5Cillustrates a progressive increase in the number of UAVs102until the maximum region capacity is reached, indicating a point at which any additional UAVs102would compromise safety due to potential collisions. The capacity at 60 meters, as depicted by curve502ofFIG.5A, shows a gradual increase and a subsequent plateau, indicating a stable capacity before reaching a critical limit. At 100 meters, as depicted by curve504ofFIG.5B, the capacity initially rises but then slightly declines, reflecting a critical density that could lead to increased collision risks. In contrast, the capacity at 120 meters, as depicted by curve506ofFIG.5C, exhibits a steady ascent, followed by a sharp peak, denoting the optimal operation limit under given constraints.

FIG.6Apresents two-dimensional views of UAV paths as derived from the IPSO.

FIG.6Bpresents three-dimensional views of UAV paths as derived from the IPSO. These visualizations display feasible flight paths that avoid conflicts with terrain obstacles, effectively illustrating the trajectories of UAVs102within the operational space. The two-dimensional view, curve602ofFIG.6A, maps out the X and Y coordinates overlaid with obstacle and NFZ distributions, while the three-dimensional view, curve604ofFIG.6B, adds depth by including the Z-coordinate, giving a comprehensive perspective on how UAVs102navigate around obstacles.

FIG.7illustrates the normalized region capacity for different numbers of terrain constraints, including obstacles and NFZs, as presented in the vertical bars702. The region capacity is normalized on a scale from 0 to 0.8, as shown on the vertical axis, against the number of terrain constraints presented on the horizontal axis, ranging from 0 to 23. Each bar indicates how the capacity to accommodate UAVs102decreases as the number of constraints increases. Specifically, the capacity is highest with no constraints and progressively decreases as more obstacles and NFZs are introduced into the region. Such depiction serves to quantify the direct impact of physical and regulatory constraints on operational capacity in UAV102deployments.

FIG.8depicts the region capacity concerning different flying altitudes for UAVs102, under scenarios of fixed and multi-level altitudes, represented by 802 and 804 bars, respectively. The bar chart compares the maximum number of UAVs102that can successfully reach their destinations at altitudes of 50 m, 60 m, 80 m, and 100 m. The effect of altitude on region capacity is evident, as higher altitudes generally allow for greater capacity, attributed to the reduced risk of collision with ground-based obstacles. However, the chart shows that increasing the altitude beyond 80 m does not significantly increase capacity, which is consistent with the maximum height of obstacles set at 70 m in the simulation scenarios. The chart effectively captures the dual effect of altitude on UAV operation, enhancing capacity by reducing terrain collisions at lower altitudes and facing increased risks of aerial collisions at higher altitudes. The visual data representations underscore the nuanced impacts of altitude and obstacle density on UAV operational strategies.

In the present disclosure, a safety system and method are implemented for maximizing the operational capacity of UAVs102within the confines of a set of constraints. The system incorporates critical factors, such as NFZs, altitude restrictions, and terrain obstacles to optimize UAV trajectories. The system utilizes a robust algorithm to ascertain the upper limit of UAVs102that can safely operate within a designated area, compliant with both regulatory and terrain constraints.

The effectiveness of the proposed safety system was verified through simulations, which confirmed its capability to enhance the operational capacity of UAVs102while maintaining adherence to regulatory constraints. Simulation outcomes showed that the system could elevate the capacity of UAVs102to its optimal potential, ensuring safety and regulatory compliance, which holds profound implications for UAV operations in complex and regulated airspace. By implementing this system, UAV operations can be optimized, efficiency improved, and the number of UAVs102that can safely operate within a specific area maximized.

Future enhancements to the system may involve incorporating real-time data and dynamic airspace constraints into the optimization framework. This advancement may enable the system to adjust to evolving conditions, optimizing UAV trajectories dynamically, thus further enhancing operational efficiency and safety.

The above-described hardware description is a non-limiting example of corresponding structure for performing the functionality described herein.

Numerous modifications and variations of the present disclosure are possible in light of the above teachings. It is therefore to be understood that within the scope of the appended claims, the invention may be practiced otherwise than as specifically described herein.