Jeremy E Cohen

Nicolas Gillis

NONNEGATIVE LOW-RANK SPARSE COMPONENT ANALYSIS

Keywords: dictionary learning, nonnegative matrix factorization, sparsity, identifiability, subspace clustering

In this paper we consider a variant of the dictionary learning problem where the dictionary has full rank, the coefficients have a fixed sparsity level, and both the coefficients and the dictionary are nonnegative. It is equivalent to k-sparse nonnegative matrix factorization (K-NMF). This model is encountered in source separation where nonnegative linear combinations of a few components generate the data points (samples), such as in hyperspectral images. We first discuss the impact of nonnegativity on the identifiability of low-rank sparse component analysis (LRSCA), building upon recent advances. Then, as a main contribution, we propose two algorithms to train K-NMF: one based on alternating optimization and exact sparse coding, the other based on a nonnegative variant of K-subspace. We show on noiseless simulated data that our methods outperform by a large margin the state of the art. Finally, we apply our methods for the spectral unmixing of a hyperspectral image.

INTRODUCTION

Sparse component analysis (SCA) is a dictionary learning model that leverages sparsity to solve an otherwise ill-posed problem. Formally, SCA is the following problem: Definition 1 (SCA). Given a matrix M ∈ R d×n and an integer r, find D ∈ R d×r and B ∈ R r×n where the columns of B are at least k-sparse with k < r such that M = DB.

SCA has been central in signal processing over the last decade, often under the name dictionary learning. In spite of the large use of this model for various applications such as image denoising, inpainting or classification [START_REF] Tosic | Dictionary learning[END_REF], few conditions are available that guarantee uniqueness of matrices D and B satisfying Def. 1 in a deterministic scenario. There are however many results in probabilistic settings where the columns of B are drawn from specific distributions; see [START_REF] Gribonval | Sparse and spurious: dictionary learning with noise and outliers[END_REF] and the references therein. Recently, focussing on the low-rank case (rank(D) = r, r ≤ d), a strong identifiability result was obtained: Theorem 1 ( [START_REF] Cohen | Identifiability of lowrank sparse component analysis[END_REF]). An SCA decomposition M = DB with rank(D) = r is essentially unique (that is, up to permutation and scaling of the columns of D and rows of B) if on each subspace spanned by all but one column of D, there are r(r-2) r-k + 1 data points with spark r (that is, any subset of r -1 points are linearly independent).

In this paper, we investigate a constrained version of lowrank SCA (LRSCA) where factor matrices D and B are required to be nonnegative. This leads to the following nonnegative LRSCA problem, which is equivalent to k-sparse nonnegative matrix factorization (K-NMF). Definition 2 (K-NMF). Given a nonnegative matrix M ∈ R d×n In this paper, we discuss the identifiability of K-NMF and dedicated algorithms. The contributions of this paper are the following:

• We show that K-NMF is identifiable under milder conditions than LRSCA for d = 3. Generalization to any rank, dimensions and sparsity level is a promising direction for further research.

• We briefly survey the literature for tackling K-NMF: most methods rely either on alternating optimization using sparse nonnegative least squares (sNNLS) or on subspace estimation. We propose two algorithms: an exact combinatorial algorithm for sNNLS that is used in combination of a standard alternating approach, and a nonnegative adaptation of K-subspace.

• We compare the performance of the proposed methods with existing ones on simulated data sets where the impact of the dimension d on the performance is studied. The main two observations are that (i) solving the sNNLS subproblems exactly can significantly impact the quality of the solution, and (ii) the nonnegative adaptation of K-subspace often outperforms alternating optimization methods. Finally, we showcase K-NMF on spectral unmixing of an hyperspectral image (HSI) using our proposed methods.

IDENTIFIABILITY OF K-NMF

In this section, we discuss the identifiability of K-NMF, making use of recent works for the identifiability of LRSCA [START_REF] Cohen | Identifiability of lowrank sparse component analysis[END_REF].

We do not formally prove a general identifiability results in this short paper, but instead explain why K-NMF requires milder conditions than LRSCA for identifiability, which is verified for d = 3. The rationale goes as follows. Suppose there exist two solutions to the K-NMF problem, and suppose without loss of generality that the data points and basis elements are scaled so that they belong to the unit simplex (that is, ||M (:, j)|| 1 = 1 for all j and ||D(:, k)|| 1 = 1 for all k). Then the data points are located on the the intersection of the convex hull of two polytopes with r vertices. Such an intersection is described by a finite number of low-dimensional subspaces. In order to ensure uniqueness of K-NMF, there must be sufficiently many well-located data points in order for such intersections not to be able to contain them all. Because of nonnegativity, these intersections are more constrained than for LRSCA. Let us show this for d = 3; see Fig. 1. In that case, the only non-trivial case is k = 2, and a solution of K-NMF can be represented as a triangle whose edges contain the data points. If the solution is not unique, the data points are located on the intersection of two triangles. Since two triangles can intersect on at most six points, K-NMF will be unique if there are at least two data points on each edge and one edge contains at least three data points. On Fig. 1, adding a single data point on any segment makes the factorization unique. In the mean time, without nonnegativity, non-unique LRSCA exists with nine data points, three per subspace spanned by two columns of D [START_REF] Cohen | Identifiability of lowrank sparse component analysis[END_REF]. Therefore, regarding identifiability of LRSCA, nonnegativity plays an important role yet unexplored in the literature, as far as we know. Consequently, one way to study the identifiabildata points first decomposition second decomposition Fig. 1. A case where parameters of K-NMF are not identifiable. ity of K-NMF is to provide sufficient conditions on the data under which such intersection cannot exist unless the two solutions coincide. However the geometry of such an intersection can be quite complex, especially since some facets might belong to both factorizations. Note that K-NMF is identifiable under the same sufficient conditions as LRSCA stated in Theorem 1 since it is a particular instance of LRSCA. We conjecture that it can be identifiable under milder assumptions, as it is the case for d = 3 as discussed above. This is an important topic for further research.

ALGORITHMS FOR K-NMF

Let us now discuss the computational aspects of K-NMF. Using the Frobenius norm as an error metric, computing K-NMF can be formulated as the follows

min D∈R d×r + ,B∈R r×n + M -DB 2 F such that B(:, j) 0 ≤ k < r for 1 ≤ j ≤ n. (1)
Solving ( 1) is bound to be difficult, since both NMF and SCA are NP-hard problems [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF][START_REF] Vavasis | On the complexity of nonnegative matrix factorization[END_REF]. Existing algorithms Traditionally, both NMF and SCA are solved using alternating optimization (AO) on D and B [START_REF] Gillis | Successive nonnegative projection algorithm for robust nonnegative blind source separation[END_REF][START_REF] Gribonval | Sparse and spurious: dictionary learning with noise and outliers[END_REF]. In the low-rank case, solving (1) with a fixed B amounts to solving a nonnegative least squares (NNLS) problem, which can be done efficiently using for example an active-set method [START_REF] Kim | Fast nonnegative matrix factorization: An active-set-like method and comparisons[END_REF] or coordinate descent [START_REF] Hsieh | Fast coordinate descent methods with variable selection for non-negative matrix factorization[END_REF]. However, solving (1) for D fixed is a challenging task known in the litterature as nonnegative sparse coding [START_REF] Hoyer | Non-negative sparse coding[END_REF] or sparse NNLS (sNNLS). Similarly to sparse coding, the two most important families of heuristics to obtain a solution to sNNLS are • Matching pursuit methods that compute scalar products between data points and the known D. We refer to these as Nonnegative Orthogonal Matching Pursuit (NNOMP) variants [START_REF] Bruckstein | Sparse non-negative solution of a linear system of equations is unique[END_REF][START_REF] Peharz | Sparse nonnegative matrix factorization with l0-constraints[END_REF][START_REF] Yaghoobi | Fast nonnegative orthogonal matching pursuit[END_REF][START_REF] Nguyen | An optimized version of non-negative omp[END_REF].

