AGDS: adaptive goal-directed strategy for swarm drones flying through unknown environments

The research on the mechanism of self-organizing behaviors promotes the development of the flying robot swarm. Vicsek et al. [20] studied the minimalist conditions of collective motion and proposed the Vicsek model, which only considered the velocity alignment rules between neighbors. Couzin et al. [21] proposed the Couzin model, which defined the zones and priorities of SAC rules. Levine et al. [22] proposed a social force model to study vortex motion based on Newtonian mechanics, which considered both velocity synergy and position synergy. Wu et al. [23] proposed an autonomous cooperative flocking algorithm for heterogeneous swarm, which solved the escort problem in the group cruise. By analyzing biological data, some scholars found unique behavior mechanisms, such as topological communication [24], hierarchical interaction [25], scale-free behavioral correlation [26], etc. Besides, the development of perceptual neuroscience has also promoted the study of collective biological behavior. Pearce et al. [17] proposed a model for long-range information exchange in bird flocks based on the projected view of each individual out through the flock and provided a solution for density control. Bastien et al. [27] proposed a purely vision-based model of collective behavior that showed the organized collective behavior that can be generated by relying solely on individual visual information. The model mainly focused on the perceptual information within the group without considering the perception of the environment. However, most of these works only explain the mechanism of collective motion from mathematical or biological data and have been seldom verified in artificial systems.

With the miniaturization of hardware, some scholars devoted themselves to deploying self-organizing algorithms in swarm robots. Slavkov et al. [28] created emergent morphologies in large swarm of real robots and reproduced the self-organized morphogenetic phenomenon of cells. Berlinger et al. [29] designed a fish-inspired robot swarm with implicit communication, which realized a variety of fish school behaviors such as synchrony, dispersion/aggregation, dynamic circle formation, and search-capture. Werfel et al. [30] developed a termite-inspired robot construction team construct complex predetermined structures. Rubenstein et al. [31] used a thousand-robot swarm to complete the self-assembly of complex two-dimensional shapes. Vásárhelyi et al. [14] deployed the flocking algorithm on 30 autonomous drones to achieve flocking flight and obstacle avoidance like a flock of birds. Balázs et al. [32] proposed a WillFull model for the persistence-responsivity trade-off in the swarm and used 52 autonomous drones to achieve abrupt collective turns like schools of fish or flocks of birds. Thus far, this is the largest self-organizing decentralized aerial swarm in an outdoor environment. The above works are mainly concerned with the reproduction of collective motions in nature on artificial collective systems.

Based on the above research, swarm robots are expected to perform given missions in various scenarios. Quan et al. [33] proposed a distributed virtual pipeline control algorithm by pre-planning the airspace as virtual pipelines without obstacles. This work addressed the pipeline passage problem of the drone swarm and was experimentally verified using 6 multicopters. Liu et al. [34] developed a pragmatic distributed flexible formation protocol to pass through a narrow and irregular channel. In this study, two leaders tracked predefined channel boundaries, followers tracked leaders, and a field experiment was carried out with 3 unmanned surface vessels. Nevertheless, the premise of study is that the environment needs to be predefined and known to swarm individuals. Virágh et al. [35] provided a model of a general autonomous flying robot integrated into a realistic simulation framework and achieved collective target tracking using 9 autonomous aerial robots in the real world. Balázs et al. [36] proposed a decentralized air traffic control solution for dense traffic problems and implemented crosswalk and package-delivery applications on 30 autonomous drones. Soria et al. [37, 38] deployed the proposed predictive model on the multicopter swarm, which ensured rapid and safe collective migration in cluttered environments. Schilling et al. [39] proposed to learn vision-based swarm behaviors in an end-to-end manner directly from raw images and implemented collision-free navigation of the drone swarm in the real world. In these works, each agent in the drone swarm has knowledge of the desired region.

To sum up, the research on the self-organizing flocking algorithm of the aerial swarm in various applications is still in its infancy. This paper mainly solves the problem of the drone swarm traversing an unknown environment. Different from the above works, we propose a self-organizing flocking algorithm, which does not require every agent to have knowledge of the desired region. This is particularly beneficial for the drone swarm operating in interference or electromagnetic environments, where knowledge of the desired region cannot be guaranteed for each aircraft. Based on using the mathematical bionic vision mechanism to perceive the environment, we propose a vision-based adaptive goal-oriented strategy, which can effectively improve the efficiency of the drone swarm traversing a complex canyon-like environment.

