Fujiao Tang

Mojdeh Lahoori

Hossein Nowamooz

Sandrine Rosin-Paumier

Farimah Masrouri

The performance of a Horizontal Ground Heat Exchanger (HGHE) under the seasonal ground energy storage behavior

A well-known backfill soil was considered to be used as the backfill substitutive material. The hydrothermal properties of the backfill material were estimated in laboratory and then injected in a numerical framework considering the atmosphere-soil-HGHE interaction. Numerical simulations were performed for a HGHE installed in the compacted backfill soil and the local materials. Two heat storage scenarios at three different installation depths were also investigated. The results show that an inlet fluid temperature of 50°C in summer increases highly the system performance (13.7% to 41.4%) while the improvement is less significant (0% to 4.8%) for the ambient inlet temperature scenario. A deeper installation depth increases also the system performance.

Introduction

Shallow geothermal energy is one of the many sources of renewable energy, and it can be easily accessed all around the world [1][2][3]. The temperature of the ground can be exploited during winter using a ground source heat pump for space heating and during summer for cooling needs. To increase the efficiency of shallow geothermal energy the solar energy can be stored during summer to increase the temperature of the ground [4]. Generally, open and closed heat exchangers are available for the exploitation of shallow geothermal energy [5], which are then served as low-potential sources of thermal energy for heat pumps [6,7]. Horizontal Ground Heat Exchanger (HGHE) is one of those closed loop heat exchangers. Compared to Vertical Ground Heat Exchanger (VGHE), it is more cost effective although it requires more installation space [8]. The experimental investigations [9] showed that the thermal performance depends on the depth of HGHE installation. Due to the shallow installation depth (conventionally between 1.0 and 2.0 m) [10,11], HGHE is also more sensitive to the meteorological condition. The results reported by Elminshawy et al. [12] showed that the thermal performance of the horizontal system highly depends on the soil compaction state (water content and density) and air flow rate. By increasing density, the solid particles are better packed into a unit volume and the number of contact points between the particles increases [13]. These contact points provide a larger heat transfer by conduction which causes the temperature variation between the inlet and outlet airflow. These observations are in agreement with the study of Hurtado et al. [14] which investigated the capacity of compacted soil to store thermal energy from the chimney power plant using an analytical model based on a finite volume procedure. They mentioned that the output power energy was increased by 10% when the soil compaction increased from loose to dense level. Since the experimental investigations are time and money consuming, the thermal performance of horizontal heat exchanger loops in soils has been numerically investigated using finite element and finite difference tools in different studies. Normally in these models, the simulation is done by considering a homogeneous soil mass with constant thermal properties and the heat transfer is modeled by conduction using solid particles of soil [15]. However, in unsaturated compacted soils, the thermal properties will change by temperature variations, soil physical and hydraulic properties. Therefore, a comprehensive investigation is a thermo-hydraulic simulation with consideration of the mass transfer by vapor and liquid flows [16][17][18][19]. Asgari et al. [19] showed that the thermal performance of the linear and slinky types of HGHE increases by increasing the number of layers arrangement in the ground. For the spiral type exchangers, the thermal performance did not change with increasing the number of layers. Gan [16] showed that during heat extraction in winter, a deeper positioning of loops is more beneficial. At deeper position, the soil thermal properties are not affected by the daily and seasonally ambient temperature variation. Moreover, this feature has been confirmed by experimental investigation. Boukelia [20] investigated the heat lost in a seasonal storage system in an embankment using HGHE by conducting the coupled thermo-hydraulic numerical simulations with a finite element tool (Code-Bright). The author observed that when the inlet temperature in the HGHE during summer was 50 °C, the temperature of the soil close to the probes reached 38 °C. At the end of the autumn when the thermal extraction season started, the temperature was about 25 °C, therefore, about 13 °C of heat loss has been occurred. Jradi et al. (2017) [15] showed the efficiency of the air source heat pump (ASHP) combined with a solar power system as a basis for seasonal thermal energy storage. They showed also that a huge heat loss occurred after storage seasons. Therefore, to increase the thermal performance of a medium to store thermal energy, the insulation material might be a good option and it can be taken into account in the design stage. Another challenging issue is the consideration of the atmosphere-soil-HGHE interaction in the prediction of the system performance. Tang and Nowamooz [21] proposed a numerical simulation framework to evaluate the HGHE performance in field conditions by considering energy and water balance on the land surface. They showed in their simulations that the consideration of the atmosphere-soil-HGHE interaction underestimates highly the outlet temperature especially for the horizontal systems installed close to the soil surface up to a difference of 48%. The same effect has also been noticed by Zhou et al. [22].

