2.1 Logic language

We use a first-order logic language consisting of an infinite set of symbols for predicates, constants, functions, and variables, obeying the usual formation rules of first-order logic. We start with the following basic definitions.

We assume the usual abbreviations: $$\[--><$> {{\rPhi }}\, \vee \,{{\rPhi ^{\prime}}} <$><!--$$ stands for $$\[--><$> \neg (\neg {{\rPhi }}\, \wedge \,\neg {{\rPhi ^{\prime}}}) <$><!--$$ ; $$\[--><$> {{\rPhi }}\, \rightarrow \,{{\rPhi ^{\prime}}} <$><!--$$ stands for $$\[--><$> \neg {{\rPhi }}\, \vee \,{{\rPhi ^{\prime}}} <$><!--$$ and $$\[--><$> {{\rPhi }}\, \leftrightarrow \,{{\rPhi ^{\prime}}} <$><!--$$ stands for $$\[--><$> ({{\rPhi }}\, \rightarrow \,{{\rPhi ^{\prime}}})\, \wedge \,({{\rPhi ^{\prime}}}\, \rightarrow \,{{\rPhi }}) <$><!--$$ . Additionally, we also adopt the equivalence $$\[--><$> \{ {{{{\rPhi }}}_{\rm{1}}},\, \ldots \,,{{{{\rPhi }}}_n}\} \, \equiv \,({{{{\rPhi }}}_{\rm{1}}}\, \wedge \, \cdots \, \wedge \,{{{{\rPhi }}}_n}) <$><!--$$ and use these interchangeably. In our mechanisms we use first-order unification (Fitting, Reference Fitting1990), which is based on the concept of substitutions.

Given an expression E and a substitution $$\[--><$> \sigma \, = \,\{ {{x}_1}/{{\tau }_1},\, \ldots, \,{{x}_n}/{{\tau }_n}\} <$><!--$$ , we use Eσ to denote the expression obtained from E by simultaneously replacing each occurrence of x_i in E with τ_i, for all $$\[--><$> i\, \in \,\{ 1,\, \ldots, \,n\} <$><!--$$ .

Unifications can be composed; that is, for any substitutions $$\[--><$> {{\sigma }_1}\, = \,\{ {{x}_1}/{{\tau }_1},\, \ldots, \,{{x}_n}/{{\tau }_n}\} <$><!--$$ and $$\[--><$> {{\sigma }_2}\, = \,\{ {{y}_1}/{{\tau ^{\prime}}_1},\, \ldots, \,{{y}_k}/{{\tau ^{\prime}}_k}\} <$><!--$$ , their composition, denoted as $$\[--><$> {{\sigma }_1}\, \cdot \,{{\sigma }_2} <$><!--$$ , is defined as $$\[--><$> \{ {{x}_1}/({{\tau }_1}{{\sigma }_2}),\, \ldots \,,{{x}_n}/({{\tau }_n}{{\sigma }_2}),{{z}_1}/({{z}_1}{{\sigma }_2}),\, \ldots \,,{{z}_m}/({{z}_m}{{\sigma }_2})\} <$><!--$$ , where $$\[--><$> \{ {{z}_1},\, \ldots, \,{{z}_m}\} <$><!--$$ are those variables in $$\[--><$> \{ {{y}_1},\, \ldots, \,{{y}_k}\} <$><!--$$ that are not in $$\[--><$> \{ {{x}_1},\, \ldots, \,{{x}_n}\} <$><!--$$ . A substitution σ is a unifier of two terms τ ₁, τ ₂, if $$\[--><$> {{\tau }_1}\sigma \, = \,{{\tau }_2}\sigma <$><!--$$ .

Thus, two terms τ ₁, τ ₂ are related through the unify relation if there is a substitution σ that makes the terms syntactically equal. We assume the existence of a suitable unification algorithm that is able to find such a substitution. Specifically, we assume the implementation has the following standard properties: (i) it always terminates (possibly failing—if a unifier cannot be found); (ii) it is correct; and (iii) it has linear computational complexity.

We denote a ground predicate as $$\[--><$> \bar{\varphi } <$><!--$$ . In our algorithms, we adopt Prolog's convention (Apt, Reference Apt1997) and use strings starting with a capital letter to represent variables and strings starting with a lower case letter to represent constants. We assume the availability of a sound and complete first-order inference mechanismFootnote ⁴ that decides if Φ′ can be inferred from Φ, denoted as $$\[--><$> {{\rPhi }}\, \models \,{{\rPhi ^{\prime}}} <$><!--$$ . In line with the equivalence mentioned before, we sometimes treat a set of ground predicates as a formula, or more specifically, as a conjunction of ground predicates. Hence, we will sometimes use the logical entailment operator with a set of ground predicates. Moreover, we assume the existence of a mechanism to determine if a formula Φ can be inferred from a set of ground predicates, and if so, under which substitution; that is, $$\[--><$> \{ {{\bar{\varphi }}_0},\, \ldots \,,{{\bar{\varphi }}_n}\} \, \models \,{{\rPhi }}\sigma <$><!--$$ .

For simplicity of presentation, we refer to well-formed atomic formulas as atoms. Now let Σ be the infinite set of atoms and variables in this language and let Σ be any finite subset of Σ. From these sets, we define $$\[--><$> {\rm{\hat{\brSigma }}} <$><!--$$ to be a set of literals over Σ, consisting of atoms and negated atoms, as well as constants for truth ( $$\[--><$>\top<$><!--$$ ) and falsehood (⊥). We denote the logic language over Σ and the logical connectives of conjunction (∧) and negation (¬) as $$\[--><$> {{{\cal L}}_{\rm{\rSigma }}} <$><!--$$ .

2.2 Planning

Now that the preliminary formalisms have been presented we can discuss the necessary background on automated planning. Automated planning can be broadly classified into domain independent planning (also called classical planning and first principles planning) and domain dependent planning. In domain independent planning, the planner takes as input the models of all the actions available to the agent, and a planning problem specification: a description of the initial state of the world and a goal to achieve—that is, a state of affairs, all in terms of some formal language such as STRIPS (Fikes & Nilsson, Reference Fikes and Nilsson1971). States are generally represented as logic atoms denoting what is true in the world. The planner then attempts to generate a sequence of actions which, when applied to the initial state, modifies the world so that the goal state is reached. The planning problem specification is used to generate the search space over which the planning system searches for a solution, where this search space is induced by all possible instantiations of the set of operators using the Herbrand universe Footnote ⁵, derived from the symbols contained in the initial and goal state specifications. Domain-dependent planning takes as input additional domain control knowledge specifying which actions should be selected and how they should be ordered at different stages of the planning process. In this way, the planning process is more focused, resulting in plans being found faster in practice than with first principles planning. Such control knowledge, however, also restricts the space of possible plans.

2.2.1 Planning formalism

In what follows we will, for simplicity, stick to the STRIPS planning language. The input for STRIPS is an initial state and a goal state—which are both specified as sets of ground atoms—and a set of operators. An operator has a precondition encoding the conditions under which the operator can be used, and a postcondition encoding the outcome of applying the operator. Planning is concerned with sequencing actions which are obtained by instantiating operators describing state transformations.

More precisely, a state s is a finite set of ground atoms, and an initial state and a goal state are states. We define an operator o as a four-tuple 〈name(o), pre(o), del(o), add(o)〉, where (i) $$\[--><$> name(o)\, = \,act(\vec {x}) <$><!--$$ , the name of the operator, is a symbol followed by a vector of distinct variables such that all variables in pre(o), del(o) and add(o) also occur in $$\[--><$> act(\vec {x}) <$><!--$$ ; and (ii) pre(o), del(o), and add(o), called, respectively, the precondition, delete-list, and add-list, are sets of atoms. The delete-list specifies which atoms should be removed from the state of the world when the operator is applied, and the add-list specifies which atoms should be added to the state of the world when the operator is applied. An operator 〈name(o), pre(o), del(o), add(o)〉 is sometimes, for convenience, represented as a three-tuple 〈name(o), pre(o), effects(o)〉, where $$\[--><$> effects(o)\, = \,add(o)\, \cup \,\{ \neg l|l\, \in \,del(o)\} <$><!--$$ is a set of literals that combines the add-list and delete-list by treating atoms to be removed/deleted as negative literals. We use effects(o)⁺ to denote the set of positive literals in effects(o) and effects(o)⁻ to denote the set of negative literals in effects(o). Finally, an action is a ground instance of an operator.

The result of applying an action o with effects effects(o) to a state S is a new state S′ in which the positive effects effects(o)⁺ are true and the negative effects effects(o)⁻ are false.

Definition 5 (Function R)The result of applying an action o to a state specification S is described by the function $$\[--><$>R\,:\,{{2}^{{\rm{\hat{\brSigma }}}}} \,\times \,{\bar {{ {\bf O}}}}\, \rightarrow \,{{2}^{{\rm{\hat{\brSigma }}}}} <$><!--$$ , where $$\[--><$> {\bar {{ {\bf O}}}} <$><!--$$ is the set of all actions (ground operators), which is defined as Footnote ⁶

$$R(S,o)\, = \,\left\{ \matrix{ {(S\backslash effects{{{(o)}}^{\rm{ - }}} )\, \cup \,effects{{{(o)}}^ + } } \hfill & {if\,\,S\, \models \,pre\,{\rm{(}}o{\rm{)}};} \hfill \cr {undefined} \hfill & {otherwise.} \hfill \right$$

□

Definition 6 (Function Res)The result of applying a sequence of actions to a state specification is described by the function $$\[--><$> Res\,:\,{{2}^{{\rm{\hat{\rSigma }}}}} \,\times \,{{{\bar {{ {\bf O}}}}}^{\bf {{\ast}}}} \, \rightarrow \,{{2}^{{\rm{\hat{\rSigma }}}}}, <$><!--$$ which is defined inductively as

$$\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!Res(S,\langle \rangle )\, = \,S$$

$$Res(S,\langle {{o}_1},{{o}_2},\, \ldots \,,{{o}_n}\rangle )\, = \,Res(R(S,{{o}_1}),\langle {{o}_2}, \ldots, {{o}_n}\rangle )$$

□

Thus, a planning problem following the STRIPS formalism comprises a domain specification, and a problem description containing the initial state and the goal state. By using the definitions introduced in this section, we define a planning instance formally in Definition 7. Here, the solution for a planning instance is a sequence of actions Δ which, when applied to the initial state specification using the Res function, results in a state specification that supports the goal state. The solution for a planning instance or plan is formally defined in Definition 8.

Definition 7 (Planning Instance)A planning instance is a tuple $$\[--><$> {\rm{\rPi }}\, = \,\langle {\rm{\brXi }},{\bf {{I}}},{\bf {{G}}}\rangle <$><!--$$ , in which:

• • $$\[--><$> \brXi \, = \,\langle {\rm{\rSigma }},{\bf {{O}}}\rangle <$><!--$$ is the domain structure, consisting of a finite set of atoms Σ and a finite set of operators O;

• • $$\[--><$> {\bf {{I}}}\, \subseteq \,{\rm{\hat{\brSigma }}} <$><!--$$ is the initial state specification; and

• • $$\[--><$> {\bf {{G}}}\, \subseteq \,{\rm{\hat{\brSigma }}} <$><!--$$ is the goal state specification.

□

Definition 8 (Plan)A sequence of actions $$\[--><$> {\rm{\rDelta }}\, = \,\langle {{o}_1},{{o}_2},\, \ldots \,,{{o}_n}\rangle <$><!--$$ is said to be a plan for a planning instance $$\[--><$> {\rm{\rPi }}\, = \,\langle {\rm{\brXi }},{\bf {{I}}},{\bf {{G}}}\rangle <$><!--$$ , or a solution for Π, if and only if $$\[--><$> Res({\bf {{I}}},{\rm{\rDelta }})\, \models \,{\bf {{G}}} <$><!--$$ Footnote ⁷. □

A planning function (or planner) is a function that takes a planning instance as its input and returns a plan for this planning instance, or failure, indicating that no plan exists for this instance. This is stated formally in Definition 9.

Definition 9 (Planning Function)A planning function is described by the function $$\[--><$> Plan\,:\,\{ {{{\rm{\rPi }}}_{\rm{1}}},\, \ldots \,,{{{\rm{\rPi }}}_n}\} \, \rightarrow \,{{{\bar {{ {\bf O}}}}}^{\bf {{\ast}}}} \, \cup \,\{ \:failure\:\}, <$><!--$$ where $$\[--><$> \{ {{{\rm{\rPi }}}_{\rm{1}}},\, \ldots \,,{{{\rm{\rPi }}}_n}\} <$><!--$$ is the set of all planning instances, which is defined as

$$Plan({\rm{\rPi }})\, = \,\left\{ {\matrix {{\rm{\rDelta }} \hfill & {{\rm{\rDelta }}\;is\,a\,plan\,for\,{\rm{\rPi }};} \hfill \cr {failure} \hfill & {otherwise.} \hfill \\\end{}} \right$$

□

We assume such a function exists. The only requirement for the result Δ of Plan(Π) is that it follows some consistency criteria (e.g., the shortest Δ). The most basic planning function is the forward search algorithm. An adapted version of the forward search algorithm (Ghallab et al., Reference Ghallab, Nau and Traverso2004, Chapter 4, page 70) is shown in Algorithm 2. The input for this algorithm is basically a planning instance, and the output is a solution for the instance. Algorithm 1 simply calls Algorithm 2 with an empty set as the last parameter, which is later used to keep track of the states visited so far during the search to avoid getting into an infinite loop (i.e., to guarantee termination)Footnote ⁸. First, Algorithm 2 finds all actions that are applicable in initial state I, and saves these in the set applicable (Line 5). From this set, an action is picked arbitrarily, and the result of applying this action in state I is taken as I′ (Line 11). Next, the algorithm is recursively called with the new state I′. If the recursive call returns a plan for $$\[--><$> \langle {\bf {{I^{\prime}}}},{\bf {{G}}},{\bf {{O}}}\rangle <$><!--$$ —i.e., the goal state is eventually reached after applying some sequence of actions to I′ (Line 2)—then the result of the forward search is attached to the end of action o, and the resulting sequence returned as a solution for the planning instance. Otherwise, a different action is picked from applicable and the process is repeated. If none of the actions in applicable can be used as the first action of a sequence of actions that leads to the goal state, then failure is returned.

2.2.2 HTNs

Unlike first principles planners, which focus on bringing about states of affairs or ‘goals-to-be’, HTN planners, like BDI systems, focus on solving abstract/compound tasks or ‘goals-to-do’. Abstract tasks are solved by decomposing (refining) them repeatedly into less abstract tasks, by referring to a given library of methods, until only primitive tasks (actions) remain. Methods are supplied by the user and contain procedural control knowledge for constraining the exploration required to solve abstract tasks—an abstract task is solved by using only the tasks specified in a method associated with it.

We use the HTN definition from Kuter et al. (Reference Kuter, Nau, Pistore and Traverso2009) (actually an STN from Ghallab et al., Reference Ghallab, Nau and Traverso2004, Chapter 11, pages 231–244, which is a simplified formalism useful as a first step for understanding HTNs) whereby a HTN task network is a pair $$\[--><$> {\cal H}\, = \,(T,C) <$><!--$$ where T is a finite set of tasksFootnote ⁹ to be accomplished and C is a set of ordering constraints on tasks in T that together make T totally ordered. Constraints specify the order in which certain tasks must be executed and are represented by the precedes relation: $$\[--><$> {{t}_i}\, \prec \,{{t}_j} <$><!--$$ means that task t_i must be executed before t_j. Conversely, the succeeds relation represents the opposite ordering: $$\[--><$> {{t}_i}\,{\succ}\,{{t}_j} <$><!--$$ means task t_i must be executed after t_j. A task can be primitive or compound/non-primitive, with each being a predicate representing the name of the task. All tasks have preconditions as defined before, specifying a state that must be true before the task can be carried out, and primitive tasks correspond to operators in first principles planning, which thereby have effects specifying changes to the state of the world. An HTN planning domain is a pair $$\[--><$> {\cal D}\, = \,({\cal A},{\cal M}) <$><!--$$ where $$\[--><$> {\cal A} <$><!--$$ is a finite set of operators and $$\[--><$> {\cal M} <$><!--$$ is a finite set of methods. A method describes how a non-primitive task can be decomposed into subtasks. We represent methods as tuples $$\[--><$> m\, = \,(s,t,{\cal H}') <$><!--$$ , where s is a precondition, denoted by pre(m), specifying what must hold in the current state for a task t (denoted task(m)) to be refined into $$\[--><$> {\cal H}'\, = \,(T^{\prime},C^{\prime}) <$><!--$$ (denoted network(m)); this involves decomposing t into new tasks in T′ by taking into account constraints in C′.

Intuitively, given an HTN planning problem $$\[--><$>\:\;{\cal P}\: = ({d} , {\bf {{I}}},{\cal D})<$><!--$$ , where $$\[--><$> {\cal D}\, = \,({\cal A},{\cal M}) <$><!--$$ is a planning domain, d is the initial task network that needs to be solved, and I is an initial state specification as in first principles planning, the HTN planning process works as follows. First, an applicable reduction method (i.e., one whose precondition is met in the current state) is selected from $$\[--><$> {\cal M} <$><!--$$ and applied to some compound task in (the first element of) d. This will result in a new, and typically ‘more primitive’ task network d′. Then, another reduction method is applied to some compound task in d′, and this process is repeated until a task network is obtained containing only primitive tasks. At any stage during the planning process, if no applicable method can be found for a compound task, the planner essentially ‘backtracks’ and tries an alternative reduction for a compound task previously reduced.

To be more precise about the HTN planning process, we first define what a reduction is. Suppose d = (T, C) is a task network, $$\[--><$> t\, \in \,T <$><!--$$ is a compound task occurring in d, and that $$\[--><$> m\, = \,(s,t^{\prime},{\cal H}') <$><!--$$ —with $$\[--><$> {\cal H}'\, = \,(T^{\prime},C^{\prime}) <$><!--$$ —is a ground instance of some method in $$\[--><$> {\cal M} <$><!--$$ that may be used to decompose t (i.e., $$\[--><$> t^{\prime}\, = \,t\sigma <$><!--$$ ). Then, reduce(d, t, m, σ) denotes the task network resulting from decomposing task t occurring in d using method m. Informally, such decomposition involves updating both the set T in d by replacing task t with the tasks in T′, as well as the constraints C in $$\[--><$> {\cal H} <$><!--$$ to take into account constraints in C′. For example, suppose task network $$\[--><$> {\cal H} <$><!--$$ mentions a task t ₁, a task t ₂, and the constraint $$\[--><$>{{t}_1}\, \prec \,{{t}_2}<$><!--$$ . Now if a method $$\[--><$> m\, = \,({{t}_1},\{ {{t}_3},{{t}_4}\}, \{ {{t}_3}\, \prec \,{{t}_4}\} ) <$><!--$$ is applied to $$\[--><$> {\cal H} <$><!--$$ , the resulting set of constraints will be $$\[--><$> \{ {{t}_3}\, \prec \,{{t}_2},{{t}_4}\, \prec \,{{t}_2},{{t}_3}\, \prec \,{{t}_4}\} <$><!--$$ .

The HTN planning process is described in Algorithm 3 (adapted from Ghallab et al. (Reference Ghallab, Nau and Traverso2004, Chapter 11, page 239)). We refer the reader to Ghallab et al. (Reference Ghallab, Nau and Traverso2004) and Kuter et al. (Reference Kuter, Nau, Pistore and Traverso2009) for a more detailed account of HTN planning.

Notice that, although both Algorithms 2 and 3 perform a non-deterministic search from an initial state until a certain goal condition holds, the goal condition in Algorithm 2 is an explicit world state, whereas in Algorithm 3 the goal condition is to reach a fully decomposed task network. This difference in the goal condition makes planning for HTNs significantly more practical than planning in STRIPS-like domains, since the search space is generally much smaller.

3.1 Plans and intentions

An agent's behaviours are encoded as plan rules that specify the means for achieving particular (implicit) goals, as well as the situations and events for which they are relevant. Plan rules contain a head describing the conditions under which a certain sequence of steps should be adopted, and a body describing the actions that the agent should carry out to accomplish the plan rule's goal. A plan rule's head contains two elements: an invocation condition, which describes when the plan rule becomes relevant as a result of a triggering event; and the context condition encoding the situations under which the plan rule is applicable, specified as a formula. Each step in a plan rule body may either be an action (causing changes to the environment) or a (sub)goal (causing the addition of a new plan from the plan library to the intention structure). Interleaving actions and subgoal invocations allows an agent to create plans using hierarchy of alternative plans, since each subgoal can be expanded using any one of a number of other plan rules whose invocation condition matches the subgoal. Finally, the plan library, defined below, stores all the plan rules available to the agent.

In Example 1, we illustrate how a plan library affects an agent's behaviour.

• • 〈+!move(B), at(A) ∧ ¬ same(A, B), [packBags; +!travel(A, B)]〉

• • 〈+!move(B), at(A) ∧ same(A, B), []〉

• • 〈+!travel(A, B), has(car), [drive(A, B)]〉

• • 〈+!travel(A, B), has(bike), [ride(A, B)]〉

• • 〈+!travel(A, B), $$\[--><$> \top <$><!--$$ , [walk(A, B)]〉

When an agent $$\[--><$> \langle Ag,[ + !travel(home,office)],Bel,Pl,Int\rangle <$><!--$$ (cf. Definition 10) using this plan library adopts an achievement goal to travel to a location (by generating event +!travel(home, office), it will be able to adopt one of three possible concrete plans, depending on the availability of a mode of transportation encoded in its beliefs. ▪

An agent interacts with the environment through (atomic) actions, which are invoked from within the body of plan rules to bring about desired states of affairs. An action basically consists of an action name and arguments, or more specifically, a first-order atomic formula. Thus, if walk is an action to walk from one place to another that takes two parameters, an instance of this action to walk from home to the office could be denoted by walk(home, office).

• • ϕ, the identifier, is a first-order predicate $$\[--><$> p({{\tau }_0},\, \ldots, \,{{\tau }_k}) <$><!--$$ where $$\[--><$> {{\tau }_0},\, \ldots, \,{{\tau }_k} <$><!--$$ are variables;

• • $$\[--><$> \hslant20%\varpi <$><!--$$ , the precondition, is a first-order formula whose free variables also occur in $$\[--><$> \varphi <$><!--$$ ;

• • ε is a set of first-order predicates representing the effects of the action. Set ε is composed of two sets, ε ⁺and ε ⁻. These sets represent new beliefs to be added to the belief base (members of ε ⁺), or beliefs to be removed from the belief base (members of ε ⁻);

• • all free variables occurring in ε must also occur in $$\[--><$> \hslant20%\varpi <$><!--$$ and $$\[--><$> \varphi <$><!--$$ .

For convenience, we refer to an action by its identifier, $$\[--><$> \varphi <$><!--$$ , and to the preconditions of an action $$\[--><$> \varphi <$><!--$$ a $$\[--><$> \hslant20%\varpi (\varphi ) <$><!--$$ and to its effects as $$\[--><$>{\epsilon}(\varphi )<$><!--$$ . We refer to the set of all possible actions as Actions.□

Hence, an agent's action as defined above is equivalent to a STRIPS-like planning operator described in Section 2.2.1. An agent's actions are stored in a library of actions $$\[--><$> {\cal A} <$><!--$$ available to the agent.

Plans that are instantiated and adopted by an agent are called intentions. When an agent adopts a certain plan as an intention, it is committing itself to executing the plan to completion. Intentions are stored in the agent's intention structure, defined below.

It is important to note that the intention structure may contain multiple intentions organised in a hierarchical way. Each individual intention is a stack of steps to be executed, with the next executable step being the one at the top of the stack. As an agent reacts to an event in the environment, it creates a new intention with the steps of the plan chosen to achieve the event comprising the initial stack of this intention, so their steps can be immediately executed. The steps of a plan adopted to achieve a subgoal of an existing intention are stacked on top of the steps already on the intention stack, so that its steps are executed before the rest (beginning after the subgoal) of the original intention.

3.2 Interpreter and control cycle

In this section we describe the mechanisms needed for BDI-style computational behaviour. Here, we specify a basic abstract BDI agent interpreter and subsequently extend it to incorporate different styles of planning. The abstract interpreter is shown in Algorithm 4; we describe each step in more detail below.

The first two steps are for updating events and beliefs, described in Algorithms 5 and 6. Updating events (Algorithm 5) consists of gathering all new events from the agent's sensors (Line 2) and then pushing them into the event queue (Line 3), whereas updating beliefs (Algorithm 6) consists of examining the set of events and then taking appropriate actions with the corresponding beliefs: either adding beliefs when the events are of the form $$\[--><$> + \bar{\varphi } <$><!--$$ (as shown in Line 4), or removing them when they are of the form $$\[--><$> - \bar{\varphi } <$><!--$$ (as shown in Line 5)Footnote ¹³. We are not concerned here with more complex belief revision mechanisms (e.g., Gärdenfors, Reference Gärdenfors2003), but such an interpreter could use them.

Selection of plans to deal with new events is shown in Algorithms 7 and 8, which starts by removing an event e from the event queue and checking it against the invocation condition t of each plan in the plan library (Lines 3, 4 in Algorithm 7) to generate the set of options Opt. To this end, if an event e unifies with invocation condition t of a plan $$\[--><$> {\cal P} <$><!--$$ from the plan library, via substitution σ, and the context cσ (i.e., σ applied to c) is entailed by the belief base Bel (Line 4), then the resulting substitution σ_pot and other information about the plan rule are combined into a structure and stored in Opt, as a possible option for achieving the associated goal.

After an option is chosen for execution, the substitution σ_opt that led to its selection is applied to the plan body bd (Algorithm 10), and added to the associated intention structure (Line 5), with no more plan rules selected for the new event. In the third line of Algorithm 10 (and in other algorithms where it is used), symbol int_e stands for the intention that generated event e Footnote ¹⁴. If the event is a belief update, a new intention will be created for it (Algorithm 9, Line 7); otherwise, the event is a subgoal for some existing intention and therefore the new intention is added to it (Algorithm 9, Line 5)Footnote ¹⁵. If there are no options available to react to an event, two outcomes for the intention that generated the event are possible. For test goals of the form $$\[--><$> + ?\bar{\varphi } <$><!--$$ , even if an option (plan) to respond to that test is not available, the test goal might still succeed if the belief being tested is supported by the belief base, in which case the only change to the intention that created the event is to compose the unifier of that belief test to it (Algorithm 8, Lines 8, 9). Finally, if the event being processed is not a test goal, and there are no options to deal with it (Algorithm 8, Line 11), the intention that generated the event has failed, in which case we must deal with the failure. Algorithm 13 illustrates a possible implementation of failure handling mechanism (Bordini et al., Reference Bordini, Hübner and Wooldridge2007), where events denoting the failure of achievement and test goals are generated.

After a new plan is adopted, Algorithm 4 executes a step from an arbitrary intention using function executeIntention(Int, Ev), detailed in Algorithm 11, and illustrated in Figure 1. This entails selecting one intention int from the intention structure and executing the topmost step of the stack. If this step is an action it is executed immediately in the environment, and if it is a subgoal the associated event is added to the event queue.

Figure 1 Executing plan steps

One possible implementation of an action execution mechanism based on Definition 5 is shown in Algorithm 12, in which the results of an agent's actions are directly pushed back into its event queue. Consequently, Algorithm 12 ‘short circuits’ the results of an action's execution to the perception of its effects entirely within the agent. We provide such a simple implementation to provide a readily understandable function that closes the loop for the agent reasoning mechanism—in a real system actions are executed in an environment, and an agent will perceive the results of its actions through events reflecting the changes that an action brings about to this environment. Thus, although we do not deal with issues regarding the environment in this paperFootnote ¹⁶, we note that the results of executing an action in most realistic multi-agent settings start to reach the agent asynchronously, possibly mixed with the results of its other actions and the actions of other agents acting concurrently in the same environment. Consequently, the complete implementation of action execution would involve a function in the agent interpreter that ultimately sends the actions executed by the agents to an implementation of the environment. Implementations of action execution can vary significantly, depending on what the underlying environment intends to model, and how the agent formalisms deal with the environment. Some agent formalisms (e.g., Sardiña et al., Reference Sardiña, de Silva and Padgham2006) make assumptions about actions being atomic, and the degree to which an agent receives any feedback about the direct effects of its own actions (i.e., a new perception is the direct result of an agent's own actions, or of others). Other agent formalisms assume that the environment functions according to a stochastic transition function (Schut et al., Reference Schut, Wooldridge and Parsons2002); hence the action implementation in the environment would include an element of chance. Thus if the preconditions of an action are met (Line 3), executing the action amounts to pushing the effects of the action onto the event queue (Lines 4–8).

This agent interpreter, and the processes upon which it is based, have a very low computational cost, as demonstrated by various practical implementations such as dMARS (d'Inverno et al., Reference d'Inverno, Luck, Georgeff, Kinny and Wooldridge2004), PRS (Ingrand et al., Reference Ingrand, Chatila, Alami and Robert1996), and Jason (Bordini & Hübner, Reference Bordini and Hübner2006).

Now, as we have seen, multiple events may occur simultaneously in the environment, and multiple intentions may be created by an agent as a result of these events, possibly resulting in multiple plan rules becoming applicable and adopted by the agent. Hence, two execution outcomes are possible: interleaved and atomic execution. In the former, plans in different intentions alternate the execution of their steps, in which case care must be taken to ensure that no two plans that may execute simultaneously have steps that jeopardise the execution of one another (e.g., actions in one plan might invalidate the preconditions of actions in a concurrent plan).

3.3 Limitations of BDI reasoning

One shortcoming of BDI systems is that they do not incorporate a generic mechanism to do any kind of lookahead or planning (i.e., hypothetical reasoning). In general, planning is useful when (Sardiña et al., Reference Sardiña, de Silva and Padgham2006): (i) important resources may be consumed by executing steps that are not necessary for a goal; (ii) steps are not reversible and may lead to situations from which the goal can no longer be solved; (iii) executing steps in the real world takes more time than deliberating about the outcome of steps (in a simulated world); and (iv) steps have side effects which are undesirable if they are not useful for the goal at hand.

Adopting intentions in traditional BDI interpreters is driven by events in the form of additions and deletions of either beliefs or goals. These events function as triggers for the adoption of plan rules in certain contexts, causing plans to be added to the intention stack from which the agent executes the plan's steps. In the process, the agent might fail to execute an atomic action or to accomplish a subgoal, resulting in the failure of the original plan's corresponding intention. On the other hand, an agent might execute a plan successfully and yet fail to bring about some result intended by the programmer. If a plan selected for the achievement of a given goal fails, the default behaviour of a traditional BDI agent is to conclude that the goal that caused the plan to be adopted is not achievable. Alternatively, modern interpreters such as JACK (Busetta et al., Reference Busetta, Rönnquist, Hodgson and Lucas1999) and Jason (Bordini et al., Reference Bordini, Hübner and Wooldridge2007) (among others) can try executing alternative plans (or different instantiations of the same plan rule) in the plan library until the goal is achieved, or until none of them achieve the goal. Here, the rules that allow the interpreter to search for effective alternative means to accomplish a goal, and verification of goal achievement must be explicitly encoded in the plan library by the programmer.

This control cycle (summarised in Figure 2) strongly couples plan execution to goal achievement. It also allows for situations in which the poor selection of a plan rule leads to the failure of a goal that would otherwise be achievable if the search for a plan rule was performed more intelligently. While such limitations can be mitigated through meta-level constructs that allow goal addition events to cause the execution of applicable plans in sequence (Georgeff & Ingrand, Reference Georgeff and Ingrand1989; Hübner et al., Reference Hübner, Bordini and Wooldridge2006a), and the goal to fail only when all plans fail, in most traditional BDI interpreters goal achievement is an implicit side effect of a plan being executed successfully. Although research on declarative goals (Winikoff et al., Reference Winikoff, Padgham, Harland and Thangarajah2002) aims to address this shortcoming from an agent programming language perspective, the problem remains that once an agent has run out of user-defined plans, the goal will fail.

Figure 2 Simplified BDI control cycle. Dashed lines represent failure recovery mechanisms

In order to address these shortcomings of BDI interpreters, as well as enable agents generate new behaviours at runtime, various planning mechanisms have been studied. The three approaches to planning that have been integrated into BDI agent systems are discussed next.

Lookahead on existing BDI plans: In this style of planning (e.g., Sardiña et al., Reference Sardiña, de Silva and Padgham2006; Walczak et al., Reference Walczak, Braubach, Pokahr and Lamersdorf2006), an agent is able to reason about the consequences of choosing one plan for solving a goal over another. Such reasoning can be useful for guiding the selection of plans for the purpose of avoiding negative interactions between them. For example, consider the goal of arranging a domestic holiday, which involves the subgoals of booking a (domestic) flight, ground transportation (e.g., airport shuttle) to a hotel, and hotel accommodation. Although the goal of booking a flight could be solved by selecting a plan that books the cheapest available flight, this will turn out to be a bad choice if the cheapest flight lands at a remote airport from where it is an expensive taxi ride to the hotel, and consequently not enough money is left over for accommodation. A better choice would be to book an expensive flight that lands at an airport closer to the hotel, if ground transportation is then cheap, and there is enough money left over for booking accommodation. By reasoning about the consequences of choosing one plan over another, the agent could guide its execution to avoid selecting the plan that books the cheapest flight. Such lookahead can be performed on any chosen substructures of goal-plan hierarchies; the exact substructures are determined by the programmer at design time.

Planning to find new BDI plans: The second way in which planning can be incorporated into the BDI architecture is by allowing agents to come up with new plans on the fly for handling goals (e.g., Despouys & Ingrand, Reference Despouys and Ingrand1999; Móra et al., Reference Móra, Lopes, Vicari and Coelho1999; Meneguzzi & Luck, Reference Meneguzzi and Luck2007; de Silva et al., Reference de Silva, Sardina and Padgham2009). This is useful when the agent finds itself in a situation where no plan has been provided to solve a goal, but the building blocks for solving the goal are available. To find a new plan, the agent performs first principles planning, that is, it anticipates the expected outcomes of different steps so as to organise them in a manner that solves the goal at hand. To this end, the agent uses its existing repertoire of steps, specifically, some combination of basic steps (e.g., deleting a file or making a credit card payment) and the more complex ones (e.g., a high-level step for going on holiday). Similarly, to how the programmer can choose substructures of a goal-plan hierarchy when looking ahead within existing plans, when planning from first principles the programmer is able to identify the points from which first principles planning should be performed. In addition, such planning could also be done automatically on, for instance, the failure of an important goal.

Planning in a probabilistic environment: By using a deterministic model of planning, even though the languages themselves are ostensibly designed to be suitable for an uncertain world, traditional BDI agent interpreters (Georgeff et al., Reference Georgeff, Pell, Pollack, Tambe and Wooldridge1999) must rely on plan libraries designed with contingency plans in case of failures in execution. While in theory these contingency plans could be designed perfectly to take into account every conceivable failure, the agent's reasoning does not take into consideration the failures before they actually happen, as there is no model of the non-determinism associated with the failures. In order to perform this kind of proactive reasoning about failures, it is necessary to introduce a model of stochastic state transition, and an associated planning model to the BDI interpreter. The implementation of such approaches range from automatically generating contingency plans (Dearden et al., Reference Dearden, Meuleau, Ramakrishnan, Smith and Washington2002) to calculating optimal policies for behaviour adoption using decision theory (e.g., using a Markov decision process (MDP); Bellman, Reference Bellman1957). In this way an agent adopting a plan takes into consideration not only a plan's feasibility but also its likelihood to be successful. Moreover, if the environment changes and the failure of certain plans become predictable, current BDI implementations have no mechanism to adapt its plan adoption policy to this new reality.

Unlike linear plans such as those explained in Section 2.2, contingency plans are branching structures where each branch is associated with a test on an agent's perception, leading to different sequences of actions depending on the state of the environment as the agent executes the plan. Optimal policies in MDPs consist of a function that associates the action with the highest expected reward for each state of the environment, usually taking into consideration an infinite time horizon. The two solution concepts for probabilistic planning domains are strongly related, as an optimal policy can be used to generate the tree structure corresponding to a contingency plan (Meuleau & Smith, Reference Meuleau and Smith2003). Within the context of this paper, we can associate the creation of contingency plans as a probabilistic approach to the creation of new BDI plans, whereas optimal policies can be used as probabilistic solution to the question of selecting a plan with the best chance of success.

4.1 Propice-plan

The Propice-plan (Despouys & Ingrand, Reference Despouys and Ingrand1999) framework is the combination of the IPP (Köhler et al., Reference Köhler, Nebel, Hoffmann and Dimopoulos1997) first principles planner and an extended version of the PRS (Ingrand et al., Reference Ingrand, Georgeff and Rao1992) BDI system. It includes extensions to allow an agent to anticipate possible execution paths for its plans, as well as the ability to update the planning process in order to cope with a dynamic world. Although plan rules (called operational plans in Propice-plan, or OPs) are very similar to the ones used in PRS, they differ in that a designer specifies a plan not only in terms of a trigger, context condition, and body (see Definition 13), but also includes a specification of the expected declarative effects of the plan rule. A Propice-plan agent contains three primary modules:

1. 1. an execution module $$\[--><$>{\cal E}_m<$><!--$$ responsible for selecting plans from the plan library and executing them, similarly to the agent processes described in Section 3.2;

2. 2. an anticipation module $$\[--><$> {{{\cal A}}_m} <$><!--$$ responsible for simulating the possible outcomes of the options selected; and

3. 3. a planning module $$\[--><$> {{{\cal P}}_m} <$><!--$$ responsible for generating a new plan when the execution module fails to find an option.

The way these modules interact during plan selection is illustrated in Algorithm 14. This algorithm is somewhat similar to the original plan selection of Algorithm 8 until Line 11. It differs in that plans from the plan library are not only filtered by their trigger and context condition into Opt, but also further filtered by the anticipation module $$\[--><$> {{{\cal A}}_m} <$><!--$$ . We discuss the $$\[--><$> {{{\cal A}}_m} <$><!--$$ module in more detail in Section 5.4, but for now assume that this module takes as input a set of options Opt, containing elements of the form $$\[--><$> \langle t,c,bd,{{\sigma }_{opt}}\rangle <$><!--$$ and returns one option anticipated to be executed without failure. If such a plan cannot be found, the remainder of the algorithm (from Lines 11 to 19) uses the planning module $$\[--><$> {{{\cal P}}_m} <$><!--$$ to construct a new plan rule from scratch. Specifically, the $$\[--><$> {{{\cal P}}_m} <$><!--$$ module uses the IPP planner to obtain a new PRS plan at runtime. To formulate plans, IPP uses the plan rules of PRS (augmented with their expected declarative effects), by treating these plan rules as planning operatorsFootnote ¹⁷. In particular, the precondition of a planning operator is taken as the context condition of the corresponding plan rule, and the postcondition of the planning operator is taken as the declarative effects of the corresponding plan rule. The goal state to plan for is the (programmer supplied) primary effect of the achievement goal that failed. Solutions found by IPP are returned to the $$\[--><$>{\cal E}_m<$><!--$$ , which executes them by mapping their actions back into ground plan rules. To this end an intention is created (Line 14) by including a test for the (ground) context condition of the plan found to ensure that when the intention is actually executed the context condition still holds. Recall from before that int_e in Algorithm 14 is the intention that generated event e.

4.2 X²-BDI

In an attempt to bridge the gap between agent logic theory and implementation (Móra et al., Reference Móra, Lopes, Vicari and Coelho1999) developed X-BDI, a logic-based agent interpreter implemented using the extended logic programming (ELP) with explicit negation formalism developed by Alferes and Pereira (Reference Alferes and Pereira1996). In turn, the ELP formalism has an implementation in Prolog that solves explicit negation using an extension of the well-founded semantics (WFS) (Alferes et al., Reference Alferes, Damasio and Pereira1995), and for which a proof of correctness existsFootnote ¹⁸. X-BDI (Móra et al., Reference Móra, Lopes, Vicari and Coelho1999) is one of the first agent models to include a recognisably declarative goal semantics. An X-BDI agent is defined in terms of a set of beliefs, a set of desires, a set of intentions, and a set of time axioms, that is, as a tuple $$\[--><$> {\cal A}g\, = \,\langle {\cal B},{\cal D},{\cal I},{\cal T}\:{\rm Ax}\:\rangle <$><!--$$ . In its original implementation, X-BDI uses the time axioms of event calculus (Kowalski & Sergot Reference Kowalski and Sergot1986), which also include the description of the actions available to the agent. Beliefs are represented as a set of properties defined in a first-order language, equivalent to that of Section 2.1 and expressed in event calculus; moreover, consistency between beliefs is enforced using the revision mechanisms of ELP. However, in keeping with the algorithmic presentation style of this paper, we simplify the explanation of X-BDI and do not refer to the event calculus representation directly. Instead, we consider beliefs as ground time-stamped logical atoms. In this paper, we consider an X-BDI belief base $$\[--><$> {\cal B} <$><!--$$ as an extension of the belief base (and its entailment relation) of Definition 12 to include the notion of time, and we use $$\[--><$> {\cal B}\,{{ \models }_T}\,{{\rPhi }} <$><!--$$ to denote first-order formula Φ being entailed by the belief base at time T Footnote ¹⁹. We denote the current time as Now and denote the set of properties at time T as $$\[--><$> {{{\cal B}}_T} <$><!--$$ . Desires represent all potential goals: those that an agent might adopt, with each desire $$\[--><$> d\, = \,\langle {{P}_d},\,{{T}_d},\,T,\,b{{d}_d}\rangle <$><!--$$ consisting of a desired property P_d (which the agent desires to make true), the time T_d at which the desired property should be valid, an unbound variable T denoting the time at which the desire was committed to an intention, and a body bd_d that conditions the adoption of the desire on a (possibly empty) conjunction of beliefs. Here, bd_d is analogous to the context conditions of the plans in a procedural BDI programming language such as the one described in Section 3. We capture the essence of the intention selection process from X-BDI in Algorithm 15.

Since the desires are not necessarily mutually consistent, it might be the case that not all of them are adopted at once by the agent; moreover, the agent has to filter possible goals at every reasoning cycle. To this end, X-BDI creates two intermediate subsets of desires before committing to intentions. The first subset consists of desires whose property P_d is not believed to be true by the agentFootnote ²⁰, and whose body rule is supported by the beliefs at the current time; this subset $$\[--><$> {\cal D}' <$><!--$$ is that of eligible desires (Line 2). X-BDI then selects a subset of the eligible desires that are both consistent among each other (Line 5) and possible: these are the candidate desires $$\[--><$> {{{\cal D}}_C} <$><!--$$ . A set of desires is deemed possible if there is a plan that can transform the set of beliefs so that the desired properties become true. These plans are obtained via a planning process for each element in the power set of eligible desires (Line 4). The planning problem given to the planner consists of a STRIPS domain specification $$\[--><$>{\rm{\brXi }<$><!--$$ (see Definition 7), the beliefs that are true at the current time, and the (combined) set of desired properties corresponding to element D in the power set of eligible desires (Line 8).

The set of intentions in X-BDI contains two distinct types of intention. Primary intentions are declarative goals in the sense that they represent the properties expressed as desires, which the agent has committed to achieving (Line 15). Commitment to primary intentions leads an X-BDI agent to adopt plans to achieve them. The steps of these plans comprise the relative intentions, which are analogous to procedural goals (Line 16). Thus, in X-BDI, an agent only starts acting (i.e., carrying out relative intentions) after a reasoning cycle that consists of filtering the set of desires so that a maximal subset of candidate desires is selected, and committing to these desires as primary intentions.

Unlike most of the agent architectures described in this paper, X-BDI does not include a library of fully formed plans, but rather a set of environment modification planning operators defined in event calculus analogous to those in Definition 14. So the possibility of a desire is verified by the existence of an explanation generated by logical abduction. Here, logical abduction refers to the process of generating a set of predicates (in this case, action descriptions in event calculus) that when added to the belief base entail the desired properties. Thus, in order to choose among multiple sets of candidate desires, X-BDI uses ELP constructs that allow desires to be prioritised in a logical revision process (cf., Móra et al., Reference Móra, Lopes, Vicari and Coelho1999)Footnote ²¹. This type of desire selection suffered from significant inefficiencies, in particular, due to the logical abduction process required to determine if a plan is possible. In order to address this, X²-BDI (Meneguzzi et al., Reference Meneguzzi, Zorzo and Mora2004a) improves on X-BDI by substituting the abduction process with a STRIPS planner based on Graphplan (Blum & Furst, Reference Blum and Furst1997).

4.3 AgentSpeak(PL)

To further enhance the ability of an agent to respond to circumstances unforeseen at design time when achieving its goals, (Meneguzzi & Luck, Reference Meneguzzi and Luck2007) has created an extended AgentSpeak(L) interpreter able to invoke a standard classical planner to create new plans at runtime. To this end, a new construct representing a declarative goal is introduced, which the designer may include at any point within a standard AgentSpeak plan. Moreover, BDI plans that can be used in the creation of new BDI plans are annotated offline with their expected effects (i.e., how the world would change if the plans were executed). Alternatively, if action descriptions (such as those from Definition 14) are available, expected effects could be extracted offline as done, for example, in Sardiña et al. (Reference Sardiña, de Silva and Padgham2006).

A declarative goal in AgentSpeak(PL) is a special event of the form $$\[--><$> + !goalconj([{{g}_1},\, \ldots, \,{{g}_n}]) <$><!--$$ , where $$\[--><$> {{g}_1},\, \ldots, \,{{g}_n} <$><!--$$ is a conjunction of logical literals representing what must be made true in the environment. The plan library of an AgentSpeak(PL) agent contains a special type of plan designed to be selected only if all the other standard plans to handle a declarative goal event have failed. Consequently, the computationally expensive process of planning from first principles is only used as a last resort, thereby making maximum use of standard AgentSpeak(PL) reasoning while still being able to handle situations not foreseen at design time. Enforcing the selection of the fallback plan as a last resort can be achieved in AgentSpeak-like interpreters through an appropriate Option Selection Function (Rao, Reference Rao1996). In the Jason-based (Bordini et al., Reference Bordini, Hübner and Wooldridge2007) implementation of AgentSpeak(PL) (Meneguzzi & Luck, Reference Meneguzzi and Luck2008), plan selection follows the order in which plans are added to the plan library at design time; thus the fallback plan is simply added last to the plan library. This fallback plan contains the action genplan that is associated with the planning process as follows:

$${ + !goalconj([{{g}_1},\, \ldots, \,{{g}_n}]): & true \cr & \leftarrow \;genplan([{{g}_1},\, \ldots, \,{{g}_n}]). \cr}$$

The action genplan performs three processes. First it converts the agent's plan library, beliefs, and a specified goal into a classical planning domain and problem. In this conversion, the agent's belief base is considered the initial state of a STRIPS planning problem and the declarative goal as the goal state. Each existing AgentSpeak plan is converted into a STRIPS planning operator named after the plan's invocation condition, using the plan's context condition as the operator's precondition and expected effects as the operator's effect. Second, genplan invokes the classical planner. Third, if the planner successfully generates a new plan, genplan converts the steps of the STRIPS plan into the body of a new AgentSpeak plan, pushing this new plan into the agent's intention structure. This planning approach was further extended by Meneguzzi and Luck (Reference Meneguzzi and Luck2008) with the addition of a method to introduce newly created plans to the agent's plan library through the generation of a minimal context condition, which ensures that the plan added to the plan library will only be invoked when it is possible to execute the plan to its completion (i.e., it assumes the downward refinement property; Bacchus & Yang, Reference Bacchus and Yang1993). Basically, this context condition is generated by constructing a data structure similar to the planning graph from Blum and Furst (Reference Blum and Furst1997) using only the actions in the plan, and propagating unsatisfied preconditions from each action back to the initial level of the graph.

Although AgentSpeak(PL)'s planning capability is realised through a planning action/function implemented outside the traditional reasoning cycle, conceptually, the AgentSpeak(PL) cycle can be understood in the context of our abstract agent interpreter, as illustrated in Figure 3. Thus, the plan selection function of Algorithm 8 can be modified to represent the operational semantics of AgentSpeak(PL) by adding, after the traditional event matching mechanism, calls to the three processes used by genplan, as shown in Algorithm 16.

Figure 3 Reasoning cycle for AgentSpeak(PL)

In more detail, the traditional option selection algorithm is first invoked in Line 4. In this line the set Plib′ is an initially empty global cache of previously generated plans. If this process fails to find any options, then the desired declarative goal associated with event e, the agent's belief base Bel, and its plan library Plib are converted to a STRIPS representation in Line 11. The resulting STRIPS domain Π is then used in the invocation of a classical planner in Line 12; if it successfully generates a plan, the resulting plan is converted into the body of an AgentSpeak plan in Line 14. Before this plan can be added to the plan library, a context condition is created by the generateContextFootnote ²² algorithm in Line 15. Finally, the newly created plan is added to the plan library, and then adopted as an intention.

4.4 Hybrid Planning Framework

In the Hybrid Planning Framework of de Silva et al. (Reference de Silva, Sardina and Padgham2009) (hereby referred to simply as the Hybrid Planning Framework), classical planning is added to the BDI architecture with the focus being on producing plans that conform to and re-use the agent's existing procedural domain knowledge. To this end, ‘abstract plans’ are produced, which can be executed using this knowledge, where abstract plans are those that are solely made up of achievement goals. The input for such a planning process is the initial and goal states as in classical planning, along with planning operators representing achievement goals. The effects of such an operator are inferred from the hierarchical structure of the associated achievement goal, using effects of operators at the bottom of the hierarchy as a basis. The authors obtain the operator's precondition by simply taking the disjunction of the context conditions of plan rules associated with the achievement goal.

One feature of abstract plans is that, as highlighted in Kambhampati et al. (Reference Kambhampati, Mali and Srivastava1998), the primitive plans that abstract plans produce preserve a property called user intent, which intuitively means that the primitive plan can be ‘parsed’ in terms of achievement goals whose primary/intended effects support the goal state. In addition, abstract plans also have the feature whereby they are, like typical BDI plans, flexible and robust: if a primitive step of an abstract plan happens to fail, another option may be tried to achieve the step.

The authors note, however, that producing abstract plans is not a straightforward process. The main issue is an inherent tension between producing plans that are as abstract as possible (or ‘maximally abstract’), while at the same time ensuring that actions resulting from their refinements are necessary (non-redundant) for the specific goal to be achieved. Intuitively, a higher level of abstraction implies a larger collection of tasks, thereby increasing the potential for redundant actions when the abstract plans are refined.

The authors explore the tension by first studying the notion of an ‘ideal’ abstract plan that is non-redundant while maximally abstract—a notion they identify as computationally expensive—and then defining a non-ideal but computationally feasible notion of an abstract plan in which the plan is ‘specialised’ into a new one that is non-redundant but also preserves abstraction as much as possible. More concretely, instead of improving an abstract plan by exploring all of its specialisations, the authors focus on improving the plan by exploring only the limited set of specialisations inherent in just one of its ‘decomposition traces’, and extracting a most abstract and non-redundant specialisation of the hybrid plan from this limited set.

For example, consider a Mars Rover agent that invokes a planner and obtains the abstract plan h shown in Figure 4(a)Footnote ²³. Consider next the actual execution of the abstract plan, shown in Figure 4(c). Now, notice that breaking the connection after sending the results for Rock2, and then re-establishing it before sending the results for Rock3 are unnecessary/redundant steps. Such redundancy is brought about by the overly abstract task PerformSoilExperiment. What we would prefer to have is the non-redundant abstract plan h′ shown in Figure 4(b). This solution avoids the redundancy inherent in the initial solution, while still retaining a lot of the structure of the abstract plans provided by the programmer. In particular, we retain the abstract tasks Navigate and ObtainSoilResults, which lets us achieve these tasks using different refinements to that shown here, if possible and necessary. Moreover, replacing each of PerformSoilExperiment and TransmitSoilResults with a subset of their components, removes the inherent redundancy.

Figure 4 (a) A redundant abstract plan h; (b) an abstract plan h′ with redundancy (actions in bold) removed; and (c) the execution trace of h

Then, the entire process for hybrid planning (de Silva et al., Reference de Silva, Sardina and Padgham2009) involves obtaining, via classical planning, an abstract plan that achieves a required goal state given some initial state. Specifically, the steps are as follows: (i) transform achievement goals in the BDI system into abstract planning operators by ‘summarising’ the BDI hierarchy, similarly to Clement and Durfee (Reference Clement and Durfee1999); (ii) call the classical planner of choice with the current (initial) state, the required goal state, and the abstract planning operators obtained in the first step; (iii) check the correctness of the plan obtained to ensure that a successful decomposition is possible—a necessary step due to the incompleteness of the representation used in the first transformation step; and finally, (iv) improve the plan found by extracting its non-redundant and most abstract part.

5.1 CANPlan

Considering the many similarities between BDI agent-oriented programming languages and HTN planning, Sardiña et al. (Reference Sardiña, de Silva and Padgham2006) formally defines how a BDI architecture can be extended with HTN planning capabilities. In this work, the authors show that the HTN process of systematically refining higher-level tasks until concrete actions are derived is analogous to the way in which a PRS-based interpreter repeatedly refines achievement goals with instantiated plans. By taking advantage of this almost direct correspondence, HTN planning is used to provide lookahead capabilities for a BDI agent, allowing it to be more ‘informed’ during plan selection. In particular, HTN planning is employed by an agent to decide which plans to instantiate and how to instantiate them in order to maximise its chances of successfully achieving goals. HTN planning does not, however, allow the agent to create new plan structures (Figure 5).

Figure 5 Summarised reasoning cycle of CANPLAN

An algorithm that illustrates the essence of the CANPlan semantics is shown in Algorithm 17Footnote ²⁴. Observe that the main difference between this algorithm and Algorithm 8 is Line 5, where HTN planning is used to select a plan in set Opt for which a successful HTN decomposition of its associated intention exists, with respect to the current belief base. To this end the forwardDecomp function (Algorithm 3) is called in Algorithm 18Footnote ²⁵. The inability of function forwardDecomp to find a plan is considered a failure, which is handled as in Algorithm 8. In arguments to forwardDecomp we use certain BDI entities (such as st) in place of the corresponding HTN representations, in line with the mapping shown in Table 1. Indeed, we assume the existence of a mapping function that transforms the relevant BDI entities into their corresponding HTN counterparts. We refer the reader to Sardiña et al. (Reference Sardiña, de Silva and Padgham2006) for the details.

Table 1 Comparison of BDI and HTN systems (Sardiña & Padgham, 2011)

Note that unlike the CANPlan semantic rules, Algorithm 17 performs HTN planning whenever a plan needs to be chosen for a goal. In CANPlan, on the other hand, HTN planning is only performed at user specified points in the plan library—hence, some goals may be refined using the standard BDI plan selection mechanism. Another difference compared to the semantics is that the algorithm does not re-plan at every step to determine if a complete, successful execution exists. Instead, the re-planning occurs only at points where goals are refined; the algorithm then executes the steps in the chosen plan until the next goal is refined. In both approaches, failure occurs in the BDI system when relevant environmental changes are detected, i.e., when the context condition in a chosen plan is no longer applicable within the BDI cycle. Consequently, environmental changes leading to failure may be detected later in the algorithm than in the semantic rules. In this sense, the algorithm seems to more closely capture the implementation discussed by Sardiña et al. (Reference Sardiña, de Silva and Padgham2006), which first obtains a complete HTN decomposition ‘tree’ and then executes it step by step until completion or until a failure is detected.

5.2 The LAAS-CNRS Architecture

Another system that uses an HTN-like planner to obtain a complete decomposition of a task(s) before execution is an integrated system used with (real and simulated) robots in human–robot interaction studies at the LAAS-CNRS (Alami et al., Reference Alami, Warnier, Guitton, Lemaignan and Sisbot2011). The integration combines a PRS-based robot controller with the Human-Aware Task Planner (HATP) (Alami et al., Reference Alami, Warnier, Guitton, Lemaignan and Sisbot2009) SHOP-like HTN planner. The algorithm for this approach is shown in Algorithm 19.

Goals to achieve are sent directly from the user to the PRS-based system, via a voice-based interface or an Android tablet. PRS then validates the goal (e.g., checks if the goal has already been achieved) and sends the goal, if valid, as a task for HATP to solve (Line 4). HATP first searches for a standard HTN solution—one composed of actions/primitive tasks—and then the plan found is post-processed by HATP into two semi-parallel streams of actions (Line 5): one for the agent to execute and the other for the human to execute, possibly with causal links between actions in the two streams to account for any dependencies (e.g., before executing an action the robot might have to wait for the human to execute an action that makes an object accessible to the robot). Basically, this step involves extracting a partially ordered plan from a totally ordered plan and then distinguishing actions that need to be done by a human from those that should be performed by the robot. To indicate to the human what actions he/she needs to execute the robot uses a speech synthesis module. Action execution is realised via PRS plans, which invoke functions that do more low-level geometric planning to achieve/execute the smaller steps such as robot-arm motions and gripper commands. More specifically, geometric planning is used here for things such as final object/grasp configurations and motion trajectories for the robot's arms, which takes into account constraints such as human postures, abilities, and preferences. Action execution is verified to check that their intended outcomes are satisfied, the failure of which triggers re-planning for the original goal.

5.3 Planning in Jadex

The work of Walczak et al. (Reference Walczak, Braubach, Pokahr and Lamersdorf2006) is another approach to merging BDI reasoning with planning capabilities, achieved through a continuous planning and execution approach implemented in the Jadex agent framework (Pokahr et al., Reference Pokahr, Braubach and Lamersdorf2005). The approach of Walczak et al. (Reference Walczak, Braubach, Pokahr and Lamersdorf2006) deviates significantly from traditional BDI systems in that an agent's desires are not seen as activities to be executed nor logically represented states to be achieved, but instead as inverse utility (i.e., cost) functions that assign a value to particular agent states (rather than environmental states). That is, each agent desire assigns a value to the states so that when different desires are adopted, the agent's valuation of the states changes.

Like in traditional BDI agents, goals in Jadex are specific world states that the agent is currently trying to bring about. However, unlike the logic-based representations used to specify the search space and the actions that modify the environment in the other approaches described in this paper, actions in Jadex define value-assignments to fields within objects in the Java programming language. Moreover, instead of using events to directly trigger the adoption of plans, Jadex uses an explicit representation of goals, each of which has a lifecycle consisting of the following states: option, suspended, and active. Adopted goals become options (and thus become eligible to create plans to adopt as intentions), which are then handed over to a meta-level reasoning component to manage the goal's state. This high-level view of Jadex's reasoning cycle is illustrated in Algorithm 20 and Figure 6. Given the representation of the environment state, Jadex uses a customised HTN-like planner that takes into account the agent's current goals and the functions specified by the agent's desires to refine goals into actions. This planning process takes as input a goal stack, the agent's current state, its desires, and a time deadline. Planning then consists of decomposing the goal stack into executable actions, while trying to maximise the expected utility of the resulting plan using a heuristic based on the distance from the current state to the goals and the expected utility of these goals.

Figure 6 Jadex overview (Pokahr et al., Reference Pokahr, Braubach and Lamersdorf2005)

5.4 Lookahead in Propice-plan

Similarly, to some of the systems already discussed that perform lookahead, the anticipation module $$\[--><$> {{{\cal A}}_m} <$><!--$$ of Propice-plan, introduced in Section 4.1, can also evaluate choices in advance and advise the execution module $$\[--><$> {{{\cal E}}_m} <$><!--$$ (as shown in Algorithm 14) regarding which plan choices are likely to be more cost effective (e.g., less resource intensive); moreover, the $$\[--><$> {{{\cal E}}_m} <$><!--$$ can detect unavoidable goal failures, that is, where no available options are applicable, and adapt PRS execution by ‘inserting’ instantiated plans to avoid such failure if possible. The anticipation module performs lookahead whenever there is time to do so: in the ‘blast furnace’ example domain used by Despouys and Ingrand (Reference Despouys and Ingrand1999) the agent system sometimes remains idle for hours between tasks.

When performing lookahead, the $$\[--><$> {{{\cal A}}_m} <$><!--$$ simulates the hierarchical expansion of PRS plans, guided by subgoals within plan bodies. The expansion is done with respect to the current state of the agent's belief base, which is updated along the way with effects of subgoals, similarly to how the initial state of the world is updated as methods are refined in HTN planning. Whenever there is a precondition of a plan having a variable whose value is unpredictable at the time of lookahead (e.g., a variable corresponding to the temperature outside at some later time in the day), and can only be determined when the variable is bound during execution, the different possible plan instances corresponding to all potential variable assignments are accounted for during lookahead.

To avoid possible goal failures, the $$\[--><$> {{{\cal A}}_m} <$><!--$$ searches for goals that will potentially have no applicable options, before the $$\[--><$> {{{\cal E}}_m} <$><!--$$ reaches that point in the execution. The $$\[--><$> {{{\cal A}}_m} <$><!--$$ then tries to insert during execution an instantiated PRS plan whose effects will aid in the precondition holding for some plan associated with the goal. The authors state that making such minor adaptations to the execution is more efficient than immediately resorting to first principles planning, which they claim is likely to be more computationally expensive. Consequently, first principles planning is only called when all attempts at using standard PRS execution coupled with the $$\[--><$> {{{\cal A}}_m} <$><!--$$ have failed.

6.1 MDPs

A state s is a truth-assignment for atoms in Σ, and a state specification S is a subset of $$\[--><$> {\rm{\hat{\rSigma }}} <$><!--$$ specifying a logic theory consisting solely of literals. S is said to be complete if, for every literal l in $$\[--><$> {\rm{{\rSigma }}} <$><!--$$ , either l or ¬l is contained in S. A state specification S describes all of the states s such that S logically supports s. For example, if we consider a language with three atoms a, b, and c, and a state specification $$\[--><$> S\, = \,\{ a,\,\neg b\} <$><!--$$ , this specification describes the states $$\[--><$> {{s}_1}\, = \,\{ a,\,\neg b,\,c\} <$><!--$$ , and $$\[--><$> {{s}_2}\, = \,\{ a,\,\neg b,\,\neg c\} <$><!--$$ . In other words, a state specification supports all states that are a model for it, so a complete state specification has only one model.

The specification formalism we use allows incomplete state specifications and first-order literals on the preconditions and effects of planning operators (incomplete state specifications can omit predicates that are not changed by an operator from its preconditions and effects, as opposed to requiring operators to include every single predicate in the language's Herbrand base)Footnote ²⁸.

We consider an MDP (adapted from Shoham & Leyton-Brown, Reference Shoham and Leyton-Brown2010) to be a tuple $$\[--><$> {\rm{\rSigma }}\, = \,(SS,\,A,\,Pr,\,R) <$><!--$$ , where SS is a finite set of states and A is a finite set of actions, Pr is a state-transition system that defines a probability distribution for each state transition so that, given $$\[--><$> s,s^{\prime}\, \in \,SS <$><!--$$ and $$\[--><$> a\, \in \,A <$><!--$$ , function $$\[--><$> P{{r}_a}(s^{\prime}|s) <$><!--$$ denotes the probability of transitioning from state s to state s′ when executing action a. R is a reward function (or utility function) that assigns a value $$\[--><$> r({{s}_i},\,{{a}_j}) <$><!--$$ to the choices of actions a_j in states s_i. The reward function is typically used to indirectly represent goal states in MDPs, making it possible to generate an optimal policy $$\[--><$> {{\pi }^\ast} <$><!--$$ that indicates the best action to take in each state. This optimal policy can be obtained through various methods that ultimately use the Bellman (Reference Bellman1957) equations to establish the optimal choices for particular search horizonsFootnote ²⁹. Although we define the reward function as taking an action and a state, which might lead one to believe that the reward function only describes the desirability of taking an action, the use of an action and a state is meant to allow the calculation of the reward of a state.

6.2 Converting BDI agents to MDPs

Schut et al. (Reference Schut, Wooldridge and Parsons2002) provides a high-level correspondence between the theory of partially observable Markov decision processes (POMDPs) and BDI agents, suggesting that one of the key efficiency features of BDI reasoning (that of committing to intentions to restrict future reasoning) can be used in POMDP solvers in order to address their inherent intractability. POMDPs are an extension of MDPs with the addition of uncertainty on the current state of the world; hence, when an agent is making decisions about the optimal action, it has no direct way of knowing what the current state $$\[--><$> s\, \in \,SS <$><!--$$ is, but rather, an agent perceives only indirect observations $$\[--><$> o\, \in \,O <$><!--$$ that have a certain probability of being generated in each state of the world, according to a conditional probability function Ω. Thus, while an MDP is defined as a tuple $$\[--><$> \langle SS,\,A,\,O,\,Pr,\,R\rangle <$><!--$$ with SS being a set of states, A a set of actions, R a reward function, and Pr a transition function, a POMDP has additional components: a set of observations O, and an observation emission probability function Ω, making it a tuple $$\[--><$> \langle SS,\,A,\,O,\,Pr,\,\Omega, \,R\rangle <$><!--$$ . While some of the components of MDPs and BDI agents are equivalent, others require the assumption that additional information about the environment be available. Most notably, BDI agents have no explicit model of the state transitions in the environment. In order to eliminate ambiguity, we shall refer to equivalent components present in both BDI and MDP with a subscript of the corresponding model, for example, the SS_mkv symbol for the set of states from a POMDP specification, and thus represent a POMDP as $$\[--><$> \langle S{{S}_{mkv}},\,{{A}_{mkv}},\,O,\,P{{r}_{mkv}},\,\Omega, \,R\rangle <$><!--$$ . Schut et al. (Reference Schut, Wooldridge and Parsons2002) defines a BDI agent as a tuple $$\[--><$> \langle S{{S}_{BDI}},\,{{A}_{BDI}},\,Bel,\,Des,\,Int\rangle <$><!--$$ , where SS_BDI is the set of agent states, A_BDI is the set of actions available to the agent, Bel is the set of agent beliefs, Des is the set of desires, and Int is the set of intentions. Moreover, a BDI agent operates within an environment, such that the environment transition function $$\[--><$> {{\tau }_{bdi}} <$><!--$$ is known. They establish first the most straightforward correspondences as follows:

• • states in a POMDP are associated with world states of a BDI agent, that is, $$\[--><$> S{{S}_{mkv}}\, \equiv \,S{{S}_{BDI}} <$><!--$$ ;

• • the set of actions in a POMDP is associated with the external actions available to a BDI agent, that is, $$\[--><$> {{A}_{mkv}}\, \equiv \,{{A}_{BDI}} <$><!--$$ —however, the way in which actions change the world (i.e., the transition function) is not known to the agent; and

• • since the transition between states as a result of actions is external to the agent, it is assumed that the environment is modelled by an identical transition function so that $$\[--><$> P{{r}_{mkv}}\, \equiv \,{{\tau }_{bdi}} <$><!--$$ .

Regarding the state correspondences, Schut et al. (Reference Schut, Wooldridge and Parsons2002) propose associating the agent beliefs Bel to the set of observations Ω, since an agent's beliefs consist mainly of the collection of events perceived from the environment. Other equivalences are harder to establish directly, for example, the reward function R from a POMDP does not easily correspond to an agent's desires Des, since the former is usually defined in terms of state and action combinations, whereas desires are often specified as a logic variable assignment that must be reached by an agent. Nevertheless, these variable assignments do represent a preference ordering over states of the environment, and consequently, they can be used to generate a reward function with higher values for states corresponding to desires. Using these equivalences, Schut et al. (Reference Schut, Wooldridge and Parsons2002) compares the optimality of a BDI agent versus a POMDP-based agent modelled for the TileWorld domain, concluding that, since POMDPs examine the entire state space, an agent following a POMDP policy is guaranteed to obtain higher payoff than a BDI agent, but only in domains that are small enough to be solved by POMDP solvers. Hence, there is a tradeoff between the optimality achievable by solving a POMDP problem versus the speed achievable by the domain knowledge encoded in a BDI agent.

Simari and Parsons (Reference Simari and Parsons2006) go into further detail in providing algorithms for bidirectional conversion between a BDI agent and an MDP, proving that they can be equivalently modelled, under the assumption that a transition function for actions in the environment is known (which is not often the case for BDI agents). The proof of the convertibility between these two formalisms is provided through two algorithms. For the MDP to BDI conversion Simari and Parsons (Reference Simari and Parsons2006) provides an algorithm that converts an MDP policy into a BDI plan body, which Simari and Parsons (Reference Simari and Parsons2006) call an intention plan or i-plan. The converse process is detailed by an algorithm that converts the steps of BDI plan bodies into entries of the MDP reward function. Both conversion processes rely on the assumption (common to most BDI implementations) that a plans’ successful execution leads to a high-reward (desired) state, and that the actions/steps in the plan provide a gradient of rewards to that desired state.

Thus, conversion from an optimal MDP policy consists of, for each state in the environment, finding a finite path through the policy that most likely leads to a local maximum. This local maximum is a reward state, and is commonly used as the head of a plan rule, whereas the starting state for the path is the context condition of the plan rule. Creation of this path is straightforward: since a policy specifies an action for each state in the environment, a path can be created by selecting an action; discovering the most likely resulting state from that action; and consulting the policy again until the desired state is reached. The sequence of actions in this path will comprise the body of the plan rule.

Converting a BDI agent to an MDP, on the other hand, consists of generating a reward function that reflects the gradient of increasing rewards encoded in each i-plan. For an individual plan $$\[--><$> {\cal P} <$><!--$$ with a body of length p and a base utility $$\[--><$> U({\cal P}) <$><!--$$ , assuming that the most likely state is reached after the ith actionFootnote ³⁰, the reward for this state is $$\[--><$> i\, \cdot \,U({\cal P}) <$><!--$$ . Converting an entire plan library involves iterating over the plans in the plan library in some fixed order (Lines 6–7 of Algorithm 21), thereby obtaining an ordered sequence of individual actions and expected states, from which the values of a reward function can be derived (Lines 8–11). Once the reward function is obtained, the resulting MDP can be solved using, for example, the value iteration algorithm (Bellman, Reference Bellman2003; Line 14).

6.3 Probabilistic plan selection based on learning

Singh et al. (Reference Singh, Sardina, Padgham and Airiau2010) provide techniques to learn context decision trees using an agent's previous experience. Although not ostensibly developed to perform planning in a probabilistic setting, the underlying assumption for this work is that the Boolean context conditions of traditional BDI programs are not enough to ensure effective plan selection, in particular, where the environment is dynamic. As a consequence Singh et al. (Reference Singh, Sardina and Padgham2010) proposes to extend (and possibly completely supplant) the context conditions used for the selection of applicable plans with decision trees trained using data from previous executions of each plan. Basically, as an agent executes instances of the plans in its plan library in multiple environment/world configurations, it builds a model of the expected degree of success for future reference during plan selection. In more detail, the training set for the decision tree of each plan in the plan library consists of samples of the form [w, e, o], where w is the world state composed of a vector of attributes/propositions, e is the vector of parameters of the triggering event associated with the plan, and o is the outcome of executing the plan, that is, either success or failure. Here, the set of attributes included in w from the environment is a user-defined subset of the full set of attributes for the entire domain, representing the attributes that are possibly relevant to plan selection. Learning of the decision tree happens online, so that whenever a plan is executed, data associated with that execution is gathered and the tree is rebuilt.

The leaves of a decision tree then indicate the likelihood of success for a plan in a certain world state given certain parameters. However, data in the decision tree alone is not sufficient to allow an agent to make an informed decision about the best plan to select to achieve a goal, since the confidence of an agent in a tree created with very little data, intuitively, should not be very high. Thus, one of the key issues addressed by Singh et al. is the determination of when a decision tree has accumulated enough data to provide a reliable measure of the success rate for a particular plan instantiation. This problem is of particular importance, since an agent must balance the exploitation of gathered knowledge with the exploration of new data when choosing a plan in a given situation. To address this, the authors develop a confidence measure based on an analysis of sub-plan coverage. This notion of coverage is based on the fact that BDI plans are often structured as a hierarchy of subgoals, each of which can be achieved by a number of different plans; consequently, coverage is proportional to the number of these possible ways of executing a plan for which there is data available.

Using the data stored in the decision trees, as well as the confidence measure of their coverage, an agent selects a plan probabilistically using a calculated likelihood of success with respect to a set of environment attributes and parameters. The confidence $$\[--><$> {\cal C}({\cal P},\,Bel,\,n) <$><!--$$ of a plan $$\[--><$> {\cal P} <$><!--$$ is calculated using the current world state (represented by the beliefs) and the last $$\[--><$> n\,\geq \,1 <$><!--$$ executions of $$\[--><$> {\cal P} <$><!--$$ .