Consider aerial swarm consists of N individuals denoted by 1, 2, ..., N. The dynamics model of single drone can be simplified as a second-order integral model [40]. Therefore, we assume that the i-th drone with altitude hold mode satisfies the following model:where \({\varvec{p}}_i(t) \in {\mathbb {R}}^2\) and \({\varvec{v}}_i(t) \in {\mathbb {R}}^2\) are respectively the position vector and velocity vector of the i-th drone at time t, \(\tau _i \in {\mathbb {R}}^+\) is the characteristic time of velocity response, \({\varvec{v}}_{i\_\text {d}}(t) \in {\mathbb {R}}^2\) is the desired velocity vector of the i-th drone at time t and is also the output of the flocking algorithm. We do not consider the differences between drones, and thus assume that \(\tau _i = \tau \) for all drones. Because of the physical constraints of the drone, the magnitude of velocity and acceleration are limited to \(v_{\max }\) and \(a_{\max }\), respectively. The rules are given bywhere \(\delta t\) is the interval of velocity updates.

To describe the model of the drone swarm in mathematical language, we use an undirected graph [41] \({\mathcal {G}}(t)=({\mathcal {V}},{\mathcal {E}}(t))\) to establish the communication network among N drones, where \({\mathcal {V}}=\{v_1,v_2,..,v_N\}\) is the set of vertices representing the set of drones, \({\mathcal {E}}(t) \in {\mathcal {V}} \times {\mathcal {V}}\) is the edge set that defines the communication at time t.

We consider three different categories of metrics to evaluate the application of the drone swarm traversing an unknown environment.

This paper mainly solves the problem of the drone swarm traversing an unknown environment as a group under the condition that all agents cannot be guaranteed to have knowledge of the desired region. As shown in Fig. 1, the mathematical expression of the proposed flocking algorithm is described below:where \({\varvec{v}}_{i\_\text {sac}}\) is the SAC interaction term that includes separation \(({\varvec{v}}_{i\_\text {s}})\), alignment \(({\varvec{v}}_{i\_\text {a}})\) and cohesion \(({\varvec{v}}_{i\_\text {c}})\), \({\varvec{v}}_{i\_\text {v}}\) is the visual perception term for obstacle avoidance, \(\lambda _i\) is the informed coefficient used to represent the role, \({\varvec{v}}_{i\_\text {w}}\) is the will propagation term and \({\varvec{v}}_{i\_\text {t}}\) is the task information term.

We define these drones equipped with task information as informed agents. The identities of informed agents are hidden, and feedback information needs to be obtained from neighbors. Therefore, the status of all agents is equal. It also means that the loss of part of the informed agents does not affect the information interaction within the flock. Of course, the informed agents can also be dynamically added, or the previous ordinary agents can be designated as informed agents.

We are inspired by a well-known model that allows the drone swarm to roam in confined environments [14]. The model includes the rule of separation to prevent collisions between drones and alignment to reduce velocity oscillations. In addition to this, we also include a cohesion rule to prevent drone swarms from splitting up. Therefore, we integrate these three basic requirements into one, as follows:where \({\varvec{v}}_{i\_\text {s}}\), \({\varvec{v}}_{i\_\text {a}}\) and \({\varvec{v}}_{i\_\text {c}}\) define the requirements of separation, alignment, and cohesion, respectively. The three requirements are illustrated in Fig. 2.

In our model, we regard each drone as a disk with radius R. The vision projection field of the drone is a circle with a radius of \(r_{\text {vis}}\). The field projection of the drone i is divided into L parts, where l represents the label, \(l = 1,2,...,L\). Thus, line of sight \(\phi _{il}\) is abstracted as the connection between the center and the circumference (see Fig. 3a). Suppose the drone has a 360-degree field of view, but walls and obstacles will block its line of sight [17]. The angle between the two lines of sight is \(\Delta \Phi = 2\pi /L\). Obviously, the closer the robot is to walls and obstacles, the larger the obscured field of view. Therefore, we define the projection field function as follows (see Fig. 3b):

