AGENT-BASED PLANNING AND SCHEDULING SYSTEMS
William J. Wolfe
Principal Investigator
University of Colorado at Denver (UCD)
Department of Computer Science and Engineering
wwolfe@cse.cudenver.colorado.edu

In Collaboration with:
Hughes Information Technology Corporation (HITC)
Aurora, Colorado
Research Grant #SG-258799SJP

HITC Research Team:
S. E. Sorensen, D. M. Romano, A. Ficker

UCD Research Assistants:
R. Sayre, J. P. Bolles, M. Emsermann

Abstract
"Intelligent agent" is one of the hottest concepts in software development today. The application of agents to the World Wide Web has produced a style of software engineering that threatens to radically alter existing methods. In this report we evaluate the various uses of agents (both real and imagined), and integrate the concept into a comprehensive planning and scheduling architecture. We review the literature in three categories: AI Agents, Planning Agents, and Control Agents. We provide examples of agents, and quote extensively from the literature. This report helps centralize the important agent issues, and helps the reader understand the many possible meanings of "agent". We are witnessing an explosion of agent-related technology, and the agent-concept will dramatically alter the future of software engineering. Consequently, current planning systems should be designed with agents in mind.

TABLE OF CONTENTS

A. Advanced Planning and Scheduling Systems
B. What is an "Agent"?
B.1. Artificial Intelligence Agents
B.1.1 An AI Agent Example
B.2. Planning Agents
B.3. Control Agents
C. A Distributed Planning System Architecture
D. Further Agent Examples
D.1. Micro-Agents
D.1.1. Scenario #1 - Reactive
D.1.2. Scenario #2 - Progressive Refinement
D.1.3. Scenario #3 - Optimization
D.2. Macro-Agents
REFERENCES

A. Advanced Planning and Scheduling Systems: We are interested in planning and scheduling systems applicable to complex domains such as space resources (e.g.: satellites), factories, large facilities, and transportation systems. Planning and scheduling, in our view, is the management of the assignment of jobs to resources over a continuously rolling horizon of time periods. The problem is complicated by:

dynamic operational environments:

many geographically distributed resources:

rapid and frequent technological advances:

The planning system must produce good schedules at any point in time, and be flexible enough to allow asynchronous inputs from many geographically dispersed users and managers. Not only must the system be effective in a dynamic, distributed, environment, it must also survive a continuous onslaught of technological advances. These requirements lead to a system that must include:

a well developed communications network:

common/sharable components (hardware and software):

autonomy:

We focus on the software architecture side of these requirements, but we acknowledge that advances in hardware can play an important roll (especially in the area of high speed, broad bandwidth, communications systems). Before we describe our agent-based approach to planning and scheduling, we provide a literature review on the topic of agents.

B. What is an "Agent"?: The term "agent" has become widely used recently, so we need to distinguish the following three sources:

Agent sources:

The "AI agent" is emerging from advances in artificial intelligence, which tends to include major issues such as natural language processing and anthropomorphism. The concept of a "planning agent" has actually been around for a long time, and is associated with distributed problem solving or distributed artificial intelligence. The concept of a "control agent" is emerging from the control systems community, and reflects the need to develop adaptive, interoperable, reconfigurable, controller modules. By far the bulk of the current research and literature is in the AI agent category.

There is a fourth source that we will discuss: Artificial Life (AL); but for the sake of simplicity we consider AL to be a subset of Artificial Intelligence Agents. AL is aimed at modeling small insect-like, autonomous agents that learn to survive (and cooperate) in complex environments. This is similar to AI agent research, where the "environment" might be a computer network (e.g.: World Wide Web).

Additionally, software products (e.g.: Java, Telescript) have recently been developed that allow users to create so-called agents by writing scripts that can run on any appropriately configured platform on the World Wide Web. Such scripts, no matter how simple, might be called "agents".

Because of the differences in these perspectives, the terminology can be confusing, especially in applications that require a fusion of some or all of these sources.

B.1. Artificial Intelligence Agents: According to reference [1]:

"The notion of an intelligent autonomous agent is one of the most important and exciting concepts to emerge in computer science in the 1990s. Agent technology looks to radically alter not only the way in which we interact with computers, but also the way we conceptualize and build complex systems."

"Agent technology" is rapidly emerging as a proposed solution to many software engineering problems. What a technologist might mean by the term "agent", however, is often vague. For example according to [2]:

" the question what is an agent? is embarrassing for the agent-based computing community in just the same way that the question what is intelligence? is embarrassing for the mainstream AI community. The problem is that although the term is widely used, by many people working in closely related areas, it defies attempts to produce a single universally accepted definition."

The fact that "agent" is difficult to define explains why the term is so widely used. Reference [2] attempts to nail things down with the following definitions:

"Perhaps the most general way in which the term agent is used is to denote a hardware or (more usually) software-based computer system that enjoys the following properties:

autonomy : agents operate without the direct intervention of humans or others, and have some kind of control over their actions and internal state;

social ability : agents interact with other agents (and possibly humans) via some kind of agent-communication language;

reactivity: agents perceive their environment, (which may be the physical world, a user via a graphical user interface, a collection of other agents, the INTERNET, or perhaps all of these combined), and respond in a timely fashion to changes that occur in it;

pro-activeness : agents do not simply act in response to their environment, they are able to exhibit goal-directed behavior by taking the initiative."

FIGURE 1: An AI agent is expected to have a wide range of capabilities.