The good capacity of the numerical framework considering the atmosphere-soil-HGHE interaction makes possible to bring some further responses on the backfill soil characteristics rarely studied so far. This point is very crucial for the thermal performance of the horizontal systems. Changing the surface soil may significantly improve the system performance. In this context, this investigation aims to visualize how the soil backfill and its installation depth influence the HGHE performance. Therefore, a compacted backfill soil that its hydrothermal behavior has been experimentally investigated is considered. Then, hydrothermal properties of the compacted soil are estimated and injected in the numerical framework considering the atmosphere-soil-HGHE interaction. The thermal energy storage scenarios are also evaluated in the numerical simulations.

Numerical simulation model 2.1 Physic equations

The primary equations in the numerical simulation model is shown in Table 1.

Table 1. Principal equations of atmosphere-soil-HGHE interaction

Type of interaction

Principal equation Soil surface energy balance [23]- [30] 0

n R H LE G     4 (1 ) ( ) n l s a s R a R R T      ( ) / a p a a s a H C T T r     1 2 2 1 ( / ) p E P E P          24 c LAI h
 for clipped grass or

1.5ln( )

c LAI h  
for other crops Soil surface water balance [31]

r i P W E W    Richard equation for hydraulic transfer is soil   0 p w r w p k H K k H D H t                        Hydrothermal transfer in subsurface soil   () s p s s s s w p w w s s T C C T k T Q t u               Heat transfer in pipe 2 2 f p f f p f D f f wall h f f f f f f T A A C A C u T Ak T f u u Q t d                 int ( ) wall ip f Q h Z T T      Rn is the net radiation heat flux (W.m -2 ), H is the sensible heat flux (W.m -2 ), LE is the latent heat flux (W.m -2 ), G is the ground heat flux (Wm -2 )
, al is the surface albedo, Rs is the shortwave radiation (W.m -2 ), Ra is the incoming longwave radiation (W.m -2 ), εσTs 4 is the outcoming longwave radiation (W.m -2 ), ε is the soil surface emissivity, σ is Stephan-Boltzman constant (Wm -2 K -4 ), Ts and Ta are the soil and the ambiant temperatures (K), ρa is the air density (kgm -3 ), Cp-a is the air specific heat capacity (Jkg -1 K -1 ), ra is the aerodynamic resistance to heat transfer (sm -1 ), P is the rainfall rate (mms -1 ), Ep is the evaporation potential (kgm -2 s -1 or mms -1 ), LAI is the leaf area index, hc is the displacement height is linear to the vegetation height (m), water run off (Wr), actual evaporation (E), and infiltration (Wi), where ρw is the water density (kgm -3 ), ψ is the specific moisture capacity (m -1 ), Hp is the suction head (m), t is the time (s), K is the hydraulic conductivity (ms -1 ), kr is the relative hydraulic conductivity, D is the elevation head (m), Hk is the kinetic head (m), ρs is the soil density (kgm -3 ), Cp-s is the soil heat capacity (Jkg -1 K -1 ), Ts is the soil temperature (°C), Cp-w is the water specific heat capacity (Jkg -1 K -1 ), uw is the water velocity in soil (ms -1 ), Qs is the soil heat source (Wm -3 ), A is the pipe inner cross-sectional area (m 2 ), ρf is the fluid density (kgm -3 ), Cp-f is the fluid specific heat capacity (Jkg -1 K -1 ), Tf is the fluid temperature (°C), uf is the fluid flowing velocity (ms -1 ), kf is the fluid thermal conductivity (Wm -1 K -1 ), fD is the Darcy friction factor, dh is the hydraulic diameter (m) and Qwall is the energy from the surrounding media (Wm -1 ), hint is the film heat transfer coefficient (Wm -2 K -1 ). Z is the pipe inner perimeter (m) and Ti-p is the inner pipe temperature (°C).

Geotechnical condition

We considered that the HGHE system is installed in Alsace region in France in June. The local soil till 1 m of depth (installation depth) around the HGHE is completely replaced by the backfill soil. The backfill soil is frequently used in France [32]. The material was classified as sandy lean clay, CL, according to the Unified Soil Classification System [START_REF]ASTM Standard D2487[END_REF].

Regarding the X-ray diffractograms analysis the compacted soil contains 81% quartz, 7% dolomite, 5% calcite, 5% clayey materials and 3% feldspar. According to the particle-size distribution, almost 20% of the particles of the soil were smaller than 2 µm corresponding to the clay content, and 59 % were higher than 0.05 mm corresponding to the sand content (xs). With a liquid limit (LL) of 27% and a plastic limit (PL) of 21%, the plasticity index (PI) was 6%. The backfill soil is compacted at a water content of 16.3% to reach a dry density of 1.72 Mg/m 3 as a reference state. Fig. 1 shows the variation of the water content with the suction for the compacted soil at its reference state.

