Elliot Brendel
email: brendel@ensta.fr

Julien Alexandre
email: alexandre@ensta.fr

Dit Sandretto

Alexandre Chapoutot
email: chapoutot@ensta.fr

Robust Motion Planning Based on Sliding Horizon and Validated Simulation *

A new algorithm of motion planning based on set-membership approach and inspired by optimal control methods is presented. The goal of this algorithm is to find a safe and optimal path taking into account various sources of uncertainties on the dynamical model of the plant, on the model of the environment, while being robust with respect to the numerical approximations introduced by numerical integration methods. The main approach is based on sliding horizon method in order to predict the behavior of the plant allowing the computation of an optimal path. As an example, the motion planning algorithm is applied on an Autonomous Underwater Vehicle (AUV) case study, showing the benefit of the proposed approach.

Introduction

Motion planning algorithms are a center piece in the control framework of mobile robots as they contribute to give them the ability of have autonomous behaviors. Furthermore, such class of algorithms is critical as a failure can cause the abort of the mission or can cause important amount of damage such as human loss. The validation of such algorithms is then mandatory in order to increase the confidence of the end users. However, those algorithms are also subject to constraints, e.g., to reduce fuel consumption. In consequence, computing a safe path is usually not enough, an optimal one is search to minimize some costs.

Moreover, one of the challenge in order to design robust and reliable motion planning algorithms is to take into account various sources of uncertainties. For example, the environment is not exactly know and some disturbance should have been considered. Mathematical models of the mobile robots are not perfect and usually come from some simplification in order to have efficient simulation activities. Lastly, computeraided design usually produces approximated results as it is based on numerical methods which cannot produce close form solution of a problems, e.g., the solution of an initial value problem for ordinary differential equations. The set-membership framework is suitable to deal with such kinds of uncertainties.

Contributions

The main contribution of this article is the combination of set-membership methods with optimizing approach. Hence, a correct-by-construction algorithm is defined with the intrinsic properties to be robust to uncertainties as it relies on setmembership approach [START_REF] Jaulin | Applied Interval Analysis[END_REF]. Moreover, embedding the motion planning problem into a constraint satisfaction problems (CSP) [START_REF] Rueher | Solving continuous constraint systems[END_REF], and more precisely into a global optimization framework [START_REF] Hansen | Global Optimization Using Interval Analysis[END_REF], the proposed algorithm produces an optimal free-collision paths with respect to a given cost function which is minimized.

Related Work

Motion planning is an active research area in Robotics and many methods have been developed. Artificial potential fields has been used in motion planning problems such as in [START_REF] Bemporad | Local incremental planning for a carlike robot navigating among obstacles[END_REF] but without producing optimal path. A popular approach is to use stochastic sampling to discretize the configuration space, e.g., the Rapidlyexploring Random Trees (RRT) [START_REF] Lavalle | Rapidly-exploring random trees: Progress and prospects[END_REF] path planning algorithm and its many variants. The (asymptotic) optimality of the solution is provided by the optimal Rapidly-exploring Random Trees (RRT*) first proposed in [START_REF] Karaman | Optimal kinodynamic motion planning using incremental sampling-based methods[END_REF]. Other methods based on receding horizon approach have also been considered to produce optimal collision-free paths. For example, [START_REF] José | Multi-robot motion planning: a modified receding horizon approach for reaching goal states[END_REF] uses receding horizon in context of multi-robot or [START_REF] Wongpiromsarn | Receding horizon temporal logic planning[END_REF] considers complex mission described by temporal logic. While all these methods are efficient to produce collision-free paths, they usually did not take into account uncertainties and so the robustness of the solution is not guaranteed.

Uncertainty in motion planning has been considered mainly based on two representations: set-membership [START_REF] Page | Robot motion planning for sensor-based control with uncertainties[END_REF][START_REF] Pepy | Reliable robust path planning with application to mobile robots[END_REF] or covariance matrices [START_REF] Lambert | Safe path planning in an uncertain-configuration space[END_REF][START_REF] Censi | A bayesian framework for optimal motion planning with uncertainty[END_REF]. While the latter is able to find paths with a collision probability under a given threshold, set-membership approaches can guarantee safe trajectories under a bounded noise assumption. In [START_REF] Pepy | Reliable robust path planning with application to mobile robots[END_REF] is introduced a preliminary conceptual reliable and robust path planner based on RRT principles and solved in an set-membership framework where all uncertainties are considered bounded. Interval analysis principle along with graph algorithms were previously used [START_REF] Jaulin | Path planning using intervals and graphs[END_REF] to find a collision-free shortest path for a polygonal rigid object in a given configuration with obstacles. Nevertheless, theses approaches builds robust and safe paths but usually cannot produce optimal paths. Contents The paper is organized as follows. Some preliminary notions on motion planning problem, set-membership methods and sliding horizon method are introduced in Section 2. The main contribution of the paper is presented in Section 3 by formulated the problem and the presentation of the algorithms. In Section 4 a case study focus on AUV is described showing the relevance of the proposed approach. Conclusion and perspective are drawn in Section 5

Preliminary notions

In this section, the main notions useful for our approach to solve the robust motion planning problem are introduced.

Dynamics of a vehicle

The dynamics of a vehicle, such as a car, a flight or a ship, can be modelized by differential equations to analyze its behavior. In the special case of autonomous vehicles -Unmanned Aerial Vehicle (UAV), Autonomous Underwater Vehicle (AUV) or Unmanned Ground Vehicle (UGV) -the dynamical modeling is very important to define the controller and the path planner. In this paper, it is assumed that the dynamics is modeled by nonlinear ordinary differential equations as the ones coming from the Newton's laws.

Starting from a given point at time zero, an initial value problem is defined by:

ẏ(t) = f (t, y(t), u(t)), with y(0) = y 0 . (1)
In [START_REF] Alexandre | Validated Explicit and Implicit Runge-Kutta Methods[END_REF], y(t) ∈ R n and u(t) ∈ R m denote the vector of states and inputs, respectively.

Motion planning

A motion planning consists on producing a continuous path in the configuration space, that satisfies system dynamics (movement constraints), safety constraints (obstacles), inputs limitations, and possibly optimizes a cost linked to a given aspect of movement.

In a more enriched motion planning, the considered constraints can take into account the quality of ground, ocean stream, up-draft, seabed shape, etc. These constraints can be considered in connection with the task and/or the sensors. A cost function are often added. This latter, linked to states of the system (and not linked to inputs) can be a distance expressed in the configuration space or a more complex functional cost involving state and/or state derivatives.

Uncertainties and Validated Simulation

The simplest and most common way to represent and manipulate sets of values is interval arithmetic (see [START_REF] Moore | Interval Analysis[END_REF]). An interval

[x i ] = [x i , x i ] defines the set of reals x i such that x i ≤ x i ≤ x i .
IR denotes the set of all intervals over reals.

Interval arithmetic extends to IR elementary functions over R. For instance, the interval sum, i.e., [

x 1 ] + [x 2 ] = [x 1 + x 2 , x 1 + x 2 ]
, encloses the image of the sum function over its arguments. An interval vector or a box [x] ∈ IR n , is a Cartesian product of n intervals.

Validated numerical integration methods are interval counterpart of numerical integration methods. A validated numerical integration of a differential equation, as defined in (1) assuming piece-wise constant input, consists in a discretization of time, such that t 0 • • • t end , and a computation of enclosures of the set of states of the system y 0 , . . . , y end , by the help of a guaranteed integration scheme. In details, a guaranteed integration scheme is made of • an integration method Φ( f , y j ,t j , h), starting from an initial value y j at time t j and a finite time horizon h (the step-size), producing an approximation y j+1 at time t j+1 = t j +h, of the exact solution y(t j+1 ; y j ), i.e., y(t j+1 ; y j ) ≈ Φ( f , y j ,t j , h);

• a truncation error function lte Φ ( f , y j ,t j , h), such that y(t j+1 ; y j ) = Φ( f , y j ,t j , h)+ lte Φ ( f , y j ,t j , h).

A validated numerical integration method is a two step method starting at time t j and for which i) it computes an enclosure [ỹ j ] of the solution of (1) over the time interval [t j ,t j+1 ] to bound lte Φ ( f , y j ,t j , h); ii) it computes a tight enclosure of the solution of (1) for the particular time instant t j+1 . There are many methods for these two steps among Taylor series and Runge-Kutta methods see [START_REF] Nedialko | Validated solutions of initial value problems for ordinary differential equations[END_REF][START_REF] Alexandre | Validated Explicit and Implicit Runge-Kutta Methods[END_REF] and the references therein for more details.

As a result, validated numerical integration methods produce two functions depending on time

R : R → IR n t → [y] (2)
with for a given t i , R(t i ) = {y(t i ; y 0 ) : ∀y 0 ∈ [y 0 ]} ⊆ [y], and R :

IR → IR n [t,t] → [ỹ] (3)
with R([t,t]) = {y(t; y 0 ) :

∀y 0 ∈ [y 0 ] ∧ ∀t ∈ [t,t]} ⊆ [ỹ].
In [START_REF] Sandretto | Formal verification of robotic behaviors in presence of bounded uncertainties[END_REF], validated numerical integration has been combined with CSP tools. Indeed, functions R() and R() are abstracted, but guaranteed, solutions of (1). Therefore, the process of validated simulation, mixed with constraint programming and abstraction of time functions provides an efficient tool for the prediction of the system evolution.

Sliding Horizon Method

A sliding, or receding, horizon-based method is used when the future cannot be anticipated, such as in a moving environment or a progressively discovered environment.