These attributes are incredibly broad. But characteristics such as "interact with" and "operate without direct intervention", and so on, could be interpreted in the most sophisticated ways (e.g.: natural language, intelligence) or in the most simple ways (e.g.: sends a binary signal). Thus, the confusion remains, but the need for "autonomous" modules that act spontaneously, without the need for direct manipulation by the user, yet somehow knowing what the user wants, is clear. For a module to act autonomously it must have enough knowledge of the goal, or user preferences, to react to any number of possible conditions. This amounts to adding "intelligence" to the module, a concept that has been around for a long time (AI) with limited success. Reference [13] contains several articles on the topic of AI agents.

It is inaccurate, however, to conclude that we are seeing traditional AI in disguise, under the rubric "agents" (i.e.: AI in a new wrapper). It is more accurate to say that we are seeing a new direction in AI research, possibly with a much more realistic agenda, but it would not be AI if it did not retain some of the unrealistic abstractions.

AI has been searching for new directions for the last 15 years. The evidence is in favor of the hypothesis that real intelligence will elude codification. My own view of the failures of traditional AI is that they result partly from the failure of the "huge monolithic" software approach, where it is common to hope that enough knowledge could eventually be added to a system to make it smart. This approach fails for three reasons:
even preliminary versions of such software can not be effectively maintained over time (across operating systems, processor innovations, system goals, etc.);
there is never (it seems) enough knowledge encoded -- there is always the need for more;
an intelligent system must be able to learn and adapt.

These reasons are neither complete nor independent, but they lead to the conclusion that we need smaller, survivable, modules that have there own identity and purpose, can interact, possibly cooperate with each other, and learn from their environment. Hence: "agents".

The progress in agent technology is mirrored by recent progress in artificial life (AL) research [12]. The goals are almost identical: model small autonomous agents that inhabit a dynamic environment, react effectively to a constant steam of changes, while cooperating, and learning. It is the hope of the AL community that a goal-directed intelligence can emerge from a mix of smaller autonomous units, but results so far have been inconclusive at best.

Both the AL and Agent research community are aimed at the idea of smaller modules that can act on their own with some intelligence. This avoids the monolithic software problem and has an inherent hedge against the effects of "continuous change".

Agent research is further supported by the amazing progress of the World Wide Web. This brings into play the distributed nature of users and processing environments. The www is becoming a "platform" of its own, potentially displacing the PC for many users, especially those primarily interested client/server services that are available on the www. This rather huge observation has sent shudders through software giants who are vested in PC software (e.g.: Microsoft).

Many geographically dispersed users and agents can work incrementally on a large problem without having a single global view. This is an attractive paradigm for large corporations that have facilities and logistics problems that span the globe. It is also attractive to software development companies that want to draw on many dispersed developers. In an Escher-like manner the developers of agent software will use web-based agents to do their job.

Emphasizing the decentralized, distributed, nature of complex systems, [11] observes:

"Generally, any non-trivial enterprise is distributed. Distribution can be geographical, logical, temporal, or spatial. In a manufacturing domain, it is not uncommon for production to be distributed geographically, sometimes on a continental scale (the automobile industry is a prime example). An enterprise can logically be distributed, reflecting its organizational structure. Organizational structuring can be a necessity in order to decompose the enterprise's problems into manageable chunks and to better exploit available expertise. Whenever distribution takes place, communication must follow as a necessity."

Thus, we see several themes converging on the idea of agents: distributed problem solving, the world-wide-web, simple autonomous entities, adaptation to continuously changing environments, opportunistic cooperation, and learning.

Reference [3] champions ideas similar to [2]:

"Researchers and software companies have set high hopes on so-called software agents, which "know" users' interests and can act autonomously on their behalf. Instead of exercising complete control (and taking responsibility for every move the computer makes), people will be engaged in a cooperative process in which both human and computer agents initiate communication, monitor events and perform tasks to meet a user's goals."

The idea that we can become task masters over a staff of intelligent agents that operate throughout computer networks doing a myriad of useful jobs is an attractive one. However, reference [3] cautions the reader:

"Although the tasks we would like software agents to carry out are fairly easy to visualize, the construction of the agents themselves is somewhat more problematic. Agent programs differ from regular software mainly by what can best be described as a sense of themselves as independent entities. An ideal agent knows what its goal is and will strive to achieve it. An agent should also be robust and adaptive, capable of learning from experience and responding to unforeseen situations with a repertoire of different methods. Finally, it should be autonomous so that it can sense the current state of its environment and act independently to make progress toward its goal."

Seasoned AI researchers would probably chuckle at the phrase "sense of themselves", but again the prospect of a team of autonomous agents working tirelessly through the night on your behalf is still attractive. But just like AI, the ideas are relatively easy to dream up, it's the application to reality that hurts. Reference [3] agrees:

"Programmers have difficulty crafting even conventional software; how will they create agents? Indeed, current commercially available agents barely justify the name. They are not very intelligent; typically, they just follow a set of rules that a user specifies."

The agent agenda gets even more aggressive, however, assuming that the initial hurdles could be overcome [3]:

"Over time, "artificial evolution" can codify and combine the behaviors of the most effective agents in a system (as rated by their owners) to breed an even fitter population."

" this approach could result in a complete electronic ecosystem housed in the next century's computer networks. Agents that are of service to users or to other agents will run more often, survive and reproduce; those that are not will eventually be purged."

