March 12, 2001

Effort Title: Agent-Based Systems Engineering

The following status information was submitted to the AFRL on-line Financial/Status reporting system for Contract Number F30602-00-2-0585.

Reporting Period: March 12, 2001.

Date Entered: March 21th, 2001.

Submitted by: George Cybenko, Thayer School of Engineering.

Demonstrations

Demonstration and simulation programs have been written to illustrate and simulate distributed control using local information and resource control using auctioning techniques. Some of those simulations will be presented in Santa Fe.

Progress Notes

In this reporting period, we studied the IVRS REF in detail and documented our findings in a draft report already sent to Technical Monitors at Rome Labs. The report summarizes previous work on intelligent vehicles and roadways with a focus on what different components and relationships have been proposed for a centralized, hierarchical solution.

The report categorizes the different components as agents of different types within our taxonomy and demonstrates that solutions to the IVRS problem can in principle be decomposed into information agents, modeling agents and planing agents quite naturally.

We initiated a review of decentralized algorithms that produce desired global, centralized solutions to optimization problems especially as they might occur in the REFS.

We have identified several major categories of techniques. Among them is a method based on approximations to centralized gradients by decentralized information. The idea is quite simple but appears to be relatively powerful and generally applicable to some problems in the REFS.

Consider a globally defined objective function that requires global information to compute. Each coordinate of the underlying variable space is a feature (location, velocity, etc) of an individual agent within the system. A gradient descent method for minimizing this objective function requires computation of partial derivatives of the objective function with respect to the various agent variables. This requires global information and communication.

We observe that in some problems within the IVRS REF, the global objective function has terms which involve strong local interactions and weaker interactions at a distance. Using the strong interactions, which can be communicated using only local information exchanges, an approximation to the true gradient can be computed. That approximation can be shown to have a positive projection onto the true gradient and therefore serves as a descent direction for minimizing the global objective function.

The approximation property and associated noisy computation of the gradient can be folded into a powerful analytic machinery developed by Bertzekas and Tsitsiklis during the 1990''s for stochastic optimization. The key concept is that local interactions are strong and interaction strength diminishes with distance. Distance can be a conceptual metric, not necessarily spatial distance.

Another direction that has been pursued actively is the coordination of multiple agent systems using decentralized, asynchronously communicated information. Examples of such coordination include resource control and apportioning of fixed assets. In the IVRS problem for example, this can be equal spacing of a platoon of vehicles using purely local information sharing.

This circle of ideas appears to be a completely new approach in decentralized computation using ideas from matrix iterative analysis, linear programming and graph theory in remarkable tight and powerful ways.

Those results are being documented in a report that will be presented in the April TASK meeting in Santa Fe.

June 29, 2001

Project Title: Agent-Based Systems Engineering

Investigators: George Cybenko, Daniela Rus, Valentino Crespi.

Period: June, 2001.

We describe four activities, not all at the same level of development. There is a logic to the ordering that will become evident.

Activity 1 - Evaluation and conceptual organization of existing and proposed approaches to 'Control and Adaptation in Heterogeneous Dynamic Environments.'

Rationale: There are a variety of approaches people are advocating for the CAHDE problem. We will: collect material describing the approaches; and will organize and evaluate (at an analytic, conceptual level, not in detailed simulations or implementations) the various approaches. This will help researchers in this general area develop a context for their work.

Hypothesis: The various existing approaches to addressing CAHDE-type problems can be organized within a single, logically coherent framework.

Status: We made a call for references and ideas to other members of the REF and are aggregating responses. The investigators on this project are already expert in several approaches and we will study other approaches to develop a comprehensive understanding. We will evaluate (with the above caveats) these approaches in the context of the CAHDE REF.

We have identified the nature of goal specification as being key to the properties of the resulting approach. For example, we can partition the methods into top-down and bottom-up approaches with respect to the way the system goal is specified. Gradient descent methods and certian types of cellular automata approaches fit with the top-down category. Evolutionary programming fits in the bottom up category.

The specific approaches we would like to address include:

• reinforcement learning;
• genetic programming and evolutionary programming (artificial life as well);
• cellular automata;
• statistical physics approaches(Ising models, mean field theory, statistical mechanics, etc);
• hierarchical control;
• 'classical' control and systems techniques;
• hybrid control techniques;
• game theoretic and economic models;
• machine learning methods (neural networks, case-based reasoning, etc);
• rule-based methods, formal methods;
• any 'classical' AI approaches not covered above;
• any other ideas not covered above.

Deliverables: Report and website will be in draft forms by October 2001.

