The title of each paper is a hot link to a pdf file of the complete paper. The date in parenthesis after each paper is when it was last updated. A chronological list is available here.
Topic Areas:
Hybrid Multi-Agent Systems: Integrating Swarming and BDI Agents (with Nielsen, Brueckner, and Alonso) (5/06
Proceedings of ESOA06
The individual agents that interact in a multi-agent system typically exist along a continuum ranging from heavyweight cognitive agents (often of the BDI type) to lightweight agents with limited individual processing (digital ants). Most systems use agents from a single position along this spectrum. We have successfully implemented several systems in which agents of very different degrees of internal sophistication interact with one another. Based on this experience, we identify several different ways in which agents of different kinds can be integrated in a single system, and offer observations and lessons from our experiences.
Multiagent Systems, State-of-the-Art and Research Challenges (with Weyns, Michel, Holvoet, and Ferber) (1/05).
Proceedings of Workshop on Environments for Multi-Agent Systems (E4MAS 2004), Springer, 2004.
It is generally accepted that the environment is an essential compound of multiagent systems (MASs). Yet the environment is typically assigned limited responsibilities, or even neglected entirely, overlooking a rich potential for the paradigm of MASs. Opportunities that environments offer, have mostly been researched in the domain of situated MASs. However, the complex principles behind the concepts and responsibilities of the environment and the interplay between agents and environment are not yet fully clarified. In this paper, we first give an overview of the state-of-the-art on environments in MASs. The survey discusses relevant research tracks on environments that have been explored so far. Each track is illustrated with a number of representative contributions by the research community. Based on this study and the results of our own research, we identify a set of core concerns for environments that can be divided in two classes: concerns related to the structure of the environment, and concerns related to the activity in the environment. To conclude, we list a number of research challenges that, in our opinion, are important for further research on environments for MAS.
Engineering Swarming Systems (with Brueckner) (11/03)
Forthcoming in F. Bergenti, M.-P. Gleizes, and F. Zambonelli, eds., Methodologies and Software Engineering for Agent Systems. Kluwer, 2004.
Most multi-agent systems are inspired by classical AI, whose objective was to realize human-level intelligence in a computer. As the field has moved toward multiple agents, there has been a presumption that individual agents still aspire to high-level intelligence. Swarming systems follow an alternative model, inspired more by artificial life than artificial intelligence. The individual agents in these systems may be non-cognitive, but complex, robust cognition emerges from their interactions. This paper defines swarming and the concepts of self-organization and emergence that underlie it. It describes the kinds of problems for which it is well suited, explores why it functions, and outlines some initial principles of an engineering methodology for developing artificial swarming systems.
Making Swarming Happen (2/03)
In Proceedings of Swarming and Network-Enabled C4ISR, Tysons Corner, VA, ASD C3I
The concept of swarming has been invoked to describe both human military tactics and the behavior of simple biological systems. Most research on the underlying mechanisms of swarming is in the biological community, and it is often not clear how these can be implemented in military systems. This paper reviews several architectures that have shown promise for generating swarming behavior in military systems, and briefly discusses how to measure and control such activity.
Temporal Aspects of Dynamic Role Assignment (with Odell, Brueckner, Sauter) (4/03)
Submitted to the 2003 Workshop on Agent-Oriented Software Engineering (AOSE2003)
A helpful abstraction of a group of agents is a set of interacting roles, or sets of normative behaviors, that the agents can assume. An important characteristic of real-world agent systems is that the roles played by an agent may change over time. These changes can be of several different kinds. We describe an illustrative application where such role changes are important, analyze and classify the various kinds of role changes over time that may occur, and show how this analysis is useful in developing a more formal description of the application.
Signs of a Revolution in Computer Science and Software Engineering (with Zambonelli) (4/02)
Forthcoming at ESAW02
Several characteristics distinguish today's complex software systems from "traditional" ones. Examples in different areas show that these characteristics, already the focus of agent-oriented software engineering research, influence many application domains. These characteristics will impact how software systems are modeled and engineered. We are on the edge of a revolutionary shift of paradigm, pioneered by the multi-agent systems community, and likely to change our very attitudes in software systems modeling and engineering.
Modeling Agents and their Environment (with Odell, Fleischer, and Brueckner)
Presented at AOSE02
Without an environment, an agent is effectively useless. Cut off from the rest of its world, the agent can neither sense nor act. An environment provides the conditions under which an entity (agent or object) can exist. It defines the properties of the world in which an agent will function. Designing effective agents requires careful consideration of both the physical and communicational aspects of their environment. Two issues exists for understanding environments:
Co-X: Defining what Agents Do Together (with Brueckner, Fleischer, and Odell)
Workshop on Teamwork and Coalition Formation, AAMAS 2002
Discussions of agent interactions frequently characterize behavior as "Coherent," "collaborative," "cooperative," "competitive," or "coordinated." We propose a series of formal distinctions among these terms and several others. We argue that all of these are spe- cializations of the more foundational category of .correlation,. which can be measured by the joint information of a system. We also propose .congruence. as a category orthogonal to the others, reflecting the degree to which correlation and its specializations satisfy user requirements. Then we explore the degree to which lack of correlation can arise purposefully, and show the need to use formal stochasticity in cases where such lack of correlation is truly necessary (such as in stochastic search).
From Design to Intention: Signs of a Revolution (with Zambonelli)
AAMAS 2002
In this paper, we identify and analyze a set of issues that are more and more influencing the characteristics of today's complex software systems, and that distinguish them from "traditional" software systems. Several examples in different areas show that these issues do not influence a few application domains only, but are instead widespread. Then, we discuss how these issues are likely to dramatically impact on the very way software is modeled and engineered. In particular, we show that we are on the edge of a revolutionary shift of paradigm, likely to change our very attitudes, and making us conceive software systems no longer in terms of mechanical systems, but rather in terms of intentional or physical systems.
Representing Social Structures in UML (with Odell) (3/01)
An extended abstract of this paper appeared as a poster at Autonomous Agents 2001, and the full version was presented at the Workshop on Agent-Oriented Software Engineering.
From a software engineering perspective, agent systems are a specialization of object-oriented (OO) systems, in which individual objects have their own threads of control and their own goals or sense of purpose. Engineering such systems is most naturally approached as an extension of object-oriented systems engineering. In particular, the Unified Modeling Language (UML) can be naturally extended to support the distinctive requirements of multi-agent systems. One such requirement results from the increasing emphasis on the correspondence between multi-agent systems and social systems. Sociological analogies are proving fruitful models for agent-oriented constructions, while sociologists increasingly use agents as a modeling tool for studying social systems. We combine several existing organizational models for agents, including AALAADIN, dependency theory, interaction protocols, and holonics, in a general theoretical framework, and show how UML can be applied and extended to capture constructions in that framework.
Representing Agent Interaction Protocols in UML (with Odell and Bauer) (10/99)
Proceedings of First International Workshop on Agent-Oriented Software Engineering
Gaining wide acceptance for the use of agents in industry requires both relating it to the nearest antecedent technology (object-oriented software development) and using artifacts to support the development environment throughout the full system lifecycle. We address both of these requirements using AUML, the Agent UML (Unified Modeling Language)—a set of UML idioms and extensions. This paper illustrates the approach by presenting a three-layer AUML representation for agent interaction protocols: templates and packages to represent the protocol as a whole; sequence and collaboration diagrams to capture inter-agent dynamics; and activity diagrams and state charts to capture both intra-agent and inter-agent dynamics.
Specification and Design of Industrial Synthetic Ecosystems (with Sauter and Clark) (5/97)
Presented at ATAL'97
Many agent-based systems rely for their effectiveness on the intelligence of individual agents, and interaction among agents is required simply to coordinate these individually complex decisions. Specification and design methods for such systems focus on the internal architecture of individual agents. An alternative approach, "Synthetic Ecosystems," uses relatively simple agents and draws heavily on the dynamics of the interaction among these agents as well as their internal processing to solve domain problems. The specification and design of such systems must include not only the individual agents, but also the structure and dynamics of their interaction. This paper briefly defines and motivates the Synthetic Ecosystems approach and outlines some techniques that have proven useful in specifying and designing them.
Army Science Conference 2006
DARPA’s Real-time Adversarial Intelligence and Decision-making (RAID) program has demonstrated a promising new capability to predict enemy location and intent in dynamic urban combat environments. This capability may significantly improve the Blue commander’s decision processes by increasing his situational awareness and tactical team coordination capabilities. Experimental results obtained over the past two years indicate that a single commander in a simulated urban combat environment assisted by RAID outperforms a 5-person senior staff of military Subject Matter Experts. These results also indicate that RAID predictions and recommendations can improve the mission planning process by providing a previously unavailable level of predictive analysis. This paper will address several team performance factors that are improved by RAID and their impact on the mission planning process, present results from the RAID Experiment 4 (July 2006), and describe a key technology extension that is needed for improving the real-time situational awareness data provided to RAID.
Swarming Methods for Geospatial Reasoning (with Brueckner, Matthews, Sauter)International Journal of Geographical Information Science
Geospatial data is often used to predict or recommend movements of robots, people, or animals ('walkers'). Analysis of such systems can be combinatorially explosive. Each decision that a walker makes generates a new set of possible future decisions, and the tree of possible futures grows exponentially. Complete enumeration of alternatives is out of the question. One approach that we have found promising is to instantiate a large population of simple computer agents that explore possible paths through the landscape. The aggregate behaviour of this swarm of agents estimates the likely behaviour of the real-world system. This paper will discuss techniques that we have found useful in swarming geospatial reasoning, illustrate their behaviour in specific cases, compare them with existing techniques for path planning, and discuss the application of such systems.
A Survey of Environments and Mechanisms for Human-Human Stigmergy (10/05)Proceedings of E4MAS05 (Invited Paper)
Stigmergy (the coordination of agents through signs they make and sense in a shared environment) was originally articulated in the study of social insects. Its basic processes are much simpler than those usually used to model human-level cognition. Thus it is an attractive way to coordinate agents in engineered environments such as robotics or information processing. Stigmergic coordination is not limited to insects. Humans regularly use environmentally-mediated signals to coordinate their activities. This paper develops a schema for analyzing stigmergy among humans, discusses examples (some using a computational environment and others antedating digital computation), and suggests how the use of such mechanisms may be extended.
Research Directions for Service-Oriented Multiagent Systems (with Huhns et al.) (11/05)IEEE Internet Computing 9:6 (Nov/Dec), 65-70.
Today’s service-oriented systems realize many ideas from the research conducted a decade or so ago in multiagent systems. Because these two fields are so deeply connected, further advances in multiagent systems could feed into tomorrow’s successful service-oriented computing approaches.This article describes a 15-year roadmap for service-oriented multiagent system research.
Stigmergic Learning for Self-Organizing Mobile Ad-Hoc Networks (MANET's) (with Brueckner) (1/2004).
he Third International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'04), Columbia University, NY, 1324-1325.
In recent years, mobile ad-hoc networks (MANET’s) have been deployed in various scenarios, but their scalability is severely restricted by the human operators’ ability to configure and manage the network in the face of rapid change of the network structure and demand patterns. In this paper, we present a self-organizing approach to MANET management based on stigmergic agents and demonstrate how to analyze its performance under different deployment assumptions. Our results emphasize the importance of attention to notions from dynamical systems theory in designing and deploying multi-agent systems.
Analyzing Stigmergic Learning for Self-Organizing Mobile Ad-Hoc Networks (MANET's) (with Brueckner).
Workshop on Engineering Self-Organising Agent Systems (ESOA04), Columbia University, NY.
In recent years, mobile ad-hoc networks (MANET’s) have been deployed in various scenarios, but their scalability is severely restricted by the human operators’ ability to configure and manage the network in the face of rapid change of the network structure and demand patterns. In this paper, we present a self-organizing approach to MANET management based on stigmergic agents and demonstrate how to analyze its performance under different deployment assumptions. Our results emphasize the importance of attention to notions from dynamical systems theory in designing and deploying multi-agent systems.
ERIM's Approach to Fine-Grained Agents (9/2001) (with Brueckner and Sauter)
NASA/JPL Workshop on Radical Agent Concepts (WRAC'2001), Greenbelt, MD, 19-21 September 2001.
Traditional software agents, an extension of Artificial Intelligence, seek human-level intelligence in each agent. For over 15 years, inspired by Artificial Life, ERIM has been devising architectures in which useful intelligence emerges at the system level from interactions of fine-grained agents. We have applied such architectures to a wide variety of domains, including business, industrial, and military. This white paper outlines three major principles that characterize our approach: environmental mediation, emergent dynamics, and growing vs. building. For each we discuss what the principle is, why it is important, and how it works in practical implementations.
A Practitioners' Review of Industrial Agent Applications (5/2000)
Autonomous Agents and Multi-Agent Systems 3:4, pp. 389-407.
ERIM's Center for Electronic Commerce (CEC) hosted a two-day Workshop on Industrial Agents in Ann Arbor, MI on Nov. 12-13, 1998. Participation in the workshop was by invitation only, and was restricted to companies with whom the CEC is doing business or developing collaborations in agent technologies. Because of its industrial focus, the workshop's objectives have a rather different emphasis than research-oriented workshops and conferences. The projects discussed at the workshop and summarized in this report fall into three areas of increasing generality: focused applications, broadly applicable tools, and methodological guidelines.
Density-Based Emergent Scheduling System (9/99) (with Clark)
US Patent 5,953,229
An apparatus for determining assignments to attributes (e.g., electrical power or overall dimensional size) of components within a system. A computerized constraint network is constructed which uses constraint agents, variable agents, and task agents in order to make assignments to the attributes of the components based upon market-based constraint optimization techniques. The attributes have variables indicative of the assignments to the attributes. Constraint data structures assist the agents in determining permissible assignments for the variables. The constraint data structures use preferential rules for determining the assignments to the variables. The preferential rules indicate which assignments for the variables of the agents produce higher utility and lower cost.
ANTS in the Supply Chain (5/99) (with Sauter)
Presented at the Workshop on Agent based Decision Support for Managing the Internet-Enabled Supply Chain, Agents 99, Seattle, WA, 1 May 1999
Computer agent based systems provide a natural mechanism to reflect
real world human agent based systems. Supply chains are networks of corporations
involving multiple human agents in connected but disparate processes. We
investigate some ways that computer agent-based systems can assist and
supplant human-based interaction and decision making in a supply chain
without the need for unwieldy centralized or top-down management schemes.
The Agent Network for Task Scheduling (ANTS) architecture uses techniques
inspired by both human institutions and insect colonies. In ANTS large
populations of simple agents exhibit robust
behavior in scheduling supply chains. We describe a new mechanism called
least commitment scheduling that defers decisions on process sequences
until the last possible moment. A Density-based Emergent Scheduling Kernel
(DESK) uses probabilistic committed capacity profiles of resources over
time to provide a surface over which the agents can wander looking for
opportunities to optimize.
International Journal of Cooperative Information Systems9:3 (2000) 209-227.
Agent technologies have steadily matured in moving from the research laboratory to industrial application over the last ten years. Numerous systems have been deployed or are under advanced development with strong industrial support. These systems suggest important lessons for both industry and researchers. From an industrial perspective, these examples reflect trends in both business and technology that make agents an increasingly attractive commercial tool. From a research perspective, these examples identify important gaps in agent technology that merit the attention of academicians.
Characterizing Multi-Agent Negotiation (2/99)
A summary of a working group at IWMAS'98.
“Negotiation” is a vague term, covering a wide range of interaction mechanisms. This paper resulted from a working group at IWMAS’98. It exhibits a selection of mechanisms that are commonly considered “negotiation,” and then develops characterizations for distinguishing different kinds of negotiation, along three dimensions: context management, complexity measurement, and coherence mechanisms.
The AARIA Agent Architecture: From Manufacturing Requirements to Agent-Based System Design (5/99)
Forthcoming in Integrated Computer-Aided Engineering. The original version of this paper was presented at the Workshop on Agent-Based Manufacturing, ICAA’98, Minneapolis, MN, 10 May 1998.
Designs for real-world agent-based systems must reflect both domain requirements and technical capabilities. We illustrate some of the requirements for agents in manufacturing scheduling and an architecture that addresses them with a case study of AARIA (Autonomous Agents for Rock Island Arsenal), an industrial-strength agent-based shop-floor control and scheduling architecture being developed for an Army manufacturing facility. A review of other agent-based manufacturing systems illustrates how the design choices made in such systems reflect the requirements anticipated by the authors.
What can Agents do in Industry, and Why? An Overview of Industrially-Oriented R&D at CEC (3/98)
Published in Klusch and Weiss, eds., Cooperative Information Agents II, LNCS 1435, pp. 1-18.
The Center for Electronic Commerce (CEC) embodies over fourteen years of experience in applying agents to industrial problems. We have found such a fit in three areas: coordination of industrial designers, simulation and modeling of complex products and processes, and scheduling and control of production systems. This presentation outlines several trends in modern manufacturing, describes how these trends affect the three problem areas, discusses the features of agents that make them attractive candidates for implementing such systems, and reviews example applications from CEC’s portfolio in each of these areas.
Practical and Industrial Applications of Agent-Based Systems (3/98)
Agent-based software architectures are finding more and more acceptance in commercial and industrial applications. This survey outlines the varieties of agent architecture in use today, discusses the requirements of industrial users from the perspective of a development life cycle, and gives numerous case studies of agents from this perspective.
"Go to the Ant": Engineering Principles from Natural Agent Systems (1/97)
Annals of Operations Research 75 (1997) 69-101.
Agent architectures need to organize themselves and adapt dynamically to changing circumstances without top-down control from a system operator. Many researchers provide this capability with complex agents that emulate human intelligence and reason explicitly about their coordination, reintroducing many of the problems of complex system design and implementation that motivated increasing software localization in the first place. Naturally occurring systems of simple agents (such as populations of insects or other animals) suggest that this retreat is not necessary. This paper summarizes several studies of such systems, and derives from them a set of general principles that artificial agent-based systems can use to support overall system behavior significantly more complex than the behavior of the individuals agents.
Workshop Report: Implementing Manufacturing Agents (7/96)
This document summarizes the discussions at the Workshop on Implementing Manufacturing Agents held in conjunction with PAAM'96. The workshop was sponsored by the Shop Floor Agents (SFA) project, a consortial activity of AMP, General Motors, Gensym, and Rockwell Automation under the auspices of the National Center for Manufacturing Sciences (NCMS; http://www.ncms.org).
Autonomous Agent Architectures: A Non-Technical Introduction (10/95)
Competitive pressures are moving manufacturers toward shorter product cycles, lower inventories, higher equipment utilization, and shorter lead times. As a result, the problem of scheduling and controlling the shop floor grows in importance. Manufacturing scheduling and control has traditionally been viewed as a top-down process of command and response that relies heavily on hierarchical models of the manufacturing enterprise. This white paper suggests a different perspective, one that focuses on the local autonomy of workstations, parts, and operators, without sacrificing the predictability required in a business context. Such an approach will be more robust and easier to modify than conventional centralized systems, and new technologies promise to make it manageable as well.
Applications of Distributed Artificial Intelligence in Industry (1/96)
Chapter 4 in O'Hare and Jennings, eds., Foundations of Distributed Artificial Intelligence. Wiley Inter-Science, 1996.
In many industrial applications, large centralized software systems are not as effective as distributed networks of relatively simpler computerized agents. For example, to compete effectively in today's markets, manufacturers must be able to design, implement, reconfigure, resize, and maintain manufacturing facilities rapidly and inexpensively. Because modern manufacturing depends heavily on computer systems, these same requirements apply to manufacturing control software, and are more easily satisfied by small modules than by large monolithic systems.
This paper reviews industrial needs for Distributed Artificial Intelligence (DAI), giving special attention to systems for manufacturing scheduling and control. It describes a taxonomy of such systems, gives case studies of several advanced research applications and actual industrial installations, and identifies steps that need to be taken to deploy these technologies more broadly.
MASCOT: A Virtual Factory for Research and Development in Manufacturing Scheduling and Control (10/95)
Both researchers and industrial engineers interested in Manufacturing Scheduling and Control (MSC) are frustrated by the complexity of the problem and the wide range of approaches that have been proposed. The research environment often discourages scientists from the extensive effort and hands-on experience needed to gain a realistic view of the problem, and manufacturing engineers have no way to assess the relative practical value of the many proposed approaches. This white paper proposes a Manufacturing Scheduling and Control Testbed (MASCOT) to address these challenges to technology transfer: a Virtual (simulated) Factory, supporting a library of detailed industrial cases. Researchers can use MASCOT as a convenient source of realistic challenges, and vendors and manufacturers can use it to identify promising technologies for more rapid transfer to commercial application. In addition to this primary mission, the MASCOT Virtual Factory will provide several key technical elements in support of the broader vision of agile manufacturing enterprises.
The AARIA Agent Architecture (with Baker and Clark)(10/98)
Presented at the Workshop on Agent-Based Manufacturing, 1998 International Conference on Autonomous Agents; forthcoming in Integrated Computer-Aided Engineering.
To be accepted in real-world applications, designs for agent-based systems must reflect domain requirements as well as technical capabilities. This needs-driven approach is being applied in AARIA (Autonomous Agents for Rock Island Arsenal), an industrial-strength agent-based shop-floor control and scheduling architecture being developed for an Army manufacturing facility. First, we define requirements, considering both those imposed by the system's interface with its external environment, and those needed in its internal operations to support the required functionality. Then we discuss why an agent approach is appropriate, what agents are needed, and how they should behave, based on the requirements, and finally illustrate the interactions of the various agents in the context of an example.
Manufacturing over the Internet and into Your Living Room (with Baker and Erol) (1/97)
Consumer demand and current computational capabilities are driving the manufacturing complex from mass production to mass customization. Current barriers to mass customization have less to do with manufacturing machinery and more to do with the manual and computerized information systems currently used to control that machinery. On-line commerce offers potential benefits and functionality far beyond the automated catalogs that characterize today's cybermarkets. The AARIA project (Autonomous Agents for Rock Island Arsenal) demonstrates how agent technologies and Internet communications can support this expanded vision. This paper outlines new directions that we expect trade on the Internet to take, and shows how AARIA's architecture, scheduling approach, and simulation capabilities support these new directions.
A Connectionist Model for Material Handling (with Kindrick and Irish) (1988)
Robotics and Computer-Integrated Manufacturing, 4(3/4) (1988), 643-654.
Connectionist models have traditionally been motivated by the desire to imitate human intelligence by copying biological information processing mechanisms. We can also apply them to tasks that are not usually associated with human cognition, by taking advantage of promising mappings between their features (such as distribution, local computation, constraint propagation and computation by relaxation) and certain problem domains. This paper reports the design and implementation of CASCADE, a system for performing the material handing function in a discrete parts manufacturing environment. CASCADE draws heavily on connectionist models, and has been implemented in an experimental machining cell. We discuss the problem domain of material handling; the connectionist framework that we are using; the structure of CASCADE in terms of the connectionist model; and some computational implications of the model that we exhibit.
Material Handling: A Conservative Domain for Neural Connectivity and Propagation (with Kindrick and Irish) (1987)
AAAI'87, 307-311.
Two important components of connectionist models are the connectivity between units and the propagation rule for mapping outputs of units to inputs of units. The biological domains where these models are usually applied are nonconservative, in that a single output signal produced by one unit can become the input to zero, one, or many subsequent units. The connectivity matrices and propagation rules common in these domains reflect this nonconservatism in both learning and performance.
CASCADE is a connectionist system for performing material handling in a discrete parts manufacturing environment. We have described elsewhere the architecture and implementation of CASCADE and its formal correspondence with the PDP model. The signals that CASCADE passes between units correspond to discrete physical objects, and thus must obey certain conservation laws not observed by conventional neural architectures.
This paper briefly reviews the problem domain and the connectionist structure of CASCADE, describes CASCADE's scheme for maintaining connectivity information and propagating signals, and reports some experiments with the system.
Manufacturing Experience with the Contract Net (1987)
In M. N. Huhns, Editor, Distributed Artificial Intelligence, Pitman, London (1987), 285-310.
We have implemented a control system for a discrete manufacturing system that partitions tasks using a negotiation protocol like the contract net described by Smith and Davis. The application domain differs in interesting ways from those to which contract nets have previously been applied. This report outlines our architecture, summarizes some differences between the factory floor and other problem domains, and discusses how we accommodate these distinctive features.
An Architecture for Heuristic Manufacturing Control (1986) (with White and Lozo)
Proceedings of the American Control Conference.
This paper describes the architecture of YAMS (Yet Another Manufacturing System), a factory control system for flexible manufacturing currently under development at the Industrial Technology Institute. We summarize some objectives such a system must satisfy, and its overall architecture. Then we focus on three details of the overall system: its scheduling strategies, strategies for moving tools and materials around the factory, and the bottom elements in the hierarchy, the individual workstations.
Computerized system for market-based constraint optimization (3/2003) (with Sauter and Ward)
US Patent 6,536,935
An apparatus for determining assignments to attributes (e.g., electrical power or overall dimensional size) of components within a system. A computerized constraint network is constructed which uses constraint agents, variable agents, and task agents in order to make assignments to the attributes of the components based upon market-based constraint optimization techniques. The attributes have variables indicative of the assignments to the attributes. Constraint data structures assist the agents in determining permissible assignments for the variables. The constraint data structures use preferential rules for determining the assignments to the variables. The preferential rules indicate which assignments for the variables of the agents produce higher utility and lower cost.
The RAPPID Project: Symbiosis between Industrial Requirements and MAS Research (with Ward, Fleischer, and Sauter) (1/02)Journal of Autonomous Agents and Multi-Agent Systems 2:2 (June 1999), 111-140.
The RAPPID project (Responsible Agents for Product-Process Integrated Design) is developing agent-based software tools and methods that use market place dynamics among members of a distributed design team to coordinate set-based design of discrete manufactured products. This report describes the interplay of industrial requirements and Multi-Agent System (MAS) research in the design, implementation, and testing of RAPPID. Like any industrial project, RAPPID begins with the requirements of the problem domain, and draws selectively from research results to meet those requirements. However, the flow of information is not unidirectional. In the process of addressing its requirements, RAPPID developed some new concepts that hold promise for broader application to distributed constraint optimization. RAPPID is work in process, not a completed product, and this report includes an assessment of what needs to be done in addition to what has been accomplished.
The MarCon Algorithm: A Systematic Market Approach to Distributed Constraint Problems (with Ward and Sauter) (10/98)
AI-EDAM 13 (1999), 217-234. A summary appears in the Proceedings of ICMAS'98.
MarCon (Market-based Constraints) applies market-based control to distributed constraint problems. It offers a new approach to distributing constraint problems that avoids challenges faced by current approaches in some problem domains, and it provides a systematic method for applying markets to a wide array of problems. Constraint agents interact with one another via the variable agents in which they have a common interest, using expressions of their preferences over sets of assignments. Each variable integrates this information from the constraints interested in it and provides feedback that enables the constraints to shrink their sets of assignments until they converge on a solution. MarCon originated in a system for supporting human product designers, and its mechanisms are particularly useful for applications integrating human and machine intelligence to explore implicit constraints. MarCon has been tested in the domain of mechanical design, in which its set-narrowing process is particularly useful.
Distributed Component-Centered Design as Agent-Based Distributed Constraint Optimization (with Ward, Fleischer, Sauter, and Chang) (8/97)
Presented at AAAI'97 Workshop on Constraints and Agents
Many manufactured systems (both consumer goods and manufacturing systems) consist of a number of discrete subsystems and components that interact with one another through various interfaces to provide the required functionality. Designing such a system requires finding values for interface variables that are compatible among the various components, and is analogous to the constraint optimization problem, with subsystems and components playing the role of constraints among the variables. Today’s business environment requires design to be done by distributed teams of engineers, so the analogy can be extended to distributed constraint optimization (DCOP). This paper develops the parallel between distributed component-centered design (DCCD) and DCOP, discusses the particular flavor that industrial requirements impart to the mapping, and reports how this parallel is being exploited in the RAPPID system for agent-based distributed design.
A Marketplace of Design Agents for Distributed Concurrent Set-Based Design (with Ward, Fleischer, and Sauter) (3/97)
Presented at Concurrent Engineering '97.
The RAPPID project (Responsible Agents for Product-Process Integrated Design) is developing agent-based software tools and methods for using market place dynamics among members of a distributed design team to coordinate set-based design of a discrete manufactured product. This report begins with an overview of the RAPPID vision, in which the components being designed (represented by their designers) buy and sell the characteristics they wish to assume. It describes the entities that interact in the market economy and outlines the market protocols through which trades are made.
Modeling Collective Cognitive Convergence (with Belding, Hilscher, and Brueckner)(10/07)
Agent 2007
When the same set of people interact frequently with one another, they tend to think more and more along the same lines, a phenomenon we call "collective cognitive convergence" (C^3). In this paper, we discuss instances of this phenomenon and why it is advantageous or disadvantageous; review previous work in computational social science and evolutionary biology that sheds light on C^3; define a computational model for the convergence process and a quantitative metric that can be used to study it; report on experiments with this model and metric; and suggest how the insights from this model can inspire techniques for managing C^3.
Comparing Agent Trajectories (with Brophy and Brueckner) (10/07)
Agent 2007
Sometimes it is desirable to measure the difference between the spatial trajectories of two or more agents. The naïve measure (the sum of Euclidean distances between locations at successive timesteps) increases with the lengths of the trajectories, which is not suitable for some applications. This paper explains the problem that motivates such a comparison, describes the design of the comparison that we are using, and gives an example of its application.
Monitoring and Managing Intelligence in Distributed Systems (9/07).
AAAI 2007 Fall Symposium, Regarding the Intelligence in Distributed Intelligent Systems (RIDIS) (invited paper)
Both the promise and the challenge of distributed systems often derive from emergent behavior, functionality that is not defined explicitly in the individual components of the system but results from their interactions. Effective use of these systems depends on techniques for monitoring and controlling such system-level behavior. A fruitful source of inspiration for such techniques is statistical mechanics, with its mature success in explaining the macro-level characteristics of matter from the interactions of atoms and molecules. This paper summarizes a number of such analogies that we have exploited in our work.
Prediction Horizons in Polyagent Models (with Belding and Brueckner) (5/07).
AAMAS 2007
One motivation for many agent-based models is to predict the future. The nonlinearity of agent interactions in most non-trivial domains mean that the usefulness of such predictions will be limited beyond a certain point (the "prediction horizon"), due to unbounded divergence of their trajectories. The model’s predictions are increasingly useful out to the prediction horizon, but become misleading beyond that point. We exhibit and characterize this behavior in a simple model, based on the polyagent modeling construct, which uses multiple ghost agents to explore alternative futures concurrently for a domain entity. We also discuss how a single agent in such a model can estimate the prediction horizon based on locally available information, and use this estimate to modulate dynamically how far it seeks to look into the future.
Global Convergence of Local Agent Behaviors (with Brueckner, Sauter, and Matthews) (12/2004).
The Fourth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'05), Utrecht, Netherlands, 305-312.
Many multi-agent systems seek to reconcile two apparently inconsistent constraints. The system’s overall objective is defined at a global level. However, the agents have only local in-formation available to them in selecting their actions. Such systems are presently more art than science. They often exhibit regularities (such as exponential convergence) that we do not understand, and we do not know how to improve their function-ing in a disciplined manner. In this paper, we develop a simple statistical model for such systems that can enhance both our intuitions about their functioning and our ability to engineer them, and apply it to three systems that we have constructed.
Universality in Multi-Agent Systems (with Brueckner and Savit) (1/2004).
The Third International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'04), Columbia University, NY, 930-937.
Much research in multi-agent systems reflects the field’s origins in classical artificial intelligence, showing how various refinements to the internal reasoning of individual agents improve overall system performance. Sometimes, aspects of a system’s behavior are independent of the algorithms used by individual agents. Drawing from an analogy in statistical physics, we term this phenomenon “universality.” The underlying concept is that systems whose elements differ widely may nevertheless have common emergent features. We develop a notion of universality in MAS based on the concept’s use in its original (physics) setting. We illustrate the concept in several examples, and discuss the implications of MAS universality for the theory and practice of MAS. We speculate that there exists a hierarchy of types of universality. The usual use of the term in statistical mechanics refers to the most refined, simplest, and quantitative, while commonalities among systems that are of interest to the MAS community are associated with somewhat more general and qualitative levels of universality. Such a hierarchy would be an important integrating principle across systems of interacting components including human societies, animal ecologies, multi-agent systems, and atoms and molecules.
Dynamic Imputation of Agent Cognition (with Brueckner) (12/2003).
Forthcoming in Proceedings of Autonomy 2003.
People can interact much more readily with a multi-agent system if they can understand it in cognitive terms. Modern work on "BDI agents" emphasizes explicit representation of cognitive attributes in the design and construction of a single agent, but transferring these concepts to a community is not straightforward. In addition, there are single-agent cases in which this approach cannot yield the desired perspicuity, including fine-grained agents without explicit internal representation of cognitive attributes, and agents whose inner structures are not accessible. We draw together two vintage lines of agent research to address this problem: the perspective that cognition can legitimately be imputed externally to a system irrespective of its internal structure, and the insight from situated automata that dynamical systems offer a well-defined se-mantics for cognition. We demonstrate this approach in both single agent and multi agent examples.
Imputing Agent Cognition from Dynamics (with Brueckner) (4/03)
2003 Workshop on Autonomy, Delegation, and Control at AAMAS'03
A cognitive model of an agent or a multi-agent system greatly enhances high-level human interaction with engineered systems. Modern work on “BDI agents” emphasizes explicit representation of cognitive attributes in the design and construction of an agent, but there are several circumstances in which this approach cannot yield the desired perspicuity, including fine-grained agents with-out explicit internal representation of cognitive attributes, agents whose inner structures are not accessible, and the emergent properties of swarms of interacting agents of any type. We draw together two vintage lines of agent research to address this problem: the perspective that cognition can legitimately be imputed externally to a system irrespective of its internal structure, and the insight from situated automata that dynamical systems offer a well-defined semantics for cognition. We demonstrate this approach in both single agent and multi agent examples, including swarm-based emergent path planning for unpiloted vehicles.
How to Calm Hyperactive Agents (with Brueckner, Matthews, and Sauter) (1/03)
AAMAS'03
System performance in multi-agent resource allocation systems can often improve if individual agents reduce their activity. Agents in such systems need a way to modulate their individual behavior in the light of the system’s state, preferably in a way that does not require centralized control. We illustrate the problem of hyperactive agents in two domains related to resource allocation. We describe a simple, decentralized scheme, inspired by insect pheromones, that enables individual agents to adjust their level of activity as the system operates, and discuss a general approach to dealing with approaching deadlines. Then we demonstrate the effectiveness of these mechanisms in the two example domains.
Information-Driven Phase Changes in Multi-Agent Coordination (with Brueckner) (1/03)
Forthcoming at AAMAS03
Large systems of agents deployed in a real-world environment face threats to their problem solving performance that are independent of the complexity of the problem or the characteristics of their specific solution mechanism. One such threat is the degrading of the quality of agent coordination mechanisms when faced with delays in the flow of critical information among the agents introduced by communication latencies. In this paper we demonstrate in a simple model of locally interacting agents that the emerging system-level performance may degrade very suddenly as the rate of individual decision making increases against the availability of up-to-date information. We present results from extensive simulation experiments that lead us to select a locally accessible metric to adapt the agent’s individual decision rate to values that are below this phase change. Given the generic nature of the coordination mechanism that is analyzed and the informationtheoretic metric, the adaptation mechanism may increase the deployability of large-scale agent systems in real-world applications.
Resource-Aware Exploration of the Emergent Dynamics of Simulated Systems (with Brueckner)
Forthcoming at AAMAS03
The emerging science of simulation enables us to explore the dynamics of large and complex systems even if a formal representation and analysis of the system is intractable and a construction of a real-world instantiation for the purpose of experimentation is too expensive. A computer simulation model can be run for many more configurations and the accumulated observations deepen our understanding of the system’s operation, but it is very important that we have tools that help us manage the huge numbers of experiments that need to be run and the massive data sets that are collected. Furthermore, as we explore vast parameter spaces of simulation model, we need guidance in finding regions of interest in a resource efficient way. In this paper we use a model of agent-based graph coloring to introduce a software infrastructure for the systematic execution of experiments across large regions of parameter space (parameter sweep). Furthermore, we present a multi-agent system that searches large parameter spaces automatically for regions of interest specified by a fitness function. The fitness function captures the researcher’s interest in certain system dynamics. We specify a function that searches for overlap regions that accompany phase changes in the simulation model. The agents search the parameter space by executing simulation experiments in regions of high fitness. As a consequence, the use of computational resources is minimized.
General Structure of Resource Allocation Games (with Savit, Brueckner, and Sauter)
A shorter version of this paper is forthcoming in Physics Letters A.
In this paper, we study a class of games that are generalizations of the minority game, and model, more generally, systems in which agents compete for a scarce resource. In particular, we study a set of games in which the demand and supply of the resource are specified independently. This allows us to study the ways in which such systems behave as the resource becomes increasingly scarce or increasingly abundant relative to demand. We find an intricate and rich structure to these games with a number of very intriguing features. Among these is the existence of a robust phase change with a coexistence region as the demand/supply ratio is varied, and the games move from scarce to abundant resources. This coexistence region exists when the amount of information used by the agents to make their choices is greater than a certain level, which is related to the point at which there is a phase transition in the standard minority game. We also discuss practical and theoretical implications of our work.
Effort Profiles in Multi-Agent Resource Allocation (with Brueckner, Sauter, and Savit)
AAMAS 2002
Multi-agent systems are particularly appropriate for resource allocation, but configuring them for efficient operation requires understanding their dynamics. Concepts from statistical physics, such as phase transitions, can help. In decision problems such as constraint satisfaction, such transitions exhibit an easy-hard-easy effort profile, so that highly overconstrained problems are easier to solve than those near the transition. The conventional wisdom is that the profile in optimization problems such as resource allocation is monotonic, becoming more difficult as constraints increase. Contrary to this lore, we exhibit an easy-hard-easy profile in a multi-agent resource allocation problem. We compare problems that exhibit such a profile with others that do not and offer insights as to when such behavior can be expected and why it is desirable from a practical perspective.
Experiments in Indirect Negotiation (8/01) (with Savit, Brueckner, and Sauter)
AAAI 2001 Fall Symposium on Negotiation Methods for Autonomous Cooperative Systems
The purpose of negotiation is to enable agents to coordinate their actions. Characterizing coordination in information-theoretic terms leads us to consider negotiation in the context of other processes that can transfer information among agents, such as those mediated by the environment. We illustrate these concepts using the Minority Game, an abstract model of resource allocation that achieves coordination without negotiation in the classical sense. Our work illustrates two important lessons. 1) Indirect (environmentally-mediated) negotiation can achieve agent coordination even without conventional negotiation. 2) The information flow between agents and the environment is likely to affect the dynamics of systems even when they use more conventional negotiation.
A keynote presentation at IMS'99.
Many potential applications for artificial intelligence (AI) in manufacturing extend classical AI in two ways. First, they go beyond modeling a single decision-maker to incorporate the interactions of multiple “agents.” Second, instead of fitting a “problem solving” rubric that seeks to reach achievement goals, they are more aptly cast as “going concerns” that support maintenance goals in the face of continual disruption. The first extension is the focus of active research in multi-agent systems (MAS), with which the IMS community has established effective ties. This paper proposes that the second extension can benefit from the use of concepts from dynamical systems theory (informally, “chaos theory”). This field provides useful metaphors for discussing going concerns. Its promise goes further than metaphor, for multi-agent systems are actually dynamical systems, whose effective design, monitoring, and control requires application of techniques developed in dynamical systems. Thus researchers and developers who are exploring and deploying MAS in manufacturing must give careful attention to the distinctive challenges and unique opportunities of dynamical systems theory.
A Dynamical Systems Perspective on Agent-Based "Going Concerns" (2/99)
A summary of a working group at IWMAS'98.
Classical AI largely follows a “problem solving” rubric that seeks to reach achievement goals. Many applications of intelligence are more aptly cast as “going concerns” that support maintenance goals in the face of continual disruption. Concepts from dynamical systems theory provide useful metaphors for discussing going concerns. Their promise goes further than metaphor, for the multi-agent systems that are widely used to implement them are actually dynamical systems, whose effective design, monitoring, and control requires application of techniques developed in dynamical systems.
DASCh: Dynamic Analysis of Supply Chains (1/99)
This document is the final report of the DASCh project, offering a detailed review of previous work, individual agent behaviors, theoretical analysis, and experimental results.
The DASCh Experience: How to Model a Supply Chain (10/98)
Presented at ICCS'98.
In many domains, agent-based system modeling competes with equation-based approaches that identify system variables and evaluate or integrate sets of equations relating these variables, and sometimes with analytical formulations that lend themselves to closed-form proofs. The distinction has been of great interest in the DASCh project (“Dynamical Analysis of Supply Chains”), which applies agent-based modeling to industrial supply networks. Virtually all computer-based modeling of such networks up to this point has used system dynamics, an approach based on ordinary differential equations (ODE’s). This paper summarizes the domain of supply networks and illustrates how they can be modeled with agents, with equations, and as a proof-based system. It summarizes the similarities and differences of these classes of models, and develops criteria for selecting one or the other approach.
Agent-Based Modeling vs. Equation-Based Modeling: A Case Study and Users’ Guide (with Savit and Riolo) (10/98)
In Proceedings of Multi-agent systems and Agent-based Simulation (MABS'98), pages 10-25, Springer, LNAI 1534, 1998.
In many domains, agent-based system modeling competes with the “system dynamics” approach that identifies flows and stocks of system variables and integrates sets of partial differential equations describing these flows and stocks over time. The competition has been of great interest in our DASCh project, which applies agent-based emulation to industrial supply networks, since virtually all computer-based modeling of such networks up to this point has been of the numerical variety. This paper summarizes the domain of supply networks and illustrates how they can be modeled both with agents and numerically. It summarizes the similarities and differences of these two classes of models, and develops criteria for selecting one or the other approach.
Modeling The Extended Supply Network (with VanderBok) (4/98)
ISA-Tech'98 (Houston)
The growth of network technology is making it possible to extend control techniques beyond the individual factory and even the single company. Today one can conceive of on-line control strategies that embrace a large segment of an extended enterprise, such as a supply network. An initial step in developing enterprise-wide control methods is modeling the dynamical behavior of the system to be controlled. This paper reports some preliminary results from an agent-based model of a simple supply network, together with some validating analyses of operating data from supply chains in automotive and electronics assembly. Then it discusses the benefits of agent-based models in comparison with more traditional differential equation models of system behavior at the enterprise level.
Managing Emergent Behavior in Distributed Control Systems (with Ray VanderBok) (4/98)
Presented at ISA-Tech '97 (Anaheim)
Distributed control architectures are becoming increasingly popular because their modularity makes them easy to install, configure, and modify. These benefits do not come for free. A population of asynchronously executing processes without central top-down control can exhibit unexpected or “emergent” behavior at the system level. To the plant engineer, this behavior may look like noise or error conditions, but it is generated by deterministic interactions among control elements, not random events or unit malfunctions, and it must be managed accordingly. Drawing on experiences in the Auto Body Consortium’s Intelligent Resistance Welding project, we illustrate the potential for this kind of behavior among welding robots in an automotive body shop and in other applications, show how recent research in nonlinear systems theory and agent-based control can be used to detect and manage such interactions, and identify some requirements that these agent techniques place on emerging standards for data and control models.
Complexity Theory in Manufacturing Engineering: Conceptual Roles and Research Opportunities (10/95)
Three recent workshops (Santa Fe, 2-4 Dec. 1992; Ann Arbor, 13-15 April 1993; 21-22 Sept. 1993) have drawn attention to the role of complexity theory in understanding and managing manufacturing scheduling and control (MSC), particularly in the domain of discrete manufacturing. These discussions bring together two conceptual areas: complexity theory (which leads to notions such as formal chaos, fractals, and emergent behavior), and manufacturing (the practical challenge of quickly and inexpensively producing goods that delight the customer).
There are at least three different ways in which these concepts can be related to one another. Each of these represents a distinctive thrust for research on the subject of complex systems in manufacturing.
1. Complexity theory undergirds new technologies that address MSC challenges. Manufacturing engineers are beginning to explore distributed architectures of relatively autonomous agents whose behaviors emerge as the system runs rather than being defined in advance and then rigidly executed. Progress in this thrust requires disciplined hands-on implementations and technology transfer.
2. Complexity theory can help define the underlying challenge that such systems seek to address. Factories are de facto complex systems. There's nothing new about this idea, but our ability to define precisely what we mean by "complex" has improved considerably in recent years, and this new understanding has yet to be applied to studies of manufacturing systems. Progress in this thrust requires construction of hypotheses about manufacturing dynamics, collection of real-world data, and empirical analysis.
3. Complexity theory can provide the scientific foundation for engineering specific MSC architectures to address specific manufacturing challenges, thus integrating the previous two points. Progress in this thrust requires the development of detailed executable models of manufacturing facilities and extensive experimentation with them.
So far, research on the subject of complexity in manufacturing has been limited to the first thrust: experimentation with novel MSC architectures. These new approaches are currently justified by the known inadequacies of current architectures and some encouraging empirical results of early implementations, not by any disciplined application of the growing body of formal knowledge about the dynamics of complex systems. This white paper argues that complexity theory offers a powerful apparatus both to understand the nature of the shop floor (the second thrust) and to derive specific engineering guidelines for MSC systems (the third thrust), and outlines specific R&D activities that will provide a solid engineering base for the next generation of MSC systems.
The paper is organized in three main sections, corresponding to the three thrusts. The first section reviews current directions in autonomous agent architectures for MSC; the second section describes how complexity theory can help understand the factory floor, and the third section develops a vision for leveraging formal results of complexity theory in engineering MSC systems. Each of these sections motivates its topic intuitively, develops in more detail the role of complexity theory, and proposes specific research activities. A fourth section describes key institutions that together could carry out this agenda.
The Heartbeat of the Factory:Understanding the Dynamics of Agile Manufacturing Enterprises (1/96)
Manufacturing engineers often characterize the behavior of a manufacturing system with averages over time. This approach is appropriate for a system that spends most of its time in a steady state. Manufacturing systems that face a constantly changing demand for a changing array of products may never reach a stable equilibrium. Like a surfer balanced on a wave, they must continually adjust themselves in a state of constant transition.
Averages and variances are not enough to understand such an adaptive system. The study of naturally occurring adaptive systems (such as ecosystems, market economies, and various physical and chemical processes) is yielding a new breed of analytical tools that can characterize the dynamics, or quantifiable time-varying behavior, of these systems. Agile manufacturing requires the adaptation and application of these tools to manufacturing systems, first to measure the baseline behavior of current systems, then to model the patterns we observe so that we can test our understanding of how the systems operate, and finally to manage systems for greatest competitive advantage.
The paper has three parts. Section 1 develops the problem of unstable manufacturing systems in more detail, and describes why we need to direct attention to their dynamic analysis. Section 2 illustrates the approach by presenting a simple analysis of data from an actual automotive-like manufacturing plant, using the "time-delay plot," one of the tools of dynamic analysis. Section 3 outlines the broader questions that must be addressed to deliver the promise of this approach.
GA's and Production Scheduling (with Fulkerson) (1994)
Short-term, process-by-process scheduling of the shop floor is seldom effective in practice for several reasons.
Some recent GA literature suggests that these issues are not adequately understood in the research community and that traditional shop floor scheduling is still the subject of active research. GAs must be applied to the most pertinent problems if they are to achieve their promised potential. In the case of production scheduling, the contribution of GAs may be limited by outdated assumptions unwittingly adopted from previous scheduling research. This note urges GA researchers who are interested in manufacturing applications to apply their powerful technology to a view of the production scheduling problem that is more realistic than the traditional one.
Characterizing the Manufacturing Scheduling Problem (1991)
Scheduling a job shop is difficult even for human intelligence. The push toward increased automation and flexibility in manufacturing has led to a number of computerized schemes that address the problem with varying degrees of success. These schemes often have little in common with one another. It is not clear whether they are addressing the same problem or how they should be extended or combined to advance the state of the art in scheduling.
The problem is of more than academic interest. The effective scheduling of a facility reduces its work-in-process inventory (WIP) and increases throughput--effectively increasing the return on investment. Scheduling is also important in enabling faster response to changing customer demands, thus gaining increased market share.
This paper develops a general context for the scheduling problem, as a framework for understanding existing approaches and as a roadmap for future development. We propose a formal definition of a schedule and describe five challenges to the computation of schedules. We then classify existing scheduling strategies under the challenges they address. We suggest new strategies for those challenges that previous approaches do not handle well. The paper's main contribution is not to solve the scheduling problem, but to exhibit its complexity, show that existing techniques address only isolated parts of the problem, and plot a course for further work on a systems approach to scheduling.
Sharpening the focus on intelligent control (with Judd) (1990)
INT. J. COMPUTER INTEGRATED MANUFACTURING, 1990, VOL. 3, NO. 1, l-5
This paper relates the technologies commonly described as ‘intelligent control’ to one another and to the application domain of manufacturing, and situates other papers in this issue of IJCIM in this context. Our presentation has three main parts. First, we analyre the interaction of the three disciplines (control theory, operations research and artificial intelligence) from which intelligent control takes its roots by describing the overall structure of any system that might use intelligent control, and show how the parent disciplines contribute to such a system. Second, we outline new trends in manufacturing and the increasingly complex problems that it confronts, and suggest how intelligent control and its subdisciplines fit into that development. Third, we briefly summarize each paper in this special issue and show where it fits, both in terms of its component technologies and in terms of the application problems that it seeks to solve.
Swarming Pattern Detection in Sensor and Robot Networks (with Brueckner and Odell) (12/03)
2004 American Nuclear Society (ANS) Topical Meeting on Robotics and Remote Systems
Monitoring for radiation (e.g., leak detection or finding smuggled materials) requires managing a dynamic spatio-temporal configuration of sensors. One promising approach is to combine fixed sensors with sensors on robots, and endow the population with the ability to configure themselves and coordinate their actions to create and maintain the required sensor configuration. This paper describes some scenarios where such a capability would be useful, identifies technical issues that need to be addressed, suggests general principles and techniques for dealing with such scenarios, and describes a specific example that we have constructed and tested in a simulation environment.
Swarming Coordination of Multiple UAV's for Collaborative Sensing (with Brueckner and Odell) (9/03)
Presented at the Second 2ND AIAA Unmanned Unlimited Systems Technologies and Operations Aerospace Land and Sea Conference and Workshop & Exhibit, San Diego, CA, 15-18 Sept 2003
Some imaging tasks and modalities (e.g., interferometric SAR) require managing a dynamic spatio-temporal configuration of sensors (whether electro-optic or RF) over a wide area. One promising approach is to mount each sensor on a separate unpiloted vehicle, and endow the population of such vehicles with the ability to con-figure themselves and coordinate their actions to create and maintain the required sensor configuration. This paper describes some scenarios where such a capability would be useful, identifies technical issues that need to be addressed, suggests general principles and techniques that we have found useful in dealing with such scenarios, and describes a specific example that we have constructed and tested in a simulation environment.
Distributed Pheromone-Based Swarming Control of Unmanned Air and Ground Vehicles for RSTA (Sauter, Matthews, Yinger, Robinson, Moody, Riddle) (3/08)
SPIE Defense and Security Conference 2008
The use of unmanned vehicles in Reconnaissance, Surveillance, and Target Acquisition (RSTA) applications has received considerable attention recently. Cooperating land and air vehicles can support multiple sensor modalities providing pervasive and ubiquitous broad area sensor coverage. However coordination of multiple air and land vehicles serving different mission objectives in a dynamic and complex environment is a challenging problem. Swarm intelligence algorithms, inspired by the mechanisms used in natural systems to coordinate the activities of many entities provide a promising alternative to traditional command and control approaches. This paper describes recent advances in a fully distributed digital pheromone algorithm that has demonstrated its effectiveness in managing the complexity of swarming unmanned systems. The results of a recent demonstration at NASA’s Wallops Island of multiple Aerosonde Unmanned Air Vehicles (UAVs) and Pioneer Unmanned Ground Vehicles (UGVs) cooperating in a coordinated RSTA application are discussed. The vehicles were autonomously controlled by the onboard digital pheromone responding to the needs of the automatic target recognition algorithms. UAVs and UGVs controlled by the same pheromone algorithm self-organized to perform total area surveillance, automatic target detection, sensor cueing, and automatic target recognition with no central processing or control and minimal operator input. Complete autonomy adds several safety and fault tolerance requirements which were integrated into the basic pheromone framework. The adaptive algorithms demonstrated the ability to handle some unplanned hardware failures during the demonstration without any human intervention. The paper describes lessons learned and the next steps for this promising technology.
Heterogeneous Unmanned Vehicle Collaborative Control Demonstration (Sauter, Matthews, Yinger, Robinson, Moody) (10/07)
AUVSI Unmanned Systems North America 2007
The use of swarming unmanned vehicles to support target detection and identification has been the subject of several research efforts. Cooperating land and air vehicles can support multiple sensor modalities providing pervasive and ubiquitous broad area sensor coverage. Coordination of air and land vehicles offers a wide range of stand-offs and viewing angles. However swarming systems are inherently diverse, decentralized, distributed, and dynamic making them nearly impossible to control through traditional command and control methods. Research in a class of algorithms based on digital pheromones has demonstrated their effectiveness in managing the complexity of swarming unmanned systems in simulated scenarios. This paper reports on the results of using digital pheromones in an onboard demonstration of unmanned land and air vehicles cooperating in a surveillance and automated target recognition scenario. Aerosonde air vehicles and Pioneer ground robots controlled by an onboard digital pheromone algorithm demonstrated the ability to self-organize and accomplish area surveillance, automatic target detection, sensor cueing, and automatic target recognition with no central processing or control and minimal operator input.
Pheromone Learning for Self-Organizing Agents (with Brueckner, Matthews, and Sauter)(1/2005)
IEEE SMC May 2005.
A central issue in distributed systems engineering is enabling agents with only a local view of their environment to take actions that advance global system objectives. One example of this tension is that individual agents may take actions that consume system resources even when they are not advancing the overall system objectives. Thus, paradoxically, system performance can sometimes improve if individual agents reduce their activity. Agents in such systems need a way to modulate their individual behavior in the light of the system’s state, preferably in a way that does not require centralized control. We illustrate the problem of hyperactive agents in three application domains. We describe a simple, decentralized scheme, inspired by insect pheromones, that enables individual agents to adjust their level of activity as the system operates, and extend this mechanism to provide a general approach for dealing with approaching deadlines. Then we demonstrate the effectiveness of these mechanisms in the example domains.
Performance of Digital Pheromones for Swarming Vehicle Control (with Sauter, Matthews, and Brueckner).
Fourth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'05), Utrecht, Netherlands (accepted).
The use of digital pheromones for controlling and coordinating swarms of unmanned vehicles is studied under various conditions to determine their effectiveness in multiple military scenarios. The study demonstrates the effectiveness of these pheromone algorithms for surveillance, target acquisition, and tracking. The algorithms were demonstrated on hardware platforms and the results from the demonstration are reported.
Self-Organizing MANET Management (with Brueckner) (12/03)
Forthcoming in Serugendo, Karageorgos, Rana, and Zambonelli, editors, Proceedings of the Workshop on Engineering Self-Organising Applications, AAMAS2003.
In recent years, mobile ad-hoc networks (MANETs) have been deployed in various scenarios, but their scalability is severely restricted by the human operators’ ability to configure and manage the network in the face of rapid change of the network structure and demand patterns. In this paper, we present a self-organizing approach to MANET management that follows general principles of engineering swarming applications.
Engineering Swarming Systems (with Brueckner) (09/03)
Bergenti, Gleizes, and Zambonelli, Methodologies and Software Engineering for Agent Systems, Kluwer, 2004, 341-376.
Most multi-agent systems are inspired by classical AI, whose objective was to realize human-level intelligence in a computer. As the field has moved toward multiple agents, there has been a presumption that individual agents still aspire to high-level intelligence. Swarming systems follow an alternative model, inspired more by artificial life than artificial intelligence. The individual agents in these systems may be non-cognitive, but complex, robust cognition emerges from their interactions. This paper defines swarming and the concepts of self-organization and emergence that underlie it. It describes the kinds of problems for which it is well suited, explores why it functions, and outlines some initial principles of an engineering methodology for developing artificial swarming systems.
Digital Pheromones for Autonomous Coordination of Swarming UAV's (with Purcell and O'Connell) (4/02)
Presented at AIAA's First Technical Conference and Workshop on Unmanned Aerospace Vehicles, Systems, and Operations
Modern UAV’s reduce the threat to human operators, but do not decrease the manpower requirements. Each aircraft requires a flight crew of one to three, so deploying large numbers of UAV’s requires committing and coordinating many human warfighters. Insects perform impressive feats of coordination without direct inter-agent coordination, by sensing and depositing pheromones (chemical scent markers) in the environment. We have developed a novel technology for coordinating the movements of multiple UAV’s based on a computational analog of pheromone dynamics. The control logic is simple enough that it can be executed autonomously by a UAV, enabling a single human to monitor an entire swarm of UAV’s. This paper describes the technology, its application to UAV coordination, and the results we have obtained.
Synthetic Pheromone Mechanisms for Coordination of Unmanned Vehicles (with Brueckner and Sauter) (4/02)
Autonomous Agents and Multi-Agent Systems (AAMAS 2002)
Agents guided by synthetic pheromones can imitate the stigmergetic dynamics of insects. The resulting software architecture is well suited to problems such as the control of unmanned robotic vehicles. We introduce the approach, describe the mechanisms we have developed, and summarize the technology's performance in a series of scenarios reflecting military command and control.
Digital Pheromones for Coordination of Unmanned Vehicles (with Brueckner and Sauter).Postproceedings of the Workshop on Environments for Multi-agent Systems (E4MAS 2004), Springer, LNAI 3374.
Agents guided by synthetic pheromones can imitate the stigmergetic dynamics of insects. The resulting software architecture is well suited to problems such as the control of unmanned robotic vehicles. We introduce the approach, describe the mechanisms we have developed, and summarize the technology's performance in a series of scenarios reflecting military command and control.
Evolving Adaptive Pheromone Path Planning Mechanisms (with Sauter, Matthews, and Brueckner) (4/02)
Autonomous Agents and Multi-Agent Systems (AAMAS 2002)
Agents guided by synthetic pheromones can imitate the behavior of insects in tasks such as path planning. These systems are well suited to problems such as path planning for unmanned robotic vehicles. We have developed a model for controlling robotic vehicles in combat missions using synthetic pheromones. In the course of our experimentation, we have identified the need for proper tuning of the algorithms to get the desired behavior. We briefly describe the synthetic pheromone mechanisms for dynamically finding targets and planning safe paths. Genetic algorithms for automatically tuning the behavior of the pheromone equations are described.
Swarming Agents for Distributed Pattern Detection and Classification (with Brueckner) (11/01)
Workshop on Ubiquitous Computing, AAMAS 2002
Swarming agents in networks of physically distributed processing nodes may be used for data acquisition, data fusion, and control applications. We present an architecture for active surveillance systems in which simple mobile agents collectively process real-time data from heterogeneous sources at or near the origin of the data. We motivate the system requirements with the needs of a surveillance system for the early detection of large-scale bioterrorist attacks on a civilian population, but the same architecture is applicable to a wide range of other domains. The pattern detection and classification processes executed by the proposed system emerge from the coordinated activities of agents of two populations in a shared computational environment. Detector agents draw each other’s attention to significant spatio-temporal patterns in the observed data stream. Classifier agents rank the detected patterns according to their respective criterion. The resulting system-level behavior is adaptive, robust, and scalable.
Swarming Distributed Pattern Detection and Classification (with Brueckner).
Postproceedings of the Workshop on Environments for Multi-agent Systems (E4MAS 2004), Springer, LNAI 3374.
Swarming agents in networks of physically distributed processing nodes may be used for data acquisition, data fusion, and control applications. We present an architecture for active surveillance systems in which simple mobile agents collectively process real-time data from heterogeneous sources at or near the origin of the data. We motivate the system requirements with the needs of a surveillance system for the early detection of large-scale bioterrorist attacks on a civilian population, but the same architecture is applicable to a wide range of other domains. The pattern detection and classification processes executed by the proposed system emerge from the coordinated activities of agents of two populations in a shared computational environment. Detector agents draw each other’s attention to significant spatio-temporal patterns in the observed data stream. Classifier agents rank the detected patterns according to their respective criterion. The resulting system-level behavior is adaptive, robust, and scalable.
Tuning Synthetic Pheromones With Evolutionary Computing (with Sauter and Brueckner) (3/01)
Workshop on Evolutionary Computation and Multi-Agent Systems (ECOMAS2001, at GECCO 2001)
Agents guided by synthetic pheromones can imitate the dynamics of insects. These systems are well suited to problems such as the control of unmanned robotic vehicles. We have developed a model for controlling robotic vehicles in air combat missions using synthetic pheromones. In the course of our experimentation, we have identified the need for proper tuning of the algorithms to get acceptable performance. We describe pheromones in natural and synthetic systems, and describe the mechanisms we have developed. The role of evolutionary computing in offline and online tuning is discussed.
Mechanisms and Military Applications for Synthetic Pheromones (with Brueckner, Sauter, and Posdamer) (3/01)
Workshop on Autonomy-Oriented Computation 2001 (at Agents 2001)
Agents guided by synthetic pheromones can imitate the stigmergetic dynamics of insects. The resulting software architecture is well suited to problems such as the control of unmanned robotic vehicles. We introduce the approach, describe the mechanisms we have developed, and summarize the technology's performance in a series of scenarios reflecting military command and control.
Distinguishing Control and Plant Dynamics in Enterprise Modeling (with Brueckner, Sauter, and Matthews).
Proceedings of Symposium on Advances in Enterprise Control.
Two factors can confound the interpretation of an enterprise model. First, the dynamics of the control technology interact in complex ways with those of the plant, and engineers need to be able to distinguish these effects. Second, “mean field” approximations of the behavior of the system may be useful for qualitative examination of the dynamics, but can differ in surprising ways from the behavior that emerges from the interactions of discrete agents. This paper examines these effects in the context of a specific research project applying agent-based control to a military air operations scenario.
Multiple Pheromones for Improved Guidance (with Brueckner).
Proceedings of Symposium on Advances in Enterprise Control.
Synthetic pheromone systems offer great potential for spatial coordination in multi-agent systems. Initial experiments with such a system applied to the control of air operations has identified the concept of local guidance that is critical to designing such a system, and that can be supported by using multiple pheromones with differing characteristics. This paper reviews the basic mechanisms of synthetic pheromones, describes local guidance and how multiple pheromones support it, and outlines design methods to guide system designers in exploiting this mechanism.
Entropy and Self-Organization in Multi-Agent Systems (with Brueckner) (10/00).
Proceedings of Autonomous Agents'01
Emergent self-organization in multi-agent systems appears to contradict the second law of thermodynamics. This paradox has been explained in terms of a coupling between the macro level that hosts self-organization (and an apparent reduction in entropy), and the micro level (where random processes greatly increase entropy). Metaphorically, the micro level serves as an entropy “sink,” permitting overall system entropy to increase while sequestering this increase from the interactions where self-organization is desired. We make this metaphor precise by constructing a simple example of pheromone-based coordination, defining a way to measure the Shannon entropy at the macro (agent) and micro (pheromone) levels, and exhibiting an entropy-based view of the coordination.
Ant-Like Missionaries and Cannibals: Synthetic Pheromones for Distributed Motion Control (with Brueckner) (10/99)
Proceedings of Autonomous Agents 2000
Many applied problems in domains such as military operations, manufacturing, and logistics require that entities change location under certain constraints. These problems are traditionally addressed with centralized control mechanisms, which become bottlenecks and points of vulnerability. More recent multi-agent negotiation schemes enable the entities to maintain the desired constraints among themselves in decentralized fashion. This paper explores a particularly simple form of coordination that replaces central coordination and agent-to-agent communication with interaction through a shared environment. Inspired by pheromone mechanisms in natural insect populations, this method is capable of solving the classical Missionaries and Cannibals movement problem. We illustrate how agents can be programmed to interact using synthetic pheromones, and evaluate the performance of our algorithms for four different levels of pheromone information and two different approaches to constructing the functions by which agents respond to the pheromones.
Case grammar is a model widely used by field linguists for studying actual human languages. It is an extension to the semantic domain of the syntactic "case endings" used by many languages, such as German and ancient Greek and Latin, to mark the role of nouns in sentences (for example, as subject or object). Studies of a wide range of human languages suggest that all human languages share a common set of such semantic cases, though they may mark them in different ways. Thus cases represent a fundamental characteristic of human cognition that can be of great value in engineering systems that must interact with humans.
This paper surveys three agent-based systems in which ITI has used case grammar as an engineering tool at three different levels. It is drawn largely from the full papers referenced in the introduction below. These examples show that case grammar provides an integrating framework for constructing the internal knowledge representation system of a single agent, for identifying the agents that are active in a domain, and for defining an abstract space within which the behaviors of agents can be described.
Section 1 provides a simple introduction to case theory, and explains why it is relevant to engineering. Sections 2, 3, and 4 describe three systems in whose design case grammar has been an important tool.
An Introduction to Speech Acts and Dooley Graphs (2/96)
A useful way to characterize a community of firms for their potential for agile interaction is to focus on the communications between them, and in particular to look at the structure of the conversations in which they engage. Relevant structure may appear at two levels in such conversations: the basic grammar by which they are generated, and characteristics of specific sequences of utterances (e.g., length, branching complexity, etc.). This document develops a domain-independent vocabulary for talking about the utterances among VE members and the possible sequences of such utterances (the "grammar" for a conversation consisting of these utterances) (Section 2). Then it introduces Dooley graphs as a way to characterize a particular sequence of utterances generated by such a grammar (Section 3). Section 4 takes stock of where we are and what might come next.
Visualizing Agent Conversations: Using Enhanced Dooley Graphs for Agent Design and Analysis (8/96)
Proceedings of the 1996 International Conference on Multi-Agent Systems
In the MAS/DAI community, most current work on speech acts focuses on formalizing individual utterances. The next stage will exploit the theory's power to explicate relationships within conversations, or groups of utterances. Computer scientists naturally seek to visualize these relationship in terms of graphs, focusing either on the identities of the individual agents involved or the states through which participating agents move.. This paper introduces an alternative formalism, the Dooley Graph. It reviews the kinds of relations that can exist among individual communicative actions (including both speech acts and non-speech acts), shows the strengths and weaknesses of participant and state graphs, explains the derivation of Dooley Graphs, and suggests their value for designing agents and analyzing the behavior of communities of agents.
A Linguistic Approach to the Problem of Slot Semantics (1989)
Proceedings of the Eleventh Annual Conference of the Cognitive Science Society
Most frame-based knowledge representation (KR) systems have two strange features. First, the concepts represetned by the nodes are nouns rather than vedrbs. Verbal ideas tend to appear mostly in describing roles or slots. thus the systems are asymmetric. Second, and more seriously, the slot names on frames are arbitrary and not defined in the system. Usually no metasystem is given to account for them. Thus the systems are not closed.
Both these features can be avoided by structures inspired by case-based linguistic theories. The basic ideas are that an ontology consiste of separate, parallel lattices of verbal and nominal concepts, and that the slots of concepts in each lattice are defined by reference to the concepts in the other lattice. Slots of verbal concepts are derived from cases, and restricted by nominal concepts. Slots of nominal concepts include conducts (verbal concepts) and derivatives of the slots of verbal concepts.
Our objective in this paper is not to define a new KR language, but to use input from the study of natural cognition (case grammar) to refine technology for artificial cognition.
SYCKL: A Symmetric Closed Knowledge Language (1985)
Frame-based knowledge representation systems are a popular way to store and organize the vast quantities of information that artificially intelligent systems need to do their work. Most current systems, though, have two strange features.
This paper introduces SYCKL-D, the Definintion component of a Symmetric, Closed Knowledge Language.
Proceedings of SASO07
In current information systems, information is passive. People act upon it, either sending it to known destinations or pulling it from known sources. InformANTS makes information active, enabling it to move actively from one user to another. This paper introduces the InformANTS vision and describes one of its major system components, the Information Matching System. Particular emphasis is placed on the distinctive self-organizing processes from which emerge the information exploration and exploitation capabilities of InformANTS.
Dynamic Decentralized Any-Time Hierarchical Clustering (with Rohwer, Belding, Brueckner) (4/06)Hierarchical clustering is used widely to organize data and search for patterns. Previous algorithms assume that the body of data being clustered is fixed while the algorithm runs, and use centralized data representations that make it difficult to scale the process by distributing it across multiple processors. Self-Organizing Data and Search (SODAS), inspired by the decentralized algorithms that ants use to sort their nests, relaxes these constraints. SODAS can maintain a hierarchical structure over a continuously changing collection of leaves, requiring only local computations at the nodes of the hierarchy and thus permitting the system to scale arbitrarily by distributing nodes (and their processing) across multiple computers.
Sift and Sort: Climbing the Semantic Pyramid (with Weinstein, Chiusano, Brueckner) (10/05)Proceedings of ESOA05
Information processing operations in support of intelligence analysis are of two kinds. They may sift relevant data from a larger body, thus reducing its quantity, or sort that data, thus reducing its entropy. These two classes of operation typically alternate with one another, successively shrinking and organizing the available data to make it more accessible and understandable. We term the resulting construct, the "semantic pyramid." We sketch the general structure of this construct, and illustrate two adjacent layers of it that we have implemented in the Ant CAFÉ.
Challenging Old Assumptions in Global Information Management (9/04Sixth ONR/CADRC Decision Support Workshop, Quantico, VA, Sept 8-9, 2004
Many fundamental assumptions in information management are driven by the nature of problems in the business world, and by the kinds of technology that have been available. The distinctive nature of combat, and new technical developments, invalidate some of these assumptions. This paper discusses three of these assumptions:
Agents Swarming in Semantic Spaces to Corroborate Hypotheses (with Weinstein, Chiusano, and Brueckner).
Third International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS'04), Columbia University, NY, 1488-1489.
To anticipate and prevent acts of terrorism, Indications and Warnings analysts try to connect clues gleaned from massive quantities of complex data. Multi-agent approaches to support Indications and Warnings are appropriate because ownership and security issues fragment the data. Furthermore, the massive scale of the data suggests the need for large numbers of agents.
The Ant CAFÉ system uses fine-grained swarming agents to extract and organize textual evidence that corroborates hypotheses about the state of the world. Multiple swarming processes are required, including the clustering of paragraphs, identification of semantic relations in text, and assembly of evidence into structures that instantiate the hypothesis. These processes occur in semantic spaces defined using the WordNet ontology.
This paper provides an overview of an Ant CAFÉ prototype. It describes the system’s architecture, and provides additional detail on the innovative algorithm for evidence assembly. Initial experiments using artificially generated data confirm that a global property that we call “clarity” emerges from agent decisions made in a local, and therefore scalable, manner.
Hypothesis Corroboration in Semantic Spaces with Swarming Agents (with Weinstein, Chiusano, and Brueckner).
Ant Colony Optimization and Swarm Intelligence, 4th International Workshop (ANTS2004). Brussels, Belgium, September 2004.
To anticipate and prevent acts of terrorism, Indications and Warnings analysts try to connect clues gleaned from massive quantities of complex data. Multi-agent approaches to support Indications and Warnings are appropriate because ownership and security issues fragment the data. Furthermore, the massive scale of the data suggests the need for large numbers of agents. This paper presents the architecture and algorithms of our Ant CAFÉ system, which uses fine-grained swarming agents to extract and organize textual evidence that corroborates hypotheses about the state of the world. Multiple swarming processes operating in semantic spaces are required, including the clustering of paragraphs, identification of semantic relations in text, and assembly of evidence into structures that instantiate the hypothesis.<\p>
Hybrid Stigmergic Mechanisms for Information Extraction (with Weinstein, Brueckner, Sauter).
Conference on the Mathematics and Algorithms of Social Insects, Georgia Tech, Dec. 2003.
Instances of stigmergy may be classified by the kinds of changes that agents make in their environments, and by the topological structure of that environment. We are combining stigmergic mechanisms that vary across both dimensions in an information extraction application. Our preliminary experimental results show that these mechanisms can be combined, and that they can enable self-organization even in the absence of the low-dimensional topologies that are ubiquitous in natural systems.
Hypermedia Topologies and User Navigation (11/89)HyperText'89 (Pittsburgh, PA)
One of the major problems confronting users of large hypermedia systems is that of navigation: knowing where one is, where one wants to go, and how to get there from here. This paper contributes to this problem in three steps. First, it articulates a number of navigational strategies that people use in physical (geographical) navigation. Second, it correlates these with various graph topologies, showing how and why appropriately restricting the connectivity of a hyperbase can improve the ability of users to navigate. Third, it analyzes some common hypermedia navigational mechanisms in terms of navigational strategies and graph topology.
Don’t Link Me In: Set Based Hypermedia for Taxonomic Reasoning (12/91)
HyperText'91 (San Antonio,TX)
Hypermedia is often described as nodes of information with links between them, suggesting the conceptual model of a graph. A broader definition is a system of nodes of information through which people can move nonlinearly. Such a definition, while including graph-based hypermedia, also allows alternative implementations. This paper illustrates the need for alternative models by exhibiting a particular reasoning task for which navigating among nodes by way of explicit links is less cffcctive than an alternative model of intersecting sets of nodes. The task is taxonomic reasoning, a particular kind of reasoning task that deals with the comparison and classification of highly similar nodes, in which an analyst viewing one node thinks not in terms of linking it to another node, but of including it in or excluding it from a set of related nodes.
This paper discusses this kind of reasoning and describes HyperSet, a set-based hypermedia system designed to support it. It compares HyperSet with other tools that support taxonomic reasoning, discusses the formal and implementational relationships between graph-based and set-based hypermedia, and defines the features that are required in a hybrid system that can concurrently support both set and graph manipulations.
Hypercubes Grow on Trees (and Other Observations from the Land of Hypersets) (11/93)
HyperText'93 (Seattle, WA)
Much of the power of hypermedia comes from the development of techniques for information management that closely match natural cognitive processes. HyperSet, a hypermedia environment tailored for taxonomic reasoning [Parunak 911, is an example of this philosophy. People perform taxonomic reasoning when they classify, store, and retrieve a number of similar information objects (such as biological specimens, or linguistic constructions, or research projects). The process is essentially set-based. The user sorts objects into sets based on their characteristics; looks together at mcmbcrs of a single set to search for correlations or discernible subsets among them; examines the different sets of which one item is a member to see whether there are relations among them; and generates new sets from old ones.
Two years of experience in using HyperSet has led to a cleeper understanding of the patterns and processes of taxonomic reasoning and the kind of computer methods that can effectively support it. This paper reports on three of these insights:
ISA-Tech '98 (Houston, TX)
The growth of network technology is making it possible to extend control techniques beyond the individual factory and even the single company. Today one can conceive of on-line control strategies that embrace a large segment of an extended enterprise, such as a supply network. An initial step in developing enterprise-wide control methods is modeling the dynamical behavior of the system to be controlled. This paper reports some preliminary results from an agent-based model of a simple supply network, together with some validating analyses of operating data from supply chains in automotive and electronics assembly. Then it discusses the benefits of agent-based models in comparison with more traditional differential equation models of system behavior at the enterprise level.
Technologies for Virtual Enterprises (1/97)
Manufacturing strategists have proposed the Agile Virtual Enterprise (AVE) as a mechanism for enabling American industry to achieve increased agility (the ability to thrive on frequent and unexpected change). An Agile Virtual Enterprise is a rapidly configured, multi-disciplinary network of firms organized to meet a window of opportunity to design and produce a specific product. It is "virtual" because it relaxes the conventional restrictions that an enterprise be a single legal entity, headquartered in a single place, with close synchronization among its various functions. A few decades ago, AVE's were neither necessary competitively nor feasible technically. Today, advances in computing and telecommunications technology are leading many firms to adopt aspects of the AVE vision, thus pressuring their competitors to follow suit and generating the market demand for AVE technologies. This paper outlines the business and technical strategy for advancing AVE's, then describes the technologies that support these strategies, and finally reviews the benefits that AVE's offer to the US.
Forthcoming in Weyns and Uhrmacher, Agents, Simulation, and Applications
The Polyagent is a new modeling construct that represents each entity in the domain by a set of agents. A single persistent avatar maintains the system’s overall model of the entity in question, and generates a stream of transient ghosts to explore various issues of interest to the agent. These ghosts may be applied in a variety of ways. We have used them extensively to explore alternative futures that the avatar may follow, but they can also be used to evaluate plan structures, compare the usefulness of alternative organizations of documents for retrieval by different analysts, or perform other combinatorially challenging domains. A common thread behind various applications of polyagents is that the ghosts explore different "if-then" scenarios that guide the decisions made by their avatar. Each ghost explores a possible trajectory for the avatar, which then chooses its behavior based on the experiences of its ghosts.
Understanding Collective Cognitive Convergence (with Belding, Hilscher, and Brueckner)Proceedings of MABS 2008
When a set of people interact frequently with one another, they often grow to think more and more along the same lines, a phenomenon we call "collective cognitive convergence" (C3). We discuss instances of C3and why it is advantageous or disadvantageous; review previous work in sociology, computational social science, and evolutionary biology that sheds light on C3; define a computational model for the convergence process and quantitative metrics that can be used to study it; report on experiments with this model and metric; and suggest how the insights from this model can inspire techniques for managing C3.
Modeling and Managing Collective Cognitive Convergence (with Belding, Brueckner, and Hilscher)AAMAS08 pp. 1505-1508
When the same set of people interact frequently with one another, they grow to think more and more along the same lines, a phenomenon we call "collective cognitive convergence" (C3). In this paper, we discuss instances of this phenomenon and why it is advantageous or disadvantageous; review previous work in sociology, computational social science, and evolutionary biology that sheds light on C3; define a computational model for the convergence process and quantitative metrics that can be used to study it; report on experiments with this model and metric; and suggest how the insights from this model can inspire techniques for managing C3.
Emergent Behavior in Modeling (with Belding, Brueckner, and Sauter)Forthcoming in Alexander Kott and Steve Morse, Advanced Campaign Planning
MAS Combat SimulationForthcoming in Michal Pechoucek, Simon G. Thompson, and Holger Voos, AAMAS Technology for Military and Security Applications (Springer).
Multi-agent systems offer a new stage in the evolution of combat simulation. Originally, warfighters simulated combat manually to explore alternatives and plan their campaigns. The first applications of computers to combat simulation used algorithms that aggregated the warriors on each side, such as differential equations or game theory, effectively modeling the entire battlespace with a single process. Entity-based models such as OOS and Combat XXI assign a single agent to each entity, following the standard MAS agenda. A new modeling construct, the polyagent, takes this trend one step further, and uses several agents to model each construct. This approach addresses several challenges that face the traditional MAS approach, including fitting, closure, dynamism, and singularity. This chapter surveys the history of combat modeling, gives two examples of polyagent systems (one for planning, the other for adversarial prediction), and discusses how this construct addresses the challenges.
Real-Time Agent Characterization and Prediction (with Brueckner, Matthews, Sauter, Brophy)(2/06)AAMAS 2007 (Industry Track)
Reasoning about agents that we observe in the world is challenging. Our available information is often limited to observations of the agent’s external behavior in the past and present. To understand these actions, we need to deduce the agent’s internal state, which includes not only rational elements (such as intentions and plans), but also emotive ones (such as fear). In addition, we often want to predict the agent’s future actions, which are constrained not only by these inward characteristics, but also by the dynamics of the agent’s interaction with its environment. BEE (Behavior Evolution and Extrapolation) uses a faster-than-real-time agent-based model of the environment to characterize agents’ internal state by evolution against observed behavior, and then predict their future behavior, taking into account the dynamics of their interaction with the environment.
E Pluribus Unum: Polyagent and Delegate MAS Architectures (with Brueckner, Weyns, Holvoet, Verstraete, and Valckenaers) (5/07)MABS07
For the past few years, our research groups have independently been developing systems in which a multi-agent system (typically of lightweight agents) provides some functionality in service of a higher-level system, and often of a higher-level agent in that system. This paper compares our approaches to develop a more generic architecture of which our individual approaches are special cases. We summarize our existing systems, describe this architecture and the characteristics of problems for which it is attractive, and outline an agenda for further research in this area.
Concurrent Modeling of Alternative Worlds with Polyagents (with Brueckner) (5/06)AAMAS 2006
Agent-based modeling is a powerful tool for systems modeling. Instantiating each domain entity with an agent captures many aspects of system dynamics and interactions that other modeling techniques do not. However, an entity’s agent can execute only one trajectory per run, and does not sample the alternative trajectories accessible to the entity in the evolution of a realistic system. Averaging over multiple runs does not capture the range of individual interactions involved. We address these problems with a new modeling entity, the polyagent, which represents each entity with a single persistent avatar supported by a swarm of transient ghosts. Each ghost interacts with the ghosts of other avatars through digital pheromone fields, capturing a wide range of alternative trajectories in a single run that can proceed faster than real time.
Modeling Uncertain Domains with Polyagents (with Brueckner) (6/06)AAMAS 2006
Agent-based modeling is a powerful tool for systems modeling. Instantiating each domain entity with an agent permits us to capture many aspects of system dynamics and interactions that other modeling techniques do not support. However, the software agent representing an entity can execute only one trajectory in each run of the system, and so does not capture the alternative trajectories accessible to the entity in the evolution of any realistic system. Averaging over multiple runs still does not capture the range of individual interactions involved. We have addressed these problems with a new modeling entity, the polyagent, which represents each entity with a single persistent avatar supported by a swarm of transient ghosts. Each ghost interacts with the ghosts of all other avatars through digital pheromone fields, capturing a wide range of alternative trajectories in a single run of the system that can proceed faster than real time for many reasonable domains. We articulate this modeling concept, give examples from actual applications, and discuss directions for further research.
Real-Time Evolutionary Agent Characterization and Prediction (with Brueckner, Matthews, Sauter, Brophy)(10/05)Submitted to AAMAS 2006
Reasoning about agents that we observe in the world is challenging. Our available information is often limited to observations of the agent’s external behavior in the past and present. To understand these actions, we need to deduce the agent’s internal state, which includes not only rational elements (such as intentions and plans), but also emotive ones (such as fear). In addition, we often want to predict the agent’s future actions, which are constrained not only by these inward characteristics, but also by the dynamics of the agent’s interaction with its environment. BEE (Behavior Evolution and Extrapolation) uses a faster-than-real-time agentbased model of the environment to characterize agents’ internal state by evolution against observed behavior, and then predict their future behavior, taking into account the dynamics of their interaction with the environment.
A Model of Emotions for Situated Agents (with Bisson, Brueckner, Matthews, Sauter) (10/05)Submitted to AAMAS 2006
Emotion is an essential element of human behavior. Particularly in stressful situations such as combat, it is at least as important as ra