"Agents will bring about a social revolution: almost anyone will have access to the kind of support staff that today is the mark of a few privileged people."

A "complete electronic ecosystem housed in the next century's computer networks" sounds like science fiction, but the prospects are intriguing nonetheless.

Reference [4] does battle with the "buzzword frenzy" as they see it. For example, they pose these questions concerning agents:

"What is so irresistibly attractive about this concept that it has exploded into faddism in this way?"

"Why have so many companies tried to position their products as based on agents?"

And suggest the answer:

" an easy answer would be simple fashion. Fad sells"

Reference [4] helps clarify things by providing a detailed example of an agent, a system called Julia, with the following properties: autonomy; personality; discourse; risk and trust; graceful degradation; cooperation; anthropomorphism; expectations.

These attributes are described in [4], and the details are a bit overwhelming, but suffice it to say that the ideas are consistent with what has already been mentioned. Thus, the agent purist considers an agent to be quite intelligent, flexible and powerful, even having human-like characteristics such as natural language and emotions.

Reference [5] expresses many of the same hopes (and dreams) for software agents but takes a more pragmatic view when it comes to defining an agent:

"The criterion for agenthood is a behavioral one. An entity is a software agent if and only if it communicates correctly in an agent communication language such as ACL".

ACL (Agent Communication Language) is a programming language that is intended to be the official language of agents. They [5] make an important point about how agents will communicate. The critical feature is interoperability: agents need to be able to:

" exchange information and services with other programs and thereby solve problems that cannot be solved alone."

This leads to interface specifications that are similar to those of object-oriented design, but the abstraction is on a higher level in that it applies to all agents, and not just to specific objects within a particular object-oriented design. Reference [5] points out that there is a major ARPA program to standardize such computer languages, called "Knowledge Query and Manipulation Language", under the ARPA Language Sharing Initiative1.

Referring to recent developments in agent technology, reference [18] expresses the related issues with a flare:

"Developments in these areas aren't happening in static environment. An unstoppable force -- symbolized by the explosive interest in the INTERNET -- is pushing us to link our computers into broad networks, and we will need a common language that can join everyone. Today, machines on the network can exchange a bag of bits, but the value of that is limited. If two machines are going to do any sophisticated collaboration across these networks, programmers will need to write special software that ensures our machines are ready to interact with each other. This interoperability is perhaps the greatest potential of autonomous software agents, which at their heart are mobile pieces of software that can run on any machine on a network. Some of the most promising agent software will establish a lingua franca for the network so that computers can exchange full-featured programs."

One of the commercial companies leading the way in these technological developments is General Magic, Inc., Sunnyvale California. In their promotional literature [19], they advertise a product called Telescript, with Telescript-based services:

"Telescript technology is an implementation of a programming language that is specifically designed for communication ... Currently, to communicate electronically, a message ... is sent through a static network ... Sometimes the message can contain some predefined instructions to fetch specific information ... There is no flexibility in this setup.

Telescript technology is based on a very simple yet extremely powerful and all-encompassing concept. Every message is a Telescript program and every network a receptacle, or Telescript interpreter, ... The network changes from a predefined, rigid system into a flexible platform for applications and services.

Agents are the Telescript programs that are sent across networks. They are encapsulations of users' instructions that perform all kinds of tasks in places on Telescript-enabled networks, places such as electronic mailboxes, or electronic merchants. People who dispatch agents can think of them as extensions of themselves, capable of gathering information resourcefully, negotiating deals, and performing transactions."

The success of this kind of product has not yet been fully proven, but it is clear that it represents a significant step in making agents practical. The capabilities of Telescript agents might be significant for a given user, in that it automates a repetitive or mundane task, but it is another level of complexity to say that such agents might coordinate, negotiate, or learn.

Sun Microsystems has a similar product, called JAVA, that has some of the same functionality as Telescript. They shy away from the term "agent", but instead invoke "applets":

"Netscape Navigator 2.0 supports Sun's Java, a new programming language based on C++ and
designed for secure two-way, real-time interaction. Using Java, developers can write custom
mini-applications called Java applets. When integrated into Web pages, Java applets allow expert
graphics rendering, real-time interaction with users, live information updating, and instant
interaction with servers over the network. Java applets are downloadable from any server and run
safely on any platform. Java is designed to provide maximum security on public networks, with
multiple safeguards against viruses, tampering, and other threats."2

Along these same lines, Microsoft Corp. recently announced3:

"Microsoft Corp. Chairman Bill Gates said yesterday that every effort at the company would be directed toward the INTERNET 'The INTERNET is the primary driver for all new work we are doing throughout the product line', Gates told an audience 'We are hard-core about the INTERNET'.

The recent phenomenal rise of the INTERNET makes the network more strategically important than any individual computer Gates promised to embrace common INTERNET standards even if those standards compete with Microsoft products.

For example, Microsoft said yesterday that it had agreed to license Sun Microsystems' Java language, even though it is considered the main rival to Microsoft's Visual Basic language for creating World Wide Web applications."

We have strayed a bit form technical issues into marketing issues, but the point is clear: there is a powerful dynamic emerging that is changing the face of software development and it involves the World Wide Web and agent-like services.

Moving on to the problem of how agents might interact, reference [5] presents an interesting paradigm for agent interaction, called the Contract Net Approach4:

"In the contract net approach to interoperation, agents in need of services distribute requests for proposals to other agents. The recipients of these messages evaluate those requests and submit bids to the originating agents. The originators use these bids to decide which agents to task and then award contracts to agents."

