Reasoning agents: intentional systems and BDI

1. Premises: which autonomy, which intelligence

The chapter opens by restating what Chapter 3 established. Computational agents are autonomous as they encapsulate the thread of control: they are independent of the computational environment as far as control is concerned; the flow of control does not pass through agent boundaries and only data crosses them; agents have no interface, cannot be controlled and cannot be invoked; and a MAS is an aggregation of multiple distinct loci of control interacting by exchanging information.

And then it asks the two questions this chapter answers. First: what about the other notions of autonomy? Autonomy with respect to other agents — social autonomy; with respect to the environment — interactive autonomy; with respect to humans — artificial autonomy; with respect to oneself — moral autonomy. Second: what is intelligence to autonomy? Any sort of intelligence? Which intelligence for which autonomy? Which intelligent architecture for which autonomy?

2. Actions and perception, formally

The classical definition: an intelligent agent is a computational system capable of autonomous action and perception in some environment, where actions are supposed to change the environment in order to meet the agent’s design objectives, and perception is the process by which the agent recognises the state of the environment so as to adapt its behaviour to it.

Two functions make this precise. The perception function is the agent’s ability to observe its environment; its outcome is a percept:

Perception : E → Per

mapping environment states to percepts. The action function represents the agent’s decision-making process; its outcome is an action:

Action : Per* → Ac

mapping sequences of percepts to actions. The asterisk is doing real work: the agent decides on the basis of everything it has perceived so far, not merely on the current percept.

Actions themselves are modelled by pre- and post-conditions. An agent has a repertoire of actions available, aimed at changing its environment; actions are applicable or not depending on the situation, so pre-conditions are conditions in the environment that must be met for an action to be applied; and actions are expected to affect the environment, so post-conditions are the expected outcomes in terms of changes to the environment.

3. Properties of the environment

Four dichotomies, which together determine how hard the agent’s job is:

The deck sets an exercise: playing chess versus car driving — which sort of environment in the two cases? Chess is accessible, deterministic, static in the relevant sense, and discrete; driving is none of those. That single contrast explains why chess fell to computation decades before driving did, and why Chapter 10 will have to spend a whole section relaxing exactly these four assumptions when it moves from classical planning to planning under uncertainty.

4. Functional vs reactive systems

A distinction imported from Harel and Pnueli [1985], and one of the most consequential in the chapter.

Functional systems are what classical software engineering deals with: systems that can be seen as functions with an input and an output, F : I → O — compilers being the example — with a relational view available.

Reactive systems aim at maintaining a continuous interaction with their environment. They cannot be described in a functional or relational way; they have instead to be described and specified in terms of their ongoing behaviour — operating systems being the example. And the consequence the deck marks: a reactive system engaging in a conceptually non-terminating relationship with its environment must continually make decisions that bring about long-term effects.

5. Reactivity, situatedness, proactiveness, social ability

The four typically-mentioned behavioural features, with the deck’s reminder that they can somehow be reduced to autonomy itself.

Reactivity. Applications in real-world domains are characterised by highly dynamic conditions: situations change, information is incomplete, resources are scarce, the actions performed are not deterministic in their effects. A reactive system maintains an ongoing interaction with its environment and responds to changes that occur in it — in time for the response to be useful. Purely reactive agents decide what to do without reference to their history: reaction is entirely based on the present, with no reference to past states, as in stimulus–response rules, giving action : E → Ac. A thermostat is a purely reactive agent.

Situatedness. Reactive models and state-less agency are not enough for entities engaged in dynamic environments, which continually face external events requiring adequate services and behavioural responses. Any “ground” model of action is strictly coupled with the context where the action takes place; an agent comes with its own model of action; therefore any agent is strictly coupled with the environment where it lives and interacts, by the very actions it is capable of.

Proactiveness. We need agents able to smartly adapt to their environment: autonomously readapting to changes, recognising opportunities, showing goal-oriented behaviour. Proactiveness is a generative approach: agents generate their objectives and attempt to achieve them; agents encapsulate control and the rule to govern it; agents are not driven solely by stimuli; agents take the initiative and make something happen, rather than waiting for something to happen.

Social ability. A MAS is an articulated world where we cannot go around attempting to achieve goals without taking other entities into account, and some goals can only be achieved with the cooperation of others. Social ability is the ability to interact with other agents, and possibly humans, via some kind of agent-communication means: speech acts [Searle, 1969], artefact-based interactions [Omicini et al., 2004], signals, environment traces [Parunak, 2006]. And coordination is social: cooperation, collaboration, but also competition with others.

