The likelihood of rescuing people caught in emergencies of natural or technological origin depends on the speed with which they are provided the necessary information. In conditions where normal communication means (radio, television, Internet) are disrupted, unmanned aerial vehicles (drones) can serve as an alternative means of notification, providing information to the population through built-in audio broadcasting systems or by dropping instructions on paper, plastic, and other carriers. Similarly, essential cargo such as rescue equipment, food, water, etc., can be dropped. In the context of the rapid flow of dangerous processes and the limited number of drones available, optimizing the flight route for time becomes crucial. This work analyses existing methods of constructing flight routes through a given set of waypoints: exhaustive search methods, Bellman's discrete dynamic programming method, greedy algorithms (nearest neighbor method), and anytime algorithms. To save onboard computer resources, a method for improving the reference trajectory, which was initially found using the nearest neighbor method, was chosen. Improving the reference trajectory is done by varying the sequence of waypoints. The advantage of this approach is that at each step of the iterative improvement of the trajectory, new information that has become available at the current time can be taken into account. Changes to the set of necessary waypoints can occur due to changes in the emergency, the completion of tasks by other drones, or the failure of other drones. The workability of the algorithm with low computational time costs onboard computers was tested for routes that include from 8 to 200 points.
The primary task in ensuring the safety of the population caught in an emergency zone is to provide notifications as quickly as possible under conditions of potential disruption to conventional means of communication—radio, television, Internet [1–3].
Unmanned aerial vehicles (drones) can serve as an alternative means of notification [4]. In the absence of the possibility for emergency service personnel to quickly enter the danger zone, drones can fly into the required area and provide the necessary information to the population through audio messages using builtin broadcasting equipment or by dropping instructions on paper, plastic, and other media. Similarly, essential supplies such as rescue equipment, food, water, etc., can be dropped.
The relevance of this work lies in the fact that the likelihood of rescuing people in danger significantly depends on the speed of providing them with the necessary information and material aid.
In conditions of the rapid flow of dangerous processes of natural and technological origin, and the limited resources (fleet) of unmanned vehicles, optimizing the flight route for time becomes a critical issue.
During an emergency, conditions can change very quickly, with new points being added or existing ones disappearing from the route. There is a need to develop methods that allow for finding optimal routes using the limited capabilities of the unmanned aerial vehicle’s onboard computer, not only in conditions of communication with the base but also during autonomous flight. Under certain conditions, an unmanned aerial vehicle can identify the situation in real time through onboard sensors or can receive information from other drones nearby [5]. This necessitates the constant recalculation of the optimal route, taking into account new data received at the current moment. This is critical because it increases the chances of saving people’s lives.
Let’s analyze the state of existing research on creating optimal flight routes for unmanned aerial vehicles.
In the tasks of constructing optimal routes, Dijkstra’s algorithm [6] is very common, but it is mostly used for building the shortest route between two points. In this case, passing through all points is not mandatory.
The discrete dynamic programming method of Bellman [7] allows finding optimal routes, including solving the problem in reverse time. Among optimization specialists, there is a widespread saying attributed to Bellman: “Any optimization problem can be solved provided there are sufficient computational resources” (the authors do not have information on whether this quote is accurate, or whether the information about the authorship of the quote is reliable). However, many researchers, including [8, 9], note that the cost of calculations can become a limitation that, in the conditions of a specific problem setting, does not allow the use of good iterative methods with good convergence, such as the Bellman method.
Therefore, researchers’ attention remains
on fast, albeit imperfect methods like greedy
algorithms [
In other situations, the greedy algorithm is
used to find a reference solution that will then
be refined by more precise methods.
Sometimes these algorithms are called anytime
algorithms, to note the fact that the iterative
procedure for improving the reference solution
can be interrupted at any moment, and the
solution obtained at that moment will be at
least no worse than the previous ones [
Details of the processes occurring when
working with anytime algorithms for finding
fault routes in cloud systems are considered in
[
The anytime algorithm can be particularly effective in situations where the decisionmaking time is commensurate with the time it takes for the initial conditions to find a solution to change. Indeed, in an emergency, waypoints may appear or disappear during the drone’s flight and while searching for the optimal route, especially if this search takes a considerable amount of time. This can occur both due to changes at the waypoints themselves and because several drones, which distribute the waypoints among themselves and duplicate each other’s actions in case of failure, may be allocated for task execution. In such a scenario, some waypoints may disappear from the plan due to the actions of other drones or, conversely, be added to the task plan due to the failure of other drones that were scheduled for that task. In any case, a recalculation of the optimal route will be necessary.
The most closely related to the problem
statement in this work are studies [
Thus, part of the unresolved problem is the methods of constructing and further improving the UAV flight trajectory during an emergency event by the criterion of minimum time. The trajectory is built by determining the order of passing through the waypoints, the set of which is clearly defined. A waypoint is considered a point where the drone must stop and perform a task: make an audio announcement, deliver cargo (material aid or information), etc.
The goal of the work is to develop algorithms for improving the reference trajectory based on varying the sequence of passing through the waypoints.
Let’s accept the main assumptions of the study.
Assumption 1. The operational time of the drone at each waypoint is the same, as the execution of an identical set of actions is assumed at every point.
Assumption 2. The drone flies at a constant speed across all segments of the route, which is cruise speed, as it allows for energy savings, thereby increasing the available time and flight range.
Assumption 3. The drone starts from the base (the initial point of the route) and returns to the base after flying over all waypoints.
As a result of studying the characteristics of existing drones, it was found that, with a certain margin of error, the total energy a drone can use for a flight task can be related to the flight time through the following equation = + ( ) , (1) where
is the total energy of the drone’s battery, is flight time, is flight speed, is battery energy expenditure coefficient depending on time, ( ) is battery energy expenditure coefficient depending on the flight range (distance covered).
In turn, the coefficient ks(V) also depends on the flight speed. Up to a certain flight speed, the coefficient remains unchanged. However, after reaching a certain value, it starts to increase, leading to accelerated battery energy consumption.
In simplified form, this dependency can be represented as 0 s( ) = { s0( / cruise) when s0 when ≤ cruise > cruise which the efficiently. where s0 is the battery energy expenditure coefficient depending on the flight range (distance covered) at a speed not exceeding cruise speed, cruise is cruise flight speed, at battery energy is used most
In this study, we will assume that the flight speed does not exceed the cruise speed.
Considering the possible change over time t of the speed and, accordingly, the coefficient ( ), the expression for the drone’s energy expenditure can be represented in the form ( ) = ∫( + ( ( )) ( ) (3) 3.1.
The simplest way to construct the optimal route is to enumerate all possible sequences of passing through the waypoints. However, in this case, for a route that includes points, it will be necessary to check several options equal to (Fig. 1).
! ≈ 10 = ∑ lg .
=1 number of options that need to be iterated through brute force for optimizing a route consisting of N points In our case, brute force iteration of route options makes sense when the number of route points is no more than 10–15, depending on the power of the onboard computer. For a larger
number computationally of
route efficient points, methods more are required. However in doing so, one might have to pay for the speed of finding the route with the loss of some of its quality. 3.2.
The simplest way to find a route that approximates the optimal is to find the nearest point that the drone has not yet visited. To do this, for the current point ( 0, 0), we build an array of Euclidean distances to all other points ( , ) where the drone has not been yet: (0, ) = √( 0 − )2 + ( 0 − )2.
(0) = min (0, ).
We remember the found index and remove the corresponding route point from further consideration. The procedure continues until all route points have been considered, i.e., an array of indices corresponding to the order of visiting the route points is constructed:
2
The found route has a route length indicator 2 much better than the length of the initial route 1, which corresponded to the sequential numbers of the points visited, but in most cases, 2 is still not optimal.
Since the solution 2 is not optimal but approximates the optimal, it is subsequently taken as a reference solution that needs to be refined. The refinement of the reference route is carried out by varying the order of the route the reference route is implemented: points in 2, the following algorithm for improving 2. For each point of the route 1. The first route point is selected. 2. The route point in the order of visiting in 3. The value of the route length 3 is 4. If the condition 3 < 2 is met, then the variation is considered successful and fixed. If not, the result of the variation is calculated.
ignored. 5. The next variation is selected—a new position for the transfer of the chosen reference route point (while all possible options are sequentially considered). 6. Steps 3–5 are repeated. 7. If all possible options for the new placement of the reference route point have been considered, a new reference route point is selected to search for a better place in the sequence 2 .
9. The found value is considered the best.
Steps 1–9 can be repeated several times. This allows for increasing the depth of variations and further improving the quality of the optimal solution.
In the graphs showing the route change during the improvement of the reference solution, the following notations with route length are adopted: • 1 is the route length for the initial order of route points (non-optimal)—indicated by a light blue line in the diagram. • 2 is the route length optimized by the nearest neighbor method—indicated by a thick blue line in the diagram. • 3 is the route length optimized by the method of varying the reference solution—indicated by a medium red line in the diagram. As seen in Figs. 2–3, with a small number of route points ( = 8), the nearest neighbor method does not require further improvement. The solution is already optimal. For 30 route points, varying the reference solution results in improvements, but only to a depth of no more than 2–3 complete cycles of variations (depending on the placement of the route points). As the dynamics of the change in 3 (caption above Figs. 4–6) show, that increasing the depth of variations beyond 2–3 does not lead to an improvement in the 3 indicator. For 50 route points, varying the reference solution can lead to improvements at a variation depth of 3 to 5, also depending on the placement of the route points (Figs. 7–9). For 100 route points, varying the reference solution can lead to improvements at a variation depth of 3 to 5, just as for 50 points, depending on the placement of the route points (Figs. 10–12). For 200 route points, the algorithm is also operational. However, the calculation time can increase to 10–20 seconds. Varying the reference solution can lead to improvements at a variation depth of 3 to 5, just as for 50 or 100 points, depending on the placement of the route points (Figs. 13–14).
Thus, the work analyzed existing algorithms for constructing flight routes for drones that would have to fly through a given set of route points.
It was found that under conditions of possible changes to the set of route points during flight in the absence of communication with the control point, the use of methods for improving the reference trajectory (anytime algorithms) is most appropriate. For this, the construction of a reference trajectory using the nearest neighbor method and further refinement of the trajectory by varying the sequence of passing the route points were used.
The operability of the algorithm with low computational time costs on onboard computers for routes that include from 8 to 200 route points was tested.
Directions for further research include testing other possible approaches to varying reference trajectories, particularly through clustering route points. [1] [2]