In this view, an agent can represent a customer, a resource, a cost factor, etc., and the system interacts so as to solve the problem in a reasonable way, such as at low cost. This appears to be a practical paradigm for how agents might interoperate and/or cooperate. The main advantage is that the architecture is modular and flexible, and the modules interact as needed to solve the problem, without having a cumbersome pre-defined structure5. It is also advantageous to have a design concept that humans are fairly familiar with, and even mimics that way "agents" work in real estate, insurance, etc.

Two kinds of agent concepts that emerge from the literature are [17]:

The Personal Assistant Agent (PA): interacts with a human user to do tasks and learn user preferences;
The Internal, Intelligent, Agent (IA): the intelligent agent that navigates the network, dealing with other IA's and PA's.

Reference [17] describes the integration of an enterprise-wide system of such agents:

"Underlying the framework is the notion of an enterprise model that is built by dividing complex enterprise operations into a collection of elementary tasks or activities. Each such task is then modeled in cognitive terms and intrusted to an IA for execution. Tasks that require human involvement are referred to the appropriate person through their PA - humans and IA's participate in the framework as equal partners."

At this point the breadth of the agent concept is evident, so now we will go through a specific example from the Media Lab at MIT.

B.1.1. An AI Agent Example: Reference [16] provides a very interesting example of an agent system that was implemented and tested with real users. The main theme of the research is to get away from "direct manipulation" of the computer, and somehow get the computer to know what the user wants, especially when it comes to mundane, repetitive tasks. From [16]:

"Techniques from the field of AI, in particular autonomous agents , can be used to implement a complementary style of interaction, which is referred to as indirect management. Instead of user-initiated interaction via commands and/or direct manipulation, the user is engaged in a cooperative process in which the human and computer agents both initiate communication, monitor events and perform tasks."

The research described in [16] applies to situations where:

frequent, repetitive, user behaviors dominate;
different users have different behaviors;

In such an environment, can an agent learn, or program itself, to know the user's preferences? We would expect the agent to become gradually more helpful as it observes the behavior of the user. The gradual-ness works both ways: the user is, hopefully, getting more and more comfortable with trusting the agent to make decisions.

The agent might learn from these four different sources:
watch the user, look for patterns, etc.
the user might reject the agent's suggestion;
the user might give specific examples of what they like or want;
the agent might ask advice from other, similar, agents.

Potential applications include:
electronic mail handling;
meeting scheduling;
news filtering;
recommend books, music, other entertainment.

Here, we will focus on the e-mail agent, as described in [16]. The article describes an MIT-Media Lab system called Maxim. Maxim learns to prioritize, delete, forward, sort and archive mail messages on behalf of the user. The agent memorizes all of the situation-action pairs generated by the user. Situations are represented as a set of features: sender, receiver, cc:, subject:, read, not read, etc.

When a new situation occurs (e.g.: arrival of a message) the agent tries to predict the action(s) of the user:

The agent compares the new situation with the memories (previous situation-action pairs) and finds a set of nearest neighbors;
The actions associated with these nearest neighbors are used to suggest an action that the agent believes that the user will take in this new situation.

The metric used to measure nearness of situations is a weighted sum of differences in each feature component. Some features carry more weight than others - the weight of a feature is determined by the agent and adjusted as the agent learns6. At quiet times (i.e.: night), the agent has the ability to go off-line and analyze the set of situation-action pairs for patterns and/or correlations. For example it might find that feature x is a clear indicator of action y, in that whenever feature x is high the action is always y, regardless of the other feature values. The agent also associates a confidence level with each suggested action, based on whether the suggested action agrees with the nearest neighbors' associated actions. Confidence is also dependent on how many examples the agent has seen so far -- the more experienced the agent, the more confident it is that the nearest neighbors are representative, and the more often it has looked for patterns and adjusted the weighting factors. Two thresholds are introduced, and set by the user: "do it"; and "tell me".


Figure 2: The MAXIM system requires the user to set two thresholds (from [16]).
If the confidence in the suggested action is above the "do it" threshold, then the action is implemented on behalf of the user, without checking with the user. Later, the user can ask the agent what has been automated recently, etc.

If the confidence level is below "do it" but above the "tell me" level, then the agent offers the suggestion to the user, and waits for the user's response.

When the confidence level is low (say, below the "tell me" level), the agent can send a copy of the new situation it is evaluating and ask other agents to provide their suggested actions (and confidence levels). Over time, the agent might learn that some agents are very helpful, while others represent different preferences.


Additionally, the user has the option of instructing the agent by showing it specific situation-action pairs that are preferred.

Although this system is interesting and innovative, my own experience with "features", "thresholds" and "weighting factors", leads me to the following questions:

Isn't it very difficult to converge on effective weighting factors when the features measure different kinds of things (apples and oranges)?

Doesn't the off-line evaluation usually just pick up on obvious correlations -- the kind that could easily be encoded in a simple rule -- or does it truly pick up on subtle useful correlations?

How easy is it to set the thresholds?

It looks like the neural-network backpropagation algorithm7 might fit nicely here (off-line): lots of situation-action pairs translate into lots of input-output training samples. The inputs would be the features (or differences), represented on some common scale (not a trivial matter), and the outputs could have one neuron for each possible action. The confidence level could be a function of how close we get to the nominal binary output, etc.