As shown in Fig. 3c, the velocity \({\varvec{v}}_i\) direction of the drone i is aligned with the \({{\textbf {x}}}_v\) axis, while its counterclockwise normal direction is the \({{\textbf {y}}}_v\) axis. We define the upper and lower bounds of the occupied angle of the field of view projection field as \(\phi _{il}^{\text {upp}}\) and \(\phi _{il}^{\text {low}}\), respectively. Thus, the motion of the drone i based on visual mechanism is formulated as follows:where \(p_{\text {fb}}\) and \(p_{\text {lr}}\) are linear coefficients that characterize shifting and steering, respectively. Note that the rotation matrix to transform a vector from the body coordinate system \({{\textbf {O}}} _v- {} {{\textbf {x}}} _v{{\textbf {y}}} _v\) to the world coordinate system \({{\textbf {O}}}-{{\textbf {x}}}{{\textbf {y}}} \) is given bywhere \(\psi _i\) is the heading of i-th the drone expressed in the coordinate system \({{\textbf {O}}}-{{\textbf {x}}}{{\textbf {y}}} \).

The motion of the drone can be decomposed into radial motion and normal motion. The former can characterize the acceleration and deceleration behavior, and the latter can describe the left and right steering behavior [27]. Therefore, the drone generates avoidance behavior by sensing the size and position occupied by the projection of obstacles or walls in its field of view. As shown in Fig. 4, the vision term \({\varvec{v}}_{i\_v}\) can produce a short-range repulsion, where the first term of the matrix in Eq. (17) can have a repulsion in the front and back directions (Fig. 4a), and the second term of the matrix in Eq. (17) can produce a repulsion in the left and right directions (Fig. 4b).

Due to the limited communication and sensing capabilities of a single drone, it is difficult for the aerial swarm to quickly avoid obstacles when they encounter obstacles. Surprisingly, as the starling encounters natural enemies or obstacles, it will quickly spread the valuable information among the flocks through calls and other means to quickly escape or avoid obstacles [17]. Therefore, in the real environment, it is essential to transmit valuable information quickly between robots. For example, when a robot in front of the flock perceives an obstacle, it can quickly transmit this information to other robots so that the flock can quickly respond to obstacle avoidance instructions. To tackle such issues, a will propagation term \({\varvec{v}}_{i\_\text {w}}\) is introduced and expressed aswhere \({\mathcal {W}}\) is a unit vector, which indicates the direction of the will propagation, given by [32]where \(\hat{{\varvec{v}}}_i^{WiSt}\) is desired velocity of the WiSt model, \({\mathcal {N}}(\cdot )\) is the normalization operator, \({\mathcal {R}}[{\varvec{v}};\theta ]\) is the operator that rotates vector \({\varvec{v}}\) at angle \(\theta \) on the \({{\textbf {x}}}-{{\textbf {y}}}\) plane and \(s_i^{WiSt}\) is the intrinsic angular momentum. Note that \(\Omega _i\) can be used to distinguish between strong and weak will. Further discussion of Eq. (20) may refer to Ref. [32].

Collective motions based on SAC self-organizing rules often show an aimless roaming phenomenon. Thus, we design a task information term to ensure that the drone can reach the desired region. The primary function of the term is to give knowledge of the desired region to the drones. The task information can be represented by the preferred direction \({\varvec{v}}_{\text {pre}}\), that is, a unit velocity vector pointing to the desired region. Therefore, the task information term is defined aswhere \(v_0\) is the preferred speed. Note the non-adaptive goal-directed strategy (non-AGDS) represented by Eq. (21).

However, drones operating in unknown environments often encounter serious conflicts between task information and obstacle avoidance. This leads to a situation where the drone is caught in a dilemma. In nature, migrating or foraging animals adjust their behavior based on real-time information about the environment. Therefore, we propose an adaptive goal-directed strategy (AGDS) based on visual perception.

Firstly, the angle \(\Delta \phi _{\text {safe}}\) suitable for safe passage of drone is determined as follows:We can then calculate the number \(n_{s}\) of the visual field occupied by the safe angle \(\Delta \Phi _{\text {safe}}\) as given byThe upper and lower bounds of the safe angle \(\Delta \Phi _{\text {safe}}\) in the projection field are \(\phi ^{\text {low}}_{\text {safe}}\) and \(\phi ^{\text {upp}}_{\text {safe}}\), respectively. Meanwhile, we determine the number \(n_{\theta }\) of areas in the visual field occupied by the angle \(\theta \) between the velocity \({\varvec{v}}_i\) and the goal-directed velocity \({\varvec{v}}_{\text {pre}}\). Next, we transform the original projection field \(V(\phi )\) (see Fig. 3a) starting with the velocity \({\varvec{v}}_i\) into the projection field \(V(\phi _{\text {task}})\) (see Fig. 5) starting with the goal-directed velocity \({\varvec{v}}_{\text {pre}}\) by rotating \(n_{\theta }\) regions equally.

