Manoj Tyagi

Aurélie Bornot

Bernard Offmann

Dr Alexandre G De Brevern
email: alexandre.debrevern@univ-paris-diderot.fr

Protein short loop prediction in terms of a structural alphabet

Keywords: local protein structure, protein loops, secondary structure, protein function, bioinformatics, biophysics

Loops connect regular secondary structures. In many instances, they are known to play crucial biological roles. To bypass the limitation of secondary structure description, we previously defined a structural alphabet composed of 16 structural prototypes, called Protein Blocks (PBs). It leads to an accurate description of every region of 3D protein backbones and have been used in local structure prediction.

In the present study, we used our structural alphabet to predict the loops connecting two repetitive structures. Thus, we showed the interest to take into account the flanking regions, leading to prediction rate improvement up to 19.8%, but we also underline the sensitivity of such an approach. This research can be used to propose different structures for the loops and to probe and sample their flexibility. It is a useful tool for ab initio loop prediction and leads to insights to flexible docking approach.

Introduction

The knowledge of the three-dimensional (3D) structures of proteins contributes to understand their biological functions. Protein 3D structures are often described as a succession of repetitive secondary structures (mainly α-helices and β-sheets (Pauling and Corey, 1951;Pauling et al., 1951)). This mono-dimensional description helps to simplify coarsely this 3D information.

Nevertheless, the secondary structures description focuses only on two kinds of regular local structures that compose only a part of protein backbone. The remaining residues are only assigned if they can be associated with some particular structures such as the β-turns [START_REF] Bornot | Protein beta-turn assignments[END_REF][START_REF] Wang | Prediction of pi-turns in proteins using PSI-BLAST profiles and secondary structure information[END_REF]. It has led some scientific teams to develop local protein structure libraries that (i) are able to approximate all (or almost all) the local protein structures and (ii) do not make use of the classical secondary structures assignments. These libraries lead to the categorization of 3D structures without any a priori into small prototypes that are specific to local folds found in proteins. The complete set of local structure prototypes defines a structural alphabet [START_REF] Karchin | Hidden Markov models that use predicted local structure for fold recognition: alphabets of backbone geometry[END_REF][START_REF] Offmann | Local Protein Structures[END_REF]. The number of libraries or structural alphabet is important, e.g. [START_REF] Martin | In silico local structure approach: a case study on outer membrane proteins[END_REF][START_REF] Sander | Local protein structure prediction using discriminative models[END_REF][START_REF] Tung | Kappa-alpha plot derived structural alphabet and BLOSUM-like substitution matrix for rapid search of protein structure database[END_REF].

Our structural alphabet is composed of 16 mean protein fragments of 5 residues in length, called Protein Blocks (PBs, see Figure 1) [START_REF] De Brevern | Bayesian probabilistic approach for predicting backbone structures in terms of protein blocks[END_REF]. They have been used both to describe the 3D protein backbones [START_REF] De Brevern | New assessment of a structural alphabet[END_REF] and to perform a local structure prediction [START_REF] De Brevern | Bayesian probabilistic approach for predicting backbone structures in terms of protein blocks[END_REF][START_REF] De Brevern | Local backbone structure prediction of proteins[END_REF][START_REF] Dong | Prediction of protein local structures and folding fragments based on building-block library[END_REF][START_REF] Etchebest | A structural alphabet for local protein structures: improved prediction methods[END_REF][START_REF] Zimmermann | LOCUSTRA: accurate prediction of local protein structure using a two-layer support vector machine approach[END_REF]. PBs have proven their efficiency in the description and the prediction of long fragments [START_REF] Benros | Analyzing the sequence-structure relationship of a library of local structural prototypes[END_REF][START_REF] Benros | Assessing a novel approach for predicting local 3D protein structures from sequence[END_REF][START_REF] Bornot | A new prediction strategy for long local protein structures using an original description[END_REF][START_REF] De Brevern | Hybrid protein model' for optimally defining 3D protein structure fragments[END_REF][START_REF] De Brevern | Extension of a local backbone description using a structural alphabet: a new approach to the sequence-structure relationship[END_REF][START_REF] De Brevern | Pinning strategy": a novel approach for predicting the backbone structure in terms of protein blocks from sequence[END_REF], to compare protein structures [START_REF] Tyagi | Protein structure mining using a structural alphabet[END_REF]Tyagi et al., 2006a;Tyagi et al., 2006b), to build globular [START_REF] Dong | Methods for optimizing the structure alphabet sequences of proteins[END_REF] and transmembrane protein structures [START_REF] De Brevern | New opportunities to fight against infectious diseases and to identify pertinent drug targets with novel methodologies[END_REF]de Brevern et al., 2009;de Brevern et al., 2005), to define a reduced amino acid alphabet dedicated to mutation design [START_REF] Etchebest | A reduced amino acid alphabet for understanding and designing protein adaptation to mutation[END_REF], to design peptides [START_REF] Thomas | Prediction of peptide structure: how far are we?[END_REF], to define binding site signatures [START_REF] Dudev | Discovering structural motifs using a structural alphabet: application to magnesiumbinding sites[END_REF] or to analyze protein contacts [START_REF] Faure | Analysis of protein contacts into Protein Units[END_REF]. The features of this alphabet have been compared with those of 8 other structural alphabets showing clearly that our PB alphabet is highly informative, with the best predictive ability of those tested [START_REF] Karchin | Hidden Markov models that use predicted local structure for fold recognition: alphabets of backbone geometry[END_REF].

In this paper, we focus on the prediction of short loops from sequence. Loop prediction is one of the major drawbacks of homology modeling methods even if loops play crucial biological role. Loop prediction is frequently performed after the positioning of repetitive secondary structures. Current protocols are based on the sampling of the conformational space of the loop fragment and the scoring of the corresponding sampled conformations, but do not perform well for loops more than 10 residues [START_REF] Zhu | Long loop prediction using the protein local optimization program[END_REF].

Prediction using a structural alphabet is an efficient way to predict loop structures. Indeed, as the PBs are overlapping and more precise than secondary structure, a small modification of PB series has a fewer consequence in comparison to a change observed in secondary structure assignment. Moreover, PBs are successful to align structural homologues even in difficult case with very divergent loops [START_REF] Tyagi | Protein structure mining using a structural alphabet[END_REF]Tyagi et al., 2006a).

Following a previous research [START_REF] Fourrier | Use of a structural alphabet for analysis of short loops connecting repetitive structures[END_REF], we described short loops that connect two repetitive structures using our structural alphabet, and performed local loop structure predictions from the amino acid sequence. In this study we assessed the importance of a priori knowledge of the flanking regions and of sequence identity of the protein databank on the loop prediction.

Methods

Data sets. 10 non-redundant protein databanks have been used in this study. They are based on the PISCES database [START_REF] Wang | PISCES: recent improvements to a PDB sequence culling server[END_REF] and represents between 162,830 (namely DB0) and 1,572,412 residues (namely DB8, see supplementary data I). They are available at http://www.dsimb.inserm.fr/~debrevern/DOWN/DB/new. The sets are defined as containing no more than x% pairwise sequence identity with x ranging from 20 to 90%. The selected chains have X-ray crystallographic resolutions less than 1.6 Å with an R-factor less than 0.25 or less than 2.5 Å with an R-factor less than 1.0. Each chain was carefully examined with geometric criteria to avoid bias from zones with missing density [START_REF] Tyagi | Analysis of loop boundaries using different local structure assignment methods[END_REF].