I would guess that this would be a difficult problem for backprop since a diverse set of feature values could lead to the same action (i.e.: complex decision boundaries), but this would also be a plague to the nearest neighbor method described above.

[16] reports that the system runs too slowly at the present time, and the user needs the capability to tell the agent to ignore some previous situation-action pairs.

From this example, we can see that the functionality of a practical agent can reduce to fairly traditional statistical analysis.

B.2. Planning Agents: Now, we take aim at agents related to "planning and scheduling" systems. It is important to realize that the term "planning agent" has been widely used in this community for a relatively long time (see [14], [15]), and overlaps with the AI agents described above. There are a wide variety of agent concepts that are described in the planning literature, generally associated with small, asynchronous, problem solving components that must work together to solve a larger problem.

We will try to narrow our investigation down to those ideas that compliment the AI agent technology already described. For example, [11] describes a hierarchical design of interacting agents: the distributed asynchronous scheduler (DAS). There are three levels:

S-agents: strategic agents, the highest level of authority, responsible for introducing tasks into the system;

T-agents: tactical agents, middle level, responsible for delegating tasks to resources;

O-agents: operational agents, lowest level, responsible for executing tasks on resources.

More details of the DAS, from [11]:

"When a job is introduced to the system, the S-agent is notified, and the S-agent delegates each operation in the process plan of the job to individual T-agents. Each T-agent then delegates its operation to a resource. This action of delegation generates a message sent to the relevant O-agent. The O-agent then attempts to introduce this new operation into its local schedule. If it succeeds, it writes out a start time for that operation, initiating constraint propagation through the job's process plan with resultant messages sent to the agents holding the remaining operations in that plan."

The focus of this architecture is to solve scheduling problems in a modular, hierarchical, asynchronous, fashion. It does not bring up "autonomy", or "intelligence", in the same way as the AI agents described above, but these planning agents must also communicate, cooperate, and learn to be effective. The DAS is a reasonable way to segment the problem solving components into loosely configured, but hierarchically organized, modules. Although this method does not invoke the exact same dynamics as the Contract Net approach, it is very similar.

It is easy to imagine that the jobs being introduced into the DAS are arriving over a network from distributed users. The users would be initiating their own agents with the following information: the job they wish done, the constraints they want satisfied, and the criteria for making choices, etc. The S-agent might evaluate an arriving job, and perform a type of filtering, or screening, to determine the feasibility of the request before it is passed on to a T-agent. This S-agent might reject the request, with an explanation, or direct the requesting job agent to other resources at other sites and so on. If the request is accepted, the S-agent might assign a priority or other features to the job before passing it the T-level. There are various forms of cooperation that might be necessary, depending on the conflicting jobs, the priorities, the willingness of a job agent to negotiate changes, etc.

The emerging picture is that of many distributed users who customize their agents to seek resource commitments. The agents have to negotiate with similar job-seeking agents, and also with agents that represent the resources. These job-seekers might have built-in relaxation and cooperation strategies that are tuned to specific situations. The user can launch these job-seekers and let them autonomously evaluate the available resources, while also acquiring relevant information from on-line services. After attaining commitments, the agent might watch (i.e.: monitor) for sudden changes to the commitments, offer re-negotiating terms, etc. Section D of this report provides many more such examples.

B.3. Control Agents: Reference [6] presents an interesting characterization of agents, biased by the fact that they are particularly interested in manufacturing environments. They describe the progress in software design as an evolution through the following levels:

traditional -> passive -> active -> self organizing.

Passive software is associated with current developments in object-oriented design. The distinction between passive and active is that active modules have an independent "thread of control". For example, from [6]:

"When does a program run?
traditional: when called by the operating system;
passive objects: when an object receives a message;
active objects: as required by the object's goals. "

[6] also provides the following characteristics of active objects:

"Active objects run their thread of execution to continually monitor their environment against goals.

An active object takes action when appropriate.

Active objects do not have to be called or invoked by another software module.

Active objects will change their state and behavior over time to reflect their operating experience."

The distinction between active and self-organizing modules is that the self-organizing modules will communicate with other modules and learn to cooperate (the full agent capability). This is a useful distinction for control systems domains since it is relatively clear that a module could have an independent thread of control but it is a major leap to say that the module can learn to cooperate. These are the same agent themes expressed earlier, but with a "control systems" flavor (less concern for interfaces, such as natural language, and more emphasis on solving sensing/action-oriented problems). As control theorists, they seem to be unable to avoid invoking non-linear systems and chaos theory. [6] goes on to say:

"Manufacturing enterprises are already agent-based. People and machines "execute" their own programs and interact with one another constantly. It is no surprise that such systems appear "chaotic" to their managers, and it is a reasonable hypothesis that these systems are in fact mathematically chaotic. However, their chaos is difficult to control. The human agents run on carbon-based CPU's, while the machines execute a combination of electronic and mechanical logic, and there is no common architecture to integrate and control them.

The vision of agent-based shop floor systems is to embed people, machines, and parts within just such a common infrastructure, so that it can be modeled, analyzed, and controlled to yield benefits of nonlinear dynamics while avoiding the disadvantages"

Reference [17] emphasizes a similar theme:

"Enterprise integration demands on incremental solution to automation. Our IA approach addresses this issue in a fundamental way by enabling men and machines to work together effectively as peers. As peers, they are interchangeable by design, permitting an enterprise to be computerized incrementally, one job at a time without impeding ongoing operations. IA's thus provide a graceful and acceptable way to migrate from a people-based to a machine-based enterprise."