In the proposed method, the predicted horizon needs to be prolonged, but long term validated simulations are difficult to obtain. A sliding horizon approach is then interesting to progressively discover the environment and by the way reducing the duration of the simulations. A sliding horizon based motion planning is then close to Model Predictive Control. The main difference is the desired result: MPC is a control synthesis, then it produces solutions in the input space (with cost on inputs), while motion planning is a path planner, then it produces solutions in the state space (with cost on states).

A sliding horizon-based method consists on computing a value (an optimal control or a path) from a time t 0 for a period T 0 (as long as possible) in order to anticipate the future, i.e., the horizon, injecting this value in the system, and re-computing this value at time t 1 , with t 0 + t 1 < T 0 , for a new horizon period T 1 (T 1 may be equal to T 0 ). The initial condition of the problem on t 1 is the state of the system evaluated or measured (in the case of control synthesis) at t 1 .

Robust and Guaranteed Motion Planning Based on

Sliding Horizon

Problem Formulation

A dynamical system as defined in [START_REF] Alexandre | Validated Explicit and Implicit Runge-Kutta Methods[END_REF], where y is the state and u is the control, is considered. Then a constraint function h : y → h(y) and a cost function g : y → g(y) are defined, constraints coming from safety and cost from task for example. Thus, the problem is to find the control u which is the solution of (P) :

   min u g(y) ẏ = f (y, u) h(y) < 0 .

Complete Approach

The robust and guaranteed motion planning using sliding horizon proposed in this paper is defined by the steps:

1. a control u 1 solution of (P) on a time span [0, T ], with T the prediction period, and from the initial state y 0 , is computed;

2. a simulation on a time span [0, T ], with T the sliding period (T < T ), and from the initial state y 0 , is performed. It provides the trajectory y 1 (t) driven by the input u 1 ;

3. a control u 2 solution of (P) on a time span [T , T + T ], and from the initial state y 1 (T ), is computed;

4. as in the second step, a simulation on a time span [T , 2T ], and from the initial state y 1 (T ) is performed. It provides the trajectory y 2 (t) driven by the input u 2 ;

5. these steps are repeated until a user defined number of steps is reached.

At

Step i, to find the control u i , we browse through the set of the controls, assuming that its finite, until the control whose corresponding y(t) satisfies the constraint h(y(t)) < 0 and minimizes the cost g(y(t)), ∀t ∈ [(i -1)T , iT ] is found.

Algorithms

The method is divided in two algorithms, the main one (see Algorithm 1) is the global procedure handling the sliding horizon progress. The second one (see Algorithm 2) solves the problem (P). A third algorithm (see Algorithm 3) which improved the second one is given.

Main Algorithm

Algorithm 1 Sliding horizon Require: y 0 , T , T , n step , f , h, g, D for i ∈ [[0, n step -1]] do u optim ←find u (y 0 , T, f , h, g, D) y(t) ←simulation f , y 0 , u optim , T y 0 ←-y(T ) Path.push back(y(t)) end for Ensure: Path In Algorithm 1, n step is the iteration number of the algorithm and y 0 is the initial state for an iteration. h and g are the constraint function and the cost function, respectively. T and T are the same than given in Section 3.2 and D is the set of inputs which is assumed to be finite. The function find u solves our problem (P) (and is given in Algorithm 2). The simulation method returns a list of boxes that contains the solution of ẏ = f (y, u) for a given u in a guaranteed way using validated simulation method (see Section 2.3). Path is the list of trajectories from the initial state driven by the inputs found for every iteration of the algorithm. ous one (the first break statement). Then we can iterate on the second dimension of the control (u 2 ) to find a possible new couple u temp , s temp . The second break statement is reached when there has not been any other tube containing a possible more optimal solution, then we skip all the iterations until the last statement u optim ←-u temp . With the parameters described in Section 4.3.1, solving the motion planning problem requires 2702 simulations with the improved Algorithm 3 instead of 3557 with Algorithm 2.

Discussion

Results of the presented method are given in term of depth w.r.t. time in Figure 2. The depth is computed with seabed(x, y). The path provided by the motion planning method for the seabeds 1, 3 and 4 allows the AUV to follow the seabed remaining between a distance d min and d max from it. As shown in Figure 2 top right, the execution for the second seabed failed after 9 steps, because of the variations of the seabed (a deep ditch and then a climb). In this picture, after t = 135 seconds, a simulation is done with the entire interval of inputs u = [-0.3, 0.3] 2 , and no solution can be found without collision with the seabed. This phenomenon is due to the fact that the dive velocity of the AUV is high at the moment when the seabed grows quickly.

A solution to this failure of the algorithm could be obtained by increasing T and decreasing T in order to see the obstacle sooner but with a longer computation time (see Figure 3). An other solution is to add a constraint to the problem, for example we bounded lb (ż) -0.03 m.s -1 and the algorithm achieved to find a path across the seabed (see Figure 4). Indeed, it succeeds by avoiding the gap and reaching the optimal depth further.

Conclusion and Future Work

In this paper, we proposed a validated algorithm to solve a motion planning problem, considering constraints and cost on states. Our approach showed its efficiency in an application of motion planning for an Autonomous Underwater Vehicle. An improvement exploiting set membership is used to avoid some tests on inputs which reduces significantly the number of simulations. The presented approach can in some case fail because of its dependency to many parameters that the user has to calibrate.

As a future work, a procedure to dynamically choose the parameters such as prediction period or additional constraints on system behavior could be considered, w.r.t. a prediction of the seabed for example.

Figure 2 :

 2 Figure 2: Results of the AUV motion planning with seabed 1 to 4 from top left to bottom right.

Figure 3 :

 3 Figure 3: Result for the seabed 2 with longer prediction period.

Figure 4 :

 4 Figure 4: Result for the seabed 2 with additional constraint on diving speed.

http://perso.ensta-paristech.fr/ ˜chapoutot/dynibex/

In order to find a control which is solution of (P), a discretization of the set of the controls is performed, and the one which minimizes g while satisfying the constraint h is returned. In Algorithm 2, D is a finite set of control inputs, u temp is the previous Algorithm 2 find u function Require: y 0 , T , f , h, g, D c ←-+∞ for u ∈ D do y(t) ←simulation( f , y 0 , u, T ) if g(y(T )) < c and h(y(t)) < 0, ∀t ∈ [0, T ] then u temp ←-u c ←g(y(T )) end if end for u optim ←-u temp Ensure: Optimal control u optim validated control, and c is the cost corresponding to u temp . The result is given in term of the "optimal control" u optim , which is proven to drive the system to the optimal and safe trajectory, while being easier to save in memory.

Improvement of Algorithm 2

Algorithm 3 Improvement of Algorithm 2: find u function

In this part, an improvement of the previous algorithm using the set-membership approach is proposed. For each control u found, considering that D is the set of the remaining untested controls, a simulation on all the set D can be performed by the help of validated numerical integration methods (see Section 2.3). We denote by y D (t) the obtained trajectories. If c g (y D (T )), we ensured that the previous validated control u is optimal and no more iteration over D is needed.

Motion Planning For an AUV

The motion planning of an AUV which has to move the closest to the seabed is considered. In consequence, the cost function is the depth of the gravity center of the AUV. As security constraints, we want to ensure that the AUV is closer to the seabed than the distance d max and further than d min .

Dynamics of an AUV

The gravity center of the AUV is subjected to the ODE defined in [START_REF] Jaulin | Mobile Robotics[END_REF] and given in Equation ( 4).

where s = (x, y, z, ψ, θ , ϕ) is the state vector which can be split into the vector (x, y, z) of the coordinates of the gravity center and the vector (ψ, θ , ϕ) of the Euler angles; u = (u 1 , u 2 ) is the control input vector; v is the velocity.

Note that (4) has been simplified by substituting tan θ by θ in the definition of φ to avoid technical issues of the implementation. Nonetheless, the algorithm remains valid.

Underwater environment

We define a function (x, y) → seabed (x, y) which returns the depth of the seabed at the coordinates (x, y). We also define d min and d max two constants such that the AUV stays at a distance to the seabed between d min and d max . Some constraints on AUV angles are considered: yaw and roll are bounded in an interval (to go in a quite straight way and to not capsize) and pitch is bounded by an extreme value (to limit the dive angle). Finally, in order to force the AUV to move forward through the x dimension, we impose x end > x init . Thus, the problem is to find the control u solution of

Experiments

Settings of the experiments

The seabed function is defined by

Then the following seabeds are considered

• seabed 1: (x, y) → seabed x-30 20 , y 2 -100;

• seabed 2: (x, y) → seabed y 2 , x-30

20

-100;

• seabed 3: (x, y) → seabed -x+30 20 , y 2 -100;

• seabed 4: (x, y) → seabed y 2 , -x+30 20 , y 2 -100. Each seabed is a rotation of the first one (see Figure 1).

The limits on depth are defined such that d min = 1 meter d max = 10 meters. The velocity v is fixed to 0.1 m.s and the initial state s 0 to (0, 0, -92, 0.1, 0.1, 0.1). As discretization of the set of the controls, we choose such that

Finally, the prediction and sliding periods are T = 30 s and T = 15 s, for a total number of steps n step of 35.

Implementation of the find u function

The presented method has been implemented in the DynIBEX framework 1 . It proposes a validated simulation procedure based on Runge-Kutta methods and provides some differential constraint programming facilities [START_REF] Sandretto | Formal verification of robotic behaviors in presence of bounded uncertainties[END_REF]. Every simulation has been Algorithm 4 find u function for an AUV Require: [START_REF] Sandretto | Formal verification of robotic behaviors in presence of bounded uncertainties[END_REF] if lb (z u ) < lb(c) and h(simu u) < 0 then u temp ←-u; s temp ←-s; c ←z u end if end for end for u optim ←-u temp Ensure: Optimal control u optim computed using Heun's method with a 10 -4 precision which is a good trade-off between speed and precision of the results.

