Hichem Bouchenitfa

Julien Chaves-Jacob

Jean-Marc Linares

Jean- Michel Sprauel

Noureddine Salim Boukebbab

Improvement of toolpath quality combining polynomial interpolation with reduction of toolpath points

Keywords: Toolpath, 5-axis milling, Polynomial interpolation, Meshed surface, Free-form surfaces, Biomedical

The aim of this study is to propose a 5-axis toolpath smoothing method in order to improve the quality of machined surfaces. Currently, toolpaths are commonly computed from CAD models presenting small geometrical discontinuities. These discontinuities may be caused by an insufficient quality of the CAD model (geometrical discontinuities) and the use of meshed surfaces (e.g. STL files). Normally, CAM systems generate linearly interpolated toolpaths. CNC options are then used on the machine to smooth the toolpath. The geometrical discontinuities of CAD models and linear toolpath interpolation may induce a unsmooth toolpath. This type of toolpath causes marks on the machined workpiece even if classical enhanced CNC options are used. Generally, these marks are unacceptable for the functionality of the workpiece. To reduce this problem, this study proposes a method to efficiently smooth toolpaths and consequently improve the obtained surface quality. The proposed method may be employed with high end controllers commonly used on 5-axis CNC machines. First, a five degree polynomial interpolation method is presented. This interpolation is computed to ensure geometrical continuity in the slope and curvature of the obtained toolpath. Next, a concatenation method is proposed to reduce the size of the CNC program and to improve the toolpath smoothness. Moreover, the purpose of this concatenation is to obtain an optimized repartition of points along the toolpath. Furthermore, in a reverse engineering process this method avoids surface reconstruction, decreasing the process time and improving the quality of the obtained surface. The efficiency of these methods is validated by the machining of biomedical prostheses. The CAD model used for the test is a meshed surface.

Introduction

Currently, the CAD model is essential to the machining of a free-form surface.

Subsequently this model is exported to CAM software to permit toolpath computation.

However, To complete this transfer, it is sometimes necessary to use exchange formats. In the case of STL data that builds meshed surfaces, a lot of geometrical discontinuities are then present in the resulting CAD model. Furthermore, meshed CAD models may also be obtained by 3D-acquisition in a reverse engineering process. Figure 1 presents the different solutions to machine a surface in a reverse engineering approach. #1: the historical solution starts with the surface reconstruction based on point clouds or meshed surfaces. Lim et al. [START_REF] Lim | Surface reconstruction techniques: a review[END_REF] proposed a review of different techniques and soft computing methods for surface reconstruction. The author insisted on the importance of pre-processing steps such as compression and simplification. Furthermore, the author highlighted the errors introduced by the reconstruction step. After the reconstruction step, the toolpath is computed on the reconstructed surface. This solution imposes the surface reconstruction step, which is tedious and may introduce large errors between the measured points and the reconstructed surface. Generally, an approximation or an interpolation is used to reconstruct the surface. #2: the second solution is to directly compute the toolpath on the point cloud. Park et al. [START_REF] Park | Tool-path generation from measured data[END_REF] proposed a method for this technique including on rough and finishing toolpaths. These methods are based on the slicing of the point cloud and the determination of machining regions applying an algorithm which calculates the boundary of a point cloud. On the other hand, the method proposed by Zhang et al. [START_REF] Zhang | Adaptive tool-path generation on point-sampled surfaces[END_REF] consists in projecting an initial toolpath onto the point cloud. Then, an interpolation with Bezier curves is performed to smooth the obtained toolpath. Freg et al. [START_REF] Feng | Iso-planar piecewise linear NC tool path generation from discrete measured data points[END_REF] proposed a method to compute an iso-planar toolpath directly on a point cloud. This toolpath is obtained using a CL-net cell boundary, which is a pattern of rectangular cells. These patterns support the toolpath and are determined to ensure the specified machining error and scallop height constraints. Chiu et al. [START_REF] Chui | Direct 5-axis tool-path generation from point cloud input using 3D biarc fitting[END_REF] used a method to construct a triangular meshed surface from point clouds. Subsequently, the computed toolpath is based on this meshed surface using toolpath smoothing with Biarc curves.

#3: the third solution is based on a meshed surface (generally triangular) to compute the toolpath. The advantages of this technique, compared to the first, are time reduction and improvement of geometrical accuracy. Certainly, a point cloud is easier to best fit by a triangular pattern than a free-form surface (Bezier, Bspline, Nurbs…). Sun et al. [START_REF] Sun | Iso-parametric tool path generation from triangular meshes for free-form surface machining[END_REF] proposed a method to compute 5-axis iso-parametric toolpaths on triangular meshed surfaces. This method is based on the parameterization of the meshed surface via a harmonic map method.

Park [START_REF] Park | Sculptured surface machining using triangular mesh slicing[END_REF] presented a method to compute a toolpath on meshed sculptured surfaces. This method begins with the determination of the CL (Cutter Location) surface: place of driven points. Subsequently, a 2D toolpath is projected onto the meshed surface using a vertical slicing strategy. Jun et al. [START_REF] Jun | A new curve-based approach to polyhedral machining[END_REF] also began computing the CL surface. This CL surface is meshed and then sliced by parallel planes to obtain the toolpath. Kim et al. [START_REF] Kim | A CL surface deformation approach for constant scallop height tool path generation from triangular mesh[END_REF] also defined a method based on the CL surface to machine meshed surfaces. This method deforms the CL surface to obtain a constant scallop height toolpath. Gouging problem is one of the main difficulties in the 5-axis toolpath computing on meshed surfaces. Lauwers et al. [START_REF] Lauwers | Development of a Five-axis Milling Tool Path Generation Algorithm based on Faceted Models[END_REF] proposed a method to compute toolpath directly on meshed model. The method starts computing the toolpath without considering gouging and after the tool position is adapted to suppress the gouging problem. The tool position adaptation is carried out in tool lift and orientation. Lu et al. [START_REF] Lu | A three-dimensional configuration-space method for 5-axis tessellated surface machining[END_REF] defined a first toolpath using the step-over distance to ensure the required machining tolerance. Thereafter, the tool position is modified to avoid gouging. Kiswanto et al. [START_REF] Kiswanto | Gouging elimination through tool lifting in tool path generation for five-axis milling based on faceted models[END_REF] proposed to lift the tool to avoid gouging. An algorithm was developed to determine the lift value of the tool based on the type of gouging.

Lasemi et al. [START_REF] Lasemi | Recent development in NC machining of freeform surfaces: A stat-of-the-art review[END_REF] explained that currently the use of the second and third solutions is emerging (figure 1). Certainly, in reverse engineering, this method helps avoiding surface reconstruction before CAM process. Accordingly, in these methods, CAD models characteristically present geometrical discontinuities. These geometrical discontinuities will have a great influence on the toolpath continuity inducing marks on the finished surface.

These marks affect the functionality of the finished surfaces. Chaves-Jacob et al. [START_REF] Chaves-Jacob | Increasing of surface quality in friction free-form surfaces of knee prosthesis[END_REF] carried out a design of experiment to highlight the effect of the CAD surface discontinuities on the machined surface quality.

Currently a toolpath is commonly defined by a sequence of ordered points linked by linear trajectories. Certainly, a slope discontinuity is present at each toolpath point. To solve this problem, new interpolations are developed. For example, a sliding five-degree polynomial interpolation was proposed to smooth toolpath discontinuities and accordingly surface smoothness [START_REF] Chaves-Jacob | Increasing of surface quality in friction free-form surfaces of knee prosthesis[END_REF]. Other interpolations are developed like B-Spline interpolation. Such approaches are presented by Langeron et al. [START_REF] Langeron | A new format for 5-axis tool path computation, using Bspline curves[END_REF] and Lartigue et al. [START_REF] Lartigue | High-Performance NC for HSM by means of Polynomial Trajectories[END_REF]. In this case, interpolation is integrated in an industrial CAM system. Furthermore, Yong et al. [START_REF] Yong | A parametric interpolator with confined chord errors, acceleration and deceleration for NC machining[END_REF] used a curve interpolation to smooth slope discontinuities. Actually, the authors added a B-Spline corner to increase the feed rate.

On the other hand, the distance between two consecutive points of a toolpath may induce a reduction of the feed rate in high speed machining. Lavernhe et al. [START_REF] Lavernhe | Kinematical performance prediction in multiaxis machining for process planning optimization[END_REF] presented a predictive model of kinematic behaviour for a 5-axis machine. In this study, the author explains that to avoid a reduction of the feed rate, a minimal distance between two consecutive points must be ensured. This distance depends on the CNC computer performance.

Figure 2 highlights the main problems of a toolpath computed on a meshed surface:

The first problem is the large discontinuities in the slope of the generated toolpath segments.

By nature, meshed surfaces present slope discontinuities between two facets. These discontinuities will evidently induce large slope discontinuities in the toolpath.

The second problem is the non-homogeneous density of points along the toolpath and the presence of overabundant points. The CAM system computes a toolpath to ensure an objective deviation between the nominal surface and the computed toolpath. Generally, this acceptable deviation is called chordal error. Figure 2 illustrates the toolpath of the contact points between the tool and the surface computed using an iso-planar strategy. To compute this toolpath, the CAM system begins computing the intersection line between a plane and the nominal surface. Next, the CAM system computes points on this intersection line; these points are the cutter contact points of the toolpath. The distance between these points is determined to ensure the chordal error. Finally, the CAM system computes the coordinates of the drive point. In the case of meshed surface machining, the intersection line is a succession of segments (each segment is the intersection of the plane and a triangular facet). Naturally, these segments will become the cutter contact toolpath with a chordal error equal to zero. In this case, the segment length is determined by the position of the plane relative to the triangle facet. Accordingly, the repartition of the point along the toolpath is not relevant and is minimal to its geometrical definition as illustrated in figure 2.

This study proposes toolpath smoothing using a polynomial interpolation combined with a concatenation method. Proposed method may be employed with high end controllers commonly used on 5-axis CNC machines. The concatenation method smoothes sets of initial toolpath points by polynomial segments. This method increases the size of each polynomial segment and reduces the number of segments. This concatenation is carried out to ensure a specified tolerance. The aim of both proposed methods is to improve the quality of the machined surface. The proposed method carries out the smoothing of an unsmooth toolpath.

