overdose DILI Hepatocytes APAP NAPQI GSH depletion NAPQI adducts ROS

Questioning the RIPK1 kinase activity involvement in acetaminophen-induced hepatotoxicity in mouse.

Huma Hameed 1# , Muhammad Farooq 1,2# , Claire Piquet-Pellorce 1 , Annaïg Hamon 1 , Michel Samson 1 * ¶ and Jacques Le Seyec 1 * 1 Univ Rennes, Inserm, EHESP, IRSET (Institut de recherche en santé, environnement et travail) -UMR_S 1085, Rennes, France 2 Department of Clinical Sciences, College of Veterinary and Animal Sciences, Jhang, Pakistan # or * Authors with similar signs contributed equally. ¶Corresponding author: michel.samson@univ-rennes1.fr To the Editor:

In a recent previous issue, Yi and its collaborators tackled a research subject related to a worldwide public health problem, the hepatotoxicity of a widely used antipyretic and analgesic drug which is listed under the category of over-the-counter medicines: acetaminophen (paracetamol or N-acetyl-p-aminophenol; APAP) [START_REF] Yi | RIP1 kinase inactivation protects against acetaminophen-induced acute liver injury in mice, Free Radic[END_REF]. Based on complementary genetic and pharmaceutical experimental approaches, authors concluded that inactivation of the kinase activity of the receptor interacting protein kinase 1 (RIPK1) would be protective against liver injury induced by APAP in mouse. However, by performing similar experiments, we did not find any therapeutic interest in targeting the kinase activity of RIPK1, questioning the real implication of RIPK1 kinase activity in APAP hepatoxicity in mouse.

Thus, two different mouse lines, either deficient for the kinase activity of RIPK1 (Ripk1 K45A ) or for Ripk1 specifically in liver parenchymal cells (Ripk1 LPC-KO ) plus their respective WT littermates (Ripk1 wt/wt and Ripk1 fl/fl ) were challenged with toxic doses of APAP (Fig. 1A). To have appropriate littermates, the Ripk1 K45A mice were obtained from heterozygous breeding. The Ripk1 LPC-KO colony has a Ripk1 fl/fl background with half of the population carrying the Cre recombinase transgene under the control of the mouse albumin regulatory elements and α-fetoprotein enhancers (Alfp-Cre transgene). In accordance with other published data [START_REF] Iorga | Interaction of RIPK1 and A20 modulates MAPK signaling in murine acetaminophen toxicity[END_REF][START_REF] Schneider | Receptor Interacting Protein Kinase 1 (RIPK1) in Hepatocytes Does Not Mediate Murine Acetaminophen Toxicity[END_REF] genetic inactivation of its kinase activity (Ripk1 K45A ) or Ripk1 depletion specifically in liver parenchymal cells (Ripk1 LPC- KO ) never affected APAP-induced hepatotoxicity. These experiments were performed as studied in the literature at sub-lethal and lethal doses of APAP (300 and 600 mg/kg, respectively) [START_REF] Iorga | Interaction of RIPK1 and A20 modulates MAPK signaling in murine acetaminophen toxicity[END_REF][START_REF] Dara | Receptor interacting protein kinase 1 mediates murine acetaminophen toxicity independent of the necrosome and not through necroptosis[END_REF]. Liver damage remained similar between genetically modified mice and their respective littermate controls as shown by the measurement of serum transaminases (Fig. 1B) and of the necrotic liver tissue (Fig. 1C). Unlike the previous study in which Ripk1 K45A mice had a C57BL/6J genetic background, those used in our study were C57BL/6N mice. Data from the literature J o u r n a l P r e -p r o o f clearly underlined the influence of the genetic background on the susceptibility of mouse strains to APAP-induced hepatitis. As previously described [START_REF] Duan | Differential susceptibility to acetaminophen-induced liver injury in sub-strains of C57BL/6 mice: 6N versus 6[END_REF], symptoms were exacerbated in Ripk1 wt/wt (N background) compared to their congeners Ripk1 fl/fl mice (J background) (Fig. 1B andC). Besides the genetic background, and most importantly, other genetic or epigenetic variations existing between different colonies of mice can influence a phenotype [START_REF] Nguyen | How informative is the mouse for human gut microbiota research?[END_REF][START_REF] Holmdahl | The need for littermate controls[END_REF].

Appropriate littermate controls, also born in the same colony under similar breeding conditions, should be used whenever possible to minimize the risk of compromising experimental results. Otherwise, in addition to the kinase activity of RIPK1, its scaffolding properties did not appear to contribute to APAP-induced liver injury in our investigations. However, previous works reported that knockdown of Ripk1 through antisense oligonucleotide treatment and adult hepatocyte-specific Ripk1 conditional knockout (Ripk1 HepCKO ) partly reduced liver damage, conversely arguing for a potential harmful role of RIPK1 scaffolding properties in APAP-induced liver damage [START_REF] Iorga | Interaction of RIPK1 and A20 modulates MAPK signaling in murine acetaminophen toxicity[END_REF][START_REF] Dara | Receptor interacting protein kinase 1 mediates murine acetaminophen toxicity independent of the necrosome and not through necroptosis[END_REF]. Dara's team attempted to propose a hypothesis to explain these conflicting results. Knowing the importance of Ripk1 during mouse embryogenesis [START_REF] Kelliher | The death domain kinase RIP mediates the TNF-induced NF-κB signal[END_REF], interfering compensatory phenomena would be less likely to occur in knockout models induced later in development (Ripk1 HepCKO versus Ripk1 LPC-KO ) [START_REF] Iorga | Interaction of RIPK1 and A20 modulates MAPK signaling in murine acetaminophen toxicity[END_REF]. Note, nonetheless, that this Ripk1 LPC-KO mice exhibit an aggravated acute hepatitis phenotype when TNF or FasL are involved [START_REF] Farooq | Depletion of RIPK1 in hepatocytes exacerbates liver damage in fulminant viral hepatitis[END_REF][START_REF] Filliol | RIPK1 protects hepatocytes from death in Fas-induced hepatitis[END_REF][START_REF] Filliol | RIPK1 protects from TNF-αmediated liver damage during hepatitis[END_REF][START_REF] Filliol | RIPK1 protects hepatocytes from Kupffer cells-mediated TNF-induced apoptosis in mouse models of PAMP-induced hepatitis[END_REF].

In addition to the genetic approach, we also tested the impact of chemical inhibition of the RIPK1 kinase activity using a generation of more specific inhibitor with better in-vivo pharmacokinetic properties, Nec-1s. As mentioned by Yi and colleagues [START_REF] Yi | RIP1 kinase inactivation protects against acetaminophen-induced acute liver injury in mice, Free Radic[END_REF], DMSO is known to interfere with the metabolism of APAP on its own partly improving liver injury. Therefore, our investigations with Nec-1s included the essential control of the vehicle alone, which only included 6% of DMSO. The inhibitory activity of the batch of Nec-1s used in our investigations was also verified in parallel in an in vitro assay (data not shown). Thus, WT C57Bl6/J mice received vehicle alone or with Nec-1s prior to APAP injection. The severity of the hepatitis induced in the two groups of mice was similar, as evidenced by the evaluation of serum transaminase levels and of percentages of necrotic liver tissue (Fig. 1D andE). The inhibitory effect observed in Yi's works most probably resulted from the known off-target effect of Nec-1 which inhibits the indoleamine-2,3-dioxygenase (IDO) that restricts inflammation, a central process in APAPinduced hepatitis [START_REF] Vandenabeele | Necrostatin-1 blocks both RIPK1 and IDO: Consequences for the study of cell death in experimental disease models[END_REF].

Therefore, the mitochondrial permeability transition (MPT)-driven necrosis, the cell death pathway that has been established to occur in APAP-overdose [START_REF] Shojaie | Cell death in liver diseases: A review[END_REF], did not appear to be influenced by the kinase activity of RIPK1.

J o u r n a l P r e -p r o o f

LegendFigure 1 :

 1 Figure 1

Acknowledgment

We would like to thank Dr. M. Bertrand and Pr. P. Vandenabeele, both from the Inflammation Research Center, VIB (Belgium) for the provision of the Ripk1 LPC-KO mouse strain and the team of Peter J. Gough (GlaxoSmithKline, Collegeville, PA, USA) for provision of the Ripk1 K45A mouse strain. We also extend our thanks to Mélanie Simoes-Eugénio, Ghania H. Kara-Ali and Ghiles Imerzoukene for their technical assistance. We acknowledge the "Laboratoire de Biochimie-Toxicologie" from the "CHU de Rennes" for transaminase measurements. For histological analysis and animal house facilities, we would like to thank the dedicated platforms (i.e.H2P2 and animal house platforms) of SFR Biosit-UMS 3480, US_S 018, France.

J o u r n a l P r e -p r o o f


Yannick Aoustin

Gaëtan Garcia

Philippe Lemoine

Estimation of the Absolute Orientation of a Five-link Walking Robot with Passive Feet

Introduction

One of the main objectives of current research on walking robots is to make their gaits more fluid by introducing imbalance phases. For example, for walking robots without actuated ankles, which are under actuated in single support, dynamically stable walking gaits have been designed with success [START_REF] Aoustin | Control design for a biped: Reference trajectory based on driven angles as function of the undriven angle[END_REF][START_REF] Chevallereau | Rabbit: A testbed for advanced control theory[END_REF][START_REF] Zonfrilli | A biped locomotion strategy for the quadruped robot Sony ers-210[END_REF][START_REF] Aoustin | Numerical and experimental study of the virtual quadruped-SemiQuad[END_REF][START_REF] Pratt | Virtual model control: an intuitive approach for bipedal locomotion[END_REF][START_REF] Westervelt | Hybrid zero dynamics of planar biped walkers[END_REF]. Both the design of reference motions and trajectories and the control of the mechanism along these trajectories usually require the knowledge of the whole state of the robot. This state contains internal variables which are easy to measure using encoders for example, and also the absolute orientation of the robot with respect to the horizontal plane. For robots with unilateral constraints with the ground, it may not be possible to derive the latter information from internal measurements, as in the case of the absolute orientation of a biped in single support. Of course, technological solutions exist such as accelerometers, gyrometers, inertial units… But the implementation of these solutions is expensive and difficult. In order to overcome these difficulties, we propose to use a state observer which, based on the measurements of the joint variables and on a dynamic model of the robot, provides estimates of the absolute orientation of the walking robot during imbalance phases. This strategy was first validated in simulation for a three link biped without feet, using nonlinear high gain observers and a nonlinear observer based on sliding modes with a finite time convergence (Lebastard et al. 2006a) and (Lebastard et al. 2006b), for walking gaits composed of single support phases and impacts. The main drawback with this family of observers is that, when only some of the degrees of freedom are measured, a state coordinates transformation is necessary to design their canonical form [START_REF] Gauthier | Observability for any u(t) of a class of nonlinear system[END_REF][START_REF] Krener | Nonlinear observers with linearization error dynamics[END_REF][START_REF] Bornard | A high gain observer for a class of uniformly observable systems[END_REF][START_REF] Plestan | Linearisation by generalized input-ouput injection[END_REF].

