Sponsoring Organizations
The Agent-Based Systems Engineering Project is part of the Taskable Agents Software Kit (TASK) program and is funded by the Defense Advance Research Projects Agency (DARPA) of the Department of Defense (DoD).
The TASK Kickoff meeting took place in Charleston, SC., on October 3 - 5, 2000.
Review Meetings
- Santa Fe, NM, April 17-19, 2001.
- Washington DC, January 9-11, 2002.
- Chicago, IL. June 18-21, 2002.
- Miami, FL. February, 2003.
- Austin, TX. July, 2003.
Important Websites
- http://task.alphatech.com (restricted access)
Related Projects
Description of the Project
For a complete overview of the project you can download the Technical Proposal.
Other descriptive documents, displayed during the meetings, are:
- Task PI Review Meeting, held in Washington DC, January, 2002:
- Task PI Review Meeting, held in Chicago, June, 2002:
Demos
Most of our algorithms have been implemented in Matlab, C and Java. In this web site we show only the applets that demonstrate how some of the algorithms work. In particular we demonstrate on the Target Surveillance Problem and on the Self-Locating Grounded Sensors System.
Software material on the Coordinated Multi-Agent Flow Control Problem (what we called The Opera Problem) are not available, at the moment, for online demonstrations.
The following applets require J2SE (version 1.4.1) in order to be run. They are also equipped with a brief online tutorial, which can be accessed by pressing button Help after their activation.
- Target Surveillance (static targets: June 2002)
- Self-Locating Sensors (upgraded July 2003)
- Surveillance and Tracking (mobile targets: December 2003)
- Risk-Based Surveillance and Tracking (mobile Targets: February 2003)
Summary
Visionary description
Systems engineering and artificial intelligence diverged from one another during the 1950's and 1960's, resulting in the situation today where for the most part the two disciplines are largely disjoint. Systems engineering (here meaning control, signal processing and communications) has focused primarily on physical domains that can be characterized by rich mathematical dynamics.
Artificial intelligence has focused on human perception, decision making and action. Viewed from a very high level of abstraction, both fields have had common goals but have evolved differently due to the circumstances of the problems they were trying to solve [DW91].
Generally speaking, in systems engineering, semantics are sharp, models are highly quantifiable and mathematical theory allows closed form, or at least computationally tractable, solutions. By contrast, artificial intelligence has had to deal with high degrees of semantic ambiguity, poorly quantified models and computational methods based on combinatorial search and optimization.
Future military command, control and intelligence capabilities will be revolutionized if these two disciplines are successfully cross-fertilized into a new field which we call agent-based systems engineering [Dy99]. The basic modeling paradigms of systems engineering - ideas such as state representations, state equations, observation models, state estimation and stochastic modeling - have proven to be extremely robust and general. At the same time, artificial intelligence has made significant advances in understanding the nature of human perception (natural language, vision, speech recognition), decision making, collaboration and efficient, heuristic problem-solving.
Recent innovations make this an opportune time to explore such cross-fertilization. The goals of this project are to explore the modeling, performance and scientific foundations of software agent systems using ideas from classical systems engineering and computer engineering.
Innovative Ideas and Tools
We propose to combine robust and proven concepts from traditional mathematical systems engineering with the technology of web-based agent systems, leading to new modeling paradigms and technical results for agent-based computing.
The main premise of this project is that a scientific approach to agent-based computing can be built using concepts and paradigms from classical systems and computer engineering. We claim that most existing agent functionalities can be mapped onto the corresponding operations in systems engineering. We have already made significant advances on several aspects of this research program [AP99, BG99, CB99, KG97], under the CoABS program and propose to continue them in a more concentrated way.
Hypothesis and Evaluation Plan
Our main hypothesis is that agent-based systems can be modeled by extending ideas and results from classical systems and computer engineering. These hypotheses will be evaluated analytically, through mathematical reasoning, and experimentally, through coordinated experiments and demonstrations with other ABC participants. Our group has demonstrated the ability to conduct ambitious experiments in cooperation with other research efforts. The table below summarizes some specific hypotheses and evaluation plans.
| Hypothesis 1: An agent taxonomy based on systems engineering concepts such as observation, modeling and prediction together with the new concept of brokering is a comprehensive foundation for agent-based systems engineering. | Evaluation: We will complete a detailed taxonomy of agent functionality as outlined below. It will be demonstrated that a variety of software agent systems can be decomposed and categorized using that taxonomy. |
| Hypothesis 2: This framework will allow the quant-ification of agent and agent-system performance in a scientifically rigorous manner. | Evaluation: We will demonstrate that information, modeling and planning agent performance can be characterized quantitatively by introducing metrics analogous to traditional systems engineering but appropriate for agent-based computing domains. We will continue development of agent computing performance, already initiated in the DARPA CoABS Program, and explore joint semantic-computing performance metrics and tradeoffs. |
| Hypothesis 3: The taxonomy introduced above will lead to more efficient, scalable and robust brokering so that agent discovery, reuse and interoperability will be enhanced. | Evaluation: We will develop agents in accordance with this taxonomy and disseminate the taxonomy and agent-based systems engineering paradigm to other DARPA Agent-Based Computing contractors. The effectiveness of our approach to agent-based system engineering will be measured in DAML, TASK and CoABS integration experiments. |
| Hypothesis 4: Hybrid systems can be built using both traditional systems engineering and agent-based computing components. Such systems will significantly enhance U.S. capabilities in countering asymmetric threats. | Evaluation: We will demonstrate a hybrid system using both traditional systems engineering techniques and agent-based computing. A candidate domain could involve combining satellite tracking (based on traditional signal processing and target tracking tech- niques) with human intelligence reporting. |
Expected Impact
One of the main challenges facing agent-based systems is the lack of performance guarantees. Performance has two aspects:
- Functional Performance - How does the agent-based system actually solve a problem? What metrics and guarantees are there to quantify this?
- Systems Performance - What systems resources are required by an agent-based system to solve a specific application? Systems resources include network bandwidth, memory, computing time and other measurable quantities.
Many current and future military operations involve collecting, organizing and disseminating large volumes of intelligence and sensor data generated in near real-time [RS97]. Agents capable of advanced semantic analysis, filtering, fusion, planning and coordination are extremely relevant in such an environment. We believe that the proposed research will advance the case for using agent-based systems in critical operations by demonstrating that reliable performance predictions and guarantees are possible in many cases. Those predictions and guarantees will be based on extending proven ideas from systems and computer engineering analysis [H90, RW89].
The table below illustrates the benefits of cross-fertilizing systems/computer engineering with agent-based computing.
| Ingredients/benefits from systems engineering | Ingredients/benefits from agent-based systems and AI | |
| Information agents | Formal mathematical models of observability, noise, sampling, state spaces, projection operations. | Natural language understanding and processing, vision, speech recognition, information retrieval techniques. |
| Modeling agents | Dynamic world models, statistical correlation theory, discrete event simulation, prediction techniques. | Rule-based models, knowledge representation techniques, fuzzy and other non-traditional logics. |
| Planning agents | Dynamic programming, formal performance criteria, controllability, approximation methods. | Heuristic optimization, human-in-the-loop models, imprecise and multi-valued objectives. |
| Brokering agents | Not applicable in general since they do not exist there. | Dynamic systems configuration capabilities, resource discovery, rapid deployment. |
Innovative Claims
This project's main innovative claim is the quantification of agent-based systems performance. While there have been some efforts in this direction by other researchers over the years, those results are scattered and address only isolated components of software agent operation. We will study agent performance from both functional and systems points of view, paying special attention to tradeoffs between system performance (use of resources) and functional performance (how well a problem is being solved).
The starting point for our approach is the decomposition of agent systems into three ingredients that have proven to be very successful in classical systems engineering: observation, state estimation and control. These three ingredients constitute a model of a system. Classical systems have been modeled using linear state-spaces, discrete event systems, queuing systems and distributed parameter systems (partial differential equations), for example. Such models can be either deterministic or stochastic. All models are implicitly based on some notion of a Newtonian state space and dynamics. This is true for models such as partially observed Markov decision processes, stochastic control systems, reinforcement learning and neurodynamic programming for example. That is, the state of a system and its dynamics completely govern the future evolution of the system - knowing the state and the dynamics is sufficient.
In the following, we outline our innovative approaches to applying these ideas to agent-based systems.
- Agent Observations: Agents are autonomous, operating under their
own control in a changing network, computing and information space environment
[KG97]. How can we model what an agent knows about the
world state, how accurate observations of a world state are and what kinds
of systems resources an agent needs to accomplish a desired level of performance?
Most agent systems implicitly use some form of state observation to operate. For example, in the DARPA CoABS program NEO Demonstration, agents monitored the state of an evacuation zone. How accurate was that monitoring? What systems resources were neede to sustain a required level of confidence that the monitoring was adequate? We believe it is possible to model very general agent monitoring requirements by extending ideas from reliability theory and we have already demonstrated some successful results which will be reviewed below.
- State Estimation: Observations are only part of the story. Observations
have to be combined with prior estimates of the world system and the known,
or conjectured, dynamics. This is the basis for example of Kalman filtering
which has been most successful for linear state space systems. The basic idea
however is generic and can be applied in more general circumstance although
the resulting computations might be extremely difficult. One example of state
estimation in a complex domain is tracking. In radar tracking applications,
the estimated state is defined by a collection of vehicle tracks, namely multiple
spatial observations of objects correlated over time and space using known
vehicle dynamics. Tracking is accomplished by computing maximum likelihood
solutions to the probabilistic expressions that govern vehicle positions and
sensor behavior.
We believe that it is possible to extend these ideas to general agent systems. Agents make noisy observations of the world state. Those estimates can be used in an expression that describes the probability of a specific world state being true. Maximum likelihood values of the expression yield estimates of the true world state. We have successfully conducted such research already and are encouraged to explore extensions of those ideas to general agent systems.
- Control: AI researchers talk about 'plans.' Control engineers talk
about 'controls.' 'Closed-loop' control to an engineer is the same as 'reactive'
planning to an AI practitioner. As already suggested in the Executive Summary
of this proposal, many of the goals of AI and systems engineering are the
same but the circumstances are quite different [H95, H90,
St81a, St81b, YF94,
F92]. Classical control systems are
often modeled by continuous state spaces so that controls can be computed
using relatively efficient dynamic programming or variational methods. Most
AI planning systems have to deal with very large, discrete state spaces so
that computing good plans (controls) requires solving hard combinatorial optimization
problems.
We have had success in modeling some agent planning problems as discrete control systems for which optimal solutions can be obtained, under reasonable assumptions, using efficient dynamic programming algorithms.
- Brokering Agents: Software agents operate in a dynamic, changing
environment. This is very different from classical systems theory that assumes
a constant model for the environment. This is not the difference between a
time-invariant and time-varying system. It is more fundamental. Agents systems
cannot in general assume the availability of resources for example. This would
be akin to having the observation sensors change, appear and disappear in
a classical control system. The theory for handling such situations is not
clear but we propose to tackle it in this project.
Brokering agents maintain an inventory of networked agent services and resources that other agents can locate and use on the fly. One approach would be to obtain an operational, empirical model of which agent services are available at what times given the realities of the networked computing environment. This would then result in a vastly expanded state space for the system, one in which the state of the services becomes part of the world state and therefore needs to be estimated as well.
We have had some success in addressing formal models of brokering agent systems. That work involved the relatively simple problem of two agents negotiating to see if the agree on the functional properties of the services they provide and expect respectively. Much more work is required in this direction.
- System Performance Models: Systems engineering has been very successful in generating resource usage models of computers and networks. We propose to apply that methodology to software agent-based systems as well. Preliminary work in this directions is already ongoing and has been reported in the CoABS program.
These examples illustrate the potential gains and difficulties of cross-fertilization between agent-based computing and classical systems engineering. This cross-fertilization is the main innovation of our project. We believe progress in these areas is essential to making agent-based computing acceptable in operational military applications.
Bibliography
- [A87] Ronald Arkin, Motor schema based navigation for a mobile robot. In Proceedings of the 1987 International Conference on Robotics and Automation.
- [AC99] Alberola, C. and Cybenko, G. Tracking with Text-Based Messages, IEEE Intelligent Systems, 14, July/August 1999, pp. 70-78.
- [AA97] Ashley K. and Aleven V. (1997). Reasoning symbolically about partially matched cases. International Joint Conference on Artificial Intelligence, IJCAI-1997. San Francisco: Morgan Kaufmann, 335-41.
- [AP99] Aslam J., Pelekhov K., and Rus D. "A practical clustering algorithm for static and dynamic information organization". In the 1999 Symposium on Discrete Algorithms (SODA99), Baltimore, MD (January 1999). Also invited to appear in Algorithmica, special issue on Internet algorithms.
- [B86] Rodney Brooks, A robust layered control system for a mobile robot. IEEE Journal of Robotics and Automation, 2(1):14-23, 1986.
- [BC99] Brian Brewington, George Cybenko "How fast is the web changing", to appear IEEE Computer May 2000.
- [BG99] Brian Brewington, Robert Gray, Katsuhiro Moizumi, David Kotz, George Cybenko and Daniela Rus. "Mobile agents in Distributed Information-Retrieval." In Matthias Klusch, editor, Intelligent Informant Agents, Springer-Verlag, 1999.
- [Cl93] Clancey W. J. (1993a). Notes on "Heuristic Classification." Artificial Intelligence, 59, 191-6.
- [CB98] George Cybenko and Brian Brewington, "The Foundations of Information Push and Pull", in The Mathematics of Information Retrieval, Coding and Storage, edited by D. O'Leary et al., 1998, Springer-Verlag.
- [DW91] Dean T.L. and Wellman M. (1991). Planning and Control. Los Altos, CA: Morgan and Kaufmann.
- [Dy99] Dyer D.E. (1999). Multiagent Systems and DARPA. Communications of the ACM, 42(3), 53.
- [F92] James Firby, Building symbolic primitives with continuous control routines. In Proceedings of the First International Conference on Artificial Intelligence Planning Systems, 1992.
- [Fo82] Forgy C.L. (1982). Rete: a fast algorithm for the many pattern/many object pattern match problem. Artificial Intelligence, 19, 17-37.
- [H90] Michael Heymann, Concurrency and discrete event control. Control Systems Magazine, 10(4):103-111, 1990.
- [H95] Hendler, J. Types of Planning - can artificial intelligence yield insights into prefrontal function? in Boller and Grafman (eds.) "The Frontal Lobes," Vol 769, 1995 (p. 265-276).
- [KG97] Kotz D., Gray R., Nog S., Rus D., Chawla S., and Cybenko G.. " Agent Tcl: A flexible mobile-agent system." IEEE Internet Computing, July/August 1997.
- [LO99] Lange D.B. and Oshima M. (1999). Dispatch your agents; shut off your machine. Communications of the ACM, 42(3), 88-89.
- [MC99] K. Moizumi and George Cybenko. The travelling agent problem. To appear in Mathematics of Control, Signals and Systems, 2000.
- [Pe97] Pearl, J. (1997). Probablistic Reasoning in Intelligent Systems: Networks of Pausible Inference. Los Altos, CA: Morgan-Kaufmann.
- [RS97] Daniela Rus and Devika Subramanian, Customizing Information Access,in CM Transactions on Information Systems 15(1):67-101, 1997.
- [RW89] P. J. Ramadge and W. M. Wonham, The control of discrete event systems. Proceedings of the IEEE, 77(1):81-97, 1989.
- [RW87] P. J. Ramadge and W. M. Wonham, Supervisory control of a class of discrete event processes. SIAM Journal of Control Optimization, 25(1):206-230, 1987.
- [St81a] Stefik M. (1981a). Planning with constraints. Artificial Intelligence, 16, 111-40.
- [St81b] Stefik M. (1981b). Planning and meta-planning. Artificial Intelligence, 16, 141-69.
- [WN96] Walker E.A. and Nguyen H.T. (1996). A First Course in Fuzzy Logic. Boca Raton, FL: CRC Press.
- [YF94] Yager R.R. and Filev D.P. (1994). Essentials of Fuzzy Modeling and Control. New York: Wiley.
