Abdullah Almaksour
email: abdullah.almaksour@irisa.fr

Eric Anquetil
email: eric.anquetil@irisa.fr

Solen Quiniou
email: solen.quiniou@synchromedia.ca

Mohamed Cheriet
email: mohamed.cheriet@etsmtl.ca

Personalizable Pen-Based Interface Using Life-Long Learning

published or not. The documents may come

Introduction

Applications with personalization capabilities become more and more of interest, to enable users to have applications that adjust to their needs and not the other way. Indeed, for a given application, various users may not all have the same set of interaction mechanisms (depending on a hierarchy of users, for example) or they may want to use them differently (for example, using a different mechanism to perform the same action). It is even more the case when using pen-based interfaces (like whiteboards or Tablet PCs) that provide handwritten interaction modalities. In such interfaces, each user writes and draws with his own style. Being able to adapt an initial handwriting recognition system to each user could then improve the interface usability. It can be par-ticularly interesting in the case of handwritten gestures that are associated to functionalities of an application, used to interact with electronic documents, for example. Indeed, gestures can be drawn differently from one user to another, and users may want to add or remove gestures, as long as they use the application (without having to define a priori the set of gestures that will be used). To achieve that, the recognition system has to be modified during its use in the application.

In this work, we aim at building a handwriting classifier which can be incrementally adapted and that will be used to recognize gestures, in an application designed for collaborative work. The challenge is to learn new unseen gestures on-the-fly, from scratch and using very few samples. Furthermore, the classification system has to remain robust and has to maintain its knowledge about the existing gestures, when introducing new unseen ones anytime during the lifelong learning process.

An incremental learning algorithm is defined in [START_REF] Polikar | Learn++: An incremental learning algorithm for supervised neural networks[END_REF] by the following criteria: it should be able to learn additional information from new data; it should not require access to the original data (i.e. data used to train the existing classifier); it should preserve previously acquired knowledge (it should not suffer from catastrophic forgetting, i.e. significant loss of original learned knowledge); and it should be able to accommodate new classes that may be introduced with new data. We can distinguish two main types of incremental learning algorithms: algorithms for parameter learning and algorithms for structure learning. The incremental learning of parameters can be considered as an "adaptation" algorithm. The structure in such systems is fixed and initialized at the beginning of the learning process, and the system parameters are learned incrementally according to newly available data. Some ex-amples of these systems are presented in [START_REF] Laviola | A practical approach for writer-dependent symbol recognition using a writerindependent symbol recognizer[END_REF][START_REF] Jang | Anfis: adaptive-network-based fuzzy inference system[END_REF]. Most of the structure incremental learning algorithms are based on the principle of the ART clustering algorithm [START_REF] Carpenter | The art of adaptive pattern recognition by a self-organizing neural network[END_REF], such as [START_REF] Sadri | A new clustering method for improving plasticity and stability in handwritten character recognition systems[END_REF][START_REF] Lughofer | Flexfis: A robust incremental learning approach for evolving takagi-sugeno fuzzy models[END_REF]. The main problem of these systems is that they are sensitive to the selection of the vigilance parameter, to the noise level in the training data, and to the order in which the training data is presented. A promised incremental clustering approach had been presented in [START_REF] Angelov | An approach to online identification of takagi-sugeno fuzzy models[END_REF], based on the Mountain Clustering algorithm (originally introduced in [START_REF] Yager | Learning of fuzzy rules by mountain clustering[END_REF]). The main idea of the proposed approach is that of a potential of a given point: it corresponds to a value representing the density in the data space at that point. The potential of a sample can be defined as the inverse of the sum of the distances between that data sample and all the other ones. Samples with high potential are then considered to be candidates to form a cluster. In this paper, we extend the recursive mountain clustering by combining it with a robust fuzzy adaptation method, and we use this hybrid algorithm to incrementally learn an evolving fuzzy rule-based classifier. Our system is used for the recognition of online handwritten gestures, and must be able to learn new classes of gestures and to evolve, sample after sample, without using all the old data. These new gestures, added by the final user, can be assigned to new commands or shortcuts in the pen-based interface, or to replace the default gestures assigned to existing commands. The advantages of our classifier are its simplicity and its adaptation ability that makes it suitable to our context, in which the system must learn rapidly and be operational and ready to be used at any moment during the lifelong learning process.

The remaining parts of this paper are as follows. In Section 2, the evolving classifier used to perform the lifelong gesture personalization is described, whereas the pen-based interface integrating it is presented in Section 3. Then, the results of the experiments of various personalization capabilities are shown in Section 4. Finally, Section 5 draws some conclusions.

Evolving fuzzy classifier

In this section, we first present the fuzzy classifier used. Then, we describe the incremental learning algorithm and the extension proposed, using a fuzzy adaptation method.

System architecture

Our system is based on a fuzzy rule-based classifier. The fuzzy rules make a link between intrinsic models (premises) and system outputs by consequent functions. For a 𝐾 classes problem, a rule 𝑅 𝑖 is built for each fuzzy model 𝑃 𝑖 :

𝑅 𝑖 : 𝐼𝐹 ⃗ 𝑥 𝑖𝑠 𝑃 𝑖 𝑇 𝐻𝐸𝑁 𝑦 1 𝑖 𝐴𝑁 𝐷 . . . 𝐴𝑁 𝐷 𝑦 𝑘 𝑖 ,
(1) where ⃗ 𝑥 is the n-dimensional feature vector, 𝑃 𝑖 is a fuzzy model (prototype) defined by a center ⃗ 𝜇 𝑖 and a covariance matrix 𝑄 𝑖 . The degree of membership of ⃗ 𝑥 to 𝑃 𝑖 is given by the Mahalanobis distance:

𝛽 𝑖 (⃗ 𝑥) = 1/(1 + 𝑑 𝑄𝑖 (⃗ 𝑥, ⃗ 𝜇 𝑖 )). (2)
For the consequent part, we can distinguish different structures [START_REF] Takagi | Fuzzy identification of systems and its applications to modeling and control[END_REF]: (i) the zero order Takagi-Sugeno (TS) with binary consequents (𝑦 𝑚 𝑖 = 1 if 𝑃 𝑖 belongs to class 𝑚, 0 otherwise), (ii) the zero order TS with constant consequents (𝑦 𝑚 𝑖 ∈ [0, 1] represents the participation of 𝑃 𝑖 in the description of class 𝑚), (iii) the first order TS, where the consequents are linear functions 𝑦 𝑚 𝑖 = ⃗ 𝑎 𝑚 𝑖 ⃗ 𝑥. Finally, the sum-product inference is used to compute the system output for each class:

