Theory and Algorithms for Cooperative Systems

The following sections are included:

• Preface

• Contents

In formation control of distributed systems, the topology of interconnections is examined in a leader-follower structure. Two fundamental interconnections are introduced. Spatial coordination assists the systems to maintain relative dynamics. When time coordination in relative dynamics is introduced, temporal coordination is defined. Majority of formations is a sequence of spatial and temporal coordinations with a high volume of communication sources. Decomposition technique systematically builds a bridge between an interconnection and a directed graph capable of handling enormous communication sources. A Lyapunov like equation is derived to shape and interpret formation dynamics using a stability-like tool called mesh stability. Examples are illustrated.

We model the problem of unmanned aerial vehicles searching for moving targets as a pursuer-evader game in which the pursuers have a speed advantage over the evaders but are incapable of determining an evader's location unless a pursuer occupies the same location as that evader. By treating the players as nondeterministic finite automata, we can model the game and use it as the input for a model checker. By specifying that there is no way to guarantee the pursuer can locate the evader, the model checker will either confirm that this is the case, or it will provide a counterexample showing one search pattern for the pursuer that will guarantee the evader must eventually be caught. As an ongoing effort to reduce the time to find pursuer-winning strategies, we also present heuristics to limit the state space of the game models.

The multidimensional assignment problem (MAP) is a combinatorial optimization problem that is known to be NP-hard, and therefore, heuristic methods are generally used to find good solutions to it. The problem has many recognized applications such as multi-agent path planning, data association, and multi-searcher problems. Simulated annealing has proven to be effective in solving many combinatorial optimization problems, but we find no references in the literature in which simulated annealing is applied to the MAP. In this chapter, we evaluate a simulated annealing algorithm for solving the MAP and report experimental results using several controlling factors in the algorithm. These factors include the cooling schedule and initial temperature, the neighborhood definition, and the method of finding a starting solution. A design of experiments approach is used to find the most effective controlling factors in the algorithm. Algorithm performance measures include time to solution and quality of solution. For a small problem, the algorithm finds the optimal solution in every case tested. For a large problem, the algorithm finds results that average 1.2 units from the optimal solution. The results show that simulated annealing is an effective method for solving the MAP.

In the Broadcast Scheduling Problem (BSP), a finite set of stations are to be scheduled in a time division multiple access (TDMA) frame. In a TDMA frame, time is divided into equal length transmission slots. Unconstrained message transmission can result in a collision of messages, rendering them useless. Therefore, the objective of the BSP is to provide a collision free broadcast schedule which minimizes the total frame length or maximizes the slot utilization within the frame. In this chapter, we introduce the BSP as a NP-complete combinatorial optimization problem and discuss several heuristics which have been applied to the problem. The heuristics are tested on over 60 networks of varying sizes and densities and the results compared.

Unmanned aerial vehicles (UAVs) are becoming increasingly useful in military, commercial, and scientific applications. Currently, UAVs can be found performing surveillance and reconnaissance missions for the military, collecting scientific data in areas that are inhospitable or inaccessible to humans, and furthering commercial and agricultural enterprises. One of the primary needs of military and civilian users is to develop an interface for a single human operator to coordinate multiple UAVs with the same ease that air traffic controllers coordinate multiple aircraft.

This chapter develops the framework for a natural language interface to a UAV. We apply our expertise in air traffic control and airport operations, combined with existing natural language processing techniques, to achieve a higher recognition success rate than traditional natural language processing endeavors in a more general domain of discourse typically do. Because there already exists a structured, yet intuitive, language for air traffic control, this chapter takes advantage of the phraseology already developed for this purpose. A corpus of air traffic control commands was gathered from recorded exchanges between pilots and controllers at Boston's Logan Airport, as well as Hanscom Field in Bedford, MA, and these were used as the “target language” for this chapter.

The implementation of a language processing system that operates according to this language is described. We believe that this is the first attempt at formalizing air traffic control phraseology for use in an unmanned system.

