Radja Boukharrou
email: boukharrou@misc-umc.org

Ahmed-Chawki Chawki Chaouche
email: ahmed.chaouche@lip6.fr

Jean-Michel Ilié
email: jean-michel.ilie@lip6.fr

Djamel Eddine Saïdouni
email: saidouni@misc-umc.org

Contextual-Timed Planning Management for Ambient Systems

Keywords: Real-time ambient system, time planning language and semantics, timing constraints, action duration, planning consistency

published or not. The documents may come   L'archive ouverte pluridisciplinaire

I. INTRODUCTION

Ambient intelligence (AmI) is an emerging technology area embedding heterogeneous electronic devices and often forming an open, dynamic and complex environment. Complexity here refers too to pro-actively, but sensibly, assisting people during their various daily activities. Actually, such systems have more and more impact over people's lifestyles [START_REF] Augusto | Ambient intelligence: The confluence of pervasive computing and artificial intelligence[END_REF], [START_REF] Preuveneers | A survey of software engineering best practices for the development of smart applications in ambient intelligence[END_REF]. Usually, multi-agent systems (MAS) approaches offer interesting and powerful framework for the design of such complex systems, since their agents are considered as intelligent, autonomous, pro-active and flexible [START_REF] Bordini | A survey of programming languages and platforms for multi-agent systems[END_REF]. Several modeling approaches are proposed for potentially improving the software engineering of these systems and which partially focus on some of MAS aspects, e.g. [START_REF] Cook | A multi-agent approach to controlling a smart environment[END_REF], [START_REF] Nygard | Multi-agent designs for ambient systems[END_REF], [START_REF] Silva | Planning with time limits in bdi agent programming languages[END_REF]. In fact, the major problem for the system entities consists in recognizing environmental context, including location, the discovery of other agents, planning and handling information in a more semantic manner within temporal reasoning.

To verify/reason about MAS we need to capture the desired properties in the right way as well as modeling agent's abilities and functionalities. The Belief-Desire-Intention (BDI) agent model can flexibly handle the entire agent modeling and developing in an AmI system [START_REF] Nygard | Multi-agent designs for ambient systems[END_REF]. Indeed, agents are able, thanks to their mental attitudes, to use their Beliefs, Desires, and Intentions in order to select and execute a plan of actions i.e., to cope easily with the real world.

The Higher-order Agent Model (HoA), presented in [START_REF] Chaouche | A Higher-order Agent Model with Contextual Management for Ambient Systems[END_REF], provides necessary theoretical foundations for designing/studding of BDI agents in AmI systems. On the other hand, it offers a useful framework, based on an agentcentric approach, to capture the behavior changes of the agent as consequence to its mental evolution according to the context-awareness ability. Therefore, At any instant of time the current state of an agent is expressed as an HoA configuration capturing the evolution of the agent in both its mental and planning states. This allows to maintain state consistency which yet appears to be absent from BDI theories.

In practice, in addition to the Mental process, the architecture of the agent is enriched within an efficient component, so-called Planning process ,with the aim to introduce more formal techniques for the description and the validation of ambient agent. Planning process is based on an algebraic language dedicated to the specification and the construction of a plan automatically from the intentions set of the agent and the library of elementary plans. The AgLOTOS [START_REF] Chaouche | A Higher-order Agent Model with Contextual Management for Ambient Systems[END_REF] is a process algebra describing agent behaviors in a modular and concurrent manner. It takes into account the AmI aspects i.e. mobility and communication. This allows designing a powerful planning management. Indeed, the semantics of AgLOTOS automatically produces a Contextual Planning System (CPS), that is a state transition system which captures the evolution of the plan according to updated information, enhancing ways to guide the agent with respect to the predicted context changes.

Most research works for AmI systems assume that agents have an unlimited amount of time available to perform and execute plan, which is often not the case in many dynamic real world environments. In this context, the conditions are highly dynamic and requiring real-time reasoning capabilities. Moreover, within this complex environment, the agent (especially BDI agent) must make often time-critical decisions and should execute right actions in the right time. So, within the absence of an appropriate mechanism considering the concepts of time, the production of good decisions would not be easy, if not impossible. In order to verify the quantitative timing properties, we argue the necessity of these two levels of time specification: timing constraints and action duration where real time performance is required.

The environment may place constraints on agents and their actions, like time issues, handling connectivity, localization and physical conditions (e.g. power/battery resources) which defined the key concepts of context. In [START_REF] Chen | A Survey of Context-Aware Mobile Computing Research[END_REF], depending on the nature of the context, the context information is categorized in four types: (1) computational context-available resources, network quality and related information; (2) user context-profile of the user, people nearby, social situation; (3) physical context-lighting, temperature, traffic conditions, noise levels, etc., and (4) time context-time of day, date of the year. Another aspect of context that is considered in some works is activity [START_REF] Henricksen | Developing context-aware pervasive computing applications: Models and approach[END_REF].

Although, more importantly, when the computing, user and physical contexts are recorded across a time span, this gives rise to a context history [START_REF] Chen | A Survey of Context-Aware Mobile Computing Research[END_REF]. This type of context is important for predicting future values of context and developing appropriate models/planning for context evolution. It can be useful for establish trends and guidance service for the agent. In this paper, our presented work deals with the main types of context: spatial context, temporal context, social context (agent nearby) and the context history.

To address the design-time issue for more complete and correct specifications of real-time AmI systems, we propose at first an extension of AgLOTOS language, called Time-AgLOTOS, describing the time-dependent behavior of the agent. Time-AgLOTOS provides a theoretical foundation for performing planning under timing constraints taking into account the duration of actions.

Other aim of this paper is to investigate true concurrency semantics instead of interleaving ones for two reasons: (1) to support structural and temporal non-atomicity of actions, i.e., actions may be divisible and of non-null duration. To escape from these assumptions, most of works consider actions as two instantaneous events: their start and their completion, in addition to the wait between these events. Although this approach seems to be attractive, it may contribute toward graph explosion in state-transition models. (2) to capture and express concurrent and parallel behaviors in a more natural and intuitive way, i.e. to distinguish between sequential and parallel runs of actions which appears interesting for the design/reasoning about the agent ability to pursue multiple desires and intentions concurrently.

Then, we give true-concurrency semantics to Time-AgLOTOS in terms of maximality semantics [START_REF] Saïdouni | Sémantique de maximalité : Application au raffinement d'actions en LOTOS[END_REF], [START_REF] Courtiat | Relating maximality-based semantics to action refinement in process algebras[END_REF], [START_REF] Saïdouni | Using maximality-based labelled transition system as a model for petri nets[END_REF]. The underlying semantics is a Contextual Time Planning System (CTPS) which is very close to Durational Action Timed Automata model [START_REF] Saïdouni | Actions duration in timed models[END_REF]. As a main result, CTPS allows the verification of new properties related to simultaneous progress of actions at different states of the system. Moreover, based on the possible evolution specified in a plan, we aim at offering a predictive service helping the agent on the fly to take time-critical decisions and to guide it to achieve its adopted desires concurrently.

II. AMBIENT ALGEBRAIC LANGUAGE FOR PLAN SPECIFICATION

The Higher-order Agent Model (HoA) [START_REF] Chaouche | A Higher-order Agent Model with Contextual Management for Ambient Systems[END_REF] provides a formal modeling for BDI agent, expressing reasoning mechanism and planning process explicitly. The building of the agent plan is described by using a process-algebra-based language, called AgLOTOS [START_REF] Chaouche | A Higher-order Agent Model with Contextual Management for Ambient Systems[END_REF]. Focusing on Intention based reasoning, the agent plan is structured to explicit the parts of the plan associated with each intention selected by the agent. As highlighted in Figure 1, The planning structure is composed of three levels of plans: elementary plans, intention plans and finally agent plan. The agent plan is obtained by sequential and/or a parallel composition of intentions plans where each one is dedicated to achieve its corresponding intention. Moreover, an Intention plan is viewed as an alternate of several elementary plans to express the possibility to achieve the intention. In the HoA architecture, elementary plans are assumed to be already specified so can be extracted from the so-callled LibP library. This library is assumed to be indexed by the set of the possible intentions that the agent can commit.