𝑦 𝑚 (⃗ 𝑥) = 𝑅 ∑ 𝑖=1 𝛽 𝑖 (⃗ 𝑥) 𝑦 𝑚 𝑖 .
(3)

Incremental learning algorithm

In order to incrementally learn a fuzzy rule-based classifier in an on-line manner, we need, on the one hand, to evolve its structure by adding (or deleting) rules, and, on the other hand, to adjust its parameters (prototypes' centers, covariance matrices and the consequent parameters). The emphasis in this section is first placed on the learning of the premise part of the system. We aim at extending the recursive mountain clustering by combining it with a robust adaptation method that can constantly re-center the fuzzy prototypes and re-shape their influence zones, according to each single data sample.

Recursive mountain clustering

As mentioned earlier in Section 1, a recursive (on-line, one-pass, non-iterative) version of the mountain clustering method was introduced in [START_REF] Angelov | An approach to online identification of takagi-sugeno fuzzy models[END_REF]. The recursive formula avoids memorizing the whole previous data but keeps -using few variables -the density distribution in the feature space, based on the previous data:

𝑃 𝑘 (𝑥(𝑘)) = 𝑘 -1 (𝑘 -1)𝛼(𝑘) + 𝛾(𝑘) -2𝜁(𝑘) + 𝑘 -1 , ( 4
) where 𝑃 𝑘 (𝑥(𝑘)) denotes the potential of the 𝑘 𝑡ℎ data sample and with

𝛼(𝑘) = 𝑛 ∑ 𝑗=1 𝑥 2 𝑗 (𝑘), (5)
𝛾(𝑘) = 𝛾(𝑘 -1) + 𝛼(𝑘 -1), 𝛾(1) = 0, (6)

𝜁(𝑘) = 𝑛 ∑ 𝑗=1 𝑥 𝑗 (𝑘)𝜂 𝑗 (𝑘), (7)
where 𝜂 𝑗 (𝑘) = 𝜂 𝑗 (𝑘 -1) + 𝑥 𝑗 (𝑘 -1), 𝜂 𝑗 (1) = 0.

Introducing a new sample affects the potential values of the centers of the existing clusters, which can be recursively updated by:

𝑃 𝑘 (𝜇 𝑖 ) = (𝑘 -1)𝑃 𝑘-1 (𝜇 𝑖 ) 𝑘 -2 + 𝑃 𝑘-1 (𝜇 𝑖 ) + 𝑃 𝑘-1 (𝜇 𝑖 ) ∑ 𝑛 𝑗=1 ∥𝜇 𝑖 -𝑥∥ 2 𝑗 . ( 8
)
If the potential of the new sample is higher than the potential of the existing centers, then this sample will be a center of a new cluster (and a new fuzzy rule will be formed in the case of a fuzzy rule-based classifier). If the high potential sample is close to an existing center ⃗ 𝜇 𝑖 , then this sample will replace ⃗ 𝜇 𝑖 and no new cluster will be created.

Fuzzy vector quantization

As can be noted in section 2.2.1, the condition to have a high potential is a very hard one, and it is inversely proportional to the growing number of data. In this way, we can imagine a cluster center ⃗ 𝜇 𝑖 which is not really in the optimal center position (according to the data history), but that remains the center because it still has the highest potential value. Therefore, the incremental clustering process of the premise part of the fuzzy classifier will not be able to take advantage of the data points that do not have a very high potential, to move (or reshape) the existing clusters. We enhance the incremental clustering process (described in section 2.2.1) by an adaptation algorithm that allows the modification of all the fuzzy prototypes, by re-centering and re-shaping them for each new data point. For this purpose, we use a fuzzy version of the Vector Quantization algorithm [START_REF] Chung | Fuzzy competitive learning[END_REF]. In this method, the farther the normalized activation 𝛽 𝑖 of the premise of the rule 𝑖 is away from its objective score 𝛽 * 𝑖 , the more the prototype has to be moved:

⃗ Δ𝜇 𝑖 = 𝜆 * (𝛽 * 𝑖 -𝛽 𝑖 (⃗ 𝑥)) * (⃗ 𝑥 -⃗ 𝜇 𝑖 ) (9)
where the adaptation parameter 𝜆 lies between 0 and 1. The objective score 𝛽 * 𝑖 is 1 if the prototype 𝑃 𝑟 and ⃗ 𝑥 belong to the same class and 0 otherwise. In the same way, a fuzzy recursive formula is given in [START_REF] Backer | Texture segmentation by frequencysensitive elliptical competitive learning[END_REF], to update the inverse of the covariance matrix as follows:

𝑄 -1 𝑖 ⇐ 𝑄 -1 𝑖 1 -𝛼𝛿 𝑖 - 𝛼𝛿 𝑖 1 -𝛼𝛿 𝑖 ⋅ (𝑄 -1 𝑖 ⃗ 𝑑) ⋅ (𝑄 -1 𝑖 ⃗ 𝑑) 𝑇 1 + 𝛼𝛿 𝑖 ( ⃗ 𝑑 𝑇 𝑄 -1 𝑖 ⃗ 𝑑) ( 10
)
𝛿 𝑖 = 𝛽 * 𝑖 -𝛽 𝑖 (⃗ 𝑥) ( 11
)
where ⃗ 𝑑 = ⃗ 𝑥 -⃗ 𝜇 𝑟 and 𝛼 lies between 0 and 1.

Learning algorithm

The incremental learning algorithm of the consequent parameters depends on the type of the fuzzy system used. If we considered the three structures mentioned in Section 2.1: (i) no consequent learning is needed for the simple structure with binary consequents; (ii) for the second structure, an online estimation of the constant consequents is presented in [START_REF] De Barros | On-line identification of computationally undemanding evolving fuzzy models[END_REF]; and (iii) the linear consequents learning problem in a first-order TS can be solved by the weighted Recursive Least Square method (wRLS) [START_REF] Angelov | An approach to online identification of takagi-sugeno fuzzy models[END_REF]. The complete learning algorithm can be summarized by Algorithm 1.

Personalizable pen-based interface using gestures

Context

This work is part of the ICIOS project, which is a project between the Sychromedia laboratory of the Ecole de Technologie Supérieure (ETS) in Montreal, Canada, and the Imadoc team project of the Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA) in Rennes, France. The aim of this project is to integrate handwritten interaction capabilities into the Synchromedia platform, an infrastructure that already integrates other modalities (audio, video, text) to support collaborative work in telepresence, so as to improve the usability of the platform by the various users that take part to a collaborative work session (collaborative applications may include virtual classrooms, ehealth, or meeting using videoconference). The handwritten interaction is based on digital ink, acquired on whiteboards or Tablet PCs. The digital ink can correspond to annotations on electronic documents shared by the various users, or to gestures associated to commands and used to manipulate the documents (zoom, rotation, or flip, for example) or the annotations (copy, cut, paste, or delete, for example). In the latter case of digital ink corresponding to gestures, the set of gestures considered may differ according to the collaborative task (ehealth or virtual classrooms, for example), the nature of the underlying documents (an X-ray image or a course pdf document, for example), or even each user. Here, we focus on offering each user gesture-based personalization capabilities. The personalization process can be invoked independently by each user, anytime during a collaborative session (using the evolving classifier presented in Section 2), and will persist from one session to another. The personalization capabilities considered here are described in the following sub-section.