In this chapter, the observer is an extended Kalman filter and it is applied to SemiQuad, a prototype walking robot built at our institute. SemiQuad is a five link mechanism with a platform and two double-link legs. It is designed to study quadruped gaits where both front legs (resp. rear legs) have identical movements. Its unique front leg (resp. rear leg) acts as the two front legs (resp. rear legs) of the quadruped, so that SemiQuad can be considered as an implementation of a virtual quadruped, hence its name. The legs have passive (uncontrolled) feet that extend in the frontal plane. Due to this, the robot is stable in the frontal plane. Four motors located in haunches and knees drive the mechanism. The locomotion of the prototype is a planar curvet gait. In double support, our prototype is statically stable and over actuated. In single support, it is unstable and under actuated. The reference walking gaits have been designed using an intuitive strategy which is such that the absolute orientation is not required. Still, it contains imbalance phases during which the observer can be used, and its results evaluated. The estimation results being correct, such an observer can be used for contexts where the absolute angle is necessary. Furthermore, the idea can be useful for other types of walking robots, such as bipeds with imbalance phases.

The organization of this chapter is the following. Section 2 is devoted to the model of SemiQuad. It also contains the data of its physical parameters. The intuitive gaits which were designed for SemiQuad are presented in section 3. The statement of the problem of estimation of the absolute orientation of SemiQuad is defined in Section 4. Simulation results and experimental results avec presented in section 5. Section 6 presents our conclusions and perspectives.

Presentation and dynamic models of SemiQuad

SemiQuad

The prototype (see figure 1) is composed of a platform and two identical double-link legs with knees. The legs have passive (uncontrolled) feet that extend in the frontal plane. Thus, the robot can only execute 2D motions in the sagittal plane, as considered here. There are four electrical DC motors with gearbox reducers to actuate the haunch joints between the platform and the thighs and the knee joints. Using a dynamic simulation, we have chosen parameters of the prototype (the sizes, masses, inertia moments of the links) and convenient actuators. The parameters of the four actuators with their gearbox reducers are specified in Table 1. The lengths, masses and inertia moments of each link of SemiQuad are specified in Table 2.

. Parameters of SemiQuad

The maximum value of the torque in the output shaft of each motor gearbox is 40 N.m . This saturation on the torques is taken into account to design the control law in simulation and in experiments. The total mass of the quadruped is approximately 14 kg. The four actuated joints of the robot are each equipped with one encoder to measure the angular position. The angular velocities are calculated using the angular positions. Currently the absolute platform orientation angle α (see figure 2) is not measured. As explained before, the proposed walking gait does not require this measurement. Each encoder has 2000 pts/rev and is attached directly to the motor shaft. The bandwidth of each joint of the robot is determined by the transfer function of the mechanical power train (motors, gearboxes) and the motor amplifiers that drive each motor. In the case of SemiQuad, we have approximately a 16 Hz bandwidth in the mechanical part of the joints and approximately 1.7 kHz for the amplifiers. The control computations are performed with a sample period of 5 ms (200 Hz). The software is developped in C language.

Dynamic model of SemiQuad

Figure 2 gives the notations of the torques, the ground reactions, the joint variables and the Cartesian position of the platform. Using the equations of Lagrange, the dynamic model of SemiQuad can be written:

+ + = Γ + + 1 2
e e e e e e R 1 R 2

D q H q G B D R D R   (1)
with,

  =     T T : e p p
q q x z . The vector q is composed of the joint actuated variables and the absolute orientation of the platform,

  =     T : 1 2 3 4 q θ θ θ θ α ; ( ) p p
x ,z are the Cartesian coordinates of the platform center. The joint angle variables are positive for counter clockwise motion. e D (q) ( ) × 7 7 is the inertia positive definite matrix. The matrix e H (q,q)  ( ) × 7 7 represents the Coriolis and centrifugal forces and e G (q) ( ) × 7 1 is the vector of the gravity forces. e B is a constant matrix composed of ones and zeros. Each matrix j R D (q) ( ) × 7 2 ( j =1,2 ) is a jacobian matrix which represents the relation between feet Cartesian velocities and angular velocities. It allows to take into account the ground reaction j R on each foot. If foot j is not in contact with the ground, then

  =   T j R 0,0 . The term   =     Γ Γ Γ Γ Γ T : 1 2 3 4
is the vector of four actuator torques. Let us assume that during the single support, the stance leg acts as a pivot joint. Our hypothesis is that the contact of the swing leg with the ground results in no rebound and no slipping of the swing leg. Then, in single support, equation ( 1) can be simplified and rewritten as:

+ + = Γ Dq Hq G B   (2)
As the kinetic energy = T 1 K q Dq 2   does not depend on the choice of the absolute frame (see [START_REF] Spong | Robot dynamics and control[END_REF])) and furthermore variable α defines the absolute orientation of SemiQuad, the inertia matrix D ( ) × 5 5 does not depend on α , and then

( ) = , , , 1 2 3 4 D D θ θ θ θ .
As for the case of equation ( 1), the matrix H(q,q)  ( ) × 5 5 represents the Coriolis and centrifugal forces and G(q) ( ) × 5 1 is the vector of gravity forces. B is a constant matrix composed of ones and zeros.

Equation ( 2) can be written under the following state form:

( ) = + Γ Γ          -1 rel q x = f(x) g(q ) D -Hq -G + B (3) With   =    T T T
x q q and the joint angle vector

  =     T 1 2 3 4 rel q θ θ θ θ . The state space is defined as ] ] { }   ∈ ⊂ = = < < ∞ ∈ -π π      T 5 10 T T M
x X R x q q q q ; q , . From these definitions, it is clear that all state coordinates are bounded.

Discrete Model

Our objective is to design an extended Kalman filter with a sampling period ∆ to observe the absolute orientation α . Then it is necessary to find a discrete model equivalent to (3). A possible solution is to write

+ - ≈ ∆ k 1 k x x x 
and (3) becomes:

= + ∆ + Γ k +1 k k relk k x x (f(x ) g(q ) ) (4)
For SemiQuad, we have preferred to sample the generalized coordinates and their velocities using approximations to a different order by a Taylor development:

∆ ∆ ∆ + + ∆ + n 2 n x(t) x (t) x(t + ) = x(t) + x(t) + ... ε 2! n!   , (5)
From ( 5), developments to second order and first order have been used for the generalized coordinates and their velocities, respectively. Limiting the order where possible limits the noise, but using second order developments for position variables introduces their second order derivative and allows to make use of the dynamic model.

2 k 1 k k k 5 1 k 1 k k q q q q q q q 0 2 + × +         ∆ ≈ + ∆ +                      (6)
With this method, a discrete model of ( 3) is calculated. If we add the equation corresponding to the measurement of the joint angles, we obtain the following system:

( )

1 1 2 3 4 4 4 + = Γ = =θ θ θ θ = = s k k k T x k k k x f (x , ) y h(x )
Cx with C I (7)

Impulsive impact equation

The impact occurs at the end of the imbalance phase, when the swing leg tip touches the ground, i.e. :

{ } f x S x X q=q ∈ = ∈
where f q is the final configuration of SemiQuad. The instant of impact is denoted by i T . Let us use the index 2 for the swing leg, and 1 for the stance leg during the imbalance phase in single support. We assume that: ♦ the impact is passive, absolutely inelastic; ♦ the swing leg does not slip when it touches the ground;

♦ the previous stance leg does not take off; ♦ the configuration of the robot does not change at the instant of impact. Given these conditions, at the instant of an impact, the contact can be considered as impulsive forces and defined by Dirac delta-functions

j j R i R I (t T ) = ∆ - (j=1, 2). Here j Nj Tj T R R R I I I   =  
, is the vector of the magnitudes of the impulsive reaction in leg j (Formal'sky 1974). The impact model is calculated by integrating (1) between i T -(just before impact) and i T + (just after impact) . The torques provided by the actuators at the joints, and Coriolis and gravity forces, have finite values, thus they do not influence the impact. Consequently the impact equation can be written in the following matrix form:

( ) 1 1 2 2 e e e R R R R D (q) q q D (q)I D (q)I + - -= +  (8)
Here, q is the configuration of SemiQuad at i t T = , e q -  and e q +  are the angular velocities just before and just after impact, respectively. Furthermore, the velocity of the stance leg tip before impact is null. Then we have:

1 2 1 0 T R e D q + × =  (9)
After impact, both legs are stance legs, and the velocity of their tip becomes null:

1 2 4 1 0 T R e T R D q D + ×   =        (10)

Walking gait strategy for SemiQuad

By analogy with animal gaits with no flight phase, SemiQuad must jump with front or back leg to realize a walking gait.

There is no other way to avoid leg sliding. Then it is necessary to take into account that SemiQuad is under actuated in single support and over actuated in double support. Let us briefly present the adopted strategy to realize a walking gait for SemiQuad. It was tested first in simulation to study its feasibility and then experimentally [START_REF] Aoustin | Numerical and experimental study of the virtual quadruped-SemiQuad[END_REF]. A video can be found on the web page http://www.irccyn.ec-nantes.fr/irccyn/d/en/equipes/Robotique/Themes/Mobile. Figure 4 represents a sequence of stick configurations for one step to illustrate the gait. Let us consider half step n as the current half step, which is composed of a double support, a single support on the rear leg and an impact on the ground. During the double support, SemiQuad has only three degrees of freedom. Then its movement can be completely prescribed with the four actuators. A reference movement is chosen to transfer the platform centre backwards. This is done by defining a polynomial of third order for both Cartesian coordinates xp and zp. The coefficients of these polynomials are calculated from a choice of initial and final positions, of the initial velocity and an intermediate position of the platform centre. The reference trajectories for the four actuated joint variables are calculated with an inverse geometric model. Then, by folding and immediately thrusting the front leg, the single support phase on the rear leg starts. During this imbalance phase, SemiQuad has five degrees of freedom and its rotation is free around its stance leg tip in the sagittal plane. Reference trajectories are specified with third order polynomial functions in time for the four actuated inter-link angles. However, the final time Tp of these polynomial functions is chosen smaller than the calculated duration Tss of the single support phase, such that before impact the four desired inter-link angles id (θ i = 1,..., 4) become constant. Using this strategy, we obtain the desired final configuration of our prototype before the impact even if Tss is not equal to the expected value.

= + + + = θ ≤ ≤ 2 3 0 1 2 3 p id ie p p ss id θ a a t a t a t if t < T θ (T ) if T t T (11)
The coefficients of these polynomials are calculated from a choice of initial, intermediate and final configurations and of the initial velocity for each joint link. Just after impact, the next half step begins and a similar strategy is applied (figure 4). The tracking of the reference trajectories is achieved using a PD controller. The gains, which were adjusted using pole placement, were tested in simulation and in experiments. Figure 3 shows the evolutions of the absolute orientation variable α(t) and its velocity α(t)  , obtained from the simulation of SemiQuad for five steps. These graphs clearly show that the dynamics of the absolute orientation cannot be neglected in the design of a control law based on a state feedback. The durations of the double support phase and the single support phase are 1.5 s and 0.4 s respectively.

Observation of the absolute orientation of SemiQuad

System (3) is generically observable if the following matrix O has a full rank (see [START_REF] Plestan | Linearisation by generalized input-ouput injection[END_REF])), which is equal to 10, with 1 p ( k ,...,k ) the p observability indexes.