This chapter presents a practical method for regulating the position of a nonholonomic system (the well-studied unicycle model) to the origin in finite time. The technique is based on a (weak) bi-partite control Lyapunov function (clf), and it produces a family of piece-wise continuous stabilizing control laws. This clf-based approach guarantees regulation to the origin even when the system is subject to rectangular or polytopic actuator constraints, such as minimum forward velocity and maximum turn rates. It also offers the designer the flexibility to incorporate performance objectives other than stabilization via a point-wise control value selection. Specifically, we employ the vertex enumeration algorithm to derive a complete parameterization of a constrained stabilizing set of input commands at any particular state.

This chapter presents a cooperative system for the minimization of energy functions in a general form. The system consists of a number of agents working together in a cooperative way to achieve a certain objective. A novel cooperation scheme is presented which has two parameters to control the cooperation of agents from two different perspectives; the first is used for controlling the level of influence among agents in decision-making, the second is used for controlling the rate of information exchanges among agents. Different settings of the parameters could lead to completely different computational behaviors of the system. When the influence level is balanced with the exchange rate, the system always has a unique equilibrium and it reaches the equilibrium regardless of initial conditions. The equilibrium is also the global optimum of the system if a consensus is reached among agents in this case. When the influence level is at the strongest, the system can always reach the Nash equilibrium, a strategic equilibrium in game theory, which formally studies conflict and cooperation in a system of agents. To demonstrate its power, two case studies are provided where the number of variables of the problems ranges from 10,000 to 100,000. Using the evaluation framework for stereo matching provided by Middlebury College, we show that the solutions found by the cooperative system are significantly better than simulated annealing. Furthermore, the operations of the system are simple and inherently parallel. Our computer simulation has suggested that if the system is implemented in parallel, it can find the stereo matching solution in less than 0.5 milliseconds.

The case of two cooperative searchers is examined, and the effect of cueing on the probability of target detection is derived from first principles using a Markov chain analysis. There are two main results: first, that the effect of cueing can be quantified, and second, that there is an upper bound on the benefit of cueing. Both results are presented in closed form. The joint probability of detection for two independent searchers is derived from Koopman's formula for a single searcher, and is shown to be a special case of one of the results in this chapter. Extensions of the model are discussed.

This chapter presents recent work on the design and implementation of on-line trajectory optimization algorithms on our multi-vehicle testbed. This work extends the previous receding horizon control (RHC) for a single vehicle to handle scenarios with multiple vehicles by explicitly including collision avoidance constraints in a distributed planning system. The basic RHC trajectory design problem is encoded as a mixed-integer linear program (MILP), but this optimization is only solved for a detailed trajectory that extends part of the way towards the target waypoint. The rest of the trajectory is represented by an approximate cost-to-go function. This RHC approach enables us to exploit the power of the MILP formulation to encode the collision and obstacle avoidance constraints in a computationally tractable algorithm. However, even the solution times of the RHC scale poorly with the fleet size. To resolve this problem, we developed a technique for embedding the collision avoidance constraints in a distributed formulation of the RHC. In the new approach, vehicles plan their own trajectories using RHC while analyzing the published plans for conflicts. The reaction to a detected conflict is to solve a coupled MILP optimization that explicitly includes a cooperative maneuver. Real-time tests of this overall control system on the hardware testbed show that this approach could be scaled to much larger teams with a very small degradation in the performance.

Task execution in a multi-agent, multi-task environment often requires allocation of agents to different tasks and cooperation among agents. Agents usually have limited resources that cannot be regenerated, and are heterogeneous in capabilities and available resources. Agent coalition benefits the system because agents can complement each other by taking different functions and hence improve the performance of a task. Good task allocation decision in a dynamic and unpredictable environment must consider overall system optimization across tasks, and the sustainability of the agent society for the future tasks and usage of the resources. In this chapter we present an efficient scheme to solve the real time team/coalition formation problem. Our domain of applications is coalition formation of various Unmanned Aerial Vehicles (UAVs) for cooperative sensing and attack. In this scheme each agent bids the maximum affordable cost for each task. Based on the bidding information and the cost curves of the tasks, the agents are split into groups, one for each task, and cost division among the group members for each task is calculated. This cost sharing scheme provably guarantees the stability in cost division within each coalition in terms of the core in game theory, therefore achieves good sustainability of the agent society with balanced resource depletions across agents. Simulation results show that, under most conditions, our scheme greatly increases the total utility of the system compared with the traditional heuristics.