Personalization capabilities for gestures

There are 2 options to personalize the gestures of a user that are considered here:

• adaptation to the user style;

• addition of a new gesture, associated to a functionality of the application.

The first personalization option enables the recognition system to adapt to the way the user draws the gestures that this system has already learned. The second personalization option allow users to add a gesture to a functionality that did not have an associated gesture, or even to add another gesture to a functionality which already possesses a gesture. In the first case, a user may want to add a gesture to a functionality he uses a lot and that did not have an associated gesture (it may also be due to the fact that the functionality may have been added afterwards). In the latter case, a user may add a new gesture that he considered to be better than the previous one (better to remember, to draw, or to recognize, for example). It may also be useful if two users are sharing the same whiteboard and they want to use different gestures for the same functionality.

Experiments and results

In this section, we present the handwritten gesture database and the experimental setup used in the experiments. Then, the results of the experiments conducted on the various personalization capabilities, using the presented evolving classifier, are described.

SIGN: on-line gesture database

The following experiments were performed on the SIGN database, which contains on-line handwritten gestures. The data collection sessions were performed at the Synchromedia laboratory, and at the Imadoc team project. It is composed of samples for 17 different gestures, drawn by 20 writers on Tablet PCs. Each writer has performed 4 acquisition sessions: each session starts with drawing each gesture 5 times, and then gestures to draw are presented in a random order to the writer, to simulate the use of an application. So each writer draws each gesture 25 times during each session. Thus, each writer has drawn each gesture 100 times, which leads to having 1,700 gestures in each writer-specific gesture dataset, and totally 34,000 gestures. The database (with additional information on the data) can be downloaded freely [1]. gestures initially assigned to the basic functionalities of the application) and a secondary set (corresponding to gestures that could be incrementally associated to the functionalities of the application). The initial gesture set contains 5 gestures, as shown in Figure 1(a). The first gesture (called snail) is used to call a contextual menu that will allow the user to change the properties of the digital ink, or to switch between the ink and gesture modes. The other gestures are associated to basic operations on digital ink (drawn after selecting the ink to consider), i.e. deleting, cutting, copying, and pasting the selected ink strokes (gestures are depicted in this order, in Figure 1(a)). The secondary gesture set contains 10 gestures, as shown in Figure 1(b). These gestures can be assigned to the previous ink editing functionalities, or to other functionalities on ink strokes or on the underlying document, like rotation, flip, or zoom.

Gestures and functionalities considered

Experimental setup

In order to emulate a real context, we suppose that the classification system is pre-trained on "batch" mode (phase A), on the initial gesture set, using a writerindependent dataset; these gestures are supposed to be assigned to the main functionalities. Then, after the interface has been delivered to its specific user, the personalization process (phase B) starts using the incremental lifelong learning. This incremental learning includes, on one hand, the adjustment of the learning of the initial gesture set, using the newly available writerdependent data (i.e. adaptation) (phase B1), and, on the other hand, the learning of new gestures according to the user needs (phases B2 to B5). Figure 2 shows three use cases that correspond to various user personalization behaviors that we consider in the experiments.

Each gesture is described by a set of 21 features. The presented results are the average of results of 20 different tests for the 20 writers. For each experimental run, we use the datasets of 19 writers for the writer-independent learning phase and one writerspecific dataset for the personalization phase. In order to get the results unbiased by the data order effect, we repeat the experiment for each writer 40 times with different random data orders and the mean results are considered. We used about half of the database for the incremental learning process and the rest is used to estimate the evolution of the performance during the learning process. Two fuzzy incremental learning models are compared in these experiments: (a) Model I (section 2.2.1), i.e. evolving zero-order TS classifier with binary consequents and recursive mountain clustering learning, and (b) Model II (section 2.2.3) i.e. our extended version in which we integrate the fuzzy vector quantization algorithm (section 2.2.2) in the incremental learning process. The parameters 𝜆 and 𝛼 are set to 0.005 and 0.001 respectively.

Results

Figure 3 shows the experimental results for the three use cases. We first note that the adaptation phase (B1) enhances the system performance for the default ges- ture set thanks to the writer-specific learning data. Secondly, we note that the average recognition rate during the incremental learning process (B2-B5) is about 95% when using Model II, while it is about 86% using Model I. These results show that integrating the premise adaptation in our model enhances significantly the performance in the incremental learning process, and decreases the error rate by about 65%. We note also the good stability of the model when introducing new unseen classes. Thus, for the three considered scenarios, the recognition rate does not go below 90% even when adding a new gesture.

Conclusion and future work