Reference [7] also brings up many agent-related ideas within the context of enterprise-wide manufacturing systems, and in particular with respect to the control of a family of machine tools. One of the goals under this program (Open Architecture Machine Tool Controllers/Agile Manufacturing [8]) is to define a "common execution environment" for the development, testing, and implementation of advanced control systems software. The plan is to draw in as many third party vendors as possible so as to continuously combat the evolutionary nature of the technology. In this context, "agents" are software modules that can communicate and cooperate with other modules (interoperable) as well as be reconfigurable as new technologies (e.g.: high resolution vibration sensor) are introduced. Since machine tools involve detailed control and sensing issues the engineering is aimed at setting operating systems-level standards/protocols and making them available to all participants, (i.e.: the "open system architecture").

The emerging picture is that of many geographically distributed developers defining and accessing various modules for testing and evaluation. The modules that are used a lot survive, and the others die off. A big advantage is that potential modules can be put quickly into the hands of the end users for rapid, realistic prototyping.

These control themes are consistent with the AI themes involving agents, but control systems are a lot more sensitive to real-time sensory connections to the environment (i.e.: specialized hardware, high speed I/O channels, sensors, signal processing), and they expect most of the reconfiguration of the system to be done by human operators. The requirements for interoperability of the components, a common execution environment, and a common communication language are essentially the same as for AI agents. The use of geographically dispersed users and developers is also a common theme.

The following requirements emerge that span the AI and Manufacturing agent concepts:

an environment of continuous change;
geographically distributed users, and resources, connected by a network;
small autonomous, interoperable, modules;
a common language;
better human/computer interfaces, integration of people and machines;

Agent technology is a reasonable paradigm for addressing these requirements, even though the issues are quite broad and much work remains.

Finally we should point out that there is much more agent-based information in the literature and available through INTERNET and the world-wide-web. For example, reference [21] provides a tour through many web sites. Here is a sample from [21]:

http://galaxy.einet.net/MCC/Carnot/DCA.html
http://dis.cs.umass.edu/dis.html
http://www.cs.umbc.edu/kqml/papers/kqmlspec.ps
http://web.nexor.co.uk/mak/doc/robots/active.html
http://www.ncsa.uiuc.edu/SDG/IT94/Proceedings/Agents/eichmann.ethical/eichmann.html

There are many more web sites to explore on this topic, but the best place to start is by doing a web search to find the MIT Media Lab and go from there.

C. A Distributed Planning System Architecture: From the previous analysis it is clear that agent technology can be integrated into many levels of a distributed planning system. Figures 3 and 4 shows an overall system architecture concept. Users and developers are envisioned as geographically dispersed but able to access resource management systems through a network of communications, most likely with some combination of local area networks and the world-wide-web. A resource management facility is divided into management, planning, and operational levels. Agents can be working at any of these levels, but the management agents are the first level of interaction with the incoming job requests, filtering and assigning priorities to them. The functions provided by these three levels are viewed as isomorphic to lower levels of functionality. For example, there is almost always a need for a "management" function that interacts with the outside world while passing on jobs to a lower level. The middle level takes the assignment from the upper level and puts it into a form that can be "tracked" and/or scheduled. The lowest level is the operational, or "do it" level and is concerned about how the task is implemented. The implementation of an "real" task usually implies that we operate some machinery, but in an abstract sense the implementation of a task might consist of attaining commitments or posting messages, etc.

One of our design concepts is to have an isomorphic structure that recursively decomposes into three layers. In this way the higher levels of abstraction are isomorphic to the lower levels, and in each case the functionality is recursively split into three levels (S, T, and O, similar to [11]). This simplifies the overall architecture and helps to define the environment for any agent (AI, Planning, or Control) that might be introduced into the system.

In particular, it is easy to integrate a contract net approach into this architecture: the S-level screens and introduces jobs into the system, the T-level promulgates and supervises the requests for bids, and the O-level specifies the bid parameters.

Specialized agents would also be introduced to: evaluate the nature of a conflict; represent resource constraints; propagate constraints as commitments are made; check for dead-lock and fruitless cycles; etc.

FIGURE 3: An asynchronous, distributed, resource planning system architecture.

Algorithms will be useful to agents that seek answers to a variety of "what-if" queries. By "algorithm" we mean the typical heuristic search strategies applied to the combinatorial search space of scheduling options. We have explored many such algorithms in past research [20]. In the architecture presented here we view algorithms as playing a limited but important role, at a very low level. For example, an agent may want to know how some jobs might be moved to make room for a new job. The agent could call an algorithm, with the initialization parameters set to that specific situation, and get an "algorithmic" solution. The agent may choose to ignore the suggestions of the algorithm, and decide to do something else. In this context the algorithms are like idiot-savants that can perform extensive computations in a short time to answer very specific questions about how constraints might propagate8. That is, the algorithms are not expected to give final schedules, but instead to provide sample schedules, or partial schedules, that help an agent evaluate the ramifications of various options.




Figure 4a: We apply a recursive design strategy, using three types of levels: Strategic, Tactical and Operational.

Figure 4b: The facility management system is divided into three levels, the management, planning and operational levels. Each of these levels is subdivided into three functional levels whose functionality is analogous to the management, planning and operational levels.

