Jean-François Landry

Jean-Pierre Dussault

Philippe Mahey

A heuristic-based planner and improved controller for a two-layered approach for the game of billiards

Keywords: Pool, Billiards, Snooker, Game, Simulation, Planning, Strategy, Optimization, Artificial Intelligence

 a two-layered approach was proposed to compute a winning strategy for the game of billiards. AI tools as well as robust optimization routines for noisy environments were combined to plan the sequence of shots. We complete here the modelling by introducing significant developments for the high-level planner which guides the precise optimal controller to generate a plan given any random initial state. We will first resume the general model for this particular class of problems and then propose several domain-specific heuristics to guide our search and render the problem tractable. Several improvements to the optimal robust controller including refinements in the objective function will also be presented in order to improve single-shot optimization. Results are presented demonstrating the full potential of the methods proposed making it the state of the art in regards to the game of billiards.

Introduction

The game of billiards is a game of skill, tactics and ingenuity. It has been played all over the world for countless years and is even officially recognized as an Olympic sport by the International Olympic Committee. It has also been the focus of many recent projects in the research community. The engineering challenge to create a robot precise enough to compete and even win against the best professional players is a very strong motivation for the field of robotics. Many projects have been developed from the mid 1990s to today, (see [START_REF] Michael Greenspan | Toward a competitive pool-playing robot[END_REF], [START_REF] Long | Robotic pool: An experiment in automatic potting[END_REF], [START_REF] Chyi | Pool balls identification and calibration for a pool robot[END_REF], [START_REF] Cheng | Design of the neural-fuzzy compensator for a billiard robot[END_REF], [START_REF] Mohammad Ebne Alian | Robotshark: a gantry pool player robot[END_REF], [START_REF] William | Automating Skills Using a Robot Snooker Player[END_REF] [2], [START_REF] Nierhoff | Playing pool with a dual-armed robot[END_REF]) with approaches ranging from a robotic arm set-up on a gantry over a table to a standalone robot moving freely around. Another interesting aspect which was investigated was the usage of augmented reality tools to help guide and teach new players how to play the game or better select shots on the table. Efforts have been made in [START_REF] Bo Larsen | Multi modal user interaction in an automatic pool trainer[END_REF] and [START_REF] Hammond | A computer vision tangible user interface for mixed reality billiards[END_REF] with interesting results. Some work has even been done in video analysis in [START_REF] Rea | Content-based analysis for video from snooker broadcasts[END_REF] to extract information from tournaments played on television to get game summaries.

Another aspect, the focus of this paper, concerns the intelligence required to plan and select the best shot sequences on the table, given a complete physical simulator of the game. A lot of work has also been done in this regard. The usage of fuzzy logic has been documented in [START_REF] Chyi | Decision algorithm for pool using fuzzy system[END_REF] as a way to evaluate shot difficulty on a given table state. Bayesian network models have also been proposed in [START_REF] Percy | Stochastic snooker[END_REF] in the same context. Monte-Carlo sampling approaches were used in [START_REF] Smith | Running the table: an AI for computer billiards[END_REF] to not only evaluate shot difficulty but generate possible plans. Finally, leastsquare optimization approaches were described in [START_REF] Landry | AI Optimization of a Billiard Player[END_REF] as an efficient approach for positionplay.

When playing the game of billiards as amateurs, we are usually confronted by one key problem: cue-ball control. Although we know which shot we are aiming for, executing it is a completely different matter. It is a matter of skill, technical precision, and mechanical physics. We can usually estimate the trajectory of the cue-ball given an average cue-strike but it takes years of practice to perfectly master the shot execution, and to be able to gauge which shot we can successfully complete. Thus for an amateur, the best shot is almost always the easiest one. This makes the game very interesting since as we progress, we are able to execute harder shots leaving us with a new array of possible shots which opens up a new level to the game and adds in the complexity of planning. This is also the area where we see the pro's come in. Having better cue-control and position play they can envision more than one shot ahead, to be able to select the shot which may be harder to execute but yields a better chance of finishing the table.

The approach discussed in this paper was inspired from watching real-world players select and execute their shots. Up to now, state of the art approaches ( [START_REF] Smith | Running the table: an AI for computer billiards[END_REF], [START_REF] Archibald | Analysis of a winning computational billiards player[END_REF]) usually planned for 2-3 shots in advance by discretizing the search space such as to try various angle and speeds at which to hit the cue-ball, simulating the shot, and then continuing at the next ply from the position reached by the cue-ball. What was proposed in [START_REF] Landry | A robust controller for a two-layered approach applied to the game of billiards[END_REF], however, was to divide the problem in two layers, such that a robust controller may be guided by a high-level planner, taking advantage of possible knowledge which can be extracted from the domain. Although the controller described in that work proved to be very robust, the downside was a necessity for many simulator calls for every single evaluation of the objective function. Also, no specific planner was proposed, thus leaving the full potential of the two-layer approach to be yet demonstrated.

With this paper we bring forward several improvements to the robust controller by modeling the objective function differently using several penalties to guide the minimization process more effectively, generating better solutions with less calls to the simulator. We also bring forth the elements necessary to complete the two-layered approach which was suggested, by expanding on the description of high-level planner that will establish a preferred shot sequence to maximize chances of finishing the game with success. Results are presented, showing an improvement of around 13% success-rate (at highest noise-level) with modifications to the controller alone in the case of randomly dispersed tables, while a 7% improvement is observed for the planning heuristics, yielding a total of over 20% of improvements over pass results and positioning this approach as state of the art in regards to the game of 8-ball.

The rest of this paper is structured as follows. We first present an overview with a short background on the game of billiards and the two-layered scheme proposed previously and then introduce the heuristic strategy for the high-level planner. In section 4, we refine the objective function of the robust controller to generate better solutions with less calls to the simulator. Finally we will discuss the results of several tests aimed at demonstrating the benefits of the various elements presented in this paper.

Background

Although there exists a significant number of billiards games, we focus in this paper on the game of 8-ball. This game variant has been the focus of a lot of research, and allows us to establish some comparisons with state of the art approaches. To provide a general idea of the difficulties present in the game, we describe below the general rules used in the game of 8-ball. We then provide a short description of the physics simulator engine used to generate the tests in the final section.

The game of 8-ball

The game of 8-ball is generally played table of 1:2 dimensions, with four pockets in the corners, and two on the sides. There are fifteen numbered balls and one cue-ball, which will be hit with the cue-stick to impact the other balls and send them in the pockets. At the beginning of the game, the balls are placed in a triangle at one end of the table, and the player which has been selected to start will break the triangle using the cue-ball from the other end of the table. If he manages to pocket one of the balls, he can continue playing, and decide to aim for the low balls (1-7) or the high balls [START_REF] Chyi | Pool balls identification and calibration for a pool robot[END_REF][START_REF] Chyi | Decision algorithm for pool using fuzzy system[END_REF][START_REF] Greenspan | Pool at the 10 th computer olympiad[END_REF][START_REF] Michael Greenspan | Toward a competitive pool-playing robot[END_REF][START_REF] Hammond | A computer vision tangible user interface for mixed reality billiards[END_REF][START_REF] Rea | Content-based analysis for video from snooker broadcasts[END_REF][START_REF] Landry | AI Optimization of a Billiard Player[END_REF]. Once a player starts playing for the low or high balls, he must finish them all and then keep the 8 th ball last. If he pockets it by accident (scratch), he loses the game. For each shots after the break, he must call the target ball and the pocket he aims for, if he misses, he loses his turn. He can also call a safety shot, which means he wilfully gives the next turn to the opponent after executing his shot. This type of shot is usually done when a player has no shot possible and prefers to leave the opponent in a bad position. The first player to finish all of his balls and pocket the 8 th ball wins the game.

Physics-based simulator

The attributes on which we focus in this paper are related the computational aspects of billiards. As such, we do not address the difficulties related to the creation of a realistic and accurate physics-based simulator, which is a great challenge in its own. Thus, we present here the framework we use to test the approaches proposed in this work, the FastFiz simulator, which is based on the Poolfiz ( [START_REF] Leckie | An event-based pool physics simulator[END_REF]) simulator used in past computational pool tournaments. Fastfiz is an event-based physical simulator which simulates the physics of a billiards table Figure 1: Break shot at the beginning of the game. At least two balls need to hit the rails. by analytically solving a set of equations describing the movement of balls on the table after an initial velocity and spin is imparted to the cue-ball by the cue-stick.

For our work, we suppose that it acts as a black-box. We provide the simulator with 5 parameters corresponding to a shot, and in return it gives us the outcome of this shot after simulation. The simulator can also provide a detailed list of the events that occurred during the shot simulation.

The five control variables corresponding to a shot defined as a vector u = {a , b , θ , φ , v} are the following:

• a: Horizontal offset from the ball's center.

• b: Vertical offset from the ball's center.

• θ: Angle of the cue-stick in relation to the plan of the table.

• φ: Orientation of the cue-stick.

• v: Initial speed given to the cue-ball.