Thereby, it is appropriated to solve the two mains problems of toolpath computed on meshed surfaces but it may also be used to improve the quality of any toolpath. The proposed method is useful and may improve the quality of the toolpath computed on unsmooth surfaces. The method may be used with any type of tool. Indeed, Vickers et al. [START_REF] Vickers | Ball-Mills Versus End-Mills for Curved Surface Machining[END_REF] highlighted the importance of the type of milling tool on the machining efficiency in end milling. Furthermore, in the proposed method the gouging problem is handled during the initial computation of the toolpath. In fact, the deviations introduced by the toolpath smoothing are small and can be neglected in the gouging phenomenon. The combination of polynomial interpolation and concatenation methods permits machining meshed free-form surface without surface reconstruction.

Fig.2

The main problems of the toolpath computed on meshed surfaces.

This study is composed of three sections. The first section presents the polynomial interpolation method. This interpolation ensures continuity in slope and curvature over the whole toolpath. This method generates a smooth toolpath which may be read by common CNC machines. Moreover, this interpolation keeps the initial toolpath points. Subsequently, a concatenation method is developed to reduce the size of the CNC program and to improve the smoothing of the toolpath. This method automatically suppresses the toolpath points that are not necessary to obtain the required quality. Finally, the efficiency of both combined methods is tested by machining a biomedical meshed surface. The presented method is compared to solutions already implemented in actual CNC machines. This experimental machining test highlights the quality of the machined surface obtained by the proposed method.

Proposed polynomial interpolation method

In industry the most commonly used interpolation is the linear interpolation between two consecutive points of the toolpath. In addition, common CNC machine controllers are also able to perform polynomial and B-spline interpolations. Polynomial interpolation is proposed to smooth unsmooth toolpaths. Certainly, toolpaths computed on CAD models that include geometrical discontinuities (e.g. Meshed models) will not be smoothed. This type of toolpath induces marks on the machined surface that affect the functionality of the surface. The aim of the proposed method is to smooth the initial toolpath with a soft polynomial interpolation. Two classical mathematical formulations are available on CNC machine controllers: standard polynomial interpolation and Bspline fitting. Standard polynomial interpolation was however selected for his main advantage: the simplicity for an operator in front of the CNC machine to read the program. Indeed, Bspline formulation uses control points that do not belong to the real toolpath, what disturbs the reading.

The proposed method starts from a linear interpolation toolpath as computed by common CAM software. The aim of the method is then to associate a smooth polynomial curve between two successive points of the linear toolpath. The proposed interpolation is defined to improve the mathematical continuity of the toolpath. It ensures the continuity of the toolpath in both slope and curvature and consequently leads to smooth variations of the tool acceleration. In fact, the minimal polynomial degree required to ensure such conditions is three. Indeed, the polynomial must cross the start and end points of a given interpolation interval (e.g. M i and M i+1 in Figure 3). At each toolpath point, the slope and curvature calculated from the left and right interpolation polynomials are also to be the same. These four constraints impose thus a minimum polynomial degree of three. However, with no additional constraint the slope and curvature of each toolpath point are then fixed by the coordinates of the start and end points of the left interpolation interval. This leads to spurious undulations. To overcome, this impediment the slopes and curvatures were imposed (with a robust method: parabolas) at each point of the toolpath. These conditions increase to six the number of constraints of each polynomial (i.e. fixed coordinates, slopes and curvatures of the start and end points of each interpolation interval), thus leading to a five degree formulation.

The sliding five-degree polynomial toolpath is used to smooth the path between the successive points of the initial toolpath. Figure 3 presents the used nomenclature. Parabolas are used to control the slope and the curvature in the link between two consecutive five degree polynomial curves. These parabolas are a mathematical artefact. A Parabola is the simplest mathematical curve to compute the curvature at a given point. Furthermore, the computation of a parabola through three points is very robust. At point M i a parabola is computed to cross the three points M i-1 , M i and M i+1 . Eq. 1 gives the expression of the parabola. This procedure defines the slopes and curvatures to be imposed at the start and end points of the five-degree interpolation polynomial. Accordingly, the continuity in slope and curvature of the whole toolpath is ensured.

Fig.3 Interpolation on a segment

Subsequently, computations are presented for the X-axis only. The same treatment is however applied to Y and Z axes to obtain the toolpath.

