-Time and uncertainty of the environment are very important aspects in the development of real world applications. Another important issue for the real world agents is, the balance between deliberation and reactivity. But most of the agent oriented programming languages ignore some or all of these important aspects. In this paper we try to fill this gap by presenting an extension to the architecture of CLAIM agent oriented programming language to endow the agents with the planning capability. We remove the assumption that agents' actions are instantaneous. We are interested in the temporal planning of on the fly goals. A coherrent framework is proposed in which agents are able to generate, monitor and repair their temporal plans. Our proposed framework creates a balance between reactivity and deliberation. This work could be considered as a first step towards a complete temporal planning solution for an AOP language.
Most of the agent oriented programming languages in the
current literature use a PRS like approach to achieve the goals
of agent. Some examples of these programming languages
are Jason[
In our proposed framework, we have made use of
Hierarchical Task Network (HTN) planning technique. The main
algorithm used to generate plan for a goal is JSHOP2[
The remainder of this paper is organized as follows. Section 2 puts some light on the current architecture of CLAIM language and JSHOP2 planner. In section 3, some important representations are presented which are helpful in understanding the agent architecture in P-CLAIM. Our proposed architecture of P-CLAIM agent with planning, execution and plan repairing components is presented in section 4. In section 5, we give an example to describe the working of system. Section 6 discussed some of the related work. Section 7 concludes the paper and some future directions are discussed.
In this section, we briefly discuss the architecture of CLAIM language and JSHOP2 algorithm to generate a plan. A multiagent system in CLAIM is a set of distributed hierarchies of agents deployed on computers connected via a network. All the computers have a global clock. With respect to the hierarchical representation, an agent is a node in a hierarchy. It is an autonomous, intelligent and mobile entity. It has a parent and contains (optional) sub-agents, running processes and cognitive elements (e.g. knowledge, goals, capabilities). An agent can dynamically create another agent, and the newly created agent becomes the sub-agent of the creator agent. In addition, an agent has three mobility primitives, in (enter another agent), out (leave another agent) and move (move from one hierarchy to another).
In CLAIM language, an agent can be defined as follows:
defineAgent agentName f
parent=null j agentName ;
knowledge=null j f (knowledge;)*g
goals=null j f (goal;)*g
messages=null j f (message;)*g
capabilities=null j f (capability;)*g
processes=null j f (process j )*g
agents=null j f (agentName;)*g
g
For a more detailed description of CLAIM language, we refer
to [
JSHOP2 is an HTN planning algorithm, and it deals with the procedural goals. Domain description required by JSHOP2 consists of methods and operators. A method indicates how to decompose a compound task into partially ordered subtasks. A method has three parts. The task for which the method is to be used, the condition which must be true in the current state to apply the method, and subtasks that need to be accomplished in order to accomplish that task. An operator is similar to the operators in classical planning and it tells how to perform a primitive task. It has a condition, a list of add effects and a list of delete effects. Planning proceeds by using the methods to decompose tasks recursively into smaller and smaller subtasks, until the planner reaches primitive tasks that can be performed directly using the planning operators.
The rationale behind choosing JSHOP2 for our work is
threefold. Firstly, it is an HTN planner and the domain
information from CLAIM can be easily transformed into the
domain information needed by the planner due to the
similarities among BDI like systems and HTN planning systems as
discussed in [
We have modified the domain representation in CLAIM
[
Goals in P-CLAIM are procedural goals. It means the goals of an agent are the tasks that agent wants to achieve. Some goals are initially given to the agent, when the multi-agent system is launched and some goals are given to the agent during the life of the agent using message passing by other agents or by user interaction. Goals have priorities associated with them. The priority of a goal could be Preemptive High, High or Normal. A goal having Preemptive High priority means that this goal should be immediately achieved by the agent, we also call this goal a reactive goal. High priority means that goal should be achieved before all the Normal priority goals currently present. Normal priority goals are the lowest priority goals. Goals with Preemptive High priority are stored in Global Reactive Goals (GRG) list and all other goals of agent are stored in a priority queue called Global Proactive Goals (GPG) list.
A message received by an agent in P-CLAIM has five parts. First part is the identity. Each message is assigned a unique number as identity. Second part is the sender, which represents the sender of the message. Thirdly, a message has a priority associated with it. This field has a value among Preemptive High, High and Normal. Fourthly, a message has a proposition which is the actual contents of the message. This proposition could be a new goal to achieve or it could be an information given to the agent which was demanded by the agent in an earlier message. Finally, a message has a ResponseTo field which is either blank or it contains a number pointing to the identity of an earlier message to which this message is responding.
The information needed by JSHOP2 algorithm to generate
the plan includes the initial state information, goals
information and domain description (methods and operators). In our
formalism, this information is automatically extracted from the
agent. Initial state information is taken from the knowledge of
the agent and from the hierarchical representation of MAS.
Goal for the Planner is a one to one mapping from agent’s goal
to Planner’s goal. In our framework, only one goal is passed to
the JSHOP2 algorithm at a time. Agent’s actions are mapped
to the operators in JSHOP2. P-CLAIM agent’s activities are
converted into JSHOP2 methods. For each activity of the
agent, an equivalent method is generated with the same name
as that of activity. Activity’s condition is mapped to the
method’s precondition. In JSHOP2, methods have subtasks.
Subtasks may be primitive tasks or other composite tasks.
Equivalently in P-CLAIM, the body of an activity consists
of different processes. So we need to convert these processes
into JSHOP2 methods and operators. To read in detail about
this conversion, we refer to our earlier article[
Each agent maintains a policy file in which it stores the importance of all other agents in the MAS for him. Importance of an agent depends on its position in the hierarchy relative to the position of the agent who is maintaining the policy. Importance also depends on the services provided by the agent during the life cycle of the agent. After receiving the message, the agent analyzes the policy file. Importance of the agent could be Normal or High.
There are concurrently four threads running inside the agent all the time. In the following subsections, we explain these threads in detail. Figure 1 is showing the architecture of an agent.
This thread is always waiting for the messages from other agents or from the user. It puts the messages into Planner Messages Queue(PMQ). These messages are either a request to achieve some goal or they are responses to some earlier sent message. After putting in the PMQ, these messages are fetched and analyzed. If the message contains some information demanded in an earlier message then this information is added to the knowledge of the agent along with an acknowledgement having the identity of the message in which this information was demanded. Agent’s treatment of a message, which is a request to achieve some goal, depends on the priority associated with message and the importance of sender.
The Messages Handler fetches the goal attached with a message and assigns a priority to the goal based on the priority associated with message and the importance of sender. A goal fetched from a message of priority Preemptive High or High which is assigned by an agent having Normal importance in the policy file is assigned a High priority. It means that agent does not preempt his own goals for the goals assigned by an agent of Normal importance. A goal fetched from a message, sent by an agent having High importance in the policy file is assigned the same priority as of the message. After assigning a priority to the goal, the goal is added to one of the two global goals lists. A goal of priority Preemptive High is added to GRG list and a goal of priority High or Normal is added to GPG list.
There is another messages queue maintained inside the agent, called Executor Messages Queue(EMQ). Messages which are sent by the Planner for the execution of actions are put in the EMQ. These are the triggering messages for the actions in the plan generated by the Planner. Number of messages in EMQ are denoted by length(EM Q) and EM Q[i] denotes the ith message in EMQ. Each triggering message in EMQ has a time stamp associated with it. T imeStamp(M sg) denotes the time stamp associated with a triggering message M sg.
Planner starts when the multi-agent system is launched. Once started, the Planner procedure runs throughout the life cycle of the agent. When there are no goals in either of the goals lists then it sits idle and waits for new goals to arrive and as soon as a new goal arrives, it starts planning. Before starting the Planner, the agent goes through an initialization phase, in which it sets the values of certain global variables.
Three states of the world are maintained in the system, SP (Act) which denotes the state of the world anticipated by planner just before the execution of the action Act, secondly SW is the current actual state of the world and F inalSP Algorithm 1 M ain Algorithm Algorithm 2 T reat Reactive Goal 1: Fetch first goal g 2 GRG 2: Suspension Signal ON 3: Wait until fExecution Signal = OF F g 4: Start T ime Current system time 5: RP lan Compute P lan(SW; g; D) 6: if RP lan 6= F ail then 7: for i = 1 To length(RP lan) do 8: T imeStamp(ExeM essages[i]) T imeStamp(RP lan[i]) 9: ExeM essages[i] T riggerM essage(RP lan[i]) 10: end for 11: End T ime Current system time 12: Duration End T ime - Start T ime 13: for i = 1 To length(EM Q) do 14: T imeStamp(EM Q[i]) T imeStamp(EM Q[i])
Duration 15: end for 16: Send ExeM essages to EMQ 17: end if + 18: Suspension Signal
OF F denotes the state of the world to which the Planner has planned till now. More precisely, it is the state of the world anticipated by planner after the very last action that the Planner has planned for. In the initialization phase F inalSP is set equal to the SW . Suspension Signal is set to OF F and Execution Signal is set to ON .
The M ain Algorithm (Algorithm 1) runs in an infinite loop and ensures that reactive goals are immediately planned for and achieved. First it looks at the GRG list and if it is not empty, (Lines 2-4) the control moves to the procedure T reat Reactive Goal (Algorithm 2). Some of the notations used inside the T reat Reactive Goal procedure are as follows. length(RP lan) denotes the number of actions in the plan RP lan. ExeM essages is an array of triggering messages for the actions in the plan. T imeStamp(Act) denotes the time stamp assigned to an action Act for its execution. T reat Reactive Goal fetches the first reactive goal g and sets the Suspension Signal to ON to ask the Executor to suspend the execution and waits for the Execution Signal to go OF F which indicates that the Executor has suspended the execution (Lines 1-3) then it calls the Compute P lan procedure to plan for the reactive goal (Line 5). The current
fg 2 LG : no other goal is constrained to precede gg else
M f(m; ) : m is an instance of a method in D, unifies fhead(m); gg, pre(m) is T rue in S, and m and are as general as possibleg if M = then
Return F ail end if Non deterministically choose pair (m; ) 2 M Modify LG by removing g, adding sub(m), constraining each goal in sub(m) to precede the goals that g preceded, and applying else if sub(m) 6=
LG0
then fg 2 sub(m) : no goal in LG precedes gg
end if end if if New acknowledgement in knowledge then id identity of the message whose acknowledgement has arrived Fetch all goals associated with message id from Pending Tasks list and put in the LG end if if G is a proactive goal then repeat
Call T reat Reactive Goal
until GRG =
end if
50: end loop
state of the world SW , the reactive goal just fetched g
and domain description D are passed to Compute P lan
procedure. This procedure call returns a temporal plan RP lan
for the reactive goal. Because every action in P-CLAIM is
executed using a triggering message, so an array ExeM essages
is generated containing the triggering messages for all the
actions in the temporal plan RP lan with a T imeStamp
associated with every message (Lines 7-10) and this array of
Algorithm 4 T emporal Converter(I; P; D)
1: for j = 1 TO no of literals(I) do
2: P roduction T ime(Literal(I[j])) 0
3: end for
4: for i = 1 TO length(P ) do
5: T imeStamp(P [i]) M ax fP roduction T ime(P re(P [i][j]))
:j = 1 To no of pre(P [i])g
6: P rereq(P [i]) Actions which achieve the preconditions of P [i]
7: SP (P [i]) World state anticipated before the execution of P [i]
8: for j = 1 TO no of ef f ects(P [i]) do
9: P roduction T ime(Literal(P [i][j])) T imeStamp(P [i])
+ Of f set(Literal(P [i][j]))
10: end for
11: end for
messages is sent to EMQ (Line 17) from where the Executor
executes the actions triggered by these messages. But before
sending ExeM essages to EMQ, the T imeStamp of all the
messages currently in the EMQ is updated, because due to
the suspension of execution, those triggering messages can
not be executed at their intended time. So every message’s
T imeStamp is increased by the duration of the suspension
(Lines 13-15). Suspension Signal is then set to OF F (Line
18) to allow the Executor to resume execution and control is
passed back to M ain Algorithm (Algorithm 1) which looks
for another goal in GRG. The M ain Algorithm turns its
attention to the proactive goals only when it finds that there is
no reactive goal (Line 5). Algorithm fetches the first goal from
GPG (Line 6). High priority goals are always fetched before
Normal priority goals. Then Compute P lan procedure is
called with the parameters F inalSP , g and D. A plan P P lan
is returned (Line 7 ) which is then sent to EMQ in the form
of triggering messages (Lines 9-13). Now we elaborate the
working of Compute P lan procedure (Algorithm 3) (Many
lines of the algorithm are taken from [
Compute P lan procedure is an extension of JSHOP2[
The second case is where g is a compound goal, so a method needs to be applied for the decomposition of g into its subtasks. In this case the planner nondeterministically chooses a method instance m matching g, that decomposes g into subgoals (Line 29) and applies this method (Lines 33-34). If no such method m exists then procedure returns failure (Lines 30-32).
At the end of each planning step, the Compute P lan procedure looks for any newly arrived acknowledgement for an earlier sent message. If a new acknowledgement for a message with identity id has been arrived then the procedure removes all the tasks depending on id, from Pending Tasks list and puts them in the Local Goals list to process those goals (Lines 41-44).
While planning for a proactive goal, the Compute P lan procedure checks GRG for any new goals after each planning step and whenever it finds a goal in GRG, it suspends planning for the proactive goal and calls the procedure T reat Reactive Goal , which we have explained earlier (Lines 45-49). When GRG becomes empty, procedure resumes planning for the proactive goal from the same state at which it had suspended the planning. While planning for a reactive goal, the Compute P lan procedure does not look at GRG, because a new reactive goal is treated only when all the previous reactive goals have been treated.
When Compute P lan finds a plan for one goal, it converts the total order plan into a temporal plan by calling the procedure T emporal Converter (Algorithm 4). The procedure takes three parameters I, P and D, where I is the initial state, P is the total order plan which is to be converted and D is the domain description file which is needed to extract the information about the durations of all the actions and offsets of all the effects. Some notations used in the procedure are as follows. no of literals(I) denotes the number of literals in the initial state and Literal(I[j]) points to the jth literal in initial state. P roduction T ime(Lit) represents the time of achievement of a literal Lit. length(P ) returns the number of actions in the plan P . no of pre(Act) and no of ef f ects(Act) denote the number of preconditions and number of effects of an action Act respectively while in the same vein P re(P [i][j]) and Literal(P [i][j]) denote the jth precondition and jth effect of ith action in plan P respectively. We have used a simple and efficient technique to convert a plan into temporal plan. The procedure starts by setting the P roduction T ime of all the literals in the initial state to 0 (Lines 1-3). Then procedure loops through all the actions starting from the first action, going towards the last one and sets the T imeStamp of the action to the maximum of the P roduction T ime of all its preconditions, because an action can be executed at least when all of its preconditions have been achieved (Lines 4-5). After setting the T imeStamp of an action, the procedure sets the P roduction T ime of all the effects of the action. The production time of an effect is the T imeStamp of the action plus the time at which the effect is produced by the action, the Of f set of the effect (Lines 8-10).
The Executor is running in parallel with the Planner. It waits for triggering messages to come in the EMQ, fetches the messages and executes the actions associated with the 17: 18: 19: 20: 21: 22: 23: 24: 25: Algorithm 5 Executor 1: loop 2: if Suspension Signal = ON then 3: Execution Signal OF F 4: Wait until fSuspension Signal = OF F g 5: Execution Signal ON 6: end if 7: if EM Q 6= then 8: N extActions Fetch all next messages C from EMQ having the earliest T imeStamp from current system time 9: N extT ime T imeStamp(N extActions) 10: Wait for system time to reach N extT ime 11: for i = 1 TO length(N extActions) do 12: if All the actions in P rereq(N extActions[i]) has not sent acknowledgement for termination then 13: Wait for all the acknowledgements 14: Duration Time spent waiting for acknowledgements 15: for i = 1 To length(EM Q) do 16: T imeStamp(EM Q[i]) T imeStamp(EM Q[i]) +
Duration end for end if if SP (N extActions[i]) = SW then
Execute N extActions[i] in a separate thread else
MP lan P lan M ender(SW; SP (NextActions[i])) Execute M P lan for i = 1 To length(EM Q) do
T imeStamp(EM Q[i]) T imeStamp(EM Q[i]) +
T imeSpan(MP lan) 26: end for 27: Execute N extActions[i] in a separate thread 28: end if 29: end for 30: end if 31: end loop messages at their planned time stamps. Every running action sends an acknowledgement just before its termination to the Executor. Algorithm 5 is a simplified version of the Executor. The Executor fetches all the next messages from EMQ that have the closest T imeStamp to the current system time. Then the Executor waits for the system time to reach the T imeStamp of these messages (Lines 10-11). When system time approaches that time, the Executor checks whether the prerequisite actions of the actions associated with these messages have been terminated or not. If they have not been terminated then it waits for their termination. And increases the T imeStamp of all the messages in EMQ by the duration of waiting for their termination (Lines 1420). Then it checks for any discrepency among the current world state and the one anticipated by the Planner for the execution of these actions. If there is no discrepency then these actions are executed in a separate thread (Lines 21-22) and the Executor fetches the next messages from EMQ. But if there is discrepency among the two world states, then the Executor calls the Plan Mender to generate a plan from the current world state to the intended world state and executes the plan thus returned to remove the discrepency (Lines 2425). After executing this plan the Executor is ready to execute the actions which it had suspended due to discrepency (Line 29). But before executing these actions, it augments their T imeStamp by the duration of the discrepency removal. Moreover, after executing each action, the Executor checks the Suspension Signal. When Suspension Signal is set to ON , it turns Execution Signl to OF F , suspends the execution, and waits for Suspension Signal to go OF F . The Executor resumes the execution once the Suspension Signal is turned to OF F . But now the triggering messages for the plan of reactive goal are at the front of EMQ, so the Executor first executes the plan for the reactive goal for which it had suspended the execution and then it resumes the execution of plan on which it was working before the suspension (Line 29). Algorithm 6 P lan M ender(I; G) 1: Generate a plan P using SATPLAN from I to G ignoring the duration of actions 2: T P Call T emporal Converter(I; P; D) 3: Return T P
This procedure is responsible for repairing the plan. It takes
as input the current actual world state I and the anticipated
world state G. The Plan Mender generates a temporal plan
for the agent to reach the anticipated world state starting
from the current world state and returns this plan to the
Executor. The Plan mender uses the classical STRIPS style
planning technique to compute its plan because now the goals
for the planner are a state to be reached (declarative goal).
So, the Plan Mender just uses operators from the domain
description file to compute the plan. In this case, the activities
are not helpful in generating the plan which were used by
the Planner component. The basic algorithm used by the Plan
Mender is shown in Algorithm 6. Plan mender computes a
plan without taking into account the durations of the actions
using the SATPLAN planner[
Fig. 2. (a).ROCO Activities
(b).Plan for Clean T able
In this example scenario we have one mobile agent ROCO, which is a home servant. When the MAS is launched then ROCO has the goal Clean T able. ROCO has activity associated with this goal Clean T able. All the activities of ROCO are shown in tree form in Figure 2(a) (A rectangle is showing a goal and an associated oval is an Activity associated with the goal, rectangles at the bottom without an associated oval are Actions.). M ain Algorithm fetches goal Clean T able from GPG list. And calls Compute P lan to plan for this goal which generates a plan consisting of the following actions M ove(Room1; T able), ArrangeBooks, ArrangeCover, Dusting. A short description of the actions in this plan is shown in Figure 3. The plan is converted to the temporal plan using the procedure T emporal Converter and the plan returned is shown in figure 2(b). In this example, all the effects of all the actions have an offset equal to the duration of the action. Here we explain the conversion of totally ordered plan to temporal plan. Procedure starts by assigning the P roduction T ime of all the literals in the initial state to 0. There is only one literal At(ROCO; Room1) in the initial state so P roduction T ime(At(ROCO; Room1)) is set to 0. Now the procedure takes first action M ove(Room1; T able) and sets its T imeStamp to 0, which is the maximum P roduction T ime from all of its preconditions. Next, the procedure sets the P roduction T ime of the effects of M ove(Room1; T able). This action has only one effect At(ROCO; T able). P roduction T ime(At(ROCO; T able)) is assigned the value T imeStamp(M ove(Room1)) plus Of f set(At(ROCO; T able)). Putting the values, we get P roduction T ime(At(ROCO; T able)) equals 1 minute, because Of f set(At(ROCO; T able)) is equal to the duration of M ove(Room1; T able). Now procedure moves to second goal which is Arrange Books and sets its T imeStamp to be the maximum of P roduction T ime of all of its preconditions. It has only one precondition At(ROCO; T able) whose P roduction T ime has already been calculated to 1 minute. So T imeStamp(Arrange Books) is assigned 1 munite. In this way the procedure continues and finds the plan shown in figure 2(b). Planner sends the messages for each action of the plan along with their T imeStamp to the EMQ for execution and Executor starts executing the plan. When the Executor has executed M ove(Room1; T able), ArrangeBooks and ArrangeCover, it checks that Suspension Signal is set to ON , because the Planner has just fetched a reactive goal Bring W ater from the GRG. The Executor suspends the execution, sets the Execution Signal to OF F and waits for the Suspension Signal to go to OF F again. It receives the following plan in the EMQ, M ove(T able; Kitchen), T akeGlass, F illGlassW ithW ater, M ove(Kitchen; OwnerRoom), Give(Glass; Owner). Now the Executor executes this plan. After the execution of this plan ROCO is in OwnerRoom. Now the Executor resumes its suspended plan but before resuming the suspended plan, it increases the T imeStamp of all the actions in the suspended plan by the T imeSpan of the plan for goal Bring W ater, then it checks whether the preconditions of the suspended plan hold in the current state. The preconditions of its suspended plan are At(ROCO; T able)^Arranged(Books)^Arranged(Cover) and the current state is Arranged(Books) ^ Arranged(Cover) ^ At(ROCO; OwnerRoom). The Executor calls Plan Mender to generate a plan from current state of the world to the intended state of the world. Plan Mender returns a plan consisting of only one action M ove(OwnerRoom; T able). Executor executes this plan, so ROCO moves to Table. Now again the Executor checks for any discrepency among the current state and the anticipated state but now both states are same so the Executor executes the suspended plan i.e. it executes the Dusting action.
In this section, we briefly review some work from the
existing literature which is related to our work. Some of
the research related to ours is CYPRESS[
In our opinion, the system closest to our research is
CYPRESS system, which also integrates a planning system
SIPE2[
Our system has many similarities with RETSINA. Like our system, RETSINA also interleaves planning with execution and supports planning for dynamic and real environments. But one main difference of RETSINA system with our system is that RESTINA system plans by only reduction of the top level task and it does not plan among the top level tasks, but our system uses a HTN planner which also plans among the top level tasks. So the plan generated is more optimal in our system than in RETSINA system. Another main difference is that RETSINA system does not use the existing information from the BDI system whereas our system proposes a method to use the existing agent’s and world’s information.
Another framework DECAF[
Like our system, [
Another framework incorporating planning in a BDI
language is presented in [
In this paper, we have presented an extension to the CLAIM language to endow the agents with the capability to plan ahead. This modified and extended language is called P-CLAIM. Agents are able to create temporal plans. Execution monitoring and plan repairing components are added. A balance between deliberation and reactivity has been established and the agents are able to turn their attention while planning to the newly arrived reactive goals. This work can be considered as a first step towards a comprehensive temporal planning solution for an Agent Oriented Programming language.
After creating the temporal plan for an agent but before its execution, the plan of an agent should be coordinated with the plans of those agents with which the plan could be in conflict or whose plans could be helpful for this agent. Our next task is to propose a coordination mechanism to coordinate the temporal plans of different agents. Coordinating the plan of agent with every other agent in the MAS is very costly, so another important task to do is to intelligently calculate the set of those agents whose plan could be in conflict or whose plans could be helpful for the agent and then the plan should be coordinated with only those agents.