The Fastfiz simulator is deterministic, which means the same shot will always result in the same table state. In reality however, imperfection in the ball collisions, the rail's elasticity and other factors may influence the outcome of a shot. To simulate such effects, in past computational tournaments, different noise-levels were applied to the shot parameters before the shots were simulated. A secondary goal was also to try and create tournaments in which players' planning abilities would tested as much as their technical abilities. The shot parameters we perturbed by the addition of randomly generated noise using a Gaussian distribution with the following standard deviations: φ=0.125 deg, θ=0.1 deg, v=0.075 m/s, a=0.5mm, b= 0.5mm. Thus in the results section, a noise-level of 1x corresponds to this noise-level, and 1 2 x corresponds to half this level.

A two-layered approach

A general model to represent the game of billiards was first proposed in [START_REF] Archibald | Modeling billiards games[END_REF], demonstrating the presence of a Nash Equilibrium in the game. This is very interesting and serves as a motivation for pure stationary strategies (i.e. where an optimal strategy will remain optimal regardless of the opponent's actions). The model proposed, however, is clearly intractable due to the state and action space being continuous. Thus, to be successful, any approach needs to perform an intelligent partitioning of the search space to render the problem tractable.

It is also clear that this model ( [START_REF] Archibald | Modeling billiards games[END_REF]) suggests we consider the possibility of executing safe shots by accounting for whichever shot our opponent would do, to then regain control of the game in a favourable position. This scenario, where we go as far as predicting the result of our opponent's shot, is highly unlikely and almost impossible to predict. A safety shot is usually done only if no shot sequence leads to victory with an acceptable success rate. In such a case, it will be better to leave the turn to our opponent, but leave him in the worst possible position on the table, to then regain control of the game later on. Very good players will often have several exchanges of safe shots when the table state has many clusters. Taking these factors into consideration, we will for this work only consider safety shots as a last resort when it is clear no shot will be possible for our next move.

It is important to remember that the mix of continuous and discrete aspects, in a domain subject to stochastic perturbations brings forward many complex elements to the model, and demands a very careful analysis. We proposed a novel approach in [START_REF] Landry | A robust controller for a two-layered approach applied to the game of billiards[END_REF] under the form of a two-layered model, using a planner and controller to establish the optimal shot sequence. It is the first time such an approach has been proposed for the game of billiards, other approaches studied until now usually relied on a discretization of the action space to generate solutions, and while these are effective in general, we believe that a more specific approach to the problem as we propose in this work will give better results in the long run.

High-level planner

Planning with continuous states and actions under stochastic environment is a challenge; we propose in this section a set of domain-specific heuristic rules to help narrow the search space and find highly efficient solutions. These heuristics are part of the planner depicted in Figure 2, which fits into the two-layered approach previously proposed (see [START_REF] Landry | A robust controller for a two-layered approach applied to the game of billiards[END_REF] for more details).

The planner receives a given table state and performs a preliminary analysis to determine which shots are possible from the cue ball's position. This shot list will be composed of direct, indirect and combination shots, and is basically a list of pocket-ball combinations, with the queue angle to execute the shot as a starting point for the optimization. The shot list will then be analysed and a value representing the shot difficulty will then be associated to each.

Next we will proceed to the planning of the sequence of shots to execute, depending on the number of balls remaining on the table. If only 3 balls are remaining, we will use a backward computation approach to compute the shots, otherwise we will use one of the heuristics described below to specify a preferred shot-order. The planner will then access the controller and optimize the selected shots. Based on the results, further evaluations will be done if necessary, otherwise the best shot will be selected and executed. Since we are playing the game of billiards, we can extract several key components from the given table state to help decide which shot sequence should lead to a better outcome. We describe several heuristics in the following subsections which help the planner establish a good shot sequence, but first, we do a short recall on the optimization model describing a shot sequence.

Given a cue ball position on the table, we can first elaborate the list of possible shots from that point in order of difficulty. A typical list would include a combination of the following shots:

• Straight shots: The cue-ball first collides with the target-ball and it goes directly in the pocket.

• Combination shots: The cue-ball first collides with a given ball, which sends it colliding on the target-ball and sends it in the pocket.

• Kick shots: The cue-ball first hits the rail, and then collides with the target-ball to send it in the pocket.

• Bank shots: The cue-ball first hits the target-ball and has it rebound on the rail to then end in the pocket.

• Cluster shots: The cue-ball sinks the target ball directly or indirectly, and then collides with a given cluster to disperse or better reposition the balls.

Many of these shots are not necessarily viable candidates as they can be quite complex to execute (i.e. long shots) and have a minimal success rate. For this reason, only the first few (best ones) are considered. The idea we propose to use is in continuity with what was discussed in the Future Work section of [START_REF] Landry | A robust controller for a two-layered approach applied to the game of billiards[END_REF] with advanced methods for selecting shot sequences.

Instead of partitioning the search space by discretizing the continuous shot parameters, we will analyse the table state to define a sequence of shots and repositioning targets, and each single shot will be solved as a sub-problem by a non-linear optimization library ( [START_REF] James | The BOBYQA algorithm for bound constrained optimization without derivatives[END_REF] was used in this case).

If we define b(u) as the target ball position after fixing the shot parameters u, p as the pocket for the given target ball, u n as the shot parameters of our n th shot and c t as the position reached by the cue-ball, we can minimize function f as:

minf (u 0 , u 1 , ..., u n ) = Posval(c 0 , c 1 , ...c n ) ∀t : 0...n s.t. b t (u t ) -p t = 0, t = 1, ..., n. (1)
The function P osval() correspond to an estimate of the value of the position in regards to a subsequent shot. For a given cue-ball c i position on the table, P osval(c i ) will return a very small value if the next shot can be easily done from this point. Details on the computation of this function will be presented in subsection 3.3.

Looking again at the function (1), we wish to search for the repositioning targets c 0 , c 1 , ...c n that will be reachable with the shot parameters u, and minimize the position value at the same time. What was previously proposed to solve this model was to do an evaluation of the table state by scanning the table to find the best positions for each ball-pocket combination, such as to establish the most desirable repositioning targets c 0 , c 1 , ...c n . This proved problematic in our preliminary tests as restricting the optimization to get the cue-ball as close as possible to a target may is not even possible in some cases, and in these cases the value of the position reached is often worthless.

What we propose to do instead is to minimize the P osval() function to get a good position value. Thus, if we combine these two aspects together in a single function, we will have (for one ball):

minf (u) = Posval(c) + ρ 1 ||b cue (u) -c|| s.t. b(u) -p = 0. (2)
We now try to find the shot parameters that minimize our position value, but at the same time, we also try to reposition the cue ball at a specific place on the table (corresponding to our previous evaluation of good positions to reach). Adding this new parameter will also help us in situations where we don't have an initial guess for our optimization method that gives us a valid position value. By guiding optimization search this way, we will have better chances of success at finding a good position value for our cue-ball if the initial guess left us in a position where P osval() was null (if no shot is possible P osval() is set to return an extreme value).

Partially ordered search

In this section, we present two related heuristics which are used to specify preferred shot sequences. The motivation for presenting these two approaches is that the first heuristic specified may be too restrictive in regards to the value given to some shot sequences. We suspect however that it may behave better when less noise is added to the shot parameters. As such, both are presented and later discussed in the results section.

Preferred shot sequence using ball distances

The first heuristic we propose to select a shot sequence is a simple shortest-path approach. Indeed, if we step back and look at a given table state, the most successful sequence of shots will usually be the one where the cue-ball travels the least distance. The less distance it has to cover, the less chances it has to deviate from its aimed trajectory or to collide with an obstacle. It is also an obvious behaviour observed when watching professional players. They will rarely cross over the whole table to do a shot in the distance if a closer shot is possible. It is also usually easier to control the cue-ball position when less speed is given to the cue ball.

Given an ordered sequence of balls {ball 1 , ball 2 , ..., ball n }, and their position in (x, y) the table defined by pos(ball i ), the value (H 1 ) associated with this shot sequence will be computed as:

H 1 = n-1 i=1 ||pos(ball i ) -pos(ball i+1 )||. (3)
If we have a look at the same example that was used in [START_REF] Landry | A robust controller for a two-layered approach applied to the game of billiards[END_REF] to demonstrate the importance of planning in some specific situations, we can see that by using the shortest-path search we just described to determine the ball sequence, the correct ball would have been selected and the table state would be finished with a much higher success percentage.

If the first shot is selected as can be seen in figure 3, the total distance covering the shortest path between the balls corresponds to 3.77 meters, while if the shot 2 is selected (figure 4), only 2.63 meters separate the balls, and less distance will be covered by our cue ball.

Ball-order clustering

A different heuristic we propose in this section is based on the same idea as the one in 3.1 but not as restrictive. Since different games may require different tactics and heuristics, we present the two approaches even though our final tests suggest that the ball-order clustering heuristic introduced next gives better results.

Specifying shot-sequences using the previous heuristic can be too constraining in some situations. For example, in figure 5, we can see that if we choose to pocket the ball in the bottom left corner, as long as we choose to reposition for one of the three closest balls, the overall distance covered by the cue ball will most likely be very similar. In some other situations however, if we put too much importance on respecting the specified order of Figure 3: In this figure, if we choose to reposition for the ball in the bottom left of the table, the shortest path separating all of the remaining balls will be of 3.77 meters. The success-rate to finish the table was of 54% in this case, based on 500 trials. Figure 4: In this figure, if we choose to reposition for the ball in the top right of the table, the shortest path separating all of the remaining balls will be of 2.63 meters. The success-rate to finish the table was of 96% in this case, based on 500 trials. shots, we may end-up selecting one which will is slightly riskier without having gained any significant reward for the risk taken. Thus, by evaluating the table state and clustering balls prior to evaluating the shortest path between them, we can insure that a riskier shot is only selected when necessary, and that we consider the table as a global state where we want to pocket all the balls in a given area of the table before proceeding to the next one.

Determining the clusters to which each ball belongs is actually a problem in itself. However, in this case, since we only want a good approximate and are not too concerned with precision, we decided to use a simple k-means clustering approach [START_REF] Macqueen | Some methods for classification and analysis of multivariate observations[END_REF]. We start with 2 clusters, which are initialized at the position of two of our balls. We then iteratively attach each ball to its closest cluster, and recompute the centroid of each of these clusters. We continue until we have converged and our balls are set and no longer switch between clusters.

Finally, we check all distances between balls and their respective clusters, and if this distance is larger than a pre-determined cut-off value (a distance of 30cm was used), the cluster size is incremented (K) and the clusters are re-generated. This step is necessary as the k-means approach requires we specify the number of clusters beforehand. By recomputing our clusters when needed, we are guaranteed to have sufficient distances between each of our clusters, and since we only have a maximum of 8 balls to group in clusters, the computation cost is negligible. The result of this process is illustrated in figure 5.

The choice for not using a fixed cluster size in our evaluation can be explained by the fact that if two balls are slightly far away from each other and still clustered together, then when selecting the preferred shot order they will have the same priority. However we wish to give a higher priority to the closest one, given that a solution is generally found faster by exploring closest shots first.

The heuristic we use will be the same as before. Given an ordered sequence of clusters cl 1 , cl 2 , ..., cl n , and their position (x, y) on the table defined by pos(cl i ), the value (H 2 ) associated with this cluster sequence will be computed as:

H 2 = n-1 i=1 ||pos(cl i ) -pos(cl i+1 )|| (4)

Dynamic programming

Our final addition to the planner is the use of dynamic programming to do a backwards search on the remaining ball-pocket combinations on the table. We described the general idea in section 2.3 but also mentioned how it was intractable to directly implement. However, if we implement a slight variation of it when only a few balls remain on the table, we may actually find good results. The reason for not using using dynamic programming unless there are only a few shots left on the table is simple; as we advance in the game, less balls on the table means we have less chances of disturbing the table state when executing our shots. If an optimal shot sequence exists to finish the game, we are more likely to find it this way and execute it properly. The hypothesis that no ball-ball collisions will happen in our search is a strong one, but we verify it by when performing our backwards search. If a ball in our sequence is blocked after computing previous shots, this specific shot sequence will not be selected, unless no other alternatives exist.

The first step is to establish the desired positions to execute our n th shot. For example, if we desire to pocket balls 1, 2 and 3, we will start by removing our balls 1 and 2 from the table, generate the best position to pocket ball 3 in the easiest pocket, and then compute a shot from this position. If such a shot is successful, we'll return its value and propagate it through our search tree, such that we will then compute the parameters to pocket ball 2 in a pocket, to reposition for ball 3.

Since we have discretized our state space into states we wish to reach, we are no longer guaranteed optimality. However we can still get a good approximation this way and find out if a specific shot sequence is better than another. Our controller being robust, we will also be informed with a good estimate of the difficulty of a shot sequence compared to another, thus will be able to make the right decision.

One important factor to take into account about using this approach is that it will most likely be a very powerful tool for other variants of the game of billiards. The game of Straight for example requires a player to be very careful when selecting his last shot since he will need to position the cue-ball in such a way as to be able to rebound and re-break the balls which are put back in a triangle to continue the game. By planning in advance with DP we will be able to foresee such a situation and select the best shot to continue the game.

Position evaluation

Up to this point, the efficiency of the P osval() function to define the quality of a position wasn't discussed. The method which was used in [START_REF] Landry | AI Optimization of a Billiard Player[END_REF] relied on a rough estimate of a shot's difficulty, using distances and cut angles to compute shot difficulty measures on the fly. Based on the 90 • rule (see [START_REF] Alciatore | The Illustrated Principles of Pool and Billiards[END_REF]), one can have a good estimate of the best position for the cue-ball, and thus subsequently have a good estimate of the shot's difficulty. The methods described in [START_REF] Smith | PickPocket: An artificial intelligence for computer billiards[END_REF] and [START_REF] Archibald | Analysis of a winning computational billiards player[END_REF] also seemingly use similar approaches, however using precomputed coefficients in a tabulated database for a given cue-ball, target-ball position and pocket. Since defining a list of desirable target positions relies heavily on a good evaluation of shot difficulty, the planner will greatly benefit from any improvement in this area.

One of the main issues we have discovered with these methods is that quite often, the direct path between a target-ball and pocket will be clear of obstacles, but a slight deviation of this path which may still pocket the target-ball may be partially blocked by another obstacle ball.

Another problem also arises when we evaluate the value of a corner shot. If the targetball is sufficiently close to the rail, its chances of success will be better than if it is aligned directly at 45 • angle with the pocket, as it can use the rail to reach its final point.

The geometry corresponding to these aspects has been studied in parallel to the writing of this paper and the details can be found in [START_REF] Bureau | Sensibilité des coups au billard[END_REF]. We will still describe here a few of the key elements which we use for our evaluation. We can see in figure 6 that a direct shot, with the cue-ball and pocket-ball directly aligned with the pocket is actually harder than a shot in which the target-ball is close to the rail (figure 7). The shot closer to the rail will have the possibility of a higher deviation from its path while still ending up in the same pocket, while the direct shot might rebound off the side of the pocket. We can actually divide these areas in two zones, one for direct shots (as shown in 6), and one for rebound shots (as shown in 7).

To correctly compute the value of a corner shot, in the case where no ball is partially blocking the path, we first determine to which zone it belongs. Using some basic geometry, we can use the following developments.

If the ball is in the first zone, we can use the following formula to compute our target ball -pocket difficulty coefficient:

P osval() = ∆θ A = arccos a 2 + b 2 -c 2 2ab
where a is defined as the vector between the target ball and one side of the pocket, b as the vector between the target ball and the other side of the pocket, and finally c as the vector between the two sides of the pocket.

If the ball is in the second zone, we use the same formula but use a mirror table to get the position of our ghost ball on the pocket and compute b (see figure 7).

We then use basic geometry to determine any ball is completely or partially blocking its path. To do so requires to do two verifications. The first is to check whether or not the ball is in the region delimited by the angle of the zone for which the ball is pocketable. The second is to check whether or not the ball intersects with one of the sides of the triangle representing the angle. If a ball is partially or completely obstructing the path, we will adjust the angle by computing the tangent between our target-ball and obstacle ball. An example of partially blocked zone is shown in figure 8. Finally, two last conditions also need to be checked when computing the value of the shot. The first can be seen in figure 9, and corresponds to a case where the cut angle is too small, and we have to actually adjust the angle to correctly represent the zone. The second is if the cue-ball is too close to the target ball. In such a case it may not see the complete angle corresponding to the target-ball -pocket trajectory.

It should be noted that the function we propose here is to evaluate one single position on the table for one single shot. It is just as easily possible to evaluate a position on the table based on all possible shots from that position (e.g. by adding all their values or taking the max). However in the approach we have proposed so far, we assume we are doing a specific sequence of shots, as such, we only verify the position value for the next shot in the sequence.

Improvements and additions to the robust controller

The controller presented in [START_REF] Landry | A robust controller for a two-layered approach applied to the game of billiards[END_REF], while very effective in low-noise situations, was not as impressive when higher noise-levels were used. Faced with the necessity to do more calls to the controller to allow the planner to work effectively, we studied the possibility of changing the model used for the single-shot optimization. The result was a much-improved controller providing better solutions than before with actually less calls to the simulator.

As a reminder, to generate robust shots in the presence of noise, the past controller was based on the use of non-linear optimization methods to minimize the objective function: We can see that a correction will need to be made on the angle corresponding to the shot difficulty since the cue-ball cannot directly reach the position which would normally be desirable for greatest chance of success.

min u f (u) = max(Posval(u, ζ) -Val min , 0) + ρ||b n (u, ζ) -p|| ∞ ∀ζ (5)
where ζ represents a vector of noise perturbation applied to the parameters in u. Thus, to actually minimize this function, it was required, for every function evaluation, to sample the function several times with different noise parameters to minimize the worst-case scenario (min-max). The problem with this model is that it is highly dependent on the samplesize, and even though it was possible to get better solutions using higher sample-sizes, the solutions found were often only marginally better.

Since the problem we are facing is actually based on a deterministic simulator (using Fastfiz), with a stochastic aspect simulated by the addition of noise to the shot parameters, a smarter search or modeling of the function should be possible in such a way as to provide solutions in a better neighborhood. Thus, most of the improvement we propose in this section are in regards to slight modifications to the optimization models used in [START_REF] Landry | A robust controller for a two-layered approach applied to the game of billiards[END_REF] in order to minimize the need for more function evaluations. Instead of using a min-max approach, we will use a few domain-based tricks to guide the optimization in finding robust solutions without actually needing to call the black-box simulator as often.

As a reminder, the noise-less model which was used previously to compute the parameters necessary to pocket a target-ball in a specific pocket while aiming to reposition the cue-ball at a specific position corresponds to:

minf (u) = ||b cue (u) -t|| s. t. ||b i (u) -p|| = 0 (6)
where the distance between the cue-ball's final position and a given target t on the table will be minimized, under the constraint of pocketing the target ball. To help find a solution satisfying the constraint of pocketing the target-ball, it can be reformulated as a penalty minimizing its distance with the pocket.

Directional vector

The success of a shot in a stochastic environment, which we will define here as sinking a target ball into a desired pocket, is closely related to one important element; the parameters used to execute the shot. These parameters must be selected very carefully, in a manner which will not only pocket the target ball, but send it with a velocity that will guarantee its success even under noise perturbations. For an easy shot, however, this doesn't always mean we have to hit the center of the pocket dead center. As a matter of fact, in certain cases where the ball is almost already in the pocket, the direction almost doesn't matter as long as we gently push it in the pocket with a minimal velocity. For other shots, harder ones, the success rate will however be directly related to this direction. Thus to improve our shot generation technique, one approach we propose here is to compute the center of the zone in which the target ball should be sent. We then trace the directional vector from the target ball to the center of this zone. Finally after executing a shot, we check the cue ball and target ball collision to get the post-impact velocity of the target ball. We then penalize our objective function with the distance between this vector and the directional vector for the center of the pocket. We add this parameter to our objective function with a penalty based on the shot difficulty coefficient. We choose to penalize based on the shot difficulty coefficient since as we said before, for an easy shot it is not as important to hit the pocket dead-center, and this way we may have more room to achieve a better position for the next shot. Supposing our target-ball's velocity after impact is represented by ṽbi , and the vector representing the center of the zone zp , we can define variable d = ||v bi -z p || as the norm of the difference between our two vectors, and ∆θ A our shot difficulty.

The function will now be reformulated as:

min u f (u) = max(Posval(b cue (u)) -Val min , 0)+ +ρ 1 ||b cue (u) -t|| + ρ 2 (∆θ A * d) (7)
We removed the constraint ρ 0 ||b i (u) -p|| ∞ (to pocket the object ball) from the function as it becomes redundant if the penalty on the directional vector is satisfied.

Robust positioning using derivatives

As we just discussed, by using a directional vector to specify the direction in which to send the object ball, we are almost guaranteed that if the penalized parameter is satisfied, our shot will be robust. However one key element we have ignored until now is the repositioning ability of our controller. When we specify a target to reposition for the next ball, we can either analyse the table and find the best possible target, which will usually be right behind a target-ball, or we can try to find the center of the zone corresponding to the area in which the shot remains feasible. In some cases, if we aim for the best possible position for the cue-ball, it may be very isolated, such that the slightest deviation will result in the cue-ball being in a position where it cannot complete the shot. In other cases, if we aim for the center of the largest zone, it might put us in a position that is rather mediocre, leaving us in a hard spot for the next shot. In the past, we have noted problems using both approaches. Thus, to try and find a better way to generate robust shots, we decided to proceed differently.

One of the key aspects making a shot's repositioning value robust or not is the rate of dispersion from the noiseless shot's position in relation to the variation of the shot parameters. Or to simply put, how sensitive will the reposition be to the slight variation in the shot parameters. An example is shown in figure 11 where the computed shot is highly sensitive to the smallest variation in shot parameters, while a second example in figure 12 shows a more robust shot. This aspect can actually be quantified with a very common tool; derivatives. By computing the derivatives of the function used to simulate a shot in relation to the position reached by the ball, we can obtain a very good estimate of its robustness, and we can then add this parameter to the objective function we are trying to minimize to generate safer shots.

The objective function will now have an added parameter ρ 3 * η accounting for the magnitude of the derivative of the function multiplied by a penalty value:

min u f (u) = max(Posval(b cue (u)) -Val min , 0) +ρ 1 ||b cue (u) -t|| + ρ 2 (∆θ A * d) + ρ 3 * η, (8)
where η is computed:

η = ||∇f (u)|| (9)
with

f (u) = b i (u) (10)
where f (u) is the final resting position of the ball for the shot parameters u and ∇f (u) is computed using forward finite differences by perturbing the value of each component of u separately while holding the other components at the nominal value. It should be noted that several parameters will have an impact on the outcome of the minimization process, to either generate shots which are more robust, or find solutions satisfying constraints such as pocketing the target ball. In this last function ( 8), we penalize using three distinct weight parameters. The first parameter, ρ 1 , weights on a distance between the cue-ball's final position after the shot, and a target position t. The second penalty value, ρ 2 , is applied on the computation of the difference between the desired directional vector and the velocity vector of the target-ball after impact. Since this value has an impact on the shot's robustness, it is indexed to the noise-level used for the current game. Finally the third scalar value, ρ 3 , is applied to the value of the derivative of the resulting shot, η. This penalty is also indexed to the noise-level used for the game since it will have an impact on the robustness for the positioning of the cue-ball for the next shot. Optimizing the meta-parameters is indeed a challenge for the application of black box optimization. For the moment these parameters have been set manually after doing many tests and trying various settings. However since the three parameters interact closely together, further study should be done to determine their optimal settings, keeping in mind however that running only 500 games with a time-limit of 5 minutes per game may take up to 40 hours to complete. This added parameter, which allows for our computed shots to be partially robust concerning reposition, is for the moment computed with finite differentiation. We hope in the future to be able to exploit automatic differentiation tools in order to get the derivatives directly from the simulator, however as was studied in [START_REF] Moré | Do you trust derivatives or differences?[END_REF] it is not yet clear if the gains will be noticeable.

Final shot evaluation

The modifications we made to the robust controller here all correspond to a nominal (noiseless) version of the problem. Although the shots computed this way should be fairly robust, they still might behave slightly different than predicted when noise is added. The main reason for this is that several discontinuities can still happen when we execute the shot with noise-induced parameters, such as pocketing the 8-ball by accident, or having the cue-ball pocketed. Although these aspects are part of the nominal model as constraints, they are not for the moment treated in a robust fashion. Thus a shot which works perfectly when evaluated without noise-induced parameters may work only 10% of the time when noise is added. What we can do however is use the same robust model as in [START_REF] Landry | A robust controller for a two-layered approach applied to the game of billiards[END_REF] to evaluate the value of a shot after its nominal counterpart is computed.

As previously explained, the robust controller in [START_REF] Landry | A robust controller for a two-layered approach applied to the game of billiards[END_REF] made several calls to the simulator to sample the objective function several times before taking the max of these function evaluations to perform a min-max search. The improvements we proposed up until now should actually present us with good solutions even without doing such a sampling. Since calls to the simulator are the most expensive in terms of CPU resources, for every evaluation done by our optimizer to minimize our model, the value of the result is stored given the specific parameters used. Thus as we go along and try to compute shots for various repositioning targets, we gather and keep all shot information in a vector. It is also important to note that the optimization library used for our computations is actually a local optimizer ( [START_REF] James | The BOBYQA algorithm for bound constrained optimization without derivatives[END_REF] ), which will have a tendency to make more evaluations as it progressively gets closer to the solution. Thus by recording those calls to the simulator, we can gather important information about the robustness of the shot.

When we want to get an idea of the robustness of a solution which was provided by the nominal model, we will simply go through the vector of previous shots, and use the values of all the shots in a given neighbourhood corresponding to the noise level used for the game. If not enough calls were made in the neighbourhood of our solution we can then generate some more to get a better estimate of the shot's value.

To give a specific value to a shot which was computed using the nominal model in ( 8), we will re-evaluate it, with one call to the following function:

f (u) = max[max(Posval(b cue (u)) -Val min , 0)∀ζ] * α 0 * dist(ζ, U ), ( 11
)
where U as the set of the normal range of the parameters under which our shot still remains successful U = {ζ : b i (u, ζ) = p}. Thus, the parameter ζ will correspond to all possible noise pertubations which could be applied to the shot computed. If not enough parameters are present in the previously-saved vector of shots, more shots will be generated. The parameter α 0 in this equation also carries great importance, since it will correspond to the penalty we apply for the distance with the closest-shot parameters of a missed shot. If all shots succeed with noise parameter ζ then only the P osval() function will carry weight.

Results

To demonstrate the potential of the presented approach as well as what we believe to be the state-of-the-art automated billiards player, the results of various tests are presented in this section.

The game on which we are performing tests at this time is one where the aspects of the planner and controller are often very closely interleaved. Some improvements done at the controller-level may generate better shots but leave us in positions from which it will be difficult to finish the game. Thus it is sometimes very difficult to gauge the gain of a particular modification to the model in the overall problem. The same was noticed from [START_REF] Archibald | Analysis of a winning computational billiards player[END_REF] when they tried to dissect the key elements of their winning player.

In our case, we have nonetheless been able to discern some stable and very nice improvements to the results by using the methods described in this paper.

Testing environment

The test parameters which we used were the same as in [START_REF] Landry | A robust controller for a two-layered approach applied to the game of billiards[END_REF]. We feel that by generating random tables rather than playing a full-game with breakshot we are able to better illustrate the planning ability of the player. In reality, professional players actually spend a lot of time perfecting their breakshots. Depending on the style of game played, it can have a crucial importance to break defensively or offensively and sometimes requires a great deal of skill. The study of the perfect breakshot is however very dependent on the simulator, and possible advantages can be exploited from analysing it to always leave the player in a favourable position to clean the table (mentioned in [START_REF] Archibald | Analysis of a winning computational billiards player[END_REF] as an important element). For the sake of curiosity we will nonetheless provide a few clean-off-the-break results, with a breakshot which was selected after doing some testing on the Fastfiz simulator.

Overall, 500 table states were generated, with balls randomly positioned. The same 500 tables used in this article were used in [START_REF] Landry | A robust controller for a two-layered approach applied to the game of billiards[END_REF], thus allowing for a direct comparison to be done. The graphs presented show a cumulated average over the number of successes such as to illustrate the fact that the averages tend to stabilize before reaching 500 samples. Success is defined as the player sinking all the balls on the table successfully without missing a single shot. Averages are cumulated with a value of 1 for a success and 0 for a failure. Random noise is added to each of the computed shots parameters. This noise was added in the previous computational pool olympiads (see [START_REF] Greenspan | Pool at the 10 th computer olympiad[END_REF]) to simulate the imperfections which would normally be present on a real pool table, and to simulate different skill levels of real players. We choose to simulate with a noise level of 1x and 0.5x of the parameters used in the last competition (Standard deviations for each parameters: φ=0.125 deg, θ=0.1 deg, v=0.075 m/s, a=0.5mm, b= 0.5mm). The same maximal computing time of 10 minutes per table state was allowed. For the standard noise level, the average computing time (Intel Core Duo 2.53ghz ) was of approximatively 280 seconds per game, while for 1 2 noise level, only about 150 seconds per game were required.

Analysis

In figures 15 and 13, we can observe that one of the major improvements to the success rate was brought by the new shot evaluation function, which is now more precise than before, and thus allows for better repositioning on the table. The gain is more noticeable in higher noise-level tables, which suggests that positioning in these states is probably more of an important factor since a better player (less noise) will still manage to complete his shots even in tougher positions. We can also observe a clear gain of 8% (in figure 15) when planning using the cluster-based shortest path heuristic. This demonstrates that planning can actually be done at a higher level, without the necessity to compute every shot in a tree-like search. It is hard to comment on the efficiency of the cluster-based heuristic vs shortest path, since the difference between the two approaches is only of 2%, which could be to the statistical significance of the sample.

Finally, figures 14 and 16 show the best results obtained using all of the improvements described in this paper, compared to the results which were originally obtained in [START_REF] Landry | A robust controller for a two-layered approach applied to the game of billiards[END_REF]. We see a gain of over 20% success rate for the 1x noise level and of 9% for the x noise level. An average of 91% success rate is achieved when no planning is used, 96% for shortest-path and 97.4% when using the cluster heuristic.

If we now have a look at figures 17 and 18, we can see the outcome of 500 games, where a player would break, and then try to finish all the balls on the table. As in [START_REF] Archibald | Success, strategy and skill: an experimental study[END_REF] the player was allowed to re-break until successful, and allowed a maximum of 6 minutes to compute all of his shots, with a binary indicator of 1 for victory and 0 for failure. An average success rate of around 80% can be observed for games played on a 1x noise level, while a higher 93% was attained for 1 2 x noise level. The last published results in [START_REF] Archibald | Success, strategy and skill: an experimental study[END_REF] seemed to be hovering around 60 -65% for 1x noise level, and 80 -85% for a 1 2 x. As a disclaimer, it should be noted that it is very hard to do a direct comparison between different players/approaches without actually confronting them in a tournament. Since the tournaments for the Computational Pool Olympiads are not being held anymore we have to find other means for benchmarking. As such, these tests should not be taken as a definite proof of the value of a method over another, but rather as an indication of the potential of the described approach. Many other factors have influence on the outcome when playing with full-games. x noise level. These results are the results which were first presented in [START_REF] Landry | A robust controller for a two-layered approach applied to the game of billiards[END_REF]. A noticeable improvement was made over PickPocket ( [START_REF] Smith | Running the table: an AI for computer billiards[END_REF]) and the old model, which had a success percentage of 84% Upon reviewing the results presented, it is possible to see that noticeable improvements have been made over the model using the controller alone. It would seem that the additions and modifications made to the controller are responsible for to 13% of the improvements (77% vs 64% in the 1x noise example), which is quite important. However, the overall usage of a two-layered system with planning capabilities also provided a noticeable advantage over a single-layered approach. Although a robust controller by itself accounts for most of the successful games, it still needs to rely on a planner of some sort, even in the simplest form, to get scores closer to perfection. Thus the question remains; controller or planner? Both, we believe. Future work on various versions of the games of billiards should provide even more insight concerning the necessity for a better planner or controller, and show that even though one may prove more important than the other in some games, both are still needed to achieve the best results.

Future work will most likely be focused on variations of the planner to improve its planning abilities, possibly by using learning algorithms to identify trouble-some states. Such a tool might also prove helpful to predict success rate given specific table state, and thus provide an efficient way to plan safety shots ahead of time.

Figure 2 :

 2 Figure 2: Detailed illustration of the planner.

Figure 5 :

 5 Figure 5: In this figure, we are able to see five different zones which were selected as a result of a k-means clustering of the balls on the table.

Figure 6 :

 6 Figure6: Corner shot illustrating a straight-in shot as well as the corresponding corridor. The ball can only be pocketed directly, if a collision with the rail occurs, it will deviate and rebound off the desired trajectory.

Figure 7 :

 7 Figure 7: Cornershot illustrating a shot with a greater angle, with a shot corridor including possible rebounds on the rail.

Figure 8 :

 8 Figure 8: Same corner shot, but this time blocked by an obstacle ball. The zone is then rectified using the tangent point of the line between the obstacle ball and cue ball.

Figure 9 :

 9 Figure 9: A side shot where the cue ball is positioned very close to the target ball.We can see that a correction will need to be made on the angle corresponding to the shot difficulty since the cue-ball cannot directly reach the position which would normally be desirable for greatest chance of success.

Figure 10 :

 10 Figure 10: A side shot in which we see a slight offset from the pocket center (black dotted line), allowing for a better reposition while still guaranteeing a high shot success rate.

Figure 11 :

 11 Figure 11: In this shot to the upper side pocket, we are able to see a number of possible positions at which the cue ball will end after being simulated 500 times with random gaussian noise added to the parameters.

Figure 12 :

 12 Figure 12: In this shot to the upper side pocket, we are able to see that the resulting positions of the cue ball after the shot are not as dispersed as widely as in the last figure [cite figure]. Thus the norm of the derivative of the position relative to the shot parameters is not as big.

Figure 14 :

 14 Figure14: Cumulated averages for the results of 500 games played on randomly dispersed table states with1 2 x noise level. These results are the results which were first presented in[START_REF] Landry | A robust controller for a two-layered approach applied to the game of billiards[END_REF]. A noticeable improvement was made over PickPocket ([START_REF] Smith | Running the table: an AI for computer billiards[END_REF]) and the old model, which had a success percentage of 84%

Figure 17 :

 17 Figure 17: 500 games with breakshot, at a noise level of 1x

Figure 18 :

 18 Figure 18: 500 games with breakshot, at a noise level of 1 2 x

  1 2 noise level. Obviously the gain were not as important in lower noise-level table states, since the margin for improvement is smaller, but we nonetheless get very close to a perfect success rate.

		1
	Clean Success Percentage	0 0.4 0.6 0.8 0.2	0	100	200	300 PoolMaster V2 -Clusters 400 PoolMaster V2 -ShortestPath PoolMaster V2 -No Plan	500
					Game number
	Figure 13: Cumulated averages for the results of 500 games played on randomly dispersed
	table states with 1 2

  Figure15: Cumulated averages for the results of 500 games played on randomly dispersed table states with 1x noise level. We can see the results when using the new improvements to the controller (77%), with the shortest-path heuristic (85%), and finally the cluster-based heuristic (87.4%).Figure16: Cumulated averages for the results of 500 games played on randomly dispersed table states with 1x noise level. These results illustrate a gain of over 20% with a success rate of 87.4% while the old version was at 64%.

		1
	Clean Success Percentage	0 0.4 0.6 0.8 0.2	0	100	200	300 PoolMaster V2 -Clusters 400 PoolMaster Robust PickPocket	500
					Game number
		1
	Clean Success Percentage	0 0.4 0.6 0.8 0.2	0	100	200	300 PoolMaster V2 -Clusters 400 PoolMaster V2 -ShortestPath PoolMaster V2 -No Plan	500
					Game number

6 Perspective -Controller or Planner?


Quratulain Rajput
email: qrajput@iba.edu.pk

Sajjad Haider
email: sahaider@iba.edu.pk

A Comparison of Two Ontology-based Semantic Annotation Frameworks

Keywords: Ontology, Information Extraction, Bayesian Network, Machine Learning, Semantic Annotation

The paper compares two semantic annotation frameworks that are designed for unstructured and ungrammatical domains. Both frameworks, namely ontoX (ontology-driven information Extraction) and BNOSA (Bayesian network and ontology based semantic annotation), extensively use ontologies during knowledge building, rule generation and data extraction phases. Both of them claim to be scalable as they allow a knowledge engineer, using either of these frameworks, to employ them for any other domain by simply plugging the corresponding ontology to the framework. They, however, differ in the ways conflicts are resolved and missing values are predicted. OntoX uses two heuristic measures, named level of evidence and level of confidence, for conflict resolution while the same task is performed by BNOSA with the aid of Bayesian networks. BNOSA also uses Bayesian networks to predict missing values. The paper compares the performance of both BNOSA and ontoX on the same data set and analyzes their strengths and weaknesses.

Introduction

A large amount of useful information over the web is available in unstructured or semistructured format. This includes reports, scientific papers, reviews, product advertisements, news, emails, Wikipedia, etc [START_REF] Ittersum | understanding the difference between structured and unstructured documents[END_REF]. Among this class of information sources, a significant percentage contains ungrammatical and incoherent contents where information is presented as a collection of words without following any grammatical rules. Many of the popular retail sites such as eBay 1 and craigslist2 fall into this category. These websites are made up of user-provided data, called posts, which contains useful information but due to lack of semantics are not easily searchable. Moreover, the automatic extraction of required information from such posts is also a big challenge [START_REF] Michelson | Semantic annotation of unstructured and ungrammatical text[END_REF]. The semantic web technologies, such as OWL/RDF, provide a major advancement to handle this challenge [START_REF] Antoniou | A semantic Web primer[END_REF] as they aid in the semantic annotation of new and existing data sources.

The semantic annotation process for existing data sources consists of many phases including information extraction, knowledge management, storage of extracted data in RDF/OWL, and user interfaces [START_REF] Reeve | Survey of semantic annotation platforms[END_REF]. Much of the research, however, has been focused on extracting information from varying type of data sources. Leander et al. [START_REF] Laender | A brief survey of web data extraction tools[END_REF] provides a good survey of the techniques used in this area. Recently, a lot of research has been done on ontology based semantic annotation as it helps in making the application independent from domain knowledge and easily scalable. Few of the important contributions in this area are BYU [START_REF] Embley | Automating the extraction of data from HTML tables with unknown structure[END_REF], MnM [START_REF] Vargas-Vera | MnM: Ontology Driven Semi-Automatic and Automatic Support for Semantic Markup[END_REF], OntoX [START_REF] Yildiz | ontoX-A Method for Ontology-Driven Information Extraction[END_REF] and BNOSA [START_REF] Rajput | BNOSA: A Bayesian Network and Ontology based Semantic Annotation Framework[END_REF] [10] which is an extension of our previous work OWIE [START_REF] Rajput | Information Extraction from Unstructured and Ungrammatical Data Sources for Semantic Annotation[END_REF] and E-OWIE [START_REF] Rajput | Use of Bayesian Network in Information Extraction from Unstructured Data Sources[END_REF].

This paper compares the performance of ontoX and BNOSA frameworks. These frameworks are selected due to their similarities in the way they exploit ontology for knowledge building, rule generation and information extraction. They, however, differ in the way conflict resolution is handled. ontoX uses heuristic measures while BNOSA uses Bayesian networks to resolve conflicts in case multiple values are extracted for a single attribute.

The rest of the paper is organized as follows. Section 2 describes ontoX and BNOSA while Section 3 compares the similarities and differences between them. The performance of both frameworks on the same data set is analyzed in Section 4. Finally, Section 5 concludes the paper and provides future research directions.

2

Selected Semantic Annotation Framework

Rule Generation Module (RGM):

This module is responsible for generating extraction rules for each data type defined in the ontology. The rules are used to identify possible values of each attribute.

Extraction Module (EM):

This module applies the rules generated by RGM to extract values corresponding to each attribute. The extraction module consists of two main steps: pre-processing and extraction. The pre-processing step removes the stop words (such as "and", "it", "at", "to", etc.), and finds the location of the pre-defined data types. The extraction step assigns the located data to the corresponding attribute. If more than one keyword is assigned to an attribute, then data is searched/located in the neighborhood of all the keywords. If more than one value is assigned to an attribute, ontoX uses a heuristic, level of evidence, to resolve this conflict. In case of same value being assigned to more than one attributes, ontoX uses another heuristic, confidence level, to resolve this conflict.

BNOSA: Bayesian Network and Ontology based Semantic Annotation

BNOSA (Bayesian Network and Ontology based Semantic Annotation) is a semantic annotation framework that is designed to extract relevant information from unstructured and ungrammatical domains such as craigslist [START_REF] Rajput | BNOSA: A Bayesian Network and Ontology based Semantic Annotation Framework[END_REF]. It utilizes ontology as well as Bayesian networks to perform information extraction and semantic annotation tasks. The information extraction in BNOSA is conducted in two phases:

Phase-I: Similar to ontoX, this phase utilizes different constructs of ontology such as classes, object properties and data type properties for information extraction. It also stores additional information in owl:AnnotationProperty elements. The additional information consists of context keywords and value constraints. Unlike ontoX, BNOSA does not define Quality and Temporal properties.

-Context Keywords: The context keywords help in finding the location of relevant information in a corpus. -Constraints: This feature is also similar to the corresponding feature in ontoX except the way string data types are handled. BNOSA applies simple pattern matching rules for all instances of a string type attribute. All such instance values are stored in the comment section of the ontology.

Once information is specified in the ontology, this phase generates rules for each data type at run time. The context keywords are located first and then with the help of these rules, data within the neighbourhood of these context keywords is searched. The extracted data is then assigned to the corresponding attribute.

Phase-II: If more than one value is assigned to an attribute or no value is extracted at all then Bayesian networks are used in Phase-II for conflict resolution and missing value prediction. Phase-II is mainly divided into two modules: Bayesian network learning module and prediction module.

-Learning Module: This module first performs data cleaning and data pre-processing (discretization of continuous data and removal of anomalies), and then learns the probabilistic relationships that exist among the attributes by learning the structure and parameters of a BN. -Prediction Module: If there are missing and/or conflicting values in the extracted data set then this module uses Bayesian inference mechanism to predict missing values and to resolve conflicts. In case of missing values, all the non-missing/nonconflicting values are considered as hard evidence and the posterior marginal probability of the missing attribute is computed. The value with the highest probability is considered the missing value if it satisfies a particular threshold value.

In case of multiple values belonging to an attribute (conflict resolution), the attribute's value is considered as missing and all the non-missing/non-conflicting values are entered as hard evidences in the BN. The posterior marginal probability of this attribute is computed next. Among the multiple values, the value with the highest posterior probability is selected as the winner and is assigned to the corresponding attribute.

Comparative Analysis

This section identifies the similarity and dissimilarity of ontoX and BNOSA in terms of their knowledge specification mechanisms and information extraction processes.

Ontology Specification:

Both approaches use ontology to define the domain knowledge as well as some additional information that is utilized during the information extraction phase.

The similarities in ontology specification are:  The comment section of the owl:AnnotationProperty is used to define and store the context keywords. It must be stated, however, that finding/defining all relevant keywords requires manual analysis of documents collection which in itself is a labor intensive and time consuming process.  Ontology constructs are used to define domain knowledge.  The ranges of possible values of an attribute are constrained by defining its data type such as int, float, date, etc. The differences in ontology specification are:

 ontoX uses owl:AnnotationProperty to define few additional properties as well. This includes quality and temporal properties. Such properties are not defined by BNOSA.  To handle a string type attribute, ontoX defines its range through xsd:Name property if the attribute has large number of instances. In case of only few instances, it uses the enumeration construct. BNOSA, on the other hand, defines all possible instance values in the comment section without specifying context keywords.

Information Extraction:

To extract values of each attribute, rules need to be generated. Both approaches define ranges of attributes' values as data types provided by OWL. The rules, thus, are generated according to the corresponding primitive data type. These rules, defined in the form of regular expressions, are used to extract values from the text. The similarities in the extraction process are:  Both approaches try to locate an attribute value within the neighborhood of the corresponding context keywords.  Each attribute can have more than one keywords associated with it therefore more than one value can be extracted for an attribute. The differences in the extraction methodology are:

 ontoX considers the neighborhood of a context keyword as the area ranging from its previous keyword to its next keyword. BNOSA, on the other hand, considers a fixed number of characters surrounding the keyword as its neighborhood.  If one value is found to be relevant to more than one attribute than ontoX resolves it using confidence level, while BNOSA assigns this value to each of the attributes.  To select one value from more than one extracted value, ontoX computes the level of evidence, while BNOSA resolves it using the Bayesian network.  BNOSA also uses Bayesian networks to predict missing values which is not performed by ontoX.  OntoX also has an ontology change detection mechanism which is not implemented in BNOSA yet.

Experimental Results

This section evaluates the extraction results of ontoX and BNOSA when they are applied on the same data set. To compare the results, the same data set has been selected as used by Burcu et al. [START_REF] Yildiz | ontoX-A Method for Ontology-Driven Information Extraction[END_REF], which is a collection of digital camera reviews available on a retail website 4 . A sample data is shown in Table 1. The evaluation is done on the basis of recall and precision values. The values are computed as:

where N is the number of values extracted from the document, C is the number of correctly extracted values, and I is the number of incorrectly extracted values. As discussed earlier, BNOSA uses Bayesian network to predict missing values and to resolve conflicts. But before being used for this purpose, a Bayesian network needs to be learned from the available data. The first step in this process requires discretizing numerical values. The discretized data is then used to train the Bayesian network. Fig. 1 shows the Bayesian network learned from the discretized camera data set. Once a BN has been learned, it is used for conflict resolution and for missing value prediction as explained in Section 2.2. ontoX, on the other hand, uses level of evidence for conflict resolution. Unlike BNOSA, there is no mechanism in ontoX to predict the missing values. To keep the results and the analysis of the experiment consistent, the prediction feature of BNOSA is not utilized during the experiments. Similarly, when there are a large number of possible instances belonging to a string type attribute, such as Model of a camera, ontoX models these instances through xds:Name property and uses a heuristic to resolve conflicts. The results reported in [START_REF] Yildiz | ontoX-A Method for Ontology-Driven Information Extraction[END_REF] show a good rate of recall and precision values for such string data types. BNOSA, on the other hand, stores all the possible values in the comments sections. Despite some obvious limitations, the approach used by ontoX -for large number of instances belonging to a string data typeis more generic and is superior in terms of its expressiveness. The method employed by BNOSA, however, would still generate better results as it stores all the instances in the comments section of the ontology. It is for these reasons; string data types with large number of instances are not compared in this analysis. String type attributes with small number of instances, however, are still being considered because both ontoX and BNOSA store them in the ontology albeit differently. The results of the extraction process by ontoX and BNOSA are shown in Table 2 and Table 3, respectively. The corresponding graphical representation of the results is shown in Fig. 2. It can be seen from the tables and the figure that in general BNOSA performs better than ontoX and, in few cases, the difference in the recall and precision values is significantly higher. For example, the recall and precision values of ontoX for MegaPixel is within the range of 0.5. In contrast, BNOSA produces recall and precision values for the same attribute in the range of 0.9. Other entries can be read and interpret in a similar fashion.

This difference in the performance is primarily due to different heuristics/methods used by these approaches. For instance, when selecting the neighborhood area of a keyword, BNOSA considers a fixed number of characters on either side of the keyword. ontoX, on the other hand, uses the whole area between a keyword and its left and right neighboring keywords. This, in some cases, may produce more conflicts. Another reason might be the use of level of evidence in ontoX. Being a user-defined metric/heuristic, an inaccurate specification may degrade the performance of the whole ontoX framework. In contrast, BNOSA uses Bayesian networks which learn the probabilistic relationship from the available data set and can be considered more robust when compared to a userdefined metric. It must be stated, however, that BN learning requires the availability of a large data set to accurately reflect the probabilistic relationship that exist among the variables in a problem domain.

Conclusion

The paper compared the information extraction capabilities of two semantic annotation frameworks, namely BNOSA and ontoX. Both frameworks model and store knowledge about a problem domain in an ontology and uses it during the information extraction phase. They, however, differ in ways, information is located, conflicts are resolved and missing values are predicted. Experiments were conducted on a sample data set to analyze the strengths and weaknesses of both frameworks. The results suggest that BNOSA performs significantly better than ontoX on the selected data set. The statement, however, cannot be generalized unless thoroughly tested on many data sets and that too of a much larger size as compared to the one selected in this study. The comparison of BNOSA with ontoX and few other information extraction techniques on multiple large data sets is one of the future research directions.

Fig. 1 .

 1 Fig. 1. Bayesian network learned model for digital camera

  The other property is relevance, which takes one of the two values {true, false}. It tells the system that a user is not very interested in this property, but if found then extract it because the construct is part of the domain of interest.-Temporal properties: Temporal properties provide two kinds of services: temporal

	type which is specified as xsd:Name 3 with the aid of named-entity-probability
	heuristic.
	-Quality properties: Quality properties enrich the constructs in ontology by creating
	two additional properties. The first one is confidence-level, which takes values
	between [0, 1]. It indicates the level of confidence of the ontology engineer that the
	construct is relevant. It also helps in situations when the same value is assigned to
	two different attributes. If such a situation arises, the property with the higher
	confidence level is considered the winner.
	Ontology Management Module (OMM): This module builds a domain-specific ontology
	to be used for information extraction. Different constructs of the ontology such as
	classes, object properties and data-type properties (also called attributes) as well as
	additional properties defined in the owl:AnnotationProperty element are utilized during
	the information extraction phase. The additional properties based on context keywords,
	constraints, quality properties and temporal properties are defined for each construct in
	the ontology.
	-Keywords: The context keywords help in finding the location of relevant information
	in a corpus.
	-Constraints: Constraints are used to narrow down the range of possible values
	belonging to an attribute. Standard data types are used to define such ranges. For
	example, int data type specifies that the value is of integer type, float data type
	specifies that the value is of float type, and so on. The only exception is the string data

2.1 ontoX: Ontology Driven Information Extraction

Burcu et al.

[START_REF] Yildiz | ontoX-A Method for Ontology-Driven Information Extraction[END_REF]

presented a framework to extract relevant data from existing web documents. The methodology suggests an ontology-driven information extraction process. It builds a domain specific ontology which is utilized during the information extraction phase. A tool, ontoX, was implemented based on the proposed scheme. The ontoX system consists of three main modules: i) Ontology Management Module, ii) Rule Generation Module and iii) Extraction Module. extraction and change management. With temporal extraction property, a user can state if she wants her input data to be extracted and can suggest valid-time-begin and valid-time-end properties for every construct defined in the ontology. With change management property, users can provide suggestions regarding out-of-date concepts if they do not appear in the corpora anymore.

