UAV Decentralized Formation Flying For Surveying Missions, Using Behavioral Techniques

Slide 3

UAV’s have proven their utility in many scenarios, such as in surveillance, inspection, and mapping. 

In this thesis, the focus is to take advantage of having a team of UAVs to perform emergency surveying missions working as part of a larger multi-agent emergency response. The reason being, by having a formation, more data can be collected at one time versus a single UAV.

Now, when considering formation maintenance architectures, various works employ one of the general formation maintenance structures. 

In the leader follower method, seen in FIGURE 3A, all the information is handled by the leader, with the followers simply following the leader.  This structure allows for low-cost follower agents but introduces a single point of failure with the leader. 

Now looking at FIGURE 3C, the Virtual Leader and Virtual Center formation method functions by following the trajectory determined for the virtual center or virtual leader. Each agent possesses their own estimation of the location of the virtual center/leader, and follows along in formation accordingly. This eliminates the single point of failure as in the Leader-Follower approach in FIGURE 3A. 

In the behavioral formation method, shown in FIGURE 3B, each respective agent makes use of discrete behaviors to result in an emergent desired behavior for a situation.  This method was made notable in papers such as in Reynolds 1987 simulating flocking behavior with the behaviors of collision avoidance, velocity matching, and flock centering.  Other works take the same behavior approach and apply it to stricter formation patterns, such as in Balch 1998, where a formation of military HUMVs go through an obstacle course using different formation patterns and compared different strategies for referencing the formation. 

This general categorization may be not sufficient to distinguish best use cases of each method since there is plenty of overlap between them.  But for this thesis, the behavioral approach is utilized since adjustments to the behaviors can be handled discretely, and it provides a simple architecture.

Slide 4

Now getting into the mission scenario where the swarm of UAVs will be deployed.

The scenario starts with a major earthquake occurring in the greater Los Angeles area, pictured on the slide. First responders need to develop situational awareness of important areas by developing a 3d map through photogrammetry to aid in emergency response.

UAV are set up in an open area as a temporary base of operations.

The mission criteria is passed to the UAV during set up, then the swarm takes-off, and gets into dense formation once reaching altitude.

Next the swarm gets to the starting point of the surveying mission, changing into row formation, and proceeds to take images of the area(s) of interest.

Once the surveying is complete the swarm changes back to dense formation and returns to the home base.

Slide 5

For this thesis we look at photogrammetry since its use is common for surveying and it is possible to attain 3D models with photo visual accuracy. Additionally, the equipment cost could be reduced with equipment selection.

Getting into the details of mapping through photogrammetry, there are some requirements for consideration with the UAV formation.

To attain the images, it is common for single UAV to take the flight path as shown in FIGURE 5A, ensuring images taken overlap.As shown in FIGURE 5B, it is important to maintain a minimum front and side overlap of 70% to accurately create a 3D representation.

Additional aspects to consider when capturing images are flight speed, flight altitude, camera angle and camera size. High flight speeds at low altitudes can introduce motion blur, while high altitudes can lose details depending on the camera. Additionally, to capture tall features, camera angle must be introduced otherwise occluded areas appear in the 3D representation as shown in FIGURE 5C.

For scenarios where time is not critical, these problems are not as apparent since an area can be re-surveyed to gather more images.

Slide 6

For this thesis, the model is based on the M300RTK by DJI shown in FIGURE 6A.

It was selected due to its commercial use and capability as a quadrotor for surveying and inspection.

A space model was provided, as shown in FIGURE 6B, and by applying property values, inertial data could be determined.

As for powertrain data, since the drone lacked this information, a similarly spec’ed powertrain system by DJI was substituted, which provided the powertrain performance curves shown in FIGURE 6C.

Taking the data from the referenced quadrotor and powertrain systems, a typical quadrotor model is developed shown in FIGURE 6D.

Slide 7

And so we get the resulting state space model, shown in EQ 7a, representing the non-linearly modeled system for control.

We make use of feedback linearization for control of this system, using state representations 2,4,6, and 8; which model angular acceleration of roll, pitch and yaw, and linear acceleration along the Z axis.

