Hiep Nguyen
email: thhnguen@toulouse.inra.fr

Simon De Givry
email: sdegivry@toulouse.inra.fr

Thomas Schiex
email: tschiex@toulouse.inra.fr

Christian Bessiere
email: bessiere@lirmm.fr

Maintaining Virtual Arc Consistency Dynamically During Search

Keywords: Weighted CSP, Cost Function Networks, arc consistency, dynamic arc consistency, virtual arc consistency

Virtual Arc Consistency (VAC) is a recent local consistency for processing cost function networks (aka weighted constraint networks) that exploits a simple but powerful connection with standard constraint networks. It has allowed to close hard frequency assignment benchmarks and is capable of directly solving networks of submodular functions. The algorithm enforcing VAC is an iterative algorithm that solves a sequence of standard constraint networks. This algorithm has been improved by exploiting the idea of dynamic arc consistency between each iteration, leading to the dynamic VAC algorithm. When VAC is maintained during search, the difference between two adjacent nodes in the search tree is also limited. In this paper, we show that the incrementality of Dynamic VAC can also be useful when maintaining VAC during search and we present results showing that maintaining dynamic VAC during search can effectively accelerate search.

I. INTRODUCTION

Graphical model processing is an important problem in Artificial Intelligence. The optimization of the combined cost of local cost functions, central in the valued CSP framework [START_REF] Schiex | Valued constraint satisfaction problems: hard and easy problems[END_REF], captures a variety of problems such as Weighted CSP, Maximum Probability Explanation in probabilistic networks or weighted MaxSAT. It has applications in resource allocation [START_REF] Cabon | Radio link frequency assignment[END_REF], combinatorial auctions, bioinformatics [START_REF] Traoré | A new framework for computational protein design through cost function network optimization[END_REF],. . . A variety of techniques can be used to solve this problem. When the problem has a graph of bounded tree-width, it can be solved using dynamic programming approaches such as bucket or cluster tree elimination. In the general case, Depth First Branch and Bound (DFBB) has the advantage of a reasonable space complexity. However, DFBB requires strong and computationally inexpensive incremental lower bounds on the minimum cost of a node to be efficient. These bounds can also be useful in the context of AND/OR and Tree decomposition based tree search algorithms [START_REF] Dechter | And/or search spaces for graphical models[END_REF], [START_REF] De Givry | Exploiting Tree Decomposition and Soft Local Consistency in Weighted CSP[END_REF], or more space intensive search algorithms such as A*.

In the last decade, increasingly better lower bounds have been proposed for optimization in graphical models. They can be local consistency based bounds for solving Cost Function Networks [START_REF] Cooper | Soft arc consistency revisited[END_REF] (CFNs), MaxSAT resolution based for solving the Partial Weighted MaxSAT problem [START_REF] Larrosa | A logical approach to efficient max-sat solving[END_REF], [START_REF] Li | New inference rules for max-sat[END_REF], or Linear programming dual based bounds for computing a maximum probability assignment in Markov Random Fields [START_REF] Wang | Subproblem-tree calibration: A unified approach to max-product message passing[END_REF]: they all reformulate the current problem in a new equivalent problem using local cost transfer operations, also known as Equivalence Preserving Transformations (EPTs, [START_REF] Cooper | Arc consistency for soft constraints[END_REF]). EPTs extend the traditional local consistency operations by moving costs between cost functions of different arities while keeping the problem equivalent. By ultimately moving cost to a constant function with empty scope, they are able to provide a lower bound on the optimum cost which can be incrementally maintained during branch and bound search.

Traditional local consistencies such as AC*, DAC*, FDAC* or EDAC* [START_REF] Cooper | Soft arc consistency revisited[END_REF], [START_REF] Larrosa | Existential arc consistency: getting closer to full arc consistency in weighted CSPs[END_REF], apply available EPTs in any order. Instead, Virtual Arc Consistency (VAC [START_REF] Cooper | Soft arc consistency revisited[END_REF], [START_REF] Cooper | Virtual Arc Consistency for Weighted CSP[END_REF]) planifies the sequence of EPTs to apply from the result of enforcing AC on a standard constraint network which forbids tuples with non zero cost. VAC is not only stronger than those local consistencies: it is also able to directly solve networks of submodular cost functions, it has a low order polynomial time enforcing algorithm and has allowed to close hard frequency assignment benchmarks [START_REF] Cooper | Virtual Arc Consistency for Weighted CSP[END_REF]. However, it is still quite expensive for general use and needs to be accelerated.

In this paper, we show that the efficiency of maintaining VAC during search, just like its iterative behavior, can be accelerated by exploiting the incrementality of the changes due to branching operations. Indeed, whether an iteration of VAC has just been executed or a decision has been taken by Branch and Bound search, maintaining VAC requires to repeatedly enforce standard AC on the hardened version of an incrementally modified version of the problem. The exploitation of incremental changes while maintaining Arc Consistency is the traditional target of Dynamic Arc Consistency algorithms [START_REF] Barták | An improved algorithm for maintaining arc consistency in dynamic constraint satisfaction problems[END_REF], [START_REF] Bessière | Arc-consistency in dynamic constraint satisfaction problems[END_REF] for Dynamic CSPs [START_REF] Dechter | Belief maintenance in dynamic constraint networks[END_REF]. We show that, just like the incremental changes of EPTs during successive iterations of VAC [START_REF] Nguyen | Dynamic virtual arc consistency[END_REF], the incremental changes between the problems considered at adjacent nodes in the search tree can be suitably exploited by Dynamic Virtual Arc Consistency, leading to a global improvement of the efficiency on a variety of problems extracted from the Cost Function Library1 and other related resources.

II. BACKGROUND

A Cost Function Network (CFN), aka weighted CSP (WCSP) is a tuple P = (X, D, W, m) where X is a set of n variables. Each variable i ∈ X has a domain D i ∈ D. For a set of variables S, we denote by (S) the set of tuples over S. W is a set of e cost functions. Each cost function w S ∈ W assigns costs to assignments of variables in S i.e. w S : (S) → [0..m] where m ∈ {1, ..., +∞}. The addition and subtraction of costs are bounded operations, defined as a + m b = min(a + b, m), am b = a -b if a < m and m otherwise. The cost of a complete tuple t is the sum of costs Val P (t) = w S ∈W w S (t[S]) where t[S] is the projection of t on S. We assume w.l.o.g. the existence of a unary cost function w i for every variable, and a nullary cost function, noted w ∅ . All costs being non negative in a CFN, this constant cost defines a lower bound on the cost of every solution. In this paper, for simplicity, we restrict ourselves to binary CFNs.

Enforcing a given local consistency on a CFN P transforms it in an equivalent problem P (such that Val P (t) = Val P (t) ∀t) with a possibly increased lower bound w ∅ . The equivalence-preserving transformations (EPTs) which shift costs between cost functions are the elementary operations of local consistency enforcing. Algorithm 1 describes the main EPTs used for enforcing arc consistency, which shifts a cost α > 0 between a binary cost function w ij and a value (i, a). This operation corresponds to either a projection of costs from w ij to (i, a) when α > 0 or an extension of costs from (i, a) to w ij when α < 0. In node consistency, similar cost transfers can occur from unary cost functions to w ∅ , thus strengthening the lower bound.

2 w i (a) ←-w i (a) + α ; 3 foreach b ∈ D j do w ij (a, b) ←-w ij (a, b) -α ;
Notice that a standard constraint network (CN) P can be represented as a CFN with m = 1 (a cost of 1 is associated with forbidden tuples). In a binary CN, represented as a CFN with m = 1, a value (i, a) is Arc Consistent (AC) w.r.t. a constraint w ij iff there is a pair (a, b) that satisfies w ij (is a support) and such that b ∈ D j (is valid). A CN is AC if all its values are AC w.r.t. to all constraints. Enforcing AC on a CN produces its AC closure, which is equivalent to P and is AC.

III. DYNAMIC VAC

A. Virtual arc consistency Definition 1. Given a CFN P = (X, D, W, m), the CN Bool(P ) = (X, D, W , 1) is such that ∃w S ∈ W iff ∃w S ∈ W , S = ∅ and w S (t) = 1 ⇔ w S (t) = 0. A CFN P is virtual arc consistent (VAC) iff the arc consistent closure of the CN Bool(P ) is non-empty [START_REF] Cooper | Soft arc consistency revisited[END_REF].

Bool(P ) is therefore a CN whose solutions are exactly all the complete assignment having cost w ∅ in P . If P is not VAC, enforcing AC on Bool(P ) will lead to a domain wipeout. In this case, it has been shown in [START_REF] Cooper | Soft arc consistency revisited[END_REF] that there exists a sequence of EPTs which, when applied on P , lead to an increase of w ∅ . To exploit this property, VAC enforcing uses an iterative process, each iteration being decomposed in three phases.