( )

- - Ο = p 1 k 1 k 1 1 1 p p f f dh ... dL h ... dh ... dL h ( 12
)
where dh is the gradient vector of function h (see system ( 7)) with respect to the state vector x, and dLfh is the Lie derivative of h along the vector field f. We have also checked that the equivalent property is satisfied by the discrete model. This means that, at each sampling time tk, it is possible to find an observability matrix with 10 independent rows or columns.

Having checked system observability, we propose an Extended Kalman Filter to observe the absolute orientation. The design of this Extended Kalman Filter is now described.

In practice, due to uncertainty in the determination of parameters and to angular measurement errors, system (3), and of course system (7), are only approximations. A standard solution is to represent modelling and measurement errors as additive noises disturbing the system. Let us consider the associated ``noisy'' system:

( )

1 + = Γ + α = = + β s k k k k T 1 2 3 4 k k k x f (x , ) y C(x ) θ θ θ θ (13)
In the case of a linear system, if k α and k β are white Gaussian noises, mutually independent and independent of x, the Kalman filter is an optimal estimator. When the system is not linear, it is possible to use the Extended Kalman Filter (EKF) by linearizing the evolution equation fs and the observation equation (which is in our case linear) around the current state estimate. Although convergence and optimality are no longer guaranteed, the interest and the effectiveness of the Extended Kalman Filter have been proved in many experimental cases. The EKF is very often used as a state observer [START_REF] Bonnifait | Design and experimental validation of an odometric and goniometric localization system for outdoor robot vehicles[END_REF]).

In the case of our system, the equations of the EKF are:

• a priori estimation: uses data available before tk+1

1 1 - + - α + = Γ = + s k k k T k k k k x f (x , ) P A P A Q   (14)
• a posteriori estimation: uses data available at tk+1 ( ) ( )

1 1 1 1 1 10 10 1 1 1 - - + + + + + - × + + + = + - = - k k k k k k k k x x K y Cx P I K C P   (15)
with:

= ∂   =   ∂   k s k x x f A x  and ( ) - - - β + + + = + 1 T T k 1 k 1 k 1 K P C CP C Q
Here yk+1 are the measured joint variables, which are the first four components of vector xk at time tk, and k+1 -Cx  is the a priori estimation of these joint variables.

α Q and β Q are the covariance matrices of k α and k β , K is the Kalman gain and P the estimated covariance matrix of prediction ( - P at tk) and estimation ( P at tk) errors.

Simulation and experimental results.

For the simulation and experimental tests, the physical parameters defined in section 2 are used. The sampling period Δ is equal to 5 ms. The incremental encoders having N=2000 points per revolution, the variance of measurement is taken equal to ( )

2 2
π 3ΔN =8.225 10 -4 . The errors of incremental encoders being independent, we have chosen β Q =8.225 10 -4 (i=1,2,3,4) are the inputs of the Extended Kalman Filter. In both cases, the state vector

         T 1 2 3 4 1 2 3 4 θ θ θ θ α θ θ θ θ α is estimated. Semiquad i Γ (i = 1, 2, 3, 4) Estended Kalman Filter i i . θ θ (i = 1, 2, 3, 4) i Γ (i = 1, 2, 3, 4) i i       α, α, θ θ (i = 1, 2, 3, 4) i i
. θ θ (i = 1, 2, 3, 4) Fig. 5. Principle of tests of the Extended Kalman Filter with SemiQuad.

Simulation results

Figure 6 shows the evolution of the estimated and real orientations of the platform during a single support phase of the cyclic walking gait of SemiQuad. The initial error, which has been set to 0.0262 rad (1.5 degree), is rapidly reduced, andthe estimated orientation converges towards the real orientation. Let us notice that a maximum value of 1.5 degree for the initial error is reasonable because experimentally  α(0) is determined by the geometric model at the end of the previous double support.

In the model used by the observer, we do not consider any friction. We have performed robustness tests of our estimator by adding a viscous friction, Γ = i v i F θ (i=1,2,3,4), and a Coulomb friction Γ = i s i F θ  (i=1,2,3,4) to the simulation model. Figure 7 shows the estimated and real orientations of the platform of SemiQuad in the case when a viscous friction is added. The coefficient Fv equals to 0.1 N.m.s/rad. Similarly, figure 8 shows the estimated and the real orientations of the platform of SemiQuad in the case of a Coulomb friction, with a coefficient Fs equal to 0.2 N.m. Last robustness test (figure 9) presents the estimated and real orientations of the platform of SemiQuad with an inertia reduced by 5% for the platform in the simulator.

In practice, 5% precision on inertia is feasible (see identification results in [START_REF] Lydoire | Experimental dynamic parameters identification of a seven dof walking robot[END_REF]).

From these robustness tests, we can conclude that we have no finite time convergence. However, the final relative errors of the estimated orientations of the platform of SemiQuad are small. Since it will be possible to update the initial condition of the estimator during the next double support phase, with the measurements of the encoders and the geometrical relations, such errors are not a problem.

Experimental results

At each step, the estimator is initialized with the configurations and the velocities at the end of the previous double support phase. At each sampling time, velocities are obtained by the usual differentiation operation

- - = i i i θ (kΔ) θ ((k 1)Δ) θ Δ  (i=1,2,3 4
). No filtering is applied to smooth the measured joint variables i θ , their velocities i θ  and the four torques i Γ (i=1,2,3 4).

Figure 10 shows the estimation of the absolute orientation of the platform α(t) . The duration of the single support phase is 15% smaller than in simulation. It can probably be explained by the fact that our knowledge of the physical parameters of the robot is not perfect, and that we neglected effects such as friction in the joints. Currently, there is no experimental measured data about the evolution of α(t) in single support, because SemiQuad is not equipped with a sensor such as a gyrometer or a gyroscope. However, in double support, using the geometric and kinematic models it is possible to calculate α(t) and α(t)  . In addition to providing initial conditions for the observer, this also allows to calculate the orientation at the end of the single support phase, just after impact. The corresponding value is displayed as a star on the next graph, and is equal to 0.01 rad (0.57 degree). The difference between this value and the estimated value at the same instant is almost 3 degrees. Fig. 10. Estimation of the absolute orientation α(t) of the platform using the experimental data.

Conclusion

An application of the digital Extended Kalman Filter has been presented for the problem of estimating the absolute orientation of SemiQuad, a 2D dynamically stable walking robot. There are some differences between simulations and experiments, but the results still prove the ability of our observer to yield a short term estimation of the orientation of the robot. The precision is sufficient for the estimation to be useful for calculating the dynamic model and monitoring the balance of the robot. This task is important for SemiQuad, and vital for bipeds, to which the idea is also applicable (see Lebastard, Aoustin, & Plestan 2006 for a different type of observer). Given the possibility to re-initialize the observer at each double support phase, even if very short, as it can be for bipeds, the observer can provide the absolute orientation over time without the use of any additionnal sensor, which was the goal of our work.

In a near future, we plan to equip SemiQuad with a gyrometer to fully evaluate the performance of our estimator over time.

Our perspective is to use the estimated orientation in advanced feedback controllers.

Fig

  Fig. 1. Photography of SemiQuad.

Fig. 2 .

 2 Fig. 2. SemiQuad's diagram: generalized coordinates, torques, forces applied to the leg tips, locations of mass centers.

Fig. 3 .

 3 Fig. 3. Evolution of α(t) and α(t) in simulation during the walking gait for five steps.

Fig. 4 .

 4 Fig. 4. Plot of half steps n and n+1 of SemiQuad. as a sequence of stick figures.

  configuration variables are determined by trial and error from simulation and experimental results. The components of α Q for velocity variables are derived from the values for position variables, taking into account the sampling period, and are larger than those corresponding to position variables. the covariance matrix P takes into account a determination of α less precise and fixes the variances on the velocities, as for α Q , taking into account of the sampling period. in simulations and in experiments were done following the scheme of figure 5. In simulations, the joint variables i θ and their velocities i θ  (i=1,2,3,4) obtained by integration of the direct dynamic model of SemiQuad and the control torques i Γ (i=1,2,3 4) are the inputs of the Extended Kalman Filter. For the experimental tests, the joint variables i θ (i=1,2,3 4) are measured and differentiated to obtain the velocities i θ  . These eight variables, together with the four experimental torques i Γ

Fig. 6 .

 6 Fig. 6. Absolute orientation α(t) of the platform: real (solid) and estimated (dashed).

Fig. 7 .

 7 Fig. 7. Absolute orientation α(t) of the platform: real (solid) and estimated (dashed), with a supplement viscous friction.

Fig. 9 .

 9 Fig. 9. Absolute orientation α(t) of the platform: real (solid) and estimated (dashed), with an error on the inertia of the platform.


Hugo Ayats
email: hugo.ayats@irisa.fr

Peggy Cellier
email: peggy.cellier@irisa.fr

Sébastien Ferré
email: sebastien.ferre@irisa.fr

Extracting Relations in Texts with Concepts of Neighbours

During the last decade, the need for reliable and massive Knowledge Graphs (KG) increased. KGs can be created in several ways: manually with forms or automatically with Information Extraction (IE), a natural language processing task for extracting knowledge from text. Relation Extraction is the part of IE that focuses on identifying relations between named entities in texts, which amounts to find new edges in a KG. Most recent approaches rely on deep learning, achieving state-ofthe-art performances. However, those performances are still too low to fully automatize the construction of reliable KGs, and human interaction remains necessary. This is made difficult by the statistical nature of deep learning methods that makes their predictions hardly interpretable. In this paper, we present a new symbolic and interpretable approach for Relation Extraction in texts. It is based on a modeling of the lexical and syntactic structure of text as a knowledge graph, and it exploits Concepts of Neighbours, a method based on Graph-FCA for computing similarities in knowledge graphs. An evaluation has been performed on a subset of TACRED (a relation extraction benchmark), showing promising results.