Table 1 .

 1 Camera data available in reviews

	Mega Pixel Optical Zoom	Display Storage Medium Movie Format Battery
	5.0		2.5	SD	QuickTime
	5.0	12	1.8	SD	QuickTime	Lithiumion
		3	2.0	SD		AA
	7.1	4	2.0
	6.0	12	2.0
	5		1.8	XD	AVI	lithium
	5	3			VGA
		4		FC

Table 2 .

 2 Extraction results using ontoX

		Number of	Correctly	Incorrectly	Recall	Precision
		fact	identified facts	identified facts
	Megapixel	137	70	63	0.51	0.52
	Optical zoom	124	105	22	0.84	0.82
	Display size	113	93	23	0.82	0.80
	Storage medium	61	15	56	0.25	0.22
	Movie format	56	41	59	0.73	0.41

Table 3 .

 3 Extraction results using BNOSA

		Number of	Correctly	Incorrectly	Recall	Precision
		fact	identified facts	identified facts
	Megapixel	137	121	7	0.88	0.95
	Optical zoom	125	104	17	0.83	0.86
	Display size	113	108	19	0.96	0.85
	Storage medium	61	46	5	0.75	0.90
	Movie format	55	50	52	0.91	0.49

Fig. 2. Graphical view of extraction result

www.ebay.com