Algorithm 4 is an adaptation of the generic Algorithm 3 to the specific problem of the AUV described above and to the dedicated implementation. Some operators coming from DynIBEX are used: lb([x]) stands for the lower bound of interval [x], [x].is empty() corresponds to the test of empty interval, simu u is the result of a validated numerical simulation method (it contains R() and R() abstractions), in particular simu u.get last() returns R(T ).

Instead of considering all the elements of the set D = -0.3 + 0.6k 9 : k ∈ [[0, 9]] × -0.3 + 0.6k 9 : k ∈ [[0, 9]] , interval based approach allows us to fix one dimension (here u 1 ) and to compute the tube of the solutions of (4) for u 2 = [-0.3, 0.3]. If this computed tube is less optimal than the previous validated solution u temp , s temp , we skip to the next u 1 until we reach a tube that may contain more optimal solutions than the previ-


Yasser Fadlallah
email: y.fadlallah@usal.edu.lb

Member, IEEE Antonia Maria Tulino
email: antoniamaria.tulino@unina.it

Fellow, IEEE Dario Barone

Student Member, IEEE Giuseppe Vettigli

Student Member, IEEE Jaime Llorca
email: jaime.llorca@nokia.com

Member, IEEE Jean-Marie Gorce

Coding for Caching in 5G Networks

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

Along with the internet revolution, IP traffic is growing at a tremendous pace and it is expected to reach two zettabytes per year by 2019. Mobile data networks are envisioned to support up to 14% of this global data traffic coming from a plethora of different market segments. Among these segments, multimedia streaming is the service with the highest penetration rate, having the major impact on the overall traffic increase. On the other hand, current mobile network generations cannot cope with this explosive traffic growth due to the capacity limitations of radio access, backhaul, and core mobile networks, and the increasingly unicast and on-demand nature of users' content demands. In order to support this traffic expansion, the fifth generation (5G) of mobile networks is under March 21, 2017 DRAFT preparation. Among the key performance challenges that 5G needs to address are: throughput, latency, and energy efficiency. That is, 5G is expected to provide 1000x higher throughput, sub-millisecond service latencies, and up to 90 percent overall energy savings [START_REF] Osseiran | Scenarios for 5G mobile and wireless communications: the vision of the METIS project[END_REF]. Despite the myriad of technological advances at the physical (PHY) and medium access control (MAC) layers (e.g., inter-cell interference coordination (ICIC), massive multiple-inputmultiple-output (MIMO), carrier aggregation), targeted data rates are still significantly out of reach. To this end, 5G envisions novel architectural components for the next generation radio access network (RAN), including small cell densification, efficient wireless backhauling, and network self-organization [START_REF] Osseiran | Scenarios for 5G mobile and wireless communications: the vision of the METIS project[END_REF]. In this context, the use of inexpensive storage resources within the RAN is emerging as a promising approach to reduce network load, and effectively increase network capacity.

A. Prominence of Wireless Caching in 5G

Wireless caching, i.e., caching content within the wireless access network is gaining interest, specially in ultradense networks where many connected devices try to access various network services under latency, energy efficiency, and/or bandwidth limitation constraints [START_REF] Osseiran | Scenarios for 5G mobile and wireless communications: the vision of the METIS project[END_REF]. Proactively caching content items at the network edge (e.g., at the RAN) helps in relieving backhaul congestion and meeting peak traffic demands with lower service latency as Fig. 1 illustrates. For maximum benefits, network operators can intelligently exploit users' context information, classify content by popularity, and improve predictability of future demands to proactively cache the most popular content before being requested by end users. Such a strategy is able to fulfill the quality of service (QoS) requirements while significantly reducing the use of bandwidth resources and its associated energy consumption. Content items can be cached at different locations of the mobile network. Within the RAN, base stations (or small base stations), user equipment (UE) devices, and access points (AP) can be enhanced with additional memory for content caching.

While caching can also happen within the evolved packet core (EPC), the main benefit of caching at the EPC is to reduce peering traffic between internet service providers (ISP). It is the additional deployment of cache memories within the RAN that can crucially help minimizing intra-ISP traffic, relieving backhaul load, and reducing service latencies [START_REF] Wang | Cache in the air: exploiting content caching and delivery techniques for 5G systems[END_REF].

B. From Uncoded to Coded Content Distribution

A substantial amount of recent studies have analyzed the use of wireless caching as a promising solution for 5G. Among these studies, [START_REF] Golrezaei | Femtocaching: Wireless video content delivery through distributed caching helpers[END_REF] introduced the idea of femtocaching and addressed the question of which files should be assigned to which helper nodes (femtocell-like base stations), while [4, and reference therein] considered the improvement in caching efficiency that can be obtained by dynamically learning content popularity and updating cache contents at the network edge. Despite considerable interest, such studies focus on the data placement problem in isolation, assuming the use of unicasting or naive (uncoded) 1 multicasting during transmission, and hence ignoring the potential benefits of joint placement and transmission code design. 1 The term uncoded is used to refer to a scheme in which, at each use of the channel, the transmission is composed of packets that belong to the same file, while the term coded refers to a scheme in which transmissions can be composed of a mixture of packets from different files.

March 21, 2017 DRAFT

In [START_REF] Llorca | Network-coded caching-aided multicast for efficient content delivery[END_REF], the data placement problem is generalized to the coded content distribution problem where the goal is to jointly determine the placement and routing of (possibly coded) information over the network, showing that joint code design significantly increases multicast efficiency, leading to substantial improvements in reducing network load and access latencies. A number of information-theoretic studies have then characterized the order-optimal performance of a caching network of special practical interest, the shared link caching network, formed by a single source node (e.g., base station) with access to a library of content files connected via a shared multicast link to multiple user nodes (e.g., end devices or access points), each with caching capabilities. In this context, the work in [START_REF] Maddah-Ali | Decentralized coded caching attains order-optimal memory-rate tradeoff[END_REF] showed that under worst-case demands, caching portions of each file uniformly at random and using index coding (IC) [START_REF] Blasiak | Index coding via linear programming[END_REF] during transmission yields an overall load reduction that is proportional to the aggregate cache size.

In [START_REF] Ji | Order-optimal rate of caching and coded multicasting with random demands[END_REF], the authors analyzed the case in which user demands follow a Zipf popularity distribution, designing orderoptimal achievable schemes 2 that adjust the caching distribution as a function of the system parameters to balance the gains from local cache hits and coded multicasting. Shortly after, [START_REF] Shanmugam | Finite Length Analysis of Caching-Aided Coded Multicasting[END_REF] showed that the gains achieved by these schemes require a number of packets per requested item that grows exponentially with the number of caches in the system, leading to codes of exponential complexity that compromise their theoretical gains. Efficient polynomialtime schemes (e.g., [START_REF] Vettigli | An efficient coded multicasting scheme preserving the multiplicative caching gain[END_REF]) have then been proposed to recover a significant part of the promising multiplicative caching gain.

In terms of practical implementations, the work in [START_REF] Zeydan | Big data caching for networking: Moving from cloud to edge[END_REF] provided a big data platform where learning algorithms can be used to predict content popularity and drive caching decisions, but the benefit of the learning techniques on improving caching efficiency is evaluated via numerical simulations. In addition, only conventional uncoded schemes are considered, and aspects related to advanced coding techniques such as caching-aided coded multicasting that can potentially provide much larger gains are largely overlooked. It is also important to note that, so far, only information-theoretic studies have shown the potential gains of such schemes, and the emulation work in [START_REF] Niesen | Coded caching for delay-sensitive content[END_REF] only considers 2-4 users and 3 files, a very limited scenario that does not allow showing the real impact of computational complexity and coding overhead. Moreover, it is unclear whether existing schemes meet the requirements of current technologies, thus leaving plenty of open questions regarding practical performance benefits.

C. The Need for Experimental Validation

This article aims at bridging the gap between theory and practice in order to validate the benefits of caching-aided coded multicasting by designing a fully working prototype implementation and testing it in a large network testbed.

Such testbed and prototype implementation provide a cornerstone for the evaluation of future schemes with more advanced wireless caching protocols and cache-enabled PHY layer techniques such as joint source-channel coding.

We first provide an overview of the caching and coded multicasting framework and discuss the key concepts behind the ability to provide load reductions that are proportional to the aggregate cache size. We then introduce a new frame structure that includes specific fields to account for all the practical aspects required for a fully working real-world 2 An achievable scheme is said to be order-optimal if, as the file size goes to infinity, the number of transmissions needed to satisfy the user demands scales as the information theoretic optimal number of transmissions needed to satisfy the user demands; i.e the ratio between the achievable and optimal number of transmissions is upper bounded by a constant independent of all the system parameters.

March 21, 2017 DRAFT implementation. The primary role of the newly designed frame structure is to allow decoding of coded data at each receiver. Our MAC layer frame design is combined with an orthogonal frequency division multiplexing (OFDM) PHY layer, which makes it compatible with long term evolution (LTE) advanced mobile networks or further PHY layer standards. The resulting fully working prototype is implemented in a large-scale testbed facility, CorteXlab [START_REF] Cardoso | CorteXlab: A facility for testing cognitive radio networks in a reproducible environment[END_REF], composed of tens of highly flexible radio nodes deployed in a controlled and reproducible environment. We present experimental results in the context of key 5G challenges related to transmission delay, bandwidth usage, and energy efficiency. Our experimentation validates the fact that memory can be effectively turned into bandwidth leading to substantial network throughput gains.

II. CACHING-AIDED CODED MULTICASTING

