There are several compelling reasons why agents defined using mental attitudes might be useful. First, if an agent can be described in terms of what it knows, what it wants, and what it intends, then, since it is modeled on familiar concepts, it becomes possible for users to understand and predict its behavior. Second, understanding the relationship between these different attitudes and how they affect behavior can provide the control mechanism for intelligent action in general. Third, computational agents designed in this way may be able to interpret the behavior of others independently from any implementation.
Moreover, many of these deliberative architectures are based on the belief-desire-intention (BDI) model of rational agency.
BDI Architecture
Although not a system, the BDI model provides a foundation for many systems and we therefore consider it separately as an abstract architecture in its own right. Arguably, the most successful agent architectures are founded on the BDI model, in which agents continually monitor their environments and act to change them, based on the three mental attitudes of belief, desire, and intention, representing informational, motivational, and decision-making capabilities. Architectures based on the BDI model explicitly represent beliefs, desires, and intentions as data structures, which determine the operation of the agent.
The intuition with BDI systems is that an agent will not, in general, be able to achieve all its desires, even if these desires are consistent. Agents must therefore fix upon some subset of available desires and commit resources to achieving them. These chosen desires are intentions, and an agent will typically continue to try to achieve an intention until either it believes the intention is satisfied, or it believes the intention is no longer achievable [8].
Many formal models have been devised in order to investigate and analyze the relationships between belief, desire, and intention. Much of this work investigates how modal and temporal logics can be used to specify theories of agent behavior. For example, Cohen and Levesque [8], Kinny et al. [9], Jennings [10], Haddadi [11], and Wooldridge [12] have all proposed such models. These models are often underpinned using the possible-worlds semantics first proposed by Hintikka [13]. Using this as a basis, it is possible to develop BDI modal logics that determine how different relationships between the mental attitudes produce different agent behavior.
As well as the formal models of BDI agents that specify desired behaviors of BDI agents, generic BDI architectures that encapsulate the BDI model have been constructed to support the design of practical agents [14], and programming languages have been proposed that can be used to implement BDI agents that satisfy some of the formal BDI properties [15]. In addition, BDI agents have been used extensively in real-world applications [16]. Many of the architectures and systems that are discussed in this chapter have been influenced by models of BDI, including the Intelligent Resource-Bounded Machine Architecture (IRMA) [17] and, arguably the best known and most established architecture, the Procedural Reasoning System (PRS). Both of these agent systems can be considered to be deliberative, and are considered next.
Procedural Reasoning System
Since the mid-1980s, many control architectures for practical reasoning agents have been proposed. Most of these have been deployed only in limited artificial environments; very few have been applied to realistic problems, and even fewer have led to the development of useful field-tested applications. The most notable exception is the Procedural Reasoning System (PRS). Originally described in 1987 [18], PRS has progressed from an experimental LISP version to a fully fledged C++ implementation known as the distributed MultiAgent Reasoning System (dMARS), which has been applied in perhaps the most significant multiagent applications to date [16]
For example, Oasis [19] is a system for air traffic management that can handle the flow of over 100 aircraft arriving at an airport. It addresses issues of scheduling aircraft, comparing actual progress with established sequences of aircraft, estimating delays, and notifying controllers of ways to correct deviations. The prototype implementation comprised several different kinds of agents, including aircraft agents and coordinator agents, each of which was based around PRS. Oasis successfully completed operational tests at Sydney Airport in 1995. Similarly, dMARS has been used as the basis of an agent-based simulation system, Swarmm, developed for Australia's Defence Science and Technology Organisation to simulate air mission dynamics and pilot reasoning. More recent work has sought to apply dMARS to represent different roles in an organization in more general business software for running call centers or Internet services. The Agentis system allowed the generation of fully automated, server-side customer-service applications, and the first major installation aimed to use 4,000 dMARS agents.
The PRS architecture has its conceptual roots in the BDI model of practical reasoning developed by Bratman and colleagues [17] As Figure 2.2 shows, a BDI architecture typically contains four key data structures: beliefs, goals, intentions, and a plan library. An agent's beliefs correspond to information the agent has about the world, which may be incomplete or incorrect. An agent's desires (or goals, in the system) intuitively correspond to the tasks allocated to it. Beliefs, desires, and intentions of PRS are represented explicitly in the Database, Goalbase, and Intention Structure, respectively. PRS agents continually respond to perceptions, or events, which represent new beliefs and goals, by selecting plans to become intentions.
In PRS agents, the BDI model is operationalized by plans. Each agent has a plan library, which is a set of plans, or recipes, specifying courses of action that may be undertaken by an agent in order to achieve its intentions. An agent's plan library represents its procedural knowledge, or know-how: knowledge about how to bring about states of affairs. Plans are designed by a programmer before run time to capture the procedural knowledge of the agent as recipes detailing courses of action. They are the main feature of PRS systems and comprise several components that we describe here.
The trigger or invocation specifies what an agent must perceive in order for a plan to become a contender for execution selection. For example, the plan make tea may be triggered by the event thirsty. In addition, the plan's context must be believed by the agent before the plan can be adopted for execution. For example, the plan make tea might have the context have tea bags. The plan body captures procedural knowledge as an OR-tree with arcs labeled with formulas that may be primitive external actions such as C++ function calls, internal actions such as adding a fact to its database, query goals that are matched to the agent's beliefs, or, finally, achieve goals that generate new subgoals. This make tea plan might have the body get boiling water; add tea bag to cup; add water to cup. Here, get boiling water is a subgoal (something that must be achieved when plan execution reaches this point in the plan), whereas add tea bag to cup and add water to cup are primitive actions (i.e., actions that can be performed directly by the agent).
At the start of execution, agents are initialized with a set of plans, goals, beliefs, an empty event buffer, and no intentions. The operation of the agent can then be enumerated as follows:
Perceive the world, and update the set of events.
For each event, generate the set of plans whose trigger condition matches the event. These are known as the relevant plans of an event.
For each event, select the subset of relevant plans whose context condition is satisfied by the agent's current beliefs. These plans are known as active plans.
From the set of active plans, select one for execution so that it is now an intention.
Include this new intention in the current intention structure either by creating a new intention stack or by placing it on the top of an existing stack.
Select an intention stack, take the topmost intention, and execute the next formula in it.
In this way, when a plan starts executing, its subgoals will be posted on the event queue, which in turn will cause plans that achieve this subgoal to become active, and so on. Once the intention stack executes successfully, the event is removed from the event queue. This is the basic execution model of dMARS agents. Note that agents do no first-principles planning at all, as all plans must be generated by the agent programmer at design time. The planning performed by agents consists entirely of context-sensitive subgoal expansion, which is deferred until a point in time at which the subgoal is selected for execution.
As mentioned above, a whole range of practical development efforts relating to BDI systems have been undertaken, and can be divided into those that are almost straightforward reimplementations and refinements of PRS and dMARS on the one hand, and those that are more loosely based on broader BDI principles. The former category includes systems such as UM-PRS developed at the University of Michigan, a freely available reimplementation of PRS [20], PRS-Lite developed at SRI by Myers [21], Huber's JAM system [22], and the commercial JACK system [23], which are respectively increasingly sophisticated. The latter category includes Bratman's IRMA architecture [17] Burmeister and Sundermeyer's COSY [24], and the GRATE* system developed by Jennings [25]. Nevertheless, PRS and dMARS remain as the exemplar BDI systems.
2.3.3 AgentSpeak(L)
Rao's AgentSpeak(L) [15] is an attempt to provide an operational and proof-theoretic semantics fora language that can be viewed as an abstraction of an implemented BDI system. Essentially, it captures the essence of a PRS system; the only PRS constructs not included in AgentSpeak(L) are simply those that have been designed to make programming tasks more efficient.
As we have seen above, agents have beliefs (about themselves, others, and the environment) and intentions, which are sequences of plans (called intended means). Each agent has a library of plans, and each plan comprises a trigger, context, and body, which is a sequence of actions and goals (collectively called formulas).
The basic operation of an AgentSpeak(L) agent is similar to PRS and has two aspects. The first concerns agents responding to internal events (new subgoals) and external events (new beliefs) by selecting appropriate plans. If the event queue is nonempty, an event is selected and those plans whose trigger matches the event are identified as relevant plans. Those relevant plans whose context is satisfied by the current beliefs become the active plans. From this set, one plan, called the intended means, is selected nondeterministically. Now, if the event that generated the intended means is external, the intended means creates a new intention. If the event is internal, then the intended means is pushed onto the intention whose top plan's current formula is the subgoal that generated the event.
The second aspect of the agent's operation is the execution of intentions. First, an intention is selected, and the next formula in the top plan of that intention is evaluated. If the formula is an action, it is placed in a buffer. If the formula is a query goal, and if it is satisfiable with respect to the beliefs using a substitution, the substitution is applied to the rest of the executing plan. Alternatively, if the formula is an achieve goal, then a new goal event is added to the set of events to be processed.
The AgentSpeak(L) language is a significant attempt to unite the theory and practice of BDI agents, but again, the link between mental attitudes as data structures in implemented systems [as modeled by AgentSpeak(L)] and as modal operators in the theoretical model is weak. Rao simply suggests that we, as designers, should ascribe these theoretical notions to implemented agents, rather than suggesting that there is an approach to defining a formal relationship between them.
In the next section, we briefly discuss IRMA, which is important because it was the first attempt, by Bratman himself among others, to build an architecture that captured the ideas to explain the BDI theory of resource-bounded reasoning. It also offers an alternative view of instantiating the BDI model.
2.3.4 IRMA
In considering the problem of enabling agents to perform means-ends reasoning, to weigh competing alternative plans of action, and to cope with interaction between these two forms of reasoning in a resource-bounded way, Bratman proposed a high-level architecture, subsequently implemented as IRMA [17] This architecture, based on the BDI model, recognizes that agents will always be computationally limited or resource-bounded, and that suboptimal decisions may have to be made.
As with PRS, IRMA explicitly represents the beliefs, desires, and intentions of an agent as data structures in the system. In IRMA, once a plan has been selected for execution it becomes an active plan, and therefore an intention. IRMA's reasoning cycle is based around five key processes, comprising the opportunity analyzer, the means-end reasoner, the compatibility filter, the filter override mechanism, and the deliberation process, described below.
Initially, IRMA perceives its environment and updates its beliefs. Then, using the opportunity analyzer it must check whether its current goals have been inadvertently achieved, whether existing intentions can no longer be realized, or whether new alternative plans can be proposed. Goals are achieved by presenting them to the means-end reasoner, which attempts to generate new subplans. Plans from both the opportunity analyzer and the means-end reasoner are passed to the filtering process made up of the compatibility filter and the filter override mechanism, which run in parallel.
The role of the compatibility filter is to ascertain whether new plans are consistent with the existing intentions of the agent. Typically, incompatible plans are discarded but, in some cases, if they satisfy certain properties, they can be passed to the deliberation process by the filter override mechanism instead. When the override mechanism intervenes in this way, existing incompatible intentions are suspended. Next, the deliberation process determines how the plans it is passed after filtering affect the current intention structure. This intention structure simply comprises plans that have been selected for execution, and may be updated to accommodate new plans, when appropriate.
IRMA has been demonstrated and tested in the Tileworld simulation environment [26], which showed that given appropriate overriding mechanisms, committing to plans by means of intentions is a useful strategy for effective agent behavior in a dynamic environment.
The real benefit of both IRMA and PRS is that they are built from a clear conceptual model of the relationship between beliefs, goals, intentions, and plans. One problem, however, is that neither architecture provides designers with guidance on how an agent makes decisions based on its mental state, nor do they provide general rules of how to construct agent plans before run time. In addition, although it is possible to simulate reactive behavior by building plans appropriately, this is not an efficient or effective way of doing so, since reactive responses can only take place at the end of each (quite long-winded) operation cycle of these agents.
No comments:
Post a Comment