www.craigslist.org

The value space of xsd:Name is a set of all strings that match the Name production of XML 1.0.

http://www.steves-digicams.com/

Acknowledgements. The first author is extremely grateful to Dr. Burcu Yildiz for helping her in running ontoX as well as for sharing the camera data set which made the comparison reported in this paper possible.


Kyriaki Kitikidou

Lazaros Iliadis

A multi-layer perceptron neural network to predict air quality through indicators of life quality and welfare

Keywords: Air quality, Economic welfare, Artificial Neural Networks, Multi-Layer Perceptron, Quality Of Life

This paper considers the similarity between two measures of air pollution/quality control, on the one hand, and widely used indicators of life quality and welfare, on the other. We have developed a multi-layer perceptron neural network system which is trained to predict the measurements of air quality (emissions of sulphur and nitrogen oxides), using Eurostat data for 34 countries. We used life expectancy, healthy life years, infant mortality, Gross Domestic Product (GDP) and GDP growth rate as a set of inputs. Results were dominated by GDP growth rate and GDP. Obtaining accurate estimates of air quality measures can help in deciding on distinct dimensions to be considered in multidimensional studies of welfare and quality of life.

Introduction

Quantitative analysis of quality of life (QOL) across countries, and the construction of summary indices for such analyses have been of interest for some time [START_REF] Slottje | Measuring the Quality of Life Across Countries: A Multidimensional Analysis[END_REF]. Most early work focused on largely single dimensional analysis based on such indicators as per capita GDP, the literacy rate, and mortality rates. Maasoumi (1998) [START_REF] Maasoumi | Multidimensional approaches to welfare[END_REF] and others called for a multidimensional quantitative study of welfare and quality of life. The argument is that welfare is made up of several distinct dimensions, which cannot all be monetized, and heterogeneity complications are best accommodated in multidimensional analysis. [START_REF] Hirschberg | Cluster analysis for measuring welfare and quality of life across countries[END_REF] [START_REF] Hirschberg | Cluster analysis for measuring welfare and quality of life across countries[END_REF] and Hirschberg et al. (1998) [START_REF] Hirschberg | A cluster analysis the quality of life in the United States over time[END_REF] identified similar indicators, and collected them into distinct clusters which could represent the dimensions worthy of distinct treatment in multidimensional frameworks.

