Jidong Chen
email: chenjd@ruc.edu.cn

Xiaofeng Meng
email: xfmeng@ruc.edu.cn

Yanyan Guo
email: guoyy@ruc.edu.cn

Stéphane Grumbach
email: grumbach@liama.ia.ac.cn

Hui Sun
email: hsun@ruc.edu.cn

Modeling and Predicting Future Trajectories of Moving Objects in a Constrained Network

Advances in wireless sensor networks and positioning technologies enable traffic management (e.g. routing traffic) that uses real-time data monitored by GPS-enabled cars. Location management has become an enabling technology in such application. The location modeling and trajectory prediction of moving objects are the fundamental components of location management in mobile locationaware applications. In this paper, we model the road network and moving objects in a graph of cellular automata (GCA), which makes full use of the constraints of the network and the stochastic behavior of the traffic. A simulation-based method based on graphs of cellular automata is proposed to predict future trajectories. Our technique strongly differs from the linear prediction method, which has low prediction accuracy and requires frequent updates when applied to real traffic with velocity changes. The experiments, carried on two different datasets, show that the simulation-based prediction method provides higher accuracy than the linear prediction method.

Introduction

The continued advances in wireless sensor networks and position technologies enable traffic management and location-based services that track continuously changing positions of moving objects. For example, moving cars on a road network can be monitored and their locations are sampled by sensors or GPS periodically, then sent to the server and stored in a database. According to the real-time locations and predicted future trajectories of cars, we can forecast traffic jams and route the traffic intelligently. Timely location information is becoming one of the key features in these applications. In this paper, we focus on the the location modeling and future trajectory prediction of mov-ing objects, which are the foundations for efficient location management in mobile location-aware applications.

Many models and algorithms have been proposed to handle the continuously changing positions of moving objects. Wolfson et al. in [START_REF] Sistla | Modeling and Querying Moving Objects[END_REF][START_REF] Wolfson | Moving Object Databases: Issues and Solutions[END_REF] firstly proposed a Moving Objects Spatio-Temporal (MOST) model, which represents the location as a dynamic attribute. Later, the model based on linear constrain [START_REF] Su | Moving Objects: Logical Relationships and Queries[END_REF], abstract data types [START_REF] Güting | A Foundation for Representing and Querying Moving Objects[END_REF] and Space-Time Grid Storage [START_REF] Chon | Using Space-Time Grid for Efficient Management of Moving Objects[END_REF] for moving objects have been proposed. However, in most real life applications, objects move within constrained networks, especially the transportation networks (e.g., vehicles move on road networks). These works ignore the interaction between moving objects and the underlying transportation networks.

In fact, the interaction is very important to manage network-constrained moving objects. For example, in the location tracking, the road-network representation of moving objects can be exploited to reduce the number of updates from moving objects to the database server [START_REF] Civilis | Techniques for Efficient Road-Network-Based Tracking of Moving Objects[END_REF]. For indexing moving objects in road networks, the temporal aspect can be distinguished and related to the road network to save considerable index storage space [START_REF] Almeida | Indexing the Trajectories of Moving Objects in Networks (Extended Abstract)[END_REF][START_REF] Frentzos | Indexing objects moving on Fixed networks[END_REF] since the spatial property of objects' movement is already captured by the network. In addition, using the network constraints, the query processing can also be improved [START_REF] Kolahdouzan | Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases[END_REF][START_REF] Shababi | A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Objects Databases[END_REF].

More recently, the models connecting moving objects with the road network representation have been proposed [START_REF] Ding | Managing Moving Objects on Dynamic Transportation Networks[END_REF][START_REF] Papadias | Query Processing in Spatial Network Databases[END_REF][START_REF] Speicys | Computational Data Modeling for network-Constrained Moving Objects[END_REF][START_REF] Vazirgiannis | A Spatiotemporal Model and Language for Moving Objects on Road Networks[END_REF]. Most of them represent road networks as graphs and moving objects as moving graph points with their speed in order to capture objects' movement. However, the models assume linear movement and can not reflect the real movement feature of moving objects in a road network where objects frequently change their velocity. This limits their applicability in a majority of real applications.

In this paper, we propose a new graph of cellular automata (GCA) model to integrate the traffic movement fea-tures into the model of moving objects and the underlying road network. The GCA model exploits the stochastic behavior of the real traffic by the cellular automaton which is used in the traffic simulation [START_REF] Nagel | A cellular automaton model for freeway traffic[END_REF]. It also combines the road network model with the real movement of objects and therefore improves the efficiency of managing network-constrained moving objects.

Considering the new feature of the GCA model, it can be efficiently used to simulate future trajectories of moving objects, where objects' movement follows traffic rules. We further propose a simulation-based prediction method based on the GCA model. Since the GCA exploits features of traffic systems, the method can predict future trajectories of moving objects in road network more accurately than the linear prediction method widely used in the predictive indexing and query processing.

The framework built on the GCA model and simulationbased prediction forms the foundation of the efficient storage and management of network-constrained moving objects. Specifically, it is capable of reducing the number of updates in tracking and indexing and supporting the predictive queries on moving objects in a road network.

In summary, this paper makes the following contributions:

1. We present the graphs of cellular automata (GCA) model to integrate the trajectory representation of moving objects and the transportation network with intrinsic movement features in the real traffic.

2.

Based on the GCA model, we propose a simulationbased prediction (SP) method, which improves the accuracy of predicting future trajectories of objects moving in a traffic network.

3.

The experiments show that the simulation-based prediction method obtains higher accuracy than the linear prediction method widely used.

The rest of the paper is organized as follows. Section 2 surveys related work. In Section 3, the graph of cellular automata model is introduced to model the road network and movement of objects. Section 4 presents the simulationbased prediction method. Section 5 contains experimental evaluation. We conclude in Section 6.

Related Work