Collaborations: USC, MIT, Hampshire have offered to help with this activity.

Activity 2 - Development of a complexity theory for multi-agent CAHDE.

Rationale: We believe that multi-agent CAHDE scenarios include tractable as well as intractable problems. An important advance in this area, especially as applied to the 3D-CAHDE REF challenge problem scenario, would be to develop some general theory about what kinds of properties and behaviors are feasible to compute within an agent framework.

Hypothesis: A multi-agent 'complexity theory' is possible to develop and that theory can be a powerful tool useful in understanding which kinds of emergent and collective behaviors and properties are possible.

Status: This activity is relatively early in development. Our approach is to investigate the expressive power of proposed multi-agent-based systems and show that classical physics questions can be formulated in terms of those agent systems. This would show that some collective, emergent behaviors and properties of multi-agent systems are at least as difficult as some statistical physics problems which are known to be extremely hard computationally. While proving some properties of multi-agent systems will be hard (intractable), proving others will be 'easy.' We will develop examples of easy and hard problems in the context of the 3D CAHDE scenario.

Deliverables: We propose to have initial results and examples by October 1, 2001.

Collaborations: Through informal discussion, this idea has generated interest from Santa Fe, Illinois and USC projects and we will pursue this.

Activity 3 - Development of the distributed potential function approach and application of it to the 3D setting.

Rationale: We believe that the distributed potential function approach can be applied to the 3D CAHDE scenario in a way that leads to provable performance and behaviors. This kind of result would be novel given that many approaches are ad hoc and heuristic.

Hypothesis: A 3D Opera Problem can be effectively solved using the distributed potential function approach used in 2D.

Status: We now have considerable experience with the 2D problem coined the 'Opera Problem.' The basic idea was to use a global objective function and a distributed descent function that could be computed by each agent using only local information asynchronously. The technique appears to be quite powerful both from a computational point of view and from an analysis perspective. That is, it is feasible to implement in a multi-agent system and it can be analyzed to understand performance.

Deliverables: Documentation and simulation of the 3D extensions of the technique by October 2001.

Collaborations: Hampshire, MIT.

Activity 4 - Application of Activities 2 and 3 to the Air Corridor Traffic Control (ACTC) Scenario.

Rationale: The 2D Opera Problem we now understand relatively well allows vehicle dynamics that are not feasible in 3D. We have identified a promising 3D version that involves a hybrid approach. This involves fine and coarse levels of control. Coarse control is based on a cellular partition of 3D space. Control at this level is based on idealized dynamics. At the coarse level, 3D dynamics are similar to 2D dynamics in that objects can 'stop' and maneuver without regard to 'fine' dynamic constraints. Vehicles/aircraft within a coarse cell are subject to specific dynamic constraints and use classical control techniques. Control at the coarse level is governed by a 3D Opera Problem approach, namely coarse controls to move between cells as based on the descent algorithms we used in 2D. Within a cell and maneuvers between cells are governed by specific, realistic vehicle dynamics.

Hypothesis: A hybrid control scheme based on a coarse control using potential function ideas and a fine control using classical vehicle dynamics can be an effective and efficient approach to the 3D CAHDE Scenario. Moreover, provable performance may be possible.

Status: We have concrete and specific ideas based on the above but have not yet implemented any simulations or experiments. It would be appropriate here to use a shared simulation framework, perhaps leveraging simulation technology used in other projects.

Collaborations: MIT, Hampshire, USC proposed.

April 25, 2002 - July 2, 2002

Project Title: Agent-Based Systems Engineering

Investigators: George Cybenko, Daniela Rus, Valentino Crespi.

Period: 2001 -- 2002.

1. Period: 2001 First Quarter -- January-March

   We developed a new (top-down) engineering design methodology for multi-agent systems and applied it to a specific instance relevant to the IVRS REF.

   In particular we considered the problem of coordination in distributed flow control systems. Our first case study, named 'The Opera Problem,' arose in the context of the design of intelligent vehicle roadway systems (IVRS REF). The problem statement is simple: a collection of autonomous vehicles move in a 2-dimensional plane and have limited communications capability with each other; their goal is to pass through an 'exit' while maintaining a safe minimum distance between themselves. The name 'Opera Problem' comes from people trying to exit an opera house. This problem clearly has relevance to UAV's attempting to move through a specific region.