In this research effort we have considered the role of air quality indicators in the context of economic and welfare life quality indicators, using artificial neural networks (ANN). Therefore in this presentation we have obtained the key variables (life expectancy, healthy life years, infant mortality, Gross Domestic Product (GDP) and GDP growth rate) and developed a neural network model to predict the air quality outcomes (emissions of sulphur and nitrogen oxides). Sustainability and quality of life indicators have been proposed recently by [START_REF] Flynn | Sustainability & Quality of life indicators: Towards the Integration of Economic, Social and Environmental Measures[END_REF] [START_REF] Flynn | Sustainability & Quality of life indicators: Towards the Integration of Economic, Social and Environmental Measures[END_REF] and life quality indices have been used to estimate willingness to pay [START_REF] Pandey | Life quality index for the estimation of social willingness to pay for safety[END_REF]. The innovative part of this research effort lies in the use of a soft computing machine learning approach like the ANN to predict air quality.

Materials and Methods

It is well known that the quality of the air in a locale influences the health of the population and ultimately affects other dimensions of that population's welfare and its economy. As a simple example, in cities where pollution levels rise significantly in the summer, worker absenteeism rates rise commensurately and productivity is adversely impacted. Other dimensions of the economy are influenced on "high pollution days" as well. For example, when outdoor leisure activity is restricted this may have serious consequences for the service sector of the economy [START_REF] Bresnahan | Averting behavior and urban air pollution[END_REF]. In this paper, we have introduced two measures of environmental quality or air quality as quality of life factors. A feature of these indices is the fact that these types of pollution are created by some of the very activities that define economic development. The two factors under investigation here are sulfur oxides (SOx) and nitrogen oxides (NOx) (million tones of SO 2 and NO 2 equivalent, respectively). They are both produced as byproducts of fuel consumption as in case of the generation of electricity. Vehicle engines also produce a large proportion of NOx. SOx is primarily produced when high sulfur coal is burned which is usually in large-scale industrial processes and power generation. Thus, the ratio of these emissions to the population is an indication of pollution control.