6. Agents with state

To face these growing complexities, stateful agents can be conceived: agents with some internal data structure, typically used to record information about the environment state and history. Let I be the set of all internal states of the agent. The perception function is unchanged, Perception : E → Per; the action-selection function becomes a mapping from internal states to actions, Action : I → Ac; and an additional function Next : I × Per → I maps an internal state and a percept to an internal state.

Which yields the first control loop of the chapter:

Agent control loop (v. 1)
1: while true
2:    observe the environment state 'e' and generate a perception(e);
3:    update internal state model:
         i ::= next(i, perception(e));
4:    select an action to execute:
         action(i);
5: end while

And with it, the questions that drive the rest of the chapter: we now have the problem to define such agent states. How to build an effective internal state model? How to make it run? How to update it?

7. Intentional systems and the intentional stance

The answer proposed is to refer to human attitudes as intentional notions. When explaining human activity it is often useful to make statements such as: Lewis got rain tires because he believed it was going to rain; Charles is working hard because he wants to win his first world championship. These can be read in terms of folk psychology, by which human behaviour can be explained and predicted through the attribution of mental attitudes such as believing and wanting, hoping, fearing, and so on.

The philosopher and cognitive scientist Daniel Dennett coined the term intentional system to describe entities “whose behaviour can be predicted by the method of attributing to it belief, desires and rational acumen” [Dennett, 1971]. He identifies several grades:

1. a first-order intentional system has beliefs, desires, etc. — Carlos believes P;
2. a second-order intentional system has beliefs and desires about beliefs and desires, both its own and of others — Carlos believes that Charles believes P;
3. a third-order intentional system is then something like Carlos believes that Charles believes that Carlos believes P;
4. and so on.

Which entities can be described in terms of the intentional stance? Human beings are prone to provide an intentional stance to almost anything — sacrifices to ingratiate the benevolence of gods, animism. The licence for machines comes from McCarthy [1979]: ascribing mental qualities like beliefs, intentions and wants to a machine is sometimes correct if done conservatively, and is sometimes necessary to express what is known about its state; it is useful when the ascription helps us understand the structure of the machine, its past or future behaviour, or how to repair or improve it.

And Dennett’s own later formulation [Dennett, 2007] makes the instrumental character explicit: the intentional stance is the strategy of interpreting the behaviour of an entity — person, animal, artifact, whatever — by treating it as if it were a rational agent who governed its ‘choice’ of ‘action’ by a ‘consideration’ of its ‘beliefs’ and ‘desires’. The scare quotes around all these terms, he notes, draw attention to the fact that some of their standard connotations may be set aside in the interests of exploiting their central features: their role in practical reasoning, and hence in the prediction of the behaviour of practical reasoners.

8. Agents with mental states

Early agent theorists start from a strong notion of agents as intentional systems: agents explained in terms of mental attitudes or mental states; in their social abilities, the simplest consistent description of agents implied the intentional stance; agents contain an explicitly-represented — symbolic — model of the world, written somewhere in the working memory; and agents make decisions on what action to take in order to achieve their goals via symbolic reasoning. And the line that names the chapter: intentions connect reasoning with action.

Which domains make this worth it

Mental states are a worthwhile abstraction for developing agents to act effectively in a class of application domains characterised by various practical limitations and requirements [Rao and Georgeff, 1995]:

• at any instant of time there are many different ways in which the environment may evolve — the environment is not deterministic;
• at any instant of time there are many actions or procedures the agent can possibly execute — the agent is not deterministic either;
• at any instant of time the agent may want to achieve several objectives;
• the actions or procedures that best achieve the various objectives are dependent on the state of the environment, that is on the particular situation and context;
• the environment can only be sensed locally, so the internal world representation is partial and local;
• the rate at which the agent can reason and act is within reasonable bounds to the rate at which the environment evolves.

Read that list as an applicability condition. If your environment is deterministic, fully observable and static, mental states buy you nothing — a lookup table would do. The apparatus of beliefs, desires and intentions earns its cost exactly in the conditions listed.

Two families of architecture

The example given for the two is memorable and closes the loop with Chapter 5: bacteria versus rational humans.

Why bother modelling agents on mental states? Because it eases the development of agents exhibiting complex behaviour; provides a familiar, non-technical way of understanding and explaining agents; allows the developer to build MAS by adopting the perspective of a cognitive entity engaged in complex tasks — what would I do in the same situation?; simplifies construction, maintenance and verification of agent-based applications; and is useful when the agent has to communicate and interact with human users or other intelligent system entities.