2 2 1 0 i ) ( parabola u d u d d X u       (1)
The value of the parameter u at each point must be chosen to determine the coefficients d 0 , d 1 and d 2 of Eq. 1. The parameter u is imposed to -1 at point M i-1 , 0 at point M i and 1 at point M i+1 . These choices produce the results presented in Eq. 2.

              2 1 0 1 2 1 0 1 0 d d d x d d d x d x Mi Mi Mi (2)
The coefficients of the parabola are determined solving Eq. 2. The results are presented in Eq. 3. This equation highlights that the coefficients of the parabola are only determined by the initial toolpath coordinates.

                   Mi Mi Mi Mi Mi Mi x x x d x x d x d 2 2 1 1 2 1 1 1 0 (3)
Subsequently, the first and second derivatives of the parabola i are computed at M i . The results of this computation are presented in Eq. 4. These values are respectively written Tx i and Cx i and are associated with point M i to compute the polynomial interpolation.

            2 2 i 2 1 i 2 ) 0 ( d ) Parabola ( d ) 0 ( d ) Parabola ( d d Cx u d Tx u i i (4)
Eq. 5 presents the mathematical definition of a five-degree polynomial. One polynomial is defined between each M i M i+1 interval. For example, if the initial toolpath has 10 points this method defines 9 polynomials. Each polynomial is driven by the parameter named p.

Subsequently, an arbitrary choice of the p value at M i and M i+1 is carried out, p is selected to have the value p=0 at M i and p=1 at M i+1 . Accordingly, the polynomial curve is imposed to cross the points M i and M i+1 . Furthermore, the first and second derivatives of the polynomial toolpath at M i are imposed respectively equal to Tx i and Cx i . Certainly, a five-degree polynomial curve between intervals M i M i+1 has 6 unknown parameters. On the other hand, this curve is submitted to 6 constraints:

-pass through M i and M i+1 ; -first derivatives at M i and M i+1 are imposed, respectively equal to that of the parabola i and parabola i+1 ; -second derivatives at M i and M i+1 are imposed respectively equal to that of the parabola i and parabola i+1 .

Eq. 6 synthesis all these constraints in a matrix form. Eq. 6 is solved to determine the equation of the five degree polynomial toolpath between M i and M i+1 . The last presented computations are only conducted for the X axis. Eq. 7 presents the mathematical form of the five degree polynomial for the three dimensions. The presented resolution of Eq. 6 in three dimensions enables the determination of all the polynomial coefficients of Eq. 7. This polynomial interpolation is computed for all M i M i+1 intervals built with the successive points of the initial toolpath. The characteristic of this method is the use of parabolas to determine the slope and curvature in the junction between two polynomial interpolations. The use of parabolas avoids the apparition of oscillations and leads to a great stability of the computed toolpath. This type of toolpath ensures thus a high quality of the machined surface. Subsequently, a CNC code is generated to be downloaded to the CNC machine. Most

                                           

Concatenation method

Section §2 proposed a method to compute a smooth polynomial interpolation between points of a toolpath. Certainly, this method defines a five-degree polynomial between the successive points of the initial toolpath. The aim of the concatenation method is to increase the length of each polynomial segment. The concatenation method is based on the skipping of unnecessary points. Points are skipped while a specified tolerance (IT C ) is maintained between the skipped points and the polynomial toolpath. The concatenation method generally has four objectives:

-To reduce the CNC program file size to avoid memory overflow, this problem is typical of complicated workpieces.

-To reduce the number of links. This will increase the toolpath quality and accordingly reduce the acceleration and deceleration steps. Consequently, the feed-rate can be increased and will be more stable, reducing the machining time.

-To get a homogeneous density of points along the toolpath, thus contributing to improve the toolpath quality.

-To skip close points of the initial toolpath. These close points may create feed rate decelerations along the toolpath inducing machining marks on the surface. Naturally, these close points can be skipped without loss of geometrical quality.

The idea behind this method is to skip initial toolpath points to increase the size of the polynomial, respecting a specified tolerance (IT C ). Figure 4 illustrates this idea. Figure 5 illustrates the main steps of the concatenation method. The algorithm presents the procedure to determine a polynomial toolpath between the points M i and M a . This iterative algorithm successively skips points as long as the error between each skipped point and the polynomial toolpath remains less than a specified tolerance IT C . Eq. 9 defines the value of the distance e i between a toolpath point and the polynomial toolpath. Indeed, this distance is an approximation of the real error made on the workpiece. Authors like Huang et al. [START_REF] Huang | Non-constant parameter nc tool path generation on sculptured surfaces[END_REF] propose to compute the real interferences caused by the chordal error. These computations need however to know the true shape of the machined surface. In the presented case only the toolpath is known to be smoothed. Furthermore, the specified tolerance (IT C ) is selected small in comparison to the machining tolerance.

)] ( Poly ; distance[ p M e i i i  (9)
The slope and curvature properties at point M a are computed using a parabola, which crosses the points M i , M a and M 2a-i . The iterative algorithm stops when: the tolerance is exceeded or the index of the last point of the initial toolpath is reached. When the tolerance is exceeded the polynomial toolpath is computed for the correct value of index a. The method used to compute the five-degree polynomial toolpath was already presented in section §2.

The presented concatenation method ensures a smooth toolpath. Furthermore, this method provides a reduced number of segments to ensure a specified tolerance between the nominal points and the concatenate toolpath.

4) Application

The Methods presented in sections §2 and §3 are used to machine a part of the tibial prosthesis plateau presented in Figure 6. The area of the friction surface machined for the tests is presented in this figure. An STL model with a small facet size defines the surface used to compute the toolpath. The toolpath is computed with industrial CAM software. An iso-planar strategy with 0.16 mm of step-over is used for that purpose. This STL model induces a toolpath with a lot of very close points. The machining was carried out in an aluminium alloy with a ball-end-tool with a diameter of 10 mm. The employed tool has four 3 000 mm/min (feed per tooth of 0.075 mm). Linear and polynomial toolpaths were employed and compared in this experiment. Three types of toolpaths were considered:

-The basic linear interpolation toolpath called G1 in table 1. This is the standard linear interpolation available in the CNC machine without using any enhanced interpolation option. This type of toolpath is not used to mill workpieces because it creates lot of vibration during machine displacement.

-The linear interpolation toolpath, named G1 + CNC options in table 1. This interpolation is the current method used in industry. It is a linear interpolation using CNC options to smooth free-form surfaces. In this case: G642 and COMPCAD commands of a SIEMENS 840D NC controller were used.

-The polynomial interpolation combined with a concatenation with IT C tolerance (methods presented in sections §2 and §3). This interpolation is defined by the value of IT C in table 1.

In table 1, the strategy with POLY and IT C equal to zero corresponds to a polynomial interpolation without concatenation. Fig. 6: definition of the machined and measured areas of the tibial plateau prosthesis Careful Roughness measurements were carried out using an optical chromatic confocal sensing Coordinate Measuring Machine (CMM). The resolution of the CMM sensor is about 10 nm. The Measurements were done on a 2 x 2.5 mm patch with a step of 4µm in both directions. Figure 6 presents the position of the measured area. To highlight the differences between the tested toolpaths, this area was selected along a local STL pattern defect. The form of the measured surface was filtered with a three degree polynomial surface. Then residuals of the best fit were used to compute the two roughness parameters, Sa (arithmetic average) and Sz (maximum height) presented in table 1.

Furthermore, table 1 presents:

-The number of toolpath points: this value expresses the number of non skipped points.

-The average length between two successive points of the toolpath. This parameter highlights that the initial toolpath (G1 in table 1) has very close points (0.1561 mm).

-The machining time is measured directly on the CNC machine for all toolpath strategies. Some experiments are conducted displacing the tool without workpiece. Since all the strategies have the same toolpath length, the execution time of such experiment is then used to characterize the real feed rate.

-The roughness parameters: The tests without workpiece have grey cells in these two columns.

Table 1 highlights the efficiency of the classical smoothing technique already incorporated in CNC options. Certainly, the machining time between the standard linear interpolation and the smoothed linear interpolation using CNC options is divided by more than five. The reduction of the machine tool feed rate may explain this phenomenon. Without CNC options, the machine must slow to exactly follow the specified points and undergoes all the geometrical discontinuities of the toolpath. In the STL file, the short distance between two successive points highlights this phenomenon.

Furthermore, this table shows that the polynomial interpolation without concatenation (IT C equal to zero) is not appropriated for small segments. Certainly, the machining time and the surface roughness are significantly increased compared to the CNC options toolpath. -The machining time versus the concatenation tolerance. This graph is composed of two curves: a solid line for the polynomial interpolation and a dotted line for the linear interpolation with CNC options (this curve is constant versus IT C ).

-The roughness maximum height versus the concatenation tolerance. This plot is also composed of two curves.

Table 1 and figure 7 show that increasing the concatenation tolerance reduces the machining time of polynomial interpolation. Furthermore, the polynomial interpolation presents an optimal value: in this case IT C = 0.01 mm. At this configuration, the roughness is the lowest and the machining time is close to the one obtained with the smoothing technique already implemented in the CNC options. Furthermore, this figure highlights that the studied method almost always improves the surface quality without significantly increasing the machining time. Figure 8 presents the measured surface micro-geometry (after form filtering) for the six machined surfaces. This roughness morphology is typical of iso-planar strategies on convex surfaces. Indeed, with such strategy, the tool axes stay in a plane during one pass but the cutter contact realises a trajectory that is curved in direction of the lowest point of the convex surface. Figure 7 highlights that in this case the optimal concatenation tolerance is 0.01 mm.

For this concatenation tolerance a smooth surface was obtained and the roughness parameters Sa and Sz were significantly decreased, respectively of 12% and 19%. The experimental tests illustrate the usefulness of the methods presented in sections §2 and §3. They highlight that the basic linear interpolation cannot be used to machine free-form surfaces defined by a meshed surface. Furthermore, in this case, the experimental test shows that the CNC options provide good machining time but the surface quality is not optimal. On the other hand, the test carried out with the proposed method (enhanced polynomial interpolation & concatenation) increases the surface quality with a similar machining time. Furthermore, an optimal tolerance value is found to carry out the best machining performance. Accordingly, the presented methods are efficient for machining meshed surfaces.

Conclusion

This study presents a method to efficiently smooth toolpaths computed on meshed surfaces. Naturally, such toolpaths present large slope discontinuities and a nonhomogeneous points repartition along the trajectory. A method was therefore proposed to overcome this impediment. The developed method is based on an enhanced five-degree polynomial interpolation. This interpolation is computed to ensure the continuity in slope and curvature of the computed toolpath. The geometrical continuity of the toolpath ensures smooth variations of the acceleration along the toolpath and consequently improves the quality of the machined surface. The proposed method may be employed with high end controllers commonly used on 5-axis CNC machines. This interpolation is coupled with a concatenation method. The aim of this method is to reduce the size of the CNC program and to remove overabundant points. This method is based on point skipping in order to increase the length of the polynomial segments. It however limits the maximum deviation between the original trajectory and the concatenated toolpath. To validate the approach, the usefulness of these two methods was tested for the machining of tibial plateau prostheses. In these tests, the CAD model of the workpiece is defined by a meshed model (*.STL). The experiments highlight that the proposed method presents an optimal value of concatenation tolerance.

The results show that the proposed method provides the same machining time as the classical smoothing technique already incorporated in CNC options and currently used in industry, but better surface roughness.

Fig. 1

 1 Fig.1 Possible solutions to machine a point cloud.

  CNC machines are able to read polynomial interpolations. Eq.8 presents a line of CNC program built for a SIEMENS 840D controller. The coefficients a 0 , a 1 , b 0 , b 1 , c 0 and c 1 are not provided in the program. These coefficients are linked to the current and end coordinates of each interpolation interval. The CNC program lines are not too complicated to write and can be easily read by a CNC operator. POLY X=PO(X Mi+1 , a 2 , a 3 , a 4 , a 5 ) Y=PO(Y Mi+1 , b 2 , b 3 , b 4 , b 5 ) Z=PO(Z Mi+1 , c 2 , c 3 , c 4 , c 5 ) PL=1[START_REF] Jun | A new curve-based approach to polyhedral machining[END_REF]

Fig. 4 :

 4 Fig. 4: concatenation method.

Fig. 5 :

 5 Fig.5: Flowchart of the concatenation method

Fig 7 :

 7 Fig 7: Evolution of the machining time and surface roughness versus the concatenation tolerance.

Fig 8 :

 8 Fig 8: Micro-geometry of the measured surface.


Jean-Marc M Linares

Jean Michel Sprauel

SIMULATION METHOD TO ESTIMATE THE UNCERTAINTIES OF ISO SPECIFICATIONS

d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction:

ISO/IEC 17000 Standard [START_REF]Conformity assessment -Vocabulary and general principles[END_REF] defines accreditation as an "Attestation issued by a third party related to a conformity assessment body conveying formal recognition of its competence to carry out specific conformity assessment tasks". ISO/IEC 1702 specifies and defines the general terms relating to conformity assessment, including the accreditation of conformity assessment bodies, and the use of conformity assessment to facilitate trade. Recently, the accreditation for 3D measures of ISO specifications was launched in European countries [2]. This accreditation imposes to estimate the uncertainties of ISO 1101 geometrical specifications [START_REF]Geometrical product specifications (GPS) -Geometrical tolerancing -Tolerances of form, orientation, location and runout[END_REF], and this even in case of measurements carried out in industrial environments. In this work a simplified method, dedicated to the use in industrial environments, is therefore proposed to evaluate uncertainties of ISO 1101 geometrical specifications [START_REF] Ricci | A categorical model for uncertainty and cost management within the Geometrical Product Specification[END_REF][START_REF] Maihle | The statistical gauge in geometrical verification: Part I. Field of probability of the presence of matter[END_REF]. For that purpose a Delete d-Jack-knife method is implemented and adapted to the estimation of specification uncertainties. As example, the verification uncertainty of ISO specification will be presented. The advantages and limitations of the method will then be discussed.

Uncertainty propagation methods:

GUM:

Uncertainties are generally evaluated using classical GUM's method [START_REF] Bipm | Guide to the expression of the uncertainty in measurement[END_REF] which is based on specific laws of propagation. A first order Taylor series expansion is also used to propagate elementary uncertainties to the composed uncertainty of the measurand. This propagation method has nevertheless some limitations, principally, when the model of the measurand is non linear. In such case, indeed, the shape of the PDF is distorted and some bias is observed for the calculated mean value of the result.

Monte Carlo Simulation Method:

Recently, a supplement to the GUM (GUM S1) has shown how to overcome this problem by using the Monte Carlo simulation Method (MCM) to evaluate uncertainties. MCM is a computational algorithm that relies on repeated random sampling to obtain numerical results and derive statistical parameters (mean value, standard deviation) [START_REF] Wen | Adaptative Monte Carlo and GUM methods for evaluation of measurement uncertainty of cylindricity error[END_REF][START_REF] Linares | Uncertainty of reference frames characterized by real time optical measurements: Application to Computer Assisted Orthopaedic Surgery[END_REF]. MCM is a common tool in uncertainty evaluation of complex measurement processes. It is used because of the lack or the difficulty to express analytical solutions. The convergence rate of Monte Carlo methods is ( )

N 1 O
, where N is the number of simulated experiments. Instead of using pseudo-random generators, it can be accelerated by employing deterministic uniformly distributed sequences known as presenting lowdiscrepancy. Methods based on such sequences are named Quasi Monte Carlo. Asymptotically, Quasi Monte Carlo can provide a rate of convergence of about ( )

N 1 O
[9]. MCM needs however numerous repeated random sampling and thus often leads to large Tables.

Sobol's method:

In analytical propagation approach, the sensitivity coefficient may also be defined by Sobol's approach [START_REF] Allard | Sensitivity analysis in metrology: study and comparison on different indices for measurement uncertainty[END_REF]. This method [START_REF] Sobol | Sensitivity estimates for nonlinear mathematical models[END_REF] is a variance based global sensitivity analysis technique founded upon "Total Sensitivity Indices" that account for interaction effects of the variables. The Total Sensitivity Indices of an input is defined as the sum of all the sensitivity indices involving that input. This method includes both main effect of each input as well as the interactions with the other variables [START_REF] Saltelli | Making best use of model evaluations to compute sensitivity indices[END_REF]. Sobol's method can cope with both nonlinear and non-monotonic models, and provides a truly quantitative ranking of inputs and not just a relative qualitative measure. Effort has been done to reduce the computational complexity associated with the calculation of Sobol's indices. However, even with its most recent developments, Sobol's method remains computer time consuming.

Jack-knife, Bootstrap or delete d-Jack-knife methods:

To reduce, the computing time of MCM, the Jack-knife, Bootstrap or delete d-Jack-knife methods can be used to estimate the uncertainties of ISO standard specifications [START_REF] Farooqui | Uncertainty analysis of cylindricity measurements using bootstrap method[END_REF][START_REF] Efron | An Introduction to the Bootstrap[END_REF].

The jack-knife was thought up by Quenouille in 1949. Ten years after, Tukey has developed its use in statistics. This method requires less computational power than MCM. For a dataset x = (x 1 , x 2 , ..., x n ) of size n and an estimator θ ˆ, the Jack-knife derives estimators i θ ˆ on subsamples that leave out a given selected element x i . The subsample is defined by this equation.

( ) ) x , • • • , x , x , • • • , x , (x x n 1 i 1 - i 2 1 i + =
The size of each Jack-knife subsample x (i) is p=n-1 and the total number of datasets that can be built is n. No sampling method is needed to define the subsamples. To estimate an uncertainty, the standard error of the Jack-knife replications is needed. Its estimate is defined by [START_REF] Rapacchi | Une introduction au bootstrap[END_REF]:

( ) ∑ ∑ = • = • = - - = n 1 i (i) ) ( n 1 i ) ( (i) e θ n 1 θ θ θ n 1 n s ŵith ˆ2
Generally, Jack-knife's method gives fine results for smooth statistics and for sufficiently large n. Nevertheless, it does not give accurate estimations for nonsmooth statistic or nonlinear behavior.

The Bootstrap method was thought up after Jack-knife's method. B. Efron introduced it in 1979. For a dataset x = (x 1 , x 2 , ..., x n ) of size n and an estimator θ ˆ, the Bootstrap derives the estimator θ ˆ on a resample b of the same size n. Each resample is obtained by random sampling with replacement from the original dataset. The total number of resamples that can thus be built is n n . A lower number B of datasets is however used in practice to estimate uncertainties. It is usually fixed to B=200 for standard error estimation and B=500 for error bar estimation. The standard error of the estimator θ ˆ can be derived from the Bootstrap replications using the equation [START_REF] Farooqui | Uncertainty analysis of cylindricity measurements using bootstrap method[END_REF][START_REF] Rapacchi | Une introduction au bootstrap[END_REF]:

The delete d-Jack-knife method consists in generating subsamples, simply by randomly removing a number d of elements from the initial dataset. The size of each subsample is thus n-d. The total number of subsamples that can be built is the number of combinations of d elements removed from the original dataset of size n. As compared to the earlier Jack-knife scheme the delete d-Jack-knife sub-sampling technique leads thus to a greater number of sub-datasets. This can improve the accuracy of the method in the case of non-smooth statistics [START_REF] Shao | A general-theory for jackknife varianceestimation[END_REF]. The standard error of the estimator θ ˆ can be evaluated through this equation [START_REF] Rapacchi | Une introduction au bootstrap[END_REF]:

( ) ∑ ∑ = • = • = - = B 1 b (b) ) ( B 1 b ) ( (b) e θ B 1 θ with θ θ 1 - B 1 s 2 ( ) ∑ ∑         = •         = •         = -         = d n 1 i (i) ) ( d n 1 i ) ( (i) e θ d n 1 θ with θ θ d n d. d - n s 2
To obtain an accurate estimate of the standard error, the number d of deleted data elements has to be selected in the range:

1 n d n - ≤ ≤
. An overview of other potential methods that can be used to estimate the uncertainties of geometrical specification has been presented in this section. A modified delete d-jack-knife method was finally chosen in our study to evaluate the measurement uncertainty of an ISO 1101 specification. The results of this work will be developed in the next section.

Estimation of the verification uncertainty of a geometrical

specification using a modified Jack-knife method:

Geometrical specification checking:

Figure 1 shows an example of parallelism constraint as specified with ISO standard. The tolerance zone which defines the limits of the checked surface is bounded by two planes parallel to the datum plane A. In the example of figure 1 which deals with the parallelism between the specified surface and the datum plane A, the geometrical defect to be evaluated and checked is defined by the distance between the two planes that bound the measured points M j , while being parallel to the datum feature A characterized by the digitized coordinates M i . In a given reference frame (O, X, Y, Z) these requirements are expressed by the minimisation conditions: This equation needs two optimisation steps. The initial optimisation that corresponds to the first minimization condition permits to determine the normal vector A n r of the datum plane A. The final step which is expressed by the second minimization condition defines the parallelism defect between the specified surface and the datum feature A. The cosines of the normal vectors of the specified surface and the datum surface are imposed equal. In consequence and after best fit, the value of minimax criterion of distances between the measured points and the specified surface describes the value of parallelism defect. These calculations allow thus to evaluate the parallelism defect of the checked surface. Next section will now focus on the presentation of the method used to estimate the uncertainty of this value.

( ) ( ) [ ] ( ) ( ) [ ]            = = = - - n .

Définition ISO 1101

Tolerance zone is oriented by the normal vector of datum reference A Tolerance zone is free in translation

Modified Jack-knife method:

The orientation of the datum surface A is, greatly, influenced by the outlier measured points. This fact can lead to a non smooth statistic of the searched parallelism defect. As stated in section 2.4, the Delete d-Jack-knife permits to accurately estimate standard errors even in the case of non-smooth statistics [START_REF] Shao | A general-theory for jackknife varianceestimation[END_REF]. This method was therefore chosen to estimate the verification uncertainty of the parallelism defect.

In the classical Delete d-Jack-knife method, the number of deleted points is usually fixed to a given value d that remains the same for all subsamples. In the proposed method, on the contrary, this number d was selected randomly. In order to contain sufficient statistical information, both the datum plane and the specified surface were characterized by datasets of at least 25 acquisition points. For each sub-sampling, the modified Delete d-Jack-knife consisted then in a random generation of two subsets of the initial data: one constructed with the coordinates that define the datum plane and one created with the points acquired to characterize the specified feature.

Select point M i or M j and Calculate

Associate at each point a random floating number: p i or j Initial set of measured points (size n, d = 0)

j or i M j or i M j or i M Z Y X , ,

Random generator

p i or j =p i=i+1 or j=j+1 d=d+1 j or i M * j or i M * j or i M * Z Y X , , n-d = 4 Generated Sub-Sample (size n-d) j or i M * j or i M * j or i M * Z Y X
, ,

Random generator

Figure 3. Sample and uploading acquisition uncertainty

The smallest number of points M i or M j required to build these two subsamples was fixed to 4 that is one more than the minimal number needed to define a plane (3 points). A specific selection procedure was implemented to generate the two sub-datasets. For every sub-sampling sequence, it consisted in randomly associating a floating number to each element of the initial datasets, that was built in the range [0,1]. A cut-off threshold p was then fixed to only select the points with a linked value lower than this limit. A random perturbation was finally added to each coordinate to account for the calibration uncertainty of the Coordinate Measuring Machine (CMM). ISO 10360 standard [17] was used for this last operation. This standard permits to know the calibration error bar ∆ for a measured length L in the CMM volume. For a CMM, this value can be defined by this equation:

( ) b.L a ∆ + ± =
The measured length L was derived from the coordinates of the acquired points M i or M j . This equation was then applied to add random perturbations to the three initial coordinates which permits to account for the acquisition error ∆ of the CMM. These calculations assume a uniform probability density of the calibration errors in the range [-∆, ∆]:

[ ] similarly defined and (), with * Z * Y Rnd Z Y X 1 - 2. ∆. 1 . X X 2 j or i M 2 j or i M 2 j or i M M M * j or i j or i =             + + + = ε ε
In these relationships, Rnd() is the random generation of a uniformly distributed variable in the interval [0,1]. The whole procedure used to build each sub-sample is presented in figure 3. After optimisation based on different tests, the value of the cut-off threshold p was chosen to 0.4. This value guarantees to obtain sub-samples of sufficient number of points.

Error Bar of ISO specification:

The uncertainties of a given specification are defined by the standard error of the geometrical defect to be characterized. It is based on repeated random generation of subsamples of the datum and specified surfaces using the modified d-Jack-knife procedure. After estimation of the mean value of the geometrical defect to be checked, the initial set of points is replicated by the random d-Jackknife method already presented. At each replication step, the geometrical defect of the virtual surfaces associated to the generated datasets is then computed. This operation is repeated M times. The standard error of the set of values which are thus obtained if finally calculated. It represents the uncertainty of the estimated geometrical defect. The lower bound of the tolerance interval of orientation specifications is always equal to 0. A test was therefore implemented in the calculation of the error bars of the estimated geometrical defect to avoid negative values of the confidence interval starting point. If this check detects a negative indicator, a unilateral distribution of probability is considered to define the error bars. The lower bound of the confidence interval is then fixed to 0. A bilateral probability distribution is considered otherwise.

Conclusion:

Uncertainty calculation of ISO specifications is a complex task. In industrial context, the calculation time is a main constraint. The revised version of the GUM (GUM S1) proposes to use Monte Carlo simulations for the evaluation of uncertainties, but this method is much computer time consuming. To avoid this impediment, an alternative uncertainty calculation method was proposed. It is based on a modified delete d-jack-knife sub-sampling technique. The results obtained with this method for measured surfaces with a small form defect are in complete adequacy with ISO 1101 standard for parallelism specification. The orientation of datum surface was deduced tangent of the material using the minimax criterion and the error bar of ISO specification was deduced quickly using the modified Delete-d-jack-knife method.

Figure 1 .

 1 Figure 1. ISO Parallelism Specification.


Salim Boukebbab
email: boukebbab@umc.edu.dz

Julien Chaves-Jacob

Jean-Marc Linares
email: jean-marc.linares@univ-amu.fr

Noureddine Azzam

A NEW APPROACH FOR THE MATHEMATICAL ALIGNMENT MACHINE TOOL-PATHS ON A FIVE-AXIS MACHINE AND ITS EFFECT ON SURFACE ROUGHNESS

This paper proposes a procedure to adapt the geometry of the toolpath to remove a constant thickness on a five-axis machine. The aim of this work is to contribute to the automation of prosthesis machining, mainly, in the preparation of polishing surface. The proposed method can deform and adapt a toolpath to respect the geometry of the manufactured surface. This method is based on three steps: alignment, deformation and smoothing toolpath. In the alignment step, a mapping is carried out between the measured surface of prostheses and the nominal toolpath using the Iterative Closest Point (ICP) algorithm. The aligned toolpath is deformed in two steps. The first step is the projection of aligned points on the measured surface (defined by STL file). In the second step, these points are offset by a value (ap) to obtain the required geometry. During the deformation step a meshed surface is used, reducing the smoothness of the deformed toolpath. Experimental tests on industrial prostheses are conducted to validate the effectiveness of this method. During these tests the effects of the smoothing methods on the surface quality of machined parts are presented.

Introduction

The surface quality of surgical implants is one of the most important properties to be controlled in their design and manufacture. The polishing operation represents the final action in the production cycle to improve the quality of implants surfaces. Generally, knee prosthesis is constituted of three parts. Two metal parts are fixed respectively on the femur and one on the tibia. The third part is intercalated between the two metallic's and it is made up of a very strong plastic resistant called the polyethylene, which improves the knee slip [START_REF] Gacon | Les prothèses tricompartimentaires du genou de première intention[END_REF].

To reduce the removed bone volume the knee prostheses thickness is reduced. Thus, this small thickness is caused by deformations due to the foundry process [START_REF] Lison | Experimental research into the pathogenesis of cobalt/hard metal lung disease[END_REF]. The geometry has a small influence on the lifespan of the prosthesis, because the intercalated parts in polyethylene will be deformed to compensate geometry errors of the femoral part which is commonly made in cobalt-chromium alloy. On the other hand, the surface discontinuities and the surface quality (roughness and waviness) have a major influence on the lifespan of the prosthesis; this implies that we must have a very accuracy surface quality and to ensure the thickness of the prosthesis to avoid the prosthesis failure. When CNC machines are used to polish these functional surfaces, the polishing force is not controlled because usual CNC machines drive the position and not the applied force. This effect requires a geometrical adaptation of the machining toolpath at each rough work piece [START_REF] Azzam | Adaptation of machining toolpath to distorted geometries: application to remove a constant thickness on rough casting prosthesis[END_REF]. In manual polishing, the operator uses his eyes to adapt his toolpath.

In the proposed method, a three-dimensional measurement is needed to obtain the rough part geometry made by foundry process. An STL model is generated after this measurement process, it should be noted here that the STL format is obtained by a triangulation of real work piece after acquisition step. The initial tool trajectory is calculated by a CAM (Computer Aided Manufacturing). It is defined on the nominal model given by CAD (Computer-aided design) software, with the respect of toolpath synchronization (figure 1). It makes it possible to avoid the traces on manufactured surface and thus avoid the build of CAD model of each deformed part and to remake a special CNC program [START_REF] Hu Gong | Improved positioning of cylindrical cutter for flank milling ruled surfaces[END_REF][START_REF] Chaves-Jacob | Improving tool wear and surface covering in polishing via toolpath optimization[END_REF]. The main objective of this research work is to modify a trajectory of machining calculated on a nominal model to remove a constant thickness over a rough surface of part coming from the foundry. In this paper, the case of femoral component of knee prostheses (femoral implant: condyles) is studied. The CNC toolpaths are made only on the upper part of the knee condyle.

Description of the developed procedure

This study proposes a method to adapt the geometry of the toolpath with the aim to remove a constant thickness. As presented in introduction, this case is present in the machining process of the femoral component of knee prostheses. The figure 2 illustrates the stages of this method. The proposed toolpath deformation method is composed of three stages: the measured surface alignment, toolpath deformation and toolpath smoothing. Each of these three items is studied in relation to the bibliography.

The alignment process using ICP algorithm

The alignment process using the ICP algorithm begins by the measurement of rough surface which must be aligned with the nominal toolpath. The ICP algorithm is a well-known method for registering a 3D set of points to a 3D model [START_REF] Rusinkiewicz | Efficient Variants of the ICP algorithm[END_REF]. It will be noted that the successive coordinates of the drive point expressed in the coordinate system of the workpiece give the nominal toolpath. Some CAM software options allow expression of the toolpath of the cutter contact point [START_REF] Azzam | Adaptation of machining toolpath to distorted geometries: application to remove a constant thickness on rough casting prosthesis[END_REF]. Subsequently, these coordinates are noted PCC(xi,yi,zi) and the tool axis direction, u. On the other hand, an STL file defines the measured surface [START_REF] Boukebbab | Applied Iterative Closest Point algorithm to automated inspection of gear box tooth[END_REF]. It is composed of vertices, edges, and triangular facets. Each facet has a normal vector, n. It should be noted here that P'CC(xi,yi,zi) is the vertical projection of PCC(xi,yi,zi) on a triangular facet. A rigid transformation [Tt] consists in the rotation matrix [R] and the translation vector {T} giving the iterative transformation Eq. 1.

P'CC(xi,yi,zi) = [R]× PCC(xi,yi,zi) + {T} (1)
The transformation is calculated in the aim to displace the nominal toolpath on the measured surface. The algorithm minimizes the sum of squared residual errors between the set of points and the model, and finds a registration that is locally the best fit using the least-squares method Eq. 2.

      1 ) , ( 2 1 '      s i i N i CC t CC s P T P N T R f (2)

Deformed toolpath and offset step

After alignment phase, the toolpath is deformed in two steps (figure 3). In the first one the projection of the aligned points on the measured surface (STL model) is realised. In the second step, an offset of these points by a value (ap) is necessary to obtain the required geometry. These steps are detailed below.

Projection aligned points

Firstly, all the points of the trajectory P'CC(xi,yi,zi) are projected on all facets of the STL model. A test is carried out to verify if the projection is inside the triangle or not. The distance between P'CC(xi,yi,zi) and a triangular element of STL model (figure 3) is determinate using the Eq. 3. The triangle vertices are denoted N1, N2 and N3. Eq. 4 is used to calculate the point PCC_def(xi,yi,zi).

Ei = PCCiN1 . n (3) ) OPCC_def(xi,yi,zi) = OP'CC(xi,yi,zi) + Ei . n ( 4
)
Where n is the unit vector of the triangular element and Ei is the distance between P'CC(xi,yi,zi) and PCC_def(xi,yi,zi).