According to whether there are obstacles in the line of sight of the task direction, there are two situations to deal with:

The first situation without obstacles is given bywhich implies that the line of sight is not blocked within the safe angle \(\Delta \Phi _{\text {safe}}\) range, then the task information term of the drone can be shown in Eq. (21).

Another situation with obstacles is expressed aswhich implies that there is a conflict between preferred direction and obstacle avoidance. The goal orientation can be adaptively corrected to alleviate such a conflict. We define a cross-correlation function to represent the relationship between the passable direction and the projection field as follows:where \(\varvec{{\mathcal {M}}}(k\Delta \Phi )\in {\mathbb {R}}^{n_{s}}\) is a weighting matrix indicating the degree of security of the safe region \(\Delta \Phi _\text {safe}\) whose elements are all set as 1. Therefore, the value of \(V_c(\phi _{\text {task}})\) is in the range [0, 1]. Any region that satisfies \(V_c(\phi _{\text {task}})=0\) is a passable direction.

\(V_c(\phi _{\text {task}})\) is divided into two parts (\(V_c^{\text {L}}\) and \(V_c^{\text {R}}\)) with the initial preferred direction \({\varvec{v}}_{\text {pre}}\) as the origin, and the passable directions on both sides are obtained:Convert the above passable directions in Eq. (27) to the projection field \(V(\phi )\) with velocity \({\varvec{v}}_i\) as the origin and calculate the sight line of the passable directions as follows:where \(\phi _{im}^{\text {task}}\in [\phi _{im}^{\text {L}},\phi _{im}^{\text {R}}]\). Thus, the corresponding angle of the sight line \(\phi _{im}\) in the projection field \(V(\phi )\) is \(\Phi _{i\_\text {m}}\). The angle \(\Phi _{i\_\text {m}}\) is converted to the world coordinate system \({{\textbf {O}}}-{{\textbf {x}}}{{\textbf {y}}} \) as follows:Finally, the task information with adaptive goal-directed strategy (AGDS) is defined as follows:

To assess the reproducibility of the results, we performed 15 stochastic simulations for each of the six initial positions of the informed agent and for the two strategies, and we report here the aggregated performance results (Fig. 12). The initial position of the informed agent has a great influence on the flocking algorithm with non-AGDS. When the initial position of the informed agent is 3#, both \(T_{\text {end}}=32.66\pm 7.52s\) and \(N_{\text {end}}=6\pm 0\) are significantly better than other initial positions. In contrast, the flocking algorithm with AGDS performs better on \(T_{\text {end}}\) and \(N_{\text {end}}\) (1#, \(T_{\text {end}}=30.05\pm 1.98s\); 2#, \(T_{\text {end}}=30.45\pm 3.00\); 3#, \(T_{\text {end}}=30.18\pm 3.64s\); 4#, \(T_{\text {end}}=23.53\pm 3.09s\); 5#, \(T_{\text {end}}=21.74\pm 0.15s\); 6#, \(T_{\text {end}}=25.87\pm 2.78s\); \(1\#\sim 6\)#, \(N_{\text {end}}=6.00\pm 0.00s\)).

Regardless of the initial position of the informed agent, the drone swarm successfully reaches the desired region. This means that we can increase or decrease the informed agent during the flight, which will not cause the conflict between task information and obstacle avoidance. The aerial swarm deployed with flocking algorithm with AGDS also performed very well in tracking the preferred swarm speed (\(\Psi _{\text {vel}}=0.98\pm 0.01, 1.00\pm 0.02, 1.01\pm 0.01, 0.98\pm 0.01, 0.98\pm 0.03, 0.97\pm 0.01\)). In addition to this, the drone swarm has better consistency \(\Psi _{\text {corr}}\) during flight. In terms of safety, the minimum distance \(r_{\text {min}}\) and the average distance \(r_{\text {ave}}\) between drones of both strategies are in the safe range (\(>2R\)).