Bacteria, bees and birds often work together in groups to find food. A group of robots can be designed to coordinate their activities. Networked cooperative UAVs are being developed for commercial and military applications. Suppose that we refer to all such groups of entities as “social foraging swarms.” In order for such multi-agent systems to succeed it is often critical that they can both maintain cohesive behaviors and appropriately respond to environmental stimuli. In this chapter we focus on discrete-time case and use a Lyapunov approach to develop conditions under which local agent actions will lead to cohesive foraging even in the presence of sensing “noise.” The results quantify earlier claims that social foraging is in a certain sense superior to individual foraging when noise is present, and provide clear connections between local agent-agent interactions and emergent group behavior.

The work described in this chapter is directed at a theoretically foundational but potentially practical control-theoretic basis for multisensor-multitarget sensor management using a comprehensive, intuitive, system-level Bayesian paradigm. Our approach is based on the following steps: (1) use point process theory to formulate all sensors and targets as a single joint dynamically evolving stochastic system; (2) propagate the state of this system using a multisensor-multitarget Bayes filter; (3) apply suitable objective functions that express global probabilistic goals; (4) apply suitable optimization strategies that hedge against the unknowability of future observation-collections; and (5) devise principled approximations of this general (but usually intractable) formulation. This chapter employs a new objective function and optimization-hedging strategy to generalize our previous results. Our refined approach now permits: preferential observation of targets of interest (Tols); multistep look-ahead; non-ideal sensor dynamics; and modeling of communication drop-outs. It also addresses the dilemma of choosing among an infinitude of plausible objective functions, by focusing on “probabilistically natural” goals of sensor management.

Communication requirements are considered for the cooperative control of wide area search munitions where resource allocation is performed by an iterative network flow. We briefly outline both the single and iterative network flow assignment algorithms and their communication requirements. Then, using the abstracted communication framework recently incorporated into AFRL's MultiUAV simulation package, a model is constructed to investigate the peak and average data rates occurring in a sequence of vehicle-target scenarios using an iterative network flow for task allocation, implemented as a redundant, centralized optimization, that assumes perfect communication.

We present a procedure for controlling a team of Unmanned Air Vehicles (UAVs) for establishing patrol patterns to protect an asset on the ground. The control is decentralized and follows a reactive, behavior-based, emergent intelligent swarm design. The patrol patterns consist of flight tracks with different radii and altitudes around the asset. The multiple tracks help maintain a persistent presence around the asset for the purposes of surveillance and the destruction of hostile intruders. Populating inner tracks is favored over outer tracks, and is accomplished through behaviors that comprise a track switching protocol. Collision avoidance is maintained. Global communication is assumed to be unavailable, and control is established only through passive sensors and minimal shortrange radio communication. The model is implemented and successfully demonstrated in an agent-based, simulated urban environment. The simulation establishes that the emergent, behavior-based patrol procedure for UAVs is effective, robust, and scalable. The approach is especially well suited for numerous, small, inexpensive, and expendable UAVs.

Associated with use of the K-means Algorithm for data partitioning is the problem of initializing the number of clusters and their centers. In this paper, we propose to integrate as a variable the number of clusters in the optimization problem. By using entropy minimization via Bayesian inference, the number of optimum clusters can easily be found. Depending on the clustering requirements of the data, the entropy constant in our algorithm can be varied in order to obtain different number of clusters.

In this work, the problem of scheduling messages in a controller area network (CAN) is presented. CAN is an important type of hard realtime distributed system, which is used to control embedded devices, connected to a main processor through a serial communication infrastructure. The main problem in CAN concerns the optimal allocation of messages in the bus field connecting processor nodes. We propose linear integer programming formulations for this problem. Our objective is to find a message schedule minimizing the time for dispatching of messages with high priority. We show that the problem is NP-hard, and present results of the mathematical programming models for a set of instances defined over subsets of the SAE Benchmark for Automotive Systems.