Offsetting the toolpath after projection

The projected toolpath is offset with a quantity ap: depth of cut inside material (figure 3). The equation Eq. 5 is used to carry out to determinate the points PCCi_def_dec(xi,yi,zi).

OPCCi_def_dec (xi,yi,zi) = OP'CC(xi,yi,zi) + (Eiap). n (5)

It will be noted that, on a meshed surface (plane element); the local normal is submitted at discontinuous variations along a toolpath. This last will induce discontinuities on the deformed toolpath [START_REF] Azzam | Adaptation of machining toolpath to distorted geometries: application to remove a constant thickness on rough casting prosthesis[END_REF]. This deformation induces oscillations, principally, in the axis of the machine and this is observed in the manufacturing surface, because the initial trajectory is far from the target surface (figure 4). To resolve this impediment, section 5 proposes a method to smooth the toolpath within a pre-assigned tolerance. The generation of toolpath starting from model STL generates disturbances of deformed trajectory then decelerations of the machine and defects on the part. These phenomena are harmful with respect to production and the surface quality.

Toolpath smoothing is carried out to improve surface quality after the deformation step. A technique of smoothing methods is developed in literature. Some authors propose the B-Spline curve interpolation to smooth the nominal toolpath points [START_REF] Can | Five-axis tool path generation for 3D curves created by projection on B-spline surfaces[END_REF][START_REF] Pechard | Geometrical deviations versus smoothness in 5-axes high-speed flank milling[END_REF].