Fig. 2 shows the variation of the hydraulic conductivity of the studied material with suction. The hydraulic conductivity was measured in saturated conditions with triaxial device and in the unsaturated state with the Wind method [START_REF] Wind | Capillary conductivity data estimated by a simple method[END_REF].

Model geometry

The studied geometry has a length of 30 m, a width of 12 m and a height of 20 m (Fig. 3). This deep geometry was selected to have no hydrothermal impact of the seasonal metrological condition on the bottom boundary. A slinky-type HGHE with 0.03 m of inner diameter and 0.036 m of outer diameter is installed 1 m below surface, covered with the backfill soil compacted at dry densities of 1.72 Mg.m -3 .

Fig. 3 Geometry and its mesh for the numerical simulations.

Boundary and meteorological condition

The temperature gradient at the bottom boundary is set 0.142 Km -1 [START_REF] Baillieux | [END_REF], and the extra water from the precipitation is drained at the bottom boundary. The groundwater level is set constant at the depth of 7.5 m in the whole year. No hydrothermal flow is imposed on the lateral boundaries.

The meteorological condition corresponds to the local condition [36] with the installation time in June. shortwave radiation fluctuation for one year.

At the site, there is no obvious seasonal fluctuation of cloud cover, wind speed, precipitation and air humidity with time. Therefore, an average cloud cover of 0.41, an average wind speed of 2 m.s -1 , an average monthly precipitation of 55.7 mm, and an average air humidity of 83% are applied in the numerical simulation model to capture the main meteorological condition of the local site.

For the surface water balance, 20% of precipitation run off, and the other 80% participate into evapotranspiration or infiltration.

Initial hydrothermal conditions

An equilibrium method (proposed by Tang & Nowamooz [36]) is used to obtain the initial hydrothermal profiles at its installation time in the end of summer.

Pipe and its carrying fluid

The pipe is a High-Density Polyethylene Pipe (HDPE) with the thermal conductivity of 0.4 W.m -1 .K -1 . Propylene Glycol (PG) with a volume concentration of 25% is selected as the carrying fluid. It has a dynamic viscosity of 0.0055 Pa.s, a density of 1026 kg.m -3 , a thermal conductivity of 0.45 W.m -1 .K -1 and a specific heat capacity of 3974 J.kg -1 .K -1 [37]. The carrying fluid velocity is 0.5 m.s -1 during the operation period.

Heat storage effect on the performance of HGHE installed in backfill soil

In this section, the effect of thermal energy storage during summer on the HGHE performance installed in compacted backfill soil is investigated. The results are compared to the original system with no heat storage (called Nsto scenario in this section). Several installation depths are also tested in the numerical simulations.

Studied scenarios and installation depths

The context of thermal energy storage is increasing the performance of the HGHE by increasing the temperature of ground. Therefore, during summer, a fluid with higher temperature than the ground can circulate through the HGHE to exchange the temperature with surrounding soil. The stored heat is expected to be released during winter. The stored energy during summer season is extracted by a circulating fluid with a temperature of 1°C in the HGHE during winter. The system stops working at the end of Winter.

To store thermal energy in soil during summer season and use it in winter, two different scenarios are investigated in this study (Table 2).

a) First scenario (StoA)

A reservoir of carrying fluid is exposed to exterior temperature and then the carrying fluid circulates in HGHE during summer. Therefore, the inlet temperature in 3 months of summer is the ambient temperature (scenario StoA) as presented in Fig. 4 (temperatures of 0 to 92 days). This system is in relaxation in Autumn (from 92 nd to 183 rd day), therefore no fluid flow will be circulated through the system. When Winter comes (from 183 rd to 274 th day), a fluid flow with inlet temperature of 1°C will be circulated. Again the system is in relaxation in Spring (from 274 rd to 365 th day) (Table 2). Solar panels absorb the solar energy and the energy can be used to heat the subsurface soil in summer while a fluid with a constant inlet temperature is circulating in the HGHE. Therefore, the inlet temperature in 3 months of summer is a constant temperature of 50 °C (Sto50) as presented in Fig. 5. The system works the same way as the ambient temperature storage scenario except that the inlet temperature is 50 °C in Summer season (Table 2). Due to the interaction with ground surface, the stored energy during relaxation seasons is dissipated into the atmosphere. If the HGHE is installed close to the land surface, a higher amount of stored energy can be dissipated. Therefore, three depths of at 1, 1.5 and 2 m beneath land surface are investigated for both scenarios to study the influence of installation depth on the HGHE performance. b) Scenario 2 (Sto50) compared to scenario with no heat storage (Nsto) Fig. 7 shows the outlet temperature for the second storage scenario (Sto50) at three installation depths compared to the outlet temperatures of the original HGHE with no heat storage (Nsto) presented in section 4. The figure shows that the ground temperature is obviously improved in summer, and the deeper the installation depth, the larger difference between the outlet temperatures of the scenario considering and nonconsidering the energy storage in summer.