In this paper, we have presented an incremental learning algorithm for fuzzy-based classifiers. The proposed classifier was used as a gesture recognition system that enables user personalization capabilities, when integrating into a pen-based application. The dynamic nature of these classifiers allow them to adapt to each user style as well as to the addition of new unseen classes, without destroying the already learned ones. Experiments considering gesture-based personalization scenarios showed the robustness of this approach.

Future work will focus on human-computer interaction purposes. First, we will investigate the integration of the gesture recognition system into a real pen-based application (as mentioned in section 3), especially on how to provide the correct label of each drawn gesture to the lifelong learning process. Indeed, when there is a recognition error made by the system, the user will have to provide the correct label to the gesture that was drawn. So, we will focus on designing approaches that will enable the user to correct the recognition result so that they would be as user friendly as possible. Helping the user in its choice of new gestures would also be of interest. In that case, we could give to the user informa-tion on possible confusions between the new gestures he wants to add and the existing ones, so as to optimize the usability of the gesture-based application.

Figure 1 .

 1 Figure 1. (a) Initial gesture set, and (b) secondary gesture set

Figure 2 .

 2 Figure 2. Various user personalization behaviors

Figure 3 .

 3 Figure 3. Results for the three different scenarios.

In this section, we present the application integrating the incremental learning classifier as well as the gesturebased personalization capabilities considered.


Fabio Gómez-Estern

Carlos Canudas-De-Wit
email: carlos.canudas-de-wit@gipsa-lab.inpg.fr.

Francisco R Rubio
email: rubio@esi.us.es

Adaptive Delta Modulation in Networked Controlled Systems with bounded disturbances

Keywords: Differential Coding, Delta Modulation, stabilization of Networked Control Systems. I

This paper investigates the closed-loop properties of the differential coding scheme known as Delta Modulation (∆-M ) when used in feedback loops within the context of linear systems controlled through a communication network. We propose a new adaptive scheme with variable quantization step ∆, by defining an adaptation law exclusively in terms of information available at both the transmitter and receiver. With this approach, global asymptotic stability of the networked control system is achieved for a class of controllable (possible unstable) linear plants. Moreover, thanks to the globally defined switching policy, this architecture enjoys a disturbance rejection property that allows the system to recover from any finite-time unbounded disturbance or communication loss.

∆ can be regarded as the quantization step. This paper proposes an adaptive extension a of fixedgain differential coding scheme previously introduced by the same authors (see [START_REF] Canudas-De-Wit | Differential coding in networked controlled linear systems[END_REF]) in the context of linear systems interconnected through some transmission network.

The selection of ∆ is a crucial issue on the quality of the decoded signals. It is well known in digital communications framework that large values of ∆ will result in a high granular noise, while too small values of ∆ will result in slope-overload distortion. In closed-loop configurations, as in the scenarios considered here, the choice of ∆ is even more important because it may cause instability. The closed-loop stability properties of Delta Modulation coding with fixed or scheduled gains, has been studied in [START_REF] Canudas-De-Wit | Differential coding in networked controlled linear systems[END_REF], [START_REF] Lopez | Compensation schemes for a delta-modulation-based ncs[END_REF], [START_REF] Canudas-De-Wit | Energy-aware 3-level coding and control co-design for sensor network systems[END_REF].

Delta modulation (∆-M ) algorithm can also be understood as the coarsest two-level (1bit) quantizer. Thus, this technique is a simple alternative to approaches concerning the use of quantizers in the context of NCS, i.e. [START_REF] Ishii | Remote control of lti systems over networks with state quatization[END_REF], [START_REF] Mitter | Stabilization of linear systems with limited information[END_REF], [START_REF] Liberzon | On stabilization of linear systems with limited information[END_REF], [START_REF] Lemmon | Control system performance under dynamic quatization: the scalar case[END_REF], [START_REF] Wei | Numerical study of joint quatization and control under block-coding[END_REF], [START_REF] Li | Robust quatization for diginal finite communication bandwidth (dfcb) control[END_REF], [START_REF] Girish | Stabilizability of stochastic linear systems with finite feedback data rates[END_REF] among others.

For a Delta Modulation scheme with constant quantization step ∆ it was shown in [START_REF] Canudas-De-Wit | Differential coding in networked controlled linear systems[END_REF] that only a limited domain of attraction was obtained. In addition, the state was only guaranteed to converge asymptotically to a finite ball, being its size related to the parameters of the open-loop plant, and to the user-defined parameter ∆.

By making ∆ an adaptive quantity, more effective schemes of ∆-modulation have been already proposed in the communications community [START_REF] Proakis | Digital Communications[END_REF]. The idea is to design an update law for ∆, defined exclusively in terms of the information available both at the receiver and transmitter, aiming at improving the resolution of the differential coding by reducing the gain ∆ for slowly varying signals, while enlarging ∆ in case of rapid change of the input, and hence allowing for faster signal tracking and higher bandwidth of the transmitted signals. So far in the communications field, adaptation laws for ∆ have been proposed under somewhat heuristic criteria, as little information is supposed to be available on the dynamics of the signal source. However, when dealing with feedback systems, the dynamical properties of the plant become very useful in designing the adaptive law. This problem, to which this paper is devoted. is framed as shown in Figure 1.

The main paper contribution is the introduction of an adaptation mechanism consisting of varying the quantization interval ∆ in terms of a minimal amount of information available at the transmitter and the receiver. This type of adaptation law, although well known in the communications field, is used and analyzed for the first time a feedback configuration shown in Figure 1. It is also shown that this adaptive coding structure, modified as proposed in [START_REF] Canudas-De-Wit | Differential coding in networked controlled linear systems[END_REF],

is proven to yield closed-loop global asymptotic stability for a class of open-loop unstable linear systems. We provide also a comparison between our approach and existing ones, in order highlight the main advantage: a disturbance recovery property that guarantees that if the system state is driven temporarily away from the origin, due to some unattended unbounded finite-time disturbance, or possibly loss of communication, the system will ultimately stabilize the estimation error, and drive the state back to the origin. This is due to the globally defined switching policy (and not only in one time sense as happens in most of the referenced papers), and also allows a free initialization of the encoder without any previous information of the state.