• LASSO methods where sparsity is enforced using a 1 norm penalty, a convex surrogate of the 0 norm. Various optimization solutions exist such as multiplicative update [START_REF] Hoyer | Non-negative matrix factorization with sparseness constraints[END_REF][START_REF] Mørup | Approximate 0 constrained non-negative matrix and tensor factorization[END_REF], projected gradient [START_REF] Rapin | Sparse and non-negative BSS for noisy data[END_REF] or coordinate descent [START_REF] Hsieh | Fast coordinate descent methods with variable selection for non-negative matrix factorization[END_REF].

On top of these two large families, an adaptation of K-SVD has also been developped for K-NMF [START_REF] Aharon | K-SVD and its non-negative variant for dictionary design[END_REF]. Both NNOMP and LASSO approaches have the drawback of solving the sNNLS subproblems for variable B in a suboptimal way. Of course these methods have theoretical guarantees of providing the optimal solution to sNNLS under some conditions on D [START_REF] Tropp | Greed is good: Algorithmic results for sparse approximation[END_REF][START_REF] Tropp | Just relax: Convex programming methods for identifying sparse signals in noise[END_REF]. However, even if such conditions are verified for the true D, it is unlikely for such conditions to be satisfied at each step of the AO scheme. Therefore, AO using for instance NNOMP will most likely not solve optimally the subproblems of finding B with known D at every iterations which may lead to rather different solutions than if the subproblems were solved exactly; see Section 4.

Another class of algorithms for K-NMF are based on subspace clustering methods. A well-known subspace clustering algorithm is an adaptation of k-means, sometimes refered to as K-subspace [START_REF] Wang | K-subspace clustering[END_REF]. For the sake of simplicity, we only discuss K-subspace in this paper, but there exist many other subspace clustering methods; see [START_REF] Vidal | Subspace clustering[END_REF] for an overview. Ksubspace is also an alternating algorithm, but instead of alternating between B and D as discussed above, it alternates between the estimation of (i) the span of D \ D(:, j) for all j and (ii) the positions of the zero values in each column of B. In fact, as discussed in Section 2, in the case k = r -1, data points lie on the union of r hyperplanes generated by all columns of D but one. Therefore, knowing to which hyperplane each data point belongs, it is possible to use any subspace estimation method such as PCA to compute a basis and scores for these data points. Since K-subspace explores the search space in a different manner than the AO methods discussed above, it may output rather different results, as observed in Section 4. A drawback of K-subspace, on top of working only for k = r -1, is that the estimation quality of D might be more sensitive to noise since D is obtained by intersecting the estimated subspaces. Moreover, as far as we know, there does not exist a variant of K-subspace taking nonnegativity into account.

In the next paragraphs, we propose two algorithms: one based on AO but solving the sNNLS subproblems exactly, and the other taking nonnegativity into account within Ksubspace and generalizing for any k. These algorithms are rather straightforward to develop. What is rather interesting is our observations from Section 4: the two proposed methods can outperform standard AO strategies and K-subspace to recover the true underlying identifiable factors D and B. ESNA: a combinatorial algorithm As for AO, we propose to compute K-NMF by solving (1) alternatively for D and B. As previously, D is updated by solving a nonnegative least squares problem. However, as opposed to most previous methods, when solving for B, we solve the sNNLS subproblem up to global optimality using a brute-force approach (further work includes using more sophisticated combinatorial approaches). In a nutshell, for each pattern of r -k zeros and for each column of B, a NNLS problem is solved, and the best solutions is kept. The computational complexity of this step is Y || F , with A ∈ R d×k and Y ∈ R d×n . We refer to this algorithm as Exact Sparse and Nonnegative Alternating least squares (ESNA). Computing exactly the solution of sNNLS may seem unrealistic, since it is typically coined as a very time consuming process with exponential algorithmic complexity. However, in K-NMF, both k and r are typically small, thus the term r k may remain sufficiently small in practical applications (e.g., in HSI, r is of the order of 10-20 while k is of the order of 2-5). In Section 4, ESNA is used to unmix a HSI with r = 6 and k = 2. Also, note that the NNLS subproblems involve k variables instead of r, where k can be an order of magnitude smaller than r.

ESNA has a few interesting features. First, it is the best possible AO algorithm, therefore its performance provide an upper bound for other AO algorithms to reach. Second, it can be seen as a subspace clustering algorithm: finding D means finding the subspaces knowing both data affectation and scores, while computing all possible k-sparse B means finding the best affectation of data to k subspaces in terms of reconstruction error. However, there is no reason to believe that ESNA is the best subspace clustering algorithm, and in the following we suggest another nonnegative subspace clustering solution avoiding exponential complexity. Third, since it is an exact block coordinate descent algorithm, the cost function always decreases.

NOLRAK: a nonnegative subspace clustering algorithm

While running experiments, we observed that K-subspace sometimes was able to identify the true underlying solution while ESNA was failing. Therefore, we propose a second algorithm adapted from K-subspace taking nonnegativity into account: NOnnegative Low-RAnk K-subspace (NOLRAK). Just like K-subspace, NOLRAK alternates between the affectation of each data points and the computation of a basis for each subspace. However, unlike K-subspace, it estimates nonnegative coefficients and uses the fact that the subspaces are generated using the columns of D, and thus does not resort to intersecting estimated subspaces. Also, each data point is not affected to only one hyperplane, but rather to r -k, to account for the knowledge of the sparsity level k. NOLRAK iterates the two following steps:

Step 1. Knowing D, for each data point m i (1 ≤ i ≤ n) and for each hyperplane H j = span(D\D(:, j)), the affectation of m i to r -k hyperplanes is obtained by computing the distances m i -Proj Hj (m i ) 2 for 1 ≤ j ≤ r and selecting the r -k smallest values. This fixes r -k zeros for the ith column of B. In other words, we assign each data point to the r -k closest hyperplanes.

Step 2. Knowing the positions of r -k zeros in each column of B, the values of D and the other coefficients of B are obtained by computing the NMF of M with a fixed support for B. For this step, we use the so-called accelerated hierarchical alternating least squares (A-HALS) algorithm for NMF [START_REF] Gillis | Accelerated multiplicative updates and hierarchical als algorithms for nonnegative matrix factorization[END_REF]. This step is a generalization of the subspace basis estimation in K-subspace, but uses NMF instead of PCA.

When using A-HALS which runs in O(dnr) operations per iteration (like most NMF algorithms [START_REF] Gillis | The Why and How of Nonnegative Matrix Factorization[END_REF]), the computational complexity of NOLRAK per iteration is also in O(dnr). Although NOLRAK requires computing a NMF at each iteration, it scales linearly in the dimension of the problem. Hence, it can be applied to large-scale data sets (as opposed to ESNA which can only be used for small r and/or small k).

NUMERICAL EXPERIMENTS