Slide 8

Here we have the quadrotor control diagram.

For each UAV, a single controller is represented as such:
The behavioral controller works as a layer of abstraction, providing the quadrotor with linear velocity commands and the yaw position.

Next the Position Controller takes the linear velocities, and outputs the reference roll and pitch angles. Additionally, the position controller determines the altitude control command to the UAV.

Then, the attitude controller takes the roll, pitch and yaw reference positions and determines the control commands U2 to U4 to the UAV.

Finally, these motor commands are converted to forces and torques to be applied to the model in gazebo simulator.

From the sensors in the Gazebo simulator, the current state of the UAV is passed back to the controllers for reference.

Slide 9

Now moving up a level of abstraction, we look at the communication network implemented.

With multi-agent cooperation, communication is crucial.

For this thesis, with the idea of teams of UAV completing tasks, a designated UAV would be assigned as a gate node, provided they have the proper equipment for long range communication.

This UAV functioning as the Gate Node would receive communications from the ground control, then it would publish the data to the rest of the swarm.

Within the swarm, communication is done through a simple flooding algorithm. Each UAV possesses data on the position and velocity of all other UAV in the swarm, and this information is propagated through the swarm.

Slide 10

Now, looking at the behavioral controller, to understand the interaction of how all the behaviors interact, we look at EQUATIONS 10A and B.

Starting with EQUATION 10A, the velocity vector commands are added up, with the magnitudes of each behavior in the left horizontal matrix and the unit vector direction for each respective behavior in the right vertical matrix.

Taking this vector sum from EQUATION 10A, the vector is normalized and rescaled by the constants setting the maximum allowable velocity in EQUATION 10B.

Slide 11

Now getting into the individual behaviors, we start off with the altitude behavior.

The vector direction is towards the goal altitude and the magnitude is dictated by the cases shown in EQUATION 11A.

Following the cases, bottom to top, we start from a distance outside the maximum boundary, so the UAV is commanded to go at 100% of the designated weight value set.

Then, from the maximum boundary, the commanded velocity magnitude is linearly decreasing until reaching the minimum boundary.

Once within the minimum boundary, the commanded velocity magnitude is se to zero.

The minimum boundary ensures a small region for providing stability in maintaining altitude. Otherwise, oscillations about the goal altitude would be exhibited.

Slide 12

Now getting into the goal seeking behavior, the application is similar as the altitude maintenance, albeit on the inertial X-Y plane.

The vector direction is towards the goal position in the inertial XY-plane, with the goal position being a formation node with the formation center at the goal position as shown in FIGURE 12A.

The cases shown in EQUATION 12A of this behavior are similar to the altitude behavior, with the only differences being a lack of a minimum boundary and there is a case for collision avoidance, where the goal-seeking behavior is minimized when near neighboring UAV.

Slide 13

For maintaining formation, it is necessary to have the assigned positions in the formation, the location and the orientation of the formation.

Each UAV possesses the same information regarding the mission and formation independently of each other. Data regarding positions of other UAVs is constantly updated asynchronously.

For determining the assigned positions within the formation, each UAV develops a distance cost table to the formation nodes, as seen in FIGURE 13A, using the Python SciPy optimization library.

For the formation maintenance behavior shown in FIGURE 13B, the formation center is imposed on the swarm center (FC), which is determined independently by each UAV. Orientation of the formation is towards the next waypoint based on the current swarm center position.

Getting back to the formation maintenance behavior, the behavior functions similar to the goal-seeking behavior as shown in EQUATION 13a.

Slide 14

The collision avoidance behavior is quite different in function compared to the other behaviors.

Instead of using UAV to UAV distance multiplied by the weight to determine the collision avoidance velocity magnitude, the time to collision is used. The weight is set to be the ideal distance the UAV should move to avoid collision.

The collision avoidance behavior is set to remain inactive until within maximum boundary, where in this thesis was set to 75% of the formation spacing. Once active, the algorithm determines if the UAV are on collision course with each other.

If a potential collision is determined, and the time to collision is below the maximum time to collision, the behavior velocity magnitude is calculated as shown in the last case of EQUATION 14A.

If at any point the UAV enters the minimum boundary of another UAV, then the goal-seeking behavior and formation maintenance behavior are set to a minimum value. This prioritizes collision avoidance but still nudges the UAV into the formation position slowly.

Now regarding the vector direction, as denoted by “r_jk” in FIGURE 14A, it is the normalized distance vector sum as represented in “V_c-avoid”.

With that, we move onto the simulation studies…

Slide 15

To analyze the swarm, simulations were ran where the swarm moves along a 40x40m square pattern, changing formations every 20 meters as shown in FIGURE 15A. And the formation spacing was set to the minimum amount for expected operation (8 meters).

(PLAY VIDEO)

This task tested the ability of the UAV to:

1. Get in and out of tight formations
2. Avoid collision during reformation
3. Maintain formation

Here we have a top-down view of this reformation test. (DESCRIBE VIDEO)

Slide 16

Now, investigating the effect of independently calculating the swarm center by each UAV during the reformation test as shown in FIGURE 16A, we expect to see some error in the true swarm average location versus what each respective UAV determines as the swarm average location.

Looking at FIGURE 16A, we see the formation moving along the X-axis, then it changes formation, and finally proceeds to move along the Y-axis. Looking at FIGURES 16B and 16C, we have the calculated position error in the X and Y axes respectively of Drone 3; Which is the grey line in FIGURE 16A.

In FIGURE 16B, we have position error along the X-axis.  Following the graph on FIGURE 16B with FIGURE 16A, an error of nearly 0.25 meters is shown initially due to reformation from row formation to circle formation.  As the formation slowly moves towards the waypoint, the error remains below 0.1 meters. 

Again, reformation takes place and then the formation settles. Since motion is along the Y-axis, the error along the X-axis is nearly zero.  Comparing Figures 16B and 16C, we see the errors are similar based on the direction of motion of the formation.

Knowing that position error is near zero in the direction the formation isn’t moving along and a maximum of 0.2 meters along the direction of motion after reformation, the overlap between images taken during surveying can easily compensate for this error.

Slide 17

Next, we look at collision avoidance.

In the scenario shown in FIGURE 17A, based on formation assignment, Drone 3 needs to overtake Drone 2 to get into single-file formation, which causes the collision avoidance behavior to activate.

Looking at the green dashed lines representing the collision avoidance behavior magnitude in Figures 17B for Drone 2 and Figure 17C for Drone 3, we see the successful effect of the behaviors to the flight paths taken by the UAV in FIGURE 17A.

The only downside being that the UAV are not more reactive at close collision distances.

Slide 18

Since the use case of the swarm is for emergency response, failure of a single drone is considered while maintaining communication.

Two scenarios are considered:

Simulation 1, as shown in FIGURE 18B, considers total motor failure of Drone 1, 35 seconds into the simulation. After failure of Drone 1, the other UAV attempt to maintain formation but oscillate about a single position due to the goal-seeking behavior.

Simulation 2, as shown in FIGURE 18A, considers partial motor failure of Drone 1, 35 seconds into the simulation. The affect is Drone 1 drifts away from the expected flight path and while the other two UAV attempt to reach the goal, they still slowly follow along fighting between the goal seeking and formation maintenance behaviors.

The solution for total failure could be a simple re-organizing of the swarm group based on the altitude of the failed UAV. But a solution for partial failure, such as drifting away from the expected flight path is not so straight forward.

Slide 19

Finally, we get to the mission scenario initially proposed.

The UAV is set to survey a 250 x 250 meter area, maintaining a 70% overlap between each row.

We compare the time taken to accomplish the mission between a single UAV versus a formation of three UAV, as shown in the FIGURES and TABLE.

The expectation is to reduce the time of the mission by nearly 2/3, but comparing the first two simulations there is a 51% difference.

After taking the time to reach the area to be surveyed, the time still deviates from expectations.

This result is expected from what we see during formation flight , since there is essentially a catch-up mechanism built into a swarm center referenced formation.

Slide 20

Read Conclusions.