The attributes of quality of life used in this paper are the following: • Life expectancy at birth: The mean number of years that a newborn child can expect to live if subjected throughout his life to the current mortality conditions (age specific probabilities of dying). • Healthy life years: The indicator Healthy Life Years (HLY) at birth measures the number of years that a person at birth is still expected to live in a healthy condition. HLY is a health expectancy indicator which combines information on mortality and morbidity. The data required are the age-specific prevalence (proportions) of the population in healthy and unhealthy conditions and agespecific mortality information. A healthy condition is defined by the absence of limitations in functioning/disability. The indicator is also called disability-free life expectancy (DFLE). Life expectancy at birth is defined as the mean number of years still to be lived by a person at birth, if subjected throughout the rest of his or her life to the current mortality conditions. • Infant mortality: The ratio of the number of deaths of children under one year of age during the year to the number of live births in that year. The value is expressed per 1 000 live births. • Gross Domestic Product (GDP) per capita: GDP is a measure of the economic activity, defined as the value of all goods and services produced less the value of any goods or services used in their creation. These amounts are expressed in PPS, i.e. a common currency that eliminates the differences in price levels between countries allowing meaningful volume comparisons of GDP between countries. • GDP growth rate: The calculation of the annual growth rate of GDP volume is intended to allow comparisons of the dynamics of economic development both over time and between economies of different sizes. For measuring the growth rate of GDP in terms of volumes, the GDP at current prices are valued in the prices of the previous year and the thus computed volume changes are imposed on the level of a reference year; this is called a chain-linked series. Accordingly, price movements will not inflate the growth rate. Data were extracted for 34 European countries, for the year 2005, from the Eurostat database [START_REF]Eurostat[END_REF]. Descriptive statistics for all variables are given in Table 1. For the performance of the analysis, multi-layer perceptron (MLP) network models were used, employing the back propagation (BP) optimization algorithm. As it is well known in BP the weighted sum of inputs and bias term are passed to the activation level through the transfer function to produce the output ([1], [START_REF] Fine | Feedforward Neural Network Methodology[END_REF], [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF], [START_REF] Ripley | Pattern Recognition and Neural Networks[END_REF]). The sigmoid transfer function was employed ([3], [START_REF] Kecman | Learning and Soft Computing[END_REF]), due to the fact that the algorithm requires a response function with a continuous, single valued with first derivative existence [START_REF] Picton | Neural Networks[END_REF]. These networks were trained in an iterative process. The number of hidden layers is chosen to be only one to reduce the network complexity, and increase the computational efficiency [START_REF] Haykin | Neural Networks: A Comprehensive Foundation[END_REF]. The schematic representation of the neural network is given in Fig. 1. Fig. 1. Multi-layer perceptron network structure.

