ecentralized Cooperative Control for Autonomous UAVs: Mission Assurance for Less
While the need for more complex and sophisticated unmanned aerial vehicle (UAV) missions is increasing, the number of skilled operators is decreasing. This has produced a strong push in recent years to reduce the operator workload. One promising solution is to integrate autonomous systems into military missions.
To provide this autonomy, a way must be found to manage complex real-time airspace demands (e.g., avoid collisions) and situational changes (e.g., target enters an urban canyon and cannot be easily seen). The rewards of success are considerable. Giving UAVs a level of autonomy (e.g., to generate a trajectory that will enable it to meet its mission goals) permits military personnel to focus on more important mission tasks, such as interpreting collected data rather than determining how to collect that data. These systems will not only enable a UAV to pursue its mission goals with little or no operator intervention, they will also enable two or more UAVs to cooperate to perform more sophisticated missions without operator intervention.
The autonomy of UAVs has been used in many activities, including mission planning (determining UAV schedules and trajectories) and dynamic mission replanning (making real-time plan changes in response to unanticipated, evolving mission conditions). While research has dealt with optimizing sensor placement and a priori UAV route planning for surveilling/tracking targets of interest,1 little work has been done on the dynamic, real-time replanning of these sensors and UAVs.
Cooperative control is the field of autonomy whereby multiple agents (e.g., the UAVs) work to achieve a common goal or set of goals. Cooperative control strategies enable replanning and are classified as follows:
- In centralized cooperative control, all state information sensed or derived from each individual UAV is sent to a central node for processing. This information is analyzed, decisions are made, and those decisions are sent to the individual agents to implement.
- In the hierarchical approach, the agents are typically organized as a tree, with individual agents sending sensed information, as well as that individual agent's objectives, up the tree to a higher (superior) level for a decision. At any stage an agent, in conjunction with agents higher in the tree, can make decisions for itself and for agents lower in the tree. Therefore, in this system, agents higher in the structure can make decisions that supersede decisions made by agents lower in the structure.
- In decentralized control, however, little communication exists among the agents. Each agent can make decisions based on its current situational understanding, independent of the other agents. In this approach, no single agent necessarily has a complete picture of the space. An overview of centralized versus decentralized cooperative control problems, and the subtleties involved, is also available.2
The type of control strategy used in any mission is based on the organizational structure of the agents and the "owner" of the agents; the information transfer bandwidth between the agents; and the amount of processing power onboard each agent, among other factors.
Although much research exists on centralized control, little exists on the problems posed by decentralized control. In response to this, we developed a decentralized cooperative control approach for UAVs tasked to track moving ground targets through an urban environment.3 In this approach, each UAV flies below the height of the buildings and must balance three types of constraints:
- Communicate with other UAVs (to share relative positions and sensed information on targets).
- Maintain line of sight to the target (taking into account sensor limitations and target obfuscation by buildings).
- Avoid a collision with other dynamic UAVs and buildings.
To accomplish these tasks, each UAV implements its own dynamic feedback loop, solving a highly nonlinear receding-horizon trajectory optimization problem.
The figure depicts this problem at a given snapshot in time. The pictured scenario consists of three UAVs and four targets in an urban environment. The three UAVs all have a current, planned trajectory moving forward in time (dashed curved arrows). Each UAV's estimate of the targets known to it is represented by the appropriately colored boxes about the targets. The dotted arrows coming from the colored boxes represent the extrapolated trajectory of the targets, from the UAV's perspective. Each UAV must consider the potential movements of the targets, as well as the potential movements of the other UAVs, and dynamically replan its trajectory to jointly minimize the anticipated target location error of all of the targets known to that UAV.
To efficiently solve this trajectory optimization problem, we use a relatively new approximation routine (i.e., heuristic), the Continuous Greedy Adaptive Search Procedure (C-GRASP).4 This is a multi-start local search procedure with each iteration consisting of two phases: a construction phase and a local search phase. In the construction phase, interactions between greediness (locally good) and randomization (arbitrary movement) generate a diverse set of high-quality solutions. The local search phase improves upon the solutions found in the construction phase. The best solution over all of the multi-start iterations is adopted.
A solution for a given UAV is its flight path, as well as the predicted paths of the UAV's neighbors. Note that the UAV does not communicate its solution to its neighbors because each neighbor is also solving its own problem and potentially has additional information for use. At each time-step, each UAV solves a problem for itself and its neighbors based on its own knowledge. Each UAV then implements its own solution.
The formulation and heuristic described above were exercised by varying the number of available UAVs in a scenario having six targets operating in an urban setting. These ground targets were simulated with minimum and maximum speeds of 0 and 30 miles per hour, respectively. Eight buildings, each 150 meters high, comprised the urban setting. The study involved having one to five UAVs in the scenario autonomously track the moving ground targets.
Results from the study5 indicate that the uncertainty in target location decreases as UAVs are added to the scenario. This is to be expected. What was not expected was the diminished rate of return in the target location uncertainty as the number of UAVs increases. This was especially apparent once all of the targets were discovered in the scenario. When detailed plots were analyzed, it was clear to see that our decentralized cooperative control approach exploits the availability of multiple UAVs for cooperative tracking by defining flight trajectories that result in improved track accuracy of the targets in the scenario.
Autonomous systems will play an increasing role in tasks that require split-second decision making. As our experimentation on cooperative tracking as a function of the number of UAVs in the scenario shows, this approach does indeed produce an accurate representation of targets in an urban setting. Future research will investigate heterogeneous UAV sensor capabilities and how they affect cooperative tracking performance. This research shows that distributed platforms and sensors lacking continuous net-centric communication connectivity could work together to aid in data fusion. Whether the mission is target tracking or reconnaissance and surveillance, an analytically rigorous process for managing the sensing platforms is critical to success.
The mathematical model is extensible both in the domain and to the objectives of different applications. For example, a very similar formulation could be used for unattended sensors, manned vehicles and even virtual agents working in cyberspace. This problem formulation and methodology can be applied to all modes of process refinement as an integral part of the data fusion process.
1G. Gu, P.R. Chandler, C.J. Schumacher, A. Sparks, and M. Pachter, "Optimal cooperative sensing using a team of UAVs," IEEE Transactions on Aerospace and Electronic Systems, vol. 42, no.4, 1446–1458, 2006; J. Kim and J. L. Crassidis, "UAV path planning for maximum visibility of ground targets in an urban area," in Proceedings of the 13th International Conference on Information Fusion, 2010.
2P. Chandler, M. Pachter, "Challenges in UAV Cooperative Decision and Control," T. Shima and S. Rasmussen, Eds. SIAM, 2009, 15–36.
3M.J. Hirsch, H. Ortiz-Pena, and C. Eck, "Cooperative tracking of multiple targets by a team of autonomous UAVs," International Journal of Operations Research and Information Systems, vol. 3, no.1, 2012.
4M.J. Hirsch, P.M. Pardalos, and M.G.C. Resende, "Speeding up Continuous GRASP," European Journal of Operational Research, 205(3), 507–521, 2010.
5M.J. Hirsch, H. Ortiz-Pena, and M. Sudit, "Decentralized Cooperative Urban Tracking of Multiple Ground Targets by a Team of Autonomous UAVs," Proc. of the 14th International Conference on Information Fusion, 1196–1202, Chicago, Ill. July 2011.
Dr. Michael J. Hirsch