Introduction

During the last decade, the need for reliable and massive knowledge bases, represented as Knowledge Graphs (KG), increased. KGs allow to structure, organize and share knowledge. A challenge is to build KGs that are at the same time reliable and large. There exist several ways to create those KGs: manually with forms (e.g., wikidata1 ), providing reliability (assuming the producer is reliable), or automatically by using Information Extraction (IE) techniques [START_REF] Grishman | Twenty-five years of information extraction[END_REF], allowing to easily build very large KG by using the large amount of existing textual data (e.g., scientific papers, books, official websites). IE is a natural language processing task for extracting knowledge from text. Relation Extraction is a sub-task of IE that focuses on identifying relations between named entities in texts, which amounts to find new edges between KG entities. It is a classification task, where given two named entities in a sentence, the goal is to predict the relation type between the two. Among existing approaches for the relation extraction task, the deep learning methods are the most efficient. First, those method were based on convolutional neural networks [START_REF] Nguyen | Relation Extraction: Perspective from Convolutional Neural Networks[END_REF]. Other deep learning approaches, such as [START_REF] Wu | Simplifying Graph Convolutional Networks[END_REF], work on pruned dependency trees. Today, methods based on language models such as BERT [START_REF] Yamada | LUKE: Deep Contextualized Entity Representations with Entity-aware Self-attention[END_REF] provide the best results. However, those deep learning methods have two main limitations. First, they are not sufficiently reliable for a full automation. Second, they suffer, as most of numerical approaches, of a lack of explanations for predictions, which hinders human interaction.

Formal Concept Analysis (FCA) has already been shown effective for classification tasks [START_REF] Kuznetsov | Machine learning and formal concept analysis[END_REF], and has the advantage to provide symbolic representations of predictions that can be used as explanations. However, it faces a problem of tractability when all concepts need to be computed. An interesting approach is to adopt lazy learning, where this computation is delayed until there is an instance to be classified, and only the concepts that are relevant to that instance are computed. This lazy approach was applied early to the incremental building of a logical context [START_REF] Ferré | The use of associative concepts in the incremental building of a logical context[END_REF], then later advocated in [START_REF] Kuznetsov | Fitting pattern structures to knowledge discovery in big data[END_REF] with Pattern Structures [START_REF] Ganter | Pattern structures and their projections[END_REF], and applied, for instance, to relation extraction in biomedical texts [START_REF] Leeuwenberg | Exploring Pattern Structures of Syntactic Trees for Relation Extraction[END_REF]. More recently, this has been formalized as Concepts of Neighbours [START_REF] Ferré | Answers Partitioning and Lazy Joins for Efficient Query Relaxation and Application to Similarity Search[END_REF] based on Graph-FCA [START_REF] Ferré | Graph-FCA: An extension of formal concept analysis to knowledge graphs[END_REF]. The particularity of the Concepts of Neighbours method, such as this contribution, is the use of an efficient anytime algorithm based on the partitioning of the set of entities into concepts. This has for consequence that there is no need for a sampling strategy: all entities appear in the extensions of the returned concepts. The use of Concepts of Neighbours has been applied to the completion of knowledge graphs [START_REF] Ferré | Application of concepts of neighbours to knowledge graph completion[END_REF], and has shown competitive results compared to deep learning approaches, and state-of-the-art results compared to rule-based approaches such as AnyBURL [START_REF] Meilicke | Anytime Bottom-Up Rule Learning for Knowledge Graph Completion[END_REF] or AMIE+ [START_REF] Galárraga | Fast rule mining in ontological knowledge bases with AMIE+[END_REF]. Rule-based approaches are also interpretable but they are not lazy because they compute a set of rules before seeing any test instance. Therefore, they have to strongly restrict the considered graph patterns for combinatorial reasons, unlike in Concepts of Neighbours where all connected graph patterns with constants are supported. AnyBURL only mines path rules and AMIE+ focuses on small connected and closed rules.

In this paper, we introduce a symbolic and lazy approach for relation extraction based on Concepts of Neighbours. A first contribution is the representation of sentences by graphs, covering both lexical and syntactic information. Other contributions, compared to previous application of Concepts of Neighbours, are that the instances to be classified are couples of graph nodes, instead of single nodes, and that node labels are organized into a taxonomy (e.g., word hypernyms). We validate our approach with experiments on TACRED [START_REF] Zhang | Position-aware Attention and Supervised Data Improve Slot Filling[END_REF], a dataset for evaluating relation extraction methods.

In the sequel, Section 2 gives preliminaries about Graph-FCA and Concepts of Neighbours. Then, Section 3 introduces the modeling of sentences as graphs. Section 4 details how Concepts of Neighbours can be used for relation extraction.

Preliminaries

In this section, we recall the main definitions and results of Concepts of Neighbours [START_REF] Ferré | Application of concepts of neighbours to knowledge graph completion[END_REF]. We start by defining graph contexts and graph concepts, introduced in Graph-FCA [START_REF] Ferré | Graph-FCA: An extension of formal concept analysis to knowledge graphs[END_REF], a generalization of Formal Concept Analysis (FCA) [START_REF] Ganter | Formal Concept Analysis: Mathematical Foundations[END_REF] The most specific query Q = msq(R) is the conjunctive query representing what the tuples of objects in R have all in common. For the sake of simplicity, we restrict the following examples to 1-tuples, aka. singletons. In the running example, the singletons (W illiam) and (Charlotte) have in common the following query, Q W C , that says that both have married parents:

Q W C = msq({(W illiam), (Charlotte)})
= (x) ← parent(x, y), f emale(y), parent(x, z), male(z), spouse(y, z).

We have

R W C = res(Q W C ) = {(W illiam), (Harry), (George), (Charlotte), (Louis)} so that C W C = (R W C , Q W C ) is a graph concept. A concept C 1 = (R 1 , Q 1 ) is more specific than a concept C 2 = (R 2 , Q 2 ), in notation C 1 ≤ C 2 , if R 1 ⊆ R 2 .
For example, a concept more specific than C W C is the concept of the children of Kate and William, whose extension is {(George), (Charlotte), (Louis)}, and whose intension is:

(x) ← parent(x, y), (y = Kate), parent(x, z), (z = W illiam).
The total number of graph concepts in a knowledge graph is finite but in the worst case, it is exponential in the number of objects, and in arity k. It is therefore not feasible in general to compute the set of all concepts. Instead of considering concepts generated by subsets of tuples, we consider concepts generated by pairs of tuples, and use them as as a symbolic form of distance between objects. Definition 2. Let t 1 , t 2 ∈ O k be two k-tuples of objects. The conceptual distance δ(t 1 , t 2 ) between t 1 and t 2 is the most specific graph concept whose extension contains both tuples, i.e. δ(t 1 , t 2 ) = (R, Q) with Q = msq({t 1 , t 2 }), and R = res(Q).

For example, the above concept C W C is the conceptual distance between (W illiam) and (Charlotte). The "distance values" have therefore a symbolic representation through the concept intension Q that represents what the two tuples have in common. The concept extension R contains in addition to the two tuples all tuples t 3 that match the common query (t 3 ∈ res(Q)). Such a tuple t 3 can be seen as "between" t 1 and t 2 : in formulas, for all t 3 ∈ ext(δ(t 1 , t 2 )), δ(t 1 , t 3 ) ≤ δ(t 1 , t 2 ) and δ(t 3 , t 2 ) ≤ δ(t 1 , t 2 ). Note that order ≤ on conceptual distances is a partial ordering, unlike classical distance measures.

A numerical distance dist(t 1 , t 2 ) = |ext(δ(t 1 , t 2 ))| can be derived from the size of the concept extension, because the closer t 1 and t 2 are, the more specific their conceptual distance is, and the smaller the extension is. For example, the numerical distance is 5 between (W illiam) and (Charlotte) (see C W C ), and 3 between (George) and (Charlotte).

The number of conceptual distances δ(t 1 , t 2 ) is no more exponential but quadratic in the number of objects |O|. In the context of lazy learning, tuple t 1 is fixed, and the number of concepts become linear. For k-tuples, that number is bounded by |O| k . Those concepts are called Concepts of Neighbours. Definition 3. Let t ∈ O k be a k-tuple of objects. The Concepts of Neighbours of t are all the conceptual distances between t and every tuple t

∈ O k . C -N (t, K) = {δ(t, t ) | t ∈ O k } Figure 2
shows the 6 Concepts of Neighbours of the singleton (Charlotte), and their partial ordering as a Venn diagram. For instance, the concept containing (Charlotte) only is included in the concept that also contains (Louis) and (George), which is included in the concept that also contains (W illiam) and (Harry). This implies that George is semantically closer to Charlotte than William is. Although (Louis) and (Diana) are both nearest neighbours of (Charlotte), and at the same extensional distance 3, they are so for different reasons as they belong to different Concepts of Neighbours with different intensions. Louis has the same parents as Charlotte, while Diana has the same gender.

The proper extension of a concept of neighbours δ l is the part of its extension that does not appear in sub-concepts. The proper extensions define a partition over the set of objects O, where two objects are in the same proper extension if and only if they are at the same conceptual distance. For instance, Diana and Kate are in the same proper extension.

x <-parent(x,y), (y = William), parent(x,z), (z = Kate) parent(x,z), female(z), spouse(y,z)

x <-parent(x,y), male(x),

Modeling Sentences as Graphs

The input data of relation extraction is a set of annotated sentences. Each sentence is annotated by two entities, the subject and object of the relation, and by the type of those entities. The input sentences are split in two parts: training sentences for which the relation is known, and test sentences for which the relation is to be predicted. In this section we explain and discuss the modeling of annotated sentences as graphs because this is the required input of Concepts of Neighbours, and more precisely as RDF graphs because this is the expected input of the existing implementation of Concepts of Neighbours.

NLP Treatments

Before building the RDF graph, several NLP treatments are applied on each sentence2 . First, the sentence is split into tokens. Second, part-of-speech (POS) tags3 and lemmas are computed for each token. Third, the syntactic structure of the sentence is extracted as a dependency tree4 . Finally, named entities are identified, and a named entity type is associated to each of them.

Table 1 shows the result of the processing of the sentence "The University of Rennes is French". For example, it shows that the 4th token is Rennes, has for lemma Rennes and for POS tag NNP (a proper noun). It is part of a named entity of type ORGANIZATION. It has for parent in the dependency tree the 2nd token and it is linked to this token via relation nmod (linking an nominal modifier to its parent noun). We then apply a few post-treatments in order to simplify and improve the sentence representation. Removing punctuation. Punctuation tokens (e.g., token 7 in Table 1) and their links are removed from the dependency tree. This is easy as they only occur as leaves. Note that the parser takes into account punctuation when extracting the dependency tree.