Finally, the vocabulary. Epistemic states represent the agent’s knowledge — its knowledge of the world: percepts, beliefs. Motivational states represent the agent’s objectives — what it aims to achieve: goals, desires. And the process of selecting one action to execute among the many available, based on the actual mental states, is called practical reasoning.

9. Practical reasoning

First, the contrast that fixes the term:

Bratman’s formulation: practical reasoning is a matter of weighing conflicting considerations for and against competing options, where the relevant considerations are provided by what the agent desires, values or cares about, and what the agent believes [Bratman, 1987].

Practical reasoning consists of two main cognitive activities:

• deliberation — when the agent makes decisions on what state of affairs it desires to achieve. Its outcome is the intentions: what the agent desires to achieve, or what it desires to do;
• means-ends reasoning — when the agent makes decisions on how to achieve those states of affairs. Its outcome is the selection of a given course of actions: the workflow of actions the agent intends to adopt in order to achieve its own goals expressed as intentions.

Means-ends reasoning

The basic idea is to provide agents with three sorts of representation: of the goal or intention to achieve; of the actions or plans in the repertoire; and of the environment. Given the environmental conditions, means-ends reasoning aims at devising a plan that could possibly achieve the adopted goal or intention.

And a formulation worth underlining: the selected intention is an emergent property, reified at runtime by selecting a given plan for achieving a given goal — no determinism.

Which produces the second control loop:

Agent control loop (v. 2)
1: while true
2:    observe the world;
3:    update internal world model (beliefs);
4:    deliberate which intention to adopt next;
5:    use means-ends reasoning to get a plan for the given intention;
6:    execute the plan;
7: end while;

10. The role of intentions

Seven properties, and they are the most examinable list in the chapter because they are what distinguishes an intention from a mere desire or a mere plan.

Intentions versus desires

The adoption of an intention follows the rise of a given desire — that is, it follows the adoption of a given goal. But desires and intentions are different concepts, and Bratman’s example says it best [Bratman, 1990]:

“My desire to play basketball this afternoon is merely a potential influencer of my conduct this afternoon. It must live with my other relevant desires [...] before it is settled what I will do.”

“In contrast, once I intend to play basketball this afternoon, the matter is settled: I normally need not continue to weigh the pros and cons. When the afternoon arrives, I will normally just proceed to execute my intentions.”

11. Bounded rationality

Now the problem that shapes every real BDI interpreter. Agents have bounded resources — what is called bounded rationality. Deliberation and means-ends processes are not for free: they have computational costs, and the time taken to reason and the time taken to act are potentially unbounded. This harms agent fitness — the reactivity and promptness that is essential for the agent to survive.

Make it precise. If the agent starts deliberating at t0, begins means-ends at t1, begins executing a plan at t2 and ends executing at t3, then the time for deliberation is t_deliberation = t1 - t0 and the time for means-ends reasoning is t_meansend = t2 - t1.

Meanwhile, agent environments are supposed to be highly dynamic: many concurrent changes may occur during decision-making as well as during plan execution. The deliberated intention is surely worth pursuing at the precise time when the deliberation process starts, that is at t0. But at t1 the agent selects a goal or intention that would have been optimal if it had been achieved at t0. So the agent runs the risk that the intention selected is no longer optimal — or no longer achievable — by the time the agent has committed to it.

The deck then states, with some irony, the three conditions under which the naive agent would exhibit optimal behaviour:

1. when deliberation and means-ends reasoning take a vanishingly small amount of time;
2. when the world is guaranteed to remain essentially static while the agent is deliberating and performing means-ends reasoning, so that the assumptions underlying the choice remain valid until both are completed;
3. when an intention that is optimal when achieved at t0 — the time at which the world is observed — is guaranteed to remain optimal until t2, the time at which the agent has found a course of action to achieve it.

12. The BDI framework

BDI is quite generally accepted as one of the most popular and successful frameworks for agent technology [Dasgupta and Ghose, 2011]. It was defined by Rao and Georgeff [1992], its core notions are belief, desire and intention, and agents in this framework are typically referred to as BDI agents.

Besides these, the BDI model includes a plan library — a set of “recipes” representing the procedural knowledge of the agent — and an event queue, where events (either perceived from the environment or generated by the agent itself to notify an update of its belief base) and internal subgoals (generated by the agent while trying to achieve a desire) are stored.