Conclusion

A well-known backfill soil was used to improve the performance of an HGHE system installed in the east of France. The hydrothermal properties of the backfill soil were first injected in a numerical framework considering the atmosphere-soil-HGHE interaction.

To improve the HGHE performance, two heat storage scenarios at three different installation depths were studied. The results show that an inlet fluid temperature of 50°C in summer increases highly the system performance (13.7 to 41.4%) while the improvement is less (0 4.8%) for the ambient inlet temperature. deeper installation depth increases the total extracted energy (TEE) but increases the installation costs.

Fig. 1 .Fig. 2 :

 12 Fig. 1. SWRC of the studied backfill soil at the reference compaction state (dry density = 1.72 Mg.m -3 )

Fig. 4

 4 Fig. 4 Simplified local meteorological condition: (a) Ambient temperature fluctuation for one year and (b)shortwave radiation fluctuation for one year.

Fig. 5 3 . 2

 532 Fig.5 Operation mode for the HGHE over one year

presented in section 4 .

 4 The figure shows the fluid outlet temperature decreases abruptly with the working of the HGHE. Afterwards, the fluid temperature generally decreases and starts to increase with warmer climate. In addition, the figure shows that outlet temperature increases by depth.

Fig. 6 Fig. 7 Fig. 8

 678 Fig. 6 Outlet temperature comparison of the storage scenario (ambient temperature) and the non-storage scenario for three installation depths a) 1m, b) 1.5m and c) 2m.

Fig. 9

 9 Fig. 9 Comparison between the heat storage scenarios (StoA & Sto50) with non-storage scenario (Nsto) at three different installation depths

Table 2

 2

	: Imposed temperature of inlet fluid
		for StoA and Sto50
	Season	StoA	Scenario	Sto50
	Summer Day 0 to 92	Ambient temperature (Fig. 4)	50 °C
	Autumn Day 92 to 183	relaxation	relaxation
	Winter Day 183 to 274	1 °C		1 °C
	Spring Day 274 to 365	relaxation	relaxation
	b) Second scenario (Sto50)


Alejandro Arbelaez
email: alejandro.arbelaez@inria.fr

Youssef Hamadi
email: youssefh@microsoft.com

Continuous Search in Constraint Programming: An Initial Investigation

 for a recent survey), Continuous Search does not require the disposal of a large set of representative instances to properly train and learn parameters. It only assumes that once the solver runs in a real situation (often called production mode), instances will come over time, and allow for proper offline continuous training. The objective is therefore not to instantly provide good parameters for top performance, but to take advantage of the real situation to train in the background and improve the performances of the system in an incremental manner.

Introduction

In Constraint Programming, properly crafting a constraint model which captures all the constraints of a particular problem is often not enough to ensure acceptable runtime performance. One way to improve efficiency is to use well known tricks like redundant and channeling constraints or to be aware that the constraint solver has a particular global constraint that can do part of the job more efficiently. The problem with these improvements (or tricks) is that they are far from obvious. Indeed, they do not change the solution space of the original model, and for a normal user (with a classical mathematical background), it is difficult to understand why adding redundancy helps.

Because of that, normal users are often left with the tedious task of tuning the search parameters of their constraint solver, and this again, is both time consuming and not necessarily straightforward. Indeed, even if tuning is conceptually simple (try different parameters, pick the best), it requires a set of representative instances in order to properly work. This might be obvious for a constraint programmer, but not for a normal user which could train on instances far different from the ones faced by his application.

In this work, we present the concept of Continuous Search (CS), the objective of which is to allow any user to eventually get top performance from their constraint solver. Unlike previous approaches (see [START_REF] Smith-Miles | Cross-disciplinary perspectives on meta-learning for algorithm selection[END_REF] for a recent survey), Continuous Search does not require the disposal of a large set of representative instances to properly train and learn parameters. It only assumes that once the solver runs in a real situation (often called production mode), instances will come over time, and allow for proper offline continuous training. The objective is therefore not to instantly provide good parameters for top performance, but to take advantage of the 'real' situation to train in the background and improve the performances of the system in an incremental manner.

The Continuous Search paradigm, uses an online learning algorithm to update a prediction function which matches instances features to the most efficient set of parameters for a given instance (e.g. Variable/Value selection algorithms). Since CS can start without offline training, this prediction function might be initially undefined. If this is the case, an instance is solved by running the solver with its default parameters. Once the instance is solved and the solution is given back to the application1 , we start our Continuous Search training. At that point, the instance is reused and the goal is to refine the strategy used to tackle it. This is done by a specific repair-like algorithm which perturbs the strategy to find a new strategy able to solve the problem more efficiently. If such a strategy is found, its parameters are stored with the instance features, and therefore, could be reused to solve similar instances more efficiently.