As previously stated, the use of caching together with smart offloading strategies in a RAN composed of evolved NodeBs (eNBs), AP (e.g., WiFi), and UEs, can significantly reduce the backhaul traffic and service latency. In this context, a shared link caching network (SLCN) topology can be identified at different levels of the mobile network.

Indeed, a radio cell constitutes a SLCN where the eNB acts as the source node connected to the UEs via a shared multicast link. In addition, a SLCN can also be formed by a core network (CN) server (source node) connected to a set of eNBS via a shared wireless backhaul. In both cases, user nodes are equipped with storage resources for content caching. Accordingly, we focus on the analysis and implementation of a SLCN composed of a source node, with access to a library F of m binary files, connected to n user nodes via a shared multicast link. Each user node is equipped with a cache of storage capacity equivalent to M files, and can make up to L file requests according to a Zipf demand distribution. A multicast link is a shared channel in which any transmission can be overheard by all receivers.

A caching-aided coded multicast scheme is performed over two phases: i) the caching phase, where the source node populates the user caches with appropriate functions of the content library, and ii) the delivery phase, where the source forms a multicast codeword to be transmitted over the shared link in order to meet the users' content demands. These phases are generic for both coded and uncoded schemes, but naively performed in the uncoded case. In fact, when relying on uncoded or naive multicasting during the delivery phase, it is well known that the optimal caching strategy is to cache the top M most popular files at each user cache. This is however, in general, far from optimal when coding can be used in the delivery phase [START_REF] Ji | Order-optimal rate of caching and coded multicasting with random demands[END_REF]. In the following, we discuss the potential of caching-aided code design and illustrate its major advantages compared to the optimal caching policy under uncoded (naive) multicasting.

A. Random Fractional Caching

Each binary file f ∈ F is divided into B f equal-size packets or chunks. Given the caching distribution {p f }, with m f =1 p f = 1, each user caches chunks of file f with probability p f . That is, each user caches a number of chunks p f M B f (p f ≤ 1/M ) of file f chosen uniformly at random. It is important to note that the randomized nature of the selection process allows users to cache different sets of chunks of the same file, shown to be key in creating coded multicast opportunities during the delivery phase. In [START_REF] Ji | Order-optimal rate of caching and coded multicasting with random demands[END_REF], the authors showed that the optimal caching March 21, 2017 DRAFT distribution can be approximated by a truncated uniform distribution p f = 1/ m, ∀f ≤ m and p f = 0, ∀f > m, without affecting order-optimality 3 , and referred to this caching policy as random least frequently used (RLFU).

Compared to the least frequently used (LFU) caching policy (best option under naive multicasting) where the same most popular files are entirely cached at each user, RLFU maximizes the amount of distinct packets collectively cached by the network.

B. Coded multicasting

A simple example in Fig. 2 illustrates the key benefits of coded multicasting during the delivery phase. The network is composed of a source and 3 user nodes requesting files from a library of m = 4 binary files F = {A, B, C, D}. Each file (e.g., video segment) is divided into 2 chunks, yielding a library of chunks

C = {A 1 , A 2 , B 1 , B 2 , C 1 , C 2 , D 1 , D 2 }.
During the caching phase, users 1, 2, and 3 randomly fill their caches with chunks Clearly, in this case, coded multicasting reduces the number of transmissions (and hence the number of delivery time slots) by a factor of three.

{A 1 , B 2 , D 2 }, {A 2 , B 1 , D 2 },
As illustrated in the above example, a given user is able to decode its requested chunk from a mixture of combined chunks if and only if it has knowledge of all other combined chunks. Such a problem can be seen as an IC problem [START_REF] Blasiak | Index coding via linear programming[END_REF], and can be described by what is referred to as the conflict graph [START_REF] Ji | Order-optimal rate of caching and coded multicasting with random demands[END_REF]. The conflict graph is constructed such that each graph vertex corresponds to one requested chunk, and an edge between two vertices is created if: i) they correspond to different requested chunks and ii) for each vertex, the associated chunk is not included in the cache of the user requesting the chunk associated with the other vertex. Notice that an edge between two vertices indicates that their associated chunks must be separately transmitted, while non-connected vertices can be modulo summed via XOR operation [START_REF] Blasiak | Index coding via linear programming[END_REF]. The goal is to find the best chunk combinations such that the total number of transmissions is minimized. A common approach, referred to as chromatic index coding (CIC) [START_REF] Ji | Order-optimal rate of caching and coded multicasting with random demands[END_REF], is to compute a minimum graph coloring of the IC conflict graph, where the goal is to find an assignment of colors to the vertices of the graph such that no two connected vertices have the same color, and the total number of colors is minimized. The multicast codeword is constructed by generating sub-codewords obtained XORing the chunks with the same color, and then concatenating the resulting sub-codewords. The conflict graph of the example given in Fig. 2 is illustrated in the top left corner of the figure. The graph consists of 3 vertices corresponding to the three requested packets A 2 , B 2 , and D 2 . There are no edges between the vertices of the graph since, for each vertex, the associated chunk is included in the cache of the users associated with the other vertices. Therefore, all vertices can be assigned the same color and binary added into a single coded transmission, as shown in 2.

The work in [START_REF] Ji | Order-optimal rate of caching and coded multicasting with random demands[END_REF] showed that the combined use of RLFU caching and CIC coded multicasting is order-optimal 4 under any Zipf demand distribution, and that RLFU-CIC provides multiplicative caching gains, that is, the per-user throughput scales linearly or super-linearly with the cache size. In order to prove this result, the authors resort to a polynomial-time approximation of CIC, referred to as greedy constrained coloring (GCC). While GCC exhibits polynomial complexity in the number of users and packets, both CIC and GCC can only guarantee the promising multiplicative caching gain when the number of packets per file grows exponentially with the number of users, significantly limiting their practical performance [START_REF] Shanmugam | Finite Length Analysis of Caching-Aided Coded Multicasting[END_REF]. Subsequently, the works in [START_REF] Vettigli | An efficient coded multicasting scheme preserving the multiplicative caching gain[END_REF] and [START_REF] Ji | An efficient multiple-groupcast coded multicasting scheme for finite fractional caching[END_REF] extended the RLFU-CIC and RLFU-GCC schemes to the non-homogeneous SLCN and proposed two improved coded multicasting algorithms: i) the greedy randomized algorithm search procedure (GRASP) based on a greedy randomized approach, and ii) the hierarchical greedy coloring (HGC). These algorithms have been shown to recover a significant part of the multiplicative caching gain, while incurring a complexity at most quadratic in the number of requested packets.

C. Decoding phase

From the observation of the received multicast codeword and its cached content, each user has to decode its intended chunks via its own decoding function. In order to guarantee decoding, the receiver needs to be informed (e.g., via a packet header that carries all necessary information, as shown in Fig. 3.a) of the sub-codewords in the concatenated multicast codeword that contain any of its intended chunks. For each of the identified sub-codewords, the receiver obtains its intended chunks by performing the simple binary addition.

In the next section, we describe a fully working prototype implementation that includes the design of the required packet header to ensure full decodability.

III. IMPLEMENTATION OF CACHING-AIDED CODED MULTICASTING

While section II describes state of the art wireless caching and transmission code design, the impact of real protocol overheads on the multiplicative caching gain remains an open question that we address via a real prototype implementation in the following.

Our prototype implementation is based on the following components: i) a simplified application layer for generating and combining the requested chunks, ii) a MAC layer extended with additional header fields to allow decoding of coded packets, and iii) a PHY layer compliant with LTE standards. Our basic MAC layer frame implementation does not account for a complete standardized frame structure and the generated data is not encapsulated through the protocol stack, since our main goal is a proof-of-concept of caching-aided coded multicasting and its real-time feasibility. In the following, we describe in detail the MAC layer frame structure.

A. Frame structure

For a clear understanding of the implementation process, the basic frame structure is given in Fig. 3. Every accumulated packet is composed of two parts: header and payload. The payload represents the coded packet (divided 4 Order-optimal in the sense that the number of transmissions needed to satisfy the user demands scales (in number of users, number of files, and memory size) as the optimal scheme.

March 21, 2017 DRAFT as: payload 1 , • • • , payload K ); a mixture of original data chunks with elements in the Galois Field of order two GF(2), making it easy to encode and decode with a simple XOR operation. The header illustrated in Fig. 3.c contains the minimal information required for a successful extraction of each individual chunk. It carries the combined chunks identities and consists of the following information:

• Header Length: This is the first element of the header, and its size is fixed to one byte. It carries the number of header bytes.

• File IDs: These are the IDs of the files to which the combined chunks (payload) belong. Each ID requires a multiple of one byte, depending on the number of content files in the library.

• Chunk IDs: These are the IDs of the combined chunks within the transmitted packet. Each ID requires a multiple of one byte, depending on how many chunks a file is partitioned into.

• Chunk sizes: These are the sizes of the combined chunks, and are encoded with a multiple of four bytes to make the receiver able to recognize the size of each chunk.