The modeling of moving objects attracts a lot of research interests. Wolfson et al. in [16,[START_REF] Wolfson | Moving Object Databases: Issues and Solutions[END_REF] firstly proposed a Moving Objects Spatio-Temporal (MOST) model which is capable of tracking not only the current, but also the near future position of moving objects. Su et al. in [START_REF] Su | Moving Objects: Logical Relationships and Queries[END_REF] presented a data model for moving objects based on linear constraint databases. Chon et al. in [START_REF] Chon | Using Space-Time Grid for Efficient Management of Moving Objects[END_REF] proposed a Space-Time Grid Storage model for moving objects. In [START_REF] Güting | A Foundation for Representing and Querying Moving Objects[END_REF], Güting et al. presented a data model and data structures for moving objects based on abstract data types. However, nearly none of these works have treated the interaction between moving objects and the underlying transportation networks in any way.

In 2001, Vazirgiannis and Wolfson [START_REF] Vazirgiannis | A Spatiotemporal Model and Language for Moving Objects on Road Networks[END_REF] first introduced a model for moving objects on road networks, which connects the moving object's trajectory model with the road network representation. In the model, the road network is represented by an electronic map and the trajectory of a moving object is constructed by the map and its destination. In [START_REF] Speicys | Computational Data Modeling for network-Constrained Moving Objects[END_REF], the authors presented a computational data model for network constrained moving objects in which the road network has two representations namely a two-dimensional representation and a graph representation to obtain both expressiveness and efficient support for queries. In this model, the moving objects treated as query points are represented by graph points located on segments or edges. Ding et al. [START_REF] Ding | Managing Moving Objects on Dynamic Transportation Networks[END_REF] proposed a MOD model, based on dynamic transportation networks. They model transportation networks as dynamic graphs and moving objects as moving graph points. In addition, Papadias et al. in [START_REF] Papadias | Query Processing in Spatial Network Databases[END_REF] presented a framework to support spatial network databases. However, these models capture movement information of objects only by their speed and assume the linear movement, which limit applicability in a majority of real applications.

Prediction methods for future trajectories of moving objects play an important role in indexing and querying current and anticipated future positions. Most existing prediction methods, used in the indexing and querying, assume linear movement, which cannot reflect the real movement. Aggarwal et al [START_REF] Aggarwal | On Nearest Neighbor Indexing of Nonlinear Trajectories[END_REF] introduced a non-linear model that uses quadratic predictive function, Tao et al [START_REF] Tao | Prediction and Indexing of Moving Objects with Unknown Motion Patterns[END_REF] proposed a prediction method based on recursive motion functions for objects with unknown motion patterns, and Cai et al [START_REF] Cai | Indexing spatiotemporal trajectories with chebyshev polynomials[END_REF] used Chebyshev polynomials to represent and index spatio-temporal trajectories. In [START_REF] Tao | Venn Sampling: A Novel Prediction Technique for Moving Objects[END_REF], Tao et al developed Venn sampling (VS), a novel estimation method optimized for a set of pivot queries that reflect the distribution of actual ones. These prediction methods improve the precision in predicting the location of each object, but they ignore the correlation of adjacent objects when they move in traffic networks, and thus may not reflect the realistic traffic scenario.

Despite the wide use of traffic simulation rules in transportation GIS domain [START_REF] Nagel | A cellular automaton model for freeway traffic[END_REF][START_REF] Brinkhof | A framework for generating networkbased moving objects[END_REF], their integration to a database model for objects in constrained networks has never been done before.

Graphs of Cellular Automata Model

We model a road network with a graph of cellular automata (GCA), where the nodes of the graph represent road intersections and the edges represent road segments with no intersections. Different from the general graph model, each edge in the GCA consists of a cellular automaton (CA), which is represented, in a discrete mode, as a finite sequence of cells. Each cell corresponds in practice to some road segment of about 7.5 m. Figure 1 shows an example of a road network and its GCA model. Each node has a label which represents an intersection of the road network. The wide lines represent edges and each edge treated as one CA connects many cells.

The CA model was used in this context by [START_REF] Nagel | A cellular automaton model for freeway traffic[END_REF]. We first recall the definition of cellular automaton.

Definition 1 A cellular automaton consists of a finite oriented sequence of cells. In a configuration, each cell is either empty or contains a symbol. During a transition, symbols can move forward to subsequent cells, symbols can leave the CA and new symbols can enter the CA.

An example of cellular automaton corresponding to edge (N 1 , N 2 ) in Figure 1(b) with a transition between two configurations is given in Figure 2. We now formally define a graph of cellular automata.

Definition 2

The structure of a GCA is a directed weighted graph G = (V, E, l) where V is a set of vertices (i.e., nodes), E is a set of edges and l : E → N is a function which associates to each edge the number of cells of the corresponding cellular automaton.

We assume a countably infinite alphabet Ω : {α, β, γ, • • •}, denoting moving objects' names. Let C be the set of cells of a GCA.

A configuration or an instance of a GCA, is a mapping from the cells of the GCA to constants in Ω together with a given velocity. Intuitively, the velocity is the number of cells an object can traverse during a time unit.

Definition 3 An instance I of a GCA is defined by two functions:

µ

: C → Ω {ε} (1-1 mapping) v : Ω → N.
A moving object is represented as a symbol attached to the cell in the GCA and it can move several cells ahead at each time unit. Figure 1(b) is an instance of the GCA corresponding to the road network of Figure 1(a). In Figure 1(b), moving objects are denoted by squares. A moving object lies on exactly one cell of the edge and its location can be obtained by computing the number of cells relative to the start node. For instance, object α lies on the edge (N 1 , N 2 ) and there are two cells away from N 1 along the edge. Therefore, its position can be expressed by (N 1 , N 2 , 2).

The motion of an object is represented as some (time, location) information. Representing such information of a moving object as a trajectory is a typical approach [START_REF] Vazirgiannis | A Spatiotemporal Model and Language for Moving Objects on Road Networks[END_REF]. In the GCA model, the trajectory of a moving object can be divided two types: the in-edge trajectory for the object's movement in one edge (CA) and the global trajectory for the object that may move cross several edges (CAs) during its movement. The in-edge trajectory of an object is a polyline in two-dimensional space (one-dimensional relative distance, plus time), which can be defined as follows:

Definition 4 The in-edge trajectory of a moving object in a CA of length L is a piece-wise function f : T → N, represented as a sequence of points (t 1 , l 1 ), (t 2 , l 2 ), . . . , (t n , l n )(t 1 < t 2 < . . . < t n , l 1 < l 2 < . . . < l n ≤ L).
When an object moves across multiple edges, its global trajectory is defined as functions mapping the time to the edge and relative distance.

Definition 5 The global trajectory of a moving object in different CAs is a piece-wise function f :

T → (E, N), represented as a sequence of points (t 1 , e 1 , l 1 ), . . . , (t i , e j , l k ), . . . , (t z , e m , l n )(t 1 < t 2 < . . . < t z ).

In the sequel, we will be interested by deterministic paths in the GCA i.e., path with source nodes of out degree 1. The successive CAs in a deterministic path can be then seen as a unique CA.

Let i be an object moving along an edge. Let v(i) be its velocity, x(i) its position, gap(i) the number of empty cells ahead (forward gap), and P d (i) a randomized slowdown rate which specifies the probability it slows down. We assume that V max is the maximum velocity of moving objects. The position and velocity of each object might change at each transition as shown definition 6 adapted from [START_REF] Nagel | A cellular automaton model for freeway traffic[END_REF]. Definition 6 At each transition of the GCA, each object changes velocity and position in a CA of length L according to the rules below:

1. if v(i) < V max and v(i) < gap(i) then v(i) ← v(i)+1 2. if v(i) > gap(i) then v(i) ← gap(i)
3. if v(i) > 0 and rand() < P d (i) then v(i) ← v(i) -1 4. if (x(i) + v(i)) ≤ L then x(i) ← x(i) + v(i)
The first rule represents linear acceleration until the object reaches the maximum speed V max . The second rule ensures that if there is another object in front of the current object, it will slow down in order to avoid collision. In the third rule, the P d (i) models erratic movement behavior. Finally, the new position of object i is given by the fourth rule as the sum of the previous position with the new velocity if it is in the CA. Note that it is easy to extend the definition of transition to deterministic paths. Because of deterministic path, the objects move to a new position in a subsequent CA. Figure 2 shows the simulated movement of objects on a cellular automaton of the GCA in two consecutive timestamps. We can see that at time t, the speed of the object a is smaller than the gap (i.e. the number of cells between the object a and b). On the other hand, the object b will reduce its speed to the size of the gap. According to the fourth rule, the objects move to the corresponding positions based on their speeds at time t + 1.

However, objects in real traffic have different desired speed. With the transitions of the GCA of one lane CA mentioned above, it can be found that slow objects being followed by faster ones, and the average speed reduced to the free-flow speed of the slowest object [START_REF] Nagatani | Bunching of cars in asymmetric exclusion models for freeway traffic[END_REF]. In view of this, we extend the one lane GCA to two lane GCA in which a CA consists of two parallel single lane. Therefore, each cell in two lane GCA is composed of two parallel single lane and each lane may contain one symbol namely a moving object. The function µ in a GCA instance I will change to the 1-2 mapping accordingly.

For the transition of GCA with one lane, we extend it to the two lane by attaching an additional rule that models the changing of lanes of the object. Suppose the objects move only sideways, the transition of GCA happens on both lanes according to the previous four rules and then the exchange of objects between two lanes is checked according to the additional conditions for changing lane as follows: In fact, the changing lane rule is based on the following observation: the car looks ahead if some car is in its way; the car looks on the other lane if it is any better there; the car looks back on the other lane if it would get in other cars way. Generally, in the above rule, both p and p o are essentially proportional to the velocity, whereas looking back depends mostly on the expected velocity of other objects, not on one's own. An example of invoking the rule of changing lane with

p = v + 1, p o = p, p o,b = v max , P c = 1 is given in

Trajectory Prediction

In the management of moving objects, the trajectory prediction method is usually used to improve the performance of the location update strategy and to support the predictive index and queries. In this part, we first review some linear prediction methods and analyze their problem in handling moving objects in constrained networks, and finally present our simulation-based prediction method.

The Linear Prediction (LP)

Most current index and query processing approaches use the linear prediction method for its simplicity and capability of approximating any curve of free movement by piecewise linear segments. Suppose the trajectory function for an object between time t 0 and t 1 is

X t = X t0 + V (t -t 0 ) (t 0 ≤ t ≤ t 1 )
where X t0 denotes the position of the object at time t 0 and V denotes the velocity of the object, which is assumed to remain fixed between t 0 to t 1 .

General LP The general linear prediction method uses the object's current position X t0 and current velocity V to predict its position in the near future. When the prediction is deemed inaccurate, that is, its deviation from the actual position is beyond a predefined threshold, we revise our prediction by resetting X t0 and V . In situations where object's velocity remains largely constant, this method enables us to make future prediction with high precision. However, when objects move with changing velocity, their trajectory functions have to be revised frequently.

Road Segment Based LP If objects move in a constrained environment such as a transportation network, we can use the road segments of the network to help model the object's movement. In other words, we assume objects move at constant speed along a road segment, that is, their trajectory functions will not change until they move out of a road segment. When an object enters a new road segment, we reset the velocity V in its trajectory function. The frequency of revising the trajectory function depends on the average length of the road segments.

Route Based LP If objects have regular and known routes in the transportation network (e.g., one takes the same route from home to work), we can use the routes instead of the road segments to reduce the number of updates needed to maintain the objects' position. If the route is predicted incorrectly, we simply make an additional update. However, any real traffic system has a stochastic, dynamic and fuzzy nature. The accuracy of linear prediction methods mentioned above is inadequate because linear methods can hardly reflect the movement of objects constrained by road networks. For example, in urban road networks, because of traffic conditions, a vehicle may travel at a constant speed, decelerate to stop, wait, accelerate and travel again at a constant speed. Vehicles may often repeat the above movement in modern urban road networks.

We use Figure 4 to demonstrate the inadequacy of the linear prediction method for real road networks. Figure 4(a) shows the predicted (linear) trajectory and the actual trajectory of an object. We can see that each time the change of the object's velocity is above a certain threshold, an update is triggered and the trajectory is revised by a new velocity vector. The frequent changes of the object's velocity will incur repeated update and prediction.

The Simulation-based Prediction (SP)

Considering the simulation feature of the GCA model, we use GCAs not only to model road networks, but also to simulate future trajectories of moving objects by the transitions of GCAs, where objects' movement follows traffic rules. Based on the GCA, a Simulation-based Prediction (SP) method to anticipate future trajectories of moving objects is proposed. The SP method treats the object's simulated results as its predicted positions to obtain its future in-edge trajectory. To refine the accuracy, based on different assumptions on the traffic conditions we simulate two future trajectories in discrete points for each object on its edge. Then, by linear regression and translating, the trajectory bounds that contain all possible future positions of a moving object on that edge can be obtained. When the object moves to another edge in the GCA or the predicted position exceeds its actual position above the predefined accuracy, another simulation and regression will be executed to predict new future trajectory bounds. The process of the simulation-based prediction can be seen in Figure 5.

Most existing work uses the CA model for traffic flow simulation in which the parameter P d (i) is treated as a random variable to reflect the stochastic, dynamic nature of traffic system. However, we extend this model for predicting the future trajectories of objects by setting P d (i) to values that model different traffic conditions. For example, laminar traffic can be simulated with P d (i) set to 0 or a small value, and the congestion can be simulated with a larger P d (i). By giving P d (i) two values, we can derive two future trajectories, which describe, respectively, the fastest and slowest movements of objects as showed in Figure 5(a). In other words, the object's future locations are most probably bounded by these two trajectories. The value of P d (i) can be obtained by the experiences or by sampling from the given dataset. Our experiments show one of methods to choose the value of P d (i). It is proved that 0 and 0.1 are realistic values of P d (i) in our cases.

For getting the future trajectory function of an object from the simulated discrete points, we need to regress the discrete positions. We find that in most cases the linear regression (as shown in Figure 4b) fits the prediction well and at low cost. The OLSE (Ordinary Least Square Estimation) method, for example, can be calculated efficiently with low data storage cost. Let the discrete simulated points be (t 1 , d 1 ), . . . , (t i , d i ), . . . , (t n , d n ), where d i (i ∈ [1, n]) denotes the relative distance in an edge and the average value be t and d. After regression, the trajectory function of the moving object is:

D(t) = β0 + β1 • t
where βo and β1 are given by:

β0 = d -β1 • t
β1 = n i=1 t i d i -nt • d n i=1 t 2 i -n(t) 2
In Figure 5(a), the dashed curves show two future trajectories, which are the slowest and the fastest movements simulated by using different P d . Applying the OLSE algorithm to the two trajectories generates two linear functions, which are shown in solid lines.

fastTrj : D(t) = α f • t + γ f slowTrj : D(t) = α s • t + γ s
Finally, in order to find the bounds of the area that contains all estimated future positions, we translate the two regression lines, until all estimated future positions fall within. More specifically, we translate the upper line (fastest movement) upwards until it touches the point with the max residual (denoting ǫ 1 the distance translated upward), and similarly, we translate the lower line (slowest movement) downwards (denoting ǫ 2 the distance translated downward). This minimizes the loss of information and errors brought by the OLSE algorithm.

We now define the two bound lines as the upper bound and lower bound of objects' future trajectory.

Definition 7

The upper bound of an object trajectory upperBound is the upper bound line of its fastest future trajectory, and the lower bound lowerBound is the lower bound line of its slowest future trajectory. They are linear functions of the following form:

upperBound : D(t) = α f • t + λ f lowerBound : D(t) = α s • t + λ s where λ f = γ f + ǫ 1 , λ s = γ s -ǫ 2 .
The two bound lines are shown in Figure 5(b). we can treat the two predicted lines as the bounds of the possible future positions of one object. The predicted trajectory bounds can be used in the predictive index structure and query processing in road network to reduce the index updates and filter unnecessary query results to improve the However, for other applications such as the tracking of moving objects, a single predicted function is needed to obtain the specific future positions of the object. For example, to lower update frequency from moving objects to server database, a general principle for location update policies is as follows: the moving objects equipped by GPS receiver do not report their locations to the server unless their actual positions exceed the predicted positions to a certain threshold. Their predicted positions need to be computed by a single predicted function. In this case, we can also adapt the SP method to obtain a compact and simple linear prediction function. The process can be seen in Figure 6. After regressing the two simulated future trajectories to two linear function denoting L 1 and L 2 , we compute the middle straight line L 3 , the bisector of the angle a between L 1 and L 2 as the final predicted function L(t).

Although the predicted function obtained by the SP method is a simple linear function, it is different from the linear prediction in that the SP method not only considers the speed and direction of each moving object, but also takes correlation of objects as well as the stochastic behavior of the traffic into account. The experimental results also show it is a more accurate and effective prediction approach.

As the prediction of in-edge trajectory only use the GCA to simulate the movement of objects in an edge, we have to consider the cases when objects move across the nodes in order to make the global trajectory prediction. If the out degree of a node in the GCA is one, the behavior of the object in the adjacent edge is the same. However, if the out degree of the node is bigger than one, we can not trace the objects cross the different edges. In this case, we could use the probability of objects changing the edges according to the historical data. In this paper, we only predict the in-edge trajectory of the object moving in one edge of the GCA. When the object moves to another edge or its prediction accuracy of the future positions cannot arrive the given accuracy requirement, we issue another prediction based on the current traffic conditions.

Experimental Evaluation

We evaluate the simulation-based prediction method by comparing it with the general linear prediction method. Using two datasets (generated by the CA simulator and by the Brinkhoff's Network-based Generator [START_REF] Brinkhof | A framework for generating networkbased moving objects[END_REF]), we measure their prediction accuracy when applied to predict the near anticipated future positions in the real map network. We also study the effect of the choice of different values of the parameter P d on the simulation-base prediction.

Datasets

We use two datasets for our experiments. The first is generated by the CA simulator, and the second by the Brinkhoff's Network-based Generator [START_REF] Brinkhof | A framework for generating networkbased moving objects[END_REF]. We use the CA traffic simulator to generate a given number of objects in a uniform network of size 10000 × 10000 consisting of 500 edges. Each object has its route and is initially placed at a random position on its route. The initial velocities of the objects follow a uniform random distribution in the range [0, 30]. The location and velocity of every object is updated at each time-stamp.

The Brinkhoff's Network-based Generator has been used as a popular benchmark in the related work of the MOD. The generator takes a map of a real road network as input (our experiment is based on the map of Oldenburg including 7035 edges). The positions of the objects are given in two dimensional X-Y coordinates. We transform them to the form of (edgeid, pos), where edgeid denotes the edge identifier and pos denotes relative position on the edge. The generator places a given number of objects at random positions on the road network, and updates their locations at each time-stamp. Each object has its own destination, and it moves toward its destination along a given route.

Prediction Accuracy and Cost

We compare the precision of the SP method with the LP method. We measure the prediction accuracy by "average error" but with different threshold. The threshold represents the maximum deviation between the predicted locations of a moving object and its real locations allowed in the prediction. That means when the deviation exceeds the threshold, we make another prediction. From Figure 8, we observe that average error will increase when threshold increases. This is because the larger the threshold is, the larger the deviation becomes, which leads to the more errors. This is tenable in both the LP and SP method. However, the SP method predicts more accurately than the LP method with any threshold. The time complexity of the simulation-based prediction depends on many factors. We compute the average CPU time when simulating and predicting the movement of one object along the edge with length 1000 in different dataset sizes. The results show that the average cost of one simulation-based prediction is about 0.25ms. This is quite acceptable.

The Slowdown Rate P d

The CA simulation has an important effect on the accuracy of the simulation-based prediction. We study the effect of the choice of different P d , which determines the two predicted trajectories corresponding to the fastest and slowest movement. We test on the Brinkhoff dataset with different data size and use P d from 0 to 0.5 and measure the average prediction accuracy by "average error" and "overflow rate". The average error is the average absolute error between the predicted and actual positions, and the overflow rate represents the probability of predicted positions exceeding the actual positions. The purpose of this metric is to find the closest two trajectories binding the actual one as future trajectories. In this way, we can choose the P d both with lower average error and overflow rate. Figure 8 shows the prediction accuracy of the SP method with different slowdown rates. We can see that when P d is set to 0 and 0.1, both the average error and overflow rate are lower than others. Therefore, we use the value 0 and 0.1 as slowdown rates for the fastest movement bound and the slowest movement bound to obtain better prediction results.

Conclusion

Managing moving objects in a constrained network is a challenging task as well as of great practical importance in mobile location-aware applications. It is necessary to represent and predict the future trajectories of moving objects more accurate. In this paper, we first combine road network representation and the movement model of objects in a traffic network to introduce a new model -GCA for networkconstrained moving objects. And then we propose a prediction method, based on the GCA, which predicts with a great accuracy the future trajectories of moving objects. The accuracy results from the fact that the GCA model exploits the constraints of the network and models the stochastic aspect of urban traffic. Our experimental results performed on two datasets show that the prediction accuracy of our simulation-based prediction is higher than the linear prediction used in the predictive indexing and query processing.

Figure 1 :

 1 Figure 1: An example of a road network and its GCA model

Figure 2 :

 2 Figure 2: Transition of the GCA

5 .Figure 3 :

 53 Figure 3: An example of changing lane in transition of the two lane GCA

Figure 3 .

 3 The object b with p = 3, p o = 3, p o,b = 5 changes to the other lane in the GCA due to satisfying the fifth rule mentioned above.

  General Linear Prediction (b) Simulation-based Prediction

Figure 4 :

 4 Figure 4: Linear Prediction VS. Simulation-based Prediction

Figure 5 :

 5 Figure 5: Two Predicted Bounds of Future Trajectories

Figure 7 :

 7 Figure 7: Prediction Accuracy with Different Threshold

Figure 8 :

 8 Figure 8: Prediction Accuracy with Different P d

  Singe Predicted Future Trajectory performance of predictive query. For example, given a predictive range query with the specified region R during time interval [t 1 , t 2 ] in the future, we can filter the objects in the result during the pre-process phase if the area between their upper and lower trajectory bounds can not intersect the R during [t 1 , t 2 ].

	d	simulated trajectory regress function	d	predicted function simulated trajectory	L1	L3	L2
		fastest		fastest
		movement		movement
		slowest movement		slowest movement
				a
		t				t
		(a) Simulated trajectories	(b) Single predicted function
		Figure 6:

Acknowledgment

This research was partially supported by the grants from the Natural Science Foundation of China under grant number 60573091, 60273018; the Key Project of Ministry of Education of China under Grant No.03044; Program for New Century Excellent Talents in University (NCET); Program for Creative PhD Thesis in University and performed in the framework of a joint project with INRIA. The authors would like to thank Zhen Xiao, Benzhao Li from Information school, Renmin University of China for the assistance of experimental evaluation and Karine Zeitouni from PRISM, Versailles Saint-Quentin University in France for many helpful advice and assistance.


Line Jakubiec-Jamet

Ontology in Coq for a Guided Message Composition

Natural language generation is based on messages that represent meanings, and goals that are the usual starting points for communicate. How to help people to provide this conceptual input or, in other words, how to communicate thoughts to the computer? In order to express something, one needs to have something to express as an idea, a thought or a concept. The question is how to represent this. In 2009, Michael Zock, Paul Sabatier and Line Jakubiec-Jamet suggested the building of a resource composed of a linguistically motivated ontology, a dictionary and a graph generator. The ontology guides the user to choose among a set of concepts (or words) to build the message from; the dictionary provides knowledge of how to link the chosen elements to yield a message (compositional rules); the graph generator displays the output in visual form (message graph representing the user's input). While the goal of the ontology is to generate (or analyse) sentences and to guide message composition (what to say), the graph's function is to show at an intermediate level the result of the encoding process. The Illico system already proposes a way to help a user for generating (or analyzing) sentences and guiding their composition. Another system, the Drill Tutor, is an exercise generator whose goal is to help people to become fluent in a foreign language. It helps people (users have to make choices from the interface in order to build their messages) to produce a sentence expressing a message from an idea (or a concept) to its linguistic realization (or a correct sentence given in a foreign language). These two systems led us to consider the representation of the conceptual information into a symbolic language; this representation is encoded in a logic system in order to automatically check conceptual well-formedness of messages. This logic system is the Coq system used here only for its high level language. Coq is based on a typed λ-calculus. It is used for analysing conceptual input interpreted as types and also for specifying general definitions representing messages. These definitions are typed and they will be instanciated for type-checking the conceptual well-formedness of messages.

Introduction

Natural language generation is typically based on messages, i.e. meanings, and goals, the usual starting points. We present our views on how to help people to provide this kind of input. Guiding a user to compose sentences can be done in many ways, a lot depending on the user's knowledge state. 1 We will present here Illico (Pasero and Sabatier) 2 , some of its shortcomings and our solution. Illico can be helpful in many ways. For example, it can analyze and synthesize expressions (words, phrases, clauses, sentences), as well as offer possible continuations for a sentence that has not been completed yet, whatever the reasons may be (lexical, syntactic, semantic, conceptual or contextual). All the suggestions made by the system are possible expressions fitting into this place and being in line with the constraints at hand. To achieve this goal a powerful mechanism is used to process in parallel knowledge of different sorts (lexical, syntactic, semantic, conceptual and even contextual ones).

Written in Prolog, Illico's engine is based on a mechanism of coroutine processing. Both for analysis and synthesis, it checks and executes the different constraints (lexical, syntactic, semantic, conceptual and contextual) as soon as the structures of the different representations on which they apply are built, the process being dynamic and taking place in parallel. Representations are processed non deterministically in a top-down manner. The implemented strategy is powerful enough to allow for analysis and synthesis to be simultaneously performed in a single pass. The same principle is used for guiding composition incrementally, i.e. by means of partial synthesis. 1 The problem we are dealing with here is search. Obviously, knowledge available at the onset (cognitive state) plays also a very important role in this kind of task, regardless of the goal (determine conceptual input, lexical access, etc.). Search strategies and relative ease of finding a given piece of information (concept, word) depend crucially on the nature of the input (knowledge available) and the distance between the latter and a given output (target word). Imagine that your target word were 'guy' while you've started search from any of the following inputs: 'cat' (synonyme), 'person' (more general term), or 'gars' (equivalent word in French).

Obviously, the type of search and ease of access would not be the same. The nature and number of items among which to choose would be different in each case. The influence of formally similar, i.e. close words ('libreria' in Spanish vs. 'library' in English) is well known. Cognates tend to prime each other, a fact that depending on the circumstances can be helpful or sheer nuisance. 2 For more details and references concerning Illico and its applications (natural language interfaces to knowledge bases, simultaneous composition of sentences in different languages, linguistic games for language learning, communication aid for disabled people, software for language rehabilitation, etc.) you may want to take a look at http://pageperso.lif.univ-mrs.fr/ ~paul.sabatier/ILLICO/illico. html.

Fig. 1. Illico Screen Printing

If you want to compose a sentence step-by-step, from left to right, Illico automatically and dynamically offers at each step a list of candidates for continuing the sentence built so far. Figure 1 illustrates this mode. Having reached a certain point in the chain ("The child takes a picture of the...") the user is waiting for suggestions to be made by the system. Offering possible continuations is but one way among others to assist a user in sentence composition. One can imagine richer kind of assistance where the user accesses various kinds of knowledge (linguistic, conceptual, etc.) to select then the one fitting best his communicative goals.

This aspect could concretely help a user in sentence composition to be fluent in a foreign language. Becoming fluent in a language requires not only learning words and methods for accessing them quickly, but also learning how to place them and how to make the necessary morphological adjustments. The Drill Tutor [START_REF] Zock | A Generic Tool for Creating and Using Multilingual Phrasebooks[END_REF] aims to help people to produce a sentence expressing some message. In the system, the user chooses the goal of communication (to introduce someone for example). The goals is tree-structured. The user can either drill down to a given goal by clicking on a goal name to expand the sub-goals until a pattern is displayed, or search for them via a term because goals are indexed. The Drill Tutor gets from the starting point, the goal, to its linguistic realization. The system presents sequentially:

1. a model: the user chooses one of the patterns proposed by the system (a pattern is a general sentence needing to be instanciated; for example, to introduce someone, one can use the model: This is <title><name> or That is <title><name> from <origin>); 2. the stimulus (chosen word): this step allows the instanciation of the chosen pattern. For example, for <title>, the user can use Mr, Mrs, Dr., Professor, and for <origin>, he can choose Japan, Germany, France; 3. the user's answer and the system's confirmation: the system has now all the information needed to create the sentence (or the exercise) expressing the conceptual input. Finally, a set of possible outputs representing the message is depicted on the screen and the user can express his message.

This approach is much more economical for storing and accessing patterns, than storing a pattern for every morphological variant. This approach also allows faster authoring, i.e., message building, than long-winded navigation through a conceptual ontology (for more details see [START_REF] Zock | Using e-learning to achieve fluency in foreign languages[END_REF]).

Limitation of sentence completion or the need of controlling conceptual input

The objectives of sentence completion systems are different from those of conventional surface generators [START_REF] Reiter | Building Natural Language Generation Systems[END_REF][START_REF] Bateman | Natural language generation[END_REF]. The latter start from a goal and a set of messages (input) in order to produce the corresponding surface form (output). Working quietly in the background, Illico tries to be pro-active, making reasonable guesses about what the author could say next. Hence, it supposes somehow that the author knows at least to some extent what he is/was going to say3 . Illico performs analysis by synthesis (top-down strategy) and, while it does not need any help from the user for analysis, it does so for synthesis, as, otherwise, it would produce unreasonably large sets of possible continuations, most of which do not even correspond to the users' intention. Figure 1 should give you a rough idea of how Illico works. You'll see basically three windows with, at the bottom, the output produced so far (generally an incomplete sentence, here: the child takes a picture of the); at the very left, the candidates for the next slot (apple, beer, brother, ...) and in the main frame, various kinds of representation, like the system's underlying ontology, pragmatic, semantic and syntactic information concerning the sentence in the making.

Offering rich assistance during sentence composition was not the main goal of the designers of Illico. The production of possible continuations is but one functionality among others, though a very useful one4 and easily implemented due to the power of Prolog's core mechanisms.

A system providing more sofisticated assistance system would look quite a bit differently: (a) the nodes of the tree would be categories (types) rather than instances (words), the latter being shown only at the leave-level; (b) frequency would be taken into account (the words' likelihood varying with the topic); (c) governors (eg. nouns) would precede their dependants (eg. determiners, adjectives), and (d) variables would be used rather than extensive lists of possible morphological values, etc.

Another problem linked to set size (i.e. great number of words from which to choose) is the fact that large sets tend to be distracting and to cause forgetting. Indeed, as the number of candidates grows (as is typically the case at the beginning of a clause) the danger to get drowned. Likewise, with the distance between the governor and its dependant increasing, grows the danger to end up producing something that, while in line with the language, does not correspond anymore to what one had in mind. Memory and divided attention have taken their toll. In order to avoid this, we suggest to determine the governing elements first and to keep the set of data from which to choose small. In other words, filtering and navigation become a critical issue and there are at least two ways to deal with them.

In order to reduce the number of candidates from which to choose, one can filter out linguistically and conceptually irrelevant material. This strategy is generally used both by the speaker and the listener as long as optimal transmission of information, i.e. reasonable input/output are considered as a

Step 1: Zidane...

Idea object •comm. status •definite •indefinite •number •singular •plural •person •place •thing •coordinate •subordinate •size •color •shape • nationality •degree •manner •frequency Z Z I I D DA AN NE E
Step 2: ...hammered the ball... Step 3: ...straight into the net.

Fig. 2. An Interactive Graph Editor for Incremental Message Composition

major means to achieve a given communication goal (default case). Hearing someone say: "I'd love to smoke a....", our mind or ears will be "tuned" to smokeable items (cigar, cigarette, pipe) rather than to any noun, no matter how correct all of them may be from a syntactic point of view. With regard to our problem (sentence completion or message composition) this means that the list to be presented should be small and contain but "reasonable" items5 . How can this be achieved without sacrificing coverage? Indeed, even a filtered list can still be quite large. Imagine that you were to talk about people, food, or a day of the year, etc. The number of representatives of each category is far too big to allow for fast identification, if the candidates are presented extensively in an unstructured or only alphabetically structured list. This can be avoided and navigation can considerably be eased by categorizing items, presenting them as a conceptually structured tree (type hierarchy) rather than as a flat list. Instead of operating at the concrete level of instances (all days of the year) the user will now operate (navigate or choose) at a much higher level, using more abstract words (generic concepts, type names, hyperonymes) like month, weekdays, hour, etc. Of course, ultimately he will have to choose one of the concrete instances, but having eliminated rapidly, i.e. via categories, most of the irrelevant data, he will now choose from a much smaller list. The gain is obvious in terms of storage (at the interface level) and speed of navigation.

Incremental building and refining a message graph

To show what we have in mind, take a look at figure 2. It is reminiscient of SWIM, an ontology-driven interactive sentence generator [START_REF] Zock | Swim or sink: the problem of communicating thought[END_REF]. Let's see how this is meant to work. Suppose you were to produce the underlying message of the following sentence "Zidane hammered the ball straight into the net". This would require several walks through the conceptual network, one for each major category (Zidane, hammer, ball, straight, net) 6 . The path for "Zidane" would be "scene/idea/objects/entity/person", while the one for the shooting-act would be "scene/idea/relation/action/verb". Concerning this yet-to-be-built resource, various questions arise concerning the components (nature), their building and usage. The three problems are somehow related. What are the components? In order to allow for the interactive building of the message graph we will need three components: a linguistically motivated ontology, a dictionary and a graph generator. The ontology is needed for guiding the user to make his choices concerning the elements to build the message from concepts/words. The fact that the user has chosen a set of building blocks (concepts, i.e. class names, or words) does not mean that we have a message. At this point we have only a set of elements which still need to be connected to form a coherent whole (conceptual structure or message graph). To this end the system might need additional information and knowledge. Part of this can be put into the dictionary. Hence, nouns can be specified in terms of subcategorial information (animate, human, etc.), verbs in terms of case-frames and roles, etc. These kinds of restrictions should allow the connection of the proper arguments, for example, baby and milk, to a verb like drink. The argument connected via the link agent is necessarily animate, the information being stated in the lexicon. In spite of all this, the system still cannot build the graph (suppose the user had given only the equivalent of two nouns and two adjectives), it will engage in a clarification dialogue, asking the user to specify which attribute qualifies which object. Once all objects (nodes) are linked, the result still needs to be displayed. This is accomplished via the graph generator which, parallel to the input, incrementally displays the message structure in the making.

How to use the resource? Obviously, as the ontology or conceptual tree grows, access time increases, or more precisely, the number of elements from which to choose to reach the terminal level (words). In addition, the metalanguage (class names) will become more and more idiosyncratic. Both of these consequences are shortcomings which should definitely be avoided. This could be done in several ways: (1) allow the message to be input in the user's mother tongue. Of course, this poses other problems: lexical ambiguity, structural mismatches between the source and the target language; (2) start navigation at any level. Indeed, when producing a sentence like, "give me a cigarette", hardly anyone would start at the root level, to reach eventually the level of the desired object. Most people would immediately start from the hyperonym or base level; (3) allow access via the words' initial letters, or, even better, (4) via associatively linked concepts/words. 7 .

7 Suppose you were looking for the word mocha (target word: tw), yet the only token coming to your mind were computer (source word: sw). Taking this latter as starting point, the system would show all the connected words, for example, Java, Perl, Prolog (programing languages), mouse, printer (hardware), Mac, PC (type of machines), etc. querying the user to decide on the direction of search by choosing one of these words. After all, s/he knows best which of them comes closest to the tw. Having started from the sw 'computer', and knowing that the tw is neither some kind of software nor a type of computer, s/he would probably choose Java, which is not only a programming language but also an island. Taking this latter as the new starting point s/he might choose coffee (since s/he is looking for some kind of beverage, possibly made from an ingredient produced in Java, coffee), and finally mocha, a type of beverage made from these beans. Of course, the word Java might just as well trigger Kawa which not only rhymes with the Last, but not least, there is no good reason to have the user give all the details necessary to reach the leaf-, i.e. word-level. He could stop anywhere in the hierarchy, providing details later on. This being so, he can combine breadth-first and depth-first strategies, depending on his knowledge states and needs. Obviously, the less specific the input, the larger the number of words from which we must choose later on. Yet, this is not necessarily a shortcoming, quite the contrary. It is a quality, since users can now decide whether they want to concentrate first on the big picture (general structure or frame of the idea) or rather on the low level details (which specific words to use). Full lexical specification is probably not even wanted, as it is not only tiresome as soon as the ontology grows (imagine the time it might take just to produce the conceptual equivalent to a message like 'a beer, please!'), but also it may pose problems later on (surface generation), as the words occurring in the message graph might not be syntactically compatible with each other. Hence, we will be blocked, facing a problem of expressibility [START_REF] Meteer | Expressibility and the Problem of Efficient Text Planning[END_REF].

Conceptual, computational and psychological issues

Building the kind of editor we have in mind is not a trivial issue and various problems need be addressed and solved:

• coverage: obviously, the bigger the coverage, the more complex the task.

For practical reasons we shall start with a small domain (soccer), as we can rely already on a good set of resources both in terms of the ontology and the corresponding dictionary [START_REF] Sabatier | Un lexique-grammaire du football[END_REF]. Kicktionary, developped by Thomas Schmidt (http://www.kicktionary.de/Introduction.html), is a domain-specific trilingual (English, German, and French) lexical resource of the language of soccer. It is based on Fillmore's Frame Semantics [START_REF] Baker | The berkeley framenet project[END_REF] and uses WordNet style semantic relations [START_REF]WordNet: An Electronic Lexical Database and some of its Applications[END_REF] as an additional layer to structure the conceptual level. • language specificity: there are good reasons to believe that the conceptual tree will be language dependant. Think of Spanish or Russian where verb-form depends on aspect, that is, on the speaker's choice of considering an action as completed, i.e perfective, or not, yielding two, morphologically speaking, entirely different lemmas (ser/estar, meaning to be in Spanish, or "uchodits" vs "uitsi" to walk in Russian). • ergonomic aspects (readability): the graph's readability will become an issue as soon as messages grow big. Imagine the underlying graph of a multiple embedded relative-clause. Also, rather than frightening the user by showing him the entire tree of figure 2, we intend to show only the useful (don't drown the user), for example, the children nodes for a given choice.

sw, but also evokes Kawa Igen, a javanese volcano, or familiar word of coffee in French. For more details, see [START_REF] Zock | Lexical access based on underspecified input[END_REF].

• the limits of symbolic representation: as shown elsewhere for time [START_REF] Ligozat | How to visualize time, tense and aspect[END_REF] and space [START_REF] Briffault | What do we mean when we say to the left or to the right? how to learn about space by building and exploring a microworld[END_REF], symbolic representations can be quite cumbersome. Just think of gradient phenomena like colors or sounds, which are much easier represented analogically (for example, in terms of a colorwheel) than categorially. • the problem of metalanguage: we will discourage the user if learning the target language is only possible by learning yet another (meta) language.

• the conceptual tree: there are basically two issues at stake: which categories to put into the tree and where to place them. Indeed, there are various problematic points in figure 2. Where shall we put negation? Shall we factor it out, or put it at every node where it is needed?

There are several other issues that we have hardly touched upon, yet they are all relevant for natural language generation, in particular for interactive language generation which is our case:

1. in what terms to encode the message (concepts vs. words), 2. at what level of abstraction (general vs. specific); 3. size of the planning unit (concepts vs. messages); 4. processing strategy: is planning done as a one-shot process or is it performed in various steps, i.e. incrementally?; 5. direction: is planning done left to right or top to bottom? 6. processing order. Do thoughts precede language, and if so, is this always the case?

We will touch upon these points here only very briefly (for more details see [START_REF] Zock | The power of words in message planning[END_REF]). Let's suppose you wanted to produce the following sentence: When the old man saw the little boy drowning in the river, he went to his canoe in order to rescue him. Obviously, before producing such a sentence its content must be planned and represented somehow, but how is this done? There are several good reasons to believe that this sentence has not been planned entirely in advance, neither from left to right, nor in a single pass.

Psychological reasons: The sentence is simply too long for a speaker to hold all its information in short-term-memory. It is highly unlikely that the speaker has all this information available at the onset of verbalization. The need of planning, that is, the need to look ahead and to plan in general terms, increases with sentence length and with the number and type of embeddings (for example, center embedded sentences). There is also good evidence in the speech error literature for the claim that people plan in abstract terms. False starts or repairs, like "I've turned on the stove switch, I mean the heater switch" suggest that the temperature increasing device has been present in the speakers mind, yet at an abstract level [START_REF] Levelt | Speaking : From Intention to Articulation[END_REF][START_REF] Fromkin | Speech production[END_REF].

Linguistic reasons: as is well known, the order of words does not necessarily parallel the order of thought. For example, the generation of the first word of the sentence here above, the temporal adverbial "when", requires knowledge of the fact that there is another event taking place. Yet, this information appears fairly late in the sentence.

Checking Conceptual Well-formedness

Obviously, messages must be complete and well-formed, and this is something which needs to be checked. The problem of well-formedness is important, not only in systems where a message is built from scratch or from incomplete sentence fragments (ILLICO), but also in message-specification systems8 . Suppose you were to make a comparison, then you must (at least at the beginning) mention the two items to be compared (completeness), and the items must be comparable (well-formedness). In other words, having chosen some predicate, a certain number of specific variables or arguments are activated, waiting for instantiation. Arguments are, however, not only of a specific kind, playing a given role, they also have specific constraints which need to be satisfied. While checking well-formedness for single words does not make sense (apart from spell checking, which is not our concern here), it does make sense to check the compatibility and well-formedness of the combination of concepts or words, to see whether they produce an acceptable conceptual structure.

To illustrate this further, lets take up again the sentence illustrated in Fig. 2, Zidane hammered the ball straight into the net. This means that, having received as input something like to shoot (or, to hammer), we know that there is someone, performing this action, with a specific target in mind (the goal), and that the action can only be performed in so many ways (manner).

While not all of this information is mandatory, some of it is (agent, object, target), and there are definitely certain constraints on the various arguments (the agent must be animate, the object some kind of sphere, typically used in soccer games, etc.). Being formalized and stored in a conceptual dictionary, this information can now be used by our system to check the well formedness of a given structure and its compatibility with the users'input.

The idea according to which types allow well-formedness checking of mathematical objects is well-known. We use them them for a different domain (messages and sentences), because they allow the checking of the adequacy of the elements used to build or complete a message. Having a rigorous representation, we can reason about objects not only to check the well-formedness of the users'input, but also its soundness.

To test this hypothesis we rely on the Coq proof assistant (Coq Development Team 2008) as it allows us to:

• take advantage of its type system and its powerful representation mechanisms: polymorphism, dependent types, higher-order logic...;

• propose natural and general specification;

• check automatically the well-formedness of the users'input.

The Coq system provides a formal language to specify mathematical definitions and prove them. The Coq language implements a higher-order typed λ-calculus, the calculus of constructions. Its logic is constructive and relies on the Curry-Howard isomorphism. Each Coq proposition is of type P rop and describes a predicate. There are also objects of type Set, but they are not used in the context of this work.

Coq allows an hierarchical organization of types via the coercion mechanism. In other words, it contains a mechanism to represent conceptual information in the form of a tree of concept types. We use coercions here to inject terms implicitly from one type into another, which can be viewed as a subtyping mechanism. Given this facility a user may apply an object (which is not a function, but can be coerced to a function) to the coercion, and more generally, consider that a term of type A is of type B, provided that there is a declared coercion between the two.

For example, in Fig. 2 we see that a Scene contains both an Attitude Perspective (speech-act, if you prefer) and an Idea (core part of the message). This is expressed in Coq as follows:

Coercion Attitude_Perspective_is_Scene :

Attitude_Perspective >-> Scene.

Coercion Idea_is_Scene : Idea >-> Scene.

where Attitude Perspective, Idea and Scene are declared as parameters of type Prop. These coercions declare the construction of the conceptual type Scene that can be seen as the composition of an Idea and an Attitude Perspective.

The coercions used for this study are described by an inheritance graph in Coq. Moreover, Coq detects ambiguous paths during the creation of the tree, and it checks the uniform inheritance condition according to which at most one path must be declared between two nodes. The relevant part of the inheritance graph for our example is:

Parameter hammer : Agent -> Object -> Target -> Prop. Parameter Zidane : human. Parameter ball : soccer_instrument. Parameter net : soccer_equipment.

These four parameters describe the variables used in our example of Fig. 2. P rop stands in Coq for the type of proposition. Roles (Agent, Object, T arget) and features (human, soccer instrument, soccer equipment) are generic types. To express conceptual constraints such as Agents must be animate, Coq uses the subtype principle in order to check that all constraints are satisfied, defining human, soccer instrument and soccer equipment respectively as subtypes of Agent, Object and T arget.

When all constraints are satisfied, the semantics of a sentence can be represented, which yields in our case "there is an agent who did something in a specific way, by using some instrument". In other words: "there is a person p, an object o and a target t that are linked via an action performed in a specific way". The user message can be defined generically and typed as follows: This definition is a λ-expression taking as parameters the following variables (type names are referred to via their initial capital):

(λs : A → P )(λo : O → P )(λt : T → P )(λr : A → O → T → P )
Hence, to produce the global message Zidane hammered the ball straight into the net, we must instantiate the composite propositions respectively by is Zidane (of type human → P rop), is ball (of type soccer instrument → P rop), is net (of type soccer equipment → P rop). Hammer is already declared. Once this is done, the parameters Zidane, ball and net can be applied to produce the desired result, the system type-checking the compatibility of the involved parameters.

More generally speaking, checking the conceptual well-formedness and consistency of the messages amounts basically to type-checking the composite elements of the message.

Another approach implemented in Coq allows the formalization of general patterns used for representing sentences. Then, these patterns are instanciated and a semantic analysis of simple sentences can been performed. This analysis relies on a hierarchy of types for type-checking the conceptual well-formedness of sentences in the same spirit of this paper 9 . The motivation for using Coq is to define general representations in order to have a more economical way for storing and analysing sentences that are built according patterns (for more details see [START_REF] Jakubiec-Jamet | A Case-study for the Semantic Analysis of Sentences in Coq[END_REF]). 9 Actually I gratefully acknowledge Michael from many fruitful discussions about this approach. He always has been very attentive to others'works and our collaboration is due to him.

Conclusion and perspectives

The goal of this paper has been to deal with a problem hardly ever addressed in the literature on natural language generation, conceptual input. In order to express something, one needs to have something to express (idea, thought, concept) to begin with (input, meaning). The question is how to represent this something. What are the building blocks and how shall we organize and index them to allow for quick and intuitive access later on? Dealing with interactive sentence generation, we have suggested the building of a linguistically motivated ontology combined with a dictionary and graph generator. While the goal of the ontology is to generate (or analyse) sentences and to guide message composition (what to say), the graph's function is to show at an intermediate level the result of the encoding process. This reduces memory load, allowing at the same time the checking of well formedness. Does the message-graph really encode the author's intention?

Of course, there are many ontologies. Unfortunately, we cannot draw on any of them directly, as they have not been built for message composition. As we have seen, different applications may require different strategies for providing input. In Illico it was driven via an ontology, taking place fairly late. Part of the message was known and expressed, thus, constraining further inputs.

Michael Zock also worked on another message-specification system (the SPB system), a multi-lingual phrasebook designed to convert meanings into speech. In SPB, conceptual input consisted mainly in searching (for existing sentences or patterns) and performing local changes. Rather than starting from scratch, data are accommodated. Given the fact that we have a translation memory, input can be given in any language (mother tongue) we are confortable with, provided that it is part of the translation memory. If there is a translation between two sentences, any element is likely to evoke its equivalent and the sentence in which it occurs in the target language. Obviously, this is a nice feature, as it allows not only for natural input, but also to speed up the authoring process 10 .

In the case of Drill Tutor, conceptual input is distributed over time, specification taking place in three steps: first via the choice of a goal, yielding an abstract, global structure or sentence pattern (steps 1), then via the variables'concrete lexical-and morphological values (steps 2 and 3). In the case of Drill Tutor, input is clearly underspecified at the earliest stage. Messages are gradually refined: starting from a fairly general idea, i.e., sentence pattern, one proceeds gradually to the specifics: lexical and morphological values. This seems a nice feature with respect to managing memory constraints. Many ideas presented here are somehow half-baked, needing maturation, but, as mentioned earlier, conceptual input is an area in Natural Language Generation where more work is badly needed.

  AM M M M E E R R B BA AL LL L v ve er rb ba al li iz ze e r re es st to or re e c ca an nc ce el l c co on nf fi ir rm m

  Parameter is_someone : Agent -> Prop. Parameter is_something : Object -> Prop. Parameter is_manner : Target -> Prop. Parameter relation : Agent -> Object -> Target -> Prop. Definition message := exists p, exists o, exists t, is_someone p/\is_something o/\ is_manner t/\relation p o t.

ve er rb ba al li iz ze e r re es st to or re e c ca an nc ce el l c co on nf fi ir rm m c co op py y a ad dd d m mo ov ve e m mo od di if fy y r re em mo ov ve e l li in nk k Scene Attitude/perspective

	adjective adverb v purpose •size •color •shape • nationality •degree •manner •frequency simple verb action, state, process predicate / relation spatial relation preposition logical relation conjunction modifiers quality / state manner composite (idea) object •comm. status •definite •indefinite •number •singular •plural •coordinate •subordinate tense polarity mood predicate / relation	•grasp •goal •purpose adjective •condition •move •source adverb •past •present positive •ingest •position •consequence •future negative •question • tranf. of poss. • direction • cause •size •degree •manner •color •frequency •shape relation object •statement •command •indicative •subjunctive simple spatial relation logical relation modifiers action, state, process composite (idea)	• nationality preposition conjunction manner quality / state verb tense	•goal •purpose adverb adjective •condition •source •grasp •move •past •present	•position •consequence •ingest •future	• direction • cause • tranf. of poss.

Of course, we can also assume that the author does not even know that. But this is a bit of an extreme case.

For example, it allows the testing of well-formedness and linguistic coverage of the application one is about to develop. This being so, we can check now whether all the produced continuations are expected and none is missing.

This idea is somehow contained in Tesnière's notion of valency [Tes59], in Schank's conceptual dependancy [Sch75] and McCoy and Cheng's discourse focus trees [MC91].

The upper part shows the conceptual building blocks structured as a tree and the lower part contains the result of the choices made so far, that is, the message built up to this point. To simplify matters we have ignored the attitude or speech-act node in the lower part of our figure.

Of course, conceptual well-formedness, i.e. meaningfulness, does not guarantee communicative adequacy. In other words, it does not assure that the message makes sense in the context of a conversion. To achieve this goal additional mechanisms are needed.