Protein Blocks & short loop description. Protein Blocks (PBs) correspond to a set of 16 local prototypes, labeled from a to p (cf. Figure 1), of 5 residues length based on Φ, Ψ dihedral angles description. They were obtained by an unsupervised classifier similar to Kohonen Maps [START_REF] Kohonen | Self-organized formation of topologically correct feature maps[END_REF] and Hidden Markov Models [START_REF] Rabiner | A tutorial on hidden Markov models and selected application in speech recognition[END_REF]. The PBs m and d can be roughly described as prototypes for central α-helix and central β-strand, respectively. PBs a through c primarily represent β-strand N-caps and PBs e and f, C-caps; PBs g through j are specific to coils, PBs k and l to α-helix N-caps, and PBs n through p to Ccaps. This structural alphabet allows a reasonable approximation of local protein 3D structures [START_REF] De Brevern | Bayesian probabilistic approach for predicting backbone structures in terms of protein blocks[END_REF] with a root mean square deviation (rmsd) now evaluated at 0.42 Å (de Brevern, 2005). PBs (de Brevern, 2005) have been assigned using in-house software (available at http://www.dsimb.inserm.fr/DOWN/LECT/), it follows similar rules to assignment done by PBE web server (http://bioinformatics.univ-reunion.fr/PBE/) (Tyagi et al., 2006b). We have defined the short loops as PB series of length 2 to 6. They represent the most frequent loop lengths. These series must be composed of non-repetitive PBs, i.e. all the PBs except PBs d and m. They must have flanking regions composed of series of PBs mm and / or dd [START_REF] Fourrier | Use of a structural alphabet for analysis of short loops connecting repetitive structures[END_REF].

Prediction. In a strategy of structure prediction from sequence [START_REF] De Brevern | Bayesian probabilistic approach for predicting backbone structures in terms of protein blocks[END_REF][START_REF] De Brevern | Local backbone structure prediction of proteins[END_REF][START_REF] Etchebest | A structural alphabet for local protein structures: improved prediction methods[END_REF], we must compute for a given sequence window S aa = {aa -w , …, aa 0 , …, aa +w }, the probability of observing a given protein block PB x , i.e. P(PB x | S aa ). For this purpose, each PB is associated with an occurrence matrix of dimension l x 20 centered upon the PB, with l = 2 w +1 (in the study, w =7). Using the Bayes theorem to compute this a posteriori probability P(PB x | S aa ) from the a priori probability P(S aa | PB x ) deduced from the occurrence matrix allows us to define the odds score R x :

( ) ( ) ∏ + = - = = = = w j w j j x j x DB i aa P PB i aa P R
The highest score R x corresponds to the most probable PB [START_REF] De Brevern | Bayesian probabilistic approach for predicting backbone structures in terms of protein blocks[END_REF][START_REF] De Brevern | Extension of a local backbone description using a structural alphabet: a new approach to the sequence-structure relationship[END_REF][START_REF] De Brevern | Pinning strategy": a novel approach for predicting the backbone structure in terms of protein blocks from sequence[END_REF][START_REF] De Brevern | Local backbone structure prediction of proteins[END_REF][START_REF] Etchebest | A structural alphabet for local protein structures: improved prediction methods[END_REF][START_REF] Fourrier | Use of a structural alphabet for analysis of short loops connecting repetitive structures[END_REF]. The Q 16 value computed is the total number of true predicted PBs over the total number of predicted PBs. We also computed a Q 14 value, specific for loops, i.e. the PB m and d are not taken into account in the accuracy rate computation [START_REF] Fourrier | Use of a structural alphabet for analysis of short loops connecting repetitive structures[END_REF].

Thus different predictions have been done: (i) one general prediction done for comparison purpose, it gives the Q 16 and Q 14 values, (ii) a specific prediction of only short loops, it gives a Q 14 short values and (iii) specific prediction of only short loops α-α, α-β, βα and β-β, it gives a Q 14 short values for each kinds of short loops.

Results & Discussion

Prediction of structural alphabets could be strongly dependant of the selection of the training and validation set [START_REF] Etchebest | A structural alphabet for local protein structures: improved prediction methods[END_REF]. This feature is amplified in the case when the letters of the structural alphabets have low frequency, e.g. π-helix [START_REF] Wang | Prediction of pi-turns in proteins using PSI-BLAST profiles and secondary structure information[END_REF], type VI β-turns [START_REF] Fuchs | High accuracy prediction of beta-turns and their types using propensities and multiple alignments[END_REF] or PB b [START_REF] De Brevern | New assessment of a structural alphabet[END_REF]. Specific learning and validation were performed (i) for all the PBs (for comparison purpose), (ii) a specific research focusing on all the protein loops, and finally (iii) for each kinds of loops, i.e. α-α, α-β, β-α and β-β. Protein databanks have been split randomly into 2/3 of the proteins used for the training step and 1/3 for the validation step. We have done large number of independent simulations for optimizing the prediction rates, i.e. for each simulation the proteins used for the training and the validation sets are different.

Global prediction rates. Figure 1 shows 1000 independent simulations performed with the databank DB0 (887 protein chains, see supplementary material I). This Figure shows the importance of sampling. The difference between average and best prediction values is 1% for the prediction rate Q 16 and increases with the diminution of the databank, e.g. this difference equals 8% for the prediction of short loops connecting α-helix to β-strand. The best prediction rates for each of the PBs have been summarized in Table 1. These results highlight the interest to perform specific prediction for each kind of short loops; a specific learning with the a priori knowledge of the flanking regions improves the prediction rate. Nonetheless, this improvement is not uniform for all the short loop kinds.

From a correct Q 16 value of 35.8%, a prediction specific to loops, i.e. Q 14 , reaches 37.5% (+1.7%), and to 43.2% (+5.7%), if only the short loops are used. An increase ranging from 0.7% to 19.0% was observed for the 4 types of short loops.

We thus confirm our previous results, but also underline the importance of shuffling the proteins between validation and learning set (as we have also shown in [START_REF] Etchebest | A structural alphabet for local protein structures: improved prediction methods[END_REF]). It allows to improve all the prediction rates in comparison to [START_REF] Fourrier | Use of a structural alphabet for analysis of short loops connecting repetitive structures[END_REF], the quality of prediction, with only limited effect on β to α short loops, but near 20% of gain for α to α short loops. The use of numerous non-redundant databanks show: (i) global prediction rates remain equivalent for all the protein databank used, with no influence of the sequence identity or quality of crystallographic resolution and (ii) the importance of overtraining, this last diminished greatly with the increase of the protein databank size.

Though sometimes the prediction rates of each PB could vary a little, most of the time it is less than 5%. We can notice that four PBs are associated with more variation of their prediction rates, interestingly their frequencies in the most redundant databanks are decreased in regards to the lower redundant databanks. Thus, a slight statistical bias is observed.

In this field, prediction of loops using a structural alphabet is an interesting tool. Instead of describing entire loops; our approach predicts each position in the loops locally. To take into account the flanking regions of the loops greatly improve the prediction rates. As nearly all protein fragments can be can be observed in the Protein DataBank [START_REF] Balamurugan | SSEP-2.0: Secondary Structural Elements of Proteins[END_REF][START_REF] Balamurugan | SMS: sequence, motif and structure--a database on the structural rigidity of peptide fragments in non-redundant proteins[END_REF][START_REF] Du | Have we seen all structures corresponding to short protein fragments in the Protein Data Bank? An update[END_REF], this approach can be used to propose many different structures for the loops and to probe and sample their flexibility, and, is a useful tool in ab initio loop prediction. ), to the short loops connecting α-helix to α-helix (αα), α-helix to β-strand (αβ), β-strand to α-helix (βα) and β-strand to α-helix (ββ). The grey dots correspond to the 1000 independent simulation prediction rates, the blue dots to the average prediction value of the prediction rates and the red ones to the best prediction rates. with the corresponding frequencies (freq) for a classical prediction (complete db), only for the loops (Loops), for the short loops (Short Loops) and dedicated for every kind of short loops (α-helix to α-helix, α-helix to β-strand, β-strand to α-helix and β-strand to β-strand). The last line corresponds to the global prediction rate Q 16 for prediction of all residues and Q 14 only for short loops. Results are based on DB0.

FiguresFigure 1 -

 1 Figures