In a practical network scenario, it is unusual to have a header length exceeding one byte since the number of requests and the number of simultaneously served users is generally limited. Notice that the uncoded design will necessitate the same header structure but only for one target user (unless the same packet is destined to multiple users) because no packet combination is performed. This means that in an uncoded scheme each packet is separately transmitted with its associated header, without the need for additional overhead information. This is due to the fact that we are assuming multicast transmission over the downlink shared channel (DL-SCH). This LTE physical layer transport channel is the main channel for downlink data transfer and it is used by many logical channels. The fact that the header information in the coded scheme depends on the number of served users implies a variable header length. An example of the header decomposition is illustrated in Fig. 3.c, where the number of files and chunks are assumed to not exceed one byte each, and the maximum size of a chunk is limited to four bytes. The payload length of a coded packet is equal to the largest chunk's length among the combined ones. Before being transmitted, the coded packet is partitioned into small packets and numbered such that the receiver can rebuilt the original coded packet. Each coded packet (see Fig. 2) is dedicated to users with IDs indicated in the header information. Aiming at decreasing the packet error probability (PER), the first small packet will be limited to the header data, and the others are charged with the payload. A 32-bit cyclic redundancy check (CRC) is appended to each small packet for error detection. In the header information, if the CRC detects some errors the whole coded packet is lost and the user drops all related small packets. Otherwise, each user checks whether concerned or not. If so, the user proceeds to the small packet decoding, based on its cached data and the reported files and chunks IDs. Conversely, if the user is not concerned the packet is dropped and the user waits for the next header to check out its affiliation. In case of channel erasure, the small packets are replaced with dummy bytes.

B. CorteXlab platform

The resulting fully working prototype is implemented in a large-scale testbed facility, CorteXlab [START_REF] Cardoso | CorteXlab: A facility for testing cognitive radio networks in a reproducible environment[END_REF] which is a testbed for cutting edge radio experimentation, composed of a mix of radio nodes, including SISO and MIMO software defined radio (SDR) nodes. The testbed shown in Fig. 4 Both RLFU with m optimized as in [START_REF] Ji | Order-optimal rate of caching and coded multicasting with random demands[END_REF] and LFU caching policies are adopted for the coded and naive multicasting delivery schemes, respectively.

The output of multicast encoder goes into an OFDM modulator with the following transmission parameters.

Each PHY frame is decomposed into small packets of size 100 bytes to which a CRC-32 and an OFDM header are appended for error detection and OFDM demodulation, respectively. The OFDM header and payload data are mapped into a binary phase shift keying (BPSK) and a quadrature PSK (QPSK), respectively, and each symbol is transmitted over a sample duration of T s = 1µs. The data is carried over L f = 48 subcarriers spaced by ∆f = 15KHz and the central frequency is set to 2.45 GHz.

B. Experimentation results

The focus herein is on the gain at the MAC layer that is based on counting the total number of required bytes to serve all UEs. Assuming the same number of requests L from all users, the normalized minimum rate (NMR) is defined as R t /(L × file size), where R t is the total number of required bytes at the MAC layer to satisfy all user demands. Note that NMR is in general a non-decreasing function of the number of users, and a decreasing function of cache size, M ; in particular, for M = 0, the NMR is equal to the total number of distinct user requests.

In the following, we provide a numerical validation of the prototype performance in terms of NMR. Specifically, we analyze the performance of our prototype solutions prot-HGC and prot-GRASP in terms of NMR compared with: i) HGC and GRASP for finite file packetization simulated in Matlab environment without taking into account implementation overhead ii) Naive multicasting with LFU caching policy at the rate of the worse channel receiver, and iii) the benchmark upper bound GCC when B = ∞ (see [START_REF] Ji | Order-optimal rate of caching and coded multicasting with random demands[END_REF]). The trend in terms of NMR demonstrated by the prototype confirms the gains predicted by the theory. In order to illustrate the behavior of the multiplicative gains, Figs. 5.c and 5.d show the prototype NMR gains as a function of the cache size M and the Zipf parameter α, respectively. The gain of a given scheme is defined as the ratio between the NMR achieved by naive multicasting with LFU caching policy and the NMR achieved by that scheme.

In particular, when the scheme is a prototype implementation, then the NMR of naive multicasting is computed with its associated overhead. From Fig 5 .c, we can observe that the gain is a monotonic non-decreasing function of the cache size. Note that we do not plot the point at M = 20 since it is well known that the NMR is zero for all the schemes, and hence the gain is given by an indeterminate form of type 0/0. Fig 5 .c shows that the gains achieved by prot-GRASP and prot-HgC are very close to the gains achieved by the corresponding MATLAB simulated schemes, confirming the little impact of the implementation overhead on the overall performance. Furthermore, it is worth noticing that due to the reduced number of transmitted coded packets compared to the number of uncoded packets transmitted by naive multicasting, the total overhead size is also smaller. That is, even though each packet header length is larger, the total number of header bytes over all transmissions is also reduced.

In terms of the Zipf parameter α, Fig. 5.d shows that for M = 2 files, a gain close to 1.3 is obtained under uniform popularity (α = 0), and this gain tends to 1 as the popularity distribution becomes more skewed.

C. Turning memory into bandwidth

In this section, we evaluate the physical layer bandwidth gains enabled by coded multicasting. To do so, we assume a fixed video transmission delay (e.g., according to users' QoS) and evaluate the bandwidth required to serve the video segment requests of all users. Fig. 6 illustrates the bandwidth gain (BG) evolution at the PHY layer with respect to the number of users for different cache sizes. We define the PHY BG as the bandwidth required to serve all requests via naive multicasting over the bandwidth required via the use of coded multicasting. The increase in BG can be clearly observed with respect to both the cache size and the number of users. For instance, assuming a cache size M = 10% of the library size, the gain starts with a value around 1.1 for 5 users and goes up to 1.31 for 40 users. Similarly, at M = 30%, the gain increases from around 1.4 for 5 users and reaches around 1.68 for 40 users. The increase of the BG with respect to the number of users is specially relevant, as it illustrates the scalability benefits of coded multicasting.

March 21, 2017 DRAFT

V. FUTURE DIRECTIONS

In the above discussion, coding overhead and computational complexity have been proven not to limit the performance gain of wireless caching for coded multicasting. However, several open problems related to PHY layer protocols are currently under investigation, among which we cite the following:

• Variation of the channel characteristics: Regarding the variations of channel statistics across users (e.g., different SNRs), the work in [START_REF] Cacciapuoti | Speeding up Future Video Distribution via Channel-Aware Caching-Aided Coded Multicast[END_REF] provided a theoretical analysis that takes into account the wireless channel characteristics in the presence of any combination of unicast/multicast transmission and wireless edge caching.

They proposed a channel-aware caching-aided coded multicast scheme based on joint source-channel coding with side information. Such scheme is able to guarantee a rate to each receiver, within a constant factor of the optimal rate, had the remaining users experienced its same channel conditions. The scheme preserves the cacheenabled multiplicative throughput gains by completely avoiding throughput penalization from the presence of receivers experiencing worse propagation conditions. The implementation of this scheme in CorteXlab is part of our next steps for future work. As opposed to network emulation platforms such as in [START_REF] Niesen | Coded caching for delay-sensitive content[END_REF], CorteXlab will allow us to properly test user mobility and realistic channel degradation across wireless end points.

• Combination with MIMO schemes: The use of MIMO schemes is an interesting topic with significant active research. Undergoing studies such as [START_REF] Yang | Content Delivery with Coded Caching and Massive MIMO in 5G[END_REF] have shown that in a MIMO setting, coded multicasting is indeed complementary to MIMO, and the combination of both provides cumulative gains in most practical scenarios.

This is also object of future work, and again, CorteXlab represents a key advantage in order to easily include next generation radio technologies.

• Dynamic scenarios: Our current implementation setting is limited to static scenarios with respect to file popularity and number of users. Ideas related to cache adaptation with respect to dynamic popularity distributions and varying number of users are of interest for future work and currently under investigation.

VI. CONCLUSION

This article discusses the potential of caching-aided coded multicasting for improving bandwidth efficiency in next generation wireless access networks. A real-time implementation for performance evaluation in real environments has been presented. On the way from theory to practical evaluation, a complete frame structure for the transmitter and the receiver has been proposed. Interestingly, the additional coding overhead does not compromise performance and leads to an overall positive multicasting gain, reducing bandwidth requirements and transmission delay when compared to the best uncoded schemes. We have integrated the coded multicast design in an OFDM based PHY layer, and deployed the scenario in CorteXlab, a shielded experimentation room, using radio nodes. Our work also shows the potential of such facility to validate new concepts relative advanced radio technologies for 5G networks.

  is installed in a large (180 m 2 ) shielded room March 21, 2017 DRAFT partly covered with electromagnetic wave absorbing material. User nodes are placed over a regular grid with an inter-node distance of 1.8 meters, and accept any PHY layer implementations on both hardware and software. A unified server is available for starting, coordinating, and collecting the results of experiments. As a development tool, the GNU Radio software is employed for real-time experimentation. IV. END-TO-END PERFORMANCE RESULTS AND PERSPECTIVES A. Setup Environment Our SLN experimentation consists of one radio source node and n = 10 radio user nodes. Each user requests L = 10 files from a library F of m = 20 binary files, each of size 2.8 Mb. A cache of size M files is deployed at every user. Such a scenario can be seen as if the users are APs carrying multiple requests from different UEs, and the source is the eNB having access to the content library. The file request distribution is drawn from a Zipf distribution with Zipf parameter α: α = 0 returns a uniform request distribution; the higher the Zipf parameter α, the more skewed is the request distribution. The binary files are partitioned into equally sized B = 100 chunks yielding a library of m b = 2000 chunks.

  Figs. 5.a and 5.b show the NMR as function of the cache size and the Zipf parameter α respectively. This metric is specially illustrative of the amount of bandwidth resources the wireless operator needs to provide in order to meet the receiver demands. In Fig. 5.a, we assume a Zipf parameter α = 0. Observe first the performance of naive-multicast. As expected, the load reduces approximately linearly with March 21, 2017 DRAFT the cache size M. Observe, now, how the significant multiplicative caching gains (w.r.t. naive-multicast) quantified by the upper bound (RLFU-GCC with B = ∞) are remarkably preserved by the prototype solutions (prot-HGC and prot-GRASP) which achieve an NMR almost indistinguishable from the corresponding schemes implemented in Matlab environment without taking into account the encoding and decoding overheard. Fig. 5.a clearly shows the effectiveness of the proposed implementation in allowing receivers to decode their requested files at an NMR very close to the theoretically optimal NMR. From Fig. 5.a, it is also apparent that the two coloring algorithms have similar performance for α = 0. The effectiveness of coded multicasting is highly influenced by the Zipf parameter α, as illustrated in Fig. 5.b for cache size M = 2 files. Observe how the reduction in NMR enabled via coded multicasting is much more attractive in the region of α ≤ 1.

1 )

 1 The users inform the source about their requests 2) The source performs coding design and broadcast the coded packet 3) Each user reads the overhead and decide whether to decode the received packet or not

