Keywords

1 Introduction

Optimising different aspects in swarms of drones such as autonomous navigation, collision avoidance, payload reduction, resource allocation is gaining traction in the research community [1]. The deployment of swarms of UAVs adds remarkable advantages over single UAVs, as the UAVs in a swarm have the ability to work in a collaborative manner, and consequently have demand in various fields ranging from commercial use to search and rescue to military applications, and etc [2,3,4]. From the general perspective, the nodes or agents in the swarm can be classified as: 1) reactive agents, where agents react to changes in the environment or a signal from another agent; 2) evolutionary agents, these are inspired by evolutionary algorithms and work on the basic principles of reproduction, mutation, recombination, and selection; 3) flocking agents, mimic the behaviour, inspired by e.g., swarms of bees or flocks of birds, moving together; 4) cognitive agents, inspired by the cognitive architecture, enables them to take decisions, process data, and make predictions [5,6,7].

Formation maintenance and collision avoidance are the most important problems in navigation of a swarm of drones [8, 9]. In a formation the relative location of each agent is defined w.r.t. the other agents in the swarm, while the collision avoidance focuses on the path planning for individual agents and is responsible for avoiding any possible collisions between agents within the swarm and the agents and objects in the environment. The methodologies, for maintaining the formation, can be categorised into the following three generic approaches [10, 11] : 1) virtual structure, in this approach the drones are collectively considered as a single drone and navigated through the trajectory as such [12,13,14]; 2) leader-follower, in this approach every drone functions individually and autonomously while maintaining and adjusting its position according to the leader and its neighbours in the formation [15,16,17,18]; 3) behavior based approach, where from a pre-defined strategy, one of the numerous behaviours is selected by the drone [19, 20]. Furthermore, collision avoidance algorithms can be classified into the following three generic categories: 1) optimization based algorithms are focused on determining the near-optimal solutions for navigational and path planning purposes of each drone relative to other drones or objects in the vicinity, by relying on the already known locations and sizes of the statics objects for an efficient route calculation [21,22,23]; 2) sense and avoid based, by simplifying the process of collision avoidance to individual detection and avoidance, these have short response times and require much less computational power, individual drones are controlled without the knowledge of other drones paths etc [24,25,26,27]; and 3) force-field based, in this technique each drone is considered as a charged particle with attractive or repulsive forces. These attractive/repulsive forces between different drones themselves or drone and obstacles are used to generate the path for the drone to be taken [28, 29].

In this paper, the leader-follower based approach is used for the swarm due to its ease of analysis, implementation, scalability, and reliability [18, 24]. The focus is cost saving by reducing the processing power and reducing the payload carried by individual drones while still keeping the swarm autonomous and able to navigate to its destination. A global collision avoidance algorithm is defined for the leader agent in the formation. Which is then used by the follower agents in the adaptive autonomous mode to be able to calculate the relative locations/coordinates of the objects in the environment as observed by the leader, hence tackling the generic problem of tracking by a follower relative to the master.

The rest of the paper is structured as follows. Section 2 gives the motivation. Development of the proposed algorithm is described in Sect. 3. Section 4 focuses on simulation results. Finally, Sect. 5 concludes the paper with some discussion and future work.

2 Motivation

There are many scenarios when the intelligent decision making is not required to be done by every single agent in a swarm. Especially when it comes to static environments, not all drones in the swarm need to be equipped with all sensors and similarly all the drones are not supposed to be taking decisions intelligently. As it increases the processing power required by individual drones resulting in decreased battery timing and hence decreased mission life on one charge. For instance in huge warehouses or in cities with high rising buildings, where normally the dynamic variables w.r.t. obstacles approaches to zero, if only one drone i.e., the leader of the swarm, can see and do all the processing required to take the decisions, it takes a lot of processing load off the followers. In this paper we consider this technique to decrease the overall cost of the swarm, e.g., power consumption of sensors, by deliberately activating and deactivating some of the follower sensors in run-time. Taking inspiration from reactive agents [5] and using our proposed technique, for instance, if the leader detects any change in environment or dynamicity, it signals to the followers to turn on the adaptive autonomous high-conscious mode wherein the followers turn on more sensors to pass the critical situation, and later they switch back again to the low-conscious mode. In the case of the high-conscious mode, we utilised the collision avoidance technique in [24], which will be activated and used by individual drones of the swarm. The main motivation behind this is the cost reduction by reducing the power consumption and processing required by every individual drone in an autonomous swarm.

3 Proposed Approach

The general pseudo code of the global leader is given in Algorithm 1. We assume that the UAVs are assigned IDs and the leader-follower connection has established before the mission is started. Using the on-board processing units, each node is executing this top-level algorithm locally. Algorithm 1 starts by checking if the global leader for the swarm has been declared, and declares the leader if it has not been set up yet. After this, the followers are connected to their immediate leaders (Lines 3–8). After this, every node (starting from the leader) sends its coordinates, along with the distance and angle at which an obstacle (if any) has been detected, to its follower (Line 11–14). Based on the received signal and coordinates from FollowerMode, the node checks and sets the Lead_is_Alive flag depending on if its leader is still functioning properly or not (Line 14). If there’s is no response from the leader, the node in question announces itself as its own leader. The node/leader cross-checks the coordinates it received from its follower(s) after the follower has calculated the distances and angles (Line 15). A criticality check is done by analysing if the absolute value of the received coordinates or angles is greater than a certain threshold, in this case the environment is defined as dynamic (Lines 16–18). If the node is itself the global leader or if the environment has been declared as dynamic, then the collision avoidance module is called (Line 20–21). Otherwise, if the node is not the global leader and the environment is not declared as dynamic, the FollowerMode module is called (Line 23–24).

