Urban Convoy Escort Utilizing a Swarm of UAVs
Advisor – Roger Cortesi, Naval Research Lab
Major – System Engineering (Honors)
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.
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.
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.
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.
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.
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
Some general conclusions were drawn from this scenario:
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.
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.
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.
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.
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.