The results are presented in scalar form. The extensions to higher dimension are easy to develop in the case of diagonalizable system matrices, and will be spared for the sake of space.

However, for non-diagonalizable systems, the analysis is involved, and the technical details have been presented in [START_REF] Canudas-De-Wit | Delta modulation for multivariable centralized linear networked controlled systems[END_REF] for the fixed Delta Modulation algorithm, while the adaptive version is part of an ongoing research work.

II. ADAPTIVE ∆-M CODING SCHEME

The problem setup will be initially presented, and the fixed-step Delta Modulation networked controller [START_REF] Canudas-De-Wit | Differential coding in networked controlled linear systems[END_REF] will be briefly recalled for the sake of completeness. Then we propose a ∆adaptation law resulting in a global asymptotic convergence of the state estimation error and system states to zero. This is a significant achievement with respect to the fixed-gain scheme presented in [START_REF] Canudas-De-Wit | Differential coding in networked controlled linear systems[END_REF].

A. Assumptions

In the following, we will assume that the transmitted information is binary δ k ∈ {-1, 1}, that only sensor-to-controller transmission is allowed, that a 100% reliable noiseless channel without transmission delays is used, and that the data is sent at a fixed rate (we select the sampling frequency in order to transmit only one δ k at a time).

B. Problem Setup

Consider first the following one-dimensional discrete time-system, together with the control law, and the fixed-step differential coding law: Open-loop system, and encoder: Control law and decoder: x k arrives at the encoder, it is compared to the prediction xk , and its difference is coded on a binary basis, i.e. the value of sgn(x k -xk ) is coded and transmitted as a binary digit. Stability of this system has been analyzed in [START_REF] Canudas-De-Wit | Differential coding in networked controlled linear systems[END_REF]. Although it has interesting disturbance rejection properties, the main limitation of this approach is the fact that stability is semiglobal, in the sense that the quantization step must be chosen as a function of an upper bound of the initial state. This is a quite frequent fact in the literature (see [START_REF] Liberzon | On stabilization of linear systems with limited information[END_REF]), and has been tackled (in that paper) by devising open-loop initialization mechanisms for estimating that bound. Another issue (also shown in [START_REF] Canudas-De-Wit | Differential coding in networked controlled linear systems[END_REF]) is that using fixed-step Delta Modulation, the state does not converge strictly to zero, but to a finite ball around the origin, whose radius is proportional to ∆ (there is chattering in steady state). As a consequence, when the gain ∆ is fixed, there is an inherent trade-off between stability and precision. This motivates our search for other coding strategies with variant gains, as shown next.

x k+1 = ax k + bu k (1) xk+1 = [a -bK]x k + ∆ • δ k (2) x0 = 0, δ k △ = sgn(x k -xk ) xk+1 = [a -bK]x k + ∆ • δ k (3) u k = -K xk (4)

C. Adaptation law design

Adaptive ∆-modulation in Digital Communications aims at improving the resolution of the differential coding scheme according to the size of the signals to be transmitted. In our case this signal is the system state, hence a reasonable approach is to enlarge ∆ for large values of the estimated states, and decrease it for smaller values. Another requisite is the Equi-Memory property described in [START_REF] Tatikonda | Control under communication constraints[END_REF], which suggests that the quantization step must be the same at the transmitter and the receiver at any time. Hence, the adaptation law must be defined exclusively in terms of the shared information, i.e. of {δ 0 , δ 1 , . . . , δ k }. Another condition is to keep the adaptation law as simple as possible, and also minimize its memory usage. With that aim we will propose a very heuristic and simple approach, and will further provide a detailed analysis to prove that it guarantees global asymptotic stability. In order to design an ∆-adaptive mechanism to achieve global asymptotic stability two opposite behaviors must be observed in the analysis of [START_REF] Canudas-De-Wit | Differential coding in networked controlled linear systems[END_REF]. For large values of the estimation error x, there is probably slope overload, so ∆ k should grow at a higher rate than the plant escape velocity. When the state is trapped into a domain of attraction for the present ∆ k , the step size must decrease (for improving resolution) at a slower rate than the state convergence in order to prevent it from getting too small relative to the state.

From this intuition, an adaptive scheme with minimal storage and computation requirements is proposed as follows:

1) If δ k = δ k-1 then the state is assumed to be escaping, thus ∆ k must be increased.

2) If δ k = δ k-1 then the state is assumed to converge (oscillations close to zero) and ∆ k must be decreased.

The following update law is proposed:

∆ k+1 = φ k+1 ∆ k (5)
φ k+1 =      λ + if δ k = δ k-1 λ -if δ k = δ k-1 (6)
where 0 < λ -< 1 is the exponential decay rate of ∆ k , and λ + > 1 is the exponential growth rate.

The proposed algorithm is shown in Fig. 2. This adaptation law can be seen as a generalization of Jayant's adaptation rule (1970) (see [START_REF] Proakis | Digital Communications[END_REF]).

April 1, 2011 DRAFT

+ - 1 -1 1 z-a c 1 z-a c ∆ k ∆ k ∆ 0 ∆ 0 ∆ k+1 = φ k ∆ k ∆ k+1 = φ k ∆ k xk xk x k × × φ k φ k gain selection gain selection channel x k+1 = Ax k + Bu k -K xk δ k = ±1 δ k = ±1 xk

D. Error equations

The complete feedback system with the adaptive delta Delta Modulation coding scheme is then: Open-loop system [START_REF] Liberzon | On stabilization of linear systems with limited information[END_REF], and encoder ( 8)- [START_REF] Li | Robust quatization for diginal finite communication bandwidth (dfcb) control[END_REF]:

Decoder ( 11)-( 13) and control law ( 14):

x k+1 = ax k + bu k (7) xk+1 = [a -bK]x k + ∆ k • δ k (8)
∆ k+1 = φ k+1 ∆ k (9)
φ k+1 =      λ + if δ k = δ k-1 λ -if δ k = δ k-1 (10)
x0 = 0, ∆ 0 > 0 freely assigned xk+1 = [a -bK]x k + ∆ k • δ k (11)
∆ k+1 = φ k+1 ∆ k (12)
φ k+1 =      λ + if δ k = δ k-1 λ -if δ k = δ k-1 (13)
u k = -K xk (14) x0 = 0, ∆ 0 > 0 same as encoder
With the above definitions, the closed-loop error dynamics become