Fig. 2 .Fig. 3 .Fig. 4 .

 234 Fig. 2. Joint design of caching-aided coded multicasting in a 3-user SLN where each user is equipped with a storage capacity of 1.5 file and requests one file from a library with 4 binary files.

Fig. 5 .Fig. 6 .

 56 Fig. 5. Comparison of the total minimum rate normalized by the 1-user network minimum rate with respect to : a) the cache size with α = 0, and b) the Zipf α parameter with M = 2 files, and the gain of the coded over the uncoded scheme with respect to: c) the cache size with α = 0, and d) the Zipf α parameter with M = 2 files.

  S10 -M' 14) received the Telecommunication Engineering Diploma from the Faculty of Engineering, Lebanese University, Lebanon, in 2009, the M.S. degree from the Universit de Bretagne Occidentale, France, in 2010, and the Ph.D. degree from Tlcom Bretagne, France, in 2013. In 2012, he was a visiting PhD student at the Coding and Signal Transmission Laboratory, University of Waterloo, Canada. Between 2013 and 2014 he was an R&D engineer position at Orange Labs, Paris. In 2015, he held a post-doctoral research position at INRIA until Sept. 2016, and then joined the University of sciences and arts in Lebanon (USAL) where he hold currently an assistant professor position. SM '05 -F '13) received the Ph.D. degree in Electrical Engineering from Seconda Universita' degli Studi di Napoli, Italy, in 1999. She held research positions at Princeton University, at the Center for Wireless Communications, Oulu, Finland and at Universita' degli Studi del Sannio, Benevento, Italy. From 2002 she has joined the Faculty of the Universita' degli Studi di Napoli Federico II, and in 2009 she joined Bell Labs. From 2011, Dr. Tulino is Member of the Editorial Board of the IEEE Transactions on Information Theory and in 2013, she was elevated to IEEE Fellow. She has received several paper awards and among the others the 2009 Stephen O. Rice Prize in the Field of Communications Theory for the best paper published in the IEEE TRANSACTION ON COMMUNICATION in 2008. She has been principal investigator of several research projects sponsored by the European Union and the Italian National Council, and was selected by the National Academy of Engineering for the Frontiers of Engineering program in 2013. Her research interests lie in the area of communication systems approached with the complementary tools provided by signal processing, information theory and random matrix theory. Dario Barone received the B.E. in Telecommunications Engineering from Universita' degli Studi di Napoli Federico II, Italy, in 2016. He developed his thesis working on this project where he makes his first contribution in research and development. He is currently studying for his Master of Telecommunications Engineering at the same university. Master degree in Computer Science from the Universit Federico II di Napoli in 2014.He is now a PhD student in Computer Science in the same university.

	PLACE PHOTO HERE	Yasser Fadlallah (His research interests lie in the wireless communications area, focusing on interference management, advanced and
	low-complexity receivers, wireless caching, and multiple antennas systems.
	PLACE PHOTO HERE Antonia M. Tulino (S '00 -M '03 -PLACE
	PHOTO
	HERE
	Finally, we have briefly described interesting open problems related to PHY layer protocols that are currently under investigation. March 21, 2017 DRAFT PLACE PHOTO HERE Giuseppe Vettigli received a March 21, 2017 DRAFT

Details about the selection of the optimal m are given in[START_REF] Ji | Order-optimal rate of caching and coded multicasting with random demands[END_REF] (see section IV).March 21, 2017 DRAFT

Content Delivery Servers

Evolved Core Network

Radio Access Network Core Network INTERNET


Claire Gardent
email: claire.gardent@loria.fr

Eric Kow
email: eric.kow@loria.fr

A Symbolic Approach to Near-Deterministic Surface Realisation using Tree Adjoining Grammar

Surface realisers divide into those used in generation (NLG geared realisers) and those mirroring the parsing process (Reversible realisers). While the first rely on grammars not easily usable for parsing, it is unclear how the second type of realisers could be parameterised to yield from among the set of possible paraphrases, the paraphrase appropriate to a given generation context. In this paper, we present a surface realiser which combines a reversible grammar (used for parsing and doing semantic construction) with a symbolic means of selecting paraphrases.

Introduction

In generation, the surface realisation task consists in mapping a semantic representation into a grammatical sentence.

Depending on their use, on their degree of nondeterminism and on the type of grammar they assume, existing surface realisers can be divided into two main categories namely, NLG (Natural Language Generation) geared realisers and reversible realisers.

NLG geared realisers are meant as modules in a full-blown generation system and as such, they are constrained to be deterministic: a generation system must output exactly one text, no less, no more. In order to ensure this determinism, NLG geared realisers generally rely on theories of grammar which systematically link form to function such as systemic functional grammar (SFG, [START_REF] Matthiessen | Text generation and systemic-functional linguistics: experiences from English and Japanese[END_REF]) and, to a lesser extent, Meaning Text Theory (MTT, (Mel'cuk, 1988)). In these theories, a sentence is associated not just with a semantic representation but with a semantic representation enriched with additional syntactic, pragmatic and/or discourse information. This additional information is then used to constrain the realiser output. 1 One drawback of these NLG geared realisers however, is that the grammar used is not usually reversible i.e., cannot be used both for parsing and for generation. Given the time and expertise involved in developing a grammar, this is a non-trivial drawback.

Reversible realisers on the other hand, are meant to mirror the parsing process. They are used on a grammar developed for parsing and equipped with a compositional semantics. Given a string and such a grammar, a parser will assign the input string all the semantic representations associated with that string by the grammar. Conversely, given a semantic representation and the same grammar, a realiser will assign the input semantics all the strings associated with that semantics by the grammar. In such approaches, non-determinism is usually handled by statistical filtering: treebank induced probabilities are used to select from among the possible paraphrases, the most probable one. Since the most probable paraphrase is not necessarily the most appropriate one in a given context, it is unclear however, how such realisers could be integrated into a generation system.

In this paper, we present a surface realiser which combines reversibility with a symbolic approach to determinism. The grammar used is fully reversible (it is used for parsing) and the realisation algorithm can be constrained by the input so as to ensure a unique output conforming to the requirement of a given (generation) context. We show both that the grammar used has a good paraphrastic power (it is designed in such a way that grammatical paraphrases are assigned the same semantic representations) and that the realisation algorithm can be used either to generate all the grammatical paraphrases of a given input or just one provided the input is adequately constrained.

The paper is structured as follows. Section 2 introduces the grammar used namely, a Feature Based Lexicalised Tree Adjoining Grammar enriched with a compositional semantics. Importantly, this grammar is compiled from a more abstract specification (a so-called "meta-grammar") and as we shall see, it is this feature which permits a natural and systematic coupling of semantic literals with syntactic annotations. Section 3 defines the surface realisation algorithm used to generate sentences from semantic formulae. This algorithm is non-deterministic and produces all paraphrases associated by the grammar with the input semantics. We then go on to show (section 4) how this algorithm can be used on a semantic input enriched with syntactic or more abstract control annotations and further, how these annotations can be used to select from among the set of admissible paraphrases precisely these which obey the constraints expressed in the added annotations. Section 5 reports on a quantitative evaluation based on the use of a core tree adjoining grammar for French. The evaluation gives an indication of the paraphrasing power of the grammar used as well as some evidence of the deterministic nature of the realiser. Section 6 relates the proposed approach to existing work and section 7 concludes with pointers for further research.

The grammar

We use a unification based version of LTAG namely, Feature-based TAG. A Feature-based TAG (FTAG, (Vijay-Shanker and Joshi, 1988)) consists of a set of (auxiliary or initial) elementary trees and of two tree composition operations: substitution and ad-junction. Initial trees are trees whose leaves are labelled with substitution nodes (marked with a downarrow) or terminal categories. Auxiliary trees are distinguished by a foot node (marked with a star) whose category must be the same as that of the root node. Substitution inserts a tree onto a substitution node of some other tree while adjunction inserts an auxiliary tree into a tree. In an FTAG, the tree nodes are furthermore decorated with two feature structures (called top and bottom) which are unified during derivation as follows. On substitution, the top of the substitution node is unified with the top of the root node of the tree being substituted in. On adjunction, the top of the root of the auxiliary tree is unified with the top of the node where adjunction takes place; and the bottom features of the foot node are unified with the bottom features of this node. At the end of a derivation, the top and bottom of all nodes in the derived tree are unified.

To associate semantic representations with natural language expressions, the FTAG is modified as proposed in [START_REF] Gardent | Semantic construction in FTAG[END_REF]. ⇒ name(j,john), run(r,j), often(r)

Figure 1: Flat Semantics for "John often runs" Each elementary tree is associated with a flat semantic representation. For instance, in Figure 1,2 the trees for John, runs and often are associated with the semantics name(j,john), run(r,s) and often(x) respectively.

Importantly, the arguments of a semantic functor are represented by unification variables which occur both in the semantic representation of this functor and on some nodes of the associated syntactic tree. For instance in Figure 1, the semantic index s occurring in the semantic representation of runs also occurs on the subject substitution node of the associated elementary tree.

The value of semantic arguments is determined by the unifications resulting from adjunction and substitution. For instance, the semantic index s in the tree for runs is unified during substitution with the semantic indices labelling the root nodes of the tree for John. As a result, the semantics of John often runs is (1) {name(j,john),run(r,j),often(r)}

The grammar used describes a core fragment of French and contains around 6 000 elementary trees. It covers some 35 basic subcategorisation frames and for each of these frames, the set of argument redistributions (active, passive, middle, neuter, reflexivisation, impersonal, passive impersonal) and of argument realisations (cliticisation, extraction, omission, permutations, etc.) possible for this frame. As a result, it captures most grammatical paraphrases that is, paraphrases due to diverging argument realisations or to different meaning preserving alternation (e.g., active/passive or clefted/non-clefted sentence).

The surface realiser, GenI

The basic surface realisation algorithm used is a bottom up, tabular realisation algorithm [START_REF] Kay | Chart Generation. In 34th ACL[END_REF] optimised for TAGs. It follows a three step strategy which can be summarised as follows. Given an empty agenda, an empty chart and an input semantics φ:

Lexical selection. Select all elementary trees whose semantics subsumes (part of) φ. Store these trees in the agenda. Auxiliary trees devoid of substitution nodes are stored in a separate agenda called the auxiliary agenda.

Substitution phase. Retrieve a tree from the agenda, add it to the chart and try to combine it by substitution with trees present in the chart. Add any resulting derived tree to the agenda. Stop when the agenda is empty.

Adjunction phase. Move the chart trees to the agenda and the auxiliary agenda trees to the chart. Retrieve a tree from the agenda, add it to the chart and try to combine it by adjunction with trees present in the chart. Add any resulting derived tree to the agenda. Stop when the agenda is empty.

When processing stops, the yield of any syntactically complete tree whose semantics is φ yields an output i.e., a sentence.

The workings of this algorithm can be illustrated by the following example. Suppose that the input semantics is (1). In a first step (lexical selection), the elementary trees selected are the ones for John, runs, often. Their semantics subsumes part of the input semantics. The trees for John and runs are placed on the agenda, the one for often is placed on the auxiliary agenda.

The second step (the substitution phase) consists in systematically exploring the possibility of combining two trees by substitution. Here, the tree for John is substituted into the one for runs, and the resulting derived tree for John runs is placed on the agenda. Trees on the agenda are processed one by one in this fashion. When the agenda is empty, indicating that all combinations have been tried, we prepare for the next phase.

All items containing an empty substitution node are erased from the chart (here, the tree anchored by runs). The agenda is then reinitialised to the content of the chart and the chart to the content of the auxiliary agenda (here often). The adjunction phase proceeds much like the previous phase, except that now all possible adjunctions are performed. When the agenda is empty once more, the items in the chart whose semantics matches the input semantics are selected, and their strings printed out, yielding in this case the sentence John often runs.

Paraphrase selection

The surface realisation algorithm just sketched is non-deterministic. Given a semantic formula, it might produce several outputs. For instance, given the appropriate grammar for French, the input in (2a) will generate the set of paraphrases partly given in (2b-2k).

(2) a. lj :jean(j) la:aime (e,j,m) To select from among all possible paraphrases of a given input, exactly one paraphrase, NLG geared realisers use symbolic information to encode syntactic, stylistic or pragmatic constraints on the output. Thus for instance, both REALPRO [START_REF] Lavoie | RealPro-a fast, portable sentence realizer[END_REF] and SURGE [START_REF] Elhadad | SURGE: a comprehensive plug-in syntactic realization component for text generation[END_REF] assume that the input associates semantic literals with low level syntactic and lexical information mostly leaving the realiser to just handle inflection, word order, insertion of grammatical words and agreement. Similarly, KPML [START_REF] Matthiessen | Text generation and systemic-functional linguistics: experiences from English and Japanese[END_REF] assumes access to ideational, interpersonal and textual information which roughly corresponds to semantic, mood/voice, theme/rheme and focus/ground information.

In what follows, we first show that the semantic input assumed by the realiser sketched in the previous section can be systematically enriched with syntactic information so as to ensure determinism. We then indicate how the satisfiability of this enriched input could be controlled.

At most one realisation

In the realisation algorithm sketched in Section 3, non-determinism stems from lexical ambiguity: 3 for each (combination of) literal(s) l in the input there usually is more than one TAG elementary tree whose semantics subsumes l. Thus each (combination of) literal(s) in the input selects a set of elementary trees and the realiser output is the set of combinations of selected lexical trees which are licensed by the grammar operations (substitution and adjunction) and whose semantics is the input.

One way to enforce determinism consists in ensuring that each literal in the input selects exactly one elementary tree. For instance, suppose we want to generate (2b), repeated here as (3a), rather than 3 Given two TAG trees, there might also be several ways of combining them thereby inducing more non-determinism. However in practice we found that most of this nondeterminism is due either to over-generation (cases where the grammar is not sufficiently constrained and allows for one tree to adjoin to another tree in several places) or to spurious derivation (distinct derivations with identical semantics). The few remaining cases that are linguistically correct are due to varying modifier positions and could be constrained by a sophisticated feature decorations in the elementary tree.

any of the paraphrases listed in (2c-2k). Intuitively, the syntactic constraints to be expressed are those given in (3b).

(3) a. Jean aime Marie b. Canonical Nominal Subject, Active verb form, Canonical Nominal Object c. lj :jean(j) la:aime(e,j,m) lm:marie(m)

The question is how precisely to formulate these constraints, how to associate them with the semantic input assumed in Section 3 and how to ensure that the constraints used do enforce uniqueness of selection (i.e., that for each input literal, exactly one elementary tree is selected)? To answer this, we rely on a feature of the grammar used, namely that each elementary tree is associated with a linguistically meaningful unique identifier.

The reason for this is that the grammar is compiled from a higher level description where tree fragments are first encapsulated into so-called classes and then explicitly combined (by inheritance, conjunction and disjunction) to produce the grammar elementary trees (cf. [START_REF] Crabbé | Metagrammar redux[END_REF]).

More generally, each elementary tree in the grammar is associated with the set of classes used to produce that tree and importantly, this set of classes (we will call this the tree identifier) provides a distinguishing description (a unique identifier) for that tree: a tree is defined by a specific combination of classes and conversely, a specific combination of classes yields a unique tree. 4 Thus the set of classes associated by the compilation process with a given elementary tree can be used to uniquely identify that tree.

Given this, surface realisation is constrained as follows.

1. Each tree identifier Id(tree) is mapped into a simplified set of tree properties TP t . There are two reasons for this simplification. First, some classes are irrelevant. For instance, the class used to enforce subject-verb agreement is needed to ensure this agreement but does not help in selecting among competing trees. Second, a given class C can be defined to be equivalent to the combination of other classes C 1 . . . C n and consequently a tree identifier containing C, C 1 . . . C n can be reduced to include either C or C 1 . . . C n .

2. Each literal l i in the input is associated with a tree property set T P i (i.e., the input we generate from is enriched with syntactic information)

3. During realisation, for each literal/tree property pair l i : T P i in the enriched input semantics, lexical selection is constrained to retrieve only those trees (i) whose semantics subsumes l i and (ii) whose tree properties are T P i

Since each literal is associated with a (simplified) tree identifier and each tree identifier uniquely identifies an elementary tree, realisation produces at most one realisation.

Examples 4a-4c illustrates the kind of constraints used by the realiser.

At least one realisation

For a realiser to be usable by a generation system, there must be some means to ensure that its input is satisfiable i.e., that it can be realised. How can this be done without actually carrying out realisation i.e., without checking that the input is satisfiable?

Existing realisers indicate two types of answers to that dilemma.

A first possibility would be to draw on [START_REF] Yang | From functional specification to syntactic structure[END_REF]'s proposal and compute the enriched input based on the traversal of a systemic network.

More specifically, one possibility would be to consider a systemic network such as NIGEL, precompile all the functional features associated with each possible traversal of the network, map them onto the corresponding tree properties and use the resulting set of tree properties to ensure the satisfiability of the enriched input.

Another option would be to check the well formedness of the input at some level of the linguistic theory on which the realiser is based. Thus for instance, REALPRO assumes as input a well formed deep syntactic structure (DSyntS) as defined by Meaning Text Theory (MTT) and similarly, SURGE takes as input a functional description (FD) which in essence is an underspecified grammatical structure within the SURGE grammar. In both cases, there is no guarantee that the input be satisfiable since all the other levels of the linguistic theory must be verified for this to be true. In MTT, the DSyntS must first be mapped onto a surface syntactic structure and then successively onto the other levels of the theory while in SURGE, the input FD can be realised only if it provides consistent information for a complete top-down traversal of the grammar right down to the lexical level. In short, in both cases, the well formedness of the input can be checked with respect to some criteria (e.g., well formedness of a deep syntactic structure in MTT, well formedness of a FD in SURGE) but this well formedness does not guarantee satisfiability. Nonetheless this basic well formedness check is important as it provides some guidance as to what an acceptable input to the realiser should look like.

We adopt a similar strategy and resort to the notion of polarity neutral input to control the well formedness of the enriched input. The proposal draws on ideas from [START_REF] Koller | Generation as dependency parsing[END_REF][START_REF] Gardent | Generating and selecting grammatical paraphrases[END_REF] and aims to determine whether for a given input (a set of TAG elementary trees whose semantics equate the input semantics), syntactic requirements and resources cancel out. More specifically, the aim is to determine whether given the input set of elementary trees, each substitution and each adjunction requirement is satisfied by exactly one elementary tree of the appropriate syntactic category and semantic index.

Roughly,5 the technique consists in (automatically) associating with each elementary tree a polarity signature reflecting its substitution/adjunction requirements and resources and in computing the grand polarity of each possible combination of trees covering the input semantics. Each such combination whose total polarity is non-null is then filtered out (not considered for realisation) as it cannot possibly lead to a valid derivation (either a requirement cannot be satisfied or a resource cannot be used).

In the context of a generation system, polarity checking can be used to check the satisfiability of the input or more interestingly, to correct an ill formed input i.e., an input which can be detected as being unsatisfiable.

To check a given input, it suffices to compute its polarity count. If it is non-null, the input is unsatisfiable and should be revised. This is not very useful however, as the enriched input ensures determinism and thereby make realisation very easy, indeed almost as easy as polarity checking.

More interestingly, polarity checking can be used to suggest ways of fixing an ill formed input. In such a case, the enriched input is stripped of its control annotations, realisation proceeds on the basis of this simplified input and polarity checking is used to preselect all polarity neutral combinations of elementary trees. A closest match (i.e. the polarity neutral combination with the greatest number of control annotations in common with the ill formed input) to the ill formed input is then proposed as a probably satisfiable alternative.

Evaluation

To evaluate both the paraphrastic power of the realiser and the impact of the control annotations on non-determinism, we used a graduated test-suite which was built by (i) parsing a set of sentences, (ii) selecting the correct meaning representations from the parser output and (iii) generating from these meaning representations. The gradation in the test suite complexity was obtained by partitioning the input into sentences containing one, two or three finite verbs and by choosing cases allowing for different paraphrasing patterns. More specifically, the test suite includes cases involving the following types of paraphrases:

• Grammatical variations in the realisations of the arguments (cleft, cliticisation, question, relativisation, subject-inversion, etc.) or of the verb (active/passive, impersonal) • Variations in the realisation of modifiers (e.g., relative clause vs adjective, predicative vs nonpredicative adjective) • Variations in the position of modifiers (e.g., pre-vs post-nominal adjective) • Variations licensed by a morpho-derivational link (e.g., to arrive/arrival) On a test set of 80 cases, the paraphrastic level varies between 1 and over 50 with an average of 18 paraphrases per input (taking 36 as upper cut off point in the paraphrases count). Figure 5 gives a more detailed description of the distribution of the paraphrastic variation. In essence, 42% of the sentences with one finite verb accept 1 to 3 paraphrases (cases of intransitive verbs), 44% accept 4 to 28 paraphrases (verbs of arity 2) and 13% yield more than 29 paraphrases (ditransitives). For sentences containing two finite verbs, the ratio is 5% for 1 to 3 paraphrases, 36% for 4 to 14 paraphrases and 59% for more than 14 paraphrases. Finally, sentences containing 3 finite verbs all accept more than 29 paraphrases.

Two things are worth noting here. First, the paraphrase figures might seem low wrt to e.g., work by [START_REF] Velldal | Statistical ranking in tactical generation[END_REF] which mentions several thousand outputs for one given input and an average number of realisations per input varying between 85.7 and 102.2. Admittedly, the French grammar we are using has a much more limited coverage than the ERG (the grammar used by [START_REF] Velldal | Statistical ranking in tactical generation[END_REF]) and it is possible that its paraphrastic power is lower. However, the counts we give only take into account valid paraphrases of the input. In other words, overgeneration and spurious derivations are excluded from the toll. This does not seem to be the case in [START_REF] Velldal | Statistical ranking in tactical generation[END_REF]'s approach where the count seems to include all sentences associated by the grammar with the input semantics.

Second, although the test set may seem small it is important to keep in mind that it represents 80 inputs with distinct grammatical and paraphrastic properties. In effect, these 80 test cases yields 1 528 distinct well-formed sentences. This figure compares favourably with the size of the largest regression test suite used by a symbolic NLG realiser namely, the SURGE test suite which contains 500 input each corresponding to a single sentence. It also compares reasonably with other more recent evaluations [START_REF] Charles | Evaluating coverage for large symbolic NLG grammars[END_REF][START_REF]An empirical verification of coverage and correctness for a general-purpose sentence generator[END_REF] which derive their input data from the Penn Treebank by transforming each sentence tree into a format suitable for the realiser [START_REF] Charles | Evaluating coverage for large symbolic NLG grammars[END_REF]. For these approaches, the test set size varies between roughly 1 000 and almost 3 000 sentences. But again, it is worth stressing that these evaluations aim at assessing coverage and correctness (does the realiser find the sentence used to derive the input by parsing it?) rather than the paraphrastic power of the grammar. They fail to provide a systematic assessment of how many distinct grammatical paraphrases are associated with each given input.

To verify the claim that tree properties can be used to ensure determinism (cf. footnote 4), we started by eliminating from the output all ill-formed sentences. We then automatically associated each wellformed output with its set of tree properties. Finally, for each input semantics, we did a systematic pairwise comparison of the tree property sets associated with the input realisations and we checked whether for any given input, there were two (or more) distinct paraphrases whose tree properties were the same. We found that such cases represented slightly over 2% of the total number of (input,realisations) pairs. Closer investigation of the faulty data indicates two main reasons for non-determinism namely, trees with alternating order of arguments and deriva-tions with distinct modifier adjunctions. Both cases can be handled by modifying the grammar in such a way that those differences are reflected in the tree properties.

Related work

The approach presented here combines a reversible grammar realiser with a symbolic approach to paraphrase selection. We now compare it to existing surfaces realisers.

NLG geared realisers.

Prominent general purpose NLG geared realisers include REALPRO, SURGE, KPML, NITROGEN and HALOGEN. Furthermore, HALOGEN has been shown to achieve broad coverage and high quality output on a set of 2 400 input automatically derived from the Penn treebank.

The main difference between these and the present approach is that our approach is based on a reversible grammar whilst NLG geared realisers are not. This has several important consequences.

First, it means that one and the same grammar and lexicon can be used both for parsing and for generation. Given the complexity involved in developing such resources, this is an important feature.

Second, as demonstrated in the Redwood Lingo Treebank, reversibility makes it easy to rapidly create very large evaluation suites: it suffices to parse a set of sentences and select from the parser output the correct semantics. In contrast, NLG geared realisers either work on evaluation sets of restricted size (500 input for SURGE, 210 for KPML) or require the time expensive implementation of a preprocessor transforming e.g., Penn Treebank trees into a format suitable for the realisers. For instance, [START_REF] Charles | Evaluating coverage for large symbolic NLG grammars[END_REF] reports that the implementation of such a processor for SURGE was the most time consuming part of the evaluation with the resulting component containing 4000 lines of code and 900 rules.

Third, a reversible grammar can be exploited to support not only realisation but also its reverse, namely semantic construction. Indeed, reversibility is ensured through a compositional semantics that is, through a tight coupling between syntax and semantics. In contrast, NLG geared realisers often have to reconstruct this association in rather ad hoc ways. Thus for instance, [START_REF] Yang | From functional specification to syntactic structure[END_REF] resorts to ad hoc "mapping tables" to associate substitution nodes with semantic indices and "fr-nodes" to constrain adjunction to the correct nodes. More generally, the lack of a clearly defined compositional semantics in NLG geared realisers makes it difficult to see how the grammar they use could be exploited to also support semantic construction.

Fourth, the grammar can be used both to generate and to detect paraphrases. It could be used for instance, in combination with the parser and the semantic construction module described in [START_REF] Gardent | Large scale semantic construction for Tree Adjoining Grammars[END_REF], to support textual entailment recognition or answer detection in question answering.

Reversible realisers. The realiser presented here differs in mainly two ways from existing reversible realisers such as [START_REF] White | Reining in CCG chart realization[END_REF])'s CCG system or the HPSG ERG based realiser [START_REF] Carroll | High efficiency realization for a wide-coverage unification grammar[END_REF].

First, it permits a symbolic selection of the output paraphrase. In contrast, existing reversible realisers use statistical information to select from the produced output the most plausible paraphrase.

Second, particular attention has been paid to the treatment of paraphrases in the grammar. Recall that TAG elementary trees are grouped into families and further, that the specific TAG we use is compiled from a highly factorised description. We rely on these features to associate one and the same semantic to large sets of trees denoting semantically equivalent but syntactically distinct configurations (cf. [START_REF] Gardent | Integration d'une dimension semantique dans les grammaires d'arbres adjoints[END_REF]).

Conclusion

The realiser presented here, GENI, exploits a grammar which is produced semi-automatically by compiling a high level grammar description into a Tree Adjoining Grammar. We have argued that a sideeffect of this compilation process -namely, the association with each elementary tree of a set of tree properties -can be used to constrain the realiser output. The resulting system combines the advantages of two orthogonal approaches. From the reversible approach, it takes the reusability, the ability to rapidly create very large test suites and the capacity to both generate and detect paraphrases. From the NLG geared paradigm, it takes the ability to symbolically constrain the realiser output to a given generation context.

GENI is free (GPL) software and is available at http://trac.loria.fr/˜geni.

(

On the other hand, one of our reviewers noted that "determinism" often comes more from defaults when input constraints are not supplied. One might see these realisers as being less deterministic than advertised; however, the point is that it is possible to supply the constraints that ensure determinism.

C x /Cx abbreviate a node with category C and a top/bottom feature structure including the feature-value pair { index : x}.

This is not absolutely true as a tree identifier only reflects part of the compilation process. In practice, they are few exceptions though so that distinct trees whose tree identifiers are identical can be manually distinguished.

Lack of space prevents us from giving much details here. We refer the reader to[START_REF] Koller | Generation as dependency parsing[END_REF][START_REF] Gardent | Generating and selecting grammatical paraphrases[END_REF] for more details.