Multiple cooperating Electronic Combat Air Vehicles (ECAV) are used to generate phantom radar tracks in a multiple radar air defense network. The vehicles use a range delay deception transponder, which delays the radar pulses received by the ECAV and sends them back to the radar. This results in the radar calculating an erroneous target range. A radar network will correlate tracks to identify phantom targets. The ECAV team, however, precisely positions and dynamically coordinates the motion of the vehicles so that all radars see the same phantom track. This chapter presents the two-dimensional mathematical relationships between the motion of the vehicle and the motion of the phantom track. Phantom tracks investigated include: a) constant heading and constant velocity; b) circular trajectory with constant velocity; and c) arbitrary trajectory and arbitrary velocity. Closed form solutions are obtained for the ECAV trajectory given a specified phantom track. Parametric analyses are performed with constraints on the vehicle dynamics, constraints on the transponder, vehicle initial position and state, and phantom track state. Results are presented for a single vehicle and a single radar, and for up to four vehicles generating a single coherent phantom track for up to four radars correlating returns. The vehicles must tightly coordinate their highly coupled actions to generate an effective phantom track using range delay deception. Also addressed is the generation of multiple phantom tracks through exploitation of sidelobes in a radar's antenna pattern.

The problems of reasoning and uncertainty have been studied since the invention of probability three hundred and fifty years ago. This research presents a method for cooperative possibility reasoning with uncertainty developed for logical proposition inferences. The approach explicitly includes “uncertain” as a logic state along with “true” and “false”. This leads to a model for possibility variables that can be solved as a linear program. The logical inference from the proposition states can be computed in terms of the possibility variables using the methods from fuzzy set and logic. The Prisoner's Dilemma and Epiminides paradox are used to illustrate the unique features available through the use of possibility reasoning with uncertainty. In addition this research illustrates how variables can be linked with both “AND” and “OR” conjunctions. The Prisoner's Dilemma shows how the two prisoners can cooperate in decision making. This model allows the prisoners to make decisions based on the possible trust for each other. Robert Axelrod made the Prisoner's Dilemma cooperative reasoning problem popular in 1986 and has explored the complexity of cooperation for many years. In contrast the 2000-year-old Epiminides Paradox is solved to illustrate the novel features of possibility reasoning with uncertainty for dealing with contradictory statements.

The central problem in multiple target tracking is the data association problem of partitioning sensor reports into tracks and false alarms. This problem occurs at all levels of tracking involving a single sensor, multiple sensors on a single platform, and multiple sensors on multiple platforms and multiple networks. Multiple frame data association, whether it is based on multiple hypothesis tracking (MHT) or multiple frame assignments (MFA), has established itself as the method of choice for difficult tracking problems, principally due to the ability to hold difficult data association decisions in abeyance until additional information is available. Over the last twenty years, these methods have focused on one-to-one assignments and occasionally on many-to-one or many-to-many assignments. Recent re-emphasis on closely spaced objects and track-to-track multiple hypothesis correlation over time have clearly demonstrated the need for a new class of data association problems and algorithms. The goal then for this work is the formulation of some of these group assignment problems, which represent a generalized data association problem in the sense that it reduces to the classical assignment problems when there are no overlapping groups.

Coordinating hundreds or thousands of Unmanned Aerial Vehicles (UAVs), presents a variety of new exciting challenges, over and above the challenges of building single UAVs and small teams of UAVs. We are specifically interested in coordinating large groups of Wide Area Search Munitions (WASMs), which are part UAV and part munition. We are developing a “flat”, distributed organization to provide the robustness and flexibility required by a group where team members will frequently leave. Building on established teamwork theory and infrastructure we are able to build large teams that can achieve complex goals using completely distributed intelligence. However, as the size of the team is increased, new issues arise that require novel algorithms. Specifically, key algorithms that work well for relatively small teams, fail to scale up to very large teams. We have developed novel algorithms meeting the requirements of large teams for the tasks of instantiating plans, sharing information and allocating roles. We have implemented these algorithms in reusable software proxies using the novel design abstraction of a coordination agent that encapsulates a piece of coordination protocol. We illustrate the effectiveness of the approach with 200 WASMs coordinating to find and destroy ground based targets in support of a manned aircraft.