2. Period: 2001 Second Quarter -- April-June

   The general methodology we have developed for designing multiagent systems with desired global, emergent behaviors involves specifying a global objective function and then using powerful mathematical techniques to approximate controls using only local information. This approach effectively amounts to approximating gradients in a descent direction and analysis techniques can be used to show convergence and non-oscillation.

   We developed a decentralized solution to the Opera Problem based on locally computable artificial potential functions. We implemented numerical simulations and provided analytical results.

   These results were presented at the Santa Fe TASK Technical Review meeting and we were encouraged by the DARPA PM to look into 3 dimensional problems.

3. Period: 2001 Third Quarter -- July-September

   We extended our approach and results to 3D versions of the Opera Problem in the context of the newly defined 'air corridor flow control' scenarios (CAHDE REF). We implemented a simulation environment and conducted a large-scale experimentation of our solutions over many characterizing parameters.

   This work was presented at the CAHDE REF meeting at MIT at the end of the reporting period.

4. Period: 2001 Fourth Quarter -- October-December

   We significantly advanced our investigations on the 3D Opera Problem and those results have been presented at the 2002 World Congress on Computational Intelligence (held in Honolulu, Hawaii, May 12--17, 2002) during the second quarter of 2002. See also papers.

   We then identified a new case study (in which we believe we can apply our methodology) that we name 'The UAV Surveillance Problem.' This concerns the application of agent-based technology to the design of decentralized algorithms for the navigation of airborne UAV that are tasked to surveil a set of designated targets located on ground. In this first stage we proposed two classes of solutions, the former entirely stochastic and the latter totally deterministic.

5. Period: 2002 First Quarter: January-March

   Our progress on the UAV Surveillance Problem was reported at the TASK Technical Review meeting in Washington in January 2002.

   During the rest of this quarter we started numerous collaborations. In particular we have discussed with James Crutchfield (Santa Fe Institute) the development of tools to quantify metrics of multiagent systems based on elaborating information on their observable state. We also interacted with Lee Spector (Hampshire College) on the development of a 3D environment to study multi-agent systems using Genetic Programming, and with Oliver Selfridge (MIT Media Lab) & Wallace Feurzeig (BBN) on developing an integrated platform to allow the simulation of general agent-based systems.

   During this quarter, we have progressed significantly on the UAV Surveillance Problem. In particular we have designed a new class of semi-stochastic algorithms with the goal of analysing the interrelations between the degree of randomness and various metrics of interest (like space aperiodicity of the trajectories, energy consumption and so on).

   To this purpose we have planned joint work with Luis Caffarelli and Irene Gamba (UT Austin) on applying mass transport and potential theory to the design and analysis of semistochastic and distributed solutions to the Surveillance Problem.

   Investigator Valentino Crespi has visited the UT Austin group, Lee Spector and the MIT group during this quarter to establish and advance collaborations with other TASK performers. Jim Crutchfield visited Dartmouth as part of our collaboration.

6. Period: 2002 Second Quarter: April-June

   We have conducted an extensive experimental analysis to test our distributed semi-stochastic algorithms for the Target Surveillance Problem. The final results were presented at the TASK PI Review Meeting, held in Chicago, in June, 2002.

   We also presented our final results on the 3D Opera Problem at the 2002 World Congress on Computational Intelligence (held in Honolulu, Hawaii, May 12--17, 2002) as mentioned before.

Summary