Smoothing toolpath and experimental validations

The proposed smoothing method is based on smoothing axis by axis with a 3dimensional admissible tolerance IT. This method may be applied to the 3 axes of the toolpath or only to one. On each axis a low degree polynomial (<6) is calculated using the least squares method. In addition with that, we propose to use the Bezier curves to smooth the toolpaths with an aim to have a better surface quality.

Tests are carried out on a femoral prosthesis. This prosthesis is a unicompartmental knee component. Shape complexity of these surfaces requires machining by a multi-axis CNC machine, in this case five-axis "ULTRASONIC 20 linear". A Siemens 840D CNC was used to carry out the tests. The measurement of manufacturing time gives us an idea of the effectiveness of the smoothing technique and makes it possible to select the most smooth toolpath trajectory as shown in the figure 5. It shows clearly that the proposed technique of smoothing by Bezier curves offers a better fluidity. From the machining experiments and the results of roughness measurements, we can conclude that the best strategy is the smoothing according to the three machine axes X, Y, Z.

Conclusion

In this paper a method to adapt a toolpath to a geometrical target to remove a constant thickness on a rough surface was proposed. This case is generally present in the production of knee prostheses. An STL model is generated after the measurement process. The toolpath deformation method starts with the measured surface and the nominal toolpath. After this, a deformation toolpath method is proposed to remove a constant thickness on rough surface. However, the use of a meshed model to deform the toolpath induces systematic effect (apparition of pattern marks) on the manufactured surface. To resolve this problem, a toolpath smoothing methods was developed. To validate the usefulness of the presented method and its effects on the machined surface quality, industrial tests were carried out and analyses, leading to an optimal method based.