Figure 2 -

 2 Figure 2 -Distribution of prediction rates. Are given the prediction rate for the classical prediction (Q 16 ), a prediction dedicated to the loops (Q 14 ), to the short loops (Q 14 short loops

Table 1 -

 1 The different PBs' predictions. Are given the prediction rates by PBs (pred)

Acknowledgements

This work was supported by grants from the Ministère de la Recherche, Université Paris Diderot -Paris 7, Université de Saint-Denis de la Réunion and the French Institute for Health and Medical Care (INSERM). MT had a grant from the Conseil Régional de Réunion and AB has a grant from Ministère de la Recherche.

thus Q 16 goes from 35.2 to 35.8% and the corresponding Q 14 from 36.0 to 37.4% highlighting the quality of prediction, i.e. this improvement is not due only to PBs m and d, the repetitive PBs. In the same way, Q 14 for the short loops also increases from Q 14 = 42.3 to 43.2%. For the 4 types of short loops, the difference between average and best prediction rates bypasses 5% in all the cases. This global improvement is also associated with an increase of the over -training, i.e. a prediction largely better with the learning set than with the validation set. For the prediction of all residues, the over -training rate is less than 1% on average; it increases to 4% for the short loops and increases again for the short loop types, this value can reach 20% and more.

Nevertheless, a strong linear correlation exists (r > 0.95) between the prediction rate and the over-training. The better is the prediction rate, the lower is the over -training. Thus interestingly, the selected predictions are associated with the lower over -training rates.

These values represent only a compatibility between (2D') representation, i.e. true PBs and predicted PBs. So, we also assessed the quality of local structure approximation using C α root mean square deviation (rmsd) measure. We superimposed all the true PBs to the local protein structure, even the good PB, in order to compute the expected rmsd random values and we found they are always between 1.95 and 2.00 Å. The percentage of predicted PBs better than random value corresponds to 64% and 66% for the loops and short loops prediction respectively. These values increase with the specialisation of short loops with prediction rates equal to 68% for β-α, 74% for β-β, 76% for α-α and 82% for α-β.

PBs prediction rates. Improvements of prediction rates for the short loops are due to different PBs. For the all short loops, only two PBs clearly lost prediction rate, i.e. PBs j and l. The most frequent PBs have often very good prediction rate. For the α-α short loops, only two PBs present a decreased prediction rate (PBs a and h), for α-β, 5 (PBs f, h, i, k and l), for Protein short loops prediction β-α 5 (PBs a, c, h, i and j) and 3 for β-β (PBs h, n and o). As most of these PBs have very low frequencies (mainly less than 5% of the PBs in their kind of loops), these losses of their prediction rate is not significant. We can note that PBs h never obtains a prediction gain with this approach, at the opposite, the prediction of PBs b and p, which are related to some βstrand N capping regions is improved in each case.

Influence of protein databanks. All the prediction rates presented bellow belongs to the smallest databank (DB0). Interestingly these prediction rates do not increase with the growth of the protein databank, i.e. databanks with more redundancy. The best prediction rates remain always near identical, thus the similarity sequence rate does not improve this prediction approach based on a single sequence. Nonetheless, the over-training rate decreases greatly with the size of the databank, i.e. for (80% of sequence identity, resolution better than 2.5 Å and R-factor less than 1.00), the biggest one, the over-training rate is less than 2% thanks to the redundancy of the protein databank.

In the same way, it must be noticed that it does not change the kind of amino occurrence matrices, i.e. no new amino acid specificities are observed or disappeared (data not shown).

This fact underlines that Bayesian prediction is an interesting tool to predict and analyze the local protein structures, we expect to use in future more sophisticated methods less dependant on the size of databank. One advantage of such an approach is that it enables us to compute the most significant series of PBs and from this information propose alternative 3D candidate structures as we have shown previously [START_REF] Fourrier | Use of a structural alphabet for analysis of short loops connecting repetitive structures[END_REF].

Conclusion.

Prediction of short loops taking into account of the flanking regions clearly improves


Manuel Amoussou
email: manuel.amoussou@centralesupelec.fr

Khaled Belahcene
email: khaled.belahcene@hds.utc.fr

Nicolas Maudet
email: nicolas.maudet@lip6.fr

Vincent Mousseau
email: vincent.mousseau@centralesupelec.fr

Khaled Belahcène

Wassila Ouerdane
email: wassila.ouerdane@centralesupelec.fr

Step-wise Explanations for the Additive Model

Keywords: Additive Model, Explanation, Argument Schemes

come   L'archive ouverte pluridisciplinaire

INTRODUCTION

In this paper we address the problem of providing step-wise explanations for pairwise comparisons of alternatives based on wellestablished decision models. Alternatives are characterized by a number of criteria. The main idea is to break down the recommendation into simple statements presented to the explainee. The whole sequence of statements should formally support the recommendation. The explanations we aim for are thus contrastive, in the sense that the decision to be explained compares two alternatives, and exact (as opposed to heuristic) in the sense that we provide guarantees that the explanation produced is correct with respect to the underlying model. It is also common to distinguish between local explanations (when they focus on a specific recommendation) and global explanations (when they deal with the model in general): our approach is globally faithful to the model, and locally relevant to the pairwise comparison to be explained. Finally, even though this aspect is not detailed in this work, the perspective is to give the explainee the opportunity to accept or contradict these statements. To make things concrete we start with an illustrative example.

We consider seven abstract criteria (a, b, c, d, e, f, g), each one described on bi-levels scales, which facilitate the symbolic representation of alternatives (e.g hotels). Each alternative can be represented as its evaluation vector (𝑠 1 = (✗, ✗, ✓, ✓, ✓, ✓, ✓)) or more succinctly by the subset of criteria on which it is evaluated positively (𝑠 1 = {cdefg}). Moreover, for each criterion, the value symbolized by ✓ is more desirable than the value symbolized by ✗ (e.g breakfast included is better than not).

a b c d e f g 𝑠 1 ✗ ✗ ✓ ✓ ✓ ✓ ✓ 𝑠 2 ✓ ✗ ✗ ✓ ✗ ✗ ✗
The aggregation of criteria is done using an additive score function, assigning weights to the different criteria as follows: 𝜔 = ⟨128, 126, 77, 59, 52, 41, 37⟩

For example, the score of 𝑠 1 is thus equal to 𝑤 𝑠 1 = 77 + 59 + 52 + 41 + 37 = 276 while that of 𝑠 2 is: 𝑤 𝑠 2 = 128 + 59 = 187. It is also useful to encode the comparison of two alternatives as a vector {-1, 0, +1} 𝑛 of arguments in favour (PRO) or against (CON) the option 𝑠 1 , or neutral (NEU). In our example, PRO 𝑠 1 = {c, e, f, g}, CON 𝑠 1 = {a}, while NEU = {b, d} Explanations can take many different forms. We list different possible explanations to the fact that 𝑠 1 is preferred to 𝑠 2 :

(i) the first approach (model disclosure) could be to provide the full score calculation for both options, as illustrated above.

But noticing that d is a neutral argument satisfied both by 𝑠 1 and 𝑠 2 , we could omit it and simply provide the summation of PRO arguments vs. CON arguments. (ii) the counter-factual approach seeks for minimal modification in the input that would change the outcome. For instance, we could state that, if 𝑠 2 had satisfied b, 𝑠 2 would instead have been recommended over 𝑠 1 . Or (affecting the other alternative this time), if 𝑠 1 had not satisfied cd. (iii) following a prime implicant approach, we could produce those arguments sufficient to explain the decision. In our case, two possible explanations could be given: [START_REF] Kh | Explaining robust additive utility models by sequences of preference swaps[END_REF] given that bd are neutral arguments, the PRO arguments cef are sufficient to overcome any set of CON arguments. In particular, this shows that the decision would remain the same even if g was a CON argument. And [START_REF] Kh | Comparing options with argument schemes powered by cancellation[END_REF] given that b is a neutral argument, the PRO arguments cefg are sufficient to overcome any set of CON arguments. In particular, this shows that the decision would remain the same even if d was a CON argument. (iv) following a step-wise approach, we could exhibit a collection of statements aiming at proving the decision. For instance, we could state that cdefg is preferred over ac, and that ac is preferred over ad, so that our conclusion should hold, following a transitive reasoning. Or, using a different logic, we could state that cd is preferred over a, while efg is preferred over d, which altogether justifies our decision. This example allows us to illustrate some key principles of explanation (see e.g. [START_REF] Coste-Marquis | From Explanations to Intelligible Explanations[END_REF][START_REF] Miller | Explanation in artificial intelligence: Insights from the social sciences[END_REF]) :

• language intelligibility-we want explanations to be conveyed in a language which is meaningful to the explainee.

In our example, the weights used in calculations may not be easily interpreted by the explainee1 . • relevance-we want explanations to focus on relevant information. In our example, as noticed, mentioning neutral arguments should be avoided if possible. • cognitive simplicity-we want explanations to be "easy to process" by the explainee. This can be instantiated in different ways: prime implicant explanations are after (subset, or sometimes cardinality) minimal sufficient reasons, while step-wise explanations make use of intermediary comparisons involving a limited number of criteria. Our ambition in this paper is to develop a principle-based and cognitively bounded model of step-wise explanations. As our example illustrates, there can be different 'logic' at play when combining statements. To account for that we describe a number of schemes for such explanations in the context of a comparison based on a weighted sum model (Section 3). By principle-based approach we mean that each scheme is attached to number of well-understood properties of the underlying decision model, that we make explicit and discuss in this paper. The resulting calculus is provably correct (Section 4). By cognitively-bounded we mean that our statements will be constrained so as to remain easy to grasp by the explainee. The resulting calculus is not complete, but we explore this issue in detail and provide several elements showing that our approach is satisfactory in terms of empirical completeness (Section 5).

OUR MODEL

We consider a set of items [𝑚], and we abstractly refer to states, as subsets of items, i.e. elements of 2 [𝑚] . A comparative statement is a pair of states (𝐴, 𝐵) ∈ 2 [𝑚] × 2 [𝑚] , interpreted as a preference statement-'𝐴 is preferred to 𝐵'.

Schemes. Our aim is to provide a formal language and reasoning machinery allowing to support (explain) such comparative statements. We build on the notion of argument scheme, that is, an operator tying a sequence of statements, called the premise, satisfying some conditions, into another statement called the conclusion [START_REF] Walton | Argumentation schemes for Presumptive Reasoning[END_REF]. As we deal with preferences, argument schemes are ways of deriving new preferences from previously established ones. Noticeably, all our schemes operate on the same set of premises -finite sequences of comparative statements, represented as bracketed lists -and the same set of conclusions -comparative statements in 2 [𝑚] × 2 [𝑚] . We shall denote an arbitrary scheme 𝑠 as:

[(𝐴 1 , 𝐵 1 ), . . . , (𝐴 𝑘 , 𝐵 𝑘 )] 𝑠 - → (𝐴, 𝐵)
Correctness. The fact that our argument schemes allow us to only derive conclusions coherent with the preference relation is captured by the notion of correctness: Definition 1. An argument scheme is correct w.r.t. a preference relation ≿ if, when all premises belong to ≿, then the conclusion also belong to ≿.

At this stage we leave the preference relation unspecified, but in Section 3 we shall delve into this connection between the properties of preference relations and the schemes.

We further formalize the requirement of relevance (the absence of neural arguments) and simplification with respect to the relative difficulty of a statement. Definition 2. A pair composed of a premise [(𝐴 1 , 𝐵 1 ), . . . , (𝐴 𝑘 , 𝐵 𝑘 )] and a conclusion (𝐴, 𝐵) is independent of irrelevant alternative (III) when

𝑘 𝑖=1 𝐴 𝑖 ∪ 𝑘 𝑖=1 𝐵 𝑖 ⊆ (𝐴 ∪ 𝐵) \ (𝐴 ∩ 𝐵). Definition 3. A pair composed of a premise [(𝐴 1 , 𝐵 1 ), . . . (𝐴 𝑘 , 𝐵 𝑘 )]
and a conclusion (𝐴, 𝐵) is simplifying when the premise is less difficult than the conclusion.

We believe this definition to be very general, as it captures one of the goals of explanation. To be actionable, though, it requires to specify the relative difficulty of a premise and a conclusion. We introduce a specific model allowing to derive the relative difficulty of statements, where this difficulty is purely syntactic and directly results from the number of items involved in the comparative statement.

Definition 4 (Difficulty of statements). The difficulty of a comparative statement (𝐴, 𝐵) ∈ 2 [𝑚] × 2 [𝑚] is the ordered pair of integers (|𝐴|, |𝐵|). Consequently, we say that a comparative statement (𝐴, 𝐵) is less difficult than another comparative statement (𝐴 ′ , 𝐵 ′ ) -when |𝐴| ≤ |𝐴 ′ | , |𝐵| ≤ |𝐵 ′ | and at least one comparison is strict. A sequence of comparative statements [(𝐴 1 , 𝐵 1 ), . . . (𝐴 𝑘 , 𝐵 𝑘 )] is less difficult than a comparative statement (𝐴, 𝐵 ) when all comparative statements (𝐴 𝑖 , 𝐵 𝑖 ) are less difficult t han ( 𝐴, 𝐵 ). Finally, we define difficulty classes of comparative statements by putting upper bounds on the difficulty: for all integers 𝑝, 𝑞 from 0 to 𝑚 , let Δ(𝑝, 𝑞) = {(𝐴, 𝐵) ∈ 2 [𝑚] × 2 [𝑚] : |𝐴| ≤ 𝑝, |𝐵| ≤ 𝑞}.

We denote A the syntactically atomic elements, those that are considered self-evident and legit to be used as steps of an explanation for the considered explainee. We shall use difficulty classes Δ(𝑝, 𝑞) to specify this set. In the context of explaining preferences between subset of desirable items, some values of the pair (𝑝, 𝑞) are of specific interest: Δ(𝑚, 𝑚 ) are unrestricted statements; comparative statements in Δ(𝑚, 0) represent Pareto dominance statements; comparative statements in Δ(1, 1) can be interpreted as swaps [START_REF] Hammond | Even Swaps: A Rational Method for Making Trade-offs[END_REF], representing the exchange of one criterion against another; those in Δ(1, 𝑚) or in Δ(𝑚, 1) represent a single item stronger or weaker than a subset of others, respectively considered as a pro or a con argument.

For instance, in the context of hotel comparisons, an argument in Δ(1, 1) could be "we prefer to have free breakfast than free wifi access". An argument in Δ(1, 2) could be "We prefer to have a swimming pool than free breakfast and wifi". To appreciate how difficult it can be to interpret higher order arguments, consider arguments in Δ(2, 2), for instance "free breakfast and wifi access is preferable to having a swimming pool and being close to the city center". In Section 5 we shall investigate how restraining explanation to such simple statements affects the ability to produce explanations.

Explanation based on schemes. Self-evident atomic statements put a bound on the difficulty o f e ach s tep o f a n e xplanation. As an explanation is a sequence of such statements, we also seek to produce correct explanations of minimal length: Definition 5 (The explanation p roblem). Given a comparative statement (𝐴, 𝐵) ∈ 2 [𝑚] × 2 [𝑚] , a preference relation ≿, a set of statements A belonging to ≿, a set of schemes S, and a positive integer 𝑘: is there a positive integer 𝑘 ′ ≤ 𝑘, a list of length 𝑘 ′ of statements [(𝐴 1 , 𝐵 1 ), . . . , (𝐴 𝑘 ′ , 𝐵 𝑘 ′ )] all belonging to A , and a scheme 𝑠 ∈ S such that [(𝐴 1 , 𝐵 1 ), . . . , (𝐴 𝑘 ′ , 𝐵 𝑘 ′ )] 𝑠 → (𝐴, 𝐵)?

Note that this definition remains agnostic regarding the way the preference relation is represented in the input.

We shall now in the next section present the different argument schemes found in S and considered for reasoning with preferences.

SCHEMES FOR REASONING WITH PREFERENCES

This section is devoted to the construction of derivation rules adequate to reason about preferences. We formalize these rules as operators tying a list of premises to a conclusion, where premises and conclusions are comparative statements. We exploit key properties of the additive model-transitivity and cancellation-and formalize derivation rules taking advantage of each, from the ground up: the transitive and ceteris paribus schemes. We then introduce the reduced transitive scheme, that allows to directly derive any conclusion that can be proven using the two previous schemes. We conclude by introducing the covering scheme, which satisfies the independence of irrelevant items property (see Definition 2).

Properties of preference

We are interested in the preference relation ≿ that might exist between states 𝐴, 𝐵 ∈ 2 [𝑚] , with 𝐴 ≿ 𝐵 meaning that 𝐴 is considered at least as good as 𝐵. We recall some useful features that preference relations may possess.

Definition 6 (Properties of preference). Let ≿ ⊂ 2 [𝑚] × 2 [𝑚] a binary relation between states. We say:

• ≿ is transitive when, for any states 𝐴, 𝐵, 𝐶 ∈ 2 [𝑚] , if 𝐴 ≿ 𝐵 and 𝐵 ≿ 𝐶 then 𝐴 ≿ 𝐶; • ≿ satisfies (first order) cancellation if preference between states does not depend on common items, i.e. ∀𝐴,

𝐵 ∈ 2 [𝑚] 𝐴 ≿ 𝐵 ⇐⇒ (𝐴 \ 𝐵) ≿ (𝐵 \ 𝐴); • ≿ is additive when there is a 𝑚-tuple of real numbers ⟨𝜔 𝑖 ⟩ 𝑖 ∈ [𝑚] ∈ R [𝑚] such that 𝐴 ≿ 𝐵 ⇐⇒ 𝑖 ∈𝐴 𝜔 𝑖 ≥ 𝑖 ∈𝐵 𝜔 𝑖 .
• ≿ is an additive linear order when it is additive and there is no indifference, i.e. if 𝐴 ≠ 𝐵 then either 𝐴 𝐵 or 𝐵 𝐴 [START_REF] Fishburn | subset comparisons for additive linear orders[END_REF].

Obviously, an additive preference satisfies both the transitive and cancellation properties.

The transitive scheme

As we strive to explain recommendations deriving from a weighted sum model, we can mechanize the transitive and cancellation properties under the form of derivation rules. For instance, we define the binary transitive scheme (2 -𝑡𝑟 ), allowing to chain preference statements:

[(𝐴, 𝐵), (𝐵, 𝐶)] 2-𝑡𝑟 ----→ (𝐴, 𝐶)
Following the approach we describe in Section 2, given an explanandum in the form of a preference statement (𝐴, 𝐵) belonging to ≿, an explanans is a proof consisting of recursive applications of a derivation rule -for instance, 2-tr -allowing to derive the conclusion (𝐴, 𝐵) from acceptable premises. Nevertheless, proofs are recursive objects that can be cumbersome to compute or present to an explainee, and we propose to alleviate this issue by introducing more powerful reasoning devices. Indeed, consider the case of purely transitive reasoning: chaining transitive lemmas amounts to consider chains of transitive premises. For instance, if we know that 𝐴 ≿ 𝐵, 𝐵 ≿ 𝐶, 𝐶 ≿ 𝐷 and 𝐷 ≿ 𝐸, we can infer that 𝐴 ≿ 𝐸, which we denote (𝐴, 𝐵), (𝐵, 𝐶), (𝐶, 𝐷), (𝐷, 𝐸) ⊢ 2-𝑡𝑟 (𝐴, 𝐸). We believe this abundance of syntactic proofs not to be relevant to the question of computing explanations, and we therefore propose to consider the following transitive scheme (𝑡𝑟 ). Definition 7 (transitive scheme (𝑡𝑟 )). The premise [(𝐴 1 , 𝐵 1 ), . . . (𝐴 𝑘 , 𝐵 𝑘 )] and conclusion (𝐴, 𝐵) satisfy the transitive scheme when, for all 2 ≤ 𝑗 ≤ 𝑘, 𝐴 𝑗 = 𝐵 𝑗 -1 , 𝐴 1 = 𝐴 and 𝐵 𝑘 = 𝐵.

Formally, ⊢ 2-𝑡𝑟 = 𝑡𝑟 --→ -what can be proven using the 2-𝑡𝑟 scheme is exactly what can be derived in a single application of the 𝑡𝑟 scheme. We have traded the recursive nature of the proof using a binary scheme for a one-shot derivation using a scheme operating on a list of premises of unbounded length. EXAMPLE 1. The premise [(acg, bef), (bef, bfg)] syntactically satisfies the transitive scheme for the conclusion (acg, bfg):

[(acg, bef), (bef, bfg)] 𝑡𝑟 --→ (acg, bfg)
which can be expressed as: "as soon as acg ≻ bef and bef ≻ bfg, acg should be preferred to bfg". Note however that the first comparative statement is complex as it involves six different criteria.

Note that the comparative statements composing the premise of a transitive scheme are ordered, so the sequence of alternatives

𝐴 ≡ 𝐴 0 ≿ 𝐵 0 ≡ 𝐴 1 ≿ • • • ≿ 𝐵 𝑘 -1 ≡ 𝐴 𝑘 ≿ 𝐵 𝑘 ≡ 𝐵 is non-increasing w.

The ceteris paribus scheme

The cancellation property allows to reason ceteris paribus -everything else being equal -independently from the context, and represents a great opportunity in terms of explanation, as preference can be deduced from comparative statements where common items are not mentioned. It motivates the following definition of the ceteris paribus argument scheme. Definition 8 (ceteris paribus scheme (𝑐𝑝)). The premise [(𝐴 1 , 𝐵 1 ), . . . (𝐴 𝑘 , 𝐵 𝑘 )] and conclusion (𝐴, 𝐵) satisfy the ceteris paribus scheme when 𝑘 = 1, 𝐴 1 \ 𝐵 1 = 𝐴 \ 𝐵 and 𝐵 1 \ 𝐴 1 = 𝐵 \ 𝐴. In this case, the comparative statements (𝐴 1 , 𝐵 1 ) and (𝐴, 𝐵) are said to be congruent.

Obviously, congruence is an equivalence relation between comparative statements. In the congruence class of a given compartive statement (𝐴, 𝐵) ∈ 2 [𝑚] × 2 [𝑚] , the comparative statement (𝐴 \𝐵, 𝐵 \𝐴), where the states are pairwise disjoint and obtained from (𝐴, 𝐵) by subtracting the common items 𝐴 ∩ 𝐵 respectively from 𝐴 and 𝐵, is of special interest. When (𝐴, 𝐵) and (𝐴 1 , 𝐵 1 ) are congruent, the preference of 𝐴 over 𝐵 translates to the preference of 𝐴 \ 𝐵 over 𝐵 \𝐴 by reasoning 'everything else' -in this case, items in 𝐴 ∩ 𝐵 -'being equal' (ceteris paribus), and then to the preference of 𝐴 1 over 𝐵 1 by considering 𝐴 1 ∩ 𝐵 1 irrelevant. EXAMPLE 3. When comparing acg to bfg, it might be warranted to consider that, as they both achieve g, this criterion can be omitted: 'the first option is better than the second one because, everything else being equal, ac is preferred to bf'.

Formally, we write [(ac, bf)]

𝑐𝑝 --→ (acg, bfg) OBSERVATION 2. If the preference ≿ satisfies cancellation then the ceteris paribus scheme is correct w.r.t. ≿.

We shall often be presented with instances of the inverse problem: given an initial state, is there a final state such that the comparative statement from the initial to final state is congruent to a given comparative statement? LEMMA 1 (FOURTH CONGRUENT PROBLEM). Given a state 𝐴 ∈ 2 [𝑚] and a comparative statement (𝐴 ′ , 𝐵 ′ ) ∈ 2 [𝑚] × 2 [𝑚] , if 𝐴 ⊇ (𝐴 ′ \ 𝐵 ′ ) and 𝐴 ∩ (𝐵 ′ \ 𝐴 ′ ) = ∅ then there is exactly one state 𝐵 ∈ 2 [𝑚] such that (𝐴, 𝐵) and (𝐴 ′ , 𝐵 ′ ) are congruent, given by 𝐵 = 𝐴 \ (𝐴 ′ \ 𝐵 ′ ) ∪ (𝐵 ′ \ 𝐴 ′ ), else there is none. EXAMPLE 4. Consider the comparative statement (ade, bce). The set of comparative statements congruent to it is: {(ad, bc), (adf, bcf), (adg, bcg), (adef, bcef), (adeg, bceg), (adfg, bcfg), (adefg, bcefg)}. The initial states {ad, ade, adf, adg, adef, adeg, adfg, adefg} are exactly the supersets of ad that do not contain bc, and for each one of them, there is only one matching final state. This makes sense when the comparative statement (ade, bce) is understood as 'give ade, take bce', from which e can be omitted. Then, ad can only be effectively taken from a state already containing it, and bc can only be effectively added to a state not yet containing it.

The reduced transitive scheme

When preference satisfies both the transitive and cancellation properties, it is correct to use both the 𝑡𝑟 and 𝑐𝑝 schemes to derive new comparative statements. Figure 1 illustrates such a proof. For practical reasons, we want to streamline and mechanize this reasoning pattern, by formalizing a scheme-called reduced transitive (rt)-directly tying the premise [(a, b), (c, f)] to the conclusion (aceg, befg) and leaving the intermediate steps unspecified 2 . Definition 9 (reduced transitive scheme (𝑟𝑡)). The premise [(𝐴 1 , 𝐵 1 ), . . . , (𝐴 𝑘 , 𝐵 𝑘 )] and conclusion (𝐴, 𝐵) satisfy the reduced transitive scheme when there exists (𝐴 ′ 1 , 𝐵 ′ 1 ), . . . , (𝐴 ′ 𝑘 , 𝐵 ′ 𝑘 ) and (𝐴 ′ , 𝐵 ′ ) such that:

           ∀𝑖 ∈ [𝑘] [(𝐴 ′ 𝑖 , 𝐵 ′ 𝑖 )] 𝑐𝑝 --→ (𝐴 𝑖 , 𝐵 𝑖 ); [(𝐴 ′ 1 , 𝐵 ′ 1 ), . . . , (𝐴 ′ 𝑘 , 𝐵 ′ 𝑘 )] 𝑡𝑟 --→ (𝐴 ′ , 𝐵 ′ ); and
[(𝐴 ′ , 𝐵 ′ )] 𝑐𝑝 --→ (𝐴, 𝐵).
EXAMPLE 5. The proof depicted by Fig. 1 can be read as follows: "acg should be preferred to bcg, since everything else being equal, a is preferred to b. Then bcg should be preferred to bfg, since everything else being equal, c is preferred to f. Therefore acg should be preferred to bfg."

We denote:

[(a, b), (c, f)] 𝑟𝑡 --→ (aceg, befg)
We can note that Definition 9 is inefficient, as the search space of sequences of comparisons of length 𝑘 is finite, but intractably large. The lack of specification can be overcome by reconstructing the missing intermediate steps, solving iteratively 𝑘 fourth congruent problems (see Lemma 1), which can be done in 𝑂 (𝑘𝑚 2 ) time.

Moreover, the 𝑟𝑡 scheme fulfills i ts r ole b y a llowing one-step derivation of proofs combining 𝑡𝑟 and 𝑐𝑝 derivations. PROPOSITION

The decomposition scheme

Introduced in [START_REF] Kh | Comparing options with argument schemes powered by cancellation[END_REF] and implementing cancellation properties of higher order, the decomposition scheme aims at leveraging the assumed additive property of the preference relation 3 . When preference is additive, preference statements translate into linear comparisons, that can be summed up. Then, the scores of items appearing on both sides cancel out, sometimes allowing to derive new comparisons. Then, as it is illustrated by Fig. 2 by cancelling 𝜔 e and 𝜔 c on both sides (this is actually an instance of second order cancellation, because it is performed across two comparative statements), we obtain

Definition 10 (decomposition scheme (𝑑𝑒𝑐)). A premise [(𝐴

𝜔 f + 𝜔 g + 𝜔 b ≥ 𝜔 d + 𝜔 a , hence bfg ≻ 𝜔 ad. b ¡ c ≻ d ¡ e ¡ e f g ≻ a ¡ c b f g ≻ a d
Figure 2: Decomposition scheme: graphical representation

The decomposition scheme strictly generalizes the schemes introduced previously. PROPOSITION 3. If a premise [(𝐴 1 , 𝐵 1 ), . . . , (𝐴 𝑘 , 𝐵 𝑘 )] and a conclusion (𝐴, 𝐵) satisfy the transitive or reduced transitive scheme, then they satisfy the decomposition scheme.

We note that the decomposition scheme is commutative by construction. Nevertheless, it does not seem very satisfying as an explanation device, as the cancellation properties of higher order it enacts are complex and of low normative appeal-actually, even though they are syntactically transductive, their justification derives from the additive form we strive to circumvent.

In general, instances of the decomposition scheme do not satisfy the reduced transitive scheme. The sequence of comparative statements of the premise can not be interpreted as ceteris paribus justifications of comparative statements between states, because at some point, they either require to add an item to a state where it is already present, or to remove an item from a state where it is absent. EXAMPLE 7. The premise [(bc, de), (efg, ac)] and the conclusion (bfg, ad) satisfy the decomposition scheme, but they cannot be interpreted as a sequence of comparative statements because e.g. the initial state of the conclusion bfg does not contain c. This situation can be avoided when the states mentioned in the premise are all pairwise disjoint. PROPOSITION 4. Let [(𝐴 1 , 𝐵 1 ), . . . , (𝐴 𝑘 , 𝐵 𝑘 )] a premise and (𝐴, 𝐵) a conclusion satisfying the decomposition scheme. Every permutation 𝜎 of the indices [𝑘] makes the premise [(𝐴 𝜎 (1) , 𝐵 𝜎 (1) ), . . . , (𝐴 𝜎 (𝑘 ) , 𝐵 𝜎 (𝑘 ) )] and conclusion (𝐴, 𝐵) satisfy the reduced transitive scheme if, and only if, the states 𝐴 1 , . . . , 𝐴 𝑘 , 𝐵 1 , . . . , 𝐵 𝑘 are pairwise disjoint.

PROOF. (Sketch) (⇐) When all the states 𝐴 1 , . . . , 𝐴 𝑘 , 𝐵 1 , . . . , 𝐵 𝑘 are pairwise disjoint, each item of 𝐴 \ 𝐵 appears exactly once in the 𝐵 𝑖 and never in the 𝐴 𝑖 , each item of 𝐵 \ 𝐴 appears exactly once in the 𝐴 𝑖 and never in the 𝐵 𝑖 , and items in both sets or neither never appear (incidentally making the transaction III (see Definition 2)). Consequently, items of the set 𝑘 𝑖=1 𝐴 𝑖 can be removed in any order from 𝐴 and those in the set 𝑘 𝑖=1 𝐵 𝑖 can be added in any order, so as to accrue to 𝐵. □

This motivates the definition of the covering scheme.

The covering scheme

In this scheme a list of comparative statements [(𝐴 ). An instance of the covering scheme is an instance of the decomposing scheme where all the states 𝐴 1 , . . . , 𝐴 𝑘 , 𝐵 1 , . . . , 𝐵 𝑘 are pairwise disjoint.

The covering scheme is commutative and independent of irrelevant items by construction. It particularizes the reduced transitive schemes -while circumventing the tedious scheduling of comparative statements -and, as a corollary, it is correct under much milder conditions than the decomposition scheme. PROPOSITION 5. If the preference ≿ is transitive and satisfies cancellation, then the covering scheme is correct w.r.t. ≿.

The covering scheme describes exactly the moral algebra introduced by Benjamin Franklin (see [START_REF]The Papers of Benjamin Franklin[END_REF]) to infer preferences. EXAMPLE 8. Consider the conclusion: (bfg, cde). The premise [(fg, c), (b, de)] constitute a covering scheme:

[(fg, c), (b, de)] 𝑐𝑜𝑣 ---→ (bfg, cde)
The covering scheme particularizes both the reduced transitive scheme, and the decomposition scheme. As such, it gives us the best of both world, in a sense. On the one hand, it formalizes a proof, articulating transitive and ceteris paribus derivations, that can be presented to the explainee as a diagram, such as in Fig. 3a, or narratively such as in Fig. 3c (for hotel comparisons for instance). On the other hand, the premises can be understood as grouping some cons with some stronger pros, so as to "cover" the cons, and can be presented visually to the explainee such as in Fig. 3b. "As, all other things being equal, having free breakfast and wifi access is preferred to having a swimming pool (fg, c), and being close to the city is preferred than having a sports hall and a low tourist tax (b, de), we get that (bfg, cde)"

Figure 3: Three representations of the Covering Scheme

Note also that a single covering scheme of length 𝑘 can be interpreted as 𝑘! transitive schemes, as the validity of its premises does not depend on their order. Hence, for instance for our Ex. 8, two transitive schemes would correspond to this covering scheme: [(bfg, cdfg), (cdfg, cde)] or [(bfg, be), (be, cde)]

We presented in this section different types of schemes representing different way of reasoning over preferences. We believe that these schemes may correspond to alternative explanation strategies.

One can note that it exist a logical dependency between the premises and conclusions satisfying the various schemes. Indeed, all instances satisfying the 𝑐𝑜𝑣 scheme satisfy the 𝑟𝑡 scheme, and the ones satisfying the latter satisfy the 𝑑𝑒𝑐 scheme (the converse is not true). This has an obvious consequence on the explainabilty relations: more general implies more explicative. Moreover, the conclusions of the 𝑡𝑟 scheme can all be obtained via the 𝑟𝑡 scheme, and those of the 𝑐𝑝 via the 𝑑𝑒𝑐, 𝑟𝑡 or 𝑐𝑜𝑣 schemes.

EXPLAINING WITH SCHEMES

Section 3 was about engineering a deductive tool allowing to derive complex preferences from simpler one, in a correct manner with respect to the latent preference model. Given an explanans-a comparative statement that needs to be explained-it allows us to cast the explanation problem as an abduction problem of finding premises that satisfy some minimality requirement given a conclusion and a set of rules. We now investigate the relative expressiveness and computational complexity of explaining with the 𝑟𝑡-see Def. 9-and 𝑐𝑜𝑣-see Def. 11-schemes, together with the influence of the choice of the atomically simple statements.

From now on, we denote as E (𝑠, A ≿ , 𝑘) the set of pairs (𝐴, 𝐵) that can be derived using the scheme 𝑠 from statements respecting the syntactic constraints of A, the semantic constraint of being coherent with ≿, and involving at most 𝑘 premises. For a given pair (𝐴, 𝐵) the explanation existence problem asks whether (𝐴, 𝐵) ∈ E (𝑠, A ≿ , 𝑘). By convention, this pair (𝐴, 𝐵) is considered not self-evident.

Solving Explanation Problems with Schemes

As we have seen in the previous section, when preference is additive, all our reasoning schemes in {transitive, ceteris paribus, reduced transitive, decomposition, covering} are correct. However, we cannot expect them to be complete, even without any syntactic restriction on A: when states 𝐴 ≻ 𝐵 are adjacent in the preference relation ≿, i.e. when there is no other state 𝑋 s.t. 𝐴 ≻ 𝑋 ≻ 𝐵, (𝐴, 𝐵) are said to be a critical pair, see [START_REF] Fishburn | subset comparisons for additive linear orders[END_REF]. But this means in turn that the conclusion (𝐴, 𝐵) cannot be obtained with the 𝑟𝑡 scheme-even less so by the 𝑐𝑜𝑣 and the 𝑡𝑟 schemes. These critical pairs are thus not explainable with these schemes (see Ex.9). EXAMPLE 9. The conclusion (bcd, aefg) is a critical pair. Indeed, 𝜔 b + 𝜔 c + 𝜔 d = 262, 𝜔 a + 𝜔 e + 𝜔 f + 𝜔 g = 258, and it is not possible to exhibit another state from 2 [𝑚] with a score ∈]258, 262[. On the other hand, as soon as a pair is not critical, and provided that A does not put any syntactic constraint on the statements used, there must exist at least one explanation with schemes 𝑡𝑟 and 𝑟𝑡. This means that the complexity of deciding the existence of an explanation for these schemes is directly related to that of deciding whether a pair is critical. We show that this problem is difficult.

𝑚 0 𝑚 0 𝑚 0 THEOREM 1.
Given 𝜔 ∈ N , and 𝐴, 𝐵 ∈ 2 [𝑚] such that 𝐴 ≿ 𝐵 where ≿ the additive preference relation induced from 𝜔. Deciding whether (𝐴, 𝐵) is a critical pair is Co-NP-complete.

PROOF. Reduction from SUBSET-SUM [START_REF] Garey | Computers and Intractability, a Guide to the Theory of NP-completeness[END_REF]. In SUBSET-SUM we are given a set 𝐴 of size 𝑚 a positive size 𝑤 (𝑎), for each 𝑎 ∈ 𝐴, and a positive integer 𝐾. We ask whether there is a subset 𝐴 ′ ⊆ 𝐴 such that the sum of the weights is exactly 𝐾. This problem is known to be NP-complete. We construct an instance of the critical pair problem as follows. We take a set 𝐶 of 𝑚 + 2 criteria: for each element 𝑎 𝑖 ∈ 𝐴, we take a criteria 𝑐 𝑖 , of weight 2𝑠 (𝑎 𝑖 ). We add two other criteria: 𝑎 𝑛+1 of weight 2𝐾 -1, and 𝑎 𝑛+2 , of weight 2𝐾 +1. We ask whether the pair (𝑋, 𝑌 ) is critical, where 𝑋 = ⟨0, . . . , 1, 0⟩ and 𝑌 = ⟨0, . . . 1⟩. Note that 𝑋 and 𝑌 have respective weights of 2𝐾 -1 and 2𝐾 + 1, hence we are looking for an intermediate alternative of weight exactly 2𝐾, an even number. We claim that the answer to this question is no iff the original SUBSET-SUM problem is a yes-instance. To see this, observe that all the weights in our critical pair instance are even, except that of 𝑐 𝑛+1 and 𝑐 𝑛+2 which are odd. As 𝑠 (𝑐 𝑛+2 ) > 2𝐾, it certainly cannot be part of the solution. Furthermore, the solution cannot include 𝑐 𝑛+1 , as in that case it would be the only odd weight, and then the sum would be odd. We are left with criteria 𝑐 1 , . . . 𝑐 𝑛 , whose weights are precisely twice the weight in the original SUBSET-SUM problem. □ As a corollary, it is difficult t o decide w hether a n explanation exists with these schemes. COROLLARY 1. Given 𝜔 ∈ N 𝐴, 𝐵 ∈ 2 [𝑚] such that 𝐴 ≿ 𝐵, where ≿ is the additive preference relation induced from 𝜔, and A the set of statements Δ(𝑚, 𝑚). Deciding whether (𝐴, 𝐵) ∈ E(𝑠, A ≿ , +∞) is NP-complete for 𝑠 ∈ {𝑟𝑡, 𝑡𝑟 }.

For our scheme of choice 𝑐𝑜𝑣, we can prove intractability through an independent proof. THEOREM 2. Given 𝜔 ∈ N , 𝐴, 𝐵 ∈ 2 [𝑚] such that 𝐴 ≿ 𝐵 where ≿ is the additive preference relation induced from 𝜔 and A the set of statements Δ(𝑚, 𝑚). Deciding whether (𝐴, 𝐵) ∈ E(𝑐𝑜𝑣, A ≿ , +∞) is NP-complete.

Explaining with Atomic Statements

We now turn our attention towards explanations which put syntactic restrictions on the sets of atomic elements used, namely Δ(1, 1), Δ(1, 𝑚), and Δ(𝑚, 1)

(see Sect.2). THEOREM 3. When ≿ is additive, E(𝑐𝑜𝑣, A ≿ , ∞) is transitive when A ≿ ∈ {Δ(1, 1), Δ(1, 𝑚), Δ(𝑚, 1)}.

PROOF. Suppose [(𝐴

(𝐴 𝑖 ∪ 𝐴 ′ 𝑖 ′ \ { 𝑗 }, 𝐵 𝑖 ∪ 𝐵 ′ 𝑖 ′ \ { 𝑗 })
. This comparative statement belongs to A, and also to ≿ because it is additive (by summation of the inequalities characterizing 𝐴 𝑖 ≿ 𝐵 𝑖 and 𝐴 ′ 𝑖 ′ ≿ 𝐵 ′ 𝑖 ′ and cancellation of the terms 𝜔 𝑗 appearing on both sides). By iterating this operation, we obtain a covering scheme supporting (𝐴, 𝐶) of size no greater than 𝑘 + 𝑘 ′ . □

As a corollary, when restricting the atoms to mention solely one pro vs any number of cons (resp. any number of pros vs one con), the 𝑟𝑡 scheme is not more expressive than the 𝑐𝑜𝑣 one. This is not the case when we allow to mix these atoms (as illustrated by Ex. 10). EXAMPLE 10. The premise [(b, ge), (fg, c)] and the conclusion (bf, ce) satisfy the 𝑟𝑡 scheme (as it is illustrated in the figure below). However, this is not the case for the cov scheme as

𝜔 𝑓 < 𝜔 𝑐 + 𝜔 𝑒 and 𝜔 𝑏 < 𝜔 𝑐 + 𝜔 𝑒 (b, eg) 𝑐𝑝 --→ (bf, efg) (fg, c) 𝑐𝑝 --→ (efg, ce) 𝑡𝑟 -→ (bf, ce) PROPOSITION 6. For any positive integer 𝑘, when A ∈ {Δ(1, 1), Δ(1, 𝑚), Δ(𝑚, 1)} and ≿ is additive, E (𝑟𝑡, A ≿ , 𝑘) = E (𝑐𝑜𝑣, A ≿ , 𝑘).
One may wonder whether these atomic statements make the problem computationally simpler to handle. While the answer is known to be positive for A = Δ(1, 1) [START_REF] Kh | Explaining robust additive utility models by sequences of preference swaps[END_REF], we show that from 𝑘 ≥ 2 the problem is difficult. THEOREM 4. Given 𝜔 ∈ N 𝑚 0 𝐴, 𝐵 ∈ 2 [𝑚] such that 𝐴 ≿ 𝐵 where ≿ is the additive preference relation induced from 𝜔, and A = Δ(1, 𝑘). When 𝑘 ≥ 2, deciding whether (𝐴, 𝐵) ∈ E (𝑐𝑜𝑣, A ≿ , +∞) is NP-complete.

When using the 𝑐𝑜𝑣 scheme, the length of explanations is bounded by the number 𝑚 of items. There are thus a range of values of 𝑚 for which finding an explanation might prove too difficult for a human, but can be easily achieved by a machine, either with a solver or even by brute force. This is a plea for the use of artificial explainers.

EMPIRICAL COMPLETENESS OF THE COVERING SCHEME

The results of Section 4 establish that the sets of atomic statements Δ(1, 𝑚) or Δ(𝑚, 1) using the cov scheme discharge us from the task of sequencing the explanations. Of course, this comes at a price, as some pairs which may be explained otherwise may not be explained with these statements. This section provides insights regarding the "empirical completeness" of the 𝑐𝑜𝑣 scheme with such statements. In general, given an additive preference relation, noted R, the set A R of comparative statements that can be used as a premise for explaining the conclusion (𝐴, 𝐵) such that (𝐴, 𝐵) ∈ R and (𝐴, 𝐵) ∉ A R is the following:

A R = [Δ(1, 𝑚) ∪ Δ(𝑚, 1)] ∩ R
In our context, we consider preference relations over states that are representable by additive linear order on the algebra of subsets of a finite set (see [START_REF] Fishburn | subset comparisons for additive linear orders[END_REF]). We assume the following ordering over the singleton states: a ≻ b ≻ c ≻ d ≻ e ≻ f ≻ . . .. Thus, we denote by 𝑇 𝑚 ≻ = {(𝐴, 𝐵) ∈ 2 [𝑚] × 2 [𝑚] : 𝐴 ≻ 𝐵 and 𝐴 ∩ 𝐵 = ∅}, and we have A ≻ ⊆ 𝑇 𝑚 ≻ . The number of additive linear orders on 2 [𝑚] grows very quickly [START_REF] Fishburn | subset comparisons for additive linear orders[END_REF][START_REF] Maclagan | Boolean Term Orders and the Root System 𝐵 𝑛[END_REF]. It corresponds to 14 for 𝑚 = 4, but for 𝑚 = 7 we already have more than 200 million orders. Technically, we have been able to generate all additive linear orders for 𝑚 ∈ [ [4; 6]]. Thus, to decide whether (𝐴, 𝐵) ∈ E (𝑐𝑜𝑣, A ≻ , ∞), we used a Mixed Integer Linear Program solver. Finally, to evaluate the proportions of pairs 𝑇 𝑚 ≻ \A ≻ which are explainable, we compute for each additive linear order ≻ given 𝑚, the following value 1 summarizes the minimum, median and maximum values obtained over the, respectively, 14, 516, and 124187 additive linear orders (for 𝑚 = 4, 5, 6). We notice that both the minimum and the median values of 𝔐 𝑚, ≻ increases with 𝑚. Regarding the maximum values, we note that there are all equal to 100% which means that for all 𝑚 ∈ [ [4; 6]], there exists at least one additive linear order ≻ for which all pairs of states are explainable.

𝔐 𝑚, ≻ = |E (𝑐𝑜𝑣, A ≻ , ∞) ∩ 𝑇 𝑚 ≻ \A ≻ | |𝑇 𝑚 ≻ \A ≻ | 𝑚 Minimum Median Maximum |𝑇 𝑚 ≻ \A ≻ | 4
Looking more globally at the set of values in the Table 1, we can say that a significant majority of the pairs of 𝑇 𝑚 ≻ \A ≻ are explainable. For example, for 𝑚 = 6, more than 3 pairs out of 4 are explainable regardless of the additive linear order considered.

Of course, the explainability of an arbitrary couple (𝐴, 𝐵) depends of its characteristics w.r.t the ranking of the criteria which compose them in the ordering over the singleton states. For example, couples as (ac, bd) will always be explainable since a ≻ b and c ≻ d. However, it will be more difficult to decide for pairs like (ad, bc) or (ae, bcd) or (bde, acf).

RELATED WORK AND CONCLUSION

Recently, [START_REF] Marques-Silva | Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay[END_REF] have explored explanations in the context of decision of linear classifiers. They focus on PI-explanations (or sufficient reasons), that is, explanations providing reasons sufficient to explain a given decision, regardless of the value of other criteria [START_REF] Darwiche | On The Reasons Behind Decisions[END_REF][START_REF] Darwiche | On Quantifying Literals in Boolean Logic and its Applications to Explainable AI[END_REF], a strategy of explanation different from ours as mentioned in the introduction. Our view of explanations as cognitively bounded deductive proofs is reminiscent of the bounded proof systems proposed in the context of description logic [START_REF] Horridge | Toward Cognitive Support for OWL Justifications[END_REF]. Also, a similar step-wise approach has been studied in the context of constraint satisfaction problems [START_REF] Bogaerts | A framework for step-wise explaining how to solve constraint satisfaction problems[END_REF]. Finally, explanations based on axioms has been advocated in computational social choice [START_REF] Cailloux | Arguing about Voting Rules[END_REF][START_REF] Procaccia | Axioms Should Explain Solutions[END_REF]. In particular, the recent work of [START_REF] Boixel | A Calculus for Computing Structured Justifications for Election Outcomes[END_REF] also exploits axioms studied in voting theory to produce explanations for collective decisions, but applied to a different setting (voting), and using different proof techniques (tableau methods).

We propose a framework to explain comparisons stemming from an additive model. The framework comes with different schemes for reasoning with preferences, and we focus on a specific one: the covering scheme. Moreover, for cognitive purposes, we propose to restrict explanations to sets of atomic elements which prefer a pro over a group of cons, or a group of pros over a single con. The covering-based explanation engine with restricted sets of atomic elements is not complete, but empirical investigations show that explanations can be computed in a large proportion of cases.

Moreover, providing an argument scheme along with the result of a comparative statement opens the possibility to discuss or challenge this result. This is made possible through what is called critical questions [START_REF] Walton | Argumentation schemes for Presumptive Reasoning[END_REF], a tool associated with argument schemes representing attacks or criticisms that, if not answered adequately, falsify the argument fitting the scheme. This naturally leads to the long-term perspective of the interactive nature of the explanation process: these schemes should be integrated into a dialectical process, whereby the end-user should be able to contest [START_REF] Mulligan | Shaping Our Tools: Contestability as a Means to Promote Responsible Algorithmic Decision Making in the Professions[END_REF], while on the other hand the system should gain knowledge about the preferences of the user through an indirect elicitation process [START_REF] Ch | A Dialogue Game for Recommendation with Adaptive Preference Models[END_REF]. Smoothly interleaving explanation and recommendation calls for designing mixed initiative systems [START_REF] Horvitz | Uncertainty, Action, and Interaction: In Pursuit of Mixed-Initiative Computing[END_REF] where the user may be active in challenging the system, and the system adaptive in its responses.

Figure 1 :

 1 Figure 1: A proof of [(a, b), (c, f)] ⊢ 𝑐𝑝,𝑡𝑟 (aceg, befg)

  (a) Covering Scheme: proof diagram of Ex. 8 fg ≻ c 𝑐𝑝 --→ bfg ≻ bc b ≻ de 𝑐𝑝 --→ bc ≻ cde 𝑡𝑟 -→ bfg ≻ cde (b) Covering Scheme: a visual representation of Ex.8 Covering Scheme: a narrative representation of Ex.8

  r.t. preference. OBSERVATION 1. If the preference ≿ is transitive, then the transitive scheme is correct w.r.t. ≿ EXAMPLE 2. In Example 1, the premise belongs to ≿, as for (acg, bef) we have : 242 = 𝜔 𝑎 + 𝜔 𝑐 + 𝜔 𝑔 > 𝜔 𝑏 + 𝜔 𝑒 + 𝜔 𝑓 = 219, and for (bef, bfg): 219 = 𝜔 𝑏 + 𝜔 𝑒 + 𝜔 𝑓 > 𝜔 𝑏 + 𝜔 𝑓 + 𝜔 𝑔 = 204. However if we use the premise [(acg, abc), (abc, bfg)], this latter satisfies the transitive scheme but does not belong to ≿, since for (acg, abc), we have: 242 = 𝜔 𝑎 + 𝜔 𝑐 + 𝜔 𝑔 < 𝜔 𝑎 + 𝜔 𝑏 + 𝜔 𝑐 = 331 (see the score function 𝑤 in Sect.2).

  1. If the premises P = 𝑛 𝑗=1 (𝐴 𝑗 , 𝐵 𝑗 ) allow to prove the conclusion (𝐴, 𝐵) via the 𝑐𝑝 and 𝑡𝑟 schemes, then there is a list [𝑃 ′ 1 , . . . , 𝑃 ′ 𝑘 ] of comparative statements of P such that [𝑃 ′ 1 , . . . , 𝑃 ′ 𝑘 ] PROOF. By construction, the 𝑟𝑡 schemes subsumes the 𝑡𝑟 and 𝑐𝑝 schemes (so ⊢ 𝑡𝑟,𝑐𝑝 ⊂⊢ 𝑟𝑡 ), and particularizes a proof combining 𝑡𝑟 and 𝑐𝑝 derivations (so ⊢ 𝑡𝑟,𝑐𝑝 ⊃⊢ 𝑟𝑡 ). Moreover, chaining 𝑟𝑡 derivations is useless, because if 𝐿 1 𝐶), where & is list concatenation. Therefore, ⊢ 𝑟𝑡 =

	𝑟𝑡 --→ (𝐴, 𝐵) and 𝐿 2	𝑟𝑡 --→ (𝐵, 𝐶), then 𝐿 1 &𝐿 2	𝑟𝑡 --→
	(𝐴,

𝑟𝑡

--→ (𝐴, 𝐵). 𝑟𝑡 --→.

□

  If the preference ≿ is additive, then the decomposition scheme is correct w.r.t. ≿.Assuming that the preference ≿ is additive, and that both bc ≿ de and efg ≿ ac. From the first comparison, we deduce that 𝜔 b + 𝜔 c ≥ 𝜔 d + 𝜔 e ; from the second that 𝜔 e + 𝜔 f + 𝜔 g ≥ 𝜔 a + 𝜔 c . By summation, we derive 𝜔 e +𝜔 f +𝜔 g +𝜔 b +𝜔 c ≥ 𝜔 d +𝜔 e +𝜔 a +𝜔 c .

	EXAMPLE 6. Consider the following decomposition scheme:
	[(bc, de), (efg, ac)]	𝑑𝑒𝑐 ---→ (bfg, ad)

1 , 𝐵 1 ), . . . , (𝐴 𝑘 , 𝐵 𝑘 )] and a conclusion (𝐴, 𝐵) satisfy the decomposition scheme when each comparative statement (𝐴 𝑖 , 𝐵 𝑖 ) is disjoint and, for all items 𝑗 ∈ 𝐴 \ 𝐵, there are as many occurrences of 𝑗 in the sets 𝐴 1 , . . . , 𝐴 𝑘 as there are in the sets 𝐵 1 , . . . , 𝐵 𝑘 plus one; for all items 𝑗 ∈ 𝐵 \𝐴, there are as many occurrences of 𝑗 in the sets 𝐵 1 , . . . , 𝐵 𝑘 as there are in the sets 𝐴 1 , . . . , 𝐴 𝑘 plus one; and for any item 𝑗 neither in 𝐴 nor 𝐵, or both in 𝐴 and 𝐵, there are as many occurrences of 𝑗 in the sets 𝐴 1 , . . . , 𝐴 𝑘 as there are in the sets 𝐵 1 , . . . , 𝐵 𝑘 , i.e. ∀ 𝑗 ∈ [𝑚] 𝑘 ∑ 𝑖=1 |𝐴 𝑖 ∩ { 𝑗 }| + |𝐵 ∩ { 𝑗 }| = 𝑘 ∑ 𝑖=1 |𝐵 𝑖 ∩ { 𝑗 }| + |𝐴 ∩ { 𝑗 }| PROPOSITION 2.

  1 , 𝐵 1 ), . . . , (𝐴 𝑘 , 𝐵 𝑘 )] supports a conclusion (𝐴, 𝐵) if, and only if, the pros 𝐴 1 , . . . , 𝐴 𝑘 partition 𝐴 \ 𝐵 and the cons 𝐵 1 , . . . , 𝐵 𝑘 partition 𝐵 \ 𝐴.

	Definition 11 (covering scheme (𝑐𝑜𝑣)

  1 , 𝐵 1 ), . . . , (𝐴 𝑘 , 𝐵 𝑘 )] 𝐶), and we only need to prove the sets 𝐴 1 ,. . . , 𝐴 𝑘 , 𝐴 ′ 1 , . . . , 𝐴 ′ 𝑘 ′ , 𝐵 1 ,. . . , 𝐵 𝑘 , 𝐵 ′ 1 , . . . , 𝐵 ′ 𝑘 ′ are pairwise disjoint. We already know that the ⟨𝐴 𝑖 , 𝐵 𝑖 ⟩ and the ⟨𝐴 𝑖 ′ , 𝐵 𝑖 ′ ⟩ are pairwise disjoint. Moreover, the 𝐴 𝑖 are contained in 𝐴 \ 𝐵 while the 𝐴 ′ 𝑖 ′ are in 𝐵 \ 𝐶, so they do not intersect (same for the 𝐵 𝑖 and 𝐵 ′ 𝑖 ′ ). The only intersections left to consider are 𝐴 𝑖 ∩ 𝐵 ′ 𝑖 ′ and 𝐵 𝑖 ∩ 𝐴 ′ 𝑖 ′ . Suppose w.l.o.g. 𝐴 𝑖 ∩ 𝐵 ′ 𝑖 ′ ≠ ∅. Because of the syntactic constraints A we consider, this intersection is a singleton { 𝑗 }. We delete the comparative statements (𝐴 𝑖 , 𝐵 𝑖 ) and (𝐴 ′ 𝑖 ′ , 𝐵 ′ 𝑖 ′ ) from the premise, and replace them with the comparative statement

		𝑐𝑜𝑣 ---→	(𝐴, 𝐵)
	and [(𝐴 ′ 1 , 𝐵 ′ 1 ), . . . , (𝐴 ′ 𝑘 , 𝐵 ′ 𝑘 )] conclusion (𝐴, 𝐶) is yielded by applying the cover-𝑐𝑜𝑣 ---→ (𝐵, 𝐶). We show the
	ing scheme to some premise. It is easy to check that
	[(𝐴 1 , 𝐵 1 ), . . . , (𝐴 𝑘 , 𝐵 𝑘 ), (𝐴 ′ 1 , 𝐵 ′ 1 ), . . . , (𝐴 ′ 𝑘 , 𝐵 ′ 𝑘 )]	𝑑𝑒𝑐 ---→	(𝐴,

Table 1 :

 1 𝔐 𝑚, ≻ for 𝑚 ∈ [[4; 6]] ∀ ≻

		66.7%	66.7%	100%	3
	5	72.0%	80.0%	100%	25
	6	78.46%	84.62%	100%	130
	Table

Another aspect, not investigated here, is that it may not be adequate to fully disclose the model for privacy or manipulation issues.

This amounts to allowing the 𝑡𝑟 scheme to operate on the quotient set of congruent classes of comparative statements, instead of representative of those classes.

This decomposition scheme is less general than the so-called syntactic cancellative scheme described in[START_REF] Kh | Comparing options with argument schemes powered by cancellation[END_REF], as it does not allow for repetition of the conclusion. This has been shown to reduce expressiveness.


Amine Mechraoui
email: amine.mechraoui@gipsa-lab.inpg.fr

Zeashan Hameed Khan
email: zeashan-hameed.khan@gipsa-lab.inpg.fr

Jean-Marc Thiriet
email: jean-marc.thiriet@gipsa-lab.inpg.fr

Sylviane Gentil
email: sylviane.gentil@gipsa-lab.inpg.fr

Co-design for wireless networked control of an intelligent mobile robot

Keywords: Autonomous mobile robots, Networked control systems, Wireless network, 802.15.4 protocol, Horizontal handoff, TrueTime simulation

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

INTRODUCTION

Networked control systems (NCS) in mobile robotics are getting very popular today. With the rapid progress in communication techniques, especially the wireless networks, distributed control and decision have become mandatory to reduce the onboard processing overhead. It includes control, decision, obstacle avoidance etc; as it effects the battery consumption in miniature robots with space and weight as key design constraints. However, introducing a wireless network in the control loops presents some disadvantages such as band limited channels, sampling delays and packet dropouts [START_REF] Hespanha | A survey of recent results in networked control systems[END_REF]. Furthermore, the mobility of the robot also adds some problems, e.g. increasing the distance between the control station and the robot increases the number of lost packets due to decreased signal strength and increased bit error rate (BER) [START_REF] Zhu | Performance analysis of fast handoff with mobility prediction[END_REF]. The communication architecture in mobile robotics may be centralized, in which case there is a fixed or mobile node, which communicates with all the other nodes, or decentralized, where individual mobile nodes should ideally operate without any central control [START_REF] Schwager | Decentralized, adaptive control for coverage with networked robots[END_REF]. In the decentralized control scheme, each component solves a part of the problem and shares memory without having a global view of the mission. There is less emphasis on computation than communication. In distributed control systems, communication is an important parameter and individual components don't need to share memory [START_REF] Martinez | Motion coordination with distributed information[END_REF]. In related research work, many approaches have been used for distributed control of mobile robots. In [START_REF] Fierro | Practical point stabilization of a nonholonomic mobile robot using neural net-works[END_REF] the dynamic model of the mobile robot is controlled by means of neural networks. In [START_REF] Aicardi | Closed loop steering of unicycle like vehicles via Lyapunov techniques[END_REF] and (canudas de Wit and Sordalen, 1992), a nonlinear control approach has been introduced. Another research area, related to the hybrid architecture of control for autonomous navigation robots is studied in [START_REF] Benzerrouk | Toward an hybrid control architecture for a mobile multi-robot systems[END_REF]. The objective of this paper is to define a communication architecture for a mobile robot moving in a 2D space with several fixed stations (wireless infrastructure communication). According to the position of the robot, communication is possible in a specific coverage area with one or several stations (see Fig. 1). When several stations are reachable, the robot will choose one of the stations (Horizontal Handoff (HHO) strategy [START_REF] Wang | Network selection with joint vertical and horizontal handoff in heterogeneous wlan and mobile wimax systems[END_REF]) that can allocate sufficient resources to ensure a good level of communication. This comprises of optimal choice of payload and delay based on distance between robot and station and thus maintaining the necessary Quality of Service (QoS) in order to ensure that the Quality of Control (QoC) is sufficient (distributed control). When there is no station in the reachable space, the robot will have to be absolutely autonomous (embedded control), maintaining a sufficient QoC despite a degradation of the communication QoS. The QoC in wireless NCS is defined as the performance delivered by each closed-loop operation. Stability is the main property that must be guaranteed but control error and response time are also important to analyse. In the literature, many researchers have proposed a HHO strategy. They proposed making a decision by taking into account the Received Signal Strength (RSS), the power consumption and the cost of communication [START_REF] Chen | A smart decision model for vertical handoff[END_REF]. We propose to add the packet dropouts caused by the propagation delay or the distance and orientation between the robot and the station, which have a consequence on the QoC. The paper is organized as follows. The second section presents a brief description of the model of the Khepera robot, notably the kinematic model and the dynamic one. In the third section, the controller design is described and simulations of the tracking trajectory are presented. Section 4 presents the control over Zig-Bee wireless network and the influence of the integration of this network on control performance. After that, the proposed HHO architecture is described with one, two and three stations. Finally, the conclusion and perspectives are presented.

MODELING AND CONTROL

This section presents the study of a unicycle Khepera robot [START_REF] Lambercy | Khepera3 user manual version 2[END_REF]. Consider a unicycle robot (Khepera) as shown in Fig. 2. Let x, y and θ be the state variables where x ∈ ℜ and y ∈ ℜ are the Cartesian coordinates, θ ∈ [0, 2π[ is the robot's orientation with respect to the X-axis. We consider 'v' and 'ω' respectively as the linear and the angular velocities of the robot. The kinematic of the robot can be modeled as

ẋ = v cos θ, ẏ = v sin θ, θ = ω (1)
The kinematics model of the mobile robot has two control inputs ω le f t and ω right i.e. the left and right wheels velocities. These are related to the linear velocity v and the angular velocity ω of the robot according to the following equations

V right = v + Rω, V le f t = v -Rω (2)
where R is half the distance between the two robot's wheels. The dynamic model of the robot wheels is characterized by the equations of the DC motors driving the wheels. They are represented by a first order

model ω * (le f t,right) U = K τs + 1 (3)
where U is the voltage applied to the motor and ω * (le f t,right) are angular velocities generated by each motor. τ is the time constant (τ = 0.63s) and K is the gain (K = 5.3).

Controller Design

The objective of this section is to present how to control the robot to track any trajectory. Two levels of controllers are required. The first one is needed to control the angular velocities of the motors. PI controllers are implemented. The second one controls the linear and angular velocities of the robot. Let us consider the controller presented in [START_REF] Toibero | Switching control of mobile robots for autonomous navigation in unknown environments[END_REF], where the robot can reach a desired target point

[x d y d θ d ]. Errors are defined as x = x d -x, y = y d -y (4)
and the tracking error (Eq. 5a) and the orientation error (Eq. 5b) are calculated as

d = x 2 + y 2 (5a) θ = θ d -θ = tan -1 ( y/ x) -θ (5b)
According to [START_REF] Toibero | Switching control of mobile robots for autonomous navigation in unknown environments[END_REF], the following control actions are defined

v = v max 1 + |d| d cos( θ) (6a) ω = v max 1 + |d| cos( θ) sin( θ) + K θ tanh(k θ θ) (6b)
where v max is the maximum linear velocity that the robot can reach (v max = 0.3m/s) and K θ , k θ are constants. Those controllers are stable according to [START_REF] Toibero | Switching control of mobile robots for autonomous navigation in unknown environments[END_REF] using the Lyapunov candidate function V t .

V t = θ 2 /2 + d 2 /2 (7)

CONTROL OVER NETWORK

In this section, the controller is digitized and Zigbee wireless network is integrated (see Fig. 4). The effects of network on control system are analyzed.

WPAN 802.15.4

ZigBee is a specification for small, low-power digital radios based on the IEEE 802.15.4 standard for wireless personal area networks (WPANs). The low cost allows the technology to be widely deployed in wireless control and monitoring applications. The low power-usage allows longer life with smaller batteries. The mesh networking provides high reliability and larger range. The main reasons for adopting this wireless network in our application is its low power

Control over Zigbee

Control feedback loops are closed through a real-time network as shown in Fig. 4. To perform this study, the following conditions are considered:

• A bit rate of 250 kb/s for Zigbee in the physical layer.

• The sensor flow and the controller flow use 248 bits each. The sensor flow uses 3.3% and the controller one uses 3.3% of the network capacity with a sampling period T s equal to 30 ms. The sensor and control data are critical to keep the stability of the system, hence packet losses are undesirable. Practically, loss of packets cannot be entirely eliminated in wireless networks. A lot of methods e.g. Forward Error Correction (FEC) [START_REF] Kurose | Computer Networking: A Top-Down Approach Featuring the internet[END_REF] are proposed to reduce the probability of packet losses. The retransmission of lost packets is proposed too but for a real-time application, this is an inappropriate solution. When a packet has been discovered to be lost and is retransmitted, the sensors state evolve to a newer one and thus the retransmitted packet will be based on the old information and the calculated control will be wrong. The solution to ensure the best control is to do over sampling, with a sampling rate higher than what is needed, which therefore makes control more tolerant to packet losses. However, this solution increases the Use Request Factor (URF) and causes more packet delays and losses [START_REF] Mechraoui | Control of an intelligent robot system over a wireless network[END_REF]. The minimal sampling period to ensure a good QoC is 0.3 s in our example. To increase the QoC over wireless network and decrease the probability of losing packets of critical data, the sampling period of 30 ms is required. Fig. 5 shows that the robot can communicate with the station only within [START_REF] Wang | Policy-enabled handoffs across heterogeneous wireless networks[END_REF] describes a policy-enabled handoff system that allows users to express policies, based on the estimation of current network conditions and determining the best network at any moment by characteristics e.g. cost, performance and power consumption. (Nkansa-Gyekye and Agbinya, 2007) proposes a distributed additive weighting based VHO mechanism to reduce the processing overhead in the The challenge in handoff is to maintain the application session alive while the physical connection interface is changed. A generic weighted 'Network Rating Function' evaluation for each network is based on

STATION SELECTION

Handoff Decision

NRF i = W RSSI N RSSI,i +W NL N NL,i +W D N D,i (8)
W RSSI +W NL +W D = 1 (9) where W RSSI , W NL and W D are weighting functions of RSSI, network load (NL) and delay (D) respectively. N RSSI,i , N NL,i and N D,i indicate the scores of interface. NRF i is between 0 and 1. W i is the weight of the factor i, which emphasizes the importance of each contributing factor and N i, j represents the normalized score of the interface j for factor i .

The embedded logic in the mobile robot, assigns different "weights" to the handoff decision parameters in order to determine the level of importance of each parameter for the information to be exchanged between neighbors. In our case W RSSI > W NL > W D . The best station connection interface at any given moment is then chosen as the one that achieves the highest score among all candidate interfaces. In our scenario, factors within N i, j include QoS parameters i.e. the RSSI, the network load (NL) and Delay or latency (D) of the candidate network. Now we calculate NRF i and NRF j to choose accordingly (which ever is greater) the station that maximizes the decision criteria (Fig. 7). Additionally, there is a corresponding function for each term N RSSI,i , N NL,i , and N D,i , and the ranges of the functions are bounded between 0 and 1. The functions are given in Eq. (10).

N RSSI,i = e P r e P s (10a)

N NL,i = 1/e NL | 0 ≤ NL ≤ 1 (10b) N D,i = 1 if S i is the current station & RSSI > -48dBm 0 if not (10c)
In our case, the transmitted power is equal to -3dBm and the receiver signal threshold is equal to -48dBm.

The RSSI is calculed as follow

P r = 1 d α P s (11a) RSSI(dBm) = 10log(P r (mW )) (11b)
where P r and P s are the power in mW received and sent respectively. d is the distance between the two nodes in meters, and α is a parameter that can be chosen to model different environments. Fig. 8 shows the trajectory of the robot with changes in station if necessary (QoS is the best to ensure the best QoC). The stations positions are

• For the first station (S 1 ) (0, 5) (m)

• For the second station (S 2 ) (-3, 30)

• For the last station(S 3 ) (40, 35).

For this experiment, the weight values are W RSSI = 0.8, W NL = 0.15 and W D = 0.05. We assume that S 1 and S 2 have a common coverage area, and S 3 is far. According to the initial position of the robot (here (X 0 ,Y 0 , θ 0 ) = (0, 0, 0)) the robot communicates first with S1. It continues its trajectory until the robot detects the second station. In this case, Khepera executes Algorithm 1.

To understand this algorithm, symbols are used. is the mobile robot, S i is the current station, S {1,2,..k} are all the stations and S {m,...,n} are the stations that are detected by the robot. We note the fact that the robot detects a set of stations by the symbol .

When the robot is out of range of all stations, it keeps the last values of the angular and the linear velocities which is not a good solution because it can

Control Decision

As the robot moves outward towards another control station, the signal strength decreases. The low value of RSSI is sensed by the mobile robot, which then requests the station for an estimation of next way-point. The control station sends the trajectory information as well as broadcasts the "standby" message to all control stations in the infrastructure to minimize the time of connection of robot for the next cell. Thus, a PAN slot is reserved in advance for the coming robot as the trajectory is already estimated. This proposition permits to maintain a sufficient QoC despite a degradation of the QoS. The embedded control design is the same than the distributed one. The only difference is that the sampling period is changed. The controller computes control signals each 0.3 s. This change is very important to reduce the energy consumption and also

CONCLUSION

This work aims to study, in a co-design approach, the influence of a wireless network QoS on the QoC of a teleoperated robot. A wireless network based control of a unicycle mobile robot in a distributed infrastructure mode is described. The simulations are performed using Matlab/TrueTime toolbox. The problem faced was a loss of communication when the mobile robot moves out of range or there is an excessive network load that prohibits successful communication. The first strategy consists of adapting the network QoS to the control requirements. An algorithm for reconfiguration by HHO is proposed as a solution to maintain communication between control stations and the mobile robot in multi stations scenarios. The HHO is made with a criterion that takes into account the QoC for the robot as well as the QoS of wireless network.

The second strategy deals with the reconfiguration of the control, for the robot to be autonomous, when the communication link is out of order. Therefore, if the robot is out of range of all stations, the control mode is switched to embedded control, increasing the sampling period to reduce computations and the robot is completely autonomous. Integration of WLAN could be a choice for extended zone coverage for mobile robots. In the future work, a quantification of QoS and QoC will be dealt. A combination of infrastructure and adhoc architecture will also be investigated in order to maintain sufficient QoC in multi robots perspective.

Figure 1 :

 1 Figure 1: Problem description

FigureFigure 3 :

 3 Figure 2: Robot Model

Figure 4 :

 4 Figure 4: Control over Zigbee network

  TrueTime simulator is used to simulate Zigbee Network. Two tasks are programmed, the first is the controller task that generates the controller flow and the second one is a periodic sensor task that generates sensors flow. The controller task is event-triggered, which means that the controller calculates and sends the control signals V k and ω k when it has received all measures X k ,Y k and θ k . With the TrueTime Simulation of ZigBee Network, there is only the CAP period (Contention Access Period which uses CSMA/CA protocol), therefore there is no priority mode like CFP (Contention Free Period) which allows Guaranteed Time Slots (GTS) (see[START_REF] Van Den Bossche | Prototyping and performance analysis of a qos mac layer for industrial wireless network[END_REF] for more information about 802.15.4 protocol).

Figure 5 :

 5 Figure 5: Trajectory of the robot with one Zigbee station

Figure 6 :

 6 Figure 6: Network HHO strategy for a mobile robot control

Figure 7 :

 7 Figure 7: HHO state diagram

Algorithm 1 Figure 8 :

 18 Figure 8: Trajectory of the robot with HHO with NL=0

Figure 10 :

 10 Figure 10: Evolution of communication with different stations with HHO with NL=0 (corresponds to Fig.8)

Figure 12 :

 12 Figure 12: The trajectory of the robot with switching controller

Acknowledgements

This work is partially supported by the Safe NeCS project funded by the French Agence Nationale de la Recherche under grant ANR-05-SSIA-0015-03.