The classical BDI abstract architecture [Rao and Georgeff, 1992] includes three dynamic and global structures representing beliefs, desires and intentions, along with an input queue of events. Update (write) and query (read) operations are possible upon the three structures; update operations are subject to compatibility requirements, since formalised constraints hold upon the mental attitudes. The events the system recognises can be external — coming from the environment — or internal, coming from some reflexive action; events are assumed to be atomic, and can be recognised after they have occurred.

13. BDI control loops

The deck gives the interpreter three more times, at increasing levels of precision. Reading them in sequence is the fastest way to understand what a BDI platform actually does — and Chapter 12 will show the same loop implemented in Java inside Jason.

Version 3: the practical one

Agent control loop (v. 3)                     [Rao and Georgeff, 1995]
1.  initialize-state();
2.  while true do
3.      options := option-generator(event-queue);
4.      selected-options := deliberate(options);
5.      update-intentions(selected-options);
6.      execute();
7.      get-new-external-events();
8.      drop-successful-attitudes();
9.      drop-impossible-attitudes();
10. end-while

Versions 4 and 5: the formal ones

The deck presents version 4 — “more formally, in some sense” — and immediately asks a good question about it: but it is not actually the same, is it? Version 4 collapses deliberation into a single deliberate(B), losing the option-generation step and the dropping of successful and impossible attitudes. Version 5 puts option generation and filtering back:

Agent control loop (v. 5)
1.  B := B0;
2.  I := I0;
3.  while true do
4.      get new percept p;
5.      B := brf(p, B);
6.      D := options(B, I);
7.      I := filter(B, D, I);
8.      pi := plan(B, I);
9.      execute(pi);
10. end-while

How deliberation is refined

The problem the refinement addresses: how can we make the reasoning procedures of deliberation and option generation sufficiently fast to satisfy the real-time demands placed upon the cognitive system? The answer is to decompose deliberation into two phases:

• option generation — the agent generates a set of possible alternatives, via a function options which takes the agent’s current beliefs and current intentions and determines a set of options, that is desires;
• deliberation proper — the agent chooses between competing alternatives and commits to the intention of achieving them, using a filter function.

Chosen options are then intentions, so the agent commits to the selected ones and executes them. And a set of practical notes: the strategy for deliberating between goals typically is in the hands of the agent developer; most BDI programming platforms provide mechanisms to describe under which conditions some goal should inhibit the others — goal formulae, typically first-order logic predicates indicating contexts and trigger conditions; and game theory can enter the picture here, maximising expected utilities.

The structure, and its three constructs

BDI architectures are based on: a set of beliefs; a set of desires or goals; a set of intentions — or better, a subset of the goals with an associated stack of plans for achieving them, these being the intended actions; a set of internal events, elicited by a belief change (update, addition, deletion) or by goal events (a goal achievement, or a new goal adoption); a set of external events, perceptive events coming from the interaction with external entities such as message arrival or signals; and a plan library, the repertoire of actions, as a further static component.

The three notions in detail:

14. Viewpoints and platforms

Three viewpoints over BDI are distinguished [Mazal et al., 2008], and knowing which one someone is speaking from prevents most confusions:

Platforms

Above the individual platforms sits JaCaMo [Boissier et al., 2013; Boissier et al., 2020], which integrates three platforms from top (meta-models) to bottom (technologies): Jason for programming agents [Bordini et al., 2007], CArtAgO for programming environments [Ricci et al., 2009], and Moise for programming organisations [Hübner et al., 2007] — for MAOP, multi-agent oriented programming. Note the correspondence with Chapter 4’s three key abstractions: agents, environment, society, each getting its own technology.

In Python, some frameworks are already available: PADE (Python Agent DEvelopment framework), SPADE (Smart Python Agent Development Environment) and SPADE-BDI; or the usual pattern-based approach can be used, to use agents in Python programs without agents in the Python language.

And the closing observation, worth quoting because it frames the whole of Chapter 11: AI agents are spreading everywhere — yet they are not BDI agents. For now, at least.

Lessons learnt

Intentional systems are a widely successful approach to model agency at every level, including software agents and multi-agent systems — mostly because they make use of goals as a first-class notion and of intentions as the core notion connecting reasoning and action through deliberation, thus providing a sound and coherent framework for agent intelligence and autonomy, along with a number of usable agent technologies.

Check your understanding