Technically, this means that there are two different search efforts. The one done to solve the real problem, and the one related to the long term improvement of the constraint solver. We believe that this extra use of computational resources is realistic, since nowadays systems (especially production ones) are almost always on. Moreover, this has to be balanced against the huge computational cost of offline training [START_REF] Xu | Satzilla-07: The design and analysis of an algorithm portfolio for sat[END_REF]. Last, this late adaptation is the only way to face the 'real' instances and even, to adapt to changes on the modeling or to the arrival of a completely new class of problem.

The paper is organized as follows. Background material is presented in Section 2. Section 3 introduces the continuous search paradigm. Section 4 presents experimental results. Finally, before our general conclusion, Section 5 presents related work.

Background

In this section, we briefly introduce definitions and notations used hereafter.

Constraint Satisfaction Problems

Definition 1 A Constraint Satisfaction Problem (CSP) is a triple (X, D, C) where, -X = {X 1 , X 2 , . . . , X n } represents a set of n variables. -D = {D 1 , D 2 , . .

. , D n } represents the set of associated domains, i.e., possible

values for the variables.

-C = {C 1 , C 2 , . . . , C m } represents a finite set of constraints.
Each constraint C i is associated to a set of variables vars(C i ), and is used to restrict the combinations of values between these variables. Similarly, the degree deg(X i ) of a variable is the number of constraints associated to X i and dom(X i ) corresponds to the current domain of X i .

Solving a CSP involves finding a solution, i.e., an assignment of values to variables such as all constraints are satisfied. If a solution exists the problem is stated as satisfiable and unsatisfiable otherwise.

In this paper, we consider four well known variable selection heuristics. mindom selects the variable with the smallest domain [START_REF] Haralick | Increasing tree search efficientcy for constraint satisfaction problems[END_REF], wdeg [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF] selects the variable which is involved in more failed constraints, dom/wdeg [START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF] which selects the variable which minimizes the ratio dom wdeg and impacts [START_REF] Refalo | Impact-based search strategies for constraint programming[END_REF] whose objective is to select the variable-value pair that maximizes the reduction of the remaining search space.

Support Vector Machines

Among the prominent Machine Learning (ML) algorithms are Support Vector Machines (SVM) [START_REF] Cristianini | An Introduction to Support Vector Machines and other kernel-based learning methods[END_REF]. This algorithm is highly used in binary classification due to its statistical learning properties, it determines the separating hyperplane with maximum distance or margin to the closest examples (so-called support vectors) of the training set.

Learning a high quality model depends on the quality of the training set. On the one hand, the description of the examples must enable to discriminate among positive and negative examples; on the other hand, the available examples must enable to accurately localize the frontier between the two classes.

Continuous Search in Constraint Programming

The goal of this paper is to take advantage of real world situations as shown in Figure 1, where instances are presented one at a time. Therefore, in Continuous Search settings we consider two different phases, exploitation (or solving time) and exploration (or learning time). The former tries to solve new instances using the acquired knowledge, and the latter is focused on improving the classification accuracy by means of re-using previously seen instances.

Online Learning

To deal with the continuous search scenario, we follow the same approach as in [START_REF] Arbelaez | Online heuristic selection in constraint programming[END_REF], where the authors propose to use a supervised Machine Learning algorithm to select the most appropriate heuristic at different states (so-called checkpoints) of the search tree. To this end, we characterize CSP instances by means of features (i.e., general information common to all CSPs). Those features are the input of an Online SVM algorithm which selects the best heuristic within the checkpoint window.

