PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 1 Decentralized Cooperative Aerial Surveillance using Fixed-Wing Miniature UAVs Randal Beard, Timothy McLain, Derek Nelson, and Derek Kingston Abstract Numerous applications require aerial surveillance. Civilian applications include monitoring forest fires, oil fields and pipelines, and tracking wildlife. Applications to homeland security include border patrol and monitoring the perimeter of nuclear power plants. Military applications are numerous. The current approach to these applications is to use a single manned vehicle for surveillance. However, manned vehicles are typically large and expensive. In addition, hazardous environments and operator fatigue can potentially threaten the life of the pilot. Therefore, there is a critical need for automating aerial surveillance using unmanned air vehicles (UAVs). This paper gives an overview of a cooperative control strategy for aerial surveillance that has been successfully flight tested on small (48 inch wingspan) UAVs. Our approach to cooperative control problems can be summarized in four steps: (1) the definition of a cooperation constraint and cooperation objective; (2) the definition of a coordination variable as the minimal amount of information needed to effect cooperation; (3) the design of a centralized cooperation strategy; and (4) the use of consensus schemes to transform the centralized strategy into a decentralized algorithm. The effectiveness of the solution will be shown using both high fidelity simulation and actual flight tests. Index Terms Cooperative control, consensus, surveillance, unmanned air vehicles. I. INTRODUCTION Group cooperative behavior implies that individuals in the group share a common objective and act according to the mutual interest of the group. Effective cooperation often requires that individuals This work was supported by AFOSR grants FA9550-04-1-0209 and FA9550-04-C-0032. The authors are with Brigham Young University, Provo, Utah 84602. R. Beard (beard@ee.byu.edu) is the corresponding author. February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 2 coordinate their actions. Coordination can take many forms ranging from staying out of each others way to directly assisting another individual. In general, group cooperation is facilitated by coordinating the actions of individuals. However, each individual may not necessarily need to directly coordinate with every other individual in the group to effect group cooperative behavior. For example, fish engaged in schooling behavior only react to other fish that are in close physically proximity. We will term this type of coordination local coordination. At the other extreme is global coordination, where an individual coordinates its action with every other individual in the group. Due to communication constraints and computational feasibility, we are primarily interested in group cooperation problems where the coordination occurs locally. One of the interesting challenges in robotics is to design coordination strategies such that local coordination will result in group cooperation. While there have been numerous publications detailing specialized approaches to cooperation problems, general design methodologies are only beginning to emerge. For the most part, these methodologies assume a group of homogeneous robots with local coordination. The objective of this paper is describe a design philosophy for cooperation problems that is general enough to include both homogeneous and heterogeneous teams of robots. In addition, our approach allows a range of coordination strategies ranging from local to global coordination.We do not claim that our approach will be appropriate for all cooperation problems. In fact we expect that it will be many more years before the general principles underlying cooperative systems will be fully understood. However, we hope that our approach contributes toward that goal. The essence of our approach is explained in the following steps: Step 1. Cooperation Objective and Constraints. The first step is to analytically define the cooperation objective. Cooperation can often be identified when certain relationships between state variables are satisfied. These relationships are called the cooperation constraints. Step 2. Coordination Variable and Coordination Function. The next step is to identify the essential information that each vehicle must know to coordinate with the team. This information is called the coordination variable. It will often be the case that cooperation can be achieved through a variety of individual actions. To facilitate the selection of the individual actions that best contribute to the cooperation objective, we quantify the relationship between the coordination variable and the cooperation objective and call this function the coordination function. Step 3. Centralized Cooperation Scheme. The next step is to derive a cooperation strategy for minimizing the team objective function assuming that each member of the team has global knowledge of the coordination variable and the coordination functions of each member of the February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 3 team. Step 4. Consensus Building. In a decentralized situation where communication links are noisy and not persistent, and where the communication topology is dynamically changing and unknown to each team member, the centralized solution will fail. The final step of our approach is to implement a consensus building algorithm that assures that each member of the team has consistent coordination information despite the inadequacies of the communication network. In this paper we will focus on flying robots: in particular, fixed-wing unmanned air vehicles. This class of systems has been our primary focus and motivation in looking at cooperative control problems. There has been extensive work in cooperative control for teams of ground robots, however, since this special issue contains other papers that describe approaches targeted at ground robots, we will focus on describing the approaches that have been developed for fixed-wing UAVs. Cooperation between UAVs has it own set of unique challenges. For example, unlike ground robots, there is generally very little physical coupling except in the obvious cases of close formation flight. The most significant challenge that is unique to UAVs is three-dimensional flight with immediate implications on path planning algorithms. Another characteristic unique to fixed-wing UAVs is that forward motion is required. Therefore, stop-and-wait path deconfliction algorithms (e.g., [1]) are not applicable. In addition small fixed-wing UAVs are highly susceptible to wind. Therefore cooperation strategies must incorporate feedback at the highest levels to account for objective failure modes. However, cooperation problems for ground robots and UAVs share a number of similarities. For example, both ground and aerial robots have strict communication constraints: team members must be in close physical proximity to communicate, bandwidth is limited, and the communication topology may change unpredictably with time. Both ground and aerial robots must deal with collision avoidance constraints. Ground robots are necessarily concerned with maneuvering around each other in confined spatial environments. On the other hand, aerial robots usually have more room to maneuver but collisions are typically catastrophic. Another similarity is that decentralized cooperation strategies are generally required for both ground and aerial robots. In addition, cooperation strategies must be robust to the failure of individual team members. Studies specific to cooperative control of UAVs have recently appeared in the literature. Extensive efforts have been directed toward close formation flight. Early studies reported in [2] and [3] reported significant potential fuel savings that could be gained by close formation flight. In [4] the physical equations that describe a fixed-wing aircraft flying in the vortex of the leader are described and a control system based on the linearized model is developed. The approach is extended to nonlinear aerodynamic February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 4 coupling terms in [5]. Standard inner/outer loop designs are extended to close-formation flight in [6]. A behavioral approach to aircraft formation flight is given in [7]. In [8], differential flatness is used to generate group formation maneuvers. The effects of communication constraints on close formation flight are studied in [9]. Rigorous conditions for stable formation flight with limited communication are developed in [10], [11]. Multiple UAV cooperative timing problems have also received significant attention. One version of this problem is where multiple UAVs are required to converge on the boundary of a radar detection area to maximize the element of surprise [12], [13], [14], [15], [16]. Cooperative timing problems also arise in re-fueling scenarios, fire and hazardous material monitoring [17], moving area of regard problems, and continuous surveillance problems [18]. Cooperative timing problems are sensitive to the assignment and ordering of tasks. One approach for handling cooperative timing is to apply timing constraints to the task assignment problem. In [19], [20], [21], mixed-integer linear programming (MILP) is used to solve tightly-coupled task assignment problems with timing constraints. The advantage to this approach is that it yields the optimal solution for a given problem. The primary disadvantages are the complexity of problem formulation and the computational burden involved. Pruning strategies for simplifying the MILP problem have been proposed to enable near-real-time solutions. Although path planning for single UAVs has been an active area of research for some time (e.g., see [22], [23], [24], [25], [26]), cooperative path planning approaches for UAVs have only recently begun to appear. In [27], a decentralized optimization method based on a bargaining algorithm is developed and applied to a multiple aircraft coordination problem. A hybrid hierarchical control architecture is used for air traffic control in [28], [29]. In this paper we describe our approach to cooperative control which is based on two main ideas. The first is the notion of coordination variables and coordination functions, which were introduced in [30], [13]. In essence, the coordination variable is the minimum amount of information that needs to be exchanged between two agents to effect coordination. Although it is known by different names, the notion of a coordination variable is found in many other works on cooperative control. For example [31], [32] introduce an action reference which, if known by each vehicle, facilities formation keeping. In leader-following applications [33], [34], the states of the leader constitute the coordination variable since the action of the other vehicles in the formation are completely specified once the leader states are known. In [35], [36], [37], the notion of a virtual structure is used to derive formation control strategies. The motion of each vehicle is causally dependent on the dynamic states of the virtual structure, therefore the February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 5 states of the virtual structure are the coordination variable. In [38] a team of autonomous underwater vehicles (AUVs) are controlled to swarm around a desired mean location of the team with a specified standard deviation. The action of each vehicle is dependent on the location of its nearest neighbor, and the desired mean and standard deviation. This information is the coordination variable. Coordination variables may also be more discrete in natures. For example, in [14], [20], cooperative task allocation is addressed. Individual vehicle behavior is dependent on the task allocation vector which becomes the coordination variable. Similarly, in [39], the coordination variable is the dynamic role assignment in a robot soccer scenario. The second main idea in our approach to cooperative control is the notion of consensus seeking. Since coordination may be required between two agents that do not directly communicate, distributed consensus algorithms are required to ensure that the agents share similar coordination variables [40]. There is a growing body of literature on distributed consensus seeking. For example, consensus problems have recently been addressed in [41], [42], [43], [44], [45], [46], [47], [48], to name a few. In [42], sufficient conditions are given for consensus of the heading angles of a group of agents under undirected switching interaction topologies. In [43], average consensus problems are solved for a network of integrators using directed graphs. In [46] and [47], an algebraic graph approach is used to show necessary and/or sufficient conditions for consensus of information under time-invariant and switching interaction topologies respectively. In [44], a set-valued Lyapunov function approach is used to consider consensus problems with unidirectional time-dependent communication links. A Kalman filter approach to consensus seeking that accommodates agent confidence is described in [49]. The remainder of the paper is organized as follows. In Section II we describe different types of coupling and coordination that occurs in cooperative control problems. In Section III we give an overview of our approach to cooperative control problems and illustrate the approach with a simple academic example. A high level description of how that approach is applied to several cooperative UAV scenarios is given in Section IV. Section V gives a detailed description of the application of our approach to cooperative aerial surveillance using miniature UAVs and presents simulation and hardware results. Finally, Section VI contains conclusion and some final thoughts. II. COUPLING IN COOPERATIVE CONTROL PROBLEMS One of the primary challenges in developing generalized strategies for cooperative control is the identification of broad classes of problems that are amenable to well-defined, straightforward approaches. One way to classify cooperative control problems is by the level and type of coupling involved. For February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 6 example, using a team of robots to cooperatively maneuver the position of an object has very tight physical coupling between the robots. On the other hand, a team of UAVs tasked to cooperatively search a particular region is coupled primarily through the cooperation algorithms employed by the individual UAVs. We believe that our approach is particularly suited to algorithmically coupled problems. In this section we describe different types of coupling that occurs in cooperative control problems. Cooperative control problems can typically be formulated with a cooperation objective or cooperation constraints or both. A cooperation objective is typically optimized to increase the level of cooperation. Cooperation constraints, when satisfied, can be used to define the occurrence of cooperation. With respect to the cooperative control of multi-agent systems, the degree and form of the coupling between the agents composing the system is of paramount importance to the nature and level of the cooperation that can be achieved. Cooperation implies some degree of coupling, if only through the cooperation objective or constraints involved. Generally speaking, the greater the degree of the coupling, the more challenging it is to formulate effective cooperative solutions. A. Objective Coupling Objective coupling describes the least restrictive form of coupling in cooperative systems. Objective coupling occurs when an agent s decisions affect only its costs and outcomes and do not influence another agent s costs and outcomes directly. Each agent s decisions affects the cooperation objective and the feasibility of cooperation constraints. Objective coupling requires agents to coordinate to ensure that constraints are satisfied and that the objective is optimized. An example of objective coupling is the cooperative timing problem described in [30]. Suppose that two vehicles are to navigate independently through an obstacle field to arrive at a destination simultaneously. The cooperation constraint requires them to arrive at the same time, while the cooperation objective could be minimization of the collective power required to do so. The trajectory taken by one vehicle (its decisions) does not affect the trajectory taken by the other vehicle directly, but it does affect the other vehicle through the cooperation constraint and objective. As this example illustrates, some degree of coupling is necessary for cooperation to occur. For objective coupling the only coupling that exists comes from the formulation of the cooperative control scenario. B. Local Coupling Local coupling describes a more restrictive coupling in cooperative systems. As with objective coupling, each agent s decisions influence the cooperation objective and the feasibility of the cooperation constraints. February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 7 Under local coupling, however, an agent s decisions affect not only its own costs and outcomes, but also the decisions (and hence the costs and outcomes) of its nearest neighbors. A simple example of local or nearest neighbor coupling is shown in the cooperative search problem described in [50], where N vehicles are assigned the task of cooperatively searching an area of interest. To provide some structure to the search task, the vehicles are required to maintain a loose row formation. To avoid collisions, the vehicles are not allowed to overlap laterally. To maintain communication, the lateral spacing of the vehicles must be kept less than the communication range. These lateral spacing constraints can be viewed as cooperation constraints. The cooperation objective could be to visit as many targets as possible. The decision by one vehicle to alter its trajectory to visit a sequence of targets will directly affect the decisions of its neighbors and the costs and benefits associated with their decisions. The key difference between objective coupling and local coupling is that for objective coupling, the cost accrued for any agent is a function of that agent s decisions only. For local coupling, the cost accrued for any agent is a function of its own decisions as well as the decisions of its local neighbors. C. Full Coupling Fully coupled systems involve agents whose decisions affect the costs and outcomes for all other members of the team, and thus their decisions, i.e., what a single agent chooses to do is influenced by what all other agents on the team are doing. Coupling exists through the cooperation objective and cooperation constraint as before, but in this most restrictive form of coupling the decisions of the individual agents are coupled directly. An example of full coupling is the wide area search munition problem described in [51]. In this problem a team of autonomous munitions are tasked to search a region and identify potential targets. Once a target is identified, it must be classified by multiple passes over the target using one or more munitions. Upon identification and verification, the target is attacked removing one of the munitions from the team. The target must then be revisited for the purpose of battle damage assessment. If the minimum turning radius of the munition is large in relation to the search area, then each of these tasks will likely be performed by a different vehicle. The coupling in this scenario is complex and requires that each member of the team knows the intentions and flight paths of all the other members of the team. D. Dynamic Coupling When the vehicles are coupled through physical interactions we call it dynamic coupling. The coupling in these systems can be either local or full coupling. For example, in close-formation flight of aircraft, the aerodynamic coupling that exists is local in that it affects those aircraft in the immediate wake of February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 8 a leading aircraft. Those aircraft on the outer edges of the formation are not affected by those in the center of the formation. An example that exhibits full coupling is that of a robot team attempting to cooperatively carry a large rigid object. The forces and motions imposed by a single robot are felt by all other robots carrying the object. Dynamic coupling can also be imposed algorithmically though through the presence of virtual objects and leaders (c.f. [35]). Although the physics of dynamic coupling can be quite complex, there is one significant advantage when the actions of one agent are captured directly in the equations of motion describing other agents. These systems can be treated as one large system by combining their equations of motion. In this way, these large systems are amenable to control theoretic approaches. With one model to characterize the behavior and interaction of multiple agents, conventional single-agent approaches can be applied to achieve cooperation. III. AN APPROACH TO DISTRIBUTED COOPERATIVE CONTROL PROBLEMS In this section we give an overview of our approach to cooperative control problems and illustrate it with a simple example. The approach has been applied to problems with objective coupling [30], [49], loose coupling [50], and dynamic coupling [52]. We will illustrate the main ideas through the use a simple academic example. Example Problem Suppose that five vehicles are placed in assigned lanes as shown in Figure 1. We will assume that the lateral position of the vehicles are maintained by an on-board controller, and that the longitudinal position yi of each vehicle is governed by the dynamics y_i = ui. The vehicles start at different longitudinal positions in the lane. The cooperation goal is to maneuver the vehicles so that they proceed along a uniform front at a constant known velocity v as shown in Figure 1. A. Cooperation Constraints and Objectives. The first step in our approach is to identify and quantify the cooperation constraint and the cooperation objective. The cooperation constraint is a formal definition of the team goal and indicates exact conditions when cooperation is achieved. More precisely, if xi is the situation state of the ith vehicle and ui is the decision variable, then the cooperation constraint is a positive definite mapping Jconstraint(x1; u1; x2; u2; : : : ; xN; uN) that is identically zero when cooperation is achieved. In our example February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 9 Fig. 1. A team of vehicles are tasked to proceed along a uniform front at a constant velocity. problem, if N is the number of agents then a possible cooperation constraint is the mapping Jconstraint = 1 2 XN i=1 XN j=1 (yi yj)2; (1) which is identically zero when yi = yj . Note in the example problem, that if the team is closely, but not precisely, aligned, that the team may still be considered to be in cooperation. When Jconstraint < we say that the team has achieved -cooperation. For a given world situation state X = fx1; : : : ; xNg there may be many different decision variables U = fu1; : : : ; uNg that achieve -cooperation. In addition, there may be auxiliary objectives that we would like to minimize. For instance, in the example problem we may also want to minimize overall fuel expenditure. To capture these auxiliary objectives we introduce a positive definite function Jobjective(X; U) that quantifies these objectives. This function is called the coordination objective [30]. In our example problem, a possible coordination objective is given by the linear quadratic regulator equation [53] Jobjective = XN i=1 Z 1 t q(yi( ) ( ))2 + r(ui( ) v)2 d ; where q and r are positive constants, and where is the position of the uniform front. It is often the case that the primary goal is to effect cooperation in a team without an auxiliary cooperation objective. In that case, there is not a cooperation objective and the algorithms focus on satisfying the cooperation constraint. February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 10 B. Coordination Variables and Coordination Functions The second step in our approach is to determine the information that must be shared to achieve cooperation and to organize that into a single vector called the coordination variable. We will let denote the coordination variable. The philosophy is to distill the essentials of the cooperation problem to a set of parameters that, if known by every agent in the group, can be used to select the decision variable so that the cooperation constraint is achieved. In the example problem, if every vehicle knows the desired position of the front, then it can regulate its position to align with the front. Therefore, let be the desired position of the uniform front. In the example problem, we will assume that evolves according to the equation _ = v: Our method assumes that the cooperation constraint can be written as a function of the coordination variable. Note that for our example problem, the cooperation constraint given in Equation (1) can be bounded by a function of the coordination variable , as Jconstraint 1 2 XN i=1 XN j=1 (yi )2 + (yj )2 < : To facilitate minimization of the auxiliary cooperation objective subject to the cooperation constraint, we desire to write the cooperation objective in terms of . To this end, we assume that the cooperation objective can be expressed as a convex function of myopic objective functions for each vehicle that depend only on the situation state and decision variable of that vehicle, and the coordination variable. This myopic objective function is called the coordination function [30] and is denoted Jcf;i(xi; ui; ). In our example, we have Jobjective = XN i=1 Jcf;i: The coordination function parameterizes the effect of the coordination variable on the objectives of each agent, i.e. the coordination function describes how the myopic objective of each agent changes with changes in the coordination variable. In the example problem we have Jcf;i = Z 1 t q(yi( ) ( ))2 + r(ui( ) v)2 d : (2) Posing the cooperation problem in terms of coordination variables and coordination functions will usually reduce the dimensionality of the problem. The example problem is already a scalar problem and so the dimensionality has not been reduced. February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 11 C. Centralized Cooperation Scheme Given the terminology introduced in the previous two sections, we can pose the cooperation problem as the following optimization problem: =arg min ( lim t!1 XN i=1 Jcf;i( ; xi; ui) ) (3) subject to: lim t!1 Jconstraint( ;X; U) < A fundamental part of our approach to cooperative control is the design of a centralized strategy that solves this optimization problem. Centralized strategies are usually easier to design than decentralized strategies. (Note that the centralized algorithm will be problem dependent.) In the process of solving problem (3) the centralized algorithm produces a decision variable for the ith vehicle denoted [30] ui = fy i ( ; xi); (4) where we assume that fy i is continuous in . Equations (3) and (4) represent what we term the cooperation algorithm. For the example problem, the centralized solution requires that each vehicle knows the position of the front (t). Accordingly, the vehicles implement the control law ui = v + k( yi); where k = p q=r is chosen to minimize the coordination function given in Equation (2). Given that _ = v, it is straightforward to show that using this strategy yields yi(t) ! (t) for each i = 1; : : : ;N, which implies that lim t!1 Jconstraint ! 0; i.e., the cooperation constraint is satisfied for every . Figure 2 shows a simulation plot of the centralized solution where v = 0:1 and k = 1. D. Consensus Building The final step in our approach is to use consensus schemes to decentralize the cooperation algorithm. Multiple vehicle cooperation requires communication between vehicles. In real-world environments the communication links will be noisy and non-persistent, and the communication topology will be dynamically changing and unknown to each team member. Therefore centralized solutions are rarely feasible. The key insight is that if each agent locally instantiates the cooperation algorithm, and the inputs to February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 12 0 5 10 15 20 25 0 0.5 1 1.5 2 2.5 t (seconds) yi(t) Fig. 2. Centralized solution to the example problem. The position of the uniform front is transmitted to all vehicles from a centralized location. each local instantiation are identical, then assuming that the algorithm is deterministic, it will produce identical outputs on each vehicle. However, if the local inputs are different, than each vehicle will compute a different instantiation of the coordination variable which we label as i. Therefore, from Equation (4) we see that the decision variable for the ith vehicle is given by ui = fy i ( i; xi): Since fy i is continuous, fy i ( i) ! fy i ( ) as i ! . Therefore, the objective of the consensus algorithm is to ensure that i ! j for every i; j despite noisy communication channels and time-varying communication topologies. Our approach to consensus building is built on the intuitive notion of compromise. Each agent adjusts its instantiation of i to be a weighted average of those agents with whom it communicates[54], [49]. For continuous-time systems the consensus strategy is given by _i = Xn j=1 gij(t)Kij(t) (( j + ij) i) ; (5) where gij(t) is one if there is a communication channel from the jth vehicle to the ith vehicle at time t and zero otherwise, Kij(t) is a time-varying weighting matrix, and ij is the communication noise. For February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 13 discrete-time systems, the consensus strategy is given by i[n + 1] = i[n] + Xn j=1 gij [n]Kij [n] (( j [n] + ij [n + 1]) i[n]) ; (6) where n is the sample index, and Pn j=1 gij [n]Kij [n] = 1 for each n. In [49] we have shown the following result. Theorem 3.1: Assume that the communication noise is zero. If there exist infinitely many consecutive uniformly bounded time intervals such that the union of the communication graph across each interval has a spanning tree, then Equation (5) guarantees that i(t) ! j(t) and Equation (6) guarantees that i[n] ! j [n] asymptotically. The conditions for consensus in Theorem 3.1 are surprisingly mild. In essence the theorem states that if the agents communicate with other agents sufficiently often, that all vehicles will come into agreement. Theorem 3.1 guarantees consensus in the absence of communication noise. If communication noise is present in the system then we need to show that -consensus is achieved, i.e., lim t!1 X ij k i(t) j(t)k < : To that end we stack the local instantiation of the coordination variables as = ( T 1 ; : : : ; T N )T and the noise vector as = ( T 11; : : : ; T NN)T and write Equation (5) as _ = A(t) + B(t) : (7) In [49] we have shown that Equation (7) is input-to-state stable which implies that the consensus error is uniformly bounded by a gain times the power in the communication noise. A fundamental result in nonlinear control theory is that the cascade of two input-to-state stable systems is also input-to-state stable [55]. Consider the control diagram shown in Figure 3. The consensus algorithm on each vehicle is input-to-state stable from the communication noise to the consensus error. Therefore, if the cooperation algorithm is input-to-state stable from the consensus error to the cooperation constraint, then the cascade system is input-to-state stable from the communication noise to the cooperation constraint: implying that -cooperation is achieved for low-enough levels of communication noise. The application of the consensus strategy given in Equation (5) to the example problem implies that each vehicle updates its coordination variable according to _i = v + X j6=i gij(t)( j i): February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 14 Fig. 3. Cascade system where the output of the consensus building mechanism drives the coordination algorithm which uses feedback from the agent to achieve coordination. Each vehicle then implements the modified control law ui = fy i ( i; yi) 4= v + k( i yi); where k can be chosen to minimize the modified coordination function Jcf;i = Z 1 t q(yi( ) i( ))2 + r(ui( ) v)2 d : (8) Since the system d dt (yi i) = k(yi i) + k ij is input-to-state stable, we are guaranteed to achieve -cooperation. Note that since each vehicle tracks its own notion of the front in an optimal manner (with respect to Equation (8)), this does not imply that the overall team has optimal performance. In fact, centralized solutions that minimize the coordination function will always have better performance than decentralized solutions. Figure 4 shows a simulation plot of the decentralized solution where v = 0:1 and k = 1 and the standard deviation of the noise on the communication channels is = 0:1. The first subplot shows the evolution of the coordination variables. The second subplot shows the evolution of the longitudinal position of the vehicles, and the third subplot shows the number of unidirectional communication links that are active in the network as a function of time. Note that updates of i only occur when the ith vehicle is communicating with another vehicle. Despite the low levels of communication, the coordination constraint is still satisfied. February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 15 0 10 20 30 40 50 60 70 80 90 100 0 5 10 15 20 t xii(t) 0 10 20 30 40 50 60 70 80 90 100 0 5 10 15 20 t yi(t) 0 10 20 30 40 50 60 70 80 90 100 0 1 2 3 t # of comm links Fig. 4. Decentralized solution to Example 1. A consensus algorithm is used to negotiate a common position of the uniform front despite low levels of communication between vehicles. IV. APPLICATIONS OF THE METHODOLOGY We have applied the approach of Section III to a variety of problems. To demonstrate the applicability of the approach we provide a brief sketch of some of these applications. A. Spacecraft Formation Flying Numerous space-based observation applications have been proposed that utilize spacecraft flying in formation to cooperatively sense objects of interest [35], [56], [57], [58], [59]. In this illustrative example, we consider a formation of spacecraft that synthesize a space-based interferometer to image celestial objects. To image objects, the spacecraft must maintain a tight formation and the formation must be able to point at the objects to be imaged. Under the assumption that the formation becomes disabled when any one of the spacecraft exhausts its fuel supply, it is important to equalize the fuel levels of the spacecraft in the formation as the formation reorients to point at various objects. By so doing, the useful life of the formation is maximized. For a formation undergoing pointing rotations, the rate of fuel consumption for each spacecraft will be influenced by their distance from the center of rotation. This scenario is depicted in Figure 5 and described in detail in [60], [61]. This problem can be formulated as a cooperative control problem where the cooperation constraint, Jconstraint, is to maintain the formation and the cooperation objective, Jobjective, is to equalize fuel levels February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 16 center of rotation desired pointing direction Fig. 5. Spacecraft formation rotation maneuver. across the formation. Utilizing the mathematical framework described in Section III, the coordination variable, , is the center of rotation for the formation. The situation state xi is the formation shape, the fuel levels for each spacecraft, the pointing directions, and the rotation rate. The decision variable ui is the trajectory they fly during transition between pointing directions. The coordination variable (center of rotation) is functionally dependent on the decision variable (trajectory arc flown by the spacecraft). The coordination function, Jcf;i expresses the fuel expenditure rate as a function of the rotation center location. With coordination function information from each spacecraft, a rotation center for the formation can be selected that will equalize the fuel at the completion of the formation maneuver thereby minimizing the cooperation objective. As each spacecraft flies circular arcs about the same center of rotation with the same angular rate, the formation will be maintained and the cooperation constraint will be satisfied. Consensus strategies can be used to ensure a robust decentralized implementation of the algorithm. B. Cooperative Timing Cooperative timing tasks for UAVs are of interest in many military missions. A simple example of this is shown in Figure 6 where several UAVs are spatially distributed over a wide area. The goal is for the UAVs to arrive at their target simultaneously (or perhaps with a specified time spacing), while avoiding threats and terrain-based obstacles [30]. We assert that cooperation is achieved if the simultaneous arrival constraint is satisfied and that the quality of the cooperation is measured by the degree to which threats and obstacles are avoided. This problem can be placed in the cooperative control framework of Section III by defining the arrival February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 17 target threats obstacle Fig. 6. Cooperative timing scenario where multiple vehicles must maneuver through a threat and obstacle field to rendezvous at a target simultaneously. time as the coordination variable, . As expected the arrival time for each vehicle is a function of the situation state xi and the decision variable ui. In this case the situation state describes the location of threats and terrain obstacles as well as the location of the target. The decision variable is the trajectory that is flown, which can be represented by a set of waypoints and a flight velocity. The coordination function Jcf;i for each vehicle describes the threat and obstacle exposure it faces versus the arrival times that it can achieve [30]. The cooperation constraint Jconstraint requires that all vehicles arrive at the target simultaneously, which is implicitly achieved through the selection of a team-optimal coordination variable . The coordination variable is chosen to minimize the cooperation objective Jobjective, which is the maximum threat cost faced by any team member. C. Cooperative Search Another example of cooperative control that is amenable to our formulation is that of cooperative search. In this problem a team of UAVs are to fly in a loose echelon formation with forward-looking sensors scanning for observation targets and hazards [50]. The UAVs are required to stay close enough to their neighbors to maintain communications, but must also stay far enough apart to avoid colliding with one another. Individually, the UAVs have the objective of observing as many targets as possible while avoiding the hazards as they fly over the region of interest. In this problem the cooperation constraint Jconstraint is to maintain the loose formation by staying within communication range of neighboring UAVs, but not crossing paths with neighboring UAVs. The cooperation objective Jobjective is to maximize the number of targets observed by the team as it traverses February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 18 observation targets hazards Fig. 7. Cooperative search scenario where multiple vehicles must maneuver around threats and pass over observation targets while maintaining communication connectivity and avoiding collisions. the region of interest. The situation state xi is comprised of the observation target locations, the hazard locations, and the formation row ordering of the UAVs. The decision variable ui is the trajectory that the ith UAV flies over the observation region. The coordination variable for each vehicle is the lateral range that it traverses as it flies its chosen trajectory. The coordination function expresses the number of targets observed as a function of the lateral range (minimum and maximum displacement laterally). Based on coordination function information, lateral ranges can be determined for each UAV that maximize the number of targets viewed and satisfy the communication and collision avoidance constraint. From the lateral range information, each UAV can choose its own trajectory to maximize the number of targets that it views. D. Cooperative Fire Surveillance The final example that we will consider is cooperative fire surveillance. As shown in Figure 8, multiple UAVs are distributed around the periphery of a growing forest fire [17]. The goal for the team is to monitor and track the periphery of the growing fire and to communicate the coordinates of the periphery to fire fighters on the ground. The UAVs have a limited communication range that requires them to work cooperatively to relay fire periphery information to the base station on the ground. In this scenario, each UAV patrols a segment of the periphery. When it encounters another UAV, it exchanges information and reverses direction until it encounters another UAV or arrives at a predetermined rendezvous point. In this problem, the situation state xi describes the fire periphery and ground station location. The February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 19 rendezvous point base station Fig. 8. Cooperative fire surveillance scenario. decision variable ui is the next rendezvous point. The cooperation constraint Jconstraint is to equalize the path lengths flown by the UAVs around the periphery of the fire. The cooperation objective Jobjective is to minimize the latency between the time that periphery information is sensed and the time that it is received at the ground station. The coordination variable is the length of the path last flown, which is a function of the situation state and the decision variable. The coordination function Jcf;i models the contribution to communication latency as a function of segment length. In this particular problem, the cooperation constraint and the cooperation objective are coupled. As shown in [17], if the cooperation constraint is satisfied (by equalizing the path lengths), then the cooperation objective will be minimized (communication latency will be minimal). Because of this coupling, it is not necessary to explicitly share coordination functions among vehicles. V. DECENTRALIZED COOPERATIVE SURVEILLANCE The objective of this section is to illustrate the design methodology introduced in Section III through a detailed example, and to demonstrate the effectiveness of the approach using high fidelity simulation and flight tests of fixed-wing miniature air vehicles. The design problem centers on cooperative aerial surveillance. We will consider two related variants of this problem. The first variant is persistent imaging, depicted in Figure 9, where a team of N UAVs equipped with imaging senors is tasked to persistently image a known target. If the field-of-view of the sensor is sufficiently small with respect to the turning radius of the UAVs, the solution of this problem will require the team of UAVs to fly over the target at regular intervals. The second variant of the cooperative aerial surveillance problem is cooperative February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 20 target im aging path target im aging path independent tasks and path plans cooperative fly-by Fig. 9. Persistent aerial surveillance. The UAVs are initially performing an auxiliary task. Upon command they coordinate their action to fly over the target at fixed intervals of time. identification where a team of UAVs is required to fly over a target simultaneously, but along different approach angles. In the taxonomy introduced in Section II, the decentralized aerial surveillance problems are objectively coupled. A. Solution Methodology The first step in addressing the aerial surveillance problem is to identify the cooperation constraint. Let ^z represent the location of the target which we assume is known to every vehicle, and let zi(t) denote February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 21 the location of the ith vehicle at time t. The cooperation constraint is given by Jconstraint( ) = XN i=1 kzi( + i ) ^zk2 ; (9) where is the desired spacing and i = (k 1) when the ith vehicle is assigned the kth position in the surveillance sequence. Note that if Jconstraint = 0 then the vehicles fly by the target location equally spaced intervals seconds apart. In Equation (9), is the time that the first vehicle passes over the target. It is clear that by increasing the loiter time, can be made arbitrarily large. Therefore, we need to introduce an auxiliary optimization criteria that selects between the many possibilities for . Toward that end, we assume that a suitable path planning algorithm is available for planning waypoint paths from the current location of the UAV zi to the target ^z in a certain time T. The algorithm will be denoted by the notation W = planPath(zi; ^z; T): In addition we assume a function Length(W) that returns the path length of W. The fuel expended in traversing a path is approximated by fuel = cf viLength (planPath(zi; ^z; T)) ; where vi is the airspeed along the path and cf is a constant. Therefore, fuel will be minimized by selecting the cooperation objective as Jobjective( ) = XN i=1 cf viLength (planPath(zi(t0); ^z; t0 + + i )) ; (10) where t0 is the time at which the path planner is executed. The second step is to make a suitable choice for the coordination variable. It is clear from the discussion above, that the instant in time that the first vehicle passes over the target is a suitable coordination variable. As seen in Equations (9) and (10) the cooperation constraint and the cooperation objective can be written in terms of the coordination variable. The coordination function is given by Jcf;i( ) = cf viLength (planPath(zi(t0); ^z; t0 + + i )) : The third step is to devise a centralized cooperation algorithm that solves Equation (3). The formulation of the path planning problem ensures that the cooperation constraint is trivially satisfied. The objective function can be optimized with a Mixed Integer Linear Program (MILP) solver where i are integers and is real. As it turns out, this particular problem has sufficient structure that it admits an analytic February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 22 solution [30]. Once has been determined (by a centralized unit) then, according to Equation (4) the ith vehicle implements the path given by ui = planPath(zi(t0); ^z; t0 + + i ): (11) The final step is to decentralize the algorithm using a consensus scheme. To do so, let i denote the ith vehicles instantiation of the coordination variable . Instead of Equation (11) the ith vehicle implements ui = planPath(zi(t0); ^z; t0 + i + i ): Given communication with the other vehicles, the coordination variable i is then adjusted according to the consensus dynamics given in Equation (5). In the cooperative identification variant of this problem we desire all vehicles to arrive at the target location simultaneously and at different approach angles. For this problem we set = 0 and pass the approach angle as an additional input to the path planning algorithm. In the next two sections we will present simulation results for the cooperative identification problem and flight test results for the persistent imaging problem. B. High-Fidelity Simulation Results To enable rapid prototyping of cooperative control algorithms, we have developed a high-fidelity simulation environment for autonomous miniature air vehicles. The simulation environment consists of two components. The first is a 6 DOF flight simulator with DEM terrain data and realistic wind models. The second component is an autopilot module that executes the same code that is implemented on the physical autopilot. The autopilot module connects to the same ground station software that is used to fly the miniature air vehicles. A screen shot of the flight simulator and the Virtual Cockpit are shown in Figure 10. The cooperative identification problem was simulated using four UAVs that were tasked to arrive at the target simultaneously with arrival angles differing by ninety degrees. The average time to reach consensus to within 0.02 units was 6.2 seconds where one communication packet per second was allowed to be sent by each UAV to another UAV selected randomly from the team. Simulation results are shown in Figure 11. Subplots (a) and (b) show the four UAVs loitering until the mission execution command is issued at the end of subplot (b). The UAVs are all flying at distinct, pre-assigned altitudes to avoid collision as they pass over the target. Subplots (c) and (d) show the UAVs executing the cooperative identification mission. February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 23 Fig. 10. Screen shot of the flight simulator (bottom left window in blue), and the virtual cockpit (background). The simulation environment enables rapid prototyping of cooperative control problems for autonomous miniature air vehicles. Twenty simulations of this scenario were executed with different initial conditions and different wind conditions. The maximum time elapsed between arrival of the first plane at the target and the arrival time of the last plane was 1.86 seconds, the minimum time was 0.02 seconds, and the average time was 1.09 seconds. Figure 12 plots the average distance from the target verses time for each UAV and demonstrates the effectiveness of the approach. C. Flight Test Results During the past two years, BYU has developed a reliable and robust testbed for autonomous miniature air vehicles [62], [63]. Figure 13 shows the key elements of our testbed. The first frame shows BYU s Kestrel autopilot which is equipped with a Rabbit 3000 29 MHz processor, rate gyros, accelerometers, absolute and differential pressure sensors, and GPS. The autopilot measures only 1:5 2:0 0:75 inches and weighs 18 grams. The second frame in Figure 13 show the airframes used for the flight tests reported in this paper. The airframe is a 48 inch wingspan Zagi XS EPP foam flying wing that was selected for its durability and adaptability to different mission scenarios. Embedded in the airframe are the autopilot, batteries, a 1000 mW, 900 MHz radio modem, a GPS receiver, video transmitter, and a small analog camera. The third frame in Figure 13 shows the ground station components. A laptop runs the Virtual February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 24 Fig. 11. Simulation results of a cooperative identification mission. In subplot (a) the UAV are loitering around a specified waypoint. In subplot (b) the mission execution command is issued and the UAVs plan their approach trajectories. Subplots (c) and (d) demonstrate the execution of the mission. The UAV are flying at distinct altitudes. Cockpit software that interfaces through a communication box to the UAVs. An RC transmitter is used as a stand-by fail-safe mechanism to facilitate safe operations. Flight tests were performed using three UAVs that were commanded to persistently image a target with fixed intervals of = 10 seconds. The three UAVs were initially commanded to loiter at specified GPS coordinates. The UAVs were then commanded to perform a persistent imaging mission and then return to their loiter coordinates. The UAVs were then commanded to execute the same mission a second time, after which they returned to their loiter patterns. Our current implementation does not correct for tracking errors due to wind disturbances, the inability of the vehicles to track sharp corners in the waypoint paths, or airspeed sensing inaccuracies. The weather conditions had a significant impact on the results of the February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 25 50 40 30 20 10 0 10 0 100 200 300 400 500 600 700 800 900 time (seconds) distance from target (meters) Fig. 12. A plot of the average distance from the target verses time, for the simulated cooperative identification problem. Fig. 13. Hardware platform used to obtain experimental results. The first frame shows the Kestrel autopilot designed at BYU. The second frame shows the airframes used for this study. The third frame shows the ground station components for our testbed. test. On the day of the flight test, the winds were 6 8 m/sec or approximately 30 to 50 percent of the UAV airspeed. The cooperation results of the flight tests were as follows. During the execution of the first mission the actual fly-by intervals were 1 = 25 seconds and 2 = 6 seconds. During the execution of the second mission the actual fly-by intervals were 1 = 10 seconds and 2 = 9 seconds. Plots of the telemetry data are shown in Figure 14. The imaging target is depicted by a green square. The magenta triangles indicate the fly through entry and exit points and the circles are the loiter points for the UAVs. In subplot (a) the UAV are loitering about their GPS locations. The mission command is February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 26 executed just prior to subplot (b) which shows the UAVs en route to the entry waypoint. Subplots (c), (d), and (e) show the arrival of the first, second, and third UAVs at the target. After completing the mission, the vehicles returned to their loiter position as shown by subplot (f). A plot of the distance to the target Fig. 14. Telemetry data for the flight tests of the persistent imaging mission (second pass). Figure (a) shows the UAV loitering before the mission command is executed. Figure (b) shows the UAVs en route to the entry waypoint. Figures (c), (d), and (e) show the UAVs transition through the imaging target. Figure (f) shows the UAVs returning to their loiter points. verses time for the flight tests is given in Figure 15 The cause of the large timing interval error in the first mission execution was due to the high wind speeds present during the test. Both UAV 2 and UAV 3 were headed upwind while UAV 1 was flying downwind when the mission execute commanded was issued. UAVs 2 and 3 took significantly longer to reach their first waypoint than did UAV 1 which accounts for the 25 second interval between UAV 1 and UAV 2. The 6 second interval between UAVs 2 and 3 is reasonable due to the wind conditions. February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 27 Fig. 15. A plot of the distance from the target verses time, for the second pass of the persistent imaging flight test. The second fly-by yielded better results because the cooperative fly-by algorithm was executed when all three vehicles were flying in a crosswind direction. With all of the vehicles in a similar wind condition initially, the intervals between arrival times were much closer to desired. While these results are promising, we are pursuing several enhancements that will improve the robustness and practical feasibility of the approach. The first enhancement is wind compensation in our trajectory tracker. The second enhancement is to base the trajectory generator on predicted airspeed verses ground speed. The third enhancement is to introduce feedback at the mission level by periodically executing the cooperative control algorithm during execution. VI. CONCLUSIONS In this paper we have provided an overview of a general design methodology for multiple vehicle decentralized cooperative control problems. The methodology consists of four main design steps. The first step is to quantify the meaning of cooperation as a function Jconstraint that is a positive definite function of the situation state and the decision variables. In addition, auxiliary optimization criteria may be encoded as a positive definite function Jobjective called the cooperation objective function. The second step is to isolate the information that is essential for pair-wise coordination and to call this information the coordination variable . The cooperation constraint Jconstraint and the cooperation objective Jobjective are then formulated in terms of the coordination variables. The third step is to design a centralized cooperation February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 28 algorithm that solves the optimization problem given in Equation (3) and determines a decision variable as in Equation (4). The cooperation algorithm must be designed so that the mapping from perturbations in the coordination variable to the cooperation constraint are input-to-state stable. The final step is to instantiate the cooperation algorithm on every vehicle and then implement a consensus seeking strategy that guarantees that the team will come into agreement on the coordination variable if there is sufficient communication. We have illustrated the approach with a simple example and by sketching the application of other cooperation problems that we have addressed. We also described in some detail the application to cooperative aerial surveillance using fixed-wing miniature UAVs and provided hardware results. While the approach described in this paper shows promise, there are numerous problems that remain to be addressed. For example, the control architecture shown in Figure 3 is a cascade structure between the consensus and the cooperation algorithm. If feedback from the cooperation algorithm is allowed to influence the consensus scheme, then the appropriate conditions on the consensus and cooperation algorithms remain to be determined. Another issue that has not been addressed is consensus algorithms where the coordination variable is only valid over finite sets. This problem arises in cooperation timing problems where the set of feasible paths for each UAV limits the range of possible rendezvous times. In all of the cooperation problems that we have addressed to this point, the coordination variable is assumed to be defined on an infinite field. However, there are numerous cooperation problems where the essential information is integer (e.g., vehicle A is in the team or not). Therefore the consensus strategies need to be extended to integer fields. REFERENCES [1] S. Akella and S. Hutchinson, Coordinating the motions of multiple robots with specific trajectories, in Proceedings of the IEEE International Conference on Robotics and Automation, Washington DC, May 2002, pp. 624 631. [2] W. Blake and D. Multhopp, Design, performance and modeling considerations for close formation flight, in Proceedings of the AIAA Navigation, Guidance and Control Conference, Boston, MA, August 1998, pp. 476 486, aIAA-98-4343. [3] D. F. Chichka and J. L. Speyer, Solar-powered, formation-enhanced aerial vehicle systems for sustained endurance, in Proceedings of the American Control Conference, Philadelphia, PA, June 1998. [4] A. W. Proud, M. Pachter, and J. J. D Azzo, Close formation flight control, in Proceedings of the AIAA Guidance, Navigation, and Control Conference and Exhibit. Portland, OR: American Institute of Aeronautics and Astronautics, August 1999, pp. 1231 1246, paper no. AIAA-99-4207. [5] M. Pachter, J. J. D Azzo, and A. W. Proud, Tight formation flight control, AIAA Journal of Guidance, Control and Dynamics, vol. 24, no. 2, pp. 246 254, March April 2001. February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 29 [6] C. Schumacher and S. N. Singh, Nonlinear control of multiple UAVs in close-coupled formation flight, in AIAA Guidance, Navigation, and Control Conference. Denver, CO: American Institute of Aeronautics and Astronautics, August 2000, paper no. AIAA 2000-4373. [7] M. R. Anderson and A. C. Robbins, Formation flight as a cooperative game, in Proceedings of the AIAA Guidance, Navigation and Control Conference. Boston, MA: American Institute of Aeronautics and Astronautics, August 1998, pp. 244 251, aIAA-98-4124. [8] S. T. Pledgie, Y. Hao, A. M. Ferreira, S. K. Agrawal, and R. Murphey, Groups of unmanned vehicles: Differential flatness, trajectory planning, and control, in Proceedings of the IEEE International Conference on Robotics and Automation, Washington DC, May 2002, pp. 3461 3466. [9] F. Giulietti, L. Pollini, and M. Innocenti, Autonomous formation flight, IEEE Control Systems Magazine, vol. 20, no. 6, pp. 34 44, December 2000. [10] J. A. Fax and R. M. Murray, Graph Laplacians and stabilization of vehicle formations, Engineering and Applied Science, California Institute of Technology, Pasadena, CA 91125, Tech. Rep. CDS Technical Report 01-007, July 2001, http: //www.cds.caltech.edu/ murray/cgi-bin/htdblist.cgi?papers/config.db. [11] , Graph Laplacians and stabilization of vehicle formations, in IFAC World Congress, Barcelona, Spain, 2002. [12] P. Chandler, S. Rasumussen, and M. Pachter, UAV cooperative path planning, in Proceedings of the AIAA Guidance, Navigation, and Control Conference, Denver, CO, August 2000, AIAA Paper No. AIAA-2000-4370. [13] T. W. McLain and R. W. Beard, Coordination variables, coordination functions, and cooperative timing missions, in Proceedings of the American Control Conference, Denver, CO, June 2003, pp. 296 301. [14] J. Bellingham, M. Tillerson, A. Richards, and J. P. How, Multi-task allocation and path planning for cooperating UAVs, in Cooperative Control: Models, Applications and Algorithms. Conference on Coordination, Control and Optimization, November 2001, pp. 1 19. [15] R. W. Beard, T. W. McLain, M. Goodrich, and E. P. Anderson, Coordinated target assignment and intercept for unmanned air vehicles, IEEE Transactions on Robotics and Automation, vol. 18, no. 6, pp. 911 922, December 2002. [16] T. McLain and R. Beard, Cooperative rendezvous of multiple unmanned air vehicles, in Proceedings of the AIAA Guidance, Navigation and Control Conference, Denver, CO, August 2000, paper no. AIAA-2000-4369. [17] D. W. Casbeer, D. B. Kingston, R. W. Beard, T. W. McLain, S.-M. Li, and R. Mehra, Cooperative forest fire surveillance using a team of small unmanned air vehicles, International Journal of Systems Sciences, in review, available at Technical Report available at https://dspace.byu.edu/handle/1877/55. [18] D. B. Kingston, R. W. Beard, and D. W. Casbeer, Decentralized perimeter surveillance using a team of uavs, in Proceedings of the AIAA Conference on Guidance, Navigation, and Control, in review, available at https://dspace.byu.edu/handle/1877/57]. [19] J. Bellingham, M. Tillerson, A. Richards, and J. P. How, Multi-task allocation and path planning for cooperating UAVs, in Cooperative Control: Models, Applications and Algorithms. Kluwer Academic Publishers, January 2003, ch. 2. [20] A. Richards, J. Bellingham, M. Tillerson, and J. How, Coordination and control of UAVs, in Proceedings of the AIAA Guidance, Navigation, and Control Conference, Monterey, CA, August 2002, pp. AIAA 2002 4588. [21] M. Alighanbari, Y. Kuwata, and J. How, Coordination and control of multiple UAVs with timing constraints and loitering, in Proceedings of the American Control Conference, June 2003, pp. 5311 5316. [22] E. Frazzoli, M. A. Dahleh, and E. Feron, Real-time motion planning for agile autonomous vehicles, Journal of Guidance, Control, and Dynamics, vol. 25, no. 1, pp. 116 129, January-February 2002. February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 30 [23] N. Faiz, S. K. Agrawal, and R. M. Murray, Trajectory planning of differentially flat systems with dynamics and inequalities, AIAA Journal of Guidance, Control and Dynamics, vol. 24, no. 2, pp. 219 227, March April 2001. [24] O. A. Yakimenko, Direct method for rapid prototyping of near-optimal aircraft trajectories, AIAA Journal of Guidance, Control and Dynamics, vol. 23, no. 5, pp. 865 875, September-October 2000. [25] G. Yang and V. Kapila, Optimal path planning for unmanned air vehicles with kinematic and tactical constraints, in Proceedings of the IEEE Conference on Decision and Control, Las Vegas, NV, 2002, pp. 1301 1306. [26] E. P. Anderson and R. W. Beard, An algorithmic implementation of constrained extremal control for UAVs, in Proceedings of the AIAA Guidance, Navigation and Control Conference, Monterey, CA, August 2002, aIAA Paper No. 2002-4470. [27] G. Inalhan, D. M. Stipanovic, and C. J. Tomlin, Decentralized optimization with application ot multiple aircraft coordination, in Proceedings of the IEEE Conference on Decision and Control, Las Vegas, NV, 2002, pp. 1147 1155. [28] S. Sastry, G. Meyer, C. Tomlin, J. Lygeros, D. Godbole, and G. Pappas, Hybrid control in air traffic management systems, in Proceedings of the 34th IEEE Conference on Decision and Control, New Orleans, 1995, pp. 1478 1483. [29] J. K. Howlett, Path planning for sensing multiple targets from an aircraft, Master s thesis, Mechanical Engineering, Brigham Young University, Provo, Utah 84602, 2002. [30] T. W. McLain and R. W. Beard, Coordination variables, coordination functions, and cooperative timing missions, AIAA Journal of Guidance, Control and Dynamics, vol. 28, no. 1, pp. 150 161, January 2005. [31] W. Kang and H.-H. Yeh, Coordinated attitude control of multi-satellite systems, International Journal of Robust and Nonlinear Control, vol. 12, pp. 185 205, 2002. [32] W. Kang, N. Xi, and A. Sparks, Formation control of autonomous agents in 3D workspace, in Proceedings of the IEEE International Conference on Robotics and Automation, San Francisco, CA, April 2000, pp. 1755 1760. [33] S. Sheikholeslam and C. A. Desoer, Control of interconnected nonlinear dynamical systems: The platoon problem, IEEE Transactions on Automatic Control, vol. 37, no. 6, pp. 806 810, June 1992. [34] P. K. C. Wang and F. Y. Hadaegh, Coordination and control of multiple microspacecraft moving in formation, The Journal of the Astronautical Sciences, vol. 44, no. 3, pp. 315 355, 1996. [35] R. W. Beard, J. Lawton, and F. Y. Hadaegh, A feedback architecture for formation control, IEEE Transactions on Control Systems Technology, vol. 9, no. 6, pp. 777 790, November 2001. [36] J. Lawton and R. Beard, A projection approach to spacecraft formation attitude control, in 23rd Annual AAS Guidance and Control Conference, Breckenridge, Colorado, February 2000, paper no. AAS 00-011. [37] N. E. Leonard and E. Fiorelli, Virtual leaders, artificial potentials and coordinated control of groups, in Proceedings of the IEEE Conference on Decision and Control, Orlando, Florida, December 2001, pp. 2968 2973. [38] D. J. Stilwell and B. E. Bishop, Platoons of underwater vehicles, IEEE Control Systems Magazine, vol. 20, no. 6, pp. 45 52, December 2000. [39] R. Emery, K. Sikorski, and T. Balch, Protocols for collaboration, coordination and dynamic role assignment in a robot team, in Proceedings of the IEEE International Conference on Robotics and Automation, Washington DC, May 2002, pp. 3008 3015. [40] W. Ren, R. W. Beard, and T. W. McLain, Coordination variables and consensus building in multiple vehicle systems, in Cooperative Control, ser. Lecture Notes in Control and Information Systems, V. Kumar, N. Leonard, and A. S. Morse, Eds. Block Island, RI: Springer-Verlag, 2004, vol. 309, pp. 171 188. [41] J. A. Fax and R. M. Murray, Information flow and cooperative control of vehicle formations, IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1465 1476, September 2004. February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 31 [42] A. Jadbabaie, J. Lin, and A. S. Morse, Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Transactions on Automatic Control, vol. 48, no. 6, pp. 988 1001, June 2003. [43] R. Olfati-Saber and R. M. Murray, Consensus problems in networks of agents with switching topology and time-delays, IEEE Transactions on Automatic Control, vol. 49, no. 9, pp. 1520 1533, September 2004. [44] L. Moreau, Stability of multi-agent systems with time-dependent communication links, IEEE Transactions on Automatic Control, vol. 50, no. 2, pp. 169 182, February 2005. [45] Z. Lin, M. Broucke, and B. Francis, Local control strategies for groups of mobile autonomous agents, IEEE Transactions on Automatic Control, vol. 49, no. 4, pp. 622 629, 2004. [46] W. Ren, R. W. Beard, and T. W. McLain, Coordination variables and consensus building in multiple vehicle systems, in Cooperative Control: A Post-Workshop Volume 2003 Block Island Workshop on Cooperative Control, V. Kumar, N. E. Leonard, and A. S. Morse, Eds., vol. 309. Springer-Verlag Series: Lecture Notes in Control and Information Sciences, 2004, pp. 171 188. [47] W. Ren and R. W. Beard, Consensus seeking in multi-agent systems under dynamically changing interaction topologies, IEEE Transactions on Automatic Control, (to appear). [48] L. Xiao and S. Boyd, Fast linear iterations for distributed averaging, Systems and Control Letters, vol. 53, pp. 65 78, 2004. [49] W. Ren, R. W. Beard, and D. B. Kingston, Kalman consensus strategies and their application to cooperative control, IEEE Transactions on Automatic Control, (in review), technical Report available at https://dspace.byu.edu/handle/1877/53. [50] R. W. Beard and T. W. McLain, Multiple UAV cooperative search under collision avoidance and limited range communication constraints, in Proceedings of the IEEE Conference on Decision and Control, Maui, Hawaii, December 2003, pp. 25 30. [51] C. Schumacher, P. R. Chandler, and S. J. Rasmussen, Task allocation for wide area search munitions via network flow optimization, in Proceedings of the AIAA Guidance, Navigation and Control Conference, Montreal, Canada, 2001. [52] W. Ren and R. W. Beard, A decentralized scheme for spacecraft formation flying via the virtual structure approach, in Proceedings of the American Control Conference, Denver, CO, June 2003, pp. 1746 1751. [53] F. L. Lewis, Optimal Control. New York: John Wiley and Sons, 1986. [54] W. Ren and R. W. Beard, Consensus seeking in multi-agent systems under dynamically changing interaction topologies, IEEE Transactions on Automatic Control, (to appear). [55] H. K. Khalil, Nonlinear Systems, 3rd ed. Upper Saddle River, NJ: Prentice Hall, 2002. [56] J. R. Carpenter, Decentralized control of satellite formations, International journal of Robust and Nonlinear Control, vol. 12, pp. 141 161, 2002. [57] A. Das, R. Cobb, and M. Stallard, TECHSAT 21: A revolutionary concept in distributed space based sensing, in Proceedings fo the Guidance, Navigation and Control Conference. Boston, MA: American Institute of Aeronautics and Astronautics, August 1998, pp. 1 6, paper no. AIAA-98-5255. [58] V. Kapila, A. G. Sparks, J. M. Buffington, and Q. Yan, Spacecraft formation flying: Dynamics and control, Journal of Guidance, Control, and Dynamics, vol. 23, no. 3, pp. 561 564, May-June 2000. [59] C. A. Bailey, T. W. McLain, and R. W. Beard, Fuel saving strategies for dual spacecraft interferometry missions, Journal of the Astronatical Sciences, vol. 49, no. 3, pp. 469 488, July-September 2001. [60] R. W. Beard, T. W. McLain, and F. Y. Hadaegh, Fuel optimization for constrained rotation of spacecraft formations, AIAA Journal of Guidance, Control, and Dynamics, vol. 23, no. 2, pp. 339 346, March-April 2000. February 28, 2005 DRAFT PROCEEDINGS OF THE IEEE. SUBMITTED FOR REVIEW. 32 [61] R. W. Beard and F. Y. Hadaegh, Fuel optimization for unconstrained rotation of spacecraft formations, Journal of the Astronautical Sciences, vol. 43, no. 3, pp. 259 273, July-December 1999. [62] R. Beard, D. Kingston, M. Quigley, D. Snyder, R. Christiansen, W. Johnson, T. McLain, and M. Goodrich, Autonomous vehicle technologies for small fixed wing uavs, AIAA Journal of Aerospace, Computing, Information, and Communication, 2005, (to appear). [63] R. W. Beard, D. Lee, S. Thakoor, and S. Zornetzer, A new approach to observation of descent and landing of future mars mission using bioinspired technology innovations, AIAA Journal of Aerospace Computing, Information, and Communication, 2005, (to appear). February 28, 2005 DRAFT