Autonomous UAV Coordination
Coordinated Intelligence, Surveillance And Reconnaissance (ISR) For A Fleet Of Unmanned Aerial Vehicles (UAVs)
Metron has developed a set of distributed algorithms for dynamic task allocation and negotiation for multi-agent systems. These algorithms show significant benefits on simulations of semi-autonomous UAV fleets coordinating ISR tasks on mobile ground targets.
With these new capabilities, UAVs can plan missions collaboratively and can re-plan adaptively based on real-time changes in UAV availability, pop-up targets and sensor capabilities. Metron has transitioned the UAV search technology to a NAVAIR Phase II SBIR contract that will lead to a new, real-time search mission planning capability.
Below, we describe the Java-based simulations we have developed for performing target search (detection) and surveillance (location monitoring). These simulations demonstrate how collective ISR goals can be satisfied through the pursuit of local UAV goals.
Target Surveillance (Monitoring)
Consider the problem of a fleet of UAVs performing surveillance on a set of mobile targets. When a UAV passes over a target, the UAV sensor updates the target position estimate. The fleet objective is to maintain tight location estimates on the set of moving targets over time, and the UAVs do this by visiting each target as frequently as possible. To achieve this goal, each UAV starts with an initial set of targets for which it maintains position estimates. The UAV solves a Traveling Salesperson-type problem to decide in which order to visit its targets.
To improve surveillance, a UAV can propose three types of target trades with another UAV: (1) an even swap (exchange a pair of targets), (2) a pull (take a target from another UAV), or (3) a push (give a target to another UAV). The criteria for swapping (whether proposing or evaluating) may be greedy or cooperative and the amount of information shared by UAVs may be high or low. If the other UAV accepts the proposal, then the UAVs make the trade; otherwise, no trade occurs.
Trading targets leads to smaller UAV tours that eventually partition the space, with each UAV responsible for one sector. These sectors are not imposed, but rather they evolve naturally from the trading behavior of the locally optimizing UAVs. As the number of UAVs or targets changes, the UAVs can use these trading strategies to adapt their sectors quickly.
Target Search (Detection)
In the target search problem, UAVs collaboratively plan search paths to detect mobile targets whose locations are uncertain. The figure below shows two UAVs and one target distribution. The cell color represents the probability of a target in that cell. The halo around each UAV is the sensor footprint, and the dots extending from each UAV show the negotiated search paths.
Each UAV optimizes its local search path (by maximizing the expected number of targets detected over a finite-planning horizon), deconflicts with the search paths of the other UAVs (to reduce duplicative coverage), and shares sensor reports with the other UAVs. We use a genetic algorithm to optimize the search paths, and use what we call delta synchronization to prioritize what information is shared between UAVs given limited bandwidth or communications range.
We use Bayesian likelihood functions and an estimated target motion model to fuse sensor information (detect or no detect) into the target prior distribution on location to produce a target posterior distribution. Likelihood functions provide a common currency for fusing information from different sensors. This Bayesian, nonlinear tracking approach easily incorporates non-Gaussian target priors, and additional details can be found in the book Bayesian Multiple Target Tracking, written by three Metron authors.
Metron has added two recent extensions to the UAV search technology. First, we developed a new path planning algorithm that uses a value potential to approximate an infinite-horizon plan. This improves the search performance, especially for disjoint, multi-mode priors (“patchy” priors).
Our second innovation, called sector negotiation, uses a UAV bidding mechanism to partition the search area dynamically and to balance the workload across UAVs. Sector negotiation eliminates the need for explicit search path deconfliction and collision avoidance because each UAV stays inside its sector. The image shows six sectors evolve over time. The cell color indicates which UAV “owns” each cell, and the cell brightness indicates the probability that the target is in that cell. Incorporating the value potential path planning and dynamic sectoring has reduced the median time to target detection by up to 40 percent in our experimental testing.