=Paper=
{{Paper
|id=Vol-494/paper-37
|storemode=property
|title=The ARTS Real-Time Agent Architecture
|pdfUrl=https://ceur-ws.org/Vol-494/ladspaper11.pdf
|volume=Vol-494
|dblpUrl=https://dblp.org/rec/conf/mallow/VikhorevAL09
}}
==The ARTS Real-Time Agent Architecture==
https://ceur-ws.org/Vol-494/ladspaper11.pdf
The ARTS Real-Time Agent Architecture
Konstantin Vikhorev Natasha Alechina Brian Logan
School of Computer Science School of Computer Science School of Computer Science
University of Nottingham University of Nottingham University of Nottingham
Nottingham, NG8 1BB, UK Nottingham, NG8 1BB, UK Nottingham, NG8 1BB, UK
Email: kxv@cs.nott.ac.uk Email: nza@cs.nott.ac.uk Email: bsl@cs.nott.ac.uk
Abstract—We present a new approach to providing soft real- an action should be performed within a particular interval
time guarantees for Belief-Desire-Intention (BDI) agents. We of an event occurring. Rather each application has to be
define what it means for BDI agents to operate in real time, individually tuned by the developer. There are also a number
or to satisfy real-time guarantees. We then develop a model
of real-time performance which takes into account the time by of hybrid agent architectures such as ROACS [5] and SIMBA
which a task should be performed and the relative priority of [6]. A hybrid architecture consists of an AI subsystem and
tasks, and identify the key stages in a BDI architecture which a low-level control subsystem connected by communication
must be bounded for real-time performance. As an illustration interface. Such systems attempt to improve responsiveness by
of our approach we introduce a new BDI architecture, ARTS, separating the ‘real-time’ aspects of the architecture from the
which allows the development of agents that guarantee (soft)
real-time performance. ARTS extends ideas from PRS and JAM high-level control. However while such systems can simplify
to include goals and plans which have deadlines and priorities, the development of agents for real-time environments, they
and schedules intentions so as to achieve the largest number of provide limited high-level support for managing the timely
high priority intentions by their deadlines. execution of tasks.
Index Terms—BDI Agents, Real-time guarantees, Task In this paper we present a new approach to Belief-Desire-
Scheduling, Priority, Deadline, ARTS.
Intention (BDI) architectures for real-time agents. We develop
a model of real time performance which takes into account
I. I NTRODUCTION
the time by which a task should be performed and the
The design of an agent system which can operate effectively relative priority of tasks, and identify the key stages in a BDI
in a real-time dynamic environment is a major challenge for architecture which must be bounded for real time performance.
multiagent research. The main difficulty in building real-time As an illustration of our approach we introduce a new BDI
agent systems is how to specify real-time constraints and architecture, ARTS, which allows the development of agents
how to ensure that the agent system meets these constraints. that guarantee (soft) real time performance. ARTS extends
As with other computational systems, agents are resource ideas from PRS and JAM to include goals and plans which
bounded because their processors have limited speed and have deadlines and priorities, and schedules intentions so as
memory. Traditionally, agents have been developed without to achieve the largest number of high priority intentions by
much attention to resource limitations. However such lim- their deadlines.
itations become important when an agent system operates The remainder of the paper is organised as follows. In
in a dynamic environment. The reasoning processes implicit section 2 we develop a notion of ‘real-time’ appropriate to
in many agent architectures may require significant time to agent-based systems. In section 3 we present our method for
execute (in some cases exponential time), with the result that any BDI architecture. In section 4 to illustrate our approach
the environment may change while the agent makes a decision the new real-time agent architecture ARTS is introduced. In
about which activity to pursue. Thus a decision made by section 5 we compare our methods with related approaches.
the agent may be wrong (incorrect, sub-optimal, or simply And, finally, in section 6 we conclude and outlined directions
irrelevant) if it is not made in a timely manner. for future research. discussion.
A number of agent architectures and platforms have been
proposed for the development of agent systems which must II. R EAL -T IME G UARANTEES
operate in highly dynamic environments. For example, the In real-time programming a distinction is made between
Procedural Reasoning System (PRS) [1] and PRS-like systems, hard real-time and soft real-time systems. In the context
e.g., PRS-CL [2], JAM [3], SPARK [4] have features such as of agent systems, hard real-time means that the agent must
metalevel reasoning which facilitate the development of agents process its inputs (i.e., facts and goals) and produce a response
for real time environments. However, to provide real time within a specified time. For an agent system which provides
guarantees, these systems have to be programmed for each hard real-time guarantees there is therefore a strict upper
particular task environment—there are no general methods bound on the time to process incoming information and pro-
or tools which allow the agent developer to specify that a duce a response. In soft real-time, the agent may not produce a
particular goal should be achieved by a specified time or that response within the specified time in all cases, i.e. timeliness
constraints may be violated under load and fault conditions goals are achieved by their deadlines. We consider each of
without critical consequences.1 For BDI agents, we would these changes in turn below.
argue that the relevant notion of ‘response’ is the achievement
A. Additional Information
of a high level goal. However, for agents in open environments,
providing hard real-time guarantees for anything other than the As discussed above, in order to provide real-time guaran-
internal operations of the agent is typically not possible, unless tees, each top-level goal must be associated with a deadline
we make strong assumptions about the characteristics of the which specifies the time by which the goal should be achieved.
agent’s environment. In this paper we therefore focus on soft We assume that the deadline for a goal is specified when the
real-time guarantees for achieving the agent’s top level goals. goal is generated by a user (or another agent), and is expressed
We assume that each of the agent’s top level achievement as a real time value in some appropriate units (milliseconds,
goals is associated with a (possibly infinite) deadline which minutes, hours etc.). By default, the plan selected to achieve
specifies the time by which the goal should be achieved. A set a top-level goal (and its subgoals and subplans) inherit the
of goals which can all be achieved by the deadlines is termed deadline of the top-level goal. However we allow the deadline
feasible. Which sets of goals are feasible will depend on the of the intention associated with the top-level goal to be
speed at which the environment changes, the capabilities of advanced by a plan, if the execution context of the plan is
the agent etc. In general, it may not be possible to achieve such as to suggest that an earlier deadline should be adopted
all of an agent’s goals by their deadlines. For example, goals for the goal. For example, a subgoal in a plan may be to
produced by users or other agents, or autonomously generated buy an item; if the store which sells the the item is about to
in response to an event in the agent’s environment, may result close, the deadline of the of the intention may be advanced
in a previously feasible set of goals becoming infeasible, if for the duration of the ‘buy an item’ subgoal so that it is
there is insufficient time to achieve each goal, or an agent may achieved while the store is open. For intentions associated
have no plan to achieve a particular goal. In such situations, with fact-invoked plans (i.e., plans triggered by the agent’s
it is frequently more important to achieve some goals than beliefs), the default deadline is infinity, as no a priori deadline
others. For example, the goal of submitting a conference paper can be associated with a fact independent of a belief context.
on time may be more important than a goal to get coffee before However, as with top-level goals, we allow the deadline of
the coffee shop closes. We therefore assume that each goal is intentions associated with fact-invoked plans to be advanced
associated with a priority which specifies the importance of by the invoked plan, if if the execution context of the plan is
achieving the goal. Priorities define a total preorder, , over such as to suggest that the response to the new fact warrants
goals. A set of goals g is said to be maximal if it is feasible an earlier deadline.2
and there is no other set of goals g 0 such that g 0 g for some Each top-level goal is also associated with a priority (e.g., a
suitable lifting of to sets of goals. We define a real-time BDI non-negative integer value, with larger values taken to indicate
agent as an agent which achieves a maximal set of goals, i.e., higher priority) which specifies the relative importance of
the largest number of high priority goals by their deadlines. achieving the goal. Each plan also has a plan priority which
specifies the relative utility of the plan for the triggering goal
III. C HANGES TO THE BDI A RCHITECTURE or belief. We assume that the agent always intends plans
with the highest priority and that goal and plan priorities are
In this section we outline the changes necessary to a BDI
commensurable (i.e., that the order over intention priorities is
architecture to implement a real-time BDI agent. We assume
independent of the belief context). For intentions associated
a simple generic BDI architecture in which an agent has
with fact-invoked plans, the priority is the plan priority of the
beliefs and goals, and selects plans (sequences of subgoals and
invoked plan.
primitive actions) in order to achieve its goals or in response
Each plan is also associated with a duration, an estimate of
to new beliefs. Once the agent has adopted a plan it becomes
the real time necessary to execute the plan. In order to define
an intention, and at each cycle the agent executes a single
durations, we assume that each primitive action has a timeout
step of one of its current intentions. To implement real-time
(specified by the agent developer) which defines the maximum
BDI agents within such an architecture, two main changes are
amount of real time required to perform the action. Actions
required: we must add additional information about goals and
which do not complete by their timeout are assumed to have
plans to support real time guarantees, and we need to change
failed. To the duration of an action we add the upper bound
the BDI execution cycle to ensure that the agent’s cycle time
on the deliberation cycle (see section III-B below) to give the
is bounded and that the maximum number of high priority
maximum amount of time necessary to select and execute the
1 Some computer systems (for example, real-time video) utilise a stricter action. The duration of a non-primitive activity within a plan
notion of real-time guarantees, where the precise time at which a response is the sum of the durations of its subplans (i.e., the duration
is produced matters [7], [8]. Hard real-time for this type of system requires of a top-level plan is the sum of the durations of all subplans
a response at an exact time rather than before a deadline, and soft real-time
means that the response time lies within a defined uncertainty range around
intended for the goal). Assuming the plan library is of fixed
the required time. However we would argue that, in agent based systems, size, we compute the durations of subplans as follows.
this stricter sense of real time guarantee is less appropriate; for many task
environments, the key requirement is that a goal is achieved before a deadline 2 For how deadlines are (re)computed in the ARTS architecture, see section
rather than exactly at a specific time. IV-C.
1) For every agent’s plan, we compute all possible variants executed in deadline order, earliest deadline first;
of an intention, leading by this plan. This can be 3) repeat 2 until no more intentions can be scheduled;
represented as a tree structure. For the moment, we 4) execute the next step of the first intention in the sched-
assume that there are no loops or recursion within plans. ule.
2) Leaf plans do not contain calls to other plans and include An intention is feasible if it can be inserted in the schedule
only the addition and deletion of goals and primitive in deadline order while meeting its own and all currently
actions, and their duration can be easily calculated from scheduled deadlines. If all intentions in the schedule had the
the time required for basic agent actions (see below) and same priority, then the resulting schedule must be feasible if
the timeouts on primitive actions. any schedule is, i.e., if a system is unschedulable with deadline
3) Starting from leaf plans we can estimate the duration of monotonic ordering then it is unschedulable with all other
each intention variant. The maximum and the minimum orderings [9]. This algorithm has a worst case complexity of
duration are the upper and the lower bound of the plan O(n), where n is the number of the agent’s intentions.
duration. There are two possible scheduling scenarios: pessimistic,
In case of plans with loops with undefined number of repe- which is based on the maximum duration of a plan and opti-
titions or recursion within the plan, the minimum duration is mistic, which is based on the minimum duration. Pessimistic
the shortest path through the tree structure and the maximum scheduling has limited applicability, as in most cases the maxi-
duration is infinity. In most cases, especially in a complex mum duration is equal to infinity. In many cases, it is therefore
system, we will not able to provide the exact upper bound more reasonable to implement an optimistic scheduler as this
estimation of duration. places no restrictions on the structure of plans. With optimistic
scheduling, even if the maximum duration of a plan is infinite,
B. Changes to the BDI Execution Cycle
it may still be scheduled, but can be descheduled if it becomes
We assume that the internal operations of the agent—adding infeasible (i.e., if the minimum duration of the plan is greater
or deleting a belief or goal, selecting a plan, adopting an than the deadline of the triggering goal given the currently
intention, selecting an intention to execute and executing a scheduled plans).
single step of the intention—require time bounded by the size
of the agent’s program and its beliefs and goals. Adding or IV. ARTS: AGENT R EAL -T IME S YSTEM
deleting a belief or goal, adopting an intention, and executing In this section ARTS, an implementation of the real-
a single step of an intention can be assumed to take constant time BDI agent architecture described above. ARTS is an
time. However selecting a plan and intention to execute agent programming framework for agents with soft real-time
are intractable in the general case, and it is necessary to guarantees; an ARTS agent will attempt to achieve as many
approximate the choices of an unbounded agent to limit the high priority tasks by their specified deadlines as possible.
agent’s cycle time. The syntax and execution semantics of ARTS is based that
To bound the time necessary to select a plan, we assume of PRS-CL [2] and JAM [3], augmented with information
that goals and plans are processed in order of priority. That about deadlines, priorities, and durations, and changes to the
is, for each goal in priority order, the highest priority plan interpreter to implement time bounded priority driven plan
for that goal is checked to see if it is both executable in the selection and deadline monotonic intention scheduling. ARTS
current belief context and feasible (has a duration less than is implemented in Java, and the current prototype imple-
the deadline of the triggering goal). If the plan is executable mentation includes the core language described below, and
and feasible, the agent immediately commits to the plan and implementations of some basic primitive actions. Additional
processing moves to the next goal. If the plan is not executable user-defined primitive actions can be added using a Java API.
or feasible matching continues for the current goal with the In the interests of brevity, we have omitted the meta-level
next plan in priority order. Plan selection stops when all goals features of ARTS.
have an executable feasible plan or a user definable plan An ARTS agent consists of five main components: a
selection timeout is reached. At this point the agent has zero database, a goal stack, a plan library, an intention structure, and
or more executable, feasible plans, which are merged into the an interpreter. The database contains the agent’s current beliefs
intention structure, either as new top-level intentions (for plans (facts). The goal stack is a set of goals to be realised. The plan
triggered by new top-level goals or facts), or by adding them library contains a set of plans which can be used to achieve
to existing intentions. agent’s goals or react to particular situations. The intention
To bound the time necessary to select an intention to execute structure contains plans that have been chosen to achieve goals
at the current cycle, we utilise a deadline monotonic schedul- or respond to facts. The interpreter is the main component
ing algorithm which, while not optimal, gives preference to of the agent. It manipulates the agent’s database, goal stack,
urgent, high-priority intentions: plan library and intention structure and reasons about which
1) find the highest priority feasible intention, i.e., where plan to select based on the agent’s beliefs and goals to create
the remaining execution time is less than the deadline; and execute intentions. Changes to the agent’s environment or
2) find the next most important intention which is feasible posting of new goals invokes reasoning to search for plans that
for the existing schedule and assuming that tasks are might be applied to the current situation. The ARTS interpreter
Fig. 1. The execution cycle of ARTS agent
selects one plan from the list of applicable plans, intends and goals is given by:
schedules it, and executes the next step of first intention in the goal exp ::= achieve | conclude
computed schedule. achieve ::= “ACHIEVE” wff [pr] [dl]
{[by] | [not by]}“;”
conclude ::= “CONCLUDE” wff {[by] | [not by]} “;”
pr ::= “:PRIORITY” ground term
A. Facts dl ::= “:DEADLINE” ground term
by ::= “:BY” plan name+
The database of an ARTS agent contains facts (beliefs) that not by ::= “:NOT_BY” plan name+
represent the state of the agent and its environment. Facts where plan name is the name of a plan. The :PRIORITY
may represent information about state variables, sensory input, field of an :ACHIEVE top-level goal is optional and allows
derived information or information about other agents, etc. the specification of either a constant priority or an expression
which allows the calculation of the plan priority as function
fact ::= wff of plan variables (see below). The default priority of a top-
wff ::= pred name term exp∗ | (NOT wff ) level goal is zero. The :DEADLINE field is also optional and
| (AND wff + ) | (OR wff + ) allows the specification of the deadline of the goal. By default
term exp ::= value | variable | function the deadline is equal to infinity. CONCLUDE goals have zero
value ::= integer | float | string priority and an infinite deadline.
variable ::= “$”var name The developer can specify one or more top-level goals for
function ::= (fun name term exp+ ) the agent as part of the agent’s program using the keyword
where pred name, fun name and var name name predicated, “GOALS:”. For example:
functions and variables respectively. GOALS:
ACHIEVE PrepareLecture agents101 : PRIORITY 9 :DEADLINE 50;
ACHIEVE HaveLunch :PRIORITY 7 :DEADLINE 40;
ACHIEVE BorrowBook R&N :PRIORITY 2 :DEADLINE 30;
B. Goals Subgoals are goals generated within plans. ARTS has the
following subgoals operators:
ARTS distinguishes two categories of goals: top-level goals ACHIEVE C achieve condition C
and subgoals. ARTS supports two top-level goal operators: CONCLUDE F add fact F to the database
ACHIEVE and CONCLUDE. An ACHIEVE goal specifies TEST C test for the condition C
that the agent desires to achieve a particular goal state. A RETRACT F retract fact F from database
CONCLUDE goal inserts a certain fact into the database and WAIT C wait until condition C is true
possibly invokes a fact-invoked plan. The form of top-level In contrast to top-level goals, the deadline and priority of
plan ::= “PLAN: {”p name [p doc] p cue [p precond] [p cont]
ACHIEVE subgoals are not specified but inherited from the p body [p pr] [p dl] [p attr] “}”
plan containing the subgoal. p name ::= “NAME:” string“;”
p doc ::= “DOCUMENTATION:” [string]“;”
C. Plans p cue ::= “CUE:” p goal exp “;”
p precond ::= “PRECONDITION:” p cond∗ “;”
Plans define a procedural specification for achieving a p cont ::= “CONTEXT:” p cond∗ ”;”
goal. In specifying plans we distinguish between plan trigger p body ::= “BODY:” body elem∗
p pr ::= “PRIORITY”:” term exp “;”
variables and plan body variables. Plan trigger variables are p dl ::= “DEADLINE”:” term exp “;”
free variables appearing in the cue, precondition and context body seq ::= “{” body elem∗ “}”
fields, while plan body variables are variables appearing in body elem ::= activity | b and | b or | b parallel | b do all
| b do any | b do while | b while | b when
the body of the plan. Plan trigger variables must be ground activity ::= prim act | misc act | subgoal “;”
when the plan is selected, while binding of plan body variables b and ::= “AND:” body seq+ “;”
can be deferred to the execution of the corresponding plan b or ::= “OR:” body seq+ “;”
step. The agent’s plan library is introduced by the keyword b parallel ::= “PARALLEL:” body seq+ “;”
b do all ::= “DO_ALL:” body seq + “;”
“PLANS:” followed by a list of plans of the form: b do any ::= “DO_ANY:” body seq+ “;”
Name is an unique symbolic identifier of the Plan. b do while ::= “DO:” body seq “WHILE:” p cond“;”
Documentation is an optional field which used to store a b while ::= “WHILE:” p cond body seq “;”
b when ::= “WHEN:” p cond body seq“;”
descriptive text string. p goal exp ::= “ACHIEVE” wff | “CONCLUDE” wff
Cue specifies the purpose of the Plan and is used to select p cond ::= “ACHIEVE” wff | “TEST” wff
the plan for possible execution. The Cue field can contain subgoal ::= subgoal op wff ”;”
subgoal op ::= “ACHIEVE” | “CONCLUDE” | “TEST” | “RETRACT”
either an ACHIEVE or CONCLUDE goal. A ACHIEVE goal | “WAIT”
in the Cue field means that the Plan may be used to achieve prim act ::= “EXECUTE:” function [“:TIMEOUT” ground term]
some condition, while a CONCLUDE goal means that the Plan misc act ::= “ASSIGN:” term exp term exp
may be chosen for possible execution when a fact is added to TABLE I
P LAN BNF
the database.
Precondition specifies conditions that must be satisfied
for Plan to be applicable. This field is optional and can contain
both ACHIEVE and TEST goal expressions. An ACHIEVE G
it effectively advances the deadline for this intention during the
precondition means that the system must currently have G as
execution of the plan). If the specified deadline is later than
a goal in order for the Plan to be applicable, while a TEST
the deadline for the intention, the plan deadline is ignored.
C precondition means that C must be true for the Plan to be
ARTS, like JAM, supports standard programming constructs
applicable.
such as DO . . . WHILE (loop with postcondition) and WHILE
Context defines additional conditions (i.e. ACHIEVE and
construct (loop with precondition), choice constructs specified
TEST goal expressions) on plan execution. This field is
by OR (do any in order), AND (do all in order), DO_ALL (do
optional and has similar functionality to the Precondition
all randomly), DO_ANY (do any randomly), WHEN (conditional
field, but in contrast to the precondition it must be satisfied
execution), and ASSIGN (assignment to plan body variables).
before and during Plan execution. As in JAM, this significantly
The BNF for plans is given in table I.
increases the reactivity of the agent.
Body defines a sequence of simple activities (i.e. primitive
D. Primitive Actions
actions, addition and deletion of goals and facts), and com-
plex constructs (e.g. loops, (non)deterministic choice, etc, see The subgoal operators are implemented directly by the
below). ARTS interpreter. Other primitive actions are implemented
Priority specifies the relative utility of the Plan. The plan as Java methods. Each primitive action referenced in a plan
priority is used to choose between the applicable plans for body must have Java code which implements the neces-
a particular goal. The priority field is optional and allows sary functionality. ARTS supports two mechanisms for defin-
the specification of either a constant priority or an expression ing primitive actions: writing a class which implements the
which allows the calculation of the plan priority as function PrimitiveAction interface, and direct invocation of meth-
of variables appearing in the plan trigger. The default priority ods in existing legacy Java code. Primitive actions are executed
value is 0. by using an EXECUTE action.
Deadline specifies a deadline for the plan. The deadline In contrast to PRS-CL and JAM, ARTS allows the agent
field is optional and allows programmer to advance the dead- programmer to specify a timeout for each primitive action
line inherited from the triggering goal. The deadline can be by using the TIMEOUT keyword. The timeout specifies the
specified as a constant value or an expression which allows maximum amount of real time required to perform the action.
the calculation of the plan deadline as function of variables Actions which do not complete by their timeout are assumed
appearing in the plan trigger. If the specified plan deadline to have failed. For example:
is earlier than the deadline for this intention it becomes the
deadline for the intention during the execution of the plan (i.e., EXECUTE move to $x $y :TIMEOUT 50
GOALS:
E. Interpreter ACHIEVE PrepareLecture agents101 :PRIORITY 9 :DEADLINE 50;
The ARTS interpreter repeatedly executes the set of activi- ACHIEVE HaveLunch :PRIORITY 7 :DEADLINE 40;
ACHIEVE BorrowBook R&N :PRIORITY 2 :DEADLINE 30;
ties shown in Figure 1.
1) New goals are added to the goal stack and facts corre- CONCLUDE LectureNotes agents101 myNotes;
sponding to CONCLUDE goals and external events are PLAN: {
added to the database. NAME: “Plan 1”;
2) The precondition and context expressions of plans with DOCUMENTATION: “Prepare for lecture”;
CUE: ACHIEVE PrepareLecture $x;
a cue matching a goal on the goal stack are evaluated PRECONDITION: TEST LectureNotes $x, $y;
against the database to determine if the plan is applicable BODY:
in the current situation. Goals and plans are matched EXECUTE revise-lecture $y :TIMEOUT 35;
}
in priority order as described in section III-B. For
ACHIEVE goals, the interpreter checks to see whether PLAN: {
the goal has already been accomplished before trying to NAME: “Plan 2”;
DOCUMENTATION: “Pickup a book from the library”;
invoke a plan. CUE: ACHIEVE BorrowBook $x;
3) The resulting set of applicable plans are placed on the BODY:
intention structure. EXECUTE goto library :TIMEOUT 10;
ACHIEVE Pickup $x;
4) Intentions are scheduled according to their deadline and }
priority value as described in section III-B. Intentions
which are not schedulable, i.e., their minimum remain- PLAN: {
NAME: “Plan 3”;
ing execution time is greater than the time remaining to DOCUMENTATION: “Pick up something”;
their deadline, are either dropped or have their priority CUE: ACHIEVE Pickup $x;
reduced to zero.3 BODY:
EXECUTE pickup $x :TIMEOUT 2;
5) Finally, the interpreter selects the first intention from }
the computed schedule and executes the one step of
that intention. The result of the execution can be (5a) PLAN: {
NAME: “Plan 4”;
execution of a primitive action or (5b) the posting of a DOCUMENTATION: “Have lunch”;
new subgoal or the conclusion of some new fact. CUE: ACHIEVE HaveLunch;
BODY:
F. Example EXECUTE eat-sandwich :TIMEOUT 20;
}
In this section sketch as simple example ARTS agent E XAMPLE ARTS AGENT
and show how it allows the specification of soft real-time
requirements. The agent has three goals: preparing a lecture,
having lunch and picking up a book from the library. Each of the HaveLunch intention is checked. It is obvious that
task has a different priority and deadline. For simplicity, we the intention is infeasible, because it can’t be inserted to the
assume that actions never fail and that the unit of time is the schedule in deadline order together with first intention and it
minute. will be dropped. On the other hand the low priority intention
The algorithm for estimating the duration of a plan is is feasible and can be scheduled in deadline order together
executed when the agent is initialised. Plans have following with the first one. It is important to note that the low priority
maximum and minimum durations: d1 = 35min, d2 = 12min, task will be executed first, because it has an earlier deadline.
d3 = 2min, d4 = 20min. Once the durations of plans have Once the schedule has been computed, the interpreter executes
been estimated, the agent begins the reasoning cycle. The one step of the first task, i.e., goto primitive action, and starts
interpreter parses the initial top-level goals. It then attempts to a new cycle.
match them against the plan library in order to invoke suitable At the second cycle the interpreter executes next step, i.e.
plans. As a result Plan 1, Plan 2 and Plan 4 are added to the ACHIEVE Pickup goal. The goal invokes Plan 3 which
the intention structure. As explained above, plans inherit their inherits the deadline of 30 and priority of 2 from the top-
deadline and priority values from the triggering goal. This level goal and extends the existing intention. The interpreter
means that the intention related to the prepare lecture goal then performs one step of the plan 3. In the same way it
has the highest priority (9), the intention which corresponds performs action to revise the notes for the lecture from the
to the goal to have lunch has medium priority (7), and the next intention.
last intention related to the goal to pickup a book from the
library has the lowest priority (2). The scheduling algorithm V. R ELATED W ORK
checks feasibility of each intention before adding them to the
schedule. The first most important intention is inserted into The scheduling of intentions is key to realisation of real-
schedule, because it is currently empty. Then the feasibility time agents and a variety of intention scheduling approaches
have been explored in the literature. For example, AgentS-
3 This choice is currently determined by a global flag, rather than per goal. peak(XL) [10] and the Soft Real-Time Agent Architecture
[11] use the TÆMS (Task Analysis, Environment Modelling, can’t execute intentions in parallel. For plans containing asyn-
and Simulation) domain-independent framework [12] together chronous primitive actions or WAIT goals, this is clearly not
with Design-To-Criteria scheduling[13]. The TÆMS frame- the case. In future work, we plan to extend the scheduler to
work assumes a worth-oriented environment, in which goals handle asynchronous execution of intentions. Other directions
are associated with a degree of achievement (i.e., a goal for future work include improved algorithms for duration
may be not fully achievable or not achievable at all). The estimation and improvements to the basic BDI interpreter to
TÆMS framework allows modelling tasks with deadlines. The reduce the overall cycle time. It would also be interesting
problem of using DTC for scheduling agent intentions is that to explore probabilistic scheduling based on the most likely
an agent which implements DTC will not perform tasks in execution time of a plan as opposed to simply the lower and
some fixed order and is unable to compute a set of feasible upper bound.
tasks because the decision about which task (intention) will
R EFERENCES
be executed is based on some rating (real value between 0
and 1), which changes from cycle to cycle. Astefanoaei et al. [1] M. P. Georgeff and A. L. Lansky, “Procedural knowledge,” in IEEE,
vol. 74, no. 10. IEEE Press, 1987, pp. 1383–1398.
[14] extend the programming language BUpL to allow agents [2] K. L. Myers, PRS-CL: A Procedural Reasoning System. User’s Guide.,
to synchronise their actions by providing each agent with a SRI International, Center, Menlo Park, CA, March 2001.
set of clock variables. The clock value is used as a condition [3] M. J. Huber, “JAM: A BDI-theoretic mobile agent architecture,” in
Proceedings of The Third International Conference on Autonomous
for executing an action (or waiting). It is not related to the Agents, Seattle, WA, 1999, pp. 236–243.
agent’s deliberation cycle nor is it used for scheduling of a set [4] D. Morley and K. Myers, “The spark agent framework,” in Proc. of the
of possible actions. Third Int. Joint Conf. on Autonomous Agents and Multi Agent Systems
(AAMAS-04), New York, NY, July 2004, pp. 712–719.
There has been considerable work on approaches to the [5] J. S. Gu and C. W. de Silva, “Development and implementation of a
development of reasoning systems which must operate in real-time open-architecture control system for industrial robot systems,”
highly dynamic environments, e.g., [15], [16], [2], [3], [4]. Engineering Applications of Artificial Intelligence, vol. 17, no. 5, pp.
469 – 483, 2004.
Much of this work has focused on deliberation and reasoning [6] C. Carrascosa, J. Bajo, V. Julian, J. M. Corchado, and V. Botti, “Hybrid
strategies involving metalevel plans and facts for reasoning multi-agent architecture as a real-time problem-solving model,” Expert
about applicable plans, the failure to achieve a goal, changing Systems Applications, vol. 34, no. 1, pp. 2–17, 2008.
[7] J. Chakareski, J. Apostolopoulos, and B. Girod, “Low-complexity rate-
the intention structure according to user specified criteria, etc. distortion optimized video streaming,” in Proceedings of the Interna-
While metalevel reasoning provides great flexibility to the tional Conference on Image Processing (ICIP), vol. 3, Oct. 2004, pp.
agent developer, it can be complex and has to be programmed 2055–2058.
[8] S. G. Deshpande, “High quality video streaming using content-
for each particular application. In contrast, ARTS has its awareadaptive frame scheduling with explicit deadlineadjustment,” in
own well defined real-time reasoning mechanism for tasks MM ’08: Proceeding of the 16th ACM international conference on
with different priorities and deadlines, which does not require Multimedia. New York, NY, USA: ACM, 2008, pp. 777–780.
[9] C. Liu and J. Layland, “Scheduling algorithms for multiprogramming in
utilisation of metalevel capabilities. a hard real-time environment,” JACM, vol. 20, no. 1, pp. 46–61, 1973.
[10] R. Bordini, A. Bazzan, R. de, O. Jannone, D. Basso, R. Vicari, and
VI. C ONCLUSION V. Lesser, “Agentspeak(XL): efficient intention selection in BDI agents
via decision-theoretic task scheduling,” in In Proc. of AAMAS’02, 2002,
The main contributions of this paper are an analysis of pp. 1294–1302.
the meaning of real-time guarantees for a BDI agent, and [11] R. Vincent, B. Horling, V. Lesser, and T. Wagner, “Implementing soft
a proposal for a new BDI agent architecture, ARTS, for the real-time agent control,” in AGENTS ’01: Proceedings of the fifth
international conference on Autonomous agents. New York, NY, USA:
development of real-time BDI agents. ARTS is influenced by ACM, 2001, pp. 355–362.
the PRS family architectures, such as PRS-CL and JAM. How- [12] K. S. Decker and V. R. Lesser, “Quantitative modeling of complex en-
ever, unlike previous PRS-like architectures, ARTS includes a vironments,” International Journal of Intelligent Systems in Accounting,
Finance and Management, vol. 2, p. 215234, 1993.
duration estimation algorithm, priority driven plan selection [13] T. Wagner, A. Garvey, and V. Lesser, “Criteria-directed heuristic task
and a deadline monotonic intention scheduling algorithm. scheduling,” International Journal of Approximate Reasoning, vol. 19,
These features enable an ARTS agent to produce an intention pp. 91–118, Jyly 1998.
[14] L. Astefanoaei, F. S. de Boer, and M. Dastani, “On coordination, au-
schedule which achieves the greatest number of high priority tonomy and time,” in Proceedings of 8th International Joint Conference
goals by their deadlines. While the resulting schedule is not on Autonomous Agents and Multiagent Systems (AAMAS 2009), vol. 2,
necessarily optimal, it is computable in bounded time, and Budapest, Hungary, 2009, pp. 1357–1358.
[15] M. P. Georgeff and A. L. Lansky, “Reactive reasoning and planning,” in
we believe that the kind of “optimistic bounded rationality” Proceedings of the Sixth National Conference on Artificial Intelligence,
implemented by the ARTS architecture provides a simple, AAAI-87, 1987, pp. 677–682.
predictable framework for agent developers, facilitating the [16] M. P. Georgeff and F. F. Ingrand, “Managing Deliberation and Reasoning
in Real-Time Systems,” in In Proceedings of the DARPA Workshop on
development of agents which can perform tasks of different Innovative Approaches to Planning, San Diego, California, 1990.
complexity and scale while providing timely responses to
events in highly dynamic environments.
The current ARTS implementation has a number of limi-
tations. For example, the architecture currently assumes that
the agent must wait for the completion of each plan step
before recomputing the intention structure, i.e., the agent