Every year, the scope of unmanned aerial vehicle use is growing, and the amount of such applications is expanding. To enhance efficiency, the focus of development is shifting from individual unmanned aerial vehicles to utilizing swarms for various applications such as agricultural surveys, irrigation, etc. The purpose of this work is to develop an algorithm for building a local positioning system for a swarm of unmanned aerial vehicles to maintain a stable structure during the swarm movement while performing its tasks in two-dimensional and three-dimensional settings. At the same time, it should be assumed that the swarm is controlled by one operator, regardless of the number of swarm elements. An additional limitation of the developed algorithm should be the prevention of potential collisions of unmanned aerial vehicles during aerial maneuvers. As part of the work, the task of forming and maintaining the structure and configuration of an agricultural unmanned aerial vehicle flock in two-dimensional and three-dimensional settings was set. The formalization of the given task has been completed. Considered possible methods of mapping the graph formed by an unmanned aerial vehicle swarm into two-dimensional Euclidean space by forming a basic triangle method to create a relative coordinate system. To determine the coordinates of the remaining graph vertices on the plane and correspondingly increase the accuracy of local positioning, the multilateration method is used and considered simplified options - application of the trilateration algorithm, triangulation and a simplified algorithm for the degenerate case of two drones. For the problem in a three-dimensional setting, the possibility of applying the multidimensional scaling algorithm using the methods of multidimensional scaling/reduction of dimensions is considered. The developed practical implementation of the created algorithm showed its efficiency during practical experiments, allowing it to determine the local positioning of elements of a swarm containing three to twenty elements.
Euclidean space
Every year, the scope of use of unmanned aerial vehicles (UAVs) is increasing and the spread of
such applications is expanding. At the same time, the emphasis is gradually shifting from the
individual UAVs use to the use of UAV swarms, since for many tasks (for example, surveying
agricultural areas, irrigation, etc.) this is more effective than the use of individual UAVs [
GPS for agricultural drones that perform the task of processing agricultural land from pests or
monitoring crops [
The purpose of this work is to develop an algorithm for building a system of local positioning of a swarm of UAVs to maintain a stable structure during the movement of the swarm while performing its assigned tasks in two-dimensional and three-dimensional settings. At the same time, we believe that the swarm is controlled by one operator regardless of the swarm elements number. The additional limitation of the developed algorithm: the prevention of potential UAV collisions during aerial maneuvers.
In the existing scientific works devoted to solving the given problem [
Another approach is the pre-planning of UAV swarm routes [
The most popular option is the use of particle swarm optimization algorithms [
Let's first consider how the problem can be solved in a simplified, two-dimensional formulation, which is applicable when the swarm moves at approximately the same height and the height difference can be neglected. This option is applicable for a swarm of ground drones communicating in the zone of radio waves direct propagation. We will consider the swarm elements as homogeneous, although with the additional parameters and restrictions it is possible to use heterogeneous UAVs.
Meaningfully, we have a set of drones that should form a swarm. In this work, a swarm of up to 20 drones is considered. Each drone is equipped with a set of sensors (GPS, compass, accelerometer, altimeter) that will al-low determination of mutual position and forming and maintenance of the swarm structure. The task is to achieve the desired configuration of mutual the swarm elements placement in the minimum time and further maintenance of this configuration with minimum costs of the total flight resource of all swarm elements. The algorithm must function iteratively, with a frequency of repetition at least once every few seconds, to consider possible changes in the swarm elements relative position. The configuration to be formed by the swarm must provide equal distances between adjacent swarm elements, i.e. three UAVs will form an equilateral triangle, four – a square, and so on. Thus, we have:
Input data – data from the sensors of each element of the swarm: • GPS coordinates. • the direction of movement. • speed.
• height.
• maximum UAV movement speed. • the maximum permissible flight height of the UAV. • minimum permissible UAV flight height. • maximum UAV flight range.
• the minimum permissible distance between UAVs.
Minimization of the total additional movement of all swarm UAVs required to restore the given configuration.
GPS coordinates of the points where each UAV should move to restore the given swarm configuration.
The two-dimensional formulation of the problem will involve mapping the graph formed by the
UAV swarm first into three-dimensional Euclidean space [
– the known lengths of the ribs.
Now consider the mapping of the graph from the three-dimensional Euclidean space to the problem on the plane (Figure 2).
It is easy to see from the figure that the length of the projection of the edge between the vertices
onto the XOY plane:
To form the desired configuration based on the swarm elements known coordinates, one must first choose the basic (largest) triangle. Its use will allow the formation of the desired configuration within the base triangle and will not require an increase in the maximum distance between any two swarm elements.
The basic triangle in the graph can be chosen according to the following characteristics: • the largest sum of sides , where are the edges of the graph for some triplet of vertices (Figure 3):
After selecting the basic triangle, several degrees of freedom are preserved when placing the projection of the graph on the plane. Let's choose the following: the origin of the coordinate system (the first vertex of the triangle), the direction of the abscissa axis (the second vertex of the triangle), the direction of the ordinate axis (the third vertex of the triangle) – Figure 5.
Fix the coordinates of the vertex
as the origin of the coordinates: 1. Let the side be part of the axis : 2. – determine the coordinate of the vertex from the area of the triangle:
– we determine the coordinate of the vertex according to the Pythagorean theorem:
Global positioning often does not provide a sufficient level of accuracy for the task at hand – potential errors that, in the case of two fast-moving UAVs, can overlap and add up, causing swarm elements to collide. One of the options for solving this problem is the multilateration methods use – local positioning, which does not depend on global positioning satellite systems and is more accurate than GPS (see Figure 7) [14].
Lider
UAV Repeater-Supervisor UAV 1
UAV 2
GSC
Z W
N 4.4. A degenerate case of two drones 1. When creating a swarm of two, their mutual location and distance are determined. The parameters of the mutual local positioning means are stored, which corresponds to the sensors data for such mutual location, determined by the means of global positioning. 2. One of the drones becomes the main one, the master. 3. The master relays control commands from the operator to the slave (or slave receives them directly and repeats them). At the same time, a survey is conducted once every ten seconds (data exchange to determine the signal strength and the corresponding distance between the drones). 4. If the distance has changed, correction is made by changing the flight direction and remeasurement.
Let us now consider the three-dimensional formulation of the problem. We have up to twenty objects, the distances between them are known, and the GSC to which the distance is also known. In addition, all objects (1-20 pcs.) can be separately controlled remotely any time (that is, telemetry is received on the GSC and the distance is measured by signal strength and time from editing/receiving data packets) when the operator needs it. Absolute coordinates are known for GSC. Thus, we have the following formulation of the problem:
A matrix of distances between two to twenty-one points in three-dimensional space is given. For one of these points, its absolute coordinates are known. It is necessary to develop an algorithm for building a relative coordinate system for these points.
The task of determining the coordinates of objects by the distances between them can be reduced to the well-known task of reducing the dimensionality of input data. A general approach to solving the problem of data dimensionality reduction consists of performing a sequence of steps to reduce the number of variables describing this data, and the result of the work of the corresponding algorithms is an ordered set of main variables.
The methods of multidimensional scaling/reduction of dimensions (Multidimensional Scaling – MDS) are applied to various types of data [18].
The basic idea of MDS is to find a general process in a low-dimensional space that minimizes the variance D in the high-dimensional space and the dependent variance d in the low-dimensional space. Mathematically, this can be expressed as follows: given a dissimilarity or distance matrix D, representing the difference between points i and j in space, where Dij is the Euclidean distance, MDS tries to find a set of coordinates xi and xj. This is done in a low-dimensional space so that the Euclidean distance between points i and j (denoted dij ) is as close as possible to the difference Dij .
The metric of the MDS algorithm is the stress function S (objective function), which defines the difference between the distances in the source space and the distances in the subspace. MDS for dimensionality reduction can be defined as follows: where Wij is the weight that can be used to emphasize or de-emphasize certain distances. dij is the Euclidean distance between data points i and j in the lower dimensional space. Dij is the difference (distance) between data points i and j in a high-dimensional space.
The stress function S is defined as: where lij is the distance between data points i and j in the original space, is the distance between data points i and j in the lower dimensional space, and i is the number of data points.
The stress function S is a measure of the deviation of the distances in the lower dimensional space from the distances in the original space and is used to evaluate the quality of the projection.
To create a relative coordinate system for the number of points from two to twenty-one in threedimensional space based on the matrix of distances and absolute coordinates of one point, we used a modification of the MDS algorithm developed by us. Additionally, the output coordinates had to be adjusted to include the known absolute coordinates of a single point. At the same time, the emphasis was on performing calculations on single-board computers of the Raspberry type Pi 4 B onboard drones [19].
For the practical implementation of the task, a Python script was created based on the developed algorithm, which uses the Scikit-learn library for the case of 10 UAVs. They are in the local coordinate system and one control object is tied to the global coordinate system.
The MDS algorithm applied to the drone distance matrix allowed us to find the relative coordinates of ten points in three-dimensional space (the local coordinate system of the swarm) and then adjust these relative coordinates to include the known absolute coordinates of a single point (Figure 8, Figure 9). reproduction errors even for the local coordinate system (as it is shown on example – Figure 12, Figure 13).
The use of Ultra Wideband (UWB) radio modules in agricultural UAVs has the following features:
Using UWB on UAVs increases the communication range compared to indoors, but also increases the delay in receiving data. For plant and soil monitoring, it is advisable to increase the distance between swarm drones to more than 100 meters.
The use of radio modules on UAVs raises the question of the effect of Doppler shift on the speed, distance and stability of data transmission.
The duration of the UWB pulse is much shorter (less than 1 millisecond) [21] than the symbol transmission time in other technologies, so the UWB technology provides high accuracy (approximately 0.01 m) and low delay in determining the distance between radio modules. Positioning accuracy and delay for the most used technologies are [21]: Bluetooth (1-5 m, over 3 sec.), WiFi (5-15 m, over 3 sec.), RFID (1 m., 1 sec.) , GPS (5-20 m., 100 millisec.), 5G (10 m., less than 1 sec.).
UWB radio modules are based on the IEEE 802.15.4a protocol [22]. The Matlab 2024a software package contains tools for modeling the physical level of this protocol. Modern UWB radio modules use channel #5 (6489.6 MHz) and channel #9 (7987.2 MHz). Since the 6.5 MHz band is close to WiFi frequencies that can be suppressed by anti-unauthorized drone protection systems, consider the effect of Doppler shift on channel #9, which is less busy.
Typical speeds of drones are 50-70 km/h. To assess the influence of the Doppler shift, it is advisable to consider a three-fold reserve relative to the average speed. For the transmitter carrier frequency of 7987.2 MHz, the values of the Doppler shift will be as follows: 50 km/h: 370 Hz; 60 km/h: 444 Hz; 70 km/h: 518 Hz; 100 km/h: 740 Hz; 150 km/h: 1110 Hz. The maximum Doppler shift of 1110 Hz was considered in the Matlab 2024a UWB channel simulator [21] and showed the applicability of radio modules for the task of positioning a swarm of agricultural UAVs.
Kalman filtering methods [23], particle filter methods [24], deep learning of neural networks [25] and combinations of the listed methods [24] are used to improve the navigation of individual drones or a swarm of drones.
True positions Noisy data Kalman filter Neural network Particle filter
Time Figure 14: The result of modeling noisy navigation data and applying different types of filters.
Simulations have shown that the Kalman filter is the most stable and accurate when using the FilterPy library for Python and TensorFlow for neural networks. Neural networks and particle filters also showed significant results, but with some differences in accuracy and stability.
The following combined approaches are also used to improve the positioning and navigation of drones [26].
1. Integration with simultaneous localization and mapping technologies – Simultaneous Localization and Mapping (SLAM):
Use of Kalman filtering methods and its variants in combination with SLAM algorithms to improve simultaneous localization and mapping. This allows drones to navigate more effectively in unfamiliar or dynamic environments.
2. Use of hybrid methods:
Combination of deep learning methods with traditional filtering methods. For example, learning neural networks to predict nonlinear system dynamics and using Kalman filters for final correction. This increases positioning accuracy and stability.
3. Integration of multisensory information:
Fusion of data from different types of sensors: laser location (Light Detection and Ranging – LiDAR), cameras, inertial measurement devices using filtering methods. This approach allows to improve navigation accuracy in difficult conditions where one type of sensor may not be effective enough.
4. Advanced optimization methods:
Use of adaptive algorithms, such as Particle Swarm Optimization (PSO) or genetic algorithms, to adjust filter parameters in real time. This makes it possible to increase the adaptability and robustness of the filter in conditions of a changing environment.
Conclusion: The Kalman filter showed the best result, stable over several simulation runs. The neural network provided little smoothing of the outliers of the random process, while the particle filter demonstrated over-smoothing for this example. However, in other simulations, its convergence to true values was at the level of a neural network. The integration of new methods and technologies, such as multi-sensor fusion, can significantly improve the accuracy and reliability of drone navigation in various environments.
As part of the work, the task of forming and maintaining the structure and configuration of a flock of agricultural UAVs in two-dimensional and three-dimensional settings was set. The formalization of the given task has been completed. Considered possible methods of mapping the graph formed by a swarm of UAVs into a two-dimensional Euclidean space by forming a basic triangle to create a relative coordinate system. To determine the coordinates of the graph’s remaining vertices on the plane and correspondingly increase the accuracy of local positioning, the multilateration method is used and considered simplified options – application of the trilateration algorithm, triangulation and a simplified algorithm for the degenerate case of two drones.
For the problem in a three-dimensional setting, the possibility of applying the multidimensional scaling algorithm using the methods of multidimensional scaling/reduction of dimensions is considered. The developed practical implementation of the created algorithm showed its efficiency during practical experiments, allowing it to determine the swarm elements local positioning, containing one to twenty elements.
The direction of further research is the development of an algorithm that allows, based on determined local coordinates, to eliminate disturbances introduced into the swarm structure due to internal or external factors, for example, the loss of one of the swarm elements [20].