In this section, we perform some numerical experiments to assess the performance of ESNA and NOLRAK compared to existing approaches. Simulated experiments We are interested in the following question: "For an exact K-NMF problem that satisfies the identifiability conditions of LRSCA (Theorem 1), are any of the algorithms discussed above able to exactly recover the dictionary D?" Due the space limitation, we only consider small-scale problems: the rank r is set to 4 and the sparsity level k to 3 or 2. The number of data points is set to n = 200 for k = 3 and n = 300 for k = 2. We generate entries of D and B using uniform distributions in [0, 1]. The columns of the matrix D are normalized, and B is sparsified so that identifiability is ensured (for k = 3, the four subspaces are randomly populated, while for k = 2, the six segments are populated, each with 50 points). Performance are computed over N = 100 realizations1 . The grid parameter is the sample dimension d, since a larger d leads to less correlation in D, thus heuristics such as NNOMP are expected to perform better as d increases. Initialization is random with optimal scaling, but we tried a separable NMF initialization [START_REF] Gillis | Fast and robust recursive algorithmsfor separable nonnegative matrix factorization[END_REF] with similar results. Figure 2 presents the performance in terms of the recovery of D (meaning that the relative MSE ||D-Dcomputed|| F ||D|| F < 10 -4 ) and average relative MSE of the following methods: ESNA, AO with SuNNOMP [START_REF] Nguyen | An optimized version of non-negative omp[END_REF], truncated active set [START_REF] Peharz | Sparse nonnegative matrix factorization with l0-constraints[END_REF] (a.set NNOMP), LASSO with coordinate descent [START_REF] Gillis | Sparse and unique nonnegative matrix factorization through data preprocessing[END_REF] (LASSO-HALS) and NMF with HALS [START_REF] Gillis | Accelerated multiplicative updates and hierarchical als algorithms for nonnegative matrix factorization[END_REF] (NMF-HALS), NOLRAK and K-subspace [START_REF] Wang | K-subspace clustering[END_REF] (KSub). For LASSO-HALS, we used a grid on the regularization parameter λ to choose it, more details are available alongside the code. To help understanding the figure, note that the reconstruction errors on the factor D are distributed in two clusters: either a large error (missidentification, above a few percent of relative error), or machine precision. The only exception is LASSO-HALS which never reaches machine precision. We observe that AO solving inexactly the sNNLS subproblems (namely, NMF-HALS, LASSO-HALS, SuNNOMP and a.set NNOMP) do not manage to compute K-NMF reliably. On the other hand, both ESNA and NOLRAK perform well, and NOLRAK performs better than ESNA for k = 2 despite being computationally cheaper. Note that when k = r -1 = 3, independently of d, K-subspace can sometimes identify D when other alternating methods fail. Spectral Unmixing The Urban hyperspectral image (HSI)2 contains 162 spectral bands with 307 × 307 pixels for each band. Noisy bands were removed beforehand. It is a rather simple and well understood data set: it is mainly composed of r = 6 types of materials (grass, trees, two types of roof tops, road and dirt) as reported in [START_REF] Guo | L1 unmixing and its application to hyperspectral image enhancement[END_REF]. The scene represents a wallmart, its parking lot and the surrounding area (it can be found on Google maps with the keywords "copperas cove texas walmart"). In the K-NMF model, each column of the matrix M ∈ R 162×94249 is the reflectance spectrum measured for a pixel, each column of D ∈ R 162×6 is the spectral signature of a pure material and each column of B ∈ R 6×94249 gives the abundance of the pure materials in the corresponding pixel. This HSI has relatively high spatial resolution hence most pixels contain no more than two materials so that using k = 2 makes sense. ESNA gives a solution with relative error ||M -DB|| F ||M || F = 5.08% which, in this case, performs better than NOLRAK with relative error of 7.91%. Fig. 3 displays the abundance maps (the matricized rows of B) which localize the pure materials relatively well.

CONCLUSION

In this paper, we have first discussed the identifiability of K-NMF showing that it requires milder assumption than LRSCA to obtain essentially unique decompositions. Then, we have proposed two algorithms, and shown their superiority compared to the state of the art. In particular, we have observed that (i) solving exactly the sNNLS subproblems within AO impacts significantly the outcome of the algorithm and allows to obtain significantly better solutions in many cases, and (ii) algorithms based on subspace clustering are a promising direction for research as they outperform AO in some cases. Far from closing the question on identifiability of K-NMF and on how to compute such decompositions, our results should be interpreted as an invitation to further study the theoretical properties and algorithms of K-NMF.

+

  and an integer r, find D ∈ R d×r + and B ∈ R r×n + where the columns of B are at least k-sparse with k < r and rank(D) = r such that M = DB.

  r k O(N N LS)(d, n, k) where O(N N LS)(d, n, k) refers to the complexity of solving the NNLS min X∈R k×n + ||AX -

Fig. 2 .

 2 Fig. 2. Average performance of K-NMF algorithms to recover D up to 10 -4 relative MSE (left) and relative MSE (right) for k = 2 (top) and k = 3 (bottom).

Fig. 3 .

 3 Fig. 3. Abundance maps extracted by ESNA on the Urban HSI. From left to right, top to bottom: grass, trees, roof tops 1 and 2, road, dirt.

Most parameters in the proposed experiment can be toyed with in the code available online on github at cohenjer/Tensor_codes

Available at http://www.agc.army.mil/.

* Authors acknowledge the support of the F.R.S.-FNRS (incentive grant for scientific research n o F.4501.16), and of the European Research Council (ERC starting grant n o 679515).


Jean-Bernard Vogt
email: jean-bernard.vogt@univ-lille1.fr

Carla Carle

Jérémie Bouquerel

Ingrid Proriol Serre

Behaviour of short and long cracks in air and in liquid metal in T91 steel

The low cycle fatigue behaviour of a 9Cr1MoNbV martensitic steel has been investigated at 350°C in air and in lead-bismuth eutectic (LBE). Total strain controlled tests were performed from ∆ε t = 0.40% to 1.2%. The material exhibited a pronounced cyclic softening in both environments. LBE reduced the fatigue resistance. LBE accelerated the formation of the long crack by promoting the growth of the first short cracks. A clear change in propagation mode was observed. In air, ductile fatigue striations were observed while in LBE a brittle fracture decorated by voluminous and largely spaced striations were visible. From EBSD analysis, it was concluded that in LBE, the long crack advanced quickly by repeated and discontinuous cleavage.

Introduction

T91 martensitic steel is a modified grade of the 9Cr1Mo steel family. It exhibits excellent combination of strength and ductility which can be achieved by control of the heat treatment. With the addition of Nb and V, T91 is particularly chosen for application where creep resistance is required. It is therefore employed for structural components in all industrial fields working at high temperatures such as refineries or power plants. With an amount of chromium less than 10.5 wt %, the alloy cannot be classified as stainless steel and is not really designed to operate in corrosive environments as can do the 12Cr steels.

T91 steel has been considered as one of the materials to be possibly employed for components of accelerator driven systems (ADS) or of Gen IV nuclear reactors. These systems employ liquid metals as spallation target or as coolant. Even if the ductility of T91 is somewhat appreciable, it can be decreased by irradiation e.g. [1] or by long term exposure at high temperature e.g. [2]. Besides these operating conditions that affect the bulk of the material, damage initiation by the liquid metal environment may occur as it is the case for aqueous environments e.g. [3]. Liquid metals do not involve similar corrosion mechanism as aqueous environments. Electrochemical corrosion is not a process that occurs when metallic alloys are in contact with a liquid metal.