In case the node itself is the leader, the timeout signal is not checked; otherwise, every node checks if it is receiving signals constantly from its respective leader. If the leader has not transmitted its coordinates by timeout, the follower declares itself as its leader and turns on its sensors for active collision avoidance maneuvering.

figure a

3.1 Coordinate Calculation

In this function (specified in Algorithm 2), the follower receives the coordinates of the leader and the coordinates of the obstacle detected (if any). If there is no feedback from the leader by the timeout, the node returns false for its leader status (Lines 2–3). This information is then used by the node to declare itself as the leader for the fail safe mode in Algorithm 1 (Lines 21–22). Otherwise, based on its own coordinates, the node calculates the translational coordinates of the obstacle and returns the calculated values to be cross-checked (Lines 6–8), as shown in the Fig. 1 (Table 1).

figure b
Fig. 1.
figure 1

Distance and direction calculation (Color figure online)

Full size image
Table 1. Description of variables from Fig. 1
Full size table

3.2 Adaptive Autonomous Mode

If there are any obstacle(s) in the detection range, then this mode, Algorithm 3, is called by the leader. If the environment has been declared to be dynamic, then those node(s) which are working individually call this module locally. The system calls for collision avoidance module and keeps on checking the status of the environment (Line 2). In order to successfully avoid collisions, we utilise the collision avoidance technique presented in [24]. As soon as the collisions have been avoided, the status of the environment is set to static and the control is returned to the main module (Lines 3–5).

figure c

4 Simulation Results

The initial conditions/assumptions for our work are defined as follows:

  1. 1.

    all UAVs have constant ground speeds

  2. 2.

    UAVs obtain their own position vectors using the on-board localization techniques

  3. 3.

    there is no information loss in communication between the UAVs

Fig. 2.
figure 2

LiDAR point set at starting point of simulation and when the obstacles are visible (Color figure online)

Full size image

The LiDAR sensor used in our experiment is Velodyne Puck LITE. The data generated by Velodyne Puck LITE was then used and injected into the simulation platform for visualisation purposes, generation of the obstacle(s), and verification of the proposed algorithm.

Figure 2, shows the LiDAR data from different angles and at different intervals for instance at starting point (Fig. 2(a)), when the obstacles enter detection range (Figure (b)), when the obstacles are in close vicinity (Figure (c) and 2(d)). In these figures, the position of the drone equipped with LiDAR is shown as the blue, red, and green bars indicating the z, y, and x-axes, respectively.

Fig. 3.
figure 3

Simulation Results at different instances (Color figure online)

Full size image

The simulation results shown in Fig. 3 show the V-shaped formation, in which UAV 1 (blue circle) is the leader (which is getting the data from LiDAR as shown in Fig. 2 and UAV 2 (red) and 3 (green) are followers calculating their coordinates as shown in Fig. 1. Figure 3(b) shows the scenario where the obstacle is within the detection range of the leader but not in its path. However, UAV3 upon performing necessary calculations realises that continuing along the current path will lead to a collision, and hence it deviates away from its original path as can be seen from the traces of the UAVs.

Figures 3(c) and 3(d) show the case when they go through the obstacles. Notice UAV2 does not deviate from its path and maintains the desired position w.r.t. UAV1 even when the second obstacle is close to it. That is because the calculations performed locally by UAV2 indicate that the collision is not possible given that the obstacle is stationary and out of the collision radius. However, after avoiding the second obstacle, UAV3 maintains the pre-defined minimum safe distance from UAV1 since going back to formation is not possible due to the third obstacle in the bottom. When the final destination is moved at run-time, Fig. 3(d), UAV3 comes back to its position in the formation, turns off the sensor, and starts following UAV1 by translating the coordinates transmitted by UAV1. Figure 4(a) shows the distances maintained by the UAVs throughout the simulation.

Fig. 4.
figure 4

Results

Full size image

5000 mAh battery was used in the setup, and the power consumption of one Velodyne Puck LITE is 8 W (in typical conditions). Based on these values we calculated the power consumed by the sensors of all nodes, by tracking the amount of time every sensor on each agent was active or turned on, during the simulation with and without our proposed methodology (shown in Figure (b)), where power consumption is given in milli-Watt hours. It is evident that utilising the proposed technique we can significantly reduce the power consumption of on-board sensors by approximately 50%, and hence increase the mission duration on one charge.

5 Conclusion

In this paper, we developed an algorithm for pre-defined formation of multi-agents in a static environment, where under normal circumstances one agent can see the surroundings and the other agents blindly follow. However, depending on the scenario the follower(s) can turn on their sensors for safety purposes. The proof of concept using simulation tools was performed to verify the method of translational coordinates calculation in a system consisting of multiple agents, i.e., a swarm of drones. The simulation results shown provide sufficient proof that the method works reliably in simulated static environments. It is evident from the results that the proposed algorithm helps reducing the power consumed by the sensors over time. In the considered test scenario it turned out to be approximately half the power consumed if the sensors are used in a continuous mode. In general, this power saving naturally depends on the dynamicity/structure of the environment. In future, we plan to further develop this algorithm by extending it for moving obstacles and test its usability in dynamic environments. This will be very interesting to analyse especially when two swarms have to cross paths i.e., multi-swarm cross-overs, as only the leader agents of both swarms can communicate, and the follower agents in the respective swarms use the leaders’ translated coordinates.