Results-Discussion

From the analysis, 19 cases (70.4%) were assigned to the training sample, 2 (7.4%) to the testing sample, and 6 (22.2%) to the holdout sample. The choice of the records was done in a random manner. The whole effort targeted in the development of an ANN that would have the ability to generalize as much as possible. The seven data records which were excluded from the analysis were countries that did not had available data on Healthy Life Years. Two units were chosen in the hidden layer.

Table 2 displays information about the results of training and applying the final network to the holdout sample. Sum-of-squares error is displayed because the output layer has scale-dependent variables. This is the error function that the network tries to minimize during training. One consecutive step with no decrease in error was used as stopping rule. The relative error for each scale-dependent variable is the ratio of the sum-of-squares error for the dependent variable to the sum-of-squares error for the "null" model, in which the mean value of the dependent variable is used as the predicted value for each case. There appears to be more error in the predictions of emissions of sulphur oxides than in emissions of nitrogen oxides, in the training and holdout samples.

The average overall relative errors are fairly constant across the training (0.779), testing (0.615), and holdout (0.584) samples, which give us some confidence that the model is not overtrained and that the error in future cases, scored by the network will be close to the error reported in this table. In the following Table 3 parameter estimates for input and output layer, with their corresponding biases, are given. (Fig. 2) and (Fig. 3), respectively. There appears to be more error in the predictions of emissions of sulphur oxides than in emissions of nitrogen oxides, something that we also pointed out in Table 2. The importance of an independent variable is a measure of how much the network's model-predicted value changes for different values of the independent variable. A sensitivity analysis to compute the importance of each predictor is applied. The importance chart (Fig. 4) shows that the results are dominated by GDP growth rate and GDP (strictly economical QOL indicators), followed distantly by other predictors.

