Diversity in Agent Organizations

The Cosmic Command, obviously no longer able to supervise every assignment on an individual basis when there were literally trillions of matters in its charge, had switched over to a random system. The assumption would be that every document, circulating endlessly from desk to desk, must eventually hit upon the right one. A time-consuming procedure, perhaps, but one that would never fail. --- Stanislaw Lem

Lem's cynical description of the limits of bureaucracy is a humbling reminder of the difficulties associated with large scale agent-based systems. As with many researchers in the software-agent community, we have been involved with the detailed mechanics of agent construction and interaction. But that's not what this paper is about.

In this paper, we consider the issues involved in developing effective collaborating-agent organizations. We assume that we have been supplied with software agents that are capable of working together to achieve great things. The important question is (Lem's description notwithstanding): How do we get them to work together to accomplish those great things?

The Competent Agent

There must be nearly as many definitions of software agents as there are implemented agents [1] and we won't add to that total. Instead, we will assume a level of agent competency sufficient to allow them to work together to perform activities that are beyond the ability of a single agent.

A competent agent possesses the ability to communicate effectively with other competent agents, to perform useful tasks, to accept or infer instructions or requests regarding its activities, and to use these to shape its autonomous activity decisions. Competent agents are the building blocks of agent societies and organizations.

A competent software agent falls somewhere between a simple event-triggered program and one with human collaborative abilities. Researchers are hard at work advancing agent capabilities towards the latter side of the spectrum. Humans, by definition, are competent agents; and, therefore, much of this paper pertains to activities involving both people and software agents as well as those consisting entirely of software agents.

Societies and Organizations

Competent agents that share common communication skills, viewpoints, and purposes form an agent society. An agent society is a very robust and flexible entity. Agents within a society can interact with one another (due to common language), identify the abilities and needs of each other (due to common viewpoints), and request or perform activities on behalf of others (due to common goals). Societal agents can determine that activities need to be performed and enlist other agents to help out.

The flexibility of an agent society comes at a cost, however: a substantial inefficiency in handling ongoing or repetitive activities. This cost begins with the problem of finding appropriate agents for an activity and continues through planning and executing the activity. The flexibility of an agent society starting at square one incurs the cost of always starting at square one.

Agent societies provide a basis for developing more structured agent organizations. What is an agent organization? To paraphrase Galbraith [2], an agent organization is:

1. composed of competent agents,
2. working together to achieve a shared purpose
3. through a division of labor,
4. integrated by decision processes
5. continuously through time.

An organization consists of patterns of behavior and interaction that are relatively stable and change slowly over time.

Market economies

An example of a societal mechanism for coordinating agent-based systems is the use of market-based techniques. A market-based approach augments an agent society with a well-defined, mutually accepted valuation for allocating resources and agent activities. In applying market techniques to the design process, for example, Wellman suggests the application of general equilibrium theory to a class of distributed configuration-design problems using the WALRAS computational market-price system [3]. In this approach, the artifacts, attributes, constraints, functions, and utilities of the design problem are mapped to concepts in computational economies of producer and consumer agents. These agents then iteratively bid so as to maximize utility or profit.

In the configuration-design domain, the market approach is limited in that only a small subclass of potential problems can be represented. It is attractive in those cases, however, because it is based on heavily researched economic theories that provide a solid foundation for analysis of decentralized coordination and global evaluation of local search. Extensions, such as the addition of constraint-reasoning techniques could potentially expand the set of solvable problems while maintaining much of the power of the approach.

A market economy, though, is a societal mechanism, not an organizational one, with ongoing transaction costs associated with repetitive activities. Techniques such as maintaining pricing histories can reduce these costs, but they still remain. Furthermore, issues such as initial allocation of wealth, transfer of wealth to new agents, concentration of wealth, predatory pricing, coalition, and antitrust all apply to large-scale market approaches. The approach is highly opaque from a management perspective; it is difficult to reason about because much of the contextual information is lost when it is mapped into utility values. At some level, the complexity of managing a market economy appears to be very small given that utility of solutions can be handily represented as a number. However, on the local level, the types of information and the degree of work that go into determining what that number should be are no less than if they were visible at the management level. Furthermore, the context of decisions is not available to permit better-informed decisions across the space of the agents.

Societal mechanisms, such as that implemented in a market economy, permit the emergence of some degree of structure in situations where there is a need for agents to be completely self-motivated and fully autonomous. However, full autonomy is not always appropriate and, in these situations, a designed organization, where agents give up some degree of self-motivation and autonomy, will outperform naturally occurring societal mechanisms.

Natural Versus Designed Organizations

Sufficiently competent agents have the ability to organize themselves naturally. If agents have similar views of what needs to be achieved, they will naturally specialize societal interactions into organizational patterns of behavior. This is a direct result of the need to coordinate the work divided among the agents. In other words, organizing is a basic activity of competent agents.

If agent organizations emerge naturally, why should we bother to design them? The standard answer for human organizations is that properly designed organizations perform better than those that emerge naturally. It is reasonable to expect this answer to hold for agent organizations as well.

Note that organization design can be performed by the agents themselves. However, such organization self-design is an explicit expert task undertaken by the agents (or a subset of agents) rather than the implicit result of societal specialization. Organization self-design is an important research area (see [4] and [5] for early discussions in this area) but in this paper we focus on organization design performed by the implementors of agent-based systems.

Organizational structure is distinct from explicit agent coordination. Organizational roles and responsibilities represent general long-term guidelines that must be elaborated and revised by the agents into the specific activities that they will perform within the context of the dynamic environment. As noted by March and Simon: ``One of the very important processes in organizations is the elaboration of this set of activities, and the determination of which precise activities are to be performed at which precise times and places'' [6].

Explicit coordination, on the other hand, involves specific short-term agreements among agents to perform specific activities for specific periods of time. Much of the behavior of agents within an organization results from autonomous decisions made in the context of organizational guidelines supported by explicit coordination of short-term activities.

Organization Diversity

An important aspect of organization design is choosing the appropriate organizational structure for the tasks being performed. In this section, we highlight the range of organization designs and their applicability.

Simple agents, simple tasks, simple organizations

Early agent architectures involved small numbers of relatively simple agents performing simple, self-contained tasks. These organizations, if they exist at all, provide little structure beyond the societal behavior of agents. This is not a pejorative analysis, as a simple organization is the correct design for such situations; a more complex organization would add unnecessary overhead and complexity to an effective structure.

Workflow organizations: the assembly line of information processing

Workflow organizations involve agents that perform repeated tasks with stable relationships to the tasks being performed by other agents. Unlike the transient, self-contained nature of the tasks in simple agent organizations, workflow tasks are highly interdependent. Agents receive information from other agents, perform their activities on that information, and pass the results on to other agents.

As with human organizations, workflow provides prespecified organizational relationships. These relationships represent agents and their roles and privileges, information flows, and routing criteria. The advantages are twofold: (1) the repetitive nature of the activities allows the relationship among the agents to be identified once (rather than redone time and again); and (2) the progress of the organization can be monitored by tracing the flow of information through the workflow procedure.

Workflow is the explicit representation of division of labor. It provides for the implementation of a wide range of organization forms, classical and modern. These include horizontal and vertical division of labor, line-staff models, departmentalization, and matrix organizations. In stable organizational settings, workflow organizations provide high efficiency and accountability. We are currently applying workflow approaches to portions of agent-based design and manufacturing applications. These activities are described at the end of the paper.

Workflow in agent organizations provides organizational guidance to the individual agents and helps to define the role of the agent in achieving some set of organizational goals. It does not, however, provide detailed instruction about how to achieve those goals: agents in a workflow organization still must decide how best to carry out their predefined responsibilities, how to prioritize activities under heavy demands, and how to prioritize activities associated with multiple workflows and, possibly, individual goals. As with people, the roles of software agents may involve multiple workflows.

Collaborative organizations

There are organizational activities that do not fit the workflow model. These activities are characterized by highly interdependent and often iterative tasks with unknown relationships among them. Examples include crisis management, innovative design, allocation of scarce resources, and other highly collaborative group problem-solving activities.

In human organizations these activities are often handled by brainstorming sessions---in the board room, in departmental meetings, telephone conferences, and so on. The underlying technique is a freewheeling style of information exchange and opportunistic generation, exploration, and evaluation of alternatives using the expertise of each participant.

Workflow does not apply to these situations, as the dynamic relationships among agents cannot be scripted. Instead, the computational equivalent of the group discussion setting must be provided. Agents in the collaborative organization must be able to freely volunteer information, as unshared information can result in missed opportunity. Agents must be able to recognize when another agent enables them to contribute to a solution.

Collaborative organization is expensive. Collaborating agents spend much of their time evaluating the contributions of other agents, incorporating the useful aspects of contributions into new suggestions, and complaining about negative implications. As with human sessions, it is easy to lose focus and stray into unproductive activities. Effective collaborative organization requires ongoing control of the dynamic activities: a moderator agent to keep everyone on track. Through collaboration, however, results can be obtained that are beyond the expertise of individual agents---results that would not have been developed in a more structured workflow setting.

Collaborative activities are not new to human organizations; but where they were formerly applied only at the highest points in corporate organizations, they are now beginning to be used both horizontally across levels and vertically through multiple levels. Recent evidence suggests that it is possible for firms to improve quality and productivity by incorporating rank-and-file workers in decision-making processes.

As with workflow structures, we are applying collaborative-integration technology to agent-based applications. We will highlight these efforts shortly.

The enterprise

Corporate organization charts notwithstanding, large enterprises consist of multiple organization designs: simple self-contained activities, as well as workflow and collaborative forms. As agent-based technology is applied to enterprise activities, we must consider what activities agents are to perform and how those activities are to be integrated with the activities of other agents, people, and physical resources.

Diversity in Organizational Architecture

Given an organization design, there must be a mechanism to implement it, both within each agent and in the agent-organization architecture. In this section we explore the range of organizational architectures that are used in agent systems.

Uniform agents

Early multi-agent systems involved relatively uniform agents (Figure 1). These agents consisted of interaction capabilities for communicating with other agents, local decision-making capabilities for controlling the activities of the agent and the communications with other agents, and task-level capabilities for performing the work of the agent. Differences among agents in this architectural structure, if they exist at all, are in the task-level capabilities.

A uniform-agent architecture is appealing. A single computational framework is developed for an agent and then replicated as needed. Each agent possesses the same social abilities as every other agent.

Figure 1: A Uniform Agent Architecture

Federated architectures

Experience with uniform-agent architectures indicated that it was expensive for each agent to duplicate the activities associated with finding appropriate agents with which to interact. This led to the development of federated agent architectures, such as that used in the Palo Alto Collaborative Testbed [7].

In a federated architecture (Figure 2), the basic approach involves developing specialized agents whose organizational role is to handle the agent matching problem. This role has been realized in several different ways: in a single server agent or decentralized in multiple matchmakers, brokers, or other facilitators. The facilitators represent a layer of diversity in the organization, providing a connectivity and routing layer, in addition to the task level represented by all other agents. Facilitators collect information about the needs, services, and capabilities of agents in the environment and match agents with needs to agents capable of assisting with those needs. The matching process can take several forms, including forwarding messages to appropriate agents or establishing direct links between the sending and receiving agents [8].

Figure 2: A Federated Agent Architecture

How do federated architectures affect the architecture of individual agents? Since general agents no longer need to perform their own matchmaking, those capabilities can be eliminated. Similarly, the specialization of the matchmaking agent encourages the creation of additional capabilities tailored to matchmaking activities. For example, more historical information about the performance of individual agents could be kept and used in future decisions. Matchmaker agents, with their unique view of recent agent activities, could be a source of diagnostic information for organizational performance. The result of this specialization is that the implementation details of the matchmaker agent may become quite different from other agents.

The federation model provides greater efficiency than a completely uniform multi-agent system, since task-level agents do not need to know about all the agents and their capabilities. However, it recognizes only a single type of organizational diversity: that of the facilitator. There are clearly a number of other potential specializations that contribute to organizational effectiveness in appropriate situations.

Beyond the federation

Specialization of the agent-matching task is only a single example of organizational specialization. What about other organizational activities? For example, the goal of a matchmaker is to get the proper agents in contact with each other and then to step out of the way. This is appropriate when the duration of the tasks is fairly short and the number of agents closely interacting is small.

As with human organizations, however, there are activities involving a larger number of participants and a longer duration that need ongoing management. In this situation, rather than have all agents mutually manage their activities, manager agents can undertake the specialized responsibility for coordinating and monitoring the high-level ongoing activities of a group or project. Manager agents would implement the tasks associated with organizational planning, coordination and monitoring of the group, taking a more organizationally-centered view of the situation than that perceived by individual members. In [9], Stafford Beer discusses hierarchy in biological and managed systems. It is interesting to note that Beer discusses language within an organization, suggesting that diversity in agent languages and ontologies may be required based upon the agent's level in the organizational structure as well as in domain-level competencies:

``... our enquiry suggests that the role of the `higher' level is to express a perception of the scene observed by the `lower' level, that is actually inaccessible to this `lower' level... Moveover: the `higher' level has a language to talk which is of a different logical order from the language of the `lower' level.''

Despite the organizational perspective of the manager(s), however, the details of performing activities that are required of a particular agent within the group and balancing these activities with commitments to other groups and projects is left to the individual agents. The goal is to balance the experience and stability captured by the organizational guidelines with the autonomy and vitality of individual agents.

In addition to specialization along managerial lines, agents can also be used to address issues related to organizational memory. What should each agent remember about what it has done? What should it remember about what it has heard? Who should decide? When should past items be forgotten? One approach is to let each agent decide. However, there are several problems with this approach. First, what if no agent realizes that a piece of information is important? Information is expensive to retain and, if a given communication does not appear to be relevant to the activities of an agent, it will not be retained. Second, information that does appear to be important is likely to be retained by many agents, even if they are not actively using it.

An effective solution to these problems is to provide specialized information repositories shared by the agents; that is, libraries where important information is retained. As with matchmaking and management, the activities associated with maintaining the library can be assigned to specialized librarian agents that implement organizational policies concerning information availability and retention.

Human organizations present examples of many other specialized agents whose responsibilities involve supporting other participants in the direct activities of the organization. Comptrollers, ombudspersons, and administrative assistants are but a few that come to mind. As with federated architectures, the basic idea is to transfer activities formerly performed by each agent to a specialized agent.

Perhaps the greatest range of diversity in human organizations is in the level of abstraction at which they work on tasks. At the least abstract end of the range are workers whose jobs primarily involve interaction with physical artifacts. At the most abstract end are workers who deal primarily with setting and planning for long-range goals. In between are some number of layers that progressively move from sensing and manipulation to high-level planning.

This same range of abstraction will exist in multi-agent systems as they become more complex and include more diverse agents (Figure 3). It is easy to envision systems that include sensors and effectors at one level, with one or more levels of intermediate data fusion, integration, and planning, and one or more levels of strategic organizational decision making. In such a rich and varied organization, there will be a number of specialized roles. Facilitators will be needed to ensure that agents are able to get the information and services they need; librarians will be needed to ensure that important information is retained and made readily available; managers (perhaps even an occasional CEO-agent) will be needed to plan and monitor larger-scale, ongoing activities; user-interface agents will be needed to keep people involved; and robotic manipulators will be needed to physically interact with the external environment. The role that each agent plays, the tools and resources that it controls, and the types of interactions it can perform all influence both the structure of the organization and the structure of the agent itself.

Figure 3: A Highly Specialized Agent Architecture

Agent Diversity

It is entertaining to speculate what Microsoft might be like if every employee were a Bill Gates. Of course, this is not an option for human organizations, but it is entirely feasible for software agent organizations. The important question is: Would this be a good idea? More generally, is it a good idea to develop software agents that can perform any and all activities in the organization?

This is an area where traditional organization design provides little guidance. Human organizations are designed to maximize the use of scarce and expensive capabilities. They are also designed to accommodate the emotional and motivational needs of people. Microsoft would probably not survive with multiple Bill Gates, even if they could be found, and even if they were able and willing to do whatever work was required.

The ease of replicating software agents, and of eliminating them when they are not needed, presents organizational opportunities and challenges not considered by traditional organizational designers. What would Microsoft be like if every employee possessed a full range of abilities? How might its organization change? Would it be more productive, responsive, innovative? What if every worker on the General Motors assembly line were also an expert process engineer, materials specialist, toolmaker, and inventor? Would this result in better ways of assembling cars, better designs, better quality? And, significantly, what level of resources would be required?

The need to organize software agents opens new areas of research in organization design. Just as the designers of agent-based systems can learn a great deal from organization designers, agent-based systems provide an unprecedented opportunity to explore theories of organization. What aspects of current organizational-design experience are based on the information-theoretic capabilities of organizational entities as opposed to being a result of our human needs and limitations? How different are the design principles for purely software-agent organizations versus mixed human and software organizations? To date, separating information-theoretic aspects from human ones has not been possible or relevant. Both aspects are part of the human package. Pure software-agent organizations remove the human aspects of organizational behavior. Therefore, identifying the purely information-theoretic organization guidelines is important in building effective software-agent organizations.

Capable software agents meet the real world

Even with clonable, expendable, self-motivated software agents, the resource bounds of the real world still apply. There are limits to the computational resources provided for agents. When agent computations exceed these bounds, organizational decisions need to be made (creating more agents and letting them fight for resources is not an ideal way of handling this situation).

Agents whose activities involve non-computational resources must recognize the constraints imposed upon them from the external world (since, for example, we can't clone another assembly line). Nowhere is this more clear than in limits to the interfaces to human participants. A major problem facing many mixed systems today is the overwhelming information overload faced by human participants. Too many user-interface agents vying for human attention will certainly not further the goal of creating effective organizational behavior.

Implementation Diversity

How should we implement competent organizational agents? Should we develop a standard agent architecture, or should we custom build each agent based on its anticipated organizational responsibilities?

Creating a standard architecture for capable agents is appealing from a software-development perspective: write one Renaissance agent, and deploy it everywhere. Task-level agent specialization, however, does not support the Renaissance agent model. Aside from basic communication and autonomous control functions, a robotics-controller agent has little in common with a manager or librarian agent for example.

What is needed is a component-based approach to agent construction from which the capabilities needed by an individual agent are assembled. Does the agent require substantial scheduling capabilities; a rapid associative memory; high-bandwidth communication; high-speed computation; special interfaces to tools, people, and legacy applications? If we are to economically deliver large-scale agent organizations, we must share more than basic agent interaction facilities.

We have been developing a component-based agent architecture called AgentExchange for implementing organizational agents. AgentExchange provides a standard set of capabilities that enable agents to exchange messages across machines and platforms and to react to events in the environment such as the creation and completion of tasks and the receipt of messages. Each agent has the ability to prioritize, schedule, and execute its own activities and to send messages to other agents. AgentExchange also supports the sharing of common infrastructure components among agents executing on the same host machine.

AgentExchange components have been developed that allow agents to primitively coordinate their activities with other agents. Facilities have also been developed for specifying and implementing workflow organizations. Work is underway to provide additional coordination components [10].

AgentExchange agents are being developed and tested in an agent-based architecture that provides partially automated support to an Integrated Product Team (IPT). This project, MADEsmart, is a part of the DARPA Rapid Design and Optimization (RaDEO) Program at Boeing Defense & Space Group, Helicopters Division [11]. MADEsmart addresses the development of a rich set of computational agents that support and interact with humans in a large-scale concurrent-engineering environment. Figure 4 shows the basic MADEsmart framework running on two hosts; however, there is no restriction on the actual number of hosts that can simultaneously run the framework.

Figure 4: The Basic MADEsmart Framework

Design engineering is a complex task that has evolved over many years. Much of the process of design engineering within a specific company has been captured and represented to some degree in relatively static workflow-like specifications. Likewise, much of the history of design solutions is captured in the representations of past designs. Although not always resulting in either optimal processes or optimal designs, these specifications represent a form of corporate memory that avoids the need to start afresh with every design, both in terms of design knowledge and in the organizational activities needed to achieve a design.

As with most large, well-established companies, the preferred organization and process flow for design at Boeing is relatively unchanging. Project managers generally assume responsibility for planning tasks and subtasks, assigning tasks to particular agents, and monitoring the progress of a process. In order to support this existing hierarchical workflow structure, MADEsmart employs a Task Structure Specification Tool (TSST). TSST permits a human agent to graphically specify the coordination and scheduling relationships among subtasks (Figure 5) and to impose these relationships in an imperative manner (rather than asking an agent if it is willing to commit to a particular activity, the agent is told that it should do that activity; how it accomplishes the activity is, however, its own responsibility).

Figure 5: The Task Structure Specification Tool

TSST enables specification of workflow and captures the existing organizational principles that enable Boeing to avoid starting from first principles in process and solution each time a new design begins. However, strict adherence to static representations of process and solution does not provide the flexibility needed to react to the exceptions that inevitably occur in large-scale processes. Nor does it bode well for competitive advantage, particularly as the external environment is changing and new tools, methods, and policies are implemented. Therefore, MADEsmart is exploring a hybrid approach to supporting cross-functional work teams, combining workflow structures with more collaborative organization [12]. This hybrid approach takes advantage of organizational guidelines and historically derived information to create initial task/role assignments and to effectively organize the resources available for a project. However, it also uses reactive mechanisms and competent local agents to provide the flexibility to cope with a rich, varied, and dynamic environment. Although the work is still too preliminary to evaluate empirically, the scope of the project is large enough that it will provide a rigorous test environment for the hybrid architecture.

Principles of Agent Organizations

Organization design is an important aspect of large-scale agent-based systems. In this paper, we described the need for organizational diversity at two levels: (1) in the structure of organizations and (2) in the functional behavior (and structure) of the agents themselves. We also highlighted our initial experience in using these ideas.

Although current agent-based systems are at best primitive organizations, the substantial agent-based research that has occurred in the last several years is bringing these systems to the point where organization will matter. As the competency of individual agents improves and larger agent-based systems are developed, consideration of organization structure and its implementation will become increasingly important to the success of these systems. With this in mind, we conclude with a set of principles that prescribe the degree of organization required within a group of agents. These principles are derived from the traditional principles of organizational design and from our experiences with the development of collaborative agents. As noted earlier, support for organizational structure within an agent-based system can and should vary according to the needs of the particular system: no one organization is right for every situation. The principles are as follows:

• The larger the number of agents, the more important organization becomes.
• The longer the duration of agent activities, the more important organization becomes.
• The more repetitive the activities are, the more important organization becomes.
• The more the activities require shared resources, the more important organization becomes.
• The more collaborative the activities are, the more important organization becomes.
• The more specialized agents are, the more important organization becomes.
• The less capable agents are, the more important organization becomes.
• The less slack resources are available, the more important organization becomes.

As agent-based systems become more widespread and complex, designed organization will become an important aspect of effective system performance. In our work, we are just reaching the point where organization design makes a difference. Soon it may become the critical difference.

References