Figure 1 :

 1 Figure 1: Tool-path generate using CAD model of the knee prosthesis (femoral condyle).

Figure 2 :

 2 Figure 2: The stage of the method The deformation of the toolpath is performed in three steps: a) Aligning the tool path (computed on the nominal model) and the STL model of the rough surface using the ICP algorithm, b) Deformation of the tool path, c) Smoothing of the deformed toolpath.

Figure 3 :

 3 Figure 3: Deformation of the nominal toolpath

Figure 4 :

 4 Figure 4: Discontinuities observed on the deformed tool path.

Figure 5 :

 5 Figure 5: Experimental testing and validation.The machined surfaces are measured with an optical coordinate measuring machine. Figure6presents the obtained results. This figure illustrates the roughness surface to the machined surface and compares the total depth of surface in micron [m].

Figure 6 :

 6 Figure 6: The measurement roughness surface results.


Camilla Schwind
email: schwind@lif.univ-mrs.fr

A first-order Temporal Logic for Actions

published or not. The documents may come

A first-order Temporal Logic for Actions

Camilla

Introduction

Most action theories consider actions being specified by their preconditions and their results. The temporal structure of an action system is then defined by the sequence of actions that occur. A world is conceived as a graph of situations where every link from one node to the next node is considered as an action transition. This yields also a temporal structure of the action space, namely sequences of actions can be considered defining sequences of world states. The action occurs instantantly at one moment and its results are true at the "next" moment.

However, the temporal structure of actions can be much more complex and complicated.

• Actions may have a duration.

• The results may be true before the action is completed or after it is finished.

• Actions may have preconditions which have to have been true during some interval preceding the action occurrence.

In order to represent complex temporal structures, underlying actions' occurrences, we have developed an action logic which allows to handle both states and time simultanuously.

We want to be able to express, for instance that action a occurs at moment t if conditions p 1 , . . . p n have been true during the intervals i 1 , . . . all preceding t.

Here we present an approach where it is possible to represent actions in a complex temporal environment. In reality, actions have sometimes a beginning time, a duration, preconditions which may also have temporal aspects ; and the results may be true only instances after the end of the action performance. For an example, consider the action of calling an elevator, taking place at instance t 1 . Depending on the actual situation this action may cause the elevator to move only many instances later, to stop still later, an so on. The action of pressing the button of a traffic light, in order to get green light to traverse the street may result in a switch immediately or after some seconds and in another switch after some more minutes.

In order to represent such issues, we define a modal action logic, where the modalities are terms containing variables which can be quantified. The same variables can occur inside the modalities as well as in the formulas after the modalities, allowing for unification between action term components and logical terms. This language makes it possible to express reasoning on states and the action terms allow to express temporal aspects of the actions.

The first-order modal action logic Dal

The language of first-order action logic, L is an extension of the language of classical predicate logic, L 0 . L 0 consists of a set of variables x, y, x 1 , y 1 , . . ., a set F F of function symbols F , where |F | ∈ ω is the arity of F , a set P P of predicate symbols P , including ⊤ and ⊥, where |P | ∈ ω is the arity of P , an equality symbol =, the logical symbols ¬, ∧ ,∀. Terms and formulas are defined as usual and so are ∃ and ∨. We denote by V t the set of all terms of L 0 . If φ is a formula and x a variable then we say that x is bounded in φ, when it occurs in a subformula ∀xφ. x occurs free in φ if it occurs in φ and is not bounded in φ.

Action terms

The language for action operators consists of • a set A A of action symbols a 1 , a 2 , . . . where |a| ∈ ω is the arity of a and such that A A ∩ P P = ∅ Action terms are built from action symbols and terms of L 0 .

• if a is an action symbol of arity n and t 1 , .

Action formulas

• If φ is a first-order formula and [A] is an action operator, then [A]φ is an action formula.

• If φ is a first-order formula and 2 is the modal operator, then 2φ is an action formula.

• If φ is an action formula and x is a variable, then ∀xφ is an action formula.

Instantiation If φ is a formula and t is a term, then φ x t is the formula obtained from φ by replacing every free occurrence of x by t. If t is the name of an element of a set O then

φ x t is called O-instance of φ. Example: [a(x, c)](¬φ(c, x) ∨ ψ(x)) x c1 = [a(c 1 , c)](¬φ(c, c 1 ) ∨ ψ(c 1 )) [a 1 ; a 2 ; a 3 (c, y)]P (c, y) y c3 = [a 1 ; a 2 ; a 3 (c, c 3 )]P (c, c 3 )
A formula is called grounded if there is no variable occurring free in it.

Semantical Characterization of Dal

A Dal structure is defined as a Kripke-type structure, such that the transition relation between worlds depends on grounded action terms.

A Dal structure is a tuple M = (W, {S w : w ∈ W}, A, R, τ ), where

• W is a set of worlds

• for every w ∈ W, S w = (O, F w , P w ) is a classical structure, where O is the set of individual objects (the same set in all worlds), F w is a set of functions over O and P w is a set of predicates over O.

• A is a set of action functions,

for f ∈ A, f : W × O × . . . × O n -→ 2 W , n ∈ ω.
Action functions will characterize the action operators (every action symbol of arity n in A A will be associeted with an action function of arity n + 1).

• R ⊆ W × W is a binary accessability relation on W, which will characterize the modal operater 2. We will write R(w) = {w ′ : (w, w ′ ) ∈ R}.

• τ is a valuation, τ = (τ 0 , τ 1 , τ 2 , τ 3 ), where τ 0 is a function assigning objects from O to terms. In order to speak about objects from O, we introduce into the language, for every o ∈ O, an o-place function symbol (denoted equally o, for simplicity).

τ 1 is a function assigning, for every world w ∈ W, functions (from F ) to function symbols (from F F ), of the same arity, τ 0 , τ 1 , τ 2 and τ 3 define the valuation τ as follows:

τ 1 : W × F F -→ F such that |τ 1 (w, F )| = |F |. τ 2 is
• If F (t 1 , t 2 , . . . , t m ) is a term then τ 0 (w, F (t 1 , t 2 , . . . , t m )) = τ 1 (w, F )(τ 0 (w, t 1 ), τ 0 (w, t 2 ), . . . , τ 0 (w, t m )).
• if P is an n-ary predicate symbol and t 1 , t 2 , . . . , t n are free object variables then

τ (w, P t 1 , t 2 , . . . , t n ) = ⊤ iff (τ 0 (t 1 ), . . . τ 0 (t n )) ∈ τ 2 (w, P ) • τ (w, t 1 = t 2 ) = ⊤ iff τ (w, t 1 ) = τ (w, t 2 ) • τ (w, ¬φ) = ⊤ iff τ (w, φ) = ⊥ • τ (w, φ ∧ ψ) = ⊤ iff τ (w, φ) = τ (w, ψ) = ⊤ • τ (w, ∀xφ) = ⊤ iff for every o ∈ O τ (w, φ x o ) = ⊤ • τ (w, [a(t 1 , t 2 , . . . , t n )]φ) = ⊤ iff for every w ′ ∈ τ 3 (a)(w, τ 0 (t 1 ), . . . , τ 0 (t n )), τ (w ′ , φ) = ⊤ • τ (w, 2φ) = ⊤ iff for every w ′ ∈ R(w), τ (w ′ , φ) = ⊤
Let φ be a formula and x 1 , x 2 , . . . , x n be the free object variables occurring in φ. Then τ (s, φ) = t iff for every tuple t 1 , t 2 , . . . , t n of ground terms,

τ (w, φ x 1 , x 2 , . . . , x n t 1 , t 2 , . . . , t n ) = t A formula φ is called valid in state w ∈ W of a Dal -structure M iff τ (w, φ) = ⊤. This is denoted by M, w |= φ.
We also say then that φ is satisfiable. A formula φ is called valid in a Dal -structure M with the set of states W, iff φ is valid in every w ∈ W. We denote that by M |= φ. A formula φ is called Dal -valid iff φ is valid in every Dal -structure. This is denoted by |= Dal φ. We suppress the index Dal , whenever it is clear from the context, in which system we are.

Remark 1 [a]⊥ is satisfiable and we have

τ (w, [a]⊥) = ⊤ iff τ 3 (a)(w, τ 0 (t 1 ), . . . , τ 0 (t n )) = ∅

Axioms and inference rules of Dal

In addition to the axioms and inference rules of classical first -order logic and those of the system K, which rule the action operators including [ε], and those of the system and S 4 , which rule the operator 2, we have the following axioms and inference rules, (where [A], [A 1 ] and [A 2 ] are arbitrary action operators):

[A1] [A 1 ; A 2 ]α ↔ [A 1 ][A 2 ]α [A2] 2α → [A]α [A3] [ε]α → α [A4] ∀xα → α x c for any individual term c of L [A5] ∀x[X]α ↔ [X]∀xα for any modal operator X, with no occurrence of x [R1] From α infer 2α [R2] From α → β infer α → ∀xβ provided x has no free occurrence in α
⊢ Dal is defined as usual, such that ⊢ Dal φ for any instance φ of one of the axioms; and ⊢ Dal ψ, whenever ψ can be inferred from φ, for any φ, such that ⊢ Dal φ by use of one of the inference rules. Again, we suppress the index Dal , whenever it is clear from the context, in which system we are.

Soundness, Completeness, Decidability

The Dal -logic is sound and complete:

Theorem 1 ⊢ Dal φ if and only if φ is Dal -valid (|= Dal φ)
The soundness proof is easy and the completeness proof goes along the lines of completeness proofs for modal logics by construction of a canonical model. The proof, which can be found in the appendix, bears several modifications according to the specific language which allows to quantify over terms occurring within modal operators.

Dal is a first order language and therefore undecidable in the general case. But for action logics, we will make use of decidable subsets of Dal .

Dal is very close to term modal logic introduced by [START_REF] Fitting | Term-modal logics[END_REF]. Term modal logic allows terms in general as modalities, whereas our action logic only admits action terms. Moreover Dal contains the S4 modal operator 2 which is not part of term modal logic.

Temporal Action Theories