Compound named entities. A named entity can overlap several contiguous tokens, for instance University of Rennes overlaps tokens 2-4 in the example. However, a named entity is a semantic unit: it holds its own meaning, which can be very different from the meaning of its individual tokens. Therefore, manipulating a named entity as a succession of tokens can cause an important loss of semantics. Except when there is a parse error, the tree structure of an entity is a subtree of the dependency tree. We call it a factor by analogy with the definition of a string factor. The proposed solution is to collapse the subtree into its root. Then the sentence retains a valid syntactic and semantic structure (no dangling link for instance). For example, in the sentence presented in Table 1, the named entity "University of Rennes" is collapsed into token 2, and tokens 3 and 4 disappear. The expression "University of Rennes" can indeed be seen as a proper noun (POS tag NNP ). In case of a parse error, the named entity is collapsed to the last token as a fallback.

Sentences as an RDF Graph

In order to model a set of processed sentences as one RDF graph, each token is represented by an RDF node (e.g., id:1_2 for the 2nd token of the 1st sentence), and each dependency link is represented by an RDF edge. The lemmas, POS tags, and named entity types of a token are represented by RDF types on the corresponding node (see discussion below). Figure 3 gives the RDF representation for the example in Table 1. The 2nd token is modeled by node id:1_2, which has as types lemma University of Rennes, POS tag NNP, and named entity type organization, and is linked to node id:1_6 by relation nsubj.

Representation of lemmas and POS tags as RDF types. As specified above, we use relation rdf:type instead of defining specific relations for linking a node to its lemma or POS tag. This choice has been made for three reasons. First, by having lemmas and POS tags represented by RDF types rather than RDF nodes, we avoid to have two sentences get connected as soon as they share a lemma or a POS tag. Second, for the computation of Concepts of Neighbours, it prevents from having intensions including dummy patterns such as "has an unspecified POS tag". Third, as presented in Section 3.3, it allows us to create a type hierarchy for lemmas and POS tags.

Lemmatisation of named entities. Note that, if in the general case the lemma of a token is a good representation, it does not stand in the case of named entities: e.g., unite state of America vs United States of America. Therefore, for named entities, we use the original words instead of the lemmas in the RDF graph.

Optimization of the modeling. Although the algorithm computing Concepts of Neighbours is anytime, the size of the RDF graph has an impact on the number of computed concepts, and hence on the quality of predictions. We can prune the RDF graph according to the position of the subject and object, in a way that reduces its size without loosing too much information. Indeed, Zhang et al. [START_REF] Zhang | Graph Convolution over Pruned Dependency Trees Improves Relation Extraction[END_REF] states that not all dependencies are of same interest for extracting relations.

Only those close to the path between the subject and the object carry useful information. However, it can be easily seen that reducing the dependency tree to a path would remove essential information for relation extraction, e.g. in the case of a negation attached to a verb that is on the path. Our solution is to prune the dependency tree to keep only the path between the subject and the object, plus the tokens up to maximal distance K from this path. Several values of K were tested, and the value K = 1 appears to be a good trade-off between size reduction and performance.

Fig. 4: Fragment of a type hierarchy obtained from WordNet

Type Hierarchies

An RDF graph can be enriched with inferred types and edges by declaring domain knowledge. The most common form of domain knowledge is hierarchies of types, based on the RDFS property rdfs:subClassOf. The inference rule is that: if node X has type A and A is a subclass of B, then X also has type B. We use several type hierarchies to increase the generalization power of Concepts of Neighbours. First, the set of POS-tags [START_REF] Toutanova | Feature-rich part-of-speech tagging with a cyclic dependency network[END_REF] is fine-grained enough to create a hierarchy on a few POS-tags: for example, the gerund of a verb (POS-tag VBG) is a subclass of verb (POS-tag VB ). In total, we have 11 rdfs:subClassOf declarations 5 . Second, in order to add semantic knowledge to the modeling, the lexical database WordNet [START_REF] Miller | WordNet: An Electronic Lexical Database[END_REF] is used for creating a lemma hierarchy for nouns and verbs. Each synset of a lemma is considered as a superclass of the lemma, and each hypernym of a given synset is considered as a superclass of this synset. Figure 4 shows a fragment of this lemma hierarchy. For instance, synset educational institution allows to generalize over lemmas university and school. The lemma hierarchy thus increases the chance to find similarities between sentences using words that have different lemmas but close meanings.

Relation Extraction with Concepts of Neighbours

Once the modeling is done, for each test example we want to compute which examples of the training corpus are the more similar, and do a prediction from their annotation. In order to do so, an RDF graph regrouping the modeling of all the sentences of the dataset is made, the Concepts of Neighbours method is used to group the examples by similarities, and then a decision method is used to do a prediction from those Concepts of Neighbours. In the following, we first present how the Concepts of Neighbours have been adapted to this specific task. Then, we describe two decision methods for making prediction from Concepts of Neighbours.

Concepts of Neighbours for Relation Extraction in Texts

In order to use Concepts of Neighbours on the modeling presented in Section 3, a few aspects needs to be addressed. First, we need to clearly identify the RDF nodes representing the subject and the object in each sentence. Then, we need to compute Concepts of Neighbours on a (subject, object) couple, compared to a single node in previous applications. This strongly increases the number of potential neighbours. Finally, we show how to reduce this number of in the specific case of relation extraction.

Identification of the Subjects and Objects

There is a need to unambiguously identify the nodes of the RDF graph forming the (subject, object) couples. The issue is that subjects or objects can overlap several tokens. The collapse of the named entities presented in Section 3.1 solves this problem in the vast majority of cases as subjects and objects are most of the time either named entities or one-token expressions. However, ambiguous cases still exist in a small proportion of the sentences. This problem can appear in three cases: first, when the subject or object is expressed as a nominal group (e..g, "the man", "the university"); second, when the subject or object includes a named entity but is longer than it (e.g., "the President of the United States of America" is a subject, whereas only "United States of America" is tagged as a named entity); third, when the subject or object is a named entity that has not been recognized as a named entity.

The solution proposed to solve these cases is similar to the solution presented in Section 3.1 to collapse named entities: as a subject or an object is necessarily a group of contiguous tokens with a particular meaning, it must form a tree factor in the dependency tree. Therefore, it can be considered that the root of this factor carries the semantic and syntactic information, and then can be pointed out as the subject or the object. Like for named entities, if the tokens do not form a tree factor because of a wrong annotation or a parse error, the last token is used instead of the root. It can be pointed out that, unlike for named entities, the choice has been made not to merge the tokens constituting the subject or the object as their syntactic structure (if any) is generally informative, like in "the President of X".

Concepts of Neighbours for Couples of Nodes

The Concepts of Neighbours of the identified couples (subject, object) are then computed. The method was originally designed to generate Concepts of Neighbours for tuples of arbitrary size. However, until now, it was only applied for unary concepts. The switch from unary concepts to binary ones (and by extension n-ary) has two main consequences discussed in the following.

Intension. First of all, unlike unary concepts, binary concepts can have an intension that is not connected. For example, in the sentence presented in Figure 3, both the connected intension (relating the object to the subject via dependency nsubj):

(s, o) ← nsubj(o, s), U nivRennes(s), f rench(o), cop(o, x), is(x)
and the disjoint one (no path between subject and object):

(s, o) ← U nivRennes(s), f rench(o), cop(o, x), is(x)
can appear during the computation of the Concepts of Neighbours. In both cases, the pruning strategy presented in Section 3.2 ensures that the intension focuses on and around the path between the subject and the object.

Reduction of the Set of Couples. Another issue is the large number of potential neighbours: as detailed in [START_REF] Ferré | Application of concepts of neighbours to knowledge graph completion[END_REF], to compute the Concepts of Neighbours for a tuple of k objects in a graph involving n objects, the algorithm has to generate and partition n k tuples. Therefore, for a large graph, the computation of concepts of arity greater than 1 is rapidly intractable. In the present case, if we consider a dataset composed of ten thousands of sentences, there are tens of billions of potential neighbours. However, the use of the Concepts of Neighbours method is in this context for extracting relations by comparing a (subject, object) couple from a test sentence to annotated couples from the training dataset, and it appears that the number of annotated couples is far smaller: only one per example in the training dataset. Therefore, in the following, we use this set of couples for the computation of Concepts of Neighbours, as it permits to simultaneously reduce drastically the computation cost and remove noise from the computed concepts while keeping all the knowledge of interest.

In addition, as evoked in Section 3, in a relation extraction dataset each subject and object has a type, and these types can be used to reduce the set of potential neighbours further. For example, if an example has for subject a person and for object a location, it can be seen that the relation expressed by this example could be place_of_birth or place_of_living, but can not be age or parent. Therefore, for a given couple (subject_type, object_type), a set of compatible relations can be deduced from the training dataset. If there is only one compatible relation, this relation can be predicted without computing Concepts of Neighbours for this example, and if there are several possible relations, the set of (subject, object) couples from the training dataset that are annotated with compatible relation types can be used as the set of possible neighbours in the algorithm.

Scoring Methods

The computation of Concepts of Neighbours of a (subject, object) pair from the test dataset returns a set of concepts, each concept is associated to a set of neighbour couples, and to an extensional distance. In addition, the specialization presented in the previous section ensures that each neighbour couple is annotated with a compatible relation type. From this result, in order to be able to predict a relation, we need to associate a score to each relation type. In the following we present two scoring methods: one based on a weighted votation, and another based on the confidence measure.

Exponential-weighted Vote (EV). Each neighbour (s, o) of each concept "votes" for its annotated relation type r(s, o). However, if not weighted this method will only reflect the proportion of each relation among the training examples annotated with a compatible relation. To avoid this problem, the extensional distance dist(c) of concept c can be used to weight each vote. The extensional distance of a concept of neighbours measures the degree of similarity between the couple from which the concept has been computed and the neighbours that the concept contains: the lower the distance, the higher the similarity. Therefore, each vote is weighted by a decreasing function of the extensional distance. We We have chosen the inverse exponential function to define each weight w(c) because of its rapid decrease, which privileges nearest neighbours. This way, the relation of one very similar example is preferred to the relation of a large number of vaguely similar examples.

Maximum Confidence (MC).

The second method is similar to the method used by AnyBURL [START_REF] Meilicke | Anytime Bottom-Up Rule Learning for Knowledge Graph Completion[END_REF], and has been successfully used with Concepts of Neighbours for link prediction [START_REF] Ferré | Application of concepts of neighbours to knowledge graph completion[END_REF]. The idea is to consider the intension int(c) = (s, o) ← P c of each concept c, to use pattern P c as the body of a rule, and for each relation type r to compute the confidence of the rule R c,r : P c → r(s, o), defined as usual as:

conf (R c,r ) = |{(s, o) | r(s, o)} ∩ ext(c)| |ext(c)|
For each relation type r, the score is the list of the confidences of all rules R c,r predicting that relation, in descending order. score(r, C) := (conf (R c,r )) c∈C in descending order Such scores are ranked according to inverse lexicographic ordering. That is, the predicted relation type is the relation type with the higher maximal confidence. If several relation types have the same maximal confidence, the relation type with the higher second maximal confidence is predicted, and so on.

Experiments

In this section we present the experiments conducted on TACRED [START_REF] Zhang | Position-aware Attention and Supervised Data Improve Slot Filling[END_REF], a standard relation extraction benchmark, to evaluate the proposed method. The evaluation of an approach on TACRED is usually made using the microaveraged F1 score. However, as the negative examples have been removed from the dataset, this score is equivalent to accuracy. Therefore, accuracy is the measure we use in this evaluation.

The fact that experiments are made on a subset of TACRED causes that direct comparison with existing approaches is no longer possible. In order to evaluate whether our modeling and use of concepts of neighbours are beneficial, we introduce a simple baseline based on named entity types. It predicts the most frequent relation type among the training sentences that have the same subject type and the same object type as the test sentence.

Experimental Settings

As the algorithm to compute the Concepts of Neighbours is anytime, a timeout has to be chosen. In order to see the influence of the computation time on the classification task, eight experiments have been run with respective timeouts: 10, 20, 30, 60, 120, 300, 600 and 1200 seconds. For each timeout we compare four configurations combining unpruned/pruned modelings (Section 3.2) and the two scoring methods (Section 4.2).

We have implemented our approach in Java6 , and we use library Concep-tualKNN 7 for the computation of Concepts of Neighbours, which is based on Apache Jena8 , a Java library for semantic web applications. Experiments have been run on Grid50009 to exploit parallel computation.

Quantitative Results

Accuracy of the baseline and of the four versions of the proposed method are presented in Table 2. For a timeout of at least 60s, the proposed approach with the Maximum Confidence scoring and the pruned modeling, has a better accuracy than the baseline, surpassing it by 1.7 point with a timeout of 120s and by 2.2 points with a timeout of over 600s. It can be observed that the pruning of the dependency trees in the modeling is necessary in order to beat the baseline. We assume that, without pruning, the search space for concepts of neighbours gets much larger, and so their computation cannot focus on the useful parts of the dependency trees in the allocated timeout. The EV scoring method shows negative results compared to Maximum Confidence and the baseline. Two conclusions can be made. First, the exponential decrease of vote weights seems to neglect too much distant concepts as Maximum Confidence does not penalize them. Second, it seems better to select a few high-confidence concepts than trying to aggregate predictions from all concepts. Considering the last line of Table 2 (pruned and MC method), we observe a saturation phenomenon. Indeed, there is an important gain when timeout gets from 10s to 120s, but a far smaller gain from 120s to 1200s. Most of the concepts of neighbours are computed in less than 120 seconds, and over 120 seconds, only a few concepts are added. The same phenomenon is seen in Figure 5. The first chart clearly shows that most of the concepts are obtained in less than 120s. In addition, the second chart shows that, in the case of a model with pruned dependency trees, over 99% of the test sentences have a fully computed set of Concepts of Neighbours -and therefore the predictions are made on the Concepts of Neighbours themselves and not an approximation -for a timeout over 600s, while for a model with full dependency trees, only about 70% of the examples have fully computed set of Concepts of Neighbours. For illustration, we examine the following example: "Her husband, Brad Hagemo, is an optometrist and Scientologist". First, as the subject and the object (in bold) designate persons, there are six possible relations: per:spouse, per:siblings, per:parents, per:children, per:other_family and per:alternate_names. After computation of the Concepts of Neighbours, the relation per:spouse is predicted with Maximum Confidence. This prediction is based on the fact that three Concepts of Neighbours predict this relations with a confidence of 1, while at most two concepts predict any other relation with such a confidence. The graph pattern used as intension for these concepts can be made explicit. For example, the intension of one of these concepts is shown in Figure 6. It expresses that the subject is a person designated as a husband, and the object is a personal pronoun of lemma "she". This intension can effectively predict with quite a high confidence a marital relation. This example shows that, with this method, an interpretation can be extracted from a prediction. In addition, this shows that a prediction can be made with good confidence from concepts with a disjoint intension. In practice, we observed that concept intensions are rarely connected. A reason is that they may form patterns that are too specific to match any sentence of the training corpus.

Conclusion

We have presented a lazy-learning method for relation extraction, based on the modeling of linguistic data as a graph and on the computation of Concepts of Neighbours on this graph. This approach has been evaluated and validated against a baseline on the subset of positive examples of the TACRED benchmark. In addition, this comes with the adventage that this approach is interpretable as, for each prediction, detailed information about how this prediction has been made is given in the form of graph patterns over the linguistic structure.

Several aspects of this contribution lead to tracks for future work. First, this method could be coupled with another method -potentially Deep Learning -in order to be able to distinguish the positive examples from the negative ones. The Concepts of Neighbours method can also be improved in order to provide more flexible and expressive patterns, useful in the case of natural language processing. Finally, our approach could be adapted to other NLP tasks that require search for linguistic similarity.

Fig. 1 :

 1 Fig. 1: Example Graph-FCA context K = (O, A, I) describing part of the British royal family. Notation p({a, b}, {c, d}) stands for p(a, c), p(a, d), p(b, c), p(b, d).

  to graphs. A graph context K = (O, A, I) is a labeled and directed multi-hypergraph, where objects are nodes, attributes are edge labels, and incidence elements are edges (noted like atoms in predicate logic a(o 1 , . . . , o k )). As a running example, Figure 1 defines a small context describing (part of) the British royal family. Definition 1. A graph concept is defined as a pair C = (R, Q), where R is a set of k-tuples of objects and Q is a conjunctive query such that R = res(Q) is the set of results of Q, and Q = msq(R) is the most specific query that verifies R = res(Q). R is called the extension ext(C), and Q is called the intension int(C).

Fig. 2 :

 2 Fig. 2: Venn diagram of the extensions of the 6 Concepts of Neighbours of (Charlotte), labelled by their intension (right) and numerical distance (inside).

Fig. 3 :

 3 Fig. 3: Example of a sentence modeled as an RDF graph.

  use the following formula to score a relation type r based on a set of Concepts of Neighbours C. score(r, C) := c∈C (s,o)∈proper (c) w(c) 1 r(s,o)=r where w(c) = e -dist(c)

5. 1

 1 Dataset and Baseline TACRED is a dataset made of 106,264 annotated examples, split into a training corpus (68,124 examples), a development corpus (22,631 examples) and a test dataset (15,509 examples). Each example is a sentence with two identified entity mentions (a subject and an object), typed among 23 possible types (the types used by the Stanford NER system [12]), and annotated with a relation type among 41 effective classes and a no_relation class denoting an absence of relation between the two mentions. In order to reflect what can be found in real-world texts, 79.5% of the examples are in the no_relation class. Several remarks can be made about this dataset. First, as the classification with Concepts of Neighbours is a lazy learning method, there is no validation step, then the development dataset can be merged with the training dataset to form a bigger training dataset. Second, the negative examples (those in the no_relation class) have no reasons to look like each other but can look like examples in other classes, because they express random situations. Therefore, as our method looks for similarities between a test example and training examples, those negative examples cannot easily be handled in our method. That is why negative examples are removed from the dataset in the experiments, and we focus on discriminating between the 41 relation types rather than discriminating between the presence and absence of a relation. This shrinks the training corpus to 18,446 examples and the test corpus to 3,325 examples.

Fig. 5 :Fig. 6 :

 56 Fig. 5: Average number of concepts per example and proportion of fully computed sets of Concepts of Neighbours

  The training examples matching this intension are the sentences "Kissel had [...] accused her husband, Merrill Lynch investment banker Robert Kissel of [...] domestic violence." and "Jane Callahan Gude, 84, [...] a tireless campaigner for her husband, former U.S. Rep. Gilbert Gude, died March 24 [...]."

Table 1 :

 1 Example of a processed sentence.

	ID token	lemma POS	NER	head deprel
	1	The	the	DT	-	2	det
	2 University University NNP ORGANIZATION 6	nsubj
	3	of	of	IN ORGANIZATION 4	case
	4 Rennes	Rennes NNP ORGANIZATION 2	nmod
	5	is	be	VBZ	-	6	cop
	6	French	french	JJ NATIONALITY	-ROOT
	7	.	.	.	-	6	punct

Table 2 :

 2 Accuracy of our approach depending on timeout, pruning, and scoring method, compared to the baseline.

				Timeout (seconds)
	Approach	10	20	30	60	120	300	600 1200
	Baseline				80.4
	Unpruned, EV	78.6	79.1	79.2	79.4	79.2	79.2	79.6	79.6
	Unpruned, MC 78.0	78.2	78.3	78.9	79.9	79.8	80.2	80.4
	Pruned, EV	79.5	79.7	79.6	80.1	80.4	80.3	80.4	80.4
	Pruned, MC	79.1	80.1	80.3	81.3 82.1 82.5 82.6 82.5

https://www.wikidata.org/

We use the CoreNLP tool[START_REF] Manning | The Stanford CoreNLP Natural Language Processing Toolkit[END_REF] but other tools could be used.

We use the 58 POS tags of English Penn Treebank[START_REF] Toutanova | Feature-rich part-of-speech tagging with a cyclic dependency network[END_REF].

We use the dependency grammar proposed by Treebank Universal Dependencies.

Full hierarchy at https://gitlab.inria.fr/hayats/jena-conceptsofneighbours/ -/blob/master/src/conceptualKNN/utils/postag.ttl

Code available at https://gitlab.inria.fr/hayats/conceptualknn-relex

https://jena.apache.org/

https://www.grid5000.fr/w/Grid5000:Home


Z Wang

Y Zhang

A Bernard

A NOVEL KNOWLEDGE-BASED TOOLPATH CONSTRUCTIVE APPROACH FOR DESIGNING HIGH-PRECISION GRADED LATTICE STRUCTURES

Keywords: Tool-path, Constructive design, Triply periodic minimal surface, Knowledge-based system

Current part-scale lattice design methods cause accuracy loss and manufacturability uncertainty in AM preparation stages. STL model conversion and slicing can lead to loss of shape accuracy and surface quality, while unqualified toolpaths may cause printing failures, e.g. pores or re-melting in the powder-bed fusion process. Moreover, all these steps are time-consuming due to the large model file. To solve these challenges, this paper proposes a novel knowledge-based toolpath constructive design method to generate high-precision graded lattice unit cells with manufacturability. It integrates implicit modeling, variable distance field, direct slicing and fine toolpath configuration to construct qualified toolpaths without any intermediate steps. To save computation time in partscale lattice design, predefined different types or sizes of graded lattice unit cells are populated and assembled into a given design space directly. Hence, it has big potential to improve industrial application of part-scale porous structures with fine and gradient porous features.

