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