As a process algebraic language, AgLOTOS provides a way to describe plans in terms of algebraic process expressions, composed in modular and concurrent ways. This language uses actions as its primitives and some of them have a special meaning e.g., mobility and communication. Actions can then be combined to describe elementary plans using a variety of defined operators. Over operators are used (1) to form the alternation of elementary plans and (2) to compose the intention plans leading to the agent plan. AgLOTOS has an operational semantics that takes the planning structure into account to offer a clear separation of the different executions related to the intention plans.

Let us now detail the highlights of the AgLOTOS-based specifications for plans.

Agent plan level:

The set of intention plans can be globally handled by using the concurrent ||| or sequential ≫ AgLOTOS composition between intention plans, leading to the specification of an Agent plan. Let P be the set of names qualifying the possible agent plans and P ∈ P be the set of names used to identify the possible intention plans with P ∈ P, such that P is any agent plan defined by: P ::= P | P ||| P | P ≫ P Intention plan level: An intention plan can be expressed by an alternate of several elementary plans, such that each one can be launched to solve the corresponding intention. This is captured in AgLOTOS by using the alternate composition operator ♦ which allows to specify an alternate of elementary plans. In particular, an intention is satisfied iff at least one of the associated elementary plans is successfully terminated. Formally, we define an intention plan P as:

P ::= P | P ♦ P
Elementory plan level: Elementary plans are descried by AgLOTOS expressions, referring to a finite set of observable actions. Any AgLOTOS expression is associated with contextual information relating to the (current) BDI state of an agent. For that, let Θ be a finite set of space locations where an agent can move and Λ be the set of agents with which it can communicate. Let O be the (finite) set of observable actions which are viewed as instantiated predicates, ranged over by a, b, ... and let L be any subset of O. H ⊂ O is the set of the so-called AmI primitives which represent the mobility and communication. The agent mobility is expressed by the primitive move(ℓ) which is used to handle the agent move to some location ℓ (ℓ ∈ Θ). The syntax of the communication primitives is defined by the expression χ!(ν) which specifies the emission to the agent χ (χ ∈ Λ) of some message ν and the expression χ?(ν) means that the message ν is received from some agent χ.

Let Act = O ∪ {τ, δ}, be the set of actions, where τ is the internal action and δ is a particular observable action which features the successful termination of a plan. The AgLOTOS language specifies pairs for each elementary plan composed of a name to identify it and an AgLOTOS expression to feature its behavior. Consider that elementary plan's names are ranged over P 1 , P 2 , ... and that the set of all the possible behavior expressions is denoted B, ranged over E 1 , E 2 , .... The AgLOTOS expressions are written by composing actions through LOTOS operators. The syntax of an AgLOTOS elementary plan P is defined inductively as follows:

P ::= E E ::= exit | stop | a; E | E ⊙ E | τ ; E (a ∈ O) | hide L in E H ::= | move(ℓ) (H ⊂ O, ℓ ∈ Θ) | χ!(ν) | χ?(ν) (χ ∈ Λ) ⊙ = { |||, |[L]|, ||, [ ], ≫, [> }
The elementary expression stop specifies a plan behavior without possible evolution and exit represents the successful termination of some plan. In the syntax, the set ⊙ represents the standard LOTOS operators: E [ ] E specifies a nondeterministic choice, hide L in E a hiding of the actions of L that appear in E, E ≫ E a sequential composition and

E [> E the interruption. The LOTOS parallel composition, denoted E |[L]| E, can model both synchronous composi- tion, E || E if L = O, and asynchronous composition, E ||| E if L = ∅.
To be pragmatic considering any BDI state of the agent, we propose that the agent can label the different elements of the set I of intentions1 by using a weight function W : I -→ N. The ones having the same weight are composed by using the concurrent parallel operator |||. In contrast, the intention plans corresponding to distinct weights are ordered by using the sequential operator ≫. For instance, let I = {i 1 0 , i 2 1 , i 1 2 , i 0 3 } be the considered set of intentions, such that the superscript information denotes a weight value, and let P 0 , P 1 , P 2 , P 3 be their corresponding intention plans, the constructed agent plan could be viewed as:

P = P 1 ≫ ( P 0 ||| P 2 ) ≫ P 3 .
The AgLOTOS operational semantics is basically derived from the one of LOTOS and can be found in [START_REF] Chaouche | A Higher-order Agent Model with Contextual Management for Ambient Systems[END_REF].

A Simple AmI Example: Let Alice and Bob be two agents of an AmI University system. Such a system is clearly dynamic and open since agents can enter and leave at any moment. Furthermore, the agents are context-aware; they can perceive the enter and the location of each agent within the system and they are able to communicate through this system. Let ℓ 1 , ℓ 2 ∈ Θ be two locations of the studied system where the two agents can behave. The proposed problem of Alice is that she wants to realize the two tasks at the same time: (a) meet Bob in ℓ 1 , and (b) get her exam copies from ℓ 2 . Clearly, the Alice's desires are inconsistent since Alice cannot be in two distinct locations simultaneously. At the considered moment, Alice is in ℓ 1 and she expresses the two inconsistent desires, whereas Bob is already arrived in ℓ 2 and has expressed the desire to work with Alice. Because of the conflictual desires, the current intention of Alice is only to meet Bob first. Consequently, the initial HoA configurations of Alice and Bob are respectively q A 0 and q B 0 in Table I. The actions in plans are simply expressed in AgLOTOS language by using instantiated predicates, like get copies(ℓ 2 ). Note Alice's scenario B0 = {in(me, ℓ1), in(copies, ℓ2)} q A 0 D0 = {meeting(Bob, ℓ1), getting copies(ℓ2)} I0 = {meeting(Bob, ℓ1)} P0 = meet(Bob, ℓ1); exit Bob's scenario B0 = {in(me, ℓ2)} q B 0 D0 = {meeting(Alice, ℓ1)} I0 = {meeting(Alice, ℓ1)} P0 = move(ℓ1); meet(Bob, ℓ1); exit that Alice and Bob are specified separately and that they are able to coordinate for improving the satisfaction of more desires (see Section IV).

III. REAL-TIME AMBIENT ALGEBRAIC LANGUAGE

Another key requirement of AmI environment is real time reasoning capabilities, when timing constraints become increasingly important to the proper functioning of AmI agent.

By way of example, let us consider the example of Table I but in the context of timing dependencies of actions. For instance, Alice is already in ℓ 1 , she wants to meet Bob in this location as soon as possible because she has a limited time for going to get her exam copies e.g just a delay of 5 time units. Also, she has only 2 time units for that meeting. Then, she will take her exam copies from ℓ 2 in the required time. On the other hand, Bob wants to terminate his work in the current location before leaving it to ℓ 1 . This takes a certain amount of time (at least 1 time unit). In this case both agents should respond in a timely manner to changes that occur in environment and to its timing constraints.

According to this example, we can define different types of real-time constraints. Hence, These constraints can limit the enabling domains regardless of the duration of other actions by delaying for example an action of a certain quantity of time before it will be feasible; or by limiting the time during which an action is offered to its environment (temporal restriction). In this paper,we define an algebraic language called Time-AgLOTOS to specify the syntax and the semantics of an agent plan considering the classical timing operators similar to those introduced in temporal extensions of LOTOS, such as D-LOTOS [START_REF] Saïdouni | Actions duration in timed models[END_REF] and RT-LOTOS [START_REF] Courtiat | Experience with rt-lotos, a temporal extension of the lotos formal description technique[END_REF] for the description of such constraints.

The delaying aspect can be specified by means of a new operator ∆ d E that describes time delays. This operator means that no evolution of E is allowed before the end of a delay equal to d. For example, the specification of Bob's plan for achieving its intention meeting(Alice, ℓ 1 ) is described by the use of the delaying operator as: ∆ 1 (move(ℓ 1 ); meet(Alice, ℓ 1 ); exit). We already know how to describe syntactically the sequencing of action occurrences by means of the action-prefixing operator of AgLOTOS. We can extend this operator to deal with the notion of temporal constraint for an action through two new prefixing operators a{d}; E and a@t[SP ]; E. The temporal restriction for the occurrence of an action can be expressed using the operator a{d} which means that action a is offered during at most d time units. Whereas, in the operator a@t[SP ]; E (resp. τ @t{d}; E), SP is a selection predicate that constrains the occurrence of action a (resp. τ ) and t is a temporal variable recording the time taken after the enabling of action a (resp. τ ). For instance in Alice's scenario, its ongoing desires are depending strongly on time limit which can be expressed by: meet(Bob, ℓ 1 )@t 1 [t 1 2]; exit{0} ≫ move(ℓ 2 )@t 2 [t 2 5t 1 ]; get copies(ℓ 2 ); exit{1}.

Moreover, we should reason on the internal action τ as a specific action that cannot be delayed and must be performed as soon as it becomes available because it refers to the local behavior of the agent. This introduces the notion of urgency when the action must occur immediately and while time progression is stopped. This notion is useful for describing features like time-outs and time deadlocks. Another question arises addressing the reasoning about time in quantitative sense. In this context, we argue that the action duration must be explicitly taken into account by the Time-AgLOTOS. In what follows, we show how to explicitly introduce action duration in AgLOTOS. This is became possible by the use of a function that gives to each action a non-null duration. The idea is based on the principle of the maximality semantics allowing the expression of the structural and temporal nonatomicity of actions in a similar way introduced for D-LOTOS.

Syntax:

We now define Time-AgLOTOS in which both timing constraints and actions duration are considered. Absolutely, as far AgLOTOS, the language allows the specification of dynamism and context-aware of AmI system. The syntax of a Time-AgLOTOS agent plan directly relates to the building of a behavior expression representing the whole agent behavior according to the construction approach discussed above in Section II. Indeed, we propose a temporal extension to the syntax of elementary plan taking into account time aspects and preserving the overall structure of the agent plan. The syntax of an Time-AgLOTOS elementary plan is defined inductively as follows:

P ::= E E ::= exit{d} | stop | ∆ d E | E ⊙ E | a@t[SP ]; E | τ @t{d}; E (a ∈ O) | hide L in E ⊙ = { |||, |[L]|, ||, [ ], ≫, [> }
Let D be a domain of time like Q + or R + . Υ : Act → D is the duration function which associates to each action its duration. Let a be an action, E a behavior expression and d ∈ D a value in the temporal domain. We recall that a{d} expresses the temporal restriction, ∆ d E represents a time delay and a@t[SP ]; E and τ @t{d}; E describe timing dependencies. Thereby, the elementary expression stop specifies a plan behavior without possible evolution and exit{d} represents the successful termination of some plan which must be taken within the interval [0, d]. We assume also that the stop and exit are of null duration. We denote that at both agent plan and intention plan levels, only the order of plan executions is expressed within time specification abstraction (as in untimed case). The specification of time-dependency is allowed explicitly at elementary plans.

IV. TIME-AGLOTOS SEMANTICS

As far as Time-AgLOTOS is concerned, the operational semantics of elementary plans is given by rules of Definition 4.5. This semantics is basically derived from the one of D-LOTOS [START_REF] Saïdouni | Actions duration in timed models[END_REF] and which captures the evolution of a concurrent processes. A pair (E, P ) represents an elementary plan configuration, viewed as a process and identified by P such that its behavior expression is E. A transition relation between configurations, embodying the behavior expressions of elementary plans, is expressed in the context of maximality semantics and which gives as a result a well-structured state transition system. In Time-AgLOTOS, observable actions are not urgent as their occurrences depend on the willingness of the environment. Whereas, for the internal action τ , the situation is more complex as one may want to express urgent occurrence of this action.

A. Formalization

In the following, H is a set of clocks with non-negative values (within a time domain T, like Q + or R + ). The set Φ t (H) of temporal constraints γ over H is defined by γ ::= x ∼ t where x is a clock in H, ∼∈ {=, <, >, ≤, ≥} and t ∈ T. F x will be used to indicate a constraint of the form x ∼ t. A valuation (or interpretation) v for H is a function which associates to each x ∈ H a value in T. A valuation v for H satisfies a temporal constraint γ over H iff γ is true by using clock values given by v. For U ⊆ H, [U → 0]v indicates the valuation for H which assigns value 0 to each x ∈ U, and agrees with v over the other clocks of H. The set of all valuations for H is noted Ξ(H). The satisfaction relation |= for temporal constraints is defined over the set of valuations for H by : v |= x ∼ t ⇔ v(x) ∼ t such that v ∈ Ξ(H). The set of all the possible elementary configurations is denoted C and given by Definition 4.1.

Definition 4.1: The set C of elementary configurations is defined by:

• ∀E ∈ B, ∀F ∈ 2 Φt(H) : F [E] ∈ C • ∀P ∈ P, ∀F ∈ 2 Φt(H) : F [P ] ∈ C • if E ∈ C then hide L in E ∈ C • if E ∈ C and F ∈ B then E ≫ F ∈ C • if E, F ∈ C then E op F ∈ C with op ∈ { [ ], |||, ||, |[L]|, [> } • ∀E ∈ C, ∀d ∈ D : △ d E∈ C • if E ∈ C and {a 1 , ..., a n }, {b 1 , ..., b n } ∈ 2 O then E [b 1 /a 1 , ..., b n /a n ] ∈ C
In order to determine a set of duration conditions w.r.t. some configuration C, we use the function ψ : C → 2 Φt(H) such that for each configuration of the form

F [E] ∈ C we have ψ( F [E]) = F . Definition 4.2:
The function ψ H : 2 Φt(H) → 2 H , determines the set of used clocks in a duration conditions set and is defined recursively by:

ψ H (∅) = ∅ ψ H ({x ∼ t}) = {x} ψ H (F 1 ∪ F 2 ) = ψ H (F 1 ) ∪ ψ H (F 2 ) such as F 1 , F 2 ∈ 2 Φt(H) , x ∈ H, ∼∈ {=, <, >, ≤, ≥} and t ∈ R + . If F [E] is an elementary configuration then F [E]\K in-
dicates the new configuration obtained by removing the set K of timing constraints from the set F s.t. the concerning clocks are used in

F . F [E]\K= F \K [E]
) with F \K given by the Definition 4.3. Definition 4.3: Let F be a set of ending conditions; F \K indicates the set obtained by removing (starting from F ) all the duration conditions which are related to the clocks of K from F . F \K is recursively defined on F as follows:

∅\K = ∅ (F1 ∪ F2) \K = F1\K ∪ F2\K {x ∼ t}\K = ∅ if x ∈ ψH(K) {x ∼ t} otherwise such that F1, F2 ∈ 2 Φt(H) , K ∈ 2 Φt (H) , x ∈ H, ∼∈ {=, <, >, ≤, ≥} and t ∈ R + .
The specification of delays and timing constraints in the generation process requires the following Definition.

Definition 4.4: Let G ∈ 2 Φt(H) be a timing constraint and t be time units:

• The function shif t(G, t) dealing with the move of a temporal domain G by a time units t is defined by shif t(G, t) ----------------- --------------------------- ---------------------------

def = {(min +t ∼ x ∼ max +t) | (min ∼ x ∼ max) ∈ G}
→ {x≥0} [stop] x=get(M) • F [exit{u}] G={∪ h∈H {shif t(0≤h≤u,t)}\F h ={h≥t}}
→ D={false},δ,x {x≥0} [stop] x=get(M) • ∅ [a{u};E] G={c ∅ ≤u},D={false},a,x -----------------→ {x≥τ (a)} [E] x=get(M) • F [a{u};E] G={∪ h∈H {shif t(0≤h≤u,t)}\F h ={h≥t}}
→ D={false},a,x {x≥τ (a)} [E] x=get(M) • ∅ [h{u};E] G={c ∅ ≤u},D:=G,h,x --------------→ {x≥0} [E] x=get(M) • F [h{u};E] G={∪ h∈H {shif t(0≤h≤u,t)}\F h ={h≥t}} ---------------------------→ D:=G,h,x {x≥0} [E] x=get(M) • SP ={min∼t∼max} ∼∈{<,≤} ∅ [a@t[SP ];E] G={[c ∅ /t]SP },D={false},a,x --------------------→ {x≥τ (a)} [E] x=get(M) • SP ={min∼t∼max} ∼∈{<,≤} F [a@t[SP ];E] G={∪ h∈H {[h/t]shif t(SP,d)}\F h ={h≥d}} --------------------------→ D={false},a,x {x≥τ (a)} [E] x=get(M) • E G,D,a,x -----→ E ′ F [ ] E G,D,a,x -----→ E ′ E [ ] F G,D,a,x -----→ E ′ • E G,D,a,x -----→ E ′ a / ∈L∪{δ} E |[L]| F G,D,a,y -----→ E ′ [y/x] |[L]| F \G y=get(M-(ψ H (ψ(E)∪ψ(F ))-ψ H (G))) • E G,D,a,x -----→ E ′ a / ∈L∪{δ} F |[L]| E G,D,a,y -----→ F \G |[L]| E ′ [y/x] y=get(M-(ψ H (ψ(E)∪ψ(F ))-ψ H (G))) • E G,D,a,x -----→E ′ F G ′ ,D ′ ,a,y ------→F ′ a∈L∪{δ} E |[L]| F G∪G ′ ,D∪D ′ ,a,z ----------→ E ′ [z/x]\G ′ |[L]| F ′ [z/y]\G z=get(M-(ψ H (ψ(E)∪ψ(F ))-(ψ H (G)∪ψ H (G ′ )))) • E G,D,a,x -----→E ′ a / ∈L hide L in E G,D,a,x -----→ hide L in E ′ • E G,D,a,x -----→E ′ a∈L hide L in E G,D:=G,h,x --------→ hide L in E ′ • E G,D,a,x -----→ E ′ d≥0 ∆ d E shif t(G,d),shif t(D,d),a,x -----------------→ E ′ • E G,D,a,x -----→E ′ a =δ E≫F G,D,a,x -----→ E ′ ≫F • E G,D,δ,x -----→E ′ E≫E G,D,h,x -----→ {x≥0} [E] • E G,D,a,x -----→E ′ a =δ E [> F G,D,a,y -----→ E ′ [y/x] [> F \G y=get(M-(ψ H (ψ(E)∪ψ(F ))-ψ H (G))) • E G,D,δ,x -----→E ′ ∀z∈ψ(F ) E [> F G,D,δ,y -----→ E ′ [y/x] [> ψ(F)-Gz [stop] y=get(M-(ψ H (ψ(E)∪ψ(F ))-ψ H (G))) • F G,D,a,x -----→F ′ ∀z∈ψ(E) E [> F G,D,a,y -----→ ψ(E)-Gz [stop] [> F ′ [y/x] y=get(M-(ψ H (ψ(E)∪ψ(F ))-ψ H (G))) • E G,D,a,x -----→E ′ a / ∈{a 1 ,...,an} E[b 1 /a 1 ,...,bn/an] G,D,a,x -----→ E ′ [b 1 /a 1 ,...,bn/an] • E G,D,a,x -----→E ′ a=a i (1≤h≤n) E[b 1 /a 1 ,...,bn/an] G,D,b i ,x ------→ E ′ [b 1 /a 1 ,...,bn/an] • P :=E F [E] G,D,a,x -----→F F [P ] G,D,a,x -----→ F
Such as, c ∅ is a particular clock which is created and initialized at the enabling time of the agent system.

Let us consider now another of level of plan and its semantics. The behavior expression of the agent plan P under evolution is called agent plan configuration and denoted [P ]. Definition 4.6 specifies how an agent plan configuration is formed composition manner from the intention plan configurations like (E, P ), themselves built from an alternate of elementary plan configurations as (♦ k=1..n E k , P ).

Definition 4.6: Any Agent plan configuration [P ] has a canonical representation defined by the following two rules: 1) P ::= P P ::=♦ k=1..n P k P k ::=E k [P ]::=(♦ k=1..n E k , P )

2)

P ::=P 1 ⊙ P 2 ⊙∈{|||,≫} [P ]::=[P 1 ] ⊙ [P 2 ]
Notice that the contextual planning state takes into account the agent location and the termination information concerning the different intention plans already achieved; its definition is given as follows:

Definition 4.7: A contextual planning state is a tuple (ps, ℓ, T ), where ps is any plan configuration [P ], ℓ corresponds to an expected location for the agent, and T is the subset of intention plans which are terminated. Table II shows the operational semantic rules defining the so-called contextual planning state changes for the agent. These rules are applied to produce a Contextual Time Planning System (CTPS). Thereby, the initial contextual planning state (ps0, ℓ, ∅) means that the agent is initially at location ℓ, and its plan configuration is ps0 = [P ] with no specific plan termination.

B. Contextual Planning Construction

From any HoA configuration q, we are now able to build a transition system representing the agent plan and its state changes. Further, from the set of intentions represented in q, denoted I(q), the CTPS is built using the former rules defined above. In addition to the timing constraints and the maximality information (ending condition and concurrent execution) of actions, CT P S takes into account three kinds of information represent the contextual ones as : (a) the reached location in a given planning state, (b) the set of intention plans that are terminated when reaching this planning state, and (c), more globally, the set Λ(q) of neighbors currently known by the agent. Considering q = (bdi, ps) any HoA configuration of the agent, its CTPS in q, starting from ps, is given by the following Definition.

Definition 4.8: A Contextual Time Planning System is a tuple S, s0, Ls, T r, L, T of the support Act where :

• S is a finite set of contextual planning states s.t s = (ps, ℓ, T ) ∈ S, • s0 = (ps, ℓ, ∅) ∈ S is the initial contextual planning state of the agent, such that ps = [P ] and ℓ represents the current location of the agent, • Ls: S → 2 Φt(H) is a function which corresponds to each state s the set F of ending conditions (duration conditions) of actions possibly in execution in s, • T r ⊆ S × 2 Φt(H) × 2 Φt(H) × Act × H × S is the set of transitions of the form (s, G, D, a, x, s ′ ) 2 , • L : S → Θ is the location labeling function,

• T : S → 2 P is the termination labeling function which captures the terminated intention plans. A transition (s, G, D, a, x, s ′ ) represents a switch from the state s to the state s ′ by starting execution of action a and resetting clock x. G is the corresponding guard which must be satisfied to fire this transition. D is the corresponding deadline which requires, at the moment of its satisfaction, that action a must occur. (s, G, D, a, x, s ′ ) can be written s G,D,a,x ----→ s ′ . As usual in real-time formal model, like [START_REF] Saïdouni | Actions duration in timed models[END_REF], the semantics of a CTPS is defined as an infinite timed transition system ΣA of the same alphabet Act.

Definition 4.9: The semantics of a Contextual Time Planning System A = S, s0, Ls, T r, L, T associates to the CTPS an infinite transition system ΣA defined over Act ∪ R + . A state of is a pair s, v such that s is a state of A and v a valuation for the clocks of H. A state s0, v0 is initial if s0 is the initial state of A and ∀x ∈ H, v0(x) = 0. Two types of transitions are specified in-between the configurations of ΣA. The time passing transitions are specified according to the rules RA1 and RA2 whereas the action transition, which refers to the launching of transition from A, is related to the rule RD.

(RA1) d ∈ R + , d > η ∀d ′ ≤ d, v + d ′ D s, v d -→ s, v + d (1)
(RA2) ε ∈ R + v + ε D ∧ ε ∈ η s, v ε -→ s, v + ε (2) (RD) (s, G, D, a, x, s ′ ) ∈ TD v G s, v a -→ s ′ , [{x} → 0]v (3)
Where η is the smallest real quantity of time in which no action occurs.

Remark: According to the proposed operational semantics for the Time-AgLOTOS language, the obtained CTPS structure is an extension of the Durational Action Timed Automata (or DATA for short) of [START_REF] Saïdouni | Actions duration in timed models[END_REF], enhancing contextual and intention termination information.

As a simple example, consider the following expression plan P1 = meet(Bob, ℓ1)@t1[t1 2]; exit{0} ≫ move(ℓ2)@t2[t2 5 -t1]; get copies(ℓ2); exit{1}, the generated CTPS is illustrated in Figure 2. For instance, state S5 captures the current action under execution which is mentioned by the corresponding clock x, the reached location ℓ2 and the set of intention plans that are terminated successfully (here it is expressed by { P1, P2}). In this paper, we present an expressive model that provides theoretical foundations and a practical reasoning framework which are dedicated to real-time AmI systems based on agent approach. Up to our knowledge; many works have proposed multi-agent modeling based on logics or behavioral languages, but few of them have dealt timing constraints.

S0 S1 {∅}, ℓ1 {x ≥ 2}, ℓ1 meet(Bob, ℓ1), x G = {C∅ ≤ 2} S2 S3 {x ≥ 0}, ℓ1, { P1} {x ≥ 1}, ℓ2, { P1} move(ℓ2), x G = {0 ≤ x ≤ 3 -val(C∅)} τ, x G = {2 ≤ C∅ ≤ 2} D = {x ≥ 2} S4 {x ≥ 1}, ℓ2, { P1} τ, x G = {1 ≤ x ≤ 2} get -copies(ℓ2), x G = {1 ≤ x ≤ 2} S5 {x ≥ 0}, ℓ2, { P1, P2}
The works of Hoogendoorn et al., e.g. [START_REF] Hoogendoorn | Formal specification and analysis of intelligent agents for model-based medicine usage management[END_REF], present a multiagent-based model for a medicine usage, associated with formal analysis methods. In fact, both multi-agent system and corresponding ambient agents are specified in the logical language TTL. This language supports the formal specification and analysis of some dynamic properties. Further, the beliefs and intentions of an agent are presented as predicates in temporal rules which can be used by the agent to perform some simulations. Nevertheless, there is no explicit expression referring to the agent desires or capacities like mobility, rationality, adaptability or context-awareness .

In contrast, our proposed AmI agent model provides a powerful framework for real-time AmI system design, which covers the major features and functionalities of such system. It also combines the mental reasoning of a BDI agent as well as its behavior evolution represented in a powerful algebraic construction within time specification.

In [START_REF] Coronato | Formal design of ambient intelligence applications[END_REF], the authors propounded a specification process and a set of formal tools for ambient design activities.They collected some existing languages and techniques which are combined in order to handle different aspects of AmI applications: formal ontology to define the entities of the application domain, ambient calculus (AC) with its related logic to specify the moves of the mobile agents in MAS and finally, real-time temporal logic (RTTL) to express temporal constraints for reasoning about time.

In contrast to such tool box based on multiple semantics, our approach provides an unified and well-founded algebra methodology for describing plans and checking within them real-time behavioral properties with respect to rich and unique semantics.

Outside of the agent-centric approaches, the methodology proposed in [START_REF] Corno | Design time methodology for the formal verification of intelligent domotic environments[END_REF] aims at verifying the logical and temporal properties of an intelligent domotic environment. It checks the correctness of such system by using UCTL model checking techniques over the UML State Charts model describing the system. Unlike to our formal approach which is intended to be concrete, this methodology presents an abstract specification of timing constraints while taking into account concurrency. However, the major features of AmI systems are not handled explicitly in this model.

Another category of works used some algebraic formalisms ala-LOTOS to specify distributed real-time systems. In [START_REF] Maarouk | Towards a calculus for distribu-ted, real-time and mobile systems[END_REF], the authors present the MDD-LOTOS language as a calculus modeling the mobility in distributed systems under time requirements. This model allows to specify the migration of processes over a set of distributed locations and also the dynamic creation of new processes. Two types of communication are presented, the local communication and the remote one. Like in our approach, they also propose a semantics model for the building of automatic verification tools, based on the maximality semantics. Moreover, it takes into account timing constraints and duration expressions. Due to the AmI requirements, in our agent-based model, the remote communications are between agents, whereas, the synchronized ones are defined locally inside the agent and are related to the parallel composition of its behaviors. So, we provide two distinct designing levels for MAS, the inside agent and outside one including moving ability.

VI. CONCLUSION

The proposed Time-AgLOTOS agent algebraic language appears to be a powerful way to express agent plan as an hierarchical structure made of concurrent processes. This language provides a theoretical basis to deal with timing constraints, taking into account the duration of actions. The formal semantics of Time-AgLOTOS associates a Contextual Time Planning System (CTPS) with each BDI state of the agent. Hence, from some current set of intentions, this allows one to capture all the possible evolutions of the agent plan, in respect to the timing constraints of the executed actions, under various environmental contexts. Observing that the presented work provides an original time mechanism that works contextually to guide the agent for its future executions, we now aim at combining the CTPS approach with learning techniques, viewed as a guidance mechanism based on past-experiences.

  Figure 1. Planning Process

  and ∼∈ {<, ≤} • The function maxval(G), which restricts a temporal domain G on its upper bound, is defined as maxval(G) = ∨ {min∼x∼max}∈G (x = max) with ∼∈ {<, } Now, we introduce the operational semantics for Time-AgLOTOS elementary plan as rules of Definition 4.5. Definition 4.5: The maximality transition relation -→ ⊆ C × 2 Φt(H) × 2 Φt (H) × Act × H × C is defined as being the smallest relation satisfying the following rules: • ∅ [exit{u}] G={c ∅ ≤u},D={false},δ,x

Figure 2 .

 2 Figure 2. CTPS corresponding to the agent plan P 1 of Alice

Table I INITIAL

 I HOA CONFIGURATIONS FOR ALICE AND BOB

We assume that the BDI agent itself can solve conflicting situations that could arise between intentions for some context, by means of a scheduling process applied on the set of intentions.

Table II SEMANTIC RULES OF BOTH INTENTION AND AGENT CONFIGURATIONS

Intention plan level


Ahmed-Chawki Chawki Chaouche
email: ahmed.chaouche@lip6.fr

Amal El

Jean-Michel Ilié
email: jean-michel.ilie@lip6.fr

Djamel Eddine Saïdouni
email: saidouni@misc-umc.org

Fallah Seghrouchni

Spatio-Temporal Guidance for Ambient Agents

Keywords: Ambient agent, BDI, contextual guidance, pastexperiences

come

I. INTRODUCTION

For the design of complex systems, Multi-Agent System (MAS) approaches offer interesting frameworks, since their agents are designed to be intelligent, proactive and autonomous [START_REF] Doyle | Rationality and its roles in reasoning[END_REF]. In particular, BDI models offer a good alternative for reactive systems whenever planning is required.

Indeed, the work of [START_REF] Chaouche | A Higher-order Agent Model with Contextual Management for Ambient Systems[END_REF] has shown how autonomous BDI agents [START_REF] Rao | An abstract architecture for rational agents[END_REF] can evolve and move within a dynamic environment, based on an agent centric approach that combines planning and context-awareness. In that approach, the environment is open and dynamic. Agents may enter and leave, and as they move, their location may change at runtime [START_REF] Olaru | A context-aware multi-agent system as a middleware for ambient intelligence[END_REF], [START_REF] Preuveneers | A survey of software engineering best practices for the development of smart applications in ambient intelligence[END_REF].

This paper introduces a planning management framework. Our approach relies on the following assumptions:

• The BDI-agent evolves in a dynamic environment. It is sensitive to the context and her changes; i.e. it is aware of the changes of the context.

• The BDI-agent is rational: it is goal-driven, i.e. the agent will pursue its goals; and it behaves according its strategy, i.e. the agent will try to satisfy the maximum of her concurrent intentions according to its strategy.

• The BDI-agent weighs the intentions with respect to its strategy. Under the previous assumptions,it is necessary to increase the agent reactiveness to the continuous changes of its context. In order to endow the BDI-agent with a such reactive behavior we developed an approach in 4 phases detailed in the following sections.

Section II develops the planning process including a brief description of AgLOTOS specification language. It consists of building the Plan of an agent (P ) from the current intentions it aims to satisfy (in a concurrent way). A plan called Intention Plan ( P i ) is associated with each intention. The intention plan is composed of Elementary Plans (P ) corresponding to different ways (alternative plans) to achieve an intention.

Section III discusses the construction of the Contextual Planning Structure (CPS), given a contextual state of the agent. The agent may interleave the execution of its actions when they belong to intention plans ( P i ) with the same weight. The CPS is then the projection of all possible executions corresponding to the actions of P . The CPS takes into account the possible interleavings (i.e. interleavings that respect the weights of intentions and the current context). Intuitively speaking, each path of the CPS is a trace of a possible execution of P .

Section IV improves the CPS with learning: unlike most existing approaches [START_REF] Singh | Integrating learning into a BDI agent for environments with changing dynamics[END_REF], [START_REF] Bourgne | Learning better together[END_REF], we will not learn plans. Indeed, we are interested with a finer granularity, i.e. we will learn actions in order to qualify them (with success or failure) and to combine these actions in order to reactively build robust plans in a dynamic context. To improve the CPS we will reason on situated actions as a pair (a, ) where ' ' is the location where the action 'a' occurs. Various contextual indicators could be associated with (a, ) such as: the outcome of the action (failure or success), the starting time (when the action begins) and the duration (the time spent for the action achievement). In addition, the agent, according to its rationality, may have various strategies for the optimization of its intentions' achievement. For instance, the agent may consider the new learning information instead the older ones, or may concentrate on the data around a specific time value. The agent strategy S is given as an input to the optimization algorithm.

In Section V, the optimization algorithm is conceived to guide the agent. Two coefficients have been first considered to evaluate a situated action (a, ). The first coefficient is the expected performance 'EP ' which computes an evaluation of the achievement of (a, ). It is an average of the obtained outcomes through some selected past-experiences. The second coefficient is the expected duration 'ED' of the situated action (a, ) computed from several past-experiences. The CPS is enriched with these two coefficients EP and ED associated with its edges. The advantage of the edge qualification is that the agent can choose a robust trace, or can avoid risky traces, etc. A trace qualification is deduced from the propagation of ED and EP through the CPS, based on a normalized accumulation. The guidance algorithm provides the agent with a set of maximum traces that respect the agent strategy. Moreover, the preferences of the agent between "race" and "secure" performances are considered. For instance, taking a speedy car could be interesting but can be risked w.r.t. the wish of the agent to safely arrive to some destination. To be progressive, these preferences are expressed by the agent as a balance proportion B, e.g. 30% for race and 70% for secure.

Section VI discusses our approach with regard to the state of the art and Section VII concludes this paper. As usual in BDI models, the mental process represents the reasoning mechanism, based on the beliefs (B), desires (D), and intentions (I), the instances of which define the BDI states of the agent. Triggered by the perceived events, the mental process manages/updates the B, D and I structures.

II. AGENT PLAN SPECIFICATION

As illustrated in Figure 1, the mental process can call the planning process to produce a plan, namely the agent plan (P ). Unlike other approaches, in our framework the plans corresponding to each intentions, namely intention plans ( P i ) are achieved concurrently, according to a weighting in order to privilege some intentions over others. This allows the mental process to solve conflicting situations, by ordering the intentions plans. However, when intentions are not conflicting, the same weight enables concurrent achievement of the intention plans in an interleaved way.

Moreover, each intention plan has alternative plans to be tried, called Elementary plans (P ), obtained from a library of plans (LibP). This allows us to consider different ways to achieve the associated intention. Further, we assume that the LibP library is indexed by the set of all the possible intentions for the agent, yielding the elementary plans that achieve some intention.

Let us now detail the highlights of the AgLOTOSbased specifications for plans, previously presented in [START_REF] Chaouche | A Higher-order Agent Model with Contextual Management for Ambient Systems[END_REF]. AgLOTOS inherits from the LOTOS language [START_REF] Brinksma | ISO 8807, LOTOS -A Formal Description Technique Based on the Temporal Ordering of Observational Behaviour[END_REF] so offers different ways to express the concurrency of actions in plans. It takes into account the AmI aspects i.e. mobility and communication.

Agent plan level: The set of intention plans can be globally handled by using the concurrent ||| or sequential AgLOTOS composition between intention plans, leading to the specification of an agent plan. Let P be the set of names qualifying the possible agent plans with P ∈ P and P be the set of names used to identify the possible intention plans with P ∈ P, such that P is any agent plan defined by: P ::= P | P ||| P | P P Intention plan level: An intention plan can be expressed by alternative elementary plans, such that each one can be launched to solve the corresponding intention. This is captured in AgLOTOS by using the composition operator ♦ to express the possibility to have alternative plans for executing intention. In particular, an intention is satisfied if and only if at least one of the associated elementary plans is successfully achieved. Formally, we define an intention plan P as: P ::= P | P ♦ P Elementary plan level: Elementary plans are described by AgLOTOS expressions, referring to a finite set of observable actions. Any AgLOTOS expression is associated with contextual information relating to the (current) BDI state of an agent. For that, let Θ be a finite set of space locations where an agent can move and Λ be the set of agents with which he can communicate. Let O be the (finite) set of observable actions which are viewed as instantiated predicates, ranging over a, b, ... and let L be any subset of O. H ⊂ O is the set of the so-called mobility and communication primitives. The agent mobility is expressed by the primitive move( ) which is used to handle the agent move to some location ( ∈ Θ). The syntax of the communication primitives is defined by the expression x!(ν) which specifies the transmission/sending to the agent x (x ∈ Λ) of some message ν and the expression x?(ν) means that the message ν is received from some agent x.

Let Act = O ∪ {τ }, be the set of actions, where τ is the internal action. The AgLOTOS language specifies pairs for each elementary plan composed of an identifier and an AgLOTOS expression to feature its plan behavior.

Consider that the set of elementary plan's names is ranged over by P 1 , P 2 , ... and that the set of all the possible behavior expressions is denoted E, ranged over by E 1 , E 2 , .... The expressions are written by composing actions through LOTOS operators. The syntax of an elementary plan P is defined inductively as follows:

P ::= E E ::= exit | stop | a; E | E E (a ∈ O) | hide L in E H ::= move( ) (H ⊂ O, ∈ Θ) | x!(ν) | x?(ν) (x ∈ Λ) = { [ ], , [>, |[L]|, ||, ||| }
The elementary expression stop specifies a plan behavior without possible evolution and exit represents the successful termination of some plan. In the syntax, the expression hide L in E denotes a hiding of the actions of L that appear in E. The set represents the standard LOTOS operators:

E [ ] E specifies a non-deterministic choice, E E a sequential composition and E [> E the interruption. The LOTOS parallel composition, denoted E |[L]| E, can model both synchronous composition, E || E if L = O, and asynchronous composition, E ||| E if L = ∅.
Building of Agent Plan from Intentions: In order to account for any BDI state of the agent, we propose that the agent can order the different elements of the set I of intentions1 by using a weight function weight : I -→ N. The ones having the same weight are composed by using the concurrent parallel operator |||. In contrast, the intention plans corresponding to distinct weights are ordered by using the sequential operator . For instance, let I = {i 2 g , i 1 e , i 2 m } be the considered set of intentions, such that the superscript information denotes a weight value, and let P g , P e , P m be their corresponding intention plans, the constructed agent plan could be viewed as: P = ( P g ||| P m ) P e .

III. CONTEXTUAL PLANNING SYSTEM

With respect to some agent plan P , we introduce a notion of configuration, denoted [P ], referring to the planning state of the agent in order to specify its plan evolution. We will now define the contextual planning state of the agent, taking into account the agent location and the outcomes of different intention plans defined for the agent.

Definition 3.1: A contextual planning state is a tuple (ps, , T ), where ps is any planning state described by an agent plan configuration [P ], corresponds to the possible location for the agent in this state, and T is the subset of intention plans who terminate successfully in this state.

The AgLOTOS operational semantics is used to specify the contextual possible planning state changes for the agent.

In this paper, it is applied to produce a Contextual Planning transition System, called CPS, from an initial contextual planning state, e.g. (ps, , ∅), meaning that the agent is initially at location and ps is its planning state.

Definition 3.2: The Contextual Planning System (CPS) is a labeled Kripke structure S, s 0 , T r, L, T where:

• S is the set of contextual planning (CPS) states,

• s 0 = (ps, , ∅) ∈ S is the initial CPS state of the agent, • T r ⊆ S × Act × S is the set of transitions. The transitions are denoted s a -→ s s.t. s, s ∈ S and a ∈ Act, • L : S → Θ is the location labeling function,

• T : S → 2 P is the intention termination labeling function which captures the intention plans that have been completed.

A. Illustrative Example

Let us consider two agents Alice and Bob. The scenarios of Alice and Bob are specified separately. It is assumed that Bob and Alice may coordinate in order to achieve their intentions, at their mental process levels. The actions in plans are simply expressed using instantiated predicates, like getc( 2 ) for the 'get copies' action. Intention plans are composed of elementary plans which are viewed as concurrent processes, terminated by exit, a la LOTOS. For instance, the set I B = {meeting(Alice, 1 ), getting copies( 2 )} is defined for Bob, containing two concurrent intentions of the same weight.

The associated agent plan is: P B = ( P g ||| P m ), where P m and P g are two concurrent intention plans to be achieved. The first one corresponds to the intention meeting(Alice, 1 ) and the second to getting copies( 2 ). For sake of simplicity, both intention plans only contain one elementary plan each, without other alternatives. Here, P m = move( 1 ); meet(Alice); exit m and P g = getc( 2 ); conf irm; exit g . The resulting agent plan expression for Bob is thus to act two concurrent processes:

(1) get the copies locally in 2 and confirm this to Alice (Alice!(conf irm)) and (2) move to 1 to meet Alice there.

An example of derivation from the initial planning state is to perform the getc action. So, the planning state change from

[P B ] getc --→ [P B ], yields [P B ] = move( 1 ); meet(Alice); exit m ||| conf irm; exit g .
The Contextual Planning System of Bob, denoted CP S B , is illustrated in Figure 2. It is built from the initial CPS state, s 0 = ([P B ], 2 , ∅), taking into account the current location 2 of Bob.

B. Guidance for Intention Satisfaction

In a CPS, the transitions from any (source) state s a -→ s represent actions to be performed. Like in the STRIPS description language [START_REF] Meneguzzi | Incorporating planning into BDI agents[END_REF], actions are modeled by instantiated predicates defined with preconditions and effects. In this paper, the preconditions concern only the contextual For instance in Figure 2, the dashed edges represent the disabled transitions from the states s ∈ {s 2 , s 5 , s 8 }, because pre(getc( 2 )) = 2 = L(s).

ℓ 2 ℓ 2 ℓ 1 ℓ 1 ℓ 1 ℓ 1 ℓ 1 , { P m } , { P m } s 6 s 10 τg move s 13 s 15 ℓ 2 , { P g } ℓ 1 , { P g } ℓ 1 , { P g } ℓ 1 , { P g , P m } conf irm conf irm conf irm ℓ 1 , { P m } ℓ 1
In order to guide the agent, the planning process can select an execution trace which maximizes the number of intentions that can be satisfied. This can be captured over the set Σ ⊆ 2 T r of all possible traces of the CPS. We introduce the notion of maximum trace based on the mapping end : Σ -→ 2 P , used to specify the set end(σ) of the different terminated intention plans that occur in a trace σ ∈ Σ. Let Σ M AX represent the set of maximum traces of the CPS.

As a specific tree structure, Figure 5 represents the 10 maximum traces of CP S B . In this unfolded version of Figure 2, the trace carried out by s 0 → s 2 → s 5 → s 9 , is not represented because it is not a maximum trace.

IV. LEARNING ACTIONS FROM PAST-EXPERIENCES

In order to improve the agent runtime performance, the planning process, in relation to the execution process, can capture the running of actions in a given context (current location and current time). The use of the learned data in a pertinent way allows us to build an enriched CPS structure, called CPS with Learning (CPS-L for short). As a result, the best possible strategic decisions are taken, driven by the agent and its preferences.

A. Data acquisition

The performance of an action a is evaluated w.r.t. a given context, however we focus on location. Each concrete performance of a in some location is considered as an (action) experience. • outcome ∈ {-1, 1}, is the result of the run performing a, respectively a failure or a success, • start ∈ R + , is the start date for the run of a,

• duration ∈ R + , is the action duration which provides that a was successfully terminated, undefined otherwise. The structure represented in Figure 3 is generically called the Learned Contextual Experiences (LCE). Regarding to the action a, LCE a shows different FIFO queues of experiences of a, distinguishing the different locations where the action was performed. The queue LCE a ( ) is ordered by the start date of the runs, so that the last recorded experience is at the top of the queue.

More precisely, if an action a is performed in some location with a certain experience exp, the agent may push it s.t. LCE a ( ) = LCE a ( ) ∪ {exp}. Moreover, k represents the effective size of LCE a ( ). Regarding to any experience exp of a queue LCE a ( ), we denote by index(exp) the position of exp in the queue. Further, the three components of a past-experience exp are respectively denoted exp.outcome, exp.start, exp.duration.

B. Data Relevance Strategies

The strategy information specified by the agent is given by the following definition and described below.

Definition 4.2: The queues of LCE are parameterized by the agent strategy S = K, f orget, M, C, f ilter where,

• K is the maximum size of the queue, • f orget : 1..K → R + is the forgetting function, yielding a relevance weight for each experience,

• M ≤ K is the maximum number of filtered experiences,

• C is a periodic classification, e.g. daily, weekly, monthly or annual, applied in a modulo operation over the start dates of the queue,

• f ilter defined over any queue is a time filtering function yielding a sub-queue according to M and C,

The Forgetting Strategy. For all the queues in LCE a , the forgetting function associates a relevance weight for each experience stored in the queue. As an interesting case illustrated in Table I For instance, the experience C stored at the index 10 in the queue LCE getc ( 2 ) has a forget value of f orget(10) = 0.10, whereas the experience F stored at the index 18 has a forget value of f orget(18) = 0.05.

Observe that every queue LCE a ( ) is bounded by K elements. Beyond the forgetting of the extra (older) data, this allows one to tackle the data explosion problem implied by the consideration of many experiences over LCE. Indeed, in case the queue is full, the adding of a new experience causes the removing of the oldest one.

The Time Filtering Strategy. Regarding to any queue LCE a ( ), in order to operate the selection, both the start dates of experiences and the current date value 'date' are evaluated through some classification period C. For this purpose, we introduce the function mod : C × R + → R + , s.t. mod C (date) corresponds to the start date modulo the classification period C (we consider standardly that date can be viewed as its textual form or like real timestamp value). For instance, if date = 'Monday 10 February 2015, 10:00', then t = mod daily (date) = 10 whereas mod weekly (date) ='Monday 10'. We filter the queue experiences in order to only consider the ones which have the smallest time interval (|t-mod C (exp.start)|). The mapping f ilter M,C (t) of LCE a ( ) specifies that M experiences must be selected. In case M is greater than the size k of the queue, all the past-experiences of the queue are considered.

In Table I, the applied filtering is f ilter 6,daily (10) = {A, B, C, D, E, F} which means that LCE getc ( 2 ) is filtered on the 6 closest experiences, w.r.t. t = mod daily (date) = 10. As illustrated in Figure 4 for mod daily (t) over the start dates of LCE getc ( 2 ), the modulo operation applied to the queue graphically yields a spiral ribbon, the rings of which correspond to the successive periods, e.g. days in our example. Daily speaking, the start dates of the experiences A, B and C occur before t, and the ones of D, E and F occur after t.

In this example, we have taken the following instantiated strategy: S 1 = (20, 1 index , 6, daily, f ilter).

EP a ( ) = f ilter M,C (t) exp exp.outcome * f orget(index(exp)) f ilter M,C (t) exp f orget(index(exp))
When performing a in , the closest EP a ( ) is to '1', the greater the chance for success, whereas the closest EP a ( ) from '-1', the greater the risk of failure. In the case LCE a ( ) = ∅ meaning that the running of a in has not been already explored, we choose EP a ( ) = 0 in order to privilege the exploration against every (bad) case s.t. EP a ( ) < 0.

Again for each non empty queue LCE a ( ), the expected duration value ED a ( ) ∈ R + corresponds to the effective durations of the M filtered experiences, according to:

ED a ( ) = f ilter M,C (t) exp exp.duration * f orget(index(exp)) f ilter M,C (t) exp f orget(index(exp))
Coming back to the frame example, from t = 10, we obtain EP getc ( 2 ) = 0.19. Moreover, ED getc ( 2 ) = 3.16, which in real time, this stands for 3h10mn. Observe that the past-experience F has a weak impact on ED getc ( 2 ) despite its important duration (5.12). In fact, the forgetting function applied to its (important) 18 index, makes it negligible compared to the other filtered past-experiences of lower indexes.

V. SPATIO-TEMPORAL GUIDANCE FROM PAST-EXPERIENCES

A. Contextual Planning System with Learning (CPS-L)

The structure CPS-L inherits from the maximum traces Σ M AX of the CPS, augmented by the different values EP a ( ) and ED a ( ) whatever the action a to run in .

Definition 5.1: Let Σ M AX be the set of the maximum traces of a CPS built from the set of intentions of the agent. The Contextual Planning System with Learning CPS-L is a tuple CP S, EP, ED where:

• CP S = S, s 0 , T r, L, T s.t. Σ M AX ⊆ 2 T r is the set
of the maximum traces of the CPS.

• EP is a mapping from T r to [-1, 1], s.t. from each transition tr = (s, a, s) ∈ Σ M AX , EP(tr) = EP a (L(s)),

• ED is a mapping from T r to R + , s.t. from each transition tr = (s, a, s) ∈ Σ M AX , ED(tr) = ED a (L(s)). From the CPS-L, it is straightforward to extend the expected quality values to every maximum trace σ (σ ∈ Σ M AX ), in order to compare them, as follows:

QP (σ) = σ tr∈T r EP(tr) |σ| QD(σ) = σ tr∈T r

ED(tr)

To compare the traces between them, we normalize all the expected quality values to be in [-1, 1], s.t. '-1' represents the worst case and '1' the best one. This is already done for QP , moreover, to normalize QD, we consider the extreme values QD min = min(QD(σ) | σ ∈ Σ M AX ) and QD max = max(QD(σ) | σ ∈ Σ M AX ). We obtain the normalized quality of duration, as follows:

N QD(σ) = 1 - QD(σ) -QD min QD max -QD min * 2
In Figure 5, the edges of two maximum traces are augmented by the two values EP and ED, as in the CPS-L structure. For instance, the values EP getc = 0.19 and ED getc = 3.16 are attached to the transition (s 0 , getc, s 1 ) computed from the values of LCE a ( ), specified in Table I, are attached to the transition (s 0 , getc, s 1 ).

As shown in Figure 6, the traces the quality of which enters the right-upper part of the figure are the best ones, and the ones entering the left-lower part are the worse ones. The other traces having a single high value either for QP or N QD enter the two other parts of the figure.

B. Optimal Traces of CPS-L

We now consider that in addition to intentions I and strategy S, the mental process can specify a preferred balance denoted B between the two qualities for traces, performance and normalized duration. It the optimal (maximum) trace to be selected, namely σ opt . The balance is expressed as a proportion to be applied to the QP and N QD values, in order to obtain a comparable global quality value Q B (σ) belonging to [-1, 1] for all maximum traces (σ ∈ Σ M AX ). Of course, the trace σ opt of the maximum quality is returned by the planning process. 5, knowing that over all maximum traces, we obtain QD min = 7.58 and QD max = 10.23. Moreover, the balance B1 specified by the mental process, is the pair (B1 P = 0.30, B1 D = 0.70). Since Q B1 (σ 2 ) is greater than Q B1 (σ 1 ), the maximum trace σ 2 can be offered to the execution process as the optimal maximum trace. In contrast for B2 (B2 P = 0.70, B2 D = 0.30), σ 2 is the one that can be offered (Q B2 (σ 1 ) > Q B2 (σ 0 )). The algorithm 1 is a synthesis of all our approach.

Q B (σ) = B P * QP (σ) + B D * N QD(σ)

Learning and planning

Learning aims to improve the behavior of intelligent agents thanks to the experimental-based information. It has been involved at various levels of the agents. Learning was first investigated at the mental level of BDI agents either to improve the BDI deliberation from some learned knowledge e.g. [START_REF] Merke | Karlsruhe brainstormersa reinforcement learning approach to robotic soccer[END_REF] or to produce a new plan with respect to some objective e.g. [START_REF] Karim | Plans as products of learning[END_REF].

Learning was also used to reinforce the selection of plans among different possible alternatives. In particular, a decision tree was introduced by [START_REF] Guerra-Hernandez | Learning in bdi multi-agent systems[END_REF] to represent the different contexts in which the agent behaves. Indeed, the behavior of the agent is learned from the successes and failures of the executions of the agent's plans. The idea to take advantage from the past execution experiences was adapted in [START_REF] Airiau | Incorporating learning in BDI agents[END_REF] bringing out an on-line technique, based on a hierarchical goal-plan structure, in order to make the selection of some alternative according to the failures of the previous ones.

The work proposed in [START_REF] Nunes | Softgoal-based plan selection in model-driven bdi agents[END_REF] addresses plan selections. Closer to our approach, it proposes to evaluate the contribution of each plan in terms of utility and preferences seen as parameters for optimization. In our approach the utilities are given by the agent and are similar to the concept of softgoal and the preferences discussed in [START_REF] Nunes | Softgoal-based plan selection in model-driven bdi agents[END_REF]. They correspond, in our approach, to a multi-objective strategy based on the proportions of performances and temporal filtering information, together used for the selection of some maximum traces. Let us notice that our traces depend of real experiments instead of pre-established probabilities.

For the two last approaches [START_REF] Nunes | Softgoal-based plan selection in model-driven bdi agents[END_REF], [START_REF] Waters | Evaluating coverage based intention selection[END_REF], the validation of the proposed techniques requires a huge number of experiences since they are based on probabilities. In this paper, unlike the former proposals, our approach is driven by the maximization of intentions' satisfaction, in order to guide the agent through the set of paths implied by the concurrency of actions.

The learned CPS can be viewed as reinforcement learning for the selection of elementary plans but based on the successes and failures of the executed actions. Actually, the selection of a path implies the selection of some alternative for each intention plan. The queues recording the pastexperiences of actions are bounded in order to tackle the combinatorial complexity introduced by their management. This approach is compatible with the idea of forgetting useless history.

Regarding the relevance strategies, our technique is aligned with earlier propositions like the Q-learning algorithm. The last one learns a quality value for each action taking into account that the known values become deprecated as the time progresses, under a function like = 1/t. In our context, the applied forgetting function (1/x) allows us to privilege the most recent past-experiences according to a logical recording time.

Finally, our plans are built dynamically by reasoning on situated actions and their context (duration, start, locality, etc.) which is valuable for dynamic environment and contexts.

VII. CONCLUSION

This paper proposes an original approach to deal with BDI agent planning in a dynamic context. The framework is based on AgLOTOS algebraic language which is suitable to specify an agent plan as a set of concurrent processes, helped by a plan library describing elementary plans. The semantics of AgLOTOS allows to build, as structure, a Contextual Planning System (CPS), for any BDI state of the agent. From the current set of intentions, all the possible evolutions of a plan can be evaluated through the CPS.

The CPS structure has been enriched with contextual and spatio-temporal information related to past-experiences of the agent. Improved with learning, our CPS allows to learn situated actions in order to qualify them with relevant attributes (success or failure, durations, starting time, etc.) and to combine these actions in order to reactively build robust plans in a dynamic context. Consequently, our approach provides a built-in look-ahead mechanism to contextually guide the agent in his future executions. This guidance, thanks to learning from past experiences, optimizes the number of satisfied intentions while respecting the agent strategies based on his utilities and preferences.

This work has been applied in the context of ambient intelligence where the concepts of "location" and "context" are the key stone of such systems. As future work, we plan to tackle the problem of the verification of formal properties of this planning system which based on formal specification language and techniques. We plan also to extend our experiment to the context of a major project called "SMART" in which we develop the " SMART CAMPUS " Framework.

Figure 1 .

 1 Figure 1. Agent planning structure

Figure 2 .

 2 Figure 2. The CP S B corresponding to the plan P B

Figure 3 .

 3 Figure 3. Learned Contextual Experiences (LCE) of an action a

1 day - 2 day - 3 Figure 4 .

 1234 Figure 4. The example of the queue LCEa( )

2 Figure 5 . 2 Figure 6 .

 2526 Figure 5. Maximum traces and CP B for the plan P B QP

  helps characterizing

					getc
	s 6		s 7			s 8		s 9
			meet
	s 11	s 12	s 13		s 14		s 15	s 16		s 17
	s 18	s 19	s 20	s 21	s 22	s 23	s 24	s 25	s 26	s 27
	s 28	s 29	s 30	s 31	s 32	s 33	s 34	s 35	s 36	s 37

Table II COMPUTED

 II QUALITY VALUES OF σ 1 AND σ 2 MAXIMUM TRACESTable II highlights the qualities of two maximum traces σ 1 and σ 2 of Figure

	Σ M AX	QP	QD	N QD	Q B1	Q B2
	σ 1 σ 2	0.42 -0.04	9.74 8.54	-0.63 0.27	-0.31 0.17	0.10 0.05

We assume that the BDI agent himself can solve conflicting situations that could arise between intentions for some context, by means of a scheduling process applied to the set of intentions.