Coordinating a number of unmanned aerial vehicles (UAVs) to be deployed in a region under a set of constraints
View Patent ↗A method for coordinating deployment of unmanned aerial vehicles (UAVs) within a designated region involves obtaining constraint data that specifies the operational limitations under which the UAVs are allowed to operate. A cost function is defined, having a set of cost terms corresponding to these constraints, including a term for the energy consumption of each UAV. This energy consumption is the power required by each UAV to travel from a source to a destination along a prescribed flight path. The method includes executing a UAV-capacity maximization function that generates flight paths for the UAVs based on the cost function, which adjusts the flight paths to minimize the total energy consumed while ensuring that the UAVs do not breach the operational constraints.
1. A method of coordinating a number of unmanned aerial vehicles (UAVs) to be deployed in a region under a set of constraints, the method comprising:
obtaining constraint data that is indicative of the set of constraints under which the number of UAVs are configured to fly in the region, the constraint data indicating, when the number of UAVs fly in the region, requirements to be satisfied with respect to a safety distance between UAVs, a safety distance between an UAV and an obstacle, an UAV altitude limit, and an UAV speed limit;
defining a cost function having (1) an UAV energy consumption term that is indicative of an energy consumption of each UAV for flying from a source location to a destination location along a given flight path, and (2) a set of cost terms that correspond to the set of constraints;
executing an UAV-capacity maximization function to determine a maximum UAV number of a group of UAVs that is able to fly in the region without violating any constraint of the set of constraints by:
(1) setting an UAV number of the group of UAVs at an initial value,
(2) iteratively performing:
(i) based on the defined cost function, applying a modified Particle Swarm Optimization algorithm to determine flight paths for the group of UAVs, and
(ii) updating the UAV number by adding a predetermined incremental value to the UAV number of a previous iteration,
until the requirement with respect to the safety distance between UAVs or the requirement with respect to the safety distance between an UAV and an obstacle is violated, and
(3) determining the updated UAV number as the maximum UAV number;
transmitting the determined flight paths to a group of UAVs that has the determined maximum UAV number of UAVs; and
monitoring flight paths of the group of UAVs and adjusting the flight paths of the group of UAVs based on the transmitted flight paths, to ensure that all UAVs in the group operate in the region without violating any constraint of the set of constraints,
wherein:
by applying the modified Particle Swarm Optimization algorithm, the flight paths of the group of UAVs are determined to minimize the energy consumption,
an initial position and velocity of each particle of the modified Particle Swarm Optimization algorithm are determined using chaos-based initialization, and
for each iteration of the modified Particle Swarm Optimization algorithm, an inertia weight and an acceleration coefficient are adjusted based on a current iteration count and a predetermined maximum iteration number.
2. The method of claim 1 , wherein the set of cost terms include a first cost term that is indicative of whether a distance between a pair of UAVs in the group of UAVs satisfies a collision constraint, and the first cost term is computed by:
determining a first distance between a first UAV of the pair of UAVs and a second UAV of the pair of UAVs based on location co-ordinates of the pair of UAVs obtained from the flight paths, and
determining that the first cost term satisfies the collision constraint when the first distance is greater than a first threshold distance specified in the requirement with respect to the safety distance between UAVs.
3. The method of claim 1 , wherein executing the UAV-capacity maximization function to generate the flight paths for the group of UAVs includes:
obtaining a first set of flight paths for a first UAV of the group of UAVs,
computing the cost function for each flight path of the first set of flight paths, and
selecting one of the first set of flight paths for which the cost function evaluates to a least value, as a first flight path of the flight paths of the first UAV.
4. The method of claim 3 , wherein selecting one of the first set of flight paths includes:
until the cost function is minimized, iteratively performing:
defining the first flight path of the first UAV based on a position of a first particle of a group of particles that moves in a search space, wherein the group of particles representative of the group of UAVs are configured to move in the search space representative of the region UAVs are configured to fly,
computing the cost function for the first flight path based on the position of the first particle,
comparing the cost function of the first flight path with the cost function of a best flight path of the first UAV, and
selecting the first flight path as the best flight path based on a determination that the cost function of the first flight path is lesser than the cost function of the best flight path.
5. The method of claim 4 , wherein defining the first flight path based on the position of the first particle in each iteration includes:
determining values of the inertia weight parameter, the acceleration coefficient, and a speed parameter, wherein the speed parameter is indicative of a speed at which the group of particles move in the search space,
determining a velocity of the first particle corresponding to the first UAV in the search space 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 coefficient, and
determining a position of the first particle in the search space based on a position of the first particle in the previous iteration, the velocity of the first particle and the speed parameter.
6. The method of claim 4 , wherein selecting one of the first set of flight paths includes:
prior to execution of the iterations,
computing 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, and
assigning 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.
7. The method of claim 1 , wherein each of the flight paths includes multiple way points from a source location to a destination location, and wherein each way point is represented using three-dimensional (3D) location coordinates.
8. The method of claim 1 , wherein defining the cost function includes:
obtaining obstacle data of an obstacle, wherein the obstacle data includes 3D location coordinates of the obstacle and a radius of a half-sphere representative of the obstacle.
9. The method of claim 8 , wherein the 3D location coordinates of the obstacle are determined based on 3D coordinates of a center of the half-sphere representative of the obstacle.
10. The method of claim 8 , wherein
the set of cost terms include a second cost term that is indicative of whether a second distance between the obstacle and an UAV of the group of UAVs satisfies an obstacle constraint, wherein the second distance is determined based on location coordinates of (a) the obstacle and (b) a particle of a group of particles corresponding to the UAV, where in the group of particles is representative of the group of UAVs, and wherein the group of particles move in a search space representative of the region, and
the second cost term is determined as satisfying the obstacle constraint when the second distance is greater than a second specified threshold specified in the requirement with respect to the safety distance between an UAV and an obstacle.
11. The method of claim 1 , wherein applying the modified Particle Swarm Optimization algorithm to determine flight paths for the group of UAVs includes:
obtaining UAV data of an UAV of the group of UAVs, wherein the UAV data includes 3D location coordinates, speed, and altitude of the UAV.
12. The method of claim 11 , wherein
the set of cost terms include a third cost term that is indicative of whether the altitude of the UAV satisfies an altitude constraint, and
the third cost term is determined as satisfying the altitude constraint when the altitude of the UAV is lesser than a third specified threshold specified in requirement with respect to the altitude limit.
13. The method of claim 11 , wherein
the set of cost terms include a fourth cost term that is indicative of whether the speed of the UAV satisfies a speed constraint, and
the fourth cost term is determined as satisfying the speed constraint when the speed of the UAV is lesser than a fourth specified threshold specified in the requirement with respect to the speed limit.
14. The method of claim 1 , wherein applying the modified Particle Swarm Optimization algorithm to determine flight paths for the group of UAVs includes:
computing the UAV energy consumption term for an UAV of the group of UAVs 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.
15. A non-transitory computer-readable storage medium for storing computer-readable instructions that, when executed by a computer, cause the computer to perform a method, the method comprising:
obtaining constraint data that is indicative of a set of constraints under which a number of unmanned aerial vehicles (UAVs) are configured to fly in a region, the constraint data indicating, when the number of UAVs fly in the region, requirements to be satisfied with respect to a safety distance between UAVs, a safety distance between an UAV and an obstacle, an UAV altitude limit, and an UAV speed limit;
defining a cost function having (1) an UAV energy consumption term that is indicative of an energy consumption of each UAV to fly from a source location to a destination location along a given flight path, and (2) a set of cost terms that correspond to the set of constraints; and
executing an UAV-capacity maximization function to determine a maximum UAV number of a group of UAVs that is able to fly in the region without violating any constraint of the set of constraints by:
(1) setting an UAV number of the group of UAVs at an initial value,
(2) iteratively performing:
(i) based on the defined cost function, applying a modified Particle Swarm Optimization algorithm to determine flight paths for the group of UAVs, and
(ii) updating the UAV number by adding a predetermined incremental value to the UAV number of a previous iteration,
until the requirement with respect to the safety distance between UAVs or the requirement with respect to the safety distance between an UAV and an obstacle is violated, and
(3) determining the updated UAV number as the maximum UAV number;
transmitting the determined flight paths to a group of UAVs that has the determined maximum UAV number of UAVs; and
monitoring flight paths of the group of UAVs and adjusting the flight paths of the group of UAVs based on the transmitted flight paths, to ensure that all UAVs in the group operate in the region without violating any constraint of the set of constraints,
wherein:
by applying the modified Particle Swarm Optimization algorithm, the flight paths of the group of UAVs are determined to minimize the energy consumption,
an initial position and velocity of each particle of the modified Particle Swarm Optimization algorithm are determined using chaos-based initialization, and
for each iteration of the modified Particle Swarm Optimization algorithm, an inertia weight and an acceleration coefficient are adjusted based on a current iteration count and a predetermined maximum iteration number.