Using Dal , we can modelize temporal aspects of dynamic actions. The modal logic allows to define action operators as modalities [START_REF] Giordano | Reasoning about actions in dynamic linear time temporal logic[END_REF][START_REF] Schwind | A logic based framework for action theories[END_REF]. The first order logic is used to formulate actions at a more general level. Here, we show an example where in addition to the relative representation of time by the modal operators, it is possible to express time points by terms.

We presuppose a time axis, linearly ordered (dense or continuous or discrete). Given a Dal -structure, we will define a transitive relation on the set of states, W, which will be related to the order on T .

Definition 1 Let M = (W, {S w : w ∈ W}, A, R, (τ 0 , τ 1 , τ 2 , τ 3 )) , be a Dal -model. Then w ≺ 0 w ′ iff ∃a ∈ A of arity n and there are terms t 1 , . . . , t n , such that w ′ ∈ f (w, t 1 , . . . , t n ). Let be the reflexive and transitive closure of ≺ 0 .

Intuitively, this means that w ≺ w ′ if we can possibly "reach" w ′ from w by performing actions a 1 , a 2 , . . . , a n . Obviously, is transitive and reflexive. Since we want to "link" worlds of W to time points in T , which is ordered, ≺ must also be antisymmetric. The temporal entrenchment of the states is defined by a homomorphism time : W -→ T from W into T , where w w ′ implies time(w) ≤ time(w ′ ). Using this construction, actions operators can be defined admitting complex temporal structures, including beginning and ending instances and a duration, which can be 0, when the result is immediate, or ∆ ∈ T . The preconditions and results of actions can be defined to occur at freely determinable time instances before or after the instance when the action occurs. When an action a occurs in the state w, time(w) gives us the time point at which a occurs. If the duration of the action is ∆, the time point of the resulting state w ′ is time(w ′ ) = time(w) + ∆.

In this particular framework, we define

• Action terms as binary action predicates a(t, d, -→ x ), where t denotes the instance on which a occurs and d denotes the duration of a, i.e. the interval on T after which the results of a will hold. , -→ x is the sequence of other variables denoting the other entities or objects involved in the action occurrence.

To give an example, let T = {1, . . . , 24} be discrete and finite, denoting the hours during one day. Then action move(t, 3, T GV, M arseille, P aris) is the action "train TGV goes from Marseille to Paris, the duration being 3 hours".

• Action axioms. An action axiom is characterized by a precondition π(t, -→ x ) and a result ρ(t + d, -→ x ), where π and ρ are Dal formulas describing all preconditions and results of action a.

To continue the previous example, the action execution axiom of the move-action is at(t, x, y) → [move(t, d, x, y, z)]at(t + d, x, z) (and can be instantiated to at(6, T GV, M arseille) → [move(6, 3, T GV, M arseille, P aris)]at(9, T GV, P aris)), which means: if x is at y at instance t, then, after moving from y to z, x is at z at instance t + d.

The general form of an action law is

π(t 1 , -→ x 1 ) → [a(t, d, -→ x 2 )]ρ(t 2 , -→ x 3 ), where -→ x 1 ∪ -→ x 2 ⊆ -→ x 3

Example

The following example is due to Lewis [START_REF] Lewis | Causation as influence[END_REF] and has been discussed by Halpern and Pearl in [START_REF] Halpern | Causes and explanations: A structural model approach, part i[END_REF] in the framework of a theory of causation. Interestingly, this example defines actions with a complex temporal structure.

Billy and Suzanne throw rocks at a bottle. Suzanne throws first and her rock arrives first. The bottle shatters. When Billy's rock gets to where the bottle used to be, there is nothing there but flying shards of glass. Without Suzanne's throw, the impact of Billy's rock on the intact bottle would have been one of the final steps in the causal chain from Billy's throw to the shattering of the bottle. But, thanks to Suzanne's preempting throw, that impact never happens.