xk+1 = ax k -∆ k • δ k ∆ k+1 = φ k+1 ∆ k , ∆ 0 > 0 (15)
φ k+1 = λ -+ 1 2 (λ + -λ -) |δ k+1 + δ k |
The causality of the system is guaranteed because the computation of xk+1 is only based on xk and older values. The following Theorem states the stability of the closed-loop system.

E. Main result (stability analysis)

Theorem 1: The error trajectories xk of system [START_REF] Brockett | Quantized feedback stabilization of linear systems[END_REF], resulting from the adaptive ∆-modulation coding scheme ( 7)-( 14), globally asymptotically converge to zero as k → ∞ if there exist parameters λ + > 1, λ -∈ (0, 1) satisfying the following inequalities:

λ + > a (16) λ -< (λ + ) -β 2 , (17)
where

β(a, λ -, λ + ) △ = 1 + log ρ 1 + a (a -λ -) (ρ -1) (λ -) 2 and ρ △ = λ + a
Moreover, ∆ k and hence x k also converge to zero regardless the initial conditions (x 0 , ∆ 0 ).

Proof: The claim will be proved in two steps. First, a new variable will be defined in order to capture the ratio between xk and ∆ k , namely y k △ = xk /∆ k , and boundedness of that variable will be proved. Secondly, it will be shown that ∆ k asymptotically converges to zero. Consequently, the convergence of xk towards the origin is directly implied. Along the trajectories of (15), the variable y k evolves along the dynamics

y k+1 = 1 φ k (ay k -sgn(y k )) . ( 18
)
Fact 1. Trajectories of y k cross the zero axis in finite time.

This means that starting from any initial condition, x0 and ∆ 0 , and thus y 0 , there must be a future time k 0 < ∞ such that y k 0 -1 • y k 0 < 0. This is easily shown by imagining a trajectory with no zero crossings on y k (hence on xk as ∆ k is always positive). Assuming initially positive

x, i.e. starting from y 0 > 0, we have y k+1 = 1/λ + (ay k -1) and hence

y k+1 -y k = 1 λ + (ay k -1) -y k = a λ + -1 y k - 1 λ + < - 1 λ +
for the given choice of λ. Then, starting from y 0 > 0, we have y k < y 0k/λ + and hence there is some constant k 0 ≤ y 0 λ + such that y k 0 -1 > 0 and y k 0 < 0. Due to the symmetry of the system equations, a similar argument applies if the trajectory starts from y 0 < 0.

Fact 2. Trajectories of y k are bounded after finite time.

Immediately after a zero crossing of the system (assuming + to -without loss of generality), y k 0 is bounded as follows

y k 0 = 1 λ + (ay k 0 -1 -1) > - 1 λ + (19)
hence |y k 0 | < 1 λ + , as y k 0 < 0. Now if we search for bounds on subsequent samples we must update the growth factor of ∆ to λ -and compute y k 0 +1 = 1/λ -(ay k 0 + 1), which is positive, as from the bound 0 > y k 0 > -1/λ + we have

y k 0 +1 > 1 λ -- a λ + + 1 > 0.
Moreover, |y k 0 +1 | < 1/λ -. These observations are summarized in Fig. 3, where the necessity of two zero crossings after a set of positive values is illustrated, as well as the upper bounds inferred by the switching dynamics. Now as the switching policy is second order, the analysis is concluded by taking one further step. Using 0 < y k 0 +1 < 1/λ -, we have y k 0 +2 = 1/λ -(ay k 0 +1 -1), and hence

- 1 λ -< y k 0 +2 < 1 λ - a λ --1 ,
As illustrated in Fig. 3 (left), two situations (a) and (b) are then identified, (a) -1 λ -< y k 0 +2 < 0. This situation (including the norm bound) is exactly the one found at instant k 0 + 1, then it has been already considered (b) y k 0 +2 > 0. Then, we have two subsequent positive samples, i.e. the situation of y k 0 -1 is recovered. In that case, the dynamic equation turns into (19) and along it the map y k → y k+1 is contracting, hence the norm will decrease until a future sign change.

The previous analysis yields that after the first sign change, the state y k remains bounded as

|y k | < 1 λ - a λ --1 (20)
With the above facts, the proof of the proposition reduces to show asymptotic convergence to zero of ∆ k , and hence concluding convergence of the state x. With this objective we will use the following definition, Definition 2.1: Given a sequence of positive (negative) samples of y k , the fly-time is the number of sampling instants elapsed between the two zero-crossings that enclose the signal. For its computation, the first and the last positive (negative) samples are considered. This magnitude is viewed in Fig. 3 (right). We will compute a non-conservative upper bound on it. Indeed, considering y 0 as the first positive sample (i.e. resetting the time count), we have along the dynamics (19),

y k = ρ k y 0 - 1 a ρ k -1 ρ -1 (21)
then, the zero crossing occurs at the next sampling instant after the time the right hand side of this equation vanishes. Therefore, the fly-time k * is bounded as

k * ≤ 1 + log ρ (1 + y 0 a(ρ -1)) ≤ 1 + log ρ 1 + a (a -λ -) (ρ -1) (λ -) 2 = β(a, λ -, λ + )
for which we have used the finite-time bound on y k (and hence y 0 ) computed in (20). On the other hand, the duration of a full flying period equals the number of times the ∆ factor is increased as ∆ k+1 = λ + ∆ k , then the net value of ∆ after the flying period, starting from ∆ 0 is

∆ k = (λ + ) k ∆ 0 .
Hence a condition for asymptotic convergence of ∆ k to zero is that, on zero crossings, the net decrease in ∆ compensates the net amount increase over the flying period. This is guaranteed by choosing λ -such that, (considering k 0 as the first negative sample, again as in Fig. 3)

∆ k0+2 = (λ -) 2 ∆ k0 < (λ -) 2 (λ + ) β ∆ 0
where the power in (λ -) 2 has been introduced using the fact that after a flying period, two consecutive zero crossings must occur (see argument of Fact 2). This gives a less restrictive condition on λ -. Hence, the condition for a net reduction of ∆ after a flying period is