Project URL:	http://actcomm.thayer.dartmouth.edu/task/
Objective:	We develop a new top-down design methodology for agent-based control systems by combining classical control theory, typically centralized, and the emergent agent technology, inerently distributed. We show how to achieve a quantitative analysis of the performance of the designed systems on a broad range of interesting problems and applications such as control of vehicles navigation, target surveillance and target tracking. Our investigations are accompanied by C, Matlab and Java simulations of the various algorithms in play. That includes an extensive experimentation in the form of numerical estimates of the relevant metrics.
Approach:	The initial REFs of the program were focused on problems related, among the others, to the design of intelligent roadway systems with the innovative idea of employing agent-based technologies. This intention was motivated by a number of observations on the preceding approaches entirely based on classical control theory. Those designs, developed over more than a decade, were accompanied by a robust and stable mathematical analysis of their performance. Unfortunately they lacked flexibility with respect to a realistic heterogeneity of the vehicle population as well as to very complex roadway infrastructures. In order to overcome those limitations and cope with an environment highly distributed a new multi-agent strucuture was prospected. Nonetheless, this apparent panacea was not free of downsides; indeed, traditionally, designers have always been exitant about applying agent-based technologies on the grounds that what would be gained in flexibility and fault-tolerance would be lost in performance guarantees. With the aim of compensating these deficiencies came our original idea of restructuring classical control systems using a well-defined taxonomy of autonomous agents. We started from the observation that arbitrary agent-based models were generally affected by the insurgence of intractable quantities (e.g. partition functions in Ising models and mean field theory typical in statistical physics). Such hard-to-compute functions would make a quantitative analysis of the system's performance practically impossible even in theory. This lead us first to state the necessity of a discipline in the definition and deployment of agent entities and, second, to envision an engineering methodology based on defining agents as a result of a top-down process of decentralization of the resources starting from a robust, global and classically designed solution. Thus, we developed a methodological approach for designing multiagent systems with desired global, emergent behaviors, that involves specifying a global objective function and then using powerful mathematical techniques to approximate controls using only local information. For a number of case studies we considered so far this approach effectively amounts to approximating gradients in a descent direction and analysis techniques can be used to show convergence and non-oscillation.
Recent Accomplishments:	The effectiveness of our methodology has been highlighted by a series of successful investigations on problems of current scientific and applicative interest. Our first case study arose in the context of the original IVRS REF on intelligent roadway systems. Inpired by the need for coordinating the flow of a mass of vehicles approaching a ramp or a toll booth, we introduced what we called 'The Opera Problem.' Its statement is simple: a collection of autonomous vehicles move in a 2-dimensional plane and have limited communications capability with each other; their goal is to pass through an 'exit' while maintaining a safe minimum distance between themselves. The name 'Opera Problem' comes from people trying to exit an opera house. This problem clearly has relevance to UAV's attempting to move through a specific region. We developed a decentralized solution to the Opera Problem based on locally computable artificial potential functions. We implemented numerical simulations and provided analytical results. Those were presented at the Santa Fe TASK Technical Review meeting and we were encouraged by the DARPA PM to look into 3 dimensional problems. We extended our approach and results to 3D versions of the Opera Problem in the context of the newly defined 'air corridor flow control' scenarios (CAHDE REF). We implemented a simulation environment and conducted a large-scale experimentation of our solutions over many characterizing parameters. This work was presented at the CAHDE REF meeting at MIT in late August, 2001. A significant enhancement of our investigations along this direction lead to results that were finally presented at the 2002 World Congress on Computational Intelligence (held in Honolulu, Hawaii, May 12--17, 2002). We named our second case study, still in progress, 'The UAV Surveillance Problem.' This concerns the application of agent-based technology to the design of decentralized algorithms for the navigation of airborne UAV that are tasked to surveil a set of designated targets located on ground. We designed initially two classes of solutions, the former entirely stochastic and the latter totally deterministic. Our progress on the UAV Surveillance Problem was reported at the TASK Technical Review meeting in Washington in January 2002. Then we introduced a new class of semi-stochastic algorithms with the goal of analysing the interrelations between the degree of randomness and various metrics of interest (like space aperiodicity of the trajectories, energy consumption and so on). The mathematical treatment of this case involves a nontrivial and original application of advanced techniques from information theory, dynamic systems theory and percolation theory. We believe that, besides our contributions in matters of algorithms and software tools, the originality of this analysis constitutes in itself an achievement worthy of notice. Closely related to Target Surveillance and Monitoring comes our third case study on 'Target Tracking.' Here we meditate to explore target tracking systems made of sensors of different capabilities (and cost). We assume for example to despose of a set of sensors partitioned in several classes according to the quantity and quality of information they are capable to provide. The problem would be to minimize the number of sofisticated sensors at the expenses of simpler devices without compromising the coverage. Although this investigation is still at a very early stage, interesting preliminary results have boosted our confidence in imminent achievements along this path.
Current Plan:	The vision of an effective engineering design methodology for the futuristic multi-agent systems of tomorrow is becoming more and more clear as we explore new case studies and devise new analytical and software tools. Our effort is finalized to a deeper understanding of agent-based models: this includes both the determination of limitative results and the development of engineering tools, well-grounded and practicle, for the design of robust and provably performant multi-agent systems. Concretely, we expect to accomplish the investigation of a wide variety of significant problems relevant to the defense with consequent enhancement and refinement of software and analytical instruments that are being produced in our labs. Target Surveillance problems in 2D and 3D will be considered. The algorithmic solutions, being built, will be analyzed and finally demonstrated. In the specific we expect to produce sofware simulators and performance analyzers of distributed semi-stochastic algorithms obtained through our methodology. Ultimately we would provide a sound mechanism to generate engineering solutions through a quantitative trade-off analysis over sequences of ideal and classically synthesized primaries. Target Tracking problems in 2D and 3D will be analogously attacked. The technology that we expect to employ will include also modern and well-tested general purpose instruments like C, Matlab and Java 2 in concert with prototypical embedded systems of our craft.