Introduction

Additive manufacturing (AM) technologies have the potential to produce highly complex geometries and material compositions with a layer-by-layer printing strategy enabling to achieve a nonlinear relationship between the geometry complexity and manufacturing cost [START_REF] Thompson | Design for Additive Manufacturing: Trends, opportunities, considerations, and constraints[END_REF][START_REF] Lebaal | Optimised lattice structure configuration for additive manufacturing[END_REF][START_REF] Vaneker | Design for additive manufacturing: Framework and methodology[END_REF]. Since the layer construction method is totally different from conventional manufacturing processes, designers and engineers enable to use intricate structures, e.g. triply periodic minimal surface (TPMS), to have more freedom in product design, such as tissue engineering [START_REF] Yoo | Computer-aided porous scaffold design for tissue engineering using triply periodic minimal surfaces[END_REF] and heat sink [START_REF] Catchpole-Smith | Thermal conductivity of TPMS lattice structures manufactured via laser powder bed fusion[END_REF]. As AM technology becomes more mature, it is possible to fabricate metal parts with high-precision complex geometry and extremely fine features, especially using the laser powder bed fusion (L-PBF) process. However, high manufacturing precision also leads to more preparation time in AM processing chain. In addition, Boolean operations would cause a large computing time and data storing space while generating high-precision TPMS-based porous structures. In particular, with the increase of the CAD model size, these issues make fabrication of part-scale porous structures become more and more difficult.

To avoid the loss of accuracy and efficiency issues, this paper proposes a knowledge-based toolpath configuration method, where a set of toolpath patterns are pre-defined for different types and sizes of uniform or graded TPMS structures with ensured manufacturability. The proposed method can significantly simplify the conventional toolpath generation method without any solid-related representation. With an implicit modeling and distance field, different types of graded offset TPMS surfaces can be created directly. Different types of toolpath patterns are infilled within slice contours via directly slicing the offset surfaces. Taking into account the repeated appearance of samesize lattice unit cell, the lattice unit with the same gradient thickness information is defined and stored in a knowledge-based data set.

The remaining contents are organized as follows: the related work will be presented in Section 2; Section 3 will introduce the proposed method; Cased study in the section 4 will be given for method demonstration, and Section 5 ends with a conclusion and future research perspectives.

Related work

Lightweight TPMS lattice structures has gained attention due to the attractive internal intricate structures. Currently, the methods to print part-scale lattice or porous structures usually follow the traditional design and printing preparation method. At first, a CAD model or design domain filling with complex lattice unit cells is designed by conventional CAD tools. Then, the CAD model obtained is converted into a Stereo-lithography (STL) file that can be recognized by many AM machines' preparation software tools. In general, it will cause the loss of geometrical accuracy in the model manipulation and conversion. Then, the mesh file is processed by a preprocessing software to obtain a slicing model. It is also easy to lead to accuracy loss in the cross-sections from STL model to slicing model, especially for fine porous TPMS structures. In the end, different types of toolpath patterns are infilled within the layers of a slicing model. The infilling process usually causes additional accuracy loss when facing shapes with concave contours since toolpaths at those locations may have overlaps or voids. Hence, the generated toolpaths should be validated before printing in real manufacturing context. Currently, the preparation process in traditional AM processing chain can be summarized as CAD model building, STL file conversion, and toolpath infill before printing. These three stages will not only cause the loss of geometrical accuracy, but also consume much computational time and memory for part-scale porous structure design. Moreover, it becomes worse when using intricate TPMS structures to infill within the part-scale lattice structures. Fig. 1 shows the main steps for designing graded TPMS structures. In literature, many studies were proposed to improve the efficiency and precision issues of partscale lattice structure designs. To avoid slicing the solid TPMS model, Feng et al. [START_REF] Feng | Layered infill area generation from triply periodic minimal surfaces for additive manufacturing[END_REF] proposed to use the Marching Square (MS) algorithm to slice open-surface TPMS structures directly. Then, based on the uniform thickness information, a bidirectional-offset-union strategy was developed to generate valid toolpath infill. However, it is still costly to deal with part-scale lattice design issues using the solid-free method. In addition, the proposed method can only construct TPMS structure with uniform thickness. Another STL-free design method was proposed by Ding et al. [START_REF] Ding | STL-free design and manufacturing paradigm for high-precision powder bed fusion[END_REF]. Implicit solid modeling and direct slicing method are used to construct toolpath configuration. Hence, it can ensure a high-precision toolpath infill for the powder bed fusion process when fabricating multi-level TPMS structures. However, the STL-free method has difficulty handling complex graded TPMS structures. In addition, the cost of slicing and toolpath generation was omitted in the implicit method. The toolpath configuration is still conducted for the whole part model. Ponche et al. [START_REF] Ponche | A novel methodology of design for Additive Manufacturing applied to Additive Laser Manufacturing process[END_REF] proposed a novel methodology of design for AM to optimize the part geometry from toolpath directly. Hence, it provided a new horizon to bridge the gap between CAD model and the corresponding manufactured part. Inspired by the pioneering work [START_REF] Ponche | A novel methodology of design for Additive Manufacturing applied to Additive Laser Manufacturing process[END_REF], a new toolpath-based layer construction method is proposed to design micro-scale porous structures in [START_REF] Zhang | A toolpath-based layer construction method for designing & printing porous structure[END_REF]. The proposed method can save time in design and printing preparation with ensured manufacturability. The toolpath is defined implicitly and the travel path is also optimized to guide the laser trajectory.

To summarize, current TPMS-based lattice design methods have the following problems: a. it is difficult to improve computational efficiency when dealing with part-scale lattice structures. b. it is hard to ensure the accuracy while designing graded TPMS structures. To solve these problems, the manuscript attempts to propose a new knowledge-based toolpath constructive solution.

Proposed method

Method overview

Different from the traditional CAD-STL-Slice-Toolpath modeling, the proposed method uses solid-free modeling method to generate toolpath configuration directly. Fig. 2 shows the proposed knowledge-based toolpath configuration method for designing graded TPMS-based porous structures. The proposed method has three modules to manage the toolpath configuration. First, a given design domain is decomposed into voxels based on certain requirements, e.g. manufacturing constraints or functional requirements, as shown in Fig. 3. Here, we suppose that all voxels have the same size and are filled with the same type of lattice unit cell. In this process, the fabrication sequence can be also defined to facilitate the toolpath configuration for voxels in different positions. Then, according to the graded thickness, unique voxels with different graded thickness information are selected to serve for graded offset surfaces generation. In the module of the knowledge data for unit cells' toolpath configuration, an implicit function is used to create 0-level iso-surface via the Marching Cubes (MC) algorithm [START_REF] Lorensen | Marching cubes: A high resolution 3D surface construction algorithm[END_REF]. According to thickness information of different voxels, offset surfaces are built by using different distance field functions. Then, toolpaths are populated into the area between two offset surfaces directly. Moreover, different types of toolpath patterns are utilized to infill the slice contours. At the same time, the travel path can be also defined in the toolpath configuration. Finally, these toolpath configuration units are as infilling templates, filling knowledge units, which can be selected to infill the voxels.

In the third module, the toolpath information stored in the templates is selected to populate for reproduction into the voxels ( ijk a ) of different positions. In addition, the scanning sequence and path of multiple lasers can also be assembled into the output file of final toolpath configuration. By using the proposed knowledge-based toolpath configuration method, computational time and memory can be saved significantly.

TPMS structure generation

The implicit method uses a single-value function of three variables to describe approximated TPMS with periodic surfaces [START_REF] Rajagopalan | Schwarz meets Schwann: design and fabrication of biomorphic and durataxic tissue engineering scaffolds[END_REF]. Three common TPMS structures, Schwarz Primitive, Diamond and Schoen Gyroid surfaces can be expressed by the following nodal equations: ( , , ) cos( ) cos( ) cos( ) ( , , ) cos( ) cos( ) sin( )sin( ) ( , , ) cos( )sin( ) cos( )sin( ) cos( )sin( )

P D G x y z x y z C x y z x y z x y z C x y z x y y z z x C                                (1)
Where x, y, z are the spatial coordinates, and L is the size of the lattice unit cell, C can control the surface expansion. The surface Γ, a zero-level set of Φ, represents the interface regions which divide the unit cell into two distinct spaces. Fig. 4 shows the three TPMS structures accomplished with the polygonization of Γ by using the MC algorithm. Schoen Gyroid surface.

In order to explain the 3D MC algorithm, the MS algorithm in 2D is illustrated in Fig. 5. The MS algorithm is used to provide a piecewise-line approximation to a 2D object [START_REF] Maple | Geometric design and space planning using the marching squares and marching cube algorithms[END_REF]. To describe an implicit function, the design domain is divided into a 2D grid. Each nodes of the grid can be calculated by the implicit function.

 

nodes inside and outside of the 0-iso-line, respectively. The linear interpolation method is usually applied to draw the lines. Take the square in Fig. 5(b) as an example, four nodes satisfy

1 2 3 4
( ) 0, ( ) 0, ( ) 0, ( ) 0

f p f p f p f p     with ()
fp being the value of the implicit function on each node. To extract the line from the square, valid grid edges need to be detected. For a valid edge, the grid nodes i p and 1 i p  should satisfy the following:

1 ( ) ( ) 0 ii f p f p   (2)
Hence, two valid edges in Fig. 5(b) are 12 pp and 23 pp. The intersection P can be calculated via the linear interpolation approach as 1 (( 1)

)

0 ii f p p      (3)
Based on the intersection situations of the MS algorithm, the connection of all intersection P can be determined to construct an approximate 0-iso-line. The resolution of the grid can be improved to obtain a high-precision 0-iso-line.

Graded offset TPMS generation

In this subsection, a MC-based distance field method is proposed to generate graded TPMS offset surfaces. In the proposed method, the 0-iso-level surface ( H ) can be obtained using the MC algo- rithm. Actually, the surface H is a mesh surface that can be controlled by the resolution of the MC algorithm. Then, the closest distance between uniform points P from the MC algorithm and the surface H can be represented as ( , )

dis p H  , and the corresponding closet points on the surface are described as H P . Since we have an implicit graded thickness function G T , the thickness values in H P can be represented as PH T . Hence, the distance field for the point set P can be described as ( ) ( , )

PH f p dis P H T   
. The distance field will be used as an input of the MC algorithm to obtain the graded TPMS surface. Fig. 6 shows the flowchart.

An implicit cylinder example ( 22 90

xy    ) is used to explain the method in Fig. 7. For grid points with iso-surface values greater than zero, these points lie outside of the circle. All those with negative values lie inside of it. In order to generate an offset surface, a distance field is used to measure the distance between grid points and the mesh surface. The distance field can be described by the following equation [START_REF] Liu | Fast intersection-free offset surface generation from freeform models with triangular meshes[END_REF]:

( ) ( , ) f p dis p H r    (4)
Where p are the grid points and H is the given cylinder generated by the MC algorithm. The distance field represents the minimum distance from these grids to the given model. For these points outside H, the function will return the distance with positive. The distance values are seen as negative for these points inside. Hence, the offset value r can be either negative or positive. To explain it easily, Fig. 8 show the generation of the inside and outside offset cylinder in 2D. To generate an offset cycle, an offset value is needed to calculate the distance field. Here, the offset value is set as 1 r  . The distance field is computed to return the MC algorithm. Two offset circles in 2D are shown in Fig. 8. The distance field function can also be used to generate a graded offset surface by describing a thickness field based on geometry information. For example, a distance field of deformed circles can be expressed as: ( ) ( , ) ( 1) 6

x i i p f p dis p H     (5)
Where x i p is the x-axis coordinate of point i p . Fig. 9 shows two graded offset circles via a graded thickness filed. Hence, the proposed method can be also applied to generate offset TPMS surfaces. By adjusting the resolution of the MC algorithm, the precision of graded offset surfaces can be controlled. To describe the impact of resolution, a sphere is represented using the MC algorithm. The mathematical expression is defined by:

2 2 2 () f S x y z R     (6)
Where ,, x y z are the spatial coordinates and R represents the radius of the sphere. The radius is defined as 3 mm. Fig. 10 shows different spheres with different resolutions.

I I O O V F V F     ); (c).
resolution = 40 ( 5052, 9856; 5340, 10000

I I O O V F V F     ); (d
I I O O V F V F     ).
In addition, due to the high manufacturing accuracy of the SLM process, the surface precision of fine TPMS lattice structures is required to be smoother. The proposed method can ensure the TPMS lattice structure model with a high-precision surface accuracy via a high resolution setting. Fig. 11 compares the effect of different resolutions on the sizes of STL files. As the resolution of STL files increases, the number of faces and vertices of the triangular mesh increases exponentially. In general, high-precision STL files lead to an increase in pre-processing time and a large consumption of computational memory.

Toolpath infill for graded offset surfaces

As mentioned above, the MC-based distance field can construct offset surfaces with different gradients for a TPMS unit cell. A solid-free toolpath configuration method is developed in this subsection. The proposed method allows us to slice offset surfaces directly. Meanwhile, to avoid time consumption in AM preparation stages, the toolpath result obtained is stored in a knowledge base for the subsequent toolpath configuration. Fig. 12 give a workflow of the toolpath configuration generation method for a graded TPMS-based unit cell example. The distance between two adjacent slice planes should respect the layer thickness. Two kinds of intersection polylines, called outside and inside offset polylines, are obtained to split the bounding surface in Fig. 12(c,d). The surface enclosed by the two intersection polylines is the slicing contour. Different types of toolpaths can be used to populate within the slicing contour. For the L-PBF process, there are generally two types of scans: contour and infill. The contour scan is usually used to scan the boundaries and the infill scan is used to scan across all areas. The zigzag scan is one of the most common infill scanning strategy in the literature. The scanning strategy plays an important role in microstructures, mechanical properties, and residual stresses of AM parts [START_REF] Jia | Scanning strategy in selective laser melting (SLM): a review[END_REF]. To form the large-size parts with high quality, the island scanning strategy is seen as an alternative method to avoid excessive and accumulated stress [START_REF] Jia | Scanning strategy in selective laser melting (SLM): a review[END_REF]. Since the proposed method enables to manipulate toolpaths directly, contour and zigzag scanning strategies are used to construct toolpath knowledge bases. To ensure the manufacturability of the contour toolpath, the MS algorithm is used to generate intersection-free contours [START_REF] Liu | Fast intersection-free offset surface generation from freeform models with triangular meshes[END_REF]. The detailed method can be seen in Fig. 8. Notice that resolution should respect the following expression to ensure the qualified intersection-free contour generation in Fig. 13.

2 d Ln  ( 7
)
Where L is the size of the voxel, n represents the resolution of the MS algorithm, and d is the hatch spacing of an AM processing. In Fig. 12(f), a contour pattern is used to scan the boundary of the slice contour and parallel-vector toolpath is filled within the contour pattern. This combined toolpath configuration is more suitable for the island scanning technique. In addition, the zigzag scanning strategy can be used alone. In this situation, adjacent zigzags in different voxels can be joined together as shown in Fig. 14.

Taking into account that many part-scale lightweight structures with TPMS sheet usually use the same type and size lattice unit cell, the toolpath configuration for a single TPMS lattice unit cell can be seen as a knowledge data set, parametric template, stored in a knowledge-based system. Therefore, a set of toolpath configurations for graded TPMS unit cells can be predefined and stored in a knowledge base. It means that the proposed knowledge-based toolpath configuration method allows us to populate predefined toolpath configuration into voxels directly and generate 3D toolpath model to approaching the desired CAD model in an implicit way, which is similar to the proposed toolpath construction method in [START_REF] Zhang | A toolpath-based layer construction method for designing & printing porous structure[END_REF]. To achieve different kinds of scanning strategies, the infilled toolpaths can be analyzed further. In addition, the proposed method can ensure the manufacturability of high-precision toolpaths given a high resolution for the MC and MS algorithms since qualified toolpath patterns for infilling can be predefined in the knowledge base.

Case study

In this section, two types of TPMS unit cells, Schwarz P surface and OCTO surface are used to generate toolpath configurations directly for implicitly designing graded high-precision TPMS structures. Table 1 gives a process parameter definition.

           (8)
Where z t is the thickness of the graded surface along z direction, z p is the coordinate value of points on the standard Schwarz P surface. The MC algorithm is used to generate the standard P surface with the 150 150 150  resolution. Fig. 15 shows the three kinds of P surfaces and their combination. Two parallel-vector scanning strategies, island and continuous strategies, are applied to construct toolpath configurations for the graded P structure. Fig. 16 presents the two parallel-vector techniques with island and non-island scanning modes. A 90 rotation with x axis in scan orientation is performed after each layer. For the island scanning mode, unjoined toolpath configurations are filled within the voxel directly. For the parallel-vector technique, the toolpaths of mutual contact between two adjacent voxels are joined together, as shown in the right of Fig. 16. In addition, the contour scan is also performed in the toolpath configuration. Fig. 17 presents the toolpath in the layer 24 and 25. A 67 rotation with initial angle 45 is conducted in this scanning mode. Another graded thickness function is utilized in the OCTO surface as follows: Three scanning strategies, island with parallel-vector, parallel-vector and island with combined scans are used to generate toolpath configurations for each graded TPMS unit cells. The three strategies are shown in Fig. 18. Here, we use the island scanning strategy with contour and parallel-vector modes to construct toolpath configurations for the two graded TPMS structures as shown in Fig. 19. To assemble a final toolpath configuration of a part-scale graded structure, Fig. 20 shows a graded toolpath configuration assembly along z direction.

Conclusion and future research perspectives

The proposed knowledge-based toolpath constructive method can design graded TPMS structures more efficiently with qualified toolpaths and robust manufacturability. It has more potential to become a new digital framework for design complex uniform or graded porous structures with greatly reduced geometric modeling time and printing preparation time and improve printing accuracy since there is neither CAD modeling nor meshing where accuracy loss happens. In the future, the proposed knowledge-based method will be validated for the L-PBF process to fabricate fine porous gradient structures that are needed in diverse applications. Then, more TPMS structures and toolpath patterns will be benchmarked in experiments to help construct qualified toolpath pattern knowledge bases for configuration design. Moreover, the authors would like to exploit more applications in multi-material and 4D printing designs, where direct writing methods, which are convenient for defining toolpath construction rules, are widely used.

Fig. 1 .

 1 Fig. 1. Traditional toolpath generation method for graded TPMS-based porous structures.

Fig. 2 .

 2 Fig. 2. Flowchart of the proposed knowledge-based toolpath configuration method for designing graded TPMS-based porous structures.

Fig. 3 .

 3 Fig. 3. Voxel decomposition process: (a). Voxel representation in a three-dimensional matrix; (b). A two-dimensional matrix; (c). A voxel ijk a .

Fig. 4 .

 4 Fig. 4. Different types of TPMS structures (3*3): (a). Schwarz Primitive surface; (b). Schwarz Diamond surface; (c).Schoen Gyroid surface.

  Fig. 5(a) enumerates all 16 intersection situations, which show the representations of all lines in the 2D space. Hollow and solid points indicate the position of the grid 2 L

Fig. 5 .

 5 Fig. 5. (a). All configurations of the MS algorithm; (b). The linear interpolation method for a square.

Fig. 6 .

 6 Fig. 6. The flowchart of the graded TPMS surface generation method.

Fig. 7 .

 7 Fig. 7. An implicit cylinder generation using Marching Cubes algorithm in 2D.

Fig. 8 .

 8 Fig. 8. The representation of the inside and outside offset circles.

Fig. 9 .

 9 Fig. 9. Graded offset circles generation.

Fig. 10 .

 10 Fig. 10. Different spheres with different resolution setting: (a). resolution = 3; (b): resolution = 5; (c). resolution = 10; (d). resolution = 20.

Fig. 12 .

 12 Fig. 12. Workflow of toolpath configuration generation for a graded TPMS-based unit cell example.

Fig. 13 .

 13 Fig. 13. Resolution definition of intersection-free contour based on the hatch spacing.

Fig. 14 .

 14 Fig. 14. Adjacent joined zigzags in different voxels.

Fig. 15 .

 15 Fig. 15. Graded offset P surface generation: (a). standard P surface; (b). inside offset surface; (c). outside offset surface; (d). front view of the three surfaces; (e). perspective view.

Fig. 16 .

 16 Fig. 16. Two parallel-vector scan strategies of the alternative layers

Fig. 17 .

 17 Fig. 17. Contour and parallel-vector scanning modes in two layers.

Fig. 18 .

 18 Fig. 18. Three scanning strategies with 90 related to x-axis.

Fig. 19 .

 19 Fig. 19. Two toolpath configurations for graded P and OCTO structure unit cells.

Fig. 20 .

 20 Fig. 20. A graded toolpath configuration assembly along z direction: (a). graded offset surfaces; (b). graded toolpath configurations of unique voxels; (c). front view of the toolpath assembly; (d). perspective view of the assembly.

Table 1 .

 1 Process parameter definition

	Voxel size L (mm) Layer thickness t (μm) Hatch spacing d (μm)
	2*2*2	40	50
	To generate a graded Schwarz P structure, a graded thickness function is proposed in the following:
	( zz 1) 1 2sin 1 , ( 1 10 4 P z p tp	1)