∆ k0+2 < ∆ 0 ⇐ (λ -) 2 (λ + ) β < 1,
or, equivalently, λ -< (λ + ) -β 2 which is the condition (17) stated at the Proposition. From the net convergence of ∆ k to zero and the boundedness of y k , we conclude that lim k→∞ xk = 0.

This completes the proof.

In the related literature, some authors have dealt with noisy systems with limited data rates, such as [START_REF] Girish | Stabilizability of stochastic linear systems with finite feedback data rates[END_REF]. In that paper, variable length coding is used for stochastic stabilization in the mean square sense. Our approach can also handle the presence of noise in the system dynamics if a minor change in the switching policy is introduced.

Corollary 1: If system ( 1) is perturbed with a state noise w k such that |w k | < W , as in

x k+1 = ax k + bu k + w k
and the same coding-control strategy is applied, with the introduction of a lower bound on ∆ k , i.e., substituting the ∆-switching policy by

∆ k+1 =      φ k+1 ∆ k if φ k+1 ∆ k ≥ ∆ min ∆ min otherwise (22)
where ∆ min > W ; then, the error xk is ultimately bounded as

|x k | < λ + k * ∆ 0 a(λ -) -2 1 + W ∆ min
where

k * = 1 log ρ log   λ + y 0 1 -W ∆ k  
Some details of the proof will be skipped for the sake of space and reported elsewhere. The main argument stems from observing that the evolution of y k is no longer (18), but

y k+1 = 1 φ k ay k -sgn(y k ) + w k ∆ k (23)
whose solution along a flying period starting at y 0 (without sign change of y k ) becomes

y k = a λ + k y 0 + 1 λ + k i=0 a λ + i v k-i where v k △ = w k ∆ k -1.
The zero crossings of y k are still guaranteed thanks to the new lower bound on ∆ k and the flying period is limited by k * .

Finally, an analysis similar to the noiseless case leads to the bound on xk given in the corollary.

Moreover, the closed loop system with nonzero error xk becomes a stable system with a bounded input disturbance perturbation, hence giving a steady state error that is proportional to W .

III. DATA RATE LIMITS

Theorem 1 solves the stabilization problem in networked control systems using adaptive Delta Modulation with no restriction on the data rates, apparently in contradiction with the theoretical limits of [START_REF] Tatikonda | Control under communication constraints[END_REF]. In fact, conditions ( 16)-( 17) establish implicitly a constraint between the required data-rate for stabilization and the maximum open-loop eigenvalue of the system.

Actually both parameters are embedded in the constant a.

This value, proceeding from the sampling of a continuous system in the form ẋ = λ cont x + B cont u cont , takes the form a = e λcontTs . In a one-bit per sample modulation scheme, which is the case of Delta Modulation we have a = e λcont/R where R is the data rate in b.p.s. Now, as an upper bound in a will result in an upper bound in the ratio λ cont /R, we will investigate what is the maximum value a max such that for all a < a max there exist valid choices of parameters λ + and λ -fulfilling ( 16)-(17).

A detailed numerical analysis of that inequality yields that for a ≤ 1.2 there are values of λ + and λ -that solve the equation. Conversely, for values of a ≥ 1.3226 no solution has been found numerically. Moreover, as the right hand side of (17) decreases with a, there will be no more solutions for greater a. An analytical result supporting these facts is presented next.

A. Conditions for solving the parameter tuning equation (17)

The following proposition states the limits of Theorem 1 in terms of the minimum datarate required for stabilizing a system given its continuous-time open-loop eigenvalues, using Adaptive Delta Modulation. Moreover, as the tuning parameters λ -and λ + must be obtained by solving (numerically) the implicit equation ( 17), finite intervals are provided for scanning those solutions.

Proposition 1: Consider (7) as a result of sampling a continuous-time system ẋ = λ cont x + B cont u cont , with sample time T s = 1/R and Adaptive Delta Modulation one-bit state coding as [START_REF] Hespanha | Towards the control of linear systems with minimum bit-rate[END_REF]. Then, a sufficient (possibly conservative) condition for closed-loop stability with feedback u = K x where x is the output of the decoder is R > λ cont / log(1.3226) bits per second.

Moreover, a less conservative search for the tuning parameters λ + and λ -satisfying (17) is to be carried out numerically scanning the finite interval

λ -∈ (0, 1)] ×   λ + ∈   a, a 1 + 1 + 4 a(a-1)
log λ - log λ + < - 1 2   1 + log 1 + a(a-λ -)(ρ-1) (λ -) 2 log(ρ)   .
Now a sufficient condition for its solution is obtained by taking limit 1 as ρ → 1 + , which gives

log λ -< - log a 2 1 + a(a -λ -) (λ -) 2 , ⇔ (λ -) 2 log λ -< - log a 2 (λ -) 2 + a 2 -aλ -) .
The left hand side of the last expression is minimized to -0.1839 at λ -= 0.6070. Substituting this value in the right hand side, we have the inequality -0.183 < -(log a)/2 (a 2 -0.6070a + 0.6070 2 )

that is fulfilled by values of a below 1.3226. This means that if a is below that value, then we can find tuning parameters λ -= 0.6070 and λ + close enough to a (from the limit as ρ → 1 + ) such that (17) holds and the coding scheme can be implemented. Now from the relation between the discrete and continuous-time formulation, the relation R > λ cont / log(1.3226) is implied.

(Parameter search interval) If the sufficient condition on the data rate (for which the parameter tuning procedure is given above) is not satisfied, (17) might be solved numerically. To this end, a finite interval for the tuning parameters will be obtained by analyzing necessary conditions for (17), also rewritten as

log λ -< - 1 2 log λ + log(ρ) log(ρ) + log 1 + a(a -λ -)(ρ -1) (λ -) 2 ,
for which, as λ + > ρ, it is necessary that

log λ -< - 1 2 log(ρ) + log 1 + a(a -λ -)(ρ -1) (λ -) 2 , ( 25
)
and the right hand side of this expression is upper bounded by r.h.s. of (25) < -