In our formulation, we focalize on the temporal structure of the throw action. We consider that the action occurs along a continuous (or dense) time axis, [0, ∞[. We define one action term for "throw", T , and two predicates H for "hits" and BB for "the bottle is broken". The action term T (t, d, p) means that "person p throws a stone to a bottle at instance t and the result of the action (the stone hits its target) occurs at instance t + d". The formula H(t, p) means that "the stone thrown by person p hits the bottle at instance t and formula BB(t) means that the bottle is broken at instance t. The intended result of the action is to hit the bottle, but this result can only be achieved if the bottle is still at the intended place and nothing else has been happened to it, namely if it is not broken in the meantime. In this example it is not enough to have the precondition that the bottle is there and not broken at the instance of throwing, but it must be non-broken at the moment when the action is to be completed, just before it is to be hit. Therefore the action law for "throw" has a precondition which must hold after the instance when the action occurs.

Example 1 The following set of laws represents the framework of this story:

(1)

¬BB(t + d) → [T (t, d, p)]H(t + d, p) (2) 2(H(t, p) → BB(t + d 1 )) (3) 2(BB(t) → ∀t ′ (t < t ′ → BB(t ′ ))) (4) ¬BB(0)
(1) is the action law for successful execution of the throw action, (2) describes the impact of hitting the bottle (d 1 is infinitesimally small) and the general law (3) says that a broken bottle remains broken "forever" 1 .

Several scenarios can happen within this framework. Here we discuss the scenario where Suzanne throws at instance 0 and Billy throws some instance later 2 .

(5) < T (0, d s , suzy) > ⊤ (6) < T (t 1 , d b , billy) > ⊤ 1 In this example we focus on the temporal relations between the different instances of throwing (by Suzanne and by Billy), so we neglected other preconditions, as for example having a stone, heavy enough, but not too heavy, having members enabling the person to throw, seeing the object to aim, etc. The throw action defined here is highly abstracted for the purpose of our temporal action theory. 2 In order to express that action aoccurs, we write [a]⊤, which simply means that action a occurs (even when nothing can be said about its results). It is always possible to throw a stone at a bottle, even if the intended result of hitting cannot be achieved.

We need these "empty results", because Three cases can then be distinguished:

1. The moment when the bottle can be hit (and broken) after Suzanne's throw (d s + d 1 ) occurs before Billy's stone could possibly hit the bottle t 1 + d b .

( 3) and ( 7) (9) ¬BB(d s ) by persistency from (4) 3 [START_REF] Schütte | Vollständige Systeme modaler und intuitionistischer Logik[END_REF] [T (0, d s , suzy)]H(d s , suzy) from ( 1) and ( 9) 2), ( 10), K for the action modality and (A2) 11), ( 8), K and (A2)

) d s + d 1 < t 1 + d b (8) 2(BB(d s + d 1 ) → BB(t 1 + d b )) from ( 7
(11) [T (0, d s , suzy)]BB(d s + d 1 ) from (
(12) [T (0, d s , suzy)]BB(t 1 + d b ) from (
In this scenario, the law

¬BB(t 1 + d b ) → [T (t 1 , d b , billy)]H(t 1 + d b , billy) cannot be used to derive T (t 1 , d b , billy)]H(t 1 + d b , billy) because BB(t 1 + d b )
holds after Suzanne's throw [START_REF] Terenziani | Temporal reasoning with classes and instances of events[END_REF]. Billy's stone cannot hit the bottle, because it is already broken when his stone could hit it and we have just [T (t 1 , d b , billy)]⊤ (( 6), Billy has thrown).

2. Billy's stone hits the bottle, which breaks, before Suzanne's stone could possibly hit the bottle. 3) and ( 13 3. Suzanne's and Billy's stone hit the bottle precisely at the same moment.

(13) t 1 + d b + d 1 < d s (14) 2(BB(t 1 + d b + d 1 ) → BB(d s )) from (
(

) t 1 + d b = d s (20) ¬BB(t 1 + d b ) ∧ ¬BB(d s ) by persistency from (4), see (9) (21) [T (0, d s , suzy)]H(d s , suzy) like (10) (22) [T (t 1 , d b , billy)]H(t 1 + d b , billy) as (16) (23) [T (0, d s , suzy)]BB(d s + d 1 ) from (21) (24) [T (t 1 , d b , billy)]BB(t 1 + d s b + d 1 ) from (22)) 19
In this case, both stones hit the bottle which breaks as a result of Suzanne's throw and Billy's throw.

Conclusion and Related Work

Modal logic approaches to action theories define a space of states but cannot handle time, neither explicitly not implicitly [START_REF] Giordano | Ramification and causality in a modal action logic[END_REF][START_REF] Herzig | Formalizing action and change in modal logic i: the frame problem[END_REF]. In situation calculus [START_REF] Reiter | Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems[END_REF][START_REF] Mccarthy | Actions and other events in situation calculus[END_REF] reasoning about time was not foreseen, properties change discretely and actions do not have durations.

Remember that in situation calculus, there is a starting state, s 0 and for any action a and state s, do(a, s) is a resulting state of s. One can consider that the set of states is given by {s : ∃a 1 . . . a n s = do(a n , do(a n-1 , . . . do(a 1 , s 0 )))}. Hence the temporal structure of situation calculus is discrete and branching and does not allow for actions of different duration neither for preconditions or results which become true during the action execution or later after the action is ended. Javier Pinto has extended situation calculus in order to integrate time [START_REF] Pinto | Occurrences and narratives as constraints in the branching structure of the situation calculus[END_REF]. He conserves the framework of situation calculus and introduces a notion of time. Intuitively, every situation s has a starting time and an ending time, where end(s, a) = start(do(a, s)) meaning that situation s ends when the succeeding situation do(a, s) is reached. The end of the situation s is the same time point as the beginning of the next situation resulting from the occurrence of action a in s. The obvious asymmetry of the start and end functions is due to the fact that the situation space has the form of a tree whose root is the beginning state s 0 . Thus, every state has a unique preceding state but eventually more that one succeeding state.

Paolo Tereziani proposes in [START_REF] Terenziani | Temporal reasoning with classes and instances of events[END_REF] a system that can handle temporal constraints between events and temporal constraints between instances of events.

In this present article, we have introduced a new modal logic formalism which can handle simultaneously states and time. We did not address here the problem of the persistency of facts over time (or over the execution of actions), because we wanted to focus on the modal temporal formalism. We have adopted a solution similar to the one presented in [START_REF] Schwind | A logic based framework for action theories[END_REF], i.e. "weak" frame laws are nonmonotonically added to the theory. But this solution is a bit more complicated in the case of our first-order action logic presented in this paper, because we need to restrict ourselves to a decidable subset of Dal .

Concerning the implementation, we use a labelled analytic tableaux approach including an abductive mechanism for the weak persistency laws, which will be described in more detail in a following paper.

We will apply this formalism to planning problems where a hybrid approach (states and time) can be very powerful. The idea is to infer temporal constraints from a Dal specification in order to create a plan for a problem Let s be a set of formulas. Then we denote by V t (s) the set of all terms occurring in formulas of s. We denote by P (s) the set of all Dal -formulas containing only nonlogical symbols (terms, action terms and predicate symbols) of formulas of s.

→ ψ then ψ ∈ s 3. If 2φ ∈ s then [a]φ ∈ s 4. If φ ∨ ψ ∈ s then φ ∈ s or ψ ∈ s 5. If φ ∨ ψ ∈ P (s) and φ ∈ s or ψ ∈ s then φ ∨ ψ ∈ s 6. If c ∈ V t (s), then φ x c ∈ s if and only if ∃xφ ∈ s 7. t = t ∈ s for any term t ∈ V t (s) 8. If t = t ′ ∈ s then t ′ = t ∈ s 9. If t = t ′ ∈ s and t ′ = t ′′ ∈ s then t = t ′′ ∈ s
The last three items show that t = t ′ ∈ s defines an equivalence relation ∼ s over V t (s), where t ∼ s t ′ iff t = t ′ ∈ s. The equivalence class of t according to ∼ s is denoted by [t] s . Definition 4 Let s be a set of formulas and a ∈ A A t . Then we define

1. s a = {φ : [a]φ ∈ s} 2. s 2 = {φ : 2φ ∈ s} Lemma 3 1. s a is inconsistent iff [a]⊥ ∈ s 2. s 2 ⊆ s a Lemma 4
Let s be a complete set of formulas and φ a formula such that s a ∪ {φ} is consistent. Let s ′ = (s a ∪ {φ}) * the complete extension of s a ∪ {φ} (which exists by lemma 1). Then V t (s) = V t (s ′ ) Proof Since s is complete, it is saturated, hence for every existential formula ∃xφ ∈ s there is a formula φ x c ∈ s for some c ∈ V t (s). The crucial point concerns existential formulas in s a not in s. But for those formulas we have that 2∃xφ ∈ s and therefore ∃xφ ∈ s a , by T . Hence existential formulas in s a are also existential formulas in s. But this means that all terms in s' are terma in s.

Q.E.D.

Definition 5 A set S of sets of formulas is called complete if 1. Every element s of S is a complete set of formulas. 2. For all s ∈ S and φ ∈ P (s), if s a ∪ {φ} is consistent, then there is s ′ ∈ S such that s a ∪ {φ} ⊂ s ′ Remark 2 If [a]⊥ ∈ s, then, since s a is not consistent, it is and not contained in any s ′ ∈ S. Now we construct the canonical model starting from a complete set of formulas, s.

Lemma 5 For every complete set of formulas s, there is a Dal -structure M = (W, {S w : w ∈ W}, A, R, (τ 0 , τ 1 , τ 2 , τ 3 )) , such that s ∈ W.

Proof : For every φ ∈ P (s) and every a ∈ A A t such that s a ∪ {φ} is consistent, we extend s a ∪ {φ} to a complete set of formulas s ′ , which exists by lemma 1. So we form successively sets of formula sets S 0 , S 1 ,. . . as follows S 0 := {s} S i+1 := {X : X is a complete extension of Y a ∪ {φ} where Y ∈ S i and φ ∈ P (s) and Y a ∪ {φ} is consistent} W := {S i : i ∈ ω}.

Because of remark 4, V t (s) = V t (s ′ ) for s, s ′ ∈ W. We note V t (s) = V t , [t] s = [t] and ∼ s =∼.

For every w ∈ W, S w = (O, F w , P w ) is a classical structure where the object set O is defined as the set of ∼-equivalence classes over V t . The proof is straightforward, by induction over formulas using the lemmata 2 and 7.

Proof of the completeness theorem:

Proof Assume for the contrary that there is a Dal valid formula φ which is not deducible in Dal . Then {¬φ} is a consistent set of formulas, which can be extended to a complete set of formulae s, by Lemma 1, where ¬φ ∈ s. By Lemma 5, there is a Dal -structure M = (W, {S w : w ∈ W}, A, R, (τ 0 , τ 1 , τ 2 , τ 3 )) where W is a complete system of sets and s ∈ W . By Lemma 8, τ (s, ¬φ) = t and hence T (s, φ) = f , which contradicts the validity of φ. Q.E.D.

φ 1 ,Lemma 8

 18 φ 2 , . . . , φ k ∈ w a such that ⊢ φ 1 ∧ . . . ∧ φ k → φ from which ⊢ [a](φ 1 ∧ . . . ∧ φ k ) → [a]φ by rule 1 of the logic Dal and therefore ⊢ [a]φ 1 ∧ . . . ∧ [a]φ k → [a]φ. But [a]φ 1 , [a]φ 2 , . . . , [a]φ k ∈ w, and therefore [a]φ ∈ w, by the lemma 2. 2. Q.E.D.The next lemma concludes our proof. For every closed formula φ ∈ P (s), τ (w, φ) = t if and only if φ ∈ w

  (t 1 ), . . . , τ 0 (t n )) ⊆ R(w). If a world can be reached from w by the execution of action a(t 1 , t 2 , . . . , t n ) then it is accessible (via the relation R).

	a function assigning, for every world w ∈ W, predicates to predicate sym-
	bols of the same arities,
	τ 2 : W × P P -→ P, such that |τ 2 (w, P )| = |P |.
	τ 3 is a function assigning action functions to action symbols,
	τ 3 : A A -→ A, such that |τ 3 (a)| = |a| + 1
	• τ 3 (a)(w, τ 0

  Definition 3 A set of formulas s is called complete (or Dal -complete) if 1. s is consistent.2. s is maximal, i.e. for all φ in P (s) holds: if φ ∈ s then s ∪ {φ} is inconsistent.3. s is saturated, i.e. for every existential formula ∃xφ ∈ s where x is a variable, there is a formula φ x c ∈ s for some constant c ∈ V t (s). Every consistent set of formulas can be extended to a complete set of formulas.Proof Let s be a consistent set of formulas and let c 1 , c 2 , . . . be a sequence of 'new' object variables not in V t (s). We define P ⋆ (s) = P (s) ∪ {ψ : ψ is a formula with variables from c 1 , c 2 . . .}. Let {∃x i φ i (x i )} i=1,... be an enumeration of all existential formulas of P*(s). Then we form a new set of formulas s ∼ , by adding to s all formulas ∃x i φ i (x i ) → φ(a i ), i = 1, 2, . . . for every existential formula of P (s). It is easy to see that s ∼ is consistent. s ∼ is extended to a complete (maximal) set of formulas s ⋆ as follows: Let Θ = {s ′ : s ⊂ s ′ and s ′ consistent}. Let H be a chain in Θ, i.e. H ⊂ Θ and if s 1 , s 2 ∈ H then s 1 ⊂ s 2 or s 2 ⊂ s 1 . Then H is an upper bound of H in Θ, since s ⊂ H for all s ∈ H. It is easy to see that H is consistent. Therefore H ∈ Θ and, by Zorn's Lemma, Θ then has a maximal element, s ⋆ . It is easy to see that s ⋆ is complete.

	Lemma 1 Q.E.D.
	The following properties of complete sets are straightforward.

Lemma 2 Let s be a complete set of formulas. Then 1. φ ∈ s if and only if ¬φ ∈ s 2. If φ ∈ s and ψ ∈ P (s) and ⊢ Dal φ

A Appendix: Proofs of the theorems A.1 Soundness and Completeness

Soundness is easy and left tyo the reader. For completeness, in this part we will show that every Dal -valid formula is a theorem of Dal . Our proof is along the same lines as [START_REF] Schütte | Vollständige Systeme modaler und intuitionistischer Logik[END_REF]. Subsequently, formulas are always grounded.

• for every n-ary function symbol F ∈ F F and for every tuple of terms t 1 , .

We show that M is a Dal -structure. By the construction, W is a complete set of sets.

. Then w a(t 1 , t 2 , . . . , t m ) ⊆ w ′ by construction of the model. But then w 2 ⊆ w ′ by lemma 3, from which follows that w ′ ∈ R(w).

Truth value τ (w, φ) for formula φ and world w is defined by induction over the construction of formulas as usual.

In order to show that τ (s, φ) = t if and only if φ ∈ s, we need the following lemma:

Lemma 7 Let M = (W, {S w : w ∈ W}, A, R, (τ 0 , τ 1 , τ 2 , τ 3 )) be the Dal -structure constructed from a complete formula set w according to lemma 5 and w ∈ W . Then for every action symbol a of arity n, [a]φ ∈ w if and only if for every tuple of terms t 1 , t 2 , . . . , t n and w ′ ∈ W , if w ′ ∈ τ 3 (a)(w, t 1 , t 2 , . . . , t n , then φ ∈ w ′ . Proof If φ is ⊥ then this lemma trivially holds because then τ 3 (a)(w, t 1 , t 2 , . . . , t n is empty. Let φ be different from false. (⇒): if [a]φ ∈ w then φ ∈ w a and therefore for every w ′ ∈ a(w, t 1 , t 2 , . . . , t n ), φ ∈ w ′ by the definition of M . (⇐): Let be |a| = n. Consider w a . We first show that w a ∪ {¬φ} is inconsistent. Assume for the contrary, that w a ∪ {¬φ} is consistent. Since W is a complete set of formula sets, according to definition 5, there is w ′ ∈ W and w a ∪ {¬φ} ⊆ w ′ . From this follows w a ⊆ w ′ , hence w ′ ∈ a(w, t(|a| 1 , |a| 2 , . . . , |a| ) ), by the constuction of M in lemma 5. Since ¬φ ∈ w ′ and w ′ is complete, φ ∈ w ′ , which contradicts the hypothesis. Therefore, w a ∪ {¬φ} is inconsistent.

Therefore there exist formulas