The features set is divided into two main categories, static and dynamic. The former intends to distinguish instances from each other (e.g., number of variables, constraints, etc.), while the latter is used to monitor the progress of the search process (e.g., max. number of failures, variable's weight, etc.). For more details about these features see [START_REF] Arbelaez | Online heuristic selection in constraint programming[END_REF].

Our choice of an Online SVM algorithm is motivated by the fact that it does not need to re-train the classifier once a new example arrives. Note that training a classical SVM (so-called batch learning) requires the solution of an optimization problem which is not an ideal situation in Continuous Search.

Experiments

This section describes the experimental validation of the proposed approach. In these experiments we included a collection of 100 nurse-scheduling problems from the MiniZinc3 repository.

Experimental setting

The learning algorithm used in the experimental validation of the proposed approach is a Support Vector Machine with Gaussian kernel; we used the libSVM implementation. All our CSP heuristics (see Section 2.1) are home-made implementations integrated in the Gecode-2.1.1 constraint solver. Two CSP adaptive strategies have been experimented, respectively considering the first 4 and 8 strategies in Table 1. In all cases, the default heuristic is the first one: dom/wdeg for variable selection and min-value for value selection.

The exploration examples are generated by adding minor perturbations to the default execution of heuristics (i.e., executing the default heuristic at each checkpoint). Thus, during the learning time, we ran the last seen instance replacing the default heuristic by another candidate in exactly one checkpoint, this process is repeated for each heuristic in Table 1 for a limited number of checkpoints (10 in this paper). Currently, we are working on a more informative way of selecting the exploration points considering the distance of unlabeled examples to the decision boundary.

All experiments were performed on a 8-machine cluster running Linux Mandriva 2009, all machines have 64 bits and two quad-core 2.33 Ghz with 8 Gb of RAM. A time out of 10 minutes was used for each experiment.

It can be observed in Figure 2 that the dynamic approach is able to solve more instances that its competitors (i.e., the default strategy and a random heuristic selection). However the performance goes down as the number of candidate heuristics increases. The main explanation for this phenomenon relies on the fact that we are not using any sophisticated strategy for breaking ties (i.e., if several heuristics are predicted to outperform the default one we pick one at random). We are currently studying different approaches to breaking ties, selecting the best algorithm using the decision value, exploiting the fact that examples that are far from the classification boundaries are more likely to be correctly predicted.

Related work

In this section, we describe some related work that has been proposed to integrate Machine Learning Algorithms into CSP and related areas such as: SAT and Quantified Boolean Formulas (QBF).

SATzilla [START_REF] Xu | Satzilla-07: The design and analysis of an algorithm portfolio for sat[END_REF] is a well known SAT portfolio solver which is built upon a set of features, in general words SATzilla includes two kinds of features: basic features such as number of variables, number of propagators, etc. and local search features which actually probe the search space in order to estimate the difficulty of each problem-instance. The goal of SATzilla is to learn a runtime predictor using a simple linear regression model.

CPHydra [START_REF] O'mahony | Using casebased reasoning in an algorithm portfolio for constraint solving[END_REF], one of the best constraint solvers in the lastest CSP competition 4 is a portfolio approach based on case-based reasoning. Broadly speaking CPhydra maintains a database with all solved instances (so-called cases). Later on, once a new instance arrives a set of similar cases C is computed and the heuristic that is able to solve the majority of instances in C is selected. The main drawback of this portfolio approach is that due to its high complexity to select the best solver, it is limited to a small number of solvers (in competition settings less than 6 solvers were used).

Our work is related to [START_REF] Samulowitz | Learning to solve qbf[END_REF] in a way that they also apply machine learning techniques to perform on-line combination of heuristics into search tree procedures. Their paper proposes to use a multinomial logistic regression method in order to maximize the probability of predicting the right heuristic at different states of the search procedure. Unfortunately, this work requires an important number of training instances to get enough generalization of the target distribution of problems and does not fulfill all the requirements of the Continuous Search settings.

Conclusion

This paper has presented an introduction to Continuous Search, this new concept includes an online algorithm to adaptively tune a constraint solver. At different states of the search, the instance feature is provided with dynamic information collected by the search engine to dynamically adapt the search strategy of a well known CP solver in order to more efficiently solve the current instance. The results in this paper show that the online approximation to deal with continuous search outperforms a very good default heuristic for solving CSPs.

Fig. 1 .

 1 Fig. 1. Continuous Search scenario

Fig. 2 .

 2 Fig.2. Nurse Scheduling-14 (nsp-14), Note that this data shows the performance of the continuous search approach with a particular ordering of the problem instances

Table 1 .

 1 Candidate heuristics; the default heuristic is the first one.

	ID Variable sel Value Sel ID Variable sel Value sel
	1 dom/wdeg	min	5 dom/deg	min
	2 dom/wdeg	max	6 dom/deg	max
	3	wdeg	min	7 min-dom	min
	4	wdeg	max	8	impacts	-

Since our standpoint is real settings, we consider the full application stack where solvers are not isolated pieces of software called from a command line, but are critically embedded in large and complex applications.

Available at http://www.g12.cs.mu.oz.au/minizinc/download.html

http://www.cril.univ-artois.fr/CPAI08/

Acknowledgements

We would like to thank the anonymous reviews and Michele Sebag for helpful discussions of the integration of Machine Learning and Constraint Programming.


Dialogue systems are a crucial component when robots have to interact with humans in natural language. In order to improve these interactions over time, the system needs to be able to learn from its experience, its mistakes and the user's feedback. This process -fittingly called lifelong learning -is the focus of LIHLITH, an EU project funded by CHIST-ERA.

Artificial Intelligence is a field that is progressing rapidly in many areas, including dialogues with machines and robots. Examples include speaking to a gadget to request simple tasks like turning on the radio or asking for the weather, but also more complex settings where the machine calls a restaurant to make a reservation [1], or where a robot assists customers in a shop. LIHLITH [2] is a project focusing on human-machine dialogues. It aims to improve the self-learning capabilities of an artificial intelligence. More specifically, LIHLITH will devise dialogue systems which learn to improve themselves based on their interactions with humans. Current industrial chatbots are based on rules which need to be hand-crafted carefully for each domain of application. Alternatively, systems based on machine learning use manually annotated data from the domain to train the dialogue system. In both cases, producing rules or training data for each dialogue domain is very time consuming, and limits the quality and widespread adoption of chatbots. In addition, companies need to monitor the performance of the dialogue system after being deployed, and re-engineer it to respond to user needs. Throughout the project, LIHLITH will explore the paradigm of life-long learning in humanmachine dialogue systems with the aim of improving their quality, lowering the cost of maintenance, and reducing efforts for deployment in new domains.

LIHLITH ("Learning to

Main goal: continuous improvement of dialogue systems

The main goal of life-long learning systems [START_REF] Chen | Lifelong Machine Learning[END_REF] is to continue to learn after being deployed. In the case of LIHLITH, the dialogue system will be developed as usual, but it will include machinery to continue to improve its capabilities based on its interaction with users. The key idea is that dialogues will be designed to get feedback from users, while the system will be designed to learn from this continuous feedback. This will allow the system to keep improving during its lifetime, quickly adapting to domain shifts that occur after deployment.

LIHLITH will focus on goal-driven question-answering dialogues, where the user has an information need and the system will try to satisfy this need as it chats with the user. The project has been structured in three research areas: lifelong learning for dialogue; lifelong learning for knowledge induction and question answering; and evaluation of dialogue improvement. All modules will be designed to learn from available feedback using deep learning techniques.

Figure 1 shows, in white boxes, a standard dialogue system. These systems use natural language understanding to process the user input, dialogue management to access the domain knowledge and decide the next utterance, and natural language generation to produce the next utterance of the system.

The lifelong learning module, in blue, is the key innovation of LIHLITH, and will improve all modules as the system interacts with users, updating the domain knowledge accordingly. The project will explore autonomous reconfiguration of dialogue strategies and proactive capabilities to ask the user for new knowledge and for performance feedback. This will be triggered, for instance, when the past reactions have been rejected, when the user interaction is too ambiguous, when the possible answers are too numerous, or if they have too similar confidence scores.

To carry out this research, LIHLITH combines machine learning, knowledge representation and linguistic expertise. The project will build on recent advances in a number of research disciplines, including natural language processing, deep learning, knowledge induction, reinforcement learning and dialogue evaluation, to explore their applicability to lifelong learning.

Links:

[1] https://ai.googleblog.com/2018/05/duplex-ai-system-for-natural-conversation.html [2] http://ixa2.si.ehu.es/lihlith/ [3] http://www.chistera.eu/ Figure 1: Schema of a standard dialogue system in white boxes. The innovative lifelong learning module is able to improve all modules (in blue) based on past interactions and the interaction with the current user, updating the domain knowledge accordingly.

  Interact with Humans by Lifelong Interaction with Humans") is a threeyear high risk / high impact project funded by CHIST-ERA [3] that started in January 2018. Participating partners are researchers from University of the Basque Country (UPV/EHU), Computer Science Laboratory for Mechanics and Engineering Sciences (LIMSI), Université Nationale de l'Éducation à Distance in Spain (UNED), Zurich University of Applied Sciences (ZHAW), and Synapse Développement in France.

  LIHLITH: Improving Communication Skills of Robots Through Lifelong Learning by Eneko Agirre, University of the Basque Country (UPV/EHU), Sarah Marchand, Synapse Développement, France, Sophie Rosset, Computer Science Laboratory for Mechanics and Engineering Sciences (LIMSI), Anselmo Peñas, Université Nationale de l'Éducation à Distance (UNED) and Mark Cieliebak, Zurich University of Applied Sciences (ZHAW)


Nicolas Amat

Bernard Berthomieu

Silvano Dal Zilio

Didier Le Botlan

Polyhedral Reductions for Petri nets

Polyhedral equivalence defines a linear dependence relation (E) between the reachable markings of two nets; where E is a Presburger formula, or a system of linear Diophantine equations. This equivalence, denoted (N 1 , m 1 ) ≡ E (N 2 , m 2 ), preserves enough information in E so that we can rebuild the state space of N 1 knowing only the one of N 2 .

We say that two markings m 1 , m 2 are compatible up-to E, denoted m 1 ≡ E m 2 , when formula E ∧ m 1 ∧ m 2 is satisfiable, with m the conjunction ∧ p∈P p = m(p) (e.g., (p 0 = 5) ∧ (p 1 = 0) ∧ . . . ).

Nets (N 1 , m 1 ) and (N 2 , m 2 ) are E-equivalent when:

(A1) E ∧ m is satisfiable for all markings m in R(N 1 , m 1 ) or R(N 2 , m 2 ); (A2) initial markings are compatible: m 1 ≡ E m 2 ; (A3) assume m ′ 1 , m ′ 2 are markings of N 1 , N 2 , such that m ′ 1 ≡ E m ′ 2 , then m ′ 1 is reachable iff m ′ 2 is reachable. Lemma (Reachability Checking). Given m ′ 2 reachable in N 2 then m ′ 1 ≡ E m ′ 2 implies m ′ 1 ∈ R(N 1 , m 1 ). m 1 m ′ 1 σ m 2 m ′ 2 m 1 ≡ E m 2 ∀m ′ 1 . m ′ 1 ≡ E m ′ 2 σ Lemma (Invariance Checking). For all m ′ 1 in R(N 1 , m 1 ) there is m ′ 2 in R(N 2 , m 2 ) such that m ′ 1 ≡ E m ′ 2 . m 1 m ′ 1 σ m 2 m ′ 2 m 1 ≡ E m 2 ∃m ′ 2 . m ′ 1 ≡ E m ′ 2 σ

Counting using SDD

$ sift AirplaneLD-PT-0050.pnml 4471223 marking(s), 19756224 transitions(s) 67.569s

$ tedd -q AirplaneLD-PT-0050.pnml 4471223 state(s) 2.691s

$ tedd -q AirplaneLD-PT-4000.pnml 2.1773922960e12 state(s) 33.574s

$ tedd -rg,redundant,compact AirplaneLD-PT-4000.pnml 2.1773922960e12 state(s) 0.000s

Reachability using SMT

To

check if property F 1 is reachable in N 1 , it is enough to check its E-transform, F 2 , on N 2 . F 2 (y) ≜ ∃x . Ẽ(x, y) ∧ F 1 (x)
We

Polyhedral reductions

We can compute instances of polyhedral equivalences using structural reductions. Token Flow Graph

# R ⊢ p5 = p4 # A ⊢ a1 = p2 + p1 # A ⊢ a2 = p4 + p3 # R ⊢ a1 = a2 p 0 p 6 a 2 a 1 p 3 p 4 p 1 p 2 p 5
Some examples

5 p 0 p 1 p 2 p 3 p 4 p 5 4 p 6 t 0 t 1 t 2 t 3 t 4 ≡ E t 5 a 2 t 7 4 p 6 t 6 5 p 0 E ≜ (p 5 = p 4 ) ∧ (a 1 = p 1 + p 2 ) ∧ (a 2 = 3 + p 4 ) ∧ (a 1 = a 2 )
k 3 Bags k 1 Cabins k 2 Out Entered E ≜               Cabins + Dress + Dressed + U ndress + W aitBag = k 1 Dress + Dressed + Entered + InBath + Out + U ndress + W aitBag = k 2 Bags + Dress + InBath + U ndress = k 3

Automatic equivalence checking

The problem of checking whether two nets are equivalent is undecidable. But we have implemented a sound, complete procedure in the case of equivalence between parametric nets: (N 1 , C 1 ) ≊ E (N 2 , C 2 ).

LAAS-CNRS

  use this property in a SMT-based modelchecker with structural reductions. It supports generalized reachability formulas of the form: AG ((p 1 + p 3 ⩾ 5) ∨ (p 0 < p 4 )) $ python3 -m smpt -n SmallOpSys-MT0016.pnml --methods BMC K-INDUCTION PDR-REACH STATE-EQUATION --show-time --show-techniques ... FORMULA RC4 FALSE TECHNIQUES ... BMC TIME 0.04s $ python3 -m smpt -n SmallOpSys-MT2048.pnml ... timeout $ same with option --auto-reduce or --mcc # Reduction time (Full): 0.11s FORMULA RC4 FALSE TIME 0.05s $ or with options --project --show-projection # Reduction time (TFG): 0.09s # Reduction ratio (TFG) 44% # Projection of RC4: [] -(1 ⩽ p 0 + p 2 + a 2 ) ∧ . . . query (s) Original Projected r ∈ [0.01, 0.5[ r ∈ [0.5, 1] k-induction with and without reductions

/

  Laboratoire d'analyse et d'architecture des systèmes du u c t r o n

  E ≜ (p 1 = p 4 + 8) ∧ (p 6 = p 0 p 2 + p 3 + p 5 + p 7 )∧ (a 1 = p 7 + 8 ) ∧ (a 2 = a 1 + p 5 )

	SmallOperatingSystem-PT-MT0016DC0008
	p 0			p 1			p 0
	16	t 0		16	t 1		16	t 0	t 1
	p 2					p 3	p 2		p 3
				p 4					p 4
		t 2	p 5	8	t 3	≡ E		t 2	8	t 3
	t 4		16	p 6	t 5	p 7	t 4	a 2
		t 6
			p 8		t 7
			SwimmingPool (fully reduced)
		W aitBag	U ndress	InBath			Dressed