Cooperative control of unmanned aerial vehicles
Steven Rasmussen, Corey J. Schumacher · International Journal of Robust and Nonlinear Control · 2007
The use of unmanned aerial vehicles (UAV) for military missions has received growing attention in the last decade, with civilian usage also starting to expand. Apart from the obvious advantage of not placing human life at risk, the lack of a human pilot also enables a wealth of new operational paradigms. To realize these new paradigms, the UAVs must have a high level of autonomy and, often, work cooperatively in groups. With the development of UAV systems that have significant processing, communications, navigation, and sensing capabilities, the stage has been set to deploy cooperative control algorithms that effectively increase the capabilities of UAV teams beyond what can be accomplished by individual vehicles. Extensive research has been conducted in recent years on the development of novel cooperative decision and control algorithms to enable effective and efficient utilization of group capabilities. This special issue presents a sampling of solution approaches to problems involving cooperative control of UAVs, with an emphasis on the ‘outer-loop’ and decision-making aspects of the problem. It brings together papers that cover a broad range of cooperative control topics, such as vehicle/task assignment, sensor coverage, cooperative patrol, multi-player games, and sequential resource allocation. In this context, cooperative control is the study, development, and implementation of algorithms that either enable a group of UAVs to perform missions that cannot be accomplished individually, or else improve the team efficiency over that which can be achieved by UAVs acting as independent agents. Owing to the multidisciplinary nature of cooperative decision and control problems, the papers in this issue do not fit neatly within the standard feedback control paradigm. Some aspects of cooperative control, such as formation control and cooperative motion, which are perhaps more familiar to control engineers, are not emphasized. It is our hope that readers will nevertheless find the papers interesting and accessible. Operations involving teams of cooperative agents face numerous fundamental challenges, including computational complexity, information uncertainty, communication constraints, operator interaction or mixed initiative control, and adversary action. The papers in this special issue address a cross-section of these fundamental challenges. These challenges appear in cooperative control problems in forms such as combinatorial solution space, sensor capabilities and limitations, hardware systems capability, operator delays and operator errors, prediction of and reaction to enemy actions, and communication system limitations. In this special issue, the papers are arranged according to the four sub-topics that address task assignment, optimal distributions, multi-player differential games, and mixed initiative control. Task assignment: The first two papers of the issue address task assignment. This is the problem of allocating vehicles to perform tasks, with aspects of task scheduling and path planning commonly also involved. The task assignment problem is dominated by the fundamental difficulties of computational complexity, information uncertainty, and implementability. The first paper, ‘A Robust Approach to the UAV Task Assignment Problem’, by Alighanbari and How, explores methods to construct and deploy UAV assignment algorithms that are insensitive to uncertainties in the environment such as target values and distances traveled by the UAVs. The authors approach this problem by tightly integrating two approaches for improving the robustness of the assignment algorithm. One approach is to design task assignment plans that are robust to the uncertainty in the data, which reduces the sensitivity to errors in the situational awareness, but which can be overly conservative for long duration plans. A second approach is to re-plan as the situational awareness is updated, which results in the best plan given the current information, but can lead to a churning type of instability if the updates are performed too frequently. The strategy proposed in this paper combines robust planning with techniques developed to eliminate churning. In the second paper, entitled ‘Tree Search Algorithm for Assigning Cooperating UAVs to Multiple Tasks’, Rasmussen and Shima address the inherent coupling between path planning, task assignment, and timing. In this paper, task costs are based on flyable trajectories calculated using a Dubin's car model for the vehicle dynamics, but Euclidean distances are used to evaluate unsearched branches of the tree, providing a lower bound for the cost of unevaluated assignments, with candidate optimal solutions providing an upper bound. An iterative application of these lower and upper bounds on active subsets within the feasible set enables efficient pruning of the solution tree, resulting in fast, efficient computation of monotonically improving solutions to the combined path planning, task assignment, and scheduling problems. Optimal distributions: Problems involving distribution of vehicles or mobile sensor agents over regions or target sets are addressed in the next three papers. The first paper in this area is ‘Efficient Routing of Multiple Vehicles with no Explicit Communications,’ by Arsie and Frazzoli. This paper considers a class of dynamic vehicle routing problems, in which a number of mobile agents in the plane must visit target points generated over time by a stochastic process. Motion coordination strategies are designed to minimize the expected time between the appearance of a target point and the time it is visited by one of the agents. Control strategies are presented that require minimal or no communication between agents, but which still provide the same level of steady-state performance achieved by the best known decentralized strategies. It is demonstrated that inter-agent communication does not improve the efficiency of such systems, but merely affects the rate of convergence to the steady state. In ‘Decentralized Redistribution for Cooperative Patrol,’ Moore and Passino address the problem of enabling a group of autonomous vehicles to effectively patrol an environment much larger than their communication and sensing radii. Their formulation uses an a priori spatial decomposition of the environment into smaller areas in order to provide a framework for vehicle distribution, and a distributed cooperative control algorithm that transfers vehicles between these areas based on only local information. The method is proven to achieve the proper environment-wide distribution of vehicles within a finite time interval. The third paper in this section, ‘Cooperative Sensor Deployment for Multi-Target Monitoring’ by Tang and Ozguner, studies the deployment of multiple sensor agents (MSAs) to monitor multiple stationary targets. The problem is modeled as a special version of the general set-covering problem. A novel motion control scheme is used to address the nonlinear, non-smooth, and non-additive nature of the multiple objectives that form the cost function in this type of sensor deployment problem. A cooperative MSA deployment algorithm is developed, with a lower bound for the optimal solution of the set-covering problem. Multi-player differential games: In the paper entitled ‘Stochastic Multi-Player Pursuit–Evasion Differential Games,’ Li et al. address the problem of controlling a cooperating UAV team in the presence of a dynamic, responsive adversary using a multi-player stochastic pursuit–evasion (PE) differential game formulation. This paper addresses some fundamental issues of stochastic PE games, including multiple players, imperfect information, and computational tractability. An iterative method for deterministic multi-player PE games is extended to the stochastic case. Starting from certain suboptimal solutions with an improving property, optimization based on limited look-ahead is used, with iterative improvement resulting in convergence. Stochastic two-player PE games and games with imperfect state information are also addressed. Mixed initiative control: In ‘Optimal MAV Operations in an Uncertain Environment,’ Pachter et al. consider optimal operator decision aiding in the context of a sequential resource allocation problem. An Intelligence, Surveillance and Reconnaissance scenario is presented, in which a Micro Air Vehicle (MAV) is tasked with classification in an environment containing both real targets and false targets or ‘clutter’. The MAV visits the objects of interest in a specified sequence, sending images of the objects to a human operator, who is tasked with aiding the MAVs in classifying the objects. Objects can be revisited and re-examined, based on the potential information gain of a revisit. The problem features random operator delays with known probability density functions and finite MAV fuel reserve. A stochastic dynamic programming approach is used to determine whether to revisit each target to maximize information gain over the entire mission. The optimal decision algorithm can be computed off-line so as to facilitate real-time implementation. Although it is not possible for any single issue to cover the full range of a complex field such as UAV cooperative control, we feel that this special issue presents a good cross-section of relevant applications and methods, with papers written by many key researchers in the field. We hope that the reader will find it an interesting and useful sample of on-going work in this field. The editors would like to thank the authors for their work in researching, writing, and revising the papers. We would also like to thank the reviewers for their diligent, timely reviews, and insightful comments. Finally we would like to thank the editor, Prof. Grimble, and his staff for their patience and assistance throughout the process.