D. Further Agent Examples: As we have seen, the agent concept can be defined in many ways. We will give more examples, just to demonstrate the breadth of the ideas. We split the examples into two categories: micro-agents and macro-agents. This is just to set some upper and lower limits - there can be agents at any level.

Figure 5: Micro-agents in an abstract environment consisting of parameters and their values.

D.1. Micro-Agents: The micro-agent concept emphasizes the lower levels of abstraction, along the lines of "artificial life" ("insect-like", etc.). They are simple, autonomous entities. They live in an abstract community defined by parameter values, continuous or discrete, (State Space, or environment). They continuously "watch" (on the alert), looking for particular events (exciting events). They can observe certain parameters of the state space (their scope), and may be active during specific phases of a system, and inactive during others (their extent). They tend to be near-sighted or have tunnel vision: they cannot see all the state variables. They might be sensitive to "messages" that are "posted" by other agents.

They can perform actions: attempt/suggest changes to particular state variables (again, only the variables that are within "reach" of the agent), post messages, warnings, etc. Agents can communicate and cooperate directly with each other, but more often than not they communicate through changes in state, and by posting messages that excite other agents variables (agents "see" the results of actions of other agents).

Agents can be sensitive to static parameter values or dynamic (sensitive to sequences in time, the flow of events, parameter history, trends, etc.). Agents can be deterministic or stochastic. There is usually no prior ordering to the actions of an agent, they tend to act when they are excited. But it is usually necessary to have "moderating agents" for resolving conflicts and detecting pointless cycles.

The overall goal of agent activity, in the context of scheduling, is to drive the system of scheduling variables to a feasible, near-optimal, schedule. Thus the emergent behavior of the many agents is the evolution from a non-feasible, sub-optimal, state, to a feasible, near-optimal, schedule. A satisfactory schedule is one where the agent activity has ceased (i.e.: there are no recommendations for change, there are no excited agents, etc.). Agents can be assigned to individual, or subsets of: requests, resources, criteria, constraints, diagnosis (what's holding things up? what kind of conflict is this? what kind of bottleneck condition is this?), conflict resolution (mini-schedulers), schedule repair, etc.


Figure 6: The reaction of a couple of agents to a new event: the arrival of a new job.


D.1.1. Scenario #1 - Reactive: Let's say the state of the schedule, for the moment, is excellent: no complaints, no active agents, all constraints satisfied, all contentions resolved. Then a change happens: a new request enters the system (i.e.: of high priority).


Figure 7: The agents will need to coordinate in order to avoid cycling: one agent does something that activates another agent to un-do it, and so on.
Some agents (the excited ones) jump into action. What resource does the new request need, for how long? What are the alternatives? What priority? Which scheduled requests will be affected? Which agent has the authority to nullify a previous scheduling commitment? How much time do we have for re-scheduling? If request x is moved, what else is affected? Are there unscheduled requests that can now take advantage of resource availability?

We could think of the new request as an agent of its own: it attempts to plop itself down at it's most preferred spot. If this creates a conflict it would be detected by, say, a capacity-agent that senses the overload and acts to resolve it by moving an activity, etc. This can cause a ripple that subsequently activates other agents, etc. The activity may die down (i.e.: converge) or cycle indefinitely. Since micro-agents are near-sighted there is the possibility that the system degenerates into a repetitive state: agent #1 makes a fix, and agent #2 fixes it back, etc. It may be necessary to be looking for such cycling throughout the sequence of actions. Other, higher level agents, would have to ensure convergence.


Figure 8: A disruption will be detected by the affected agents and they will react spontaneously.
Of course, it does not have to be a new request that activates the agents, it can be any disruption, such as a change in resource availability, a canceled activity, an unexpected event, etc.


D.1.2. Scenario #2 - Progressive Refinement: Agents become active based on the stage of refinement of the scheduling process. For example, over-booking of a resource may be allowed on an out-day schedule, but as the near-day approaches constraint checking agents become less tolerant and force a timely resolution.

D.1.3. Scenario #3 - Optimization: Given a feasible but sub-optimal schedule to start with. Individual request-oriented agents might suggest slight adjustments in order to improve their "worth"9. This may involve the re-scheduling of a few activities: contention is resolved in favor of more worth. "Hill climbing" emerges as these local conflicts are resolved in favor of increasing worth (or switches to some other criteria when the worth is high enough or enough tasks have been bumped, etc.). At some point the agent-directed action stops (convergence) because all suggested moves are "negative" and therefore rejected.

D.2. Macro-Agents: Macro-Agents represent clients that need resources (or services). The macro-agent must negotiate with a resource manager, who has the authority to allocate the resources. The manager may access lower level functions to modify the schedule (make room for a new activity, cancel an activity, optimize a part of the schedule, etc.), but these types of details are dwarfed by the managers need to accommodate rapid changes. The resource manager might need helpful facilities, such as: i) provide the activities that conflict with a suggested commitment, the extent, or depth, of the conflict, etc.; ii) the resource loading across time for a given resource, etc.; iii) effective human-computer interfaces.

Much of the action in this scenario is related to managing the changes that may occur (resulting from unexpected, un-modeled, events). For example, the resource manager may receive a request for resources that conflicts with an existing commitment. Rather than simply denying the request, or performing some complex algorithmic re-scheduling, the manager could send a query to the agent(s) who represents the conflicting activities, asking them what variations they can accept and at what cost. The idea here is that there may not be an easy way to evaluate the actual impact of a schedule change without talking directly to the client or his agent (the criteria changes, the circumstances change, etc.). The agent might possess enough knowledge of the client's request to autonomously respond to the query, or the agent may have to contact the client. Thus, the agent plays the role of an intermediary, expediting adjustments, while representing several clients at the same time. This is similar to airline reservations, and various other customer services (US West, etc.).