August, 2002 - July, 2003

Project Title: Agent-Based Systems Engineering

Investigators: George Cybenko, Daniela Rus, Valentino Crespi.

Period: 2002 -- 2003.

1. Period: 2002 Third Quarter -- July - September

   We investigated problems of targets surveillance in presence of mobile targets extending our approach previously applied to battlefields with fixed targets. We considered several scenarios and planned the development of a software simulator.

2. Period: 2002 Fourth Quarter -- October - December

   We designed semi-decentralized algorithms to drive surveilling UAV's in their patrols. As the problem was to learn the positions of unknown targets we studied a performance metric based of (alpha,beta)-currency suitable to quantify the situational awarness of the battlefield.

   A preliminary version of a Java-based software simulator (see the demo section) was completed.

3. Period: 2003 First Quarter -- January - March

   We applied (alpha,beta)-currency to define a risk-based Objective to be fulfilled by our surveilling system. So, we could offer a novel formalization of the Surveillance Problem in analogy with concepts proper of Algorithmics and Complexity Theory.

   A new and more sophisticated Java-based software simulator was exhibited to describe the measurement of (alpha,beta)-currency in connection with the uncertainty of the monitoring system about the positions of the unknown targets.

   At the same time, we investigated also surveilling systems based on networks of sensors and also envisioned a possible integration of the two approaches (see [ABFCCR2003] and [CC2003]). See also next reporting period below for further notes on metrics and approches from robotics that have been applied in this framework.

   Investigator Valentino Crespi has visited the UT Austin group in relation to our joint work on UAV's Surveillance (see [CCCGR2003]).

4. Period: 2003 Second Quarter -- April - June

   A hardware demonstration based on coordinating ground sensors and moving scouts in battlefields infested by unknown moving targets has been designed. Currently this design is under implementation.

   We have demonstrated adaptation and coordination of a multi agent system in the context of the autonomous vehicle (UAV) application. The guiding application can be formulated as a robotics motion planning problem in the presence of obstacles. The ground is covered by stationary agents that can sense, communicate locally to each other and compute based on local information. Each such agent can be thought of as a node in a sensor network.

   The interesting areas of a field surveyed by the agents are targets and correspond to places where the agents' sensors have triggered. These targets can be thought of as obstacles and include anything that can be sensed, for example a moving vehicle, excessive heat (from volcanoes, fire, etc), people, etc. We assume that each agent can sense locally the presence or absence of such an event. An event configuration protocol run across all the agents in the system creates the event map. We do not envision that the network will create an accurate geometric map, distributed across all the agents. Instead, we wish for each agent to provide some information about how far from the event each node is. If the agents are uniformly distributed, the smallest number of communication hops to an agent that triggers `yes' to the event is a measure of the distance. The goal is to find a path for the UAV that moves toward the events and targets (or avoids them, depending on the application.) The UAV may ask the network regularly for where to go next. The agents within broadcasting range from the UAV supply the next best step.

   Inspired by robotics motion planning, we developed several protocols for the distributed guidance problem across such a network of agents and reported the details of these algorithms in a paper that has just been accepteed by Mobicom 2003. The map can be constructed incrementally and adaptively as an artificial potential field using hop-by-hop communication. The `obstacles' correspond to events and have repulsing values and the goal has an attracting value. The potential field is computed in the following way. Each agent whose sensor triggers `event' diffuses the information about the event to its neighbors in a message that includes its source node id, the potential value, and the number of hops from the source of the message to the current agent. This message is used to update the potential value at the current agent. The agent then broadcasts a message with its new potential value and number of hops to its neighbors.

   The potential field information stored at each agent can be used to guide a UAV that can talk to the network in an on-line fashion. The safest path to the goal can be identified with a distributed protocol using dynamic programming. In our Mobicom 2003 paper we prove that our algorithm does not get stuck in local minima. A user of the MAS can get continuous feedback from the network on how to traverse the area. The UAV asks the network for where to go next. The neighboring agents reply with their current values. The UAV chooses the best possibility from the returned values.

   The navigation guidance application is an example of how simple agents distributed over a large geographical area can assist with global tasks. This application relies on the ability of the UAV to interact with the MAS as a whole and with specific agents in the network. This interaction is directed at retrieving data from the network (such as collecting local information from individual agents and collecting global maps from the network) and injecting data into the network (such as configuring the MAS with a new task or reprogramming its agents).