1 2 log(ρ) + log a(a -1)(ρ -1) (λ -) 2 = - 1 2 log ρ a(a -1)(ρ -1) (λ -) 2 .
Hence the necessary condition for the existence of solutions is

(λ -) 2 < ρ a(a -1)(ρ -1) (λ -) 2 -1
1 Intuitively, the best choice for λ + is to be close to a, as this would reduce the flying period and impose a less conservative constraint on λ -for a net reduction of ∆ k .

April 1, 2011 DRAFT i.e. ρa(a -1)(ρ -1) < 1 and hence ρ(ρ -1) < 1/(a(a -1)). Therefore, the valid choices of ρ are such that 1 -1 + 4 a(a-1)

2 < ρ < 1 + 1 + 4 a(a-1)
2 .

But, as λ + > a, the search interval becomes (24).

IV. RECOVERY AND PERSISTENCE ISSUES

In previous papers presented in this field, such as [START_REF] Hespanha | Towards the control of linear systems with minimum bit-rate[END_REF] and [START_REF] Liberzon | On stabilization of linear systems with limited information[END_REF] an explicit bound on the initial state x(t 0 ) is required in order to initialize the encoder. The proposed bypass is to execute an initial uncontrolled stage (with undesired transient effects) to estimate that bound (See [START_REF] Liberzon | On stabilization of linear systems with limited information[END_REF],

Section III), but it is not stated how to switch back and forth between stages in case a disturbance drives away the state (it is a known fact that the switching policy is crucial in stability analysis).

On the other hand, [START_REF] Brockett | Quantized feedback stabilization of linear systems[END_REF] proposes a zoom-out and then zoom-in mechanism (in that particular ordering), and it deals only with continuous-time quantization (and hence unlimited data rate).

Our claim is that our algorithm does not distinguish between different stages, i.e. the mathematical definition is unique, and it does not require any bound on the initial state. As a consequence, the algorithm allows the state to escape momentarily at any time due to unattended unbounded finite-time disturbances, and after them it will recover stability.

It must be acknowledged, however, that a temporary loss of communication could have a side effect: the equi-memory property may be lost, i.e. ∆ k may differ between receiver and transmitter. In that case, a recovery procedure for synchronizing both ends is proposed as follows.

Considering k * as the maximum flying period (see proof of 1), we propose the following resynchronization algorithm: Initialization Sequence Coding operation

1) N s = 0, x 0 = 0, ∆ 0 = ∆ * 2) Wait until δ k = δ k-1 3) Go to Coding operation 1) If δ k =δ k-1 set N s = N s + 1; else set N s = 0 2) If N s = k * + 1 go to Initialization Seq.
3) Apply ( 8)-(10) (enc.), or (11)-( 13) and ( 14) (dec.)

Here, ∆ * > 0 is the freely-chosen (but shared) initial value of the quantization step. Thanks to the global stability of the system with unconstrained encoder initialization, this algorithm at both the emitter and receiver guarantees that, in the case of temporary loss of communication provokes instability of the error dynamics (loss of synchronization, or equi-memory), both communication 16) and (17). The simulation compares the fixed-gain ∆ coding scheme (left figure) [START_REF] Canudas-De-Wit | Differential coding in networked controlled linear systems[END_REF], with the proposed adaptive scheme (right figure). In the first case, the value of ∆ is changed at pre-specified time instants whereas the adaptive law for ∆ allows for better granularity which is adapted as a function of the closed-loop error signal improving the system performance while enlarging the domain of attraction. ends will reset their Delta Modulators and recover stability after a transient. The validity of this procedure relies in the fact that, in normal operation, no more than k * consecutive samples with the same value of δ k can occur. Step 3 in the initialization sequence is required because the flying period is bounded only after the first zero crossing the error signal.

V. SIMULATIONS

Simulations are illustrated in Fig. 4. The upper plots show x k , x and r k . The lower figures show the time evolution of ∆ k for both; fixed and adaptive cases. As expected, the adaptive law performs over the fixe case as the tracking error decrease up to an arbitrarily small value dictate by the minimum saturation for ∆ min = 0.05. Without this saturation, ∆ k would decrease to zero indefinitely annulling the system capacity to recover from future perturbations.

VI. CONCLUSIONS

In this paper we have investigated the stability properties of the Delta-modulation coding rule, when used as a transmission means in networked controlled linear systems. It was first shown that the standard form of the ∆-M algorithm can be modified, including information about the

Fig. 1 .

 1 Fig. 1. Block diagram of the problem set up studied in this paper.

x0 = 0

 0 In that structure, x ∈ IR is the state of the plant, and a standard Delta Modulator is used to encode it. This structure uses a prediction of the state xk generated by a model of the closedloop dynamics (2) synchronized at both communication ends. When a new sample of the state

Fig. 2 .

 2 Fig. 2. Adaptive coding scheme. The figure shows the case of one-dimensional systems. The selection gain block toggles the value of φ k according to Equation (6).

Fig. 3 .

 3 Fig. 3. Left: Behavior of y k at zero crossings. Right: Definition of fly-time.

  Sufficient condition) We are concerned with the existence of solutions satisfying inequality (17), i.e. λ -< (λ + ) -β 2 within the range of validity of the constants, i.e. [λ -∈ (0, 1)] × [λ + ∈ (a, ∞)]. Using the property λ -= (λ + ) log λlog λ + , we can rewrite (17) as

Fig. 4 .

 4 Fig.[START_REF] Canudas-De-Wit | Energy-aware 3-level coding and control co-design for sensor network systems[END_REF]. System (7)-(14) has been simulated for the set of values a = 1.1, b = 1, K = 0.2, x k (0) = -0.5, xk (0) = 0, with ∆0 = 5, λ -= 0.4, λ + = 1.21, according to conditions (16) and (17). The simulation compares the fixed-gain ∆ coding scheme

April 1, 2011 DRAFT

system and the controller. These results were extended to the case of adaptive ∆ k . An explicit adaptation rule was proposed and the range of parameters were derived to ensure asymptotic stability. These results displayed a limit on the maximum unstable eigenvalues of the system that are compatible with the ones given in [START_REF] Tatikonda | Control under communication constraints[END_REF].