A very amazing response that can exhibit a ductile material stressed in liquid metal is the so called liquid metal embrittlement (LME) or liquid metal assisted damage (LMAD). It has been shown by several authors working in the field of materials in contact with lead bismuth eutectic (LBE) that T91 is especially sensitive. For T91, the ductile to brittle transition in LBE at 300°C is strongly influenced by the heat treatment and especially the tempering temperature [4].

The objective of the paper is to study the effect of LBE on the mechanical response and on the behaviour of short and long cracks under cyclic loading by using low cycle fatigue tests (LCF).

Materials

The chemical composition of the studied T91 satisfies the standard. Expressed in wt%, it contains 0.1 C, 8.99 Cr, 0.89 Mo, 0.06 Nb, 0.21 V, 0.38 Mn, 0.22 Si, 0.11 Ni, 0. 0146 Al, 0.06 Cu, 0. 0034 Ti, 0.01 W, 0.021 P, 0. 0004 S, Fe bal.

The material 91 was heat treated at 1100°C for 15 minutes followed by water cooling and a subsequent tempering for 45 minutes at 770°C and then air cooling.

The microstructure is a fully tempered martensite (Figure 1) with an average hardness value of 220 HV.

MATEC

Low cycle fatigue details

A tank and samples specifically designed to perform LCF tests in LBE were machined. The specimens were smooth and cylindrical with a gauge length of 10 mm and a gage diameter of 6 mm. In order to avoid effects due to the roughness of the surface and to residual stresses developed during the machining, the sample surface was carefully electro polished. The fatigue tests were carried out using a servo-hydraulic Schenk machine with a load capacity of 250 kN under total axial strain control ∆ε t ranging from 0.40% to 1.2%. A fully push pull mode (R ε = -1), a triangular waveform and a constant strain rate of 4.10 -3 s -1 were used. All the tests were carried out at 350°C in air and in LBE.

The specimen was immersed into a small reservoir containing the LBE (Figure 2) which could not accept the extensometer to be attached onto the specimen. Therefore, the strain control was performed by using a strain gage extensometer fixed outside of the specimen.

Fig. 2. Picture showing the specimen in the LBE reservoir

The fatigue life N f , is defined as the number of cycles needed for a 25% drop in the tensile stress taking as a reference the (pseudo) stabilized hysteresis loop 4 Results

Stress response to strain cycling

Except for the test performed at ∆ε t = 0.4%, the material cycled at 350°C presents a strong tendency to softening at the beginning of cycling and then at a moderate rate (see Figure 3). Then the fall of the stress is more moderate. Finally a marked decrease of the stress amplitude occurs that is related to the propagation of a macroscopic crack into the bulk just before the final failure.

Except for the final decrease in the stress amplitude which is affected by the liquid metal, the same overall behaviour is observed when cycling in the LBE environment. Note that the amount and duration of the initial softening clearly depends on the applied strain range only.

Effect of LBE on fatigue crack initiation resistance

The evolution of the total strain range as a function of the number of cycles to failure is plotted Fig. 4.

The main effect of LBE is to reduce the fatigue resistance in comparison with tests performed in air. Such an influence of a liquid metal on fatigue resistance has been reported for the Manet II martensitic (Fe-10Cr-0.8Mn-0.2V-0.1C) in LBE at 260°C [5] and in T91 at 300°C [6] and 350°C [7].

Effect of LBE on fatigue crack propagation resistance

Normally, the study of fatigue crack propagation is performed by using pre-cracked specimens in order to connect the fatigue crack velocity da/dN to the cyclic stress intensity factor ∆K. This could not have been performed. However, the final part (the last 10 percents of the fatigue life) of the curves stress amplitude-number of cycles was analysed for that.

For each test, ∆Ν 5%-25% = Ν 25% -Ν 5% was calculated where ∆Ν 25% and ∆Ν 5% are the number of cycles correspond to a 25% drop in the tensile stress and to a 5% drop in the tensile stress respectively. The result is reported in figure 5.

Short crack analysis

Fatigue specimen were cut transversally in order to appreciate the number and the depth of the short cracks. After cutting, the specimen were polished to have a mirror surface and then were etched with the Villela etchant. After fatigue in air, it was possible to observe on the transverse cross sections a lot of short cracks of different lengths (Figure 6). After fatigue in LBE, the number of short cracks was considerably reduced so that it can be considered that only the main crack was visible. (Figure 7). The strain range had a noticeable effect on the density of short cracks in air, i.e. the density increased with the strain range, but not for the tests performed in LBE.

Long crack analysis

The long crack morphology was first observed directly on the gage length of the specimen. After fatigue in air, the main crack was accompanied by a rough zone. The rough aspect tended to vanish gradually the observation left the crack tip. However, even at 1 mm from the crack tip, the plastic deformation was still visible. After fatigue in LBE, the crack path appeared more serrated without any roughness on the lips. The most striking difference between cycling in air and in LBE was the fracture surface morphology. In air, in agreement with the short crack distribution, the fracture surface contained multiple crack initiation sites from which several cracks propagate by fatigue in the bulk and a final fracture due to monotonic loading. Fatigue striations could be observed by SEM. The fracture surfaces of specimen cycled in LBE are totally different. First, the fracture surface was very flat and contained a single initiation site from which the crack propagated by cyclic loading. The final fracture occurred by pure tensile loading. On the fracture surface related to cyclic loading, it was possible to see at very low magnification, and even with the naked eye, curved striations (Figure 8). For a given strain range, the distance between two striations increased as long as the crack advanced in the bulk. showing brittle fracture SEM-EBSD analysis were performed on specimen fatigued in air and in LBE at ∆ε t = 1.2%. When the long crack was supposed to propagate in the bulk, then the test was stopped, the specimen removed and cut along the loading direction. Specific preparation was performed to obtain high quality EBSD patterns and further processing. EBSD patterns were acquired far away from the crack to have a reference state, on the crack lips very close to the external surface, at 2.5 mm from the external surface and very near the crack tip.

For the specimen fatigued in air, the inverse pole figures (IPF) revealed that the crack lips were decorated by a continuous raw of misoriented fine grains in the very first micrometers of the material adjacent to the fracture surface (Figure 10). The grains were highly misoriented and had a grain size ranging from 0.25 µm to 0.5µm. This was not observed for the specimen failed in LBE except at some spots where small groups of misoriented fine grains similar to those observed in the specimen fatigued in air could be observed (Figure 11).

Discussion

The present investigation performed on T91 shows a conventional response typical of martensitic steel i.e. a cyclic softening. This is in accordance with the microstructure resulting from the heat treatment which produced and arranged a high density of dislocations. Annihilation can explain the softening and since it is a bulk effect, there is no reason why the presence of LBE should modifies the response. Therefore, in air as well in LBE, slip bands can emerge at the surface and intrusionextrusion pairs can form. Intrusions are preferential sites for short crack initiation and their developments are sensitive to the presence of the environment.

In air, the very first short cracks with a dimension of a grain size are hindered by the presence of grain boundaries (including a misorientation effect between the grains) which can be overcome after a given number of cycles. The crack extension proceeds by crystallographic growth and may again be delayed by other grain boundaries as its length reached three or four grain sizes. Longer microcracks (up to ten grain sizes typically) can eventually form by the coalescence of the shorter cracks and finally, only a very few of them propagated into the bulk perpendicularly to the stress axis. In LBE, the absence of short cracks is a clear indication that the liquid metal provided a driving force to the very first short cracks to overcome the structural barriers.