Conclusions

The multi-layer perceptron neural network model, that was trained to predict air quality indicators, using life quality and welfare indicators, appears to perform reasonably well. Results showed that GDP growth rate and GDP influenced mainly air quality predictions, while life expectancy, infant mortality and healthy life years followed distantly.

One possible way to ameliorate performance of the network would be to create multiple networks. One network would predict the country result, perhaps simply whether the country increased emissions or not, and then separate networks would predict emissions conditional on whether the country increased emissions. We could then combine the network results to likely obtain better predictions. Note also that neural network is open ended; as more data is given to the model, the prediction would become more reliable.

  the network does a reasonably good job of predicting emissions of sulphur and nitrogen oxides. Ideally, linear regression parameters a and b should have values 0 and 1, respectively, while values of the observed-by-predicted chart should lie roughly along a straight line.

Figs 2 and 3

 3 actually seem to suggest that the largest errors of the ANN are overestimations of the target values.

Fig. 2 .

 2 Fig. 2. Linear regression of observed values for emissions of sulphur oxides by predicted values.

Fig. 3 .

 3 Fig. 3. Linear regression of observed values for emissions of nitrogen oxides by predicted values.

Fig. 4 .

 4 Fig. 4. Independent variable importance chart.

Table 1 .

 1 Descriptive statistics for all variables used in the analysis.

		Emissions	Emissions
		of	of
		sulphur oxides (million tones	nitrogen oxides (million tones	Infant Mortality	GDP (PPS)	GDP Growth Rate	Life Expectancy At Birth (years)	Healthy Life Years
		of SO 2	of NO 2
		equivalent)	equivalent)
	Valid N	34	34	34	33	33	33	27
	Missing	0	0	0	1	1	1	7
	Mean	0.503	0.372	5.721 95.921 4.206	77.535	60.448
	Std. Deviation	0.648	0.482	4.227 46.620 2.521	3.244	5.443
	Min	0.00	0.00	2.30	28.50	0.70	70.94	50.10
	Max	2.37	1.63	23.60 254.50 10.60	81.54	69.30

Table 2 .

 2 Model Summary.

	Training	Sum of Squares Error		14.029
		Average Overall Relative Error	0.779
		Relative Error for Scale	Emissions of sulphur oxides	0.821
		Dependents	(million tones of SO 2
			equivalent)
			Emissions of nitrogen	0.738
			oxides (million tones of
			NO 2 equivalent)
	Testing	Sum of Squares Error		0.009
		Average Overall Relative Error	0.615
		Relative Error for Scale	Emissions of sulphur oxides	0.390
		Dependents	(million tones of SO 2
			equivalent)
			Emissions of nitrogen	0.902
			oxides (million tones of
			NO 2 equivalent)
	Holdout	Average Overall Relative Error	0.584
		Relative Error for Scale	Emissions of sulphur oxides	0.603
		Dependents	(million tones of SO 2
			equivalent)
			Emissions of nitrogen	0.568
			oxides (million tones of
			NO 2 equivalent)

Table 3 .

 3 Parameter Estimates.

	Predictor					Predicted
					Hidden Layer 1		Output Layer
					H(1:1)	H(1:2)	SO 2	NO 2
	Input Layer		(Bias)		-0.119	-0.537
			Infant Mortality	-0.805	0.752
			GDP		1.033	-3.377
			GDP Growth Rate	0.318	-3.767
			Life Expectancy	1.646	1.226
			At Birth
			Healthy Life Years	0.567	0.358
	Hidden Layer 1	(Bias)					-0.635	-0.877
			H(1:1)					-0.518	0.116
			H(1:2)					1.396	1.395
	Linear	regression	between	observed	and	predicted	values