Planning in BDI agents: a survey of the integration of planning algorithms and agent reasoning

We would like to thank Michael Luck for valuable input and discussions throughout the process of writing this paper, and Lin Padgham, Sebastian Sardiña, and Michael Luck for supervising our respective PhD theses, which formed the basis for this paper. We would also like to thank Félix Ingrand, Malik Ghallab, and Wamberto Vasconcelos for valuable discussions in the course of writing this paper in its current form. We are grateful to the anonymous reviewers for providing detailed feedback, which has helped improve this paper substantially. Finally, we thank the funding agencies that sponsored our respective PhDs: Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (under grant 2315/04-1) for Felipe and the Australian Research Council (under grant LP0882234) for Lavindra.

An exception is the PLACA language (Thomas, 1995), which has not been widely adopted.

That is, events perceived by a BDI agent using a traditional programming language are assumed to represent all the relevant perceptions for that particular agent, and not indirect observations from the environment that induce a probability distribution over a set of possible states.

This is because most agent interpreters assume that actions may fail, but do not have an explicit model of state transitions with probabilities.

Such mechanisms have a design space defined by the expressiveness of the language and complexity/decidability aspects—the more expressive the language, the fewer are the guarantees that can be given (Fitting, 1990). In particular, if we assume our first-order language is restricted to Horn clauses, then we can use Prolog's resolution mechanism (Apt, 1997).

Any formal language with symbols for constants and functions has a Herbrand universe, which describes all the terms that can be created by applying all combinations of constant symbols as parameters to all function symbols.

We use the notation $$\[--><$>{{ 2}^S} <$><!--$$ to denote the power set of $$\[--><$> S <$><!--$$ (Weisstein, 1999).

Recall from Section 2.1 that we sometimes treat a set of ground predicates as a formula.

More information regarding the properties of the forward search algorithm can be found in Ghallab et al. (2004: Chapter 4, pp. 70–72).

Actually, these tasks are labelled so that we can have duplicates and uniquely identify them when writing constraints. We omit this extra bit of detail to simplify the notation.

In the BDI literature, plan rules are often referred to as plans, and sometimes as BDI plans.

Note that the operational semantics of goal deletions are neither provided nor clear in Rao (1996). In Hübner et al. (2006b), an informal semantics for $$\[--><$> {-} !\varphi <$><!--$$ is given where it is used as a means to facilitate ‘backtracking’, that is, the trying of alternative plans on the failure of a plan to solve an achievement goal.

Here $$\[--><$>\bar{e} <$><!--$$ denotes a ground instance of event $$\[--><$> e <$><!--$$.

Note that in Algorithm 6 the same beliefs are likely to be added multiple times to the belief base, until their associated events are removed from the event queue in Algorithm 8. Indeed, Algorithm 6 can be made more efficient by, for example, keeping track of such associated events and not re-updating the belief base. We disregard such efficiency improvements for the sake of readability.

Note that this line is left vague because it is an uninteresting implementation-level detail. One possible way to implement this is by using the event queue to store not just events but also the intentions that generated them (see Line 12 of Algorithm 11).

Note that although all events are considered at once for belief updates, they are handled one per interpreter cycle for plan rule invocations to avoid unbounded computations.

We suggest reading Chapter 2 of Wooldridge (2002).

Actually, we assume that the plan library Plib provided as an argument to IPP is an extended version including information about expected declarative effects of plan rules, which could easily be obtained from a (global) lookup table, for instance.

This interpreter is now available from the XSB project: http://xsb.sourceforge.net/

The exact definition of this entailment relation involves the axioms of event calculus, which we omitted for readability. For details, please refer to Móra et al. (1999).

Because it is not rational to desire something that will come about regardless of one's actions.

The specifics of how this is implemented has been omitted for readability.

We refer the reader to Meneguzzi and Luck (2008) for the implementation of generateContext.

This figure is slightly adapted from de Silva et al. (2009).

We have kept the algorithm simple rather than trying to precisely capture the CANPlan semantics.

Note that we have, for brevity, kept intention creation implicit in this algorithm.

In systems such as CANPlan, for instance, actions are assumed to always succeed.

Or POMDP to account for incomplete sensing capabilities.

Similarly to the Herbrand universe, any formal language with a Herbrand universe and predicate symbols has a Herbrand base, which describes all of the terms that can be created by applying predicate symbols to the elements of the Herbrand universe.

We shall not go into the details of the Bellman equations and their solutions.

The state with the highest probability of being reached after executing the $$\[--><$> i <$><!--$$ actions in the plan.

We thank Lin Padgham for this insight.

We thank Sebastian Sardina and the group at University of Toronto for this idea.