• Phase 1 is an instrumented AC enforcing on the CN Bool(P ) that records the cause of every deletion in a dedicated data-structure denoted as killer. killer(i, a) = j means that (i, a) has been deleted because of w ij . killer(i, a) = i means that (i, a) is a value deleted because of its own positive cost. Otherwise, killer(i, a)= nil is used when (i, a) is not deleted in Bool(P ). When a value (i, a) lacks a valid support on w ij , we set killer(i, a) = j and we delete the value. If no domain wipe-out occurs, P is VAC and we stop. • Otherwise, Phase 2 is performed to identify a minimal subset of value deletions that are necessary to produce the wipe-out by tracing back the propagation history defined by killer, in reverse order, from the wiped-out variable up to non-zero costs. Phase 2 also computes the maximum possible increase achievable in w ∅ and the set of EPTs to apply to P in order to achieve this increase. • Phase 3 of VAC, modifies the original CFN by applying the EPTs defined in Phase 2. These 3 phases can be iterated until the problem is VAC or until the lower bound does not increase more than a threshold ε. In this last case, we say that we enforce VAC ε . In all cases, each iteration leaves a locally reformulated problem which is used as the starting point of the next iteration.

B. Dynamic Virtual Arc Consistency

Ultimately, VAC iterations therefore enforce AC on a sequence of slightly modified CNs: Bool(P ), Bool(P ), . . . The first proposed VAC enforcing algorithm [START_REF] Cooper | Soft arc consistency revisited[END_REF] enforces AC from scratch on each of these problems. The incremental changes on P performed at Phase 3 of each iteration induce incremental changes in Bool(P ), and this motivated the use of dedicated Dynamic AC (DnAC) algorithms to enforce VAC [START_REF] Nguyen | Dynamic virtual arc consistency[END_REF].

The aim of DnAC algorithms is to maintain AC in CN problems after constraint additions or retractions. Among existing algorithms proposed for DnAC, the AC/DC2 algorithm has been used because of its simplicity and good empirical results [START_REF] Barták | An improved algorithm for maintaining arc consistency in dynamic constraint satisfaction problems[END_REF]. AC/DC2 uses a data structure justification(i, a) to remember the cause of deletion for (i, a). This is exactly equivalent to the killer data-structure of VAC and therefore justification is available for free. The DynVAC algorithm proposed in [START_REF] Nguyen | Dynamic virtual arc consistency[END_REF] uses a version of AC/DC2 [START_REF] Barták | An improved algorithm for maintaining arc consistency in dynamic constraint satisfaction problems[END_REF] based on AC2001 instead of AC3.

AC being naturally incremental for restriction, the addition of a constraint can be directly handled by any coarse grained AC algorithm that relies on a variable based propagation queue Q AC by pushing the variables of the new constraint in Q AC . Relaxation (constraint removal) is not so easy. In this case, AC/DC2 goes through three stages. In the initialization stage, only values which have been deleted because of the removed constraint w ij are considered as candidates for restoration. In the propagation stage, all the neighboring values (k, c) of a variable i having restored values and that have been removed due to the lack of support on the constraint w ki (known through justification≡ killer) are iteratively restored. In a last stage, all restored values need to be checked again for arc consistency.

In the case of VAC, at each iteration, a series of modifications of Bool(P ) can occur during Phase 3 through the application of the identified sequence of EPTs. It has been shown in [START_REF] Nguyen | Dynamic virtual arc consistency[END_REF] that the global effect of the EPTs applied on Bool(P ) in Phase 3 consists only in a series of relaxations, at the unary and binary levels. More precisely, when the application of Phase 3 transforms the previous CFN P in an equivalent CFN P , values or pairs with non zero cost in P and therefore forbidden in Bool(P ) may become authorized in Bool(P ) if their cost becomes 0 in Bool(P ).

Therefore, the DnAC algorithm used can be specialized for relaxations in Dynamic VAC. The restoration protocol has 3 stages, as in AC/DC2. The initialization stage aims at identifying restorable values. As shown in [START_REF] Nguyen | Dynamic virtual arc consistency[END_REF], this stage can be performed after Phase 2 because it is already possible to compute the values of the reformulated cost functions w i and w ij of P . This stage scans only values on which EPTs will be performed in Phase 3 and restores all restorable values. When a value (i, a) is restored, it is stored in an array restored[i] and variable i is kept in a list RL for future propagation.

The propagation stage propagates value restorations to direct neighbours of the variables whose domain has been extended, as in AC/DC2. Each such variable i can restore a value (j, b) if it was deleted due to w ij and is now supported by a restored value in i.

The final filtering stage eliminates the restored values (i, a) which are not arc consistent on some constraint w ij and properly set the associated killer(i, a) to j. This is precisely what is achieved by the Phase 1 of VAC. Hence, this stage is integrated into Phase 1 by adding the neighbour variables of variables having restored values into the revision propagation queue Q AC .

IV. MAINTAINING DYNAMIC VAC DURING SEARCH

The standard way to maintain VAC during search is to rebuild the CN Bool(P ) at each new node and then use this new Bool(P ) to enforce VAC in the CFN P . If DynVAC has been shown to enhance VAC efficiency for preprocessing CFNs at the root node, DynVAC has never been maintained during search.

Similarly, the simplest way to maintain Dynamic VAC during search consists in enforcing Dynamic VAC at each node. However, maintaining Dynamic VAC during search offers new opportunities for incrementality. In this section, we show that VAC can be incrementally maintained not only between successive iterations of VAC inside a node, but also during search between nodes, by incrementally maintaining an AC-closure of Bool(P ) beween search nodes.

Between two consecutive nodes, the CN Bool(P ) is only modified according to the changes in P caused by branching operations. The branches out of a node can be the assignment of a variable (i = a) or a domain restriction (i = a), (i < a) or (i > a). We expect that maintaining AC with a Dynamic AC algorithm in such a slightly modified Bool(P ) will be beneficial compared to a cold restart. Suppose that branching operations transform the current CFN P into P |i=a , P |i =a , P |i>a or P |i<a . We denote all these different cases as P |i . After a branching operation, P |i will have modified domains and also possibly modified cost functions. These will be respectively denoted as D and w i or w ij . To enforce VAC incrementally between nodes, we need to compute the AC closure of Bool(P |i ) from the AC closure of Bool(P ) using only the modification from P to P |i .

When a variable domain D i is restricted by a branching operation of the form (i = a), (i < a) or (i > a) that does not reduce the domain to a singleton, the removal of values leads to a new domain D i and thus a new domain, denoted as D i , in the currently computed AC closure of Bool(P |i ). Some values of the neighboring variables j may have lost their support on w ij in Bool(P |i ) and thus need to be checked for AC. Similary to the case of constraint restriction, this can be naturally achieved by DnAC by (1) adding the neighbour variables of i in the propagation queue Q AC and (2) restarting propagation to remove all values which are arc inconsistent in Bool(P |i ) due to this domain restriction.

When instead, an assignment is performed (or equivalently the domain is reduced to a singleton), solvers exploits this very specific situation to directly eliminate the variable i from the problem. Therefore, the modifications caused by a variable assignment (i = a) are more complex than for other domain reductions. Indeed, when the domain of a variable i is restricted to a single value a, the unary cost w i (a) of (i, a) is immediately projected on w ∅ . Then binary costs w ij (a, b) are also projected on neighboring values (j, b) of i and the binary cost functions w ij are removed from the CFN P |i=a . Property 1. The CFN P |i=a = (X, D , W ) which is obtained from P by a variable assignment (i = a) satisfies t he following properties: a) w i (a) = 0. b) for every variable j, there is not cost function w ij connecting i and j. c) for every value (j, b) such that ∃w ij in P , we have

w j (b) = w j (b) + w ij (a, b).
Figure 1 lists all the situations that can happen after a variable assignment (i = a) for the values (j, b) of a neighbor variable j. It shows that, except for the two cases that will be considered later in Corollary 2, the deleted/non deleted status of (j, b) remains unchanged in Bool(P |i=a ). To show this, we first prove the following Corollary of Property 1:

Corollary 1. The CN Bool(P |i=a ) satisfies the following Proof. a) The constraints of Bool(P |i=a ) are directly defined from the cost functions of P |i=a . From Property 1b), we know that there does not exist any w ij in P |i=a where j = i. Therefore, there also does not exists any constraint w ij in Bool(P |i=a ). As a result, j is arc consistent with variable i. b) In Bool(P |i=a ), (i, a) cannot be deleted because of its positive cost since w i (a) = 0 according to Property 1a). Moreover, (i, a) cannot be killed by any other variable j because no constraint links i to other variables in Bool(P |i=a ).

Considering the various the cases where the status of (j, b) does not change, most are straightfoward. The only non obvious case is when w j (b) = w j (b) = 0 and (j, b) is arc consistent in Bool(P ). This implies that (j, b) is arc consistent with every variable k = i in Bool(P ). Because the variable assignment does not change cost functions w jk , (j, b) will still be arc consistent with k in Bool(P |i=a ). In addition, Corollary 1a) indicates that (j, b) is also arc consistent with i in Bool(P |i=a ). Therefore, being arc consistent with every variable and having a zero unary cost, (j, b) is an arc consistent value in Bool(P |i=a ) (and it has the same status as in Bool(P )).

Then, as shown in Figure 1, there are two cases where the status of values may change compared to the status in Bool(P ), requiring to update Bool(P |i=a ) . This is proved in Corollary 2. In all other cases, as we saw, the status of values in Bool(P |i=a ) remains the same as in Bool(P ). For the dynamic AC point of view, this corresponds to the relaxation of a unary constraint on j (domain relaxation) and (j, b) needs to be considered as restorable.

In summary, the change in a cost function network P caused by variable assignments can lead to both the restoration and the removal of values in the CN Bool(P ). DnAC can perform this combined work by using two dedicated queues Q AC and RL, the former for propagating value removals and the second for value restorations. Q AC stores variables whose domain has been reduced while RL stores variables whose domain has been relaxed.

Procedure assign(i, a) in Algorithm 2 is used to update P and Bool(P ) when assigning (i = a). The unary cost of (i, a) and binary costs of pairs of values ((i, a), (j, b)) are respectively projected on w ∅ and on w j (b) (line 3, 9). Only neighboring values (j, b) of i are considered (line 5). New values of non-zero cost (line 6) will be removed from Bool(P ) (line 7). The removal of (j, b) can further lead to the removal of other values. Thus, j is pushed into queue Q AC for the future revision for AC (line 8). Conversely, if (j, b) has been removed by i and still has a zero cost (line 10), it is restorable and will be restored (line 11). This is done by Procedure restore(j, b) at line 25 which adds b into array restored[j] and adds j into queue RL for the future propagation of value restorations. Array restored[j] contains values of i that have just restored in Bool(P ) and wait for being propagated. After defining all values to be removed and restored because of the value assignment for i, the algorithm will do the propagation for value restorations and then for value removals (line 13, 14 respectively).

AC-revise(Q AC ) is simply the usual instrumented AC enforcement used in VAC while relaxation(RL) aims to propagate value restorations in Bool(P ). At each iteration of Procedure "relaxation" (line 15), a variable i is popped from RL. i ∈ RL means that some value of i have been restored. The restored values of i can provide AC supports (line 20) for neighboring values (j, b) which have been deleted due to i (line 19). In this case, (j, b) will be restored (line 21) and "flag" is activated in order to inform that i need to be rechecked for AC later by adding its neighbour variables j into queue Q AC (line 24).

When the search backtracks, the AC-closure of Bool(P ) can be simply rebuilt via the restoration of the justification system "killer" through trailing. Indeed, if killer(i, a) = nil, this means that (i, a) was consistent in the old Bool(P ). In this case, (i, a) will be set as an available value in D i . Conversely, if killer(i, a) = j or i, this means that (i, a) was removed because of constraint w ij or w i . In this case, (i, a) will be removed from D i .

A. Example

Consider the CFN P in Figure 2(a). It has four variables i, j, k and l, with domains D i = D k = D l = {a, b, c}, D j = {a, b}, and four cost functions w ik , w il , w jk , w jl . Values are represented as vertices. Numbers displayed besides values represent non-zero unary costs of values. An edge between two vertices indicates that the corresponding pair of values has a binary cost of 1. Zero costs are not represented. Suppose that P is the CFN obtained at some node of the tree search. The AC-closure of Bool(P ) for this node is represented in Figure 2(b). Forbidden values are shown as crossed-out and edges represent forbidden pairs. The dotted arrows represent the killer data-structure for removed values, pointing to the variable that offered no valid support. A removed value without any justification arrow means that the value is deleted because of its own positive unary cost. Now we will show how Bool(P ) is updated in two cases: a domain restriction (i = a) and a variable assignment (i = a).

In the case (i = a), DynVAC will propagate the domain reduction of i to neighboring variables k, l. We observe that (i, a) was also deleted in Bool(P ) of the parent node. It did not support any value. Thus, the removal of (i, a) does not lead to any support loss. The propagation procedure stops here. We obtain a new Bool(P ), which is identical to the old one in Figure 2(b). In this favorable case, DynVAC has almost nothing to do to construct Bool(P |i =a ).

Consider now the case of a variable assignment (i = a). Only the pair ((i, a), (l, c)) has positive cost and this binary cost will be projected to (l, c) : w l (c) = 1. Then cost functions w ik , w il are removed from P . The network of P |i=a (i,c) and constraint w ik , w il will be removed from Bool(P ) and value (i, a) will be set as consistent in Bool(P |i=a ) (Figure 2(d)). In the neighborhood of i, only value (k, c) is restorable because it was removed due to w ij but w ij has just been removed from Bool(P ). Thus, (k, c) is restored (Figure 2(e)). The restoration of (k, c) does not make any other value restorable. At the same time, in the neighborhood of i, only value (l, c) has an increased unary cost. (l, c) will be deleted in Bool(P |i=a ) because of its positive cost (Figure 2(f)). The domain of l becomes empty and VAC can project unary costs of 1 to w ∅ . We observe that the result of enforcing AC on the subproblem of Bool(P ) defined by variables j, k, l (for constraints w jl , w jk , w kl ) is preserved and that a variable wipeout is detected early.

V. EXPERIMENTS

In this section, we will compare the efficiency of VAC when being maintained during search in three different ways:

• Static VAC (VAC): Bool(P ) is always rebuilt from scratch whenever a new iteration of VAC or a branching operation is performed. • Normal Dynamic VAC (norDVAC): Bool(P ) is maintained incrementally inside each node of the search (betwwen VAC iterations) but it is rebuilt from scratch when the search makes a branching operation. • Full DynVAC (fulDVAC): Bool(P ) is incrementally maintained both inside each node of the search and when a branching operation is performed.

As described in [START_REF] Cooper | Soft arc consistency revisited[END_REF], we remind the reader that when VAC is enforced in practice, iterations are stopped when the increase of the lower bound w ∅ becomes less than a threshold ε. This is called VAC ε . When maintained during search, two different ε thresholds are used. A small value ε r is used at the root for maximum results. Then a larger value ε s is used during search.

Furthermore, to accelerate VAC enforcing, [START_REF] Cooper | Soft arc consistency revisited[END_REF] suggest to try to collect largest costs first by using relaxations of Bool(P ) that only forbids tuples with sufficiently large costs, above a threshold θ. This is denoted as Bool(P ) θ . VAC is enforced with a decreasing sequence of thresholds (θ 1 , θ 2 , ...θ k ) with θ k = ε.

In VAC and Normal DynVAC, θ is reinitialized to θ 1 when the search makes a branching operation (i.e, goes down in the search tree) or when the search backtracks. In Full DynVAC however, in order to incrementally maintain DynVAC during search between nodes, θ is incrementally updated when the search makes a branching operation and is restored by "trailling" when the search backtracks.

Our experiments use a set of benchmarks (in wcsp format) that are collected from different resources:

• maxcsp, planning, celar, tag08, warehouse, bep are extracted from the Cost Function Library (CFLib) • CPD are instances of computational protein design problems [START_REF] Traoré | A new framework for computational protein design through cost function network optimization[END_REF], [START_REF] Allouche | Computational protein design as an optimization problem[END_REF].

Following the result of previous DynVAC experimentations for preprocessing in [START_REF] Nguyen | Dynamic virtual arc consistency[END_REF] that showed that DynVAC does not improve VAC on problems with boolean domains, we excluded problems with only boolean variables. The resulting very wide set of benchmarks represents a total of more than 1,000 instances coming from various application areas.

In our experiments, we set ε r = 1, ε s = 1000 for problems with very large costs (such as tag08, warehouse, CPD, GeomSurf-7), and ε r = 1, ε s = 100 for problems with large cost such as ImageAlignment. For the remaining problems, we use ε = 0.0001, ε S = 0.1. The same thresholds are used in all algorithms. All experiments are executed on the same hardware using AMD Opteron(tm) 6176 processors.

Table I reports the mean run-time (in seconds) for solving these different categories of benchmarks by enforcing static VAC, normal DynVAC and full DynVAC. Each line corresponds to a category of benchmarks where the number of instances (#inst) and the mean values of problem size (n: number of variables, d: domain size, e: number of cost functions) are given. We also report the mean graph densities per category (dens). The graph density of an instance is defined as the ratio of its number of cost functions with the number of edges in a complete graph. The three following columns reprots results for our three algorithms. Each box here contains two numbers. The italic number in the bottom right corner represents the number of instances solved by the algorithm in less than one hour while the number in the top left corner represents the mean value of the run-time. This mean is computed only over problems that are solved in less than 1 hour by all three variants of VAC. The best results are in bold. Finally, the last two columns give the speedups obtained by full DynVAC compared respectively to normal DynVAC and VAC.

From these last two columns, we observe that full DynVAC outperforms normal DynVAC on all categories of benchmarks and is more efficient than VAC in most cases.

Compared to normal DynVAC, Full DynVAC shows very significant speed-ups on the categories GeomSur-7, Im-ageAlignment and warehouse (speed-ups of 8.7, 7.4 and 3.2 respectively). For the other categories (coloring, maxcsp, planning, matching, celar, tag08, ProteinFolding), the speedup of full DynVAC goes from a factor 1.79 to a factor 1.15. Finally, it has almost the same efficiency on two categories (CPD and bep).

To explain these differences, we have to remember what makes full DynVAC different from normal DynVAC. The difference between full DynVAC and nornal DynVAC comes from the way they update Bool(P ) after a branching operation. In full DynVAC, only the variables of Bool(P ) that are directly linked to the branching variable (its neighborhood) are modified and restorations are propagated to the other variables before arc consistency is rechecked on the modified variables. In normal DynVAC, the whole arc consistency process is redone from scratch on the reinitialized Bool(P ). It is therefore expected that the graph density of the instance solved will have a strong impact on efficiency. If the graph density is low, very few variables will appear in the neighborhood of the modidifed variable and full DynVAc should save a lot of work compared to normal Dyn VAC.

Another important factor for efficiency is the domain size. If we restore a few values incrementally in a domain that was initially large, the cost of repropagating AC can be much lower than if resetting the whole domain from scratch. If we restore a few values in a domain that was initially small, AC will not be significantly faster than if resetting the whole initial domain.

Overall, it is therefore expected that the greatest savings will be obtained by full DynVAC on problems with low graph densities and large domains. If we analyse the characteristics of the categories of problems on which full DynVAC behaves very well, we effectively observe that GeomSur-7 has a very low graph density (0,011 -lowest density of the set of benchmarks), ImageAlignement has a low density (0.123) and a great domain size (70), and warehouse has a medium density (0.237) but is characterized by a large domain size (78). Along the same line, by observing the categories on which full DynVAC is only slightly faster than normal DynVAC, we see that they are characterized by a high graph density (0.527 for CPD and 0.5 for bep).

This impact of density and domain size on the performance of full DynVAC seems to be confirmed on the other categories of problems. Coloring, for instance, has a very low density (0.112), and we would expect a very good performance of full DynVAC. However, the moderately improved performance of full DynVAC on this coloring category ('only' 1.4 times faster than normal DynVAC) can be explained by the very small mean domain size [START_REF] Dechter | And/or search spaces for graphical models[END_REF].

We now compare the efficiency of full DynVAC to the efficiency of static VAC. We observe that full DynVAC is better than static VAC on 7 of the 12 categories. The categories GeomSur-7, ImageAlignment and warehouse, where full Dyn-VAC was significantly better than normal DynVAC, remain very favorable to full DynVAC when compared to static VAC. This tends to show that the criteria of density and domain size remain true when comparing to static VAC. We also observe that category planning is another example where full DynVAC is significantly faster than static VAC (by a factor 2.11).

Overall, if we compare the efficiency of the two variants of DynVAC to static VAC we observe that when normal DynVAC is faster than static VAC then full DynVAC is even faster. This however happens for only two categories: planning and bep, whereas full DynVAC is faster on 7 categories.

In summary, incrementally maintaining DynVAC during search is in general very beneficial in comparison with restarting from scratch after each branching operation and graph density and domain size are the main criteria that have a visible impact on the performance of full DynVAC.

VI. CONCLUSION

Following [START_REF] Nguyen | Dynamic virtual arc consistency[END_REF] that introduced the Dynamic VAC algorithm combining the idea of dynamic arc consistency algorithms with the iterative VAC algorithm in order to efficiently maintain arc consistency in the CN Bool(P ) during VAC enforcing for preprocessing, we show that Dynamic VAC can be also be maintained during search.

In this situation, two approaches can be considered: either Dynamic VAC can be just maintained at each node of the search tree or the incrementality of Dynamic VAC can be exploited also to account for the small problem changes that occur following branching operations in the search tree.

By exploiting both incremental changes caused by branching operations as well as incremental changes of EPTs during sucessive iterations of VAC, the new fully incremental method outperforms both the direct application of dynamic VAC and the usual maintenance of static VAC on a variety of problems. This is especially true for problems having small graph densities and large domains.

There are still more opportunities to accelerate algorithms maintaining VAC during search. Indeed, VAC does not require to enforce AC on Bool(P ) but only to detect if the AC closure is empty or not. Therefore, it is sufficient to identify a single viable value in each domain to conclude. This simplified problem has been solved using so-called Lazy AC algorithms [START_REF] Schiex | Lazy arc consistency[END_REF] that could also be injected in VAC algorithms to increase their efficiency.

Algorithme 1 :

 1 Equivalence Preserving Transformation 1 Procedure Shift(i, j, a, α) // precondition: wi(a) + α ≥ 0 and wij(a, b) ≥ α for ∀b ∈ Dj

Fig. 1 .

 1 Fig. 1. All possible situations that can happen after a variable assignment

Corollary 2 .

 2 Each variable assignment (i = a) in P can generate both: a) the removal of values (j, b) in Bool(P |i=a ) such that there exists w ij in P and w j (b) > w j (b) = 0. b) the restoration of values (j, b) in Bool(P |i=a ) which were deleted in Bool(P ) by w ij and such that w j (b) = 0. Proof. a) From Property 1c), unary costs of values (j, b) that are neighbour with i in P may only increase or remain unchanged in P |i=a . Some may therefore go from a zero to a non-zero cost. In this case, the corresponding values are deleted in Bool(P |i=a ). From the dynamic AC point of view, this can be considered as a restriction, with the addition of a unary constraint on j (i.e., domain restriction). b) If (j, b) is a value removed in Bool(P ) because of w ij (killer(j, b)= i), this implies that w j (b) = 0 (otherwise, we would have killer(j, b)= j). According to Property 1c), the unary cost of (j, b) in P |i=a can remain unchanged, i.e.; w j (b) = 0, if w ij (a, b) = 0. Such a value with zero cost cannot be killed by itself in Bool(P |i=a ). Furthermore, i is no longer a reason to delete (j, b) because as Corollary 1a) states, (j, b) is arc consistent with i. Hence, (j, b) can become viable in Bool(P |i=a ).

Algorithme 2 : 2 D 3 UnaryProject(i); 4 foreach w ij do 5 foreach b ∈ D j do 6 if 7 remove b from D j ; 8 add j into Q AC ; 9 w

 223456789 algorithm updating Bool(P ) wrt a variable assignment 1 Procedure assign(i, a) i = D i = {a}; w j (b) = 0 and w j (b) + w ij (a, b) > 0 then j (b) ← w j (b) + w ij (a, b); 10 if w j (b) = 0 and killer(j, b) = i then 11 restore(j, b); 12 remove w ij and w ij ; 13 relaxation(RL); 14 AC-revise(Q AC ); 15 Procedure relaxation(RL) 16 while RL = ∅ do 17 i ← RL.pop(); flag ← false; 18 foreach w ij do 19 foreach b ∈ D j -D j s.t. killer(j, b) = i do 20 if ∃a ∈ restored[i] s.t. w ij (a, b) = 0 then 21 restore(j, b); 22 flag ← true; 23 restored[i] ← ∅; 24 if flag then Q AC ← Q AC ∪ {j | w ij ∈ W }; 25 Procedure restore(j, b) 26 add b into D j and restored[j]; 27 killer(j, b) = nil; 28 add j into RL;

Fig. 2 .

 2 Fig. 2. Updating Bool(P ) in the case of a variable assignment

TABLE I AVERAGE

 I SOLVING TIME PER CATEGORY OF BENCHMARKS WHEN MAINTAINING VARIANTS OF VAC IN SEARCH.

		# mean mean	mean mean	Maint		Maint		Maint		Speedup Speedup
	Categories	inst	n	d	e	dens	VAC		norDVAC	fulDVAC	/norDVAC	/VAC
	coloring	22	120	4	1203 0.112	16.70	17	26.35	17	18.64	17	1.41	0.90
	GeomSur7	300	505	7	2140 0.011	6.20	300	9.36	300	1.08	300	8.67	5.74
	maxcsp	340	31	10	129 0.213	58.76	340	78.75	340	58.99	340	1.34	1.00
	planning	76	240	14 14746 0.307	20.22	75	11.69	75	9.56	76	1.22	2.11
	Matching	4	19	19	166 0.441	104.03	4	367.40	3	281.99	3	1.30	0.37
	celar	46	137	36	1346 0.507	364.27	38	337.31	37	290.78	38	1.16	1.25
	tag08	82	185	62	8003 0.179	14.09	81	31.42	80	27.39	81	1.15	0.51
	ImageAlignment	10	191	70	1819 0.123	18.58	10	23.74	10	3.23	10	7.36	5.76
	warehouse	57	216	78 18739 0.237	164.26	54	289.30	51	90.49	55	3.20	1.82
	CPD	35	50	148	1561 0.527	39.30	24	46.79	24	46.72	24	1.00	0.84
	bep	4	18	168	160 0.500	3.20	3	2.62	3	2.56	3	1.02	1.25
	ProteinFolding	31	334	221	1583 0.384	27.68	30	48.58	30	27.12	30	1.79	1.02

See https://mulcyber.toulouse.inra.fr/projects/costfunctionlib.

https://mulcyber.toulouse.inra.fr/scm/viewvc.php/trunk/?root=costfunctionlib

http://hci.iwr.uni-heidelberg.de/opengm2


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

Amal El

Fallah Seghrouchni

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

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

Improving the Contextual Selection of BDI Plans by Incorporating Situated Experiments

Keywords: Ambient agent, BDI, plan selection, contextual guidance, past-experiences

This paper is dedicated to intentional BDI agents evolving in ambient environment. The planning management framework we propose, looks for efficient guidance to improve the satisfaction of the agent's intentions with respect to the possible concurrent plans and the current context of the agent. Adopting the idea that "location" and "time" are key stones information in the activity of the agent, we show how to enforce guidance by ordering the different possible plans. As a major contribution, we demonstrate two original utility functions that are designed from the past-experiences of the action executions, and that can be combined accordingly to the current balance policy of the agent.

Introduction

Designing and developing applications for Ambient Intelligence (AmI) systems involves different challenges in several computing areas as well as intelligent systems research, sensor networks, mobile technologies and interaction within user centered design. Multi-Agent Systems (MAS) are a powerful approach to design AmI systems to function potentially within dynamic environments. They offer interesting frameworks and support for autonomy, proactivity, societal cooperation and context-awareness needed for such systems.

To deal with 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) model can flexibly handle the entire modeling and developing of rational agents in AmI systems, based on well-structured and goal-driven aspects, e.g. [START_REF] Chaouche | A Higherorder Agent Model with Contextual Management for Ambient Systems[END_REF][START_REF] Calvaresi | A goaloriented requirements engineering approach for the ambient assisted living domain[END_REF].

However, some AmI applications are really complex [START_REF] Preuveneers | A survey of software engineering best practices for the development of smart applications in ambient intelligence[END_REF]. The environment can be open so that the agents may enter and leave. Moreover, agents can move between locations. In fact, the agents must adapt their decisions and behavior to cope with dynamic and unexpected changes of the context. It is necessary to increase the agent reactiveness and consistency, contributing to better flexibility and resilience properties.

In [START_REF] Chaouche | A Higherorder Agent Model with Contextual Management for Ambient Systems[END_REF], new possibilities of modeling AmI systems are presented, not only by referring to MAS and BDI agents, but also by embedding a formal and automated planning management mechanism. Plans are consistent w.r.t. the intentions of the agent and can be achieved concurrently. Based on an underlying model of actions and processes, a contextual planning system (CPS) was demonstrated, that can be exploited to maximize the satisfaction of intentions, taking the spatial information into account.

However, we argue that the former mechanism, which looks for guidance, can be improved by a learning from the past-experiences of actions. For instance, taking into account the failure of actions can be used to evaluate a pertinence of some plan wherein this action occurs, e.g. [START_REF] Airiau | Incorporating learning in BDI agents[END_REF]. Closer to our aim, the work of [START_REF] Nunes | Softgoal-based plan selection in model-driven bdi agents[END_REF] evaluates the contribution of each plan in terms of utility and preference, seen as parameters for the optimization.

The utility functions we introduce evaluate plans on safety and speed notions. Both can be based on concrete information issued from the executions of actions. In particular, safety criteria is based on the outcomes of the past-experiences whereas speed criteria is learned from the durations of these experiences. We need to define a reinforcement technique adapted to AmI agents and the unexpected changes of their contexts. In particular, our approach to predict the outcome and the duration of some action in a plan does not rely on recurrent learning principles but rather on a systematic analysis of some pertinent situated pastexperiences.

In this paper, we present a method to organize the filtering of past-experiences according to spatio-temporal strategies. In fact, location is a very fundamental context information to evaluate an action but time is another important data. For example, it is not really interesting to take the highway, at the time it is crowded. This can be captured by a study of the duration of previous transportations via the highway, made at some time during the business day.

The remaining of the paper is organized as follows: Section 2 describes the functional architecture of our planning process, together with its guidance mechanism based on the capability of an agent to reason on the future actions, on the basis of its knowledge about past experiences. Section 3 shows how the possible plans to satisfy the intentions of the agent can be expressed compactly with the AgLOTOS specification language. From such an expression, the derived CPS structure is built automatically to process the agent guidance. Section 4 details the acquisition of past-experiences and their exploitation. In Section 5, the spatio-temporal guidance mechanism is presented, based on the CPS information enriched by the past-experiences of actions. Section 6 presents related work, then Section 7 concludes our paper. The overall agent architecture, we deal with, is standardly based on several processes. Triggered by some events expressing the context changes, the mental process is assumed to be highly deductive and rational, based on BDI structures (Beliefs, Desires and Intentions). Figure 1 brings out a functional view of our planning process, in charge to offer some plan to execute (σ) from the current set of intentions (I). It is composed of two modules:

-The Plan Factory builds the so-called agent plan which globally corresponds to the current set of intentions. The LibP library is used to exploit the different alternative of plans that must be specified for each intention. With respect to the current spatial context of the agent, a CPS is built, made of the different allowed interleaving of the actions in plans. By its traces, the CPS represents all the possible plans that can be realized. -The Guidance module is able to enrich the CPS information taking profit from the past-experiences of actions, that are stored in the so-called Learned Contextual Experiences (LCE) module. This results in a structure called CPS with learning (CPS-L for short), which can be used to searching the optimal trace w.r.t. the spatio-temporal context of the agent.

Our approach to specify the agent behavior is strongly related to the fact that the mental process can proactively decide to revise its set of intentions, at real time. Let us illustrate two nominal cases [START_REF] Chaouche | A Higherorder Agent Model with Contextual Management for Ambient Systems[END_REF]:

the agent can decide to investigate the first action of one of the best possible plans offered by the planning process, but can decide to revise some of the intentions, in case there is no plan to select, in respect to the current context. -face to unexpected changes of context, the agent can update some of its intentions. This causes the revising of a part of the agent plan automatically.

Planning P P 0 P 1 P j P 0,0 P 0,1 P 0,k E 0,0

Proc. The plan structure is formally captured by using a formal description language, namely AgLOTOS. It introduces modularity and concurrency aspects to compose and schedule different sub-plans, viewed as processes [START_REF] Chaouche | A Higherorder Agent Model with Contextual Management for Ambient Systems[END_REF]. Let us now briefly recall the AgLOTOS-based specifications for plans.

I = {i w 0 , i w 1 , ..., i w j } ⊙ E 0,1 E 0,k
Agent plan level. The set of intention plans can be globally handled by using the concurrent ||| or sequential operators 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 (P ), such that each one can be executed to achieve the corresponding intention. This is captured in AgLOTOS by using the composition operator ♦.

In particular, an intention is satisfied if and only if at least one of the associated elementary plans is successfully executed. Formally, let P be the set of names qualifying the possible elementary plans with P ∈ P. 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 related 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, ... Let Act = O ∪{τ }, be the set of actions, where τ is the internal action. In the context of this paper, the internal actions mainly correspond to the information related to the termination of a plan. The AgLOTOS language specifies pairs for each elementary plan composed of an identifier and an AgLOTOS expression to specify its behavior. The syntax of an elementary plan P is inductively defined as follows:

P ::= E E ::= exit | a; E (a ∈ O)
In this syntax, P ::= E represents an elementary plan identified by P , such that its behavior expression is E. The expression a; E denotes an action a prefixing E, and the elementary expression exit expresses the successful termination of some plan. For sake of concision, the other operators defined in AgLOTOS are not detailed in this paper. Please refer to [START_REF] Chaouche | A Higherorder Agent Model with Contextual Management for Ambient Systems[END_REF] for more details, however, let us note that elementary plans do not generate new intentions, as it is the case for some other BDI approaches.

Building of Agent Plan from Intentions. In order to account for any BDI state of the agent, we propose that the agent can label the different elements of the set I of intentions3 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 P g , P e , P m respectively correspond to their intention plans. The constructed agent plan could be viewed as: P ::= ( P g ||| P m ) P e . In terms of elementary plans, by considering that P g ::= P g , P m ::= P m and P e ::= P e1 ♦P e2 , then the agent plan is refined in P ::= (P g |||P m )

(P e1 ♦P e2 ).

Contextual Planning System (CPS)

With respect to some agent plan P , we introduce a notion of configuration, denoted [P ], corresponding to the planning state of the agent. This helps specifying the evolution of the agent plan. Some examples are given further. Let usl now define the contextual planning state of the agent, taking into account the location of the agent and the outcomes of different intention plans defined for this agent.

Definition 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 that 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 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.

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 ). The intention plan P m is used to satisfy the intention meeting(Alice, 1 ) and has only one elementary plan P m ::= move( 1 ); meet(Alice); exit m . The second intention plan P m corresponds to the intention getting copies( 2) and also has one elementary plan P g ::= getc( 2 ); conf irm; exit g .

The initial agent plan configuration is directly given from the above here plan description, [P B ] = (move( 1 ); meet(Alice); exit m )|||getc( 2 ); conf irm; exit g . One of the possible derivations from this configuration consists in performing the getc action. So, the agent plan configuration of Bob changes to move( 1 ); meet(Alice); exit m ||| conf irm; exit g .

The Contextual Planning System of Bob, denoted CP S B , is illustrated in Figure 3. It is built from the initial CPS state, s 0 = ([P B ], 2 , ∅), taking into account the current location 2 of Bob. It is worth noting that the CPS could grow exponentially depending on the current intentions of the agent, hence on the

τ m ℓ 1 ℓ 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 ℓ 1 ℓ 2 meet meet meet τ g τ g τ g τ m τ m τ m
Fig. 3. The CP SB corresponding to the plan PB related actions in plans. Nevertheless, we consider that the number of intentions to be dealt with dynamically is reasonably small, moreover the CPS structure is only partial since actions are only allowed w.r.t. the current spatio-temporal context of the agent4 .

Guidance for Intention Satisfaction

In a CPS, any transition 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 information attached to the source state. Let pre(a) be the precondition of any action a, e.g. pre(a( )) = = L(s). For instance in Figure 3, the dashed edges represent the disabled transitions from the states s ∈ {s 2 , s 5 , s 8 }, because pre(getc( 2 )) = 2 = L(s).

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 VIII 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 6 represents the 10 maximum traces of CP S B . In this unfolded version of Figure 3, the trace carried out by s 0 → s 2 → s 5 → s 9 , is not represented because it is not a maximum trace.

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 action execution 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.

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 4 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.

Data Relevance Strategies

The strategy information specified by the agent is given by the following definition and described below. Definition 4. The queues of LCE are parameterized by the agent strategy S = K, f orget, M, C 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 subqueue 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 1, the forgetting function f orget(index) = 1 index is used, yielding much more relevance for any experience in the queue than another one of greater index. 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 (|tmod 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 1, 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 5 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).

Computing the Expected Performance and Expected Duration for an action

For each non empty queue LCE a ( ), the expected performance EP a ( ) ∈ [-1, 1] represents the performance of a in some location , based on M experiences filtered from LCE a ( ) s.t.: 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.

EP a ( ) = f ilter M,C (t) exp exp.outcome * f orget(index(exp)) f ilter M,C (t) exp f orget(index(exp)) (1)
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)) (2)
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.

5 Spatio-Temporal Guidance from Past-Experiences

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 perform in . Definition 5. 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. 3. It distinguishes the maximum traces (with possibly common prefix), and 2 of them explicitly exhibit the labels attached to the transitions. For instance, the values EP getc = 0.19 and ED getc = 3.16 are attached to the transition (s 0 , getc, s 1 ). These values are computed from the experiments selected in LCE a ( ), specified in Table 1.

s 0 meet meet meet meet τ g τ g τ g τ g τ g τ g τ g τ g τ m τ m τ g τ m τ m τ m τ m τ m τ m τ m
From any CPS-L, it is straightforward to extend the expected quality to every maximum trace σ ∈ Σ M AX , in order to compare them, as follows:

QP (σ) = σ tr∈T r EP(tr) |σ| (3)
QD(σ) = σ tr∈T r ED(tr) (4)
In order to compare the traces in-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 ), hence, the normalized quality of duration, is featured by the N QD(σ) expression, for any represented σ.

N QD(σ) = 1 - QD(σ) -QD min QD max -QD min * 2 (5)

Optimal Trace of the CPS-L

Algorithm 1 Spatio-Temporal Guidance process Order ΣMAX from the CPS-L; 8:

Offer σopt among the ones of ΣMAX ; 9: end if

The algorithm 1 synthetically highlights the planning process approach for selecting an (optimal) maximum trace, σ opt . As this process acts as a service provider, it must also notify the case where there is no possible maximum trace. Actually, this is useful to let the mental process revise its planning process request in accordance. To select an optimal trace, the set Σ M AX of maximum traces is ordered regarding the assigned values from QP and N QD, considered separately.

This allows the planning process to select an optimal sequence, either with the lowest duration or the maximum performance (i.e. with the minimum risk of failure). To make a compromise, we also assume that the mental process can specify a preference balance denoted B, to the planning process. It 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 the maximum traces (σ ∈ Σ M AX ). Of course, the optimal trace σ opt corresponds to the maximum trace having the best global quality value. 6, knowing that over all the maximum traces, we obtain QD min = 7.58 and QD max = 10.23. Assuming the preference balance B1 s.t. B1 P = 0.30 and B1 D = 0.70, i t appears that Q B1 (σ 2 ) is greater than Q B1 (σ 1 ), so 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 B (σ) = B P * QP (σ) + B D * N QD(σ) (6)
(Q B2 (σ 1 ) > Q B2 (σ 0 )).
A last remark is that the exploitation of the CPS-L allows efficient exploitation/exploration guidance by focusing on some transition labels. In particular, the selection of a trace having a 0 labeled transition corresponds to exploration of untested action, whereas a trace having a -1 labeled transition should fail, but that could be selected in a degraded mode, when there is no better choice. Exploration can be investigated since our approach to select good traces from the past-experiences is only heuristics. In contrast, a conservative agent (rejecting exploration) should abstract the above exploration cases.

Discussion and Related Works

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 brainstormers -a 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-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 soft-goal 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 traces 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 trace implies the selection of some alternative for each intention plan. The queues recording the past-experiences 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, location, etc.) which is valuable for dynamic environment and contexts.

Conclusion

The proposed CPS-L planning tree structure reveals various interests in the agent design since it demonstrates a formal representation of the concurrency of the plans to achieve the intentions of the agent. In fact, each maximum trace in this structure represents a possible plan to execute at real time, in respect to any current context of the agent. As a major contribution of this paper, guidance is reinforced by exploiting the past-experiences of the execution of situated actions. Face to the change of contexts, the forgetting strategy is of a great help since it allows to privilege the recent past experiences. We provide two utility functions that is used to label the CPS-L, respectively based on the outcomes (the success or failure information of the executions) and time concepts (the starts and durations of the executions). Exploration is also considered in case there is no past-experiment for some situated action. Anyway, these CPS-L labels allow us by extension to compare the possible plans. A normalization approach is demonstrated in order to combine both functions, so that optimizations is balanced in-between speed and safety plans.

The CPS-L of the frame scenario, is built out from our prototype tool associated with an automatic generation of the past-experiences. It yields from the study that the current time of the agent can effectively be used as a reference to filter a number of experiences, even in the case the past-experiences were performed under a time periodical strategy. With respect to every situated action, the used filtering function strongly improves the chances to only take relevant past-experiences into account, in respect to the current time of the agent, however, this reduces the number of experiences used to estimate the duration of the action. In fact, different parameters could be used to adapt the influences of the past-experiences, therefore, we are now investigating the different strategies to better guide the agent.

Fig. 1 .

 1 Fig. 1. Extended BDI model with contextual planning architecture

Fig. 4 .Definition 3 .

 43 Fig. 4. Learned Contextual Experiences (LCE) of an action a

1 day - 2 day - 3 Fig. 5 .

 1235 Fig. 5. The example of the LCEgetc( 2)

2 Fig. 6 .Figure 6

 266 Fig. 6. Maximum traces and CP S-LB for the plan PB

Table 1 .

 1 LCE of the action getc in the location 2

	index 1	5	6	10	11	12		18	k
	LCEgetc( 2)	...
	f ilter 6,daily (10)
	Experiences	outcome mod daily (start) duration	index	f orget(index)
	A	-1	8.29		-		5	0.20
	B	1	9.50	3.00		6	0.16
	C	1	9.05	2.10		10	0.10
	D	1	10.78	3.40		11	0.09
	E	-1	10.05		-		12	0.08
	F	1	11.05	5.12		18	0.05

A B ... C D E ... F ...

  t. from each transition tr = (s, a, s) ∈ Σ M AX , ED(tr) = ED a (L(s)).

				getc
				s 1
		s 3					s 4
	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 2 .

 2 Computed quality values of σ1 and σ2 maximum traces

	ΣMAX	QP	QD	N QD	QB1	QB2
	σ1	0.42	9.74	-0.63	-0.31	0.10
	σ2	-0.04	8.54	0.27	0.17	0.05

Table 2

 2 highlights the global qualities of two maximum traces σ 1 and σ 2 of Figure

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 to the set of intentions.

Intuitively speaking, the achievements of intentions are more or less costly depending on the plans they involve.


Roudy Dagher
email: roudy.dagher@inria.fr

Nathalie Mitton
email: nathalie.mitton@inria.fr.

ONLINE PATH LOSS ESTIMATION FOR LOCALIZATION USING LARGE APERTURE ARRAY SIGNAL PROCESSING

In this paper, a novel array-based method to estimate the path loss exponent (PLE) is developed. The method is designed as a part of an automatic calibration step, prior to localization of a source transmitting in the near-far field of the array. The method only requires the knowledge of the ranges between the array elements. By making the antenna elements transmit in turn, the array response model in the near-far field is exploited to estimate the current environment PLE. Simulation results show that this method can achieve good performance with one transmission round. The performance of the PLE estimation is investigated in the context of source localization with a sensitivity analysis to the PLE estimation.

INTRODUCTION

In various signal processing and communications applications, locating transmitting sources enables a myriad locationbased services at both application and network level [START_REF] Sun | Signal processing techniques in network-aided positioning: a survey of state-of-the-art positioning designs[END_REF][START_REF] Gezici | A survey on wireless position estimation[END_REF][START_REF] Liu | Location, localization, and localizability[END_REF]. In the most common case, position related measurements are This work is partially supported by a grant from CPER Nord-Pas-de-Calais / FEDER Campus Intelligence Ambiante, the IPL SmartCities@Inria and the FP7 SMART CITIES VITAL. first extracted from the received signals, and then used in a second step for estimating the position of the source node by means of a specific algorithm: fingerprinting, geometric or statistical methods [START_REF] Gezici | A survey on wireless position estimation[END_REF]. The first step is also called "Association" phase, and the second one "Metric-Fusion" phase [START_REF] Manikas | Source localization using sparse large aperture arrays[END_REF].

Recently, a novel large aperture array (LAA) processing technique was proposed in [START_REF] Manikas | Source localization using sparse large aperture arrays[END_REF][START_REF] Manikas | Positioning in wireless sensor networks using array processing[END_REF] to provide a range-based source localization solution. The LAA procedure is carried in two steps as depicted in Fig. 1. In the association phase, a set

X ∈ C N ×L 'Array Signals' Association Phase K ∈ R N -1×1 'Metrics' Metric-Fusion Phase rm ∈ R 3×1 r ∈ R 3×N a ∈ R 'Estimated Position'
Fig. 1. The LAA localization procedure (P LE a) from [START_REF] Manikas | Source localization using sparse large aperture arrays[END_REF].

of metrics is estimated from the impinging signal on the array elements. Those metrics associate the range of the source to the array elements with the signal eigenvalues under both narrow and wide band assumptions. Those metrics are then fed to the metric-fusion process that estimates the source location by using the knowledge of the array geometry r and the path loss exponent (PLE) denoted as a. In the association phase, the source is assumed to lie in the near-far field of the array, and thus undergoes spherical wave propagation. Under such assumption, the array manifold vector depends on range and direction of the source, in contrast with the far-field region where the manifold vector only depends on the direction of arrival [START_REF] Krim | Two decades of array signal processing research: the parametric approach[END_REF][START_REF] Willerton | Array shape calibration using a single multi-carrier pilot[END_REF]. This particularity also led to the development of novel array pilot and self calibration techniques that exploit such form of the array manifold vector [START_REF] Willerton | Array shape calibration using a single multi-carrier pilot[END_REF][START_REF] Akindoyin | Localization and array shape estimation using software defined radio array test bed[END_REF] where the PLE is assumed to be known.

In this paper, we relax the assumption of the LAA localization on the prior knowledge of the PLE. We propose an array-based technique to automatically estimate the PLE by the array itself. This is achieved by making its elements act as pilot sources in turn, whilst the rest of the array receiving elements form a sub-array. Since the array geometry is known, the PLE can be estimated by inverting the localization procedure in Fig. 1 by estimating the PLE when the source posi-tion is known. The advantage of this approach is to use the same formalism for calibration and LAA localization, in contrast with PLE estimation in the framework of received signal strength localization [START_REF] Bel | Realtime path loss and node selection for cooperative localization in wireless sensor networks[END_REF][START_REF] Mao | Online calibration of path loss exponent in wireless sensor networks[END_REF].

PROBLEM FORMULATION

Consider a fully calibrated large aperture sparse array of N omnidirectional antennas (sensors, transceivers...etc), with a common reference point (zero-phase reference point taken to be the origin of the coordinate system). The array antenna locations are known and defined by the matrix r ∈ R 3×N with respect to the system origin. That is

r = r 1 , r 2 , . . . , r N = r x , r y , r z T (1)
where r i ∈ R 3×1 for i = 1 . . . N is the location of i th antenna in the array and r x , r y , r z ∈ R N ×1 denote the x, y and z coordinates of the N antennas. The array aperture is therefore given by D = max ∀i,j

r i -r j (2)
Assume the array operates in the presence of a single source node located at an unknown position1 with respect to the array reference point

r m = [x, y, z] T = ρ • u(θ, φ). (3)
The vector u(θ, φ) = [cos θ cos φ, sin θ cos φ, sin φ] T denotes the unity norm vector pointing in the direction of the source, and ρ the source distance to the origin. The source transmits an unknown narrowband message signal m(t) with a carrier frequency F c . The message can also be represented as a complex signal, defined as the complex envelope (baseband signal). The wavenumber, also pointing in the direction of the source is then given by

k(θ, φ) = 2πF c c • u(θ, φ) (4)
where c is the speed of light. It is clear from ( 3) and ( 4) that k(θ, φ) is collinear to the source location vector

r m = ρc 2πF c • k(θ, φ) (5)
The source is assumed to lie in the near-far field of the array, which is given by

ρ < 2D 2 F c c . (6)
In the case of a single path (LOS condition2 ), the signal x(t) ∈ C N ×1 received by the array (downconverted to baseband) can be modeled as

x(t) = q Sm(t) + n(t), (7)
R nn = σ 2 n I N ∈ R N ×N . ( 8
)
For a signal arriving from position (θ, φ, ρ), the modeling of the array manifold vector in the array's near-far region can be expressed as follows.

S = (ρ • 1 N ρ) a exp(-j 2πF c c • (ρ • 1 N -ρ)) (9)
where the parameter ρ denotes the unknown vector of ranges from the source to each of the array elements

ρ = [ρ 1 , ρ 2 , . . . , ρ N ] T ∈ R N ×1 . ( 10
)
Consider an observation of L data snapshots received by the N -elements array in the presence of a single source located at position r m . The signals received over this interval can be expressed as a matrix in accordance with the model in ( 7)

X = [x(t 1 ), x(t 2 ), . . . , x(t L )] ∈ C N ×L (11)
with the second order statistics, the covariance matrix

R xx = E x(t)x(t) H ≈ R = 1 L XX H . (12)
It is proved in [START_REF] Manikas | Source localization using sparse large aperture arrays[END_REF] that the signal eigenvalue λ can be estimated from the channel noise power and the principal eigenvalue γ = max(eig R) as

λ = γ -σ2 n , (13)
where the noise power in the channel σ2 n , is estimated by the average of the N -1 smallest eigenvalues of the matrix R. Now consider that the i th sensor of the array is the array reference point, that is all measurements X are taken with respect to this new reference point. The corresponding model becomes :

• Manifold vector S i with array geometry r i = r -r i 1 T N and source position (θ i , φ i , ρ i ) relative to this new reference point.

• Observation X i with the sample covariance matrix R i and eigenvalue λ i . Without any loss of generality, assume that the primary reference point is placed at the first sensor r 1 . By changing the reference point to be the i th sensor, for all array elements in turn, it is proved in [START_REF] Manikas | Source localization using sparse large aperture arrays[END_REF] that the following metrics can be constructed to relate the ratio of ranges between the source and the array elements:

K =      λ2 λ1 λ3 λ1 . . . λ N λ1      1 2a =      ρ2 ρ1 ρ3 ρ1 . . . ρ N ρ1      . ( 14
)

ARRAY ONLINE PATH-LOSS ESTIMATION

The PLE estimation method is presented under narrowband assumption for both single pilot calibration and array self calibration. The same methods remain valid under wideband assumption by using the corresponding association metrics in [START_REF] Manikas | Source localization using sparse large aperture arrays[END_REF].

Single Pilot PLE Estimation

Consider a single pilot source, with known ranges to the array elements ρ, that is transmitting in the near-far field of the array. Under narrowband assumption, in accordance with ( 14), the following metrics can be constructed

K = (λ (1 N • λ 1 )) 1 2a = ρ (1 N • ρ 1 ) (15)
where

λ = λ 1 , λ 2 , . . . , λ N T . ( 16
)
Therefore the path loss exponent can be estimated as

a = 1 2 • log(λ (1 N • λ 1 )) log(ρ (1 N • ρ 1 )) . ( 17
)
This equation is the key for online path loss estimation using the antenna array itself, by assuming that its elements operate as transceivers.

Array self PLE Estimation

In order to achieve online path loss estimation, all N array elements transmit in turn to the other N -1 elements operating as a receivers thus forming a sub-array. One can build the following matrix of eigenvalues Λ ∈ R (N -1)×(N -1) as,

Λ = λ 2 λ 3 . . . λ N             λ 12 λ 13 . . . λ 1N λ 32 λ 23 λ 2N λ 42 λ 43 λ 3N . . . . . . . . . λ N 2 λ N 3 . . . λ (N -1)N (18)
where λ j ∈ R (N -1)×1 is the vector of eigenvalues λ ij obtained when the transmitting element is r j , and the reference point is rotated on elements r i (i = 1 . . . N, i = j). By introducing the matrix K ∈ R (N -1)×(N -1) such that

K = Λ 1 N -1 • δ T 1 • Λ 1 2a (19)
where δ i ∈ R (N -1)×1 denotes a zero vector having its i th element equal to 1. By taking the first antenna element as the primary reference point, in accordance with (14), the matrix K corresponds to

K = K 2 K 3 K 4 . . . K N               1 1 1 . . . 1 ρ23 ρ21 ρ32 ρ31 ρ42 ρ41 . . . ρ N 2 ρ N 1 ρ24 ρ21 ρ34 ρ31 ρ43 ρ41 ρ N 3 ρ N 1 . . . . . . . . . ρ 2N ρ21 ρ 3N ρ31 ρ 4N ρ41 . . . ρ N (N -1) ρ N 1 , (20)
where ρ ij = r j -r i . Let us introduce the distance matrix ∈ R (N -1)×(N -1) defined as

= ρ 2 , ρ 3 , . . . , ρ N , (21)
where ρ i ∈ R (N -1)×1 is defined for i = 2 . . . N as

ρ i = ρ i1 , ρ i2 , . . . , ρ i(i-1) , ρ i(i+1) , . . . , ρ iN T . ( 22
)
Under the above notation, the vector ρ i now corresponds to the range of pilot antenna r i to the rest of the array elements. Equation ( 20) becomes

K = 1 N -1 • δ T 1 • (23)
Finally, the path loss exponent can be estimated as

a = 1 2 • log Λ 1 N -1 • δ T 1 • Λ log 1 N -1 • δ T 1 • , ( 24
)
where • is the matrix spectral norm i.e its maximum singular value. Based on the above discussion, the proposed path loss estimation algorithm can be summarized as follows:

STEP-1 Take the 1st element r 1 as the primary array reference point, and make the remaining N -1 elements transmit in turn. STEP-2 When the j th element transmits, the other N -1 remaining elements form a receiving sub-array, and the array reference point is rotated from r 1 to be at each element of the subarray. STEP-3 When the reference point is at a given array element, the signal eigenvalue is extracted from the received covariance matrix in accordance to (13). By repeating this step, construct the matrix Λ in (18). STEP-4 Construct the matrix from the known array inter-element spacing using (21) STEP-5 Estimate the path-loss exponent a using (24). Note that the above process can also be repeated several rounds and the estimation results can be averaged to refine the PLE estimation. For an extra degree of freedom, the process can also be repeated by changing the primary reference point from r 1 to other antenna elements in turn.

NUMERICAL SIMULATION RESULTS

In this section, the performance of the proposed PLE estimation approach is evaluated versus the SN R and the number of snapshots L. In addition, the LAA localization sensitivity to PLE inaccuracies is evaluated and its performance with PLE being estimated by the proposal. For consistency with reference LAA source localization, we consider a planar array of N = 4 elements as follows:

We suppose that the wireless channel has a fading, denoted by the vector q, with its magnitude modeled by log-normal distribution with mean 0 dB and standard deviation 8 dB and a phase modeled by a uniform distribution over 0 -2π radians. For transmission, the source baseband message m(t) is modeled by complex circular normal distribution of zero mean and unity power.

Performance of Path Loss Estimation

In practice, the observation interval is limited to the number of snapshots L, and the signal covariance matrix is approximated by the sample covariance matrix (in ( 12)). Thus the estimated signal eigenvalues will cause errors in the estimation of the matrix Λ, the latter having its elements affected by the noise power (in (13)). Consequently, we investigate the RMS of the PLE estimation over 200 realizations under increasing SN R × L. The PLE true value is set to a = 2. Fig. 2 shows that estimation quality is good, and it increases with the SN R and the number of snapshots L. Another interesting view of the estimator performance is shown in In Fig 3,

where the distribution of the estimated values is plotted under different SN R and L values. The results show that low SN R leads to higher dispersion around the average value, and vice versa. Finally, the number of snapshots has limited effect on the estimation dispersion, and rather affects the average value. This suggests that, under low SN R, it is more efficient to perform several estimations and average them, whereas under good SN R conditions the PLE estimation can be performed with a single round with a high number of snapshots.

Sensitivity of LAA Localization

Since the targeted application is LAA localization [START_REF] Manikas | Source localization using sparse large aperture arrays[END_REF][START_REF] Manikas | Positioning in wireless sensor networks using array processing[END_REF], it is key to study the quality of the PLE estimation by analyzing its overhead on the positioning error. We use the metric-fusion in the section III of [START_REF] Manikas | Source localization using sparse large aperture arrays[END_REF]. The latter estimates the source position by solving a set of linear equations Hr m = b. By setting the PLE to a = 3, 200 independent simulations are performed for different SN R and L values. Fig. 4 shows the reference LAA localization is sensitive to the PLE parameter. Clearly, inaccuracies in the PLE introduce a bias in the source location estimation. Results in Fig. 5 show that when using the proposed PLE estimation procedure as self calibration step prior to localization, the localization performance is practicality the same as with the true PLE.

CONCLUSION

In this paper, an array based method is proposed for estimating the path loss exponent of the array environment. The method can be used in a calibration phase prior to source localization and can be automatically performed by the system itself at any time. Simulation results illustrate the performance of the proposal and its adequacy with the targeted localization process. Future work will concern full array self calibration where the PLE and the array shape are estimated jointly, using a prediction-correction loop that is trained by the measured signals.

Fig. 2 .

 2 Fig. 2. PLE estimation performance versus SN R over 200 realizations (P LE = 2).

Fig. 3 .

 3 Fig. 3. PLE estimation performance distribution over 200 realizations (P LE = 2).

Fig. 4 .

 4 Fig. 4. LAA localization sensitivity over 200 realizations (P LE = 3, L = 500 snapshots).

Fig. 5 .

 5 Fig. 5. LAA localization sensitivity and proposal performance over 200 realizations (P LE = 3, L = 500 snapshots).

The azimuth angle θ is measured anticlockwise with respect to the positive x-axis, and the elevation angle φ is measured anticlockwise from the x-y plane.

[START_REF] Gezici | A survey on wireless position estimation[END_REF] In presence of multipath, the signal LOS component can be extracted from the received signal by prepossessing the signal prior to calibration[START_REF] Venieris | Preprocessing algorithm for source localisation in a multipath environment[END_REF].where q ∈ C N ×1 models the unknown channel's slow fading effect. The vector S S(θ, φ, ρ, r, F c ) represents the array manifold vector (array response/steering vector). The vector n(t) ∈ C N ×1 denotes the baseband additive white Gaussian noise of power σ 2 and covariance matrix (isotropic noise)