Several research simulations have been created to support development and refinement of teamed autonomous agents using decentralized cooperative control algorithms. Simulation is the necessary tool to evaluate the performance of decentralized cooperative control algorithms, however these simulations lack a method to validate their output. This work presents a method to validate the performance of a decentralized cooperative control simulation environment for an autonomous Wide Area Search Munition (WASM). Rigorous analytical methods for six wide area search and engagement scenarios involving Uniform, Normal, and Poisson distributions of N real targets and M false target objects are formulated to generate expected numbers of target attacks and kills for a searching WASM. The mean value based on the number of target attack and kills from Monte Carlo simulations representative of the individual scenarios are compared to the analytically derived expected values. Emphasis is placed on Wide Area Search Munitions operating in a multiple target environment where a percentage of the total targets are either false targets or may be misconstrued as false by varying the capability of the WASM's Automatic Target Recognition (ATR) capability.

Close formation control of multi-UAVs is addressed in this chapter. Nonlinear dynamic model reflecting the aerodynamic coupling effects introduced by close formation flight (such as vortex of the adjacent lead aircraft) is considered. Adaptive control algorithms for asymptotic lateral, longitudinal, and vertical separation tracking are developed. Simulation on three F16 class aircrafts performing Δ-shaped formation was conducted. Both theoretical studies and simulation results demonstrate the effectiveness of the proposed control method.

This chapter develops a control methodology which allows a group of Unmanned Aerial Vehicles (UAVs) to follow a ground vehicle, or, more generally, a moving or stationary point, while maintaining a desired formation pattern. This capability could be used in a number of applications, including surveillance missions such as convoy protection or search and rescue operations.

Assuming that the point of interest is moving at a speed less than the maximum flight speed of the aircraft, the point is used to define the location and orientation of a moving orbital trajectory. This trajectory is designed to satisfy aircraft speed and turn rate constraints, and is developed such that an aircraft which tracks the trajectory will cross over the point periodically, with a specified time interval. As the ratio of point speed to aircraft speed varies from zero to one, the path traced by the aircraft changes smoothly from a figure-eight to a periodic curve to a straight line. A tracking law is developed which steers the aircraft along the trajectory using heading and airspeed commands.

In order to apply this approach to a formation of UAVs, we use a formation controller which is based on the use of generalized coordinates. These coordinates characterize the location (L), orientation (O), and shape (S) of the formation. This provides a natural and convenient way of specifying configuration and makes it possible to control a group of aircraft as a single entity. This controller is used as an intermediate layer between the orbit tracking control and the individual aircraft. It accepts orbit tracking commands as group motion commands, and produces heading and airspeed commands for the individual aircraft in the formation. These individual commands are designed to move the group along a desired LO trajectory while maintaining desired relative positioning of the aircraft.

The methodology is illustrated through several hardware-in-the-loop simulations, in which two aircraft follow a truck moving at different speeds and headings. In addition, experimental results from a two-aircraft flight test are presented.

In this chapter a method for assigning unmanned aerial vehicle agents to targets through the use of preplanned vehicle tours is presented. Assignments are based on multi-target tours that consider the spread of the targets and the sensor capabilities of the vehicles. In this way, the individual agents and the team as a whole make better use of team resources and improve team cooperation. Planning and assignments are accomplished in reasonable computational time through the use of heuristics to reduce the problem size.

We present a new method for solving multi-player coordination problems using decentralized optimization. The algorithm utilizes the Nash Bargaining solution as the preferable outcome for all players among the set of Pareto optimal points, under assumptions of convexity. We demonstrate the concept on a multi-agent kinematic trajectory planning problem with collision avoidance. An analysis and numeric comparison of complexity is performed between centralized and decentralized penalty method based optimization. The analysis and the simulations suggest operation regimes where the decentralized method incurs no increase in complexity and even improvement in computation time proportional to the number of players over the centralized method. Experimental results from the MIT rover testbed are presented as well, showing very good correlation between the planned and executed trajectories.