Figure 9: A resource management system must deal with agents that represent different types of clients.

The fun begins when we realize that in complex systems (flow of materials between factories, etc.) there may be several resource managers at work in their own domain, but interacting with others: making commitments and requesting commitments from external resources etc. The many possible changes that can ripple through the enterprise is quite large and therefore there is a need to carefully manage the flow of changes. Because of the uncertainty, and potential uniqueness of each change, there is very little hope that an "algorithm" could anticipate all the queries. Such complex systems could identify specific, lower level, functions that could be automated, but the efficacy of such a network depends on real-time communication of changes to minimize the effect of unexpected events (failures, late deliveries, employee illness, etc.).






Figure 10: In an enterprise-wide system the resource managers will have to keep track of commitments and cancellations in a highly dynamic environment.

References

[1] "Intelligent Agents: Theories, Architectures, and Languages", Edited by Michael Wooldridge and Nicholas R. Jennings, Springer-Verlag Lecture Notes in AI - Volume 890, Published January, 1995 (Europe), April 1995 (USA)

[2] "Intelligent Agents: Theory and Practice", Michael Wooldridge, Nick Jennings
Knowledge Engineering Review Volume 10 No 2, June, 1995, Cambridge University Press, 1995.

[3] "Intelligent Software: Programs that can act independently will ease the burdens that computers put on people", Scientific American, Vol. 273, No.3, pp. 84-86, September 1995. MIT Media Lab: http://www.media.mit.edu/.

[4] "What's an Agent Anyway? A Sociological Case Study", L. N. Foner, Agent Memo 93-01, Agents Group, MIT Media Lab, 1993.

[5] "Software Agents", M. Genesereth, S. Ketchpel, Communications of the ACM, July 1994.

[6] "Technical Assessment: The Impact of Agents in Manufacturing", BRL & Co., for National Center for Manufacturing Sciences, May, 1995.

[7] "Next Generation Controller Specification for an Open Systems Architecture Standard", T. Depkovich, Martin Marietta, Denver, Colorado, Final Report WL-TR-94-8033, Sept., 1994.

[8] "Evaluation of Open Architecture Machine Tool Controllers and Agile Manufacturing", W. J. Wolfe, AFOSR, Summer Faculty Final Report No. 62, Wright Laboratory, Wright Patterson AFB, Dayton, Ohio, July 1995.

[11] "The Distributed Asynchronous Scheduler", P. Burke, P. Prosser, in Intelligent Scheduling, editors: M. Zweben, M. Fox, Morgan Kaufmann Publishers, 1994.

[12] "Artificial Life II", Proceedings of the Workshop on Artificial Life, February, 1990, Santa Fe, New Mexico.

[13] "Intelligent Agents", Comm. of the ACM, July, 1994, Volume 37, Number 7.

[14] "Readings in Planning", J. Allen, J. Hendler, A. Tate, Morgan Kaufmann Publishers, 1990.

[15] SIGART BULLETIN, Special Section on Planning Agents, Vol. 6, No. 1, Jan., '95.

[16] "Agents that Reduce Work and Information Overload", P. Maes (MIT Media Lab), Communications of the ACM, July 1994, Vol. 37, No. 7.

[17] "An Intelligent Agent Framework for Enterprise Integration", J. Pan, J. Tenenbaum, IEEE Trans. on Sys., Man, and Cyb., Vol. 21, No. 6, Nov. - Dec., 1991.

[18] "Agents of Change", P. Wayner, A. Joch, Byte Magazine, March, 1995.

[19] "The World of Telescript Technology" , GM-M-TSBROII94-V2, General Magic Inc., Sunnyvale, CA, 1994.

[20] "Spacebased Resource Planning and Scheduling - Phase II Report", W. J. Wolfe, Research Grant #SG-258799SJP, Hughes Information Technology Corporation, Aurora, Colorado, February, 1995.

[21] "Intelligent Agents", Manuscript, Jan., 1995, R. Oliver, html version available by contacting roliver@raisinets.den.mmc.com (Richard Oliver).


Footnotes:
 1 See reference [21] and "Specifications of the KQML Agent-Communication Language", available at http:www.cs.umbc.edu/kqml/papers/kqmlspec.ps.
2 http://home.netscape.com/comprod/products/navigator/version_2.0/java_applets/index.html.
3 See The Denver Post, December 8, 1995.
4 A reference on contract nets: Davis, R., Smith, R. G. "Negotiation as a metaphor for distributed problem solving", Artificial Intelligence 20, 1 (1983), pp 63-109.
5 This concept is not very different from a "blackboard systems" approach.
6 [16] does not explain the details of how the agent adjusts the weights, but it seems clear that there are a variety of ways to encourage the agent by increasing some weights and decreasing others.
7 See any text on Neural Networks.
8 In some sense, we view "algorithms" as potential "buttons" on a sophisticated "scheduling calculator " -- used by managers to answer "what-if" questions.
9 "Worth" here is a euphemism for whatever the scheduling criteria might be, such as the "profit" of a job.
Agents.rev.1
W. J. Wolfe (UCD), S. E. Sorensen (HITC), 12/9/95

Agents.rev.1