The presence of fatigue striation in specimen fatigued in air is a clear indication that the crack propagated in a ductile manner. The very small distance between striations suggests that the crack extension is slow and involves plastic deformation during tensile and compressive phase of the loading signal. The striations may be the result of successive blunting and resharping due to plastic deformation at the crack tip. In LBE, the large distance between striations indicates that the crack advanced rapidly. And this is in good agreement with the observations of brittle transgranular fracture. The modification of fracture mode between fatigue in air and fatigue in LBE is a simple appearance of LME. There are several explanations and models for LME. In our situation, the brittle fracture theory proposed by Stoloff and Johnson [8] & Westwood and Kamdar [9] and based on the weakening of inter-atomic bonds by the liquid metal atoms at the crack sounds well. LME occurrence requires an actual wetting between atoms of the liquid metal and the steel. This can be not encountered if the crack tip is not wetted due to capillarity. However, in our case, EDX analysis of the crack tip after fatigue in LBE clearly showed that the liquid metal reached the very crack tip. Another reason for the non wetting is the presence of an oxide film. In the present experiments, LBE was oxygen saturated which means that even fresh surface formed in the LBE, dissolved oxygen can react with the fresh steel to form an oxide film. However, the stability of the oxide film is disturbed due to very localized plasticity. And this allows atoms to adsorb the steel and to promote a liquid metal assisted crack propagation.

Finally, the EBSD analysis revealed a very strong and localized activity of cyclic plasticity at tip of a crack propagating in air in which recrystallization operated and gave rise to new fine grains. The absence of such fine grains in large portion of the crack lip in specimen fatigued in LBE is well in agreement with brittle fracture. The presence of fine grains at some spots of the lips may be explained by the temporary arrest of the brittle crack due to temporary non-wetting of the surface by the atoms of the liquid metal.

Conclusion

The low cycle fatigue behaviour of the T91 martensitic steel has been investigated at 350°C in air and in LBE. LBE accelerates the formation of the long crack by promoting the growth of the first short cracks. In LBE, the long crack advanced quickly by repeated and discontinuous cleavage.

Fig. 3 .

 3 Fig. 3. Evolution of the stress amplitude with the number of cycles of T91 steel fatigued in air and LBE at 350°C

Fig. 4 .

 4 Fig. 4. Evolution of the total strain range with the number of cycles to failure of T91 steel fatigued in air and LBE at 350°C

Fig. 5 .

 5 Fig. 5. Evolution of the number of cycles for propagation of the long crack versus the total strain range of T91 steel fatigued in air and LBE at 350°C

Fig. 6 .Fig. 7 .

 67 Fig. 6. Observation of short cracks in T91 steel fatigued in air at 350°C and ∆ε t = 1.2%

Fig. 8 .

 8 Fig. 8. Macroview of the fracture surface of T91 steel fatigued in LBE at 350°C and ∆ε t = 1.2% (the red arrow indicates crack initiation site)At higher magnification, SEM observations pointed out transgranular brittle fracture (Figure9).

Fig. 9 .

 9 Fig. 9. SEM observation of the fracture surface between two striations of T91 steel fatigued in LBE at 350°C and ∆ε t = 1.2%showing brittle fracture

Fig. 10 :

 10 Fig. 10: IPF acquired near the crack tip in T91 fatigued in air at 350°C and ∆ε t = 1.2%

Fig. 11 :

 11 Fig. 11: IPF acquired near the crack tip in T91 fatigued in LBE at 350°C and ∆ε t = 1.2%

© The Authors, published by EDP Sciences. This is an open access article distributed under the terms of the Creative Commons Attribution License 4.0 (http://creativecommons.org/licenses/by/4.0/).

MATEC Web of Conferences 165, 03016 (2018) https://doi.org/10.1051/matecconf/201816503016 FATIGUE 2018

Acknowledgements

The work was partly funded by the European Atomic Energy Community's (Euratom) Seventh Framework Programme FP7/2007-2013 under Grant agreement no. 604862 (MatISSE project)


Olivier Gasquet

Dominique Longin

Frédéric Maris

Pierre Régnier

Maël Valais

Compact Tree Encodings for Planning as QBF

Considerable improvements in the technology and performance of SAT solvers has made their use possible for the resolution of various problems in artificial intelligence, and among them that of generating plans. Recently, promising Quantified Boolean Formula (QBF) solvers have been developed and we may expect that in a near future they become as efficient as SAT solvers. So, it is interesting to use QBF language that allows us to produce more compact encodings. We present in this article a translation from STRIPS planning problems into quantified propositional formulas. We introduce two new Compact Tree Encodings: CTE-EFA based on Explanatory frame axioms, and CTE-OPEN based on causal links. Then we compare both of them to CTE-NOOP based on No-op Actions proposed in (Cashmore, Fox, and Giunchiglia 2012). In terms of execution time over benchmark problems, CTE-EFA and CTE-OPEN always performed better than CTE-NOOP.

Introduction

An algorithmic approach for plans synthesis is automated compilation (i.e., transformation) of planning problems. In the SATPLAN planner [START_REF] Kautz | Planning as satisfiability[END_REF], a planning problem is transformed into a propositional formula whose models, corresponding to solution plans, can be found using a SAT solver. The SAT approach searches for a solutionplan of fixed length k. In case of failure to find such a plan, this length is increased before restarting the search for a solution. In the classical framework, the complexity of finding a solution to any problem is PSPACE-hard, but the search for a fixed-size solution becomes NP-hard (By-lander 1994). This compilation approach directly benefits from improvements in SAT solvers1 . The most obvious ex-ample is the planner BLACKBOX [START_REF] Kautz | BLACKBOX: A new approach to the application of theorem proving to problem solving[END_REF]1999) (and its successors SATPLAN'04 [START_REF] Kautz | Satplan04: Planning as satisfiability[END_REF]) and SATPLAN'06 [START_REF] Kautz | Satplan04: Planning as satisfiability[END_REF]). These planners won the optimal (in the number of plan steps) planning track of the International Planning Competitions2 IPC-2004 andIPC-2006. This was unexpected because these planners were essentially updates of BLACKBOX and did not include any real novelty: improved performance was mainly due to progresses in the underlying SAT solver.

Numerous improvements of this original approach have been proposed since then, in particular via the development of more compact and efficient encodings [START_REF] Kautz | Pushing the envelope: Planning, propositional logic and stochastic search[END_REF][START_REF] Ernst | Automatic SAT-compilation of planning problems[END_REF][START_REF] Mali | Refinement-based planning as satisfiability[END_REF]1999;[START_REF] Rintanen | Symmetry reduction for sat representations of transition systems[END_REF][START_REF] Rintanen | Parallel encodings of classical planning as satisfiability[END_REF]2006;Rintanen et al. 2008). Following these works, numerous other similar techniques for encoding planning problems have been developed: Linear Programming (LP) [START_REF] Wolfman | The LPSAT engine & its application to resource planning[END_REF], Constraint Satisfaction Problems (CSP) [START_REF] Do | Planning as constraint satisfaction: Solving the planning graph by compiling it into CSP[END_REF], SAT Modulo Theories (SMT) [START_REF] Shin | Processes and continuous change in a sat-based planner[END_REF][START_REF] Maris | TLP-GP: new results on temporally-expressive planning benchmarks[END_REF][START_REF] Rintanen | Discretization of temporal models with application to planning with SMT[END_REF]. More recently, a Quantified Boolean Formulas (QBF) approach had been proposed by [START_REF] Rintanen | Asymptotically optimal encodings of conformant planning in QBF[END_REF][START_REF] Cashmore | Planning as quantified boolean formula[END_REF].

Currently SAT solvers outperform QBF solvers and the SAT approach is the most effective because SAT solvers and encodings have been greatly improved since 1992. However, over the past decade, there has been a growing interest in the QBF approach. The competitive evaluation of QBF solvers QBFEVAL3 is now a joint event with the international SAT conference and QBF solvers improve regularly. QBFEVAL'16 had more participants than ever and QBFrelated papers represented 27% of all papers published at SAT'16. Some promising techniques have been adapted to QBF solving such as counterexample guided abstraction refinement (CEGAR) [START_REF] Clarke | Counterexample-guided abstraction refinement for symbolic model checking[END_REF][START_REF] Janota | Solving QBF by clause selection[END_REF][START_REF] Janota | Solving QBF with counterexample guided refinement[END_REF][START_REF] Rabe | CAQE: A certifying QBF solver[END_REF]. For comparable SAT / QBF encodings, the QBF approach also have the advantage to generate more compact formulas [START_REF] Cashmore | Planning as quantified boolean formula[END_REF]. Even if the QBF approach is not as efficient as the SAT approach, it deserves the interest of the community.

Our paper shows that beyond the implementation of solvers, further work must be done to improve the encodings. In particular, we introduce two new QBF Compact Tree Encodings of STRIPS planning problems: CTE-EFA based on Explanatory frame axioms, and CTE-OPEN based on causal links. Then we compare both of them to CTE-

X i bi=⊥ bi=⊤ right(i) X i-1 bi-1=⊤ X i-1 bi-1=⊥ X i-2 bi-2=⊥ b {i-2,...,1} =⊤ X i-2 b {i-2,...,1} =⊥ bi-2=⊤ X 0 left(i) C C X 0
Figure 1: Both possible transitions in a CTE following the branching structure of a QBF: X 0 → X i (from leaf to node on the left) and X i → X 0 (from node to leaf on the right).

Note that i refers to any level (except for the leaf layer), not only the root.

NOOP based on No-op Actions proposed in [START_REF] Cashmore | Planning as quantified boolean formula[END_REF]. In terms of execution time over benchmark problems, CTE-EFA and CTE-OPEN always performed better than CTE-NOOP.

Planning as QBF

Two different approaches of planning as QBF have been proposed by [START_REF] Cashmore | Planning as quantified boolean formula[END_REF]: Flat Encoding, that was first introduced by [START_REF] Rintanen | Partial implicit unfolding in the davisputnam procedure for quantified boolean formulae[END_REF]) as an approach to general reachability, and Compact Tree Encoding (CTE). Cashmore, Fox, and Giunchiglia showed in (2012) that Compact Tree Encodings outperform Flat Encodings. Both these planning encodings make use of the branching structure of the QBF to reuse a single set of clauses that describes a single step in the plan. The two assignments inside each universal variable represent the first and second half of the plan split around that branch. The assignments to each existential set represent action choices within a single step.

Preliminary Definitions

Let F be a finite set of fluents (atomic propositions). A STRIPS planning problem is a tuple I, A, G where I ⊆ F is the set of initial fluents, G ⊆ F is the set of goal fluents and A is the set of actions. An action a ∈ A is a tuple Pre(a), Add(a), Del(a) where

• Pre(a) ⊆ F is the set of fluents required to be true in order to execute a,

• Add(a) ⊆ F and Del(a) ⊆ F are the sets of fluents respectively added and removed by the action a.

All QBF encodings studied in this paper use propositional variables for actions. The Compact Tree Encoding proposed in [START_REF] Cashmore | Planning as quantified boolean formula[END_REF] is based on the planning graph introduced in [START_REF] Blum | Fast planning through planning-graphs analysis[END_REF] and uses additional no-op actions as frame axioms. We denote it by CTE-NOOP. Considering every action as a propositional variable, we define a set of propositional variables X, given by X = A ∪ {noop f | f ∈ F}.

In a CTE formula, we want to select two consecutive steps in order to define transitions (Figure 1). For each depth i of the tree, X i denotes a copy of the set of variables X.

For CTE-NOOP, there exists a single variable a i ∈ X i for each action and a single variable noop f,i ∈ X i (noop action) for each fluent used to determine a transition in the plan. At a same depth i, the value of these variables depends on the node (corresponding to a step in the plan) selected by the values of upper universal branching variables b i+1 . . . b depth . More details can be find in the slides 4 .

An upper bound on the plan length is 2 k+1 -1, where k is the number of alternations of quantifiers in the quantified boolean formula associated with the planning problem. In the case of CTE, k is also the compact tree depth. The number of possible states for a given planning problem is bounded by 2 |F | . Then, the existence of a plan can be determined using a linear QBF encoding with at most k =| F |.

In the sequel, we propose two new encodings of planning problems into QBF. The first, denoted by CTE-OPEN, is based on causal links (plan-space). It has been first introduced by [START_REF] Mali | On the utility of planspace (causal) encodings[END_REF]) but needs to be adapted using additional variables for open conditions. The second, denoted by CTE-EFA, is based on explanatory frame axioms (state-space) first introduced by (Kautz and Selman 1992) and uses variables for fluents as well as for actions.

Causal Link Encoding: CTE-OPEN

The plan-space encodings of [START_REF] Mali | On the utility of planspace (causal) encodings[END_REF] cannot be directly adapted to the CTE. All these encodings refer to three indexed (not necessarily consecutive) steps of the plan. This is not possible in a CTE because each rule can refer to only one branch of the tree. To overcome this problem, it would be possible to duplicate the tree by adding, for each branching variable b i , two more branching variables b ′ i and b ′′ i , and for each node X i , two node copies X ′ i and X ′′ i , and equivalence rules xi∈Xi

(x i ↔ x ′ i ) ∧ (x i ↔ x ′′ i ) .
Unfortunately, this would increase the branching factor unnecessarily. So, we propose a new plan-space encoding which allows us to only refer to consecutive steps in the plan.

For every fluent f ∈ F, we create a propositional variable open f to express that f holds in some previous step and must be protected at least until the current step. In Figure 2, the fluent f is an open condition in step S i , entailing that either f ∈ I or an action a ′ which adds f is executed in a previous step S i-k . Open conditions are propagated backwards until the initial state or some step in which they are added by an action.

We define the set of "open" variables, denoted as ∆, as ∆ = {open f | f ∈ F}. Considering every action as a propositional variable, we define a set of propositional variables X, given by X = A ∪ ∆.

Quantifiers For each depth i of the tree, X i denotes a copy of the set of variables X. It exists a single variable a i ∈ X i for each action used to determine last transition in the plan and a single variable open f,i ∈ X i for each fluent used to determine if f is an open condition. At a same depth i, the value of these variables depends on the node (corresponding to a step in the plan) selected by the values of upper universal branching variables b i+1 . . . b depth .

∃ a∈A adepth. ∃ f ∈F open f,depth . ∀ bdepth. ∃ a∈A adepth-1. ∃ f ∈F open f,depth-1 . ∀ bdepth-1. . . . ∃ a∈A a1. ∃ f ∈F open f,1 . ∀ b1. ∃ a∈A a0. ∃ f ∈F open f,0 .
In the following, a node now refers to a non-leaf node (i.e., an inner node) and depth is the depth of the tree. The predecessor of a node at level i is the rightmost leaf of the left subtree. The successor of a node at level i is the leftmost leaf of the right subtree. In order to select these transitions, we introduce the leaf-to-node operator left(i) defined as:

left(i) ≡ ¬b i ∧ i-1 j=1 b j .
Symmetrically, we introduce the node-to-leaf operator right(i) defined as:

right(i) ≡ b i ∧ i-1 j=1 ¬b j .
Open conditions If an action a is executed in a step of the plan, then each precondition of a must be an open condition at this step (i.e., a causal link is required for this precondition).

depth i=0 a∈A   a i ⇒ f ∈Pre(a) open f,i  
In the last plan step leading to the goal (i.e. the rightmost leaf of the tree), all the goal fluents must be either open conditions or added by actions executed in this step.

depth i=1 b i ⇒ f ∈G     open f,0 ∨ a∈A f ∈Add(a) a 0     a f ∈ Pre(a) open f S i-1 S i propagate open f S i-k open f a ′ f ∈ Add(a ′ )
Figure 2: Causal link: a ′ produces f for a.

Propagate and close

No conditions should remain open in the first plan step (i.e. the leftmost leaf of the tree) if it is not provided in the initial state.

depth i=1 ¬b i ⇒ f ∈F \I ¬open f,0
Any open condition in a step must either remain open or be added (closed) by an action in the previous step.

depth i=1 f ∈F     open f,i ∧ left(i) ⇒     open f,0 ∨ a∈A f ∈Add(a) a 0         depth i=1 f ∈F     open f,0 ∧ right(i) ⇒     open f,i ∨ a∈A f ∈Add(a) a i        
Protect open conditions An open condition in a given step cannot be removed in the previous step. This guarantees not to break any causal link in the plan.

depth i=1 f ∈F     open f,i ∧ left(i) ⇒ a∈A f ∈Del(a) ¬a 0     depth i=1 f ∈F     open f,0 ∧ right(i) ⇒ a∈A f ∈Del(a) ¬a i    
Prevent negative interactions In a given step, if an action removes a fluent which is needed or added by another action, then these two actions cannot be both executed in this step.

depth i=0 a∈A f ∈(Add(a)∪Pre(a)) a ′ ∈A a =a ′ f ∈Del(a ′ ) (¬a i ∨ ¬a ′ i )

State-Space Encoding: CTE-EFA

In this encoding, we define the set of propositional variables as X = A ∪ F. Each step is now defined by a transition (as in CTE-OPEN) as well as the resulting state (valuation of the fluents in F). The formula is an adaptation to the CTE of the well known state-space SAT encoding rules based on explanatory frame axioms of (Kautz and Selman 1992).

Quantifiers At each depth i of the tree, it exists a single variable a i for each action used to determine last transition in the plan and a single variable f i for each fluent used to determine the state. At a same depth i, the values of these variables depend on the node (corresponding to a transition in the plan and the resulting state) selected by the values of upper universal branching variables b i+1 . . . b depth .

∃ a∈A adepth. ∃ f ∈F fdepth. ∀ bdepth. ∃ a∈A adepth-1. ∃ f ∈F fdepth-1. ∀ bdepth-1. . . . ∃ a∈A a1. ∃ f ∈F f1. ∀ b1. ∃ a∈A a0. ∃ f ∈F f0.
Goal In the state after the last plan transition (i.e. the rightmost leaf of the tree), all goal fluents must be achieved.

depth i=1 b i ⇒ f ∈G f 0
Conditions and effects of actions If an action a is executed in a transition of the plan, then each effect of a occurs in the resulting state and each condition of a is required in the previous state.

depth i=0 a∈A   a i ⇒   f ∈Add(a) f i   ∧   f ∈Del(a) ¬f i     depth i=1 a∈A   a i ∧ left(i) ⇒ f ∈Pre(A) f 0   depth i=1 a∈A   a 0 ∧ right(i) ⇒ f ∈Pre(A) f i  
Moreover, an action which do not have all conditions in initial state cannot be executed in the first plan transition (i.e. the leftmost leaf of the tree):

depth i=1 ¬b i ⇒ a∈A Pre(a) ⊂I ¬a 0
Explanatory frame axioms If the value of a fluent changes between two consecutive states, then an action which produces this change is executed in the plan transition between these states.

depth i=1 f ∈F     (¬f0 ∧ fi ∧ left(i)) ⇒     a∈A f ∈Add(a) ai         depth i=1 f ∈F     (¬fi ∧ f0 ∧ right(i)) ⇒     a∈A f ∈Add(a) a0         depth i=1 f ∈F     (f0 ∧ ¬fi ∧ left(i)) ⇒     a∈A f ∈Del(a) ai         depth i=1 f ∈F     (fi ∧ ¬f0 ∧ right(i)) ⇒     a∈A f ∈Del(a) a0        
An extra rule is also required to describe explanatory frame axioms for the first plan transition from initial state (i.e. the leftmost leaf of the tree):

f ∈F \I       f 0 ∧ depth i=1 ¬b i ⇒ a∈A f ∈Add(a) Pre(a)⊂I a 0       f ∈I       ¬f 0 ∧ depth i=1 ¬b i ⇒ a∈A f ∈Del(a) Pre(a)⊂I a 0      
Prevent negative interactions Unlike in CTE-NOOP and CTE-OPEN, contradictory effects are already disallowed by previous rules (effects of actions). Then, this rule only need to prevent interactions between conditions and deletes of actions. If an action removes a fluent which is needed by another action, then these two actions cannot be both executed in a same plan transition.

depth i=0 a∈A f ∈Pre(a) a ′ ∈A a =a ′ f ∈Del(a ′ ) (¬a i ∨ ¬a ′ i )

Experimental Trials

To compare these three encodings on a same basis we used our translator TouIST5 [START_REF] Comte | Twist your logic with touist[END_REF]) that can use several QBF solvers. We ran all available STRIPS IPC benchmarks (1 through 8, except for the 7th which was not available and authors did not answer) on an Intel Xeon CPU E7-8890 v4 @ 2.20GHz, 512 GB of RAM. The domains tested include Gripper, Logistics, Mystery, Blocks, Elevator, Depots, DriverLog, ZenoTravel, FreeCell, Airport, Pipesworld-NoTankage, Pipesworld-Tankage, PSR, Satellite, OpenStacks, Pathways, Rovers, Storage, TPP, Trucks, ChildSnack, Hiking, VisitAll and the non-IPC Ferry.

We tried to consider as many QBF solvers as possible using the QBFEval 2017 as a reference. Qute (version of 2017-07-09, based on dependency learning QCDCL) and CaQE (version of 2017-07-08, based on CEGAR clausal abstraction) were not able to give a valuation for the outer existential quantifier. AIGSolve and Qell weren't available for download. GhostQ was skipped (but we should have included it). DepQBF (version 6.03 of 2017-08-02, based on generalized Q-resolution, described in [START_REF] Lonsing | Depqbf 6.0: A search-based QBF solver beyond traditional QCDCL[END_REF]) and RAReQS (version 1.1 of 2013-05-07, based on a CEGAR approach, detailed in [START_REF] Janota | Solving QBF with counterexample guided refinement[END_REF])) were the only solvers left. RAReQS was consistently twice as fast as DepQBF, we thus dismissed DepQBF and only shown results for RAReQS. Finally, we did not apply any QBF preprocessor (e.g., Bloqqer). We ran these benchmarks using our new encodings CTE-EFA and CTE-OPEN as well as the state-of-the-art compact tree encoding (CTE-NOOP). We compared them two-bytwo by considering the time needed to prove the existence of a plan (decision time, Figure 3) and the overall time required to obtain a plan (extraction time, Figure 5). The "decision" step consists of launching incrementally the QBF solver on a CTE of increasing depth until the solver returns true or reaches the upper bound (total number of fluents). The "extraction" step consists of one solver launch per node of the tree in order to retrieve the plan. Each experiment had a 60 minutes6 timeout for searching the plan and 60 minutes for extracting it. The benchmark results are available as an Excel file 7 .

The results show that our encodings CTE-EFA and CTE-OPEN are more efficient than CTE-NOOP both in plan existence as well as in plan extraction. CTE-EFA by a factor of 2.1 (1/0.4843) and CTE-OPEN by a factor of 1.7 (1/0.5953). Also, the comparison between CTE-EFA and CTE-OPEN (Figure 4, Figure 6) consistently shows that CTE-EFA outperforms CTE-OPEN by a factor of 1.4 (1/0.7266). Table 1 gives a summary of the benchmark results.

Contrary to what happens with flat encodings, the gain over CTE-NOOP cannot be explained by the difference in quantifier alternations as the depth is the same in the three encodings. However, the way actions are represented in these encodings may explain this difference.

Discussion

In order to identify the source of these improvements, we propose two hypothesis:

Hypothesis 1 "The performance gain is correlated to a decrease in the number of clauses and/or literals across encodings". Although the size of the problem is known to be noticeably non-correlated with its hardness in SAT, we wondered if we could see the same non-correlation.

As shown in Table 1, we do not observe any clear tendency: CTE-EFA tends to have a slightly higher number of clauses (+15%) than CTE-NOOP although having less variables (-26%). CTE-OPEN has the same number of literals and much less clauses than CTE-NOOP, but resulting in a lower performance gain (-41%) than CTE-EFA (-55%). This non-correlation leads us to reject this hypothesis. Hypothesis 2 "The performance gain is due to a difference in the number of transition-based constraints compared to the number of node-based constraints". Intuitively, one can think that a lower ratio of transition-based constraints over node-based constraints would ease the solving pro-cess: in node-based constraints, a clause has the same context8 across the whole QBF expansion. In branch constraints, the corresponding clause has different contexts depending on the selected branch. The idea is that clauses based on different contexts slow the solver down. As displayed in Table 1, this hypothesis does not appear to be correct experimentally: although CTE-OPEN shows a lower transitions-to-nodes ration, it does not lead to the best performance gain. On the contrary, CTE-EFA has a poorer ratio, although being the most efficient compared to CTE-NOOP. We thus refute this hypothesis as we did not see any noticeable correlation supporting it, although we noticed a slight tendency where the decrease of time and of number of clauses were correlated.

Through these hypotheses, we tried to understand the causes of these enhancements. None of these hypothesis proved to be useful.

Conclusion

We have proposed two new QBF Compact Tree Encodings: CTE-OPEN based on causal links (plan-space) and CTE-EFA based on explanatory frame axioms (state-space). We compared these encodings with the state-of-the-art QBF encoding CTE-NOOP. In average over all available STRIPS IPC benchmarks, CTE-EFA performed twice as fast as CTE-NOOP (respectively 1.7 times faster for CTE-OPEN).

Through experiments, we refuted the two hypotheses we had formulated in order to explain the causes of this enhancement: neither the difference in the number of literals and clauses nor the transitions-to-nodes ratio between the three encodings allow us to draw conclusions.

Although it is fair to say that the work we are presenting lacks explanations on the reasons for the gain in performance, we think that this paper aims at showing the interest of systematically studying the statistical properties of the various action representations in encodings in order to understand the ontological choices related to these action representations.

Furthermore, it is noticeable that the performance ranking of the various action representations of SAT encodings (e.g., No-op performs better than EFA) is different in QBF (as we showed, EFA performs better than No-op in the CTE encoding). It would be interesting to study more broadly the methods used in SAT for encoding actions and see how their QBF counterpart behave.

Figure 3 :

 3 Figure 3: Plan decision time (EFA/OPEN vs NOOP).

Figure 4 :

 4 Figure 4: Plan decision time (EFA vs OPEN).

Figure 5 :

 5 Figure 5: Plan extraction time (EFA/OPEN vs NOOP).

Figure 6 :

 6 Figure 6: Plan extraction time (EFA vs OPEN).

Table 1 :

 1 Comparison of the presented encodings across 65 STRIPS domains from IPC 1 through 8 (IPC 7 excepted) with a total of 2112 problems. Decision time, literals count, clauses count and the transitions-over-nodes ratio are averages. The transitions-over-nodes ratio measures the quantity (in average) of transition-based constraints over node-based constraints.

	Encoding	Solved problems	Decision Time Literals Clauses Transitions-over-nodes ratio
	CTE-NOOP 412 over 2112 (20%)	0%	0%	0%	30%
	CTE-EFA	463 over 2112 (22%)	-55%	-26%	+15%	47%
	CTE-OPEN 445 over 2112 (21%)	-41%	-2%	-28%	17%

http://www.satcompetition.org/

http://www.icaps-conference.org/index. php/Main/Competitions

http://www.qbflib.org/index_eval.php

https://www.irit.fr/ ˜Frederic.Maris/ documents/coplas2018/slides.pdf

https://www.irit.fr/touist

The grounding step (i.e., action instantiation) is not included in the elapsed time.

https://www.irit.fr/ ˜Frederic.Maris/ documents/coplas2018/results.xls

Context and expansion are defined in[START_REF] Cashmore | Planning as quantified boolean formula[END_REF]. Intuitively, the expansion is a tree representing the QBF and a context is a leaf in that tree.


Victor Vergnieux

J.-M Macé

Hombeline Valton

Emmanuel Barbeau

Vergnieux Victor

Mace Marc

J-M Valton

Hombeline Barbeau

Emmanuel Jouffrais Christophe

Spontaneous representation of vista spaces: similarities and differences between sighted and blind people

Keywords: Vista space, Spatial representation, Urban space

published or not. The documents may come

Background

Vista space (VS) is a psychological space whose scale is "larger than the body but can be visually apprehended from a single place without appreciable locomotion" [Montello, 1993]. Moreover, VS can combine to represent larger spaces [Meilinger, 2008]. VS are considered as unit elements of mental representations of space and have only been assessed in sighted subjects (not in visually impaired people).

Aims

In this study, we compared VS of sighted and blind people.

Method

We designed a cardboard model of a famous square in Toulouse and the surrounding buildings. 30 subjects (21 blindfolded sighted, 9 blind) who had previous knowledge of the square were asked to spontaneously imagine it (dominant viewpoint). Then they positioned and oriented a figurine in the model, at the location of this dominant viewpoint. We used vector based hierarchical clustering to extract meaningful groups of subjects.

Results

52.4% of the sighted subjects had their viewpoint oriented towards the city hall side, i.e. their mental representation was based on the square geometry. The others had representations attached to the way they usually enter the place, i.e. autobiographical strategies. Two main clusters were identified, one containing 57.1% of the sighted subjects and no blind subjects, another containing 55.6% of the blind subjects and only 4.8% of sighted subjects.

Conclusion

The clustering analysis suggests that VS strongly differ between sighted and blind people. VS of sighted subjects rely on the geometry of the place and strong visual landmarks, whereas blind subjects' VS are mainly based on autobiographical memories linked to navigation.