USNA Research

Urban Convoy Escort Utilizing a Swarm of UAVs

 

This page describes the work completed as part of the requirements of the Trident Scholar program.

 

Advisor – Associate Professor Matthew G. Feemster, Weapons and Systems Engineering Department
Advisor – Roger Cortesi, Naval Research Lab
Major – System Engineering (Honors)
Wil Selby USNA Thesis NRL SIMDIS Simulation

This research extended the work of Eric Justh and P. S. Krishnaprasad from the University of Maryland, College Park. Their 2004 paper “Equlibria and Steering Laws for Planar Formations” published in the Systems and Control Letters journal described the UAV formation control algorithm evaluated in this research.
pdf  bibtex

Abstract

This project, in conjunction with the Naval Research Lab (NRL), evaluated and modified a current UAV control algorithm to perform a security role for military convoys in urban terrain. The desired end state was to provide the simulated military convoy with constant UAV sensor coverage as the convoy navigated an urban environment.

This research used the NRL multi-vehicle simulator to asses the behavior of the control algorithm under real world conditions. This included using improved vehicle dynamics and real world GPS tracks for convoy routes. The control algorithm was evaluated using performance metrics including the distance between UAVs, distance from each UAV to the convoy, and UAV fuel consumption. The control algorithm was tested in simulation on three scenarios involving a UAV swarm following a military ground convoy. The Basic Navigation scenario simulated a mechanized convoy while the Foot Patrol scenario simulated soldiers on a foot patrol. Lastly, the Obstacles en Route scenario simulated a practical convoy route with constant speed fluctuations.
Based on the data taken from simulations, the control algorithm was modified to provide effective sensor coverage of the convoy in the scenarios. Also, several blending strategies were created to transition between rectilinear and circular control. Specifically, one involving the bearing rate of the convoy relative to the UAVs provides a more secure and low tech form of control than traditional methods. This research identified the limitations of the UMD control algorithm, provided vital data necessary for further development of the controller for field tests, and developed a cumulative design process for future NRL control algorithm investigations.

Multi-vehicle Control Law

The control algorithm is depicted below in both a mathematical form as well as a conceptual form. These equations above control the position and approximate orientation of the UAV. In the steering control equation, the term involving μ (mu) aligns the heading directions of the vehicles, the α (alpha) gain is used to control the distances between the UAVs as regulated by the r0 distance, and the η (eta) term is used to keep the vehicles abreast of each other. Each of
these terms emulates a biologically plausible behavior. These specific gains are the primary focus of this research. The gains effectively create a weighted average of the three behaviors to produce a steering command for the vehicle based on its position and heading relative to all other vehicles in the swarm. Based on the scenarios and performance metrics, these gains will be modified extensively to create an algorithm tuned for specific objectives in an urban environment.

Wil Selby USNA Thesis UAS Swarm Control Law

Wil Selby USNA Thesis UAS Swarm Control Law Behaviors

With all positive values of the variables, the swarm follows a rectilinear form of behavior. However, when the term that controls heading is dropped, the swarm performs circular trajectories. The plots below show these two basic behaviors. A blending strategy to efficiently transition from these behaviors was evaluated as well. Variables such as convoy speed, distance from the UAV to the convoy, and the bearing rate of the convoy were used to determine how to blend these two control schemes as well as several functions to determine the weights of each of the controllers.

Wil Selby USNA Thesis UAS Rectilinear Control Simulation

Wil Selby USNA Thesis UAS Circular Control Simulation

NRL Multi-vehicle Simulator One deliverable for this project was the migration of NRL’s multi-vehicle simulator to the Systems Department at USNA for both student and faculty use in future research. The simulator is a powerful tool that can be used to test control algorithms using vehicle models with advanced and accurate kinematic models. The NRL multi-vehicle simulator uses a CybelePro interface which supports agent to agent message transfer that is helpful in applications such as swarm simulation. CybelePro also limits the amount of information the UAV agents have access to by only allowing their position to be broadcast on the message traffic at certain times. This resembles the real world since no vehicle has real-time omnipotent knowledge of the properties of the other UAV and convoy agents. Once CybelePro is installed, the user is free to run simulations.

NRL’s visualization software, SIMDIS, was used to generate scenario visualizations in three dimensions. To facilitate the use of SIMDIS, a MATLAB script was created that is able to take a raw data file consisting of time and position data and convert it into the .asi file format that is needed by SIMDIS (Appendix 5). This allows students and faculty to use simulated or experimental data to create professional video files of their trials in a graphic rich environment for use in presentations or post data analysis.

Lastly, it was necessary to create a JAVA class that could read in a GPS text file and inject it into the simulator as convoy route. To get the GPS data, a Garmin handheld GPS receiver from NRL was used to log the vehicle’s position every second. A program called GPSBabel was used to extract the GPS waypoints that were logged by the GPS and convert it to a form that was more convenient to work with. The final GPS track was saved in the form of a comma separated value file which followed the pattern of “waypoint number, latitude in degrees, longitude in degrees, altitude in feet, date, and time.” This data was extracted and converted from degrees to radians for the simulator. Also the time stamps are converted from raw time to elapsed time. The next step in the injection process is to broadcast this message to the other vehicles in the simulation. The vehicles update their position every second which is limited by the logging rate of the GPS receiver. To solve this issue, a timer is started when the simulation begins and every time the elapsed time of the GPS waypoint equals the elapsed time of the simulation, the GPS point is broadcast on a message channel using the CybelePro infrastructure. Also, the code was modified to support time stamps down to the millisecond, which was artificially created through MATLAB scripts for use in several of the scenarios.

Wil Selby USNA Thesis Software Architecture Overview
Algorithm Evaluation
In order to determine an overall performance value for each parameter set, a cost function was used to combine the three main performance metrics into one value. First, the distance between vehicles is calculated over the entire simulation run. The percentage of the time that the intra-vehicle distance is below a user specified minimum value is reported for this performance metric. This is a binary metric, meaning that the vehicle is either above the minimum distance or below it. The distance between UAVs was measured to determine the risk of collisions. However, if the distance between UAVs is too large, there is a potential for communications losses between the UAVs. The infinite norm was used to compute the collision percentage between UAVs. This was used to simulate the worst case scenario.

The second metric is the distance of the vehicle away from the convoy. The performance metric represented the percentage of the time that the vehicles were outside of a maximum distance away from the convoy and was calculated in a linear method and not a binary method as the collision metric was. When the vehicle is at or under a minimum distance, there is no penalty. However, as the vehicle moves away from this minimum distance, the performance penalty increases linearly until it reaches a value of one. At a value of one, the vehicle is at or beyond a specified maximum distance from the convoy and the sensors are unable to constantly cover the convoy. This way the performance metric is a strong representation of the distance between the UAVs and the convoy and penalized larger values of r0. The one norm was used to compute the average distance between the UAVs and the convoy.

Lastly, it was necessary to calculate a performance metric to determine the fuel efficiency of the UAVs as well as a method of penalizing large gain values. As the gains increase, they create larger and larger values of u, the output of the algorithm. However, due to the vehicle kinematics, there are physical limitations on the size of u. The average amount of steering energy was calculated using the Euclidian norm.

Wil Selby USNA Thesis Convoy Range Performance Metric Description

Wil Selby USNA Thesis Collision Hazard Performance Metric Description

Wil Selby USNA Thesis Steering Energy Performance Metric Description

These were combined in a cost function to compute an estimate of the performance of the algorithm for that specific set of gains. The cost function was C=(.1*Steering)+(.2*Convoy Range)+(.7*Collision). The weights for each metric were kept constant throughout the experiments.

Scenario 1: Basic Navigation

The goal of this research was to find the set of gain values which provided the best performance for the urban convoy scenario. To begin this research, only the rectilinear form of the control algorithm was used and along with a GPS track that moved continuously at a constant speed with no stops. This scenario simulated an ideal mechanized convoy. The desired endstate of this scenario was to determine the basic navigation parameters controlling obstacle avoidance and maneuverability

Wil Selby USNA Thesis Mechanized Convoy Scenario 1 Route
Wil Selby USNA Thesis Mechanized Convoy Scenario 2 Route

Some general conclusions were drawn from this scenario:

• Alpha and eta have the largest influence on swarm behavior.
• Ro = Rmin greatly increases chance of collisions and steering energy with no noticeable effect on convoy range.
• Parameters for 3 vehicles less flexible than 2 vehicle case, but still effective. Gain scheduling unnecessary.
• Less complex routes result in smaller parameter values. Alpha parameter values highest for both routes.

Scenario 2: Foot Patrol

The next scenario for analysis was designed to test the parameters of the circling form of the control law. To transition to this form of the algorithm the heading alignment term μ is dropped. If the user desires the vehicles to maintain a circular orbit, the vehicles should not have their headings aligned. This prevents problems when vehicles are on opposite sides of the orbit and facing opposite directions. By removing the alignment behavior, the control law is able to support stable circling formations which are useful when tracking slow moving convoys or foot patrols. Thus, convoy routes that mimicked foot patrols were created in order to isolate the circular control law for analysis. For this scenario, the convoy needed move at a slow and steady pace simulating a foot patrol. Having obstacles in the route of the convoy was no longer an issue. The convoy would be moving at such a slow speed that obstacles would not have an affect on the swarm’s performance. The goal of this scenario was to evaluate loitering formations as the UAVs follow a slowly moving target and to determine the relative speed limitations of the control law.

Wil Selby USNA Thesis Foot Patrol Scenario 1 Route

Wil Selby USNA Thesis Foot Patrol Scenario 2 Route

Conclusions:

•Performance more related to size of Ro and not gain values.
•Risk of collisions when creating a stable orbit, after which there is no collision risk.
•Number of vehicles has little effect on convoy range but requires more steering energy to control.
•Top parameter sets performed well regardless of swarm size. Gain scheduling unnecessary.
•Swarm performance affected by convoy speed but not route complexity



Scenario 3: Obstacles en Route

In the last scenario, the main objective was to create a more realistic convoy trajectory with varying speeds which represented practical military convoy characteristics. In the real world, military convoys do not always travel at a constant speed. When traveling in and urban environment, especially in a conflict zone, unforeseen events may cause the convoy to slow down or even stop progress. In these situations, the UAVs must still be able to provide accurate and reliable security in the form of sensor coverage. If only the loitering form of the control law was used, the vehicles would quickly fall behind when the convoy moves at a high speed. However, if only the rectilinear form of the control law was used, the vehicles would scatter and move in a disorganized and inefficient fashion when the convoy speed slows significantly or stops suddenly. To solve this control issue and in order to asses the ability of the control law to operate in a more realistic convoy scenario, a blending of the rectilinear and loitering forms of the control law was investigated. This blending was based on several factors including the speed of the convoy, the distance between the vehicles and the convoy, and the turn bearing rate of the convoy relative to the UAVs. The goal of this scenario was to determine the best method for transitioning between rectilinear and loitering control.

Wil Selby USNA Thesis Obstacle Scenario Route 1
Wil Selby USNA Thesis Obstacle Scenario Route 2
Speed Blending

This first factor to be analyzed for the basis of blending was the speed of the convoy. This has a very large impact on the effectiveness of the UAV swarm. This blending method assumes that the vehicles all begin in close range with the convoy.

Conclusions:
• Speed blending performs better than pure rectilinear or pure circular control.
• Swarm performance insensitive to blending function.
• Exponential routinely performed worst.
• Takes longer for the impact of high convoy speed to have an effect on the transition to rectilinear control.
• For faster convoys, blend begins and ends at lower speeds.

 

Distance Blending

Speed blending proved to be an effective technique for improving the behavior of the swarm as the vehicles followed a convoy of constantly fluctuating speed. However, the blending function had one assumption which is not always true on the battlefield. For the speed blending, the UAVs all started relatively close to the convoy.

To support a wider variety of missions, a form of distance blending was also implemented. When the UAVs were outside a certain user specified distance, pure rectilinear control was used. As the UAVs get closer to the convoy, the distance blending formula blends rectilinear control with speed blending control. Once inside a certain distance, only speed blending control is used.

 

Conclusions:
• Swarm performance insensitive to blending function.
• As the UAV’s initial conditions become farther from the convoy (greater than 2 miles), the benefits of distance blending become more pronounced.
• Distance component acts to dampen the effects of sudden convoy acceleration by incorporating a larger amount of rectilinear control, allowing the UAVs to respond faster.
• Faster convoy speed leads to larger range between blend saturation distances.

 

Bearing Rate Blending
The intent behind this form of bended control was to create a method that was effective, but also more robust and requiring less technology to implement. With an electronic warfare defensive mind frame, it is evident that having the military convoy broadcast its GPS position constantly is not operationally secure.

In an attempt to remedy the electronic attack hazard, the method of calculating the relative bearing rate of the convoy to each UAV was developed to blend the circular and rectilinear control laws. This form of blending requires the UAVs to be outfitted with some sort of visual device such as a camera or IR sensor. These are usually available on modern UAVs and do not require any additional hardware to implement this method. The convoy only needs to wear some sort of IR flasher or other visual identification mark for the UAVs to recognize. Most convoys already carry this sort of equipment to prevent blue on blue targeting, so there is no additional hardware needed on that end either. Using these devices, the UAVs are able to locate the relative position of the convoy and determine the rate at which the convoy is moving. This, in effect, combines the distance and speed variables used in previous methods into one simple calculation as shown in the figure below.

Wil Selby USNA Thesis Bearing Rate Blending Model
Conclusions:
• Outperformed pure rectilinear and pure circular control in all but one case.
• Performance sensitive to function but not saturation limits.
• Logarithmic function routinely top performer.
• Able to quickly transition to rectilinear control, handles spikes in bearing rate well.

 

Final Conclusions
• Mission planner has route selected, along with  platform and sensor package.
• Ability to “plug in” my parameters and simulate the scenario to determine how effective the swarm will be.
• Can the vehicles cover the entire course? Is their enough fuel?
• Are there areas where the range to convoy is more important?
• Speed blending – Convoy expected to travel at a slow speed and UAVs begin less than 2 miles from convoy.
• Distance Blending – Convoy expected to vary speeds widely and UAVs begin far from the convoy.
• Bearing Rate Blending – Accuracy can be sacrificed and mission requires operational security.

Leave a Reply

Your email address will not be published.