Valmi Dufour-Lussier

Florence Le Ber
email: florence.leber@engees.unistra.fr

Jean Lieber
email: jean.lieber@loria.fr

Laura Martin
email: laura.martin@mirecourt.inra.fr

Adaptation de cas spatiaux et temporels

Les algèbres qualitatives forment une famille de langages utilisés principalement pour représenter des connaissances de nature temporelle ou spatiale. Cet article propose une approche pour adapter des cas représentés dans une telle algèbre. Un exemple spatial portant sur l'agronomie ainsi qu'un exemple temporel portant sur la cuisine sont donnés. L'idée sous-jacente à cette approche de l'adaptation est d'appliquer une substitution puis de réparer les incohérences qui pourraient être apparues, grâce à la révision des croyances appliquée aux algèbres qualitatives.

Révision de croyances et adaptation fondée sur la révision

3.2.1 Révision de croyance.

Introduction

Le raisonnement qualitatif spatial et temporel (RQST) est un domaine de recherche actif depuis les années 1980. Ce paradigme a été exploité dans le cadre de la résolution de contraintes et de la planification, mais plus rarement dans le cadre du raisonnement à partir de cas (RÀPC). Pourtant de nombreux problèmes où le RQST s'applique relèvent du RÀPC, car les connaissances visées sont souvent contextuelles et mal formalisées. C'est le cas dans le domaine de l'agronomie des territoires, où la connaissance et constituée à partir d'enquêtes en exploitation et de descriptions schématiques de l'organisation spatiale des territoires de ces exploitations (voir [START_REF] Osty | Raisonnement à partir de cas et agronomie des territoires -constructions croisées[END_REF]). C'est le cas aussi dans le domaine culinaire, qui fait l'objet depuis quelques années d'un concours spécifique de la conférence ICCBR, et où interviennent des connaissances de nature temporelle.

Cet article propose une approche pour l'adaptation de cas spatiaux ou temporels. L'approche est fondée sur une procédure intégrant une adaptation par substitution et par révision. Par exemple, il peut être nécessaire de remplacer, dans une exploitation, une parcelle de maïs par une parcelle d'une autre culture, ou, dans une recette donnée, des champignons par des carottes. Une simple substitution est alors insuffisante, car toutes les cultures, ou tous les ingrédients d'une recette, ne se comportent pas de la même façon. C'est pourquoi nous ajoutons à la substitution une procédure de révision de croyance qui permet de modifier les contraintes spatiales de l'exploitation ou les contraintes temporelles de la recette pour les rendre cohérentes avec la connaissance du domaine.

Le plan de l'article est le suivant. La section 2 justifie notre approche en présentant deux exemples des domaines agricole et culinaire. La section 3 introduit ensuite les notions formelles nécessaires à la description de notre approche, à savoir l'adaptation par révision et le RSTQ. L'approche est ensuite décrite en détail dans la section 4 et un algorithme est présenté en section 5. La section 6 illustre ces notions formelles et les résultats de l'algorithme à partir des deux exemples de la section 2. Nous situons notre approche par rapport à d'autres travaux en section 7 avant de conclure et de présenter les perspectives de ce travail dans la section 8.

Présentation des exemples

Cette partie décrit deux exemples pour lesquels une simple substitution ne donnerait pas une adaptation acceptable du cas remémoré vis-à-vis du problème cible. Dans le premier exemple, l'adaptation spatiale d'un cas agricole doit prendre en compte des connaissances agronomiques sur la localisation de cultures, telles que des règles environnementales ou des contraintes culturales. Dans le deuxième exemple, l'adaptation temporelle d'une recette de risotto doit tenir compte de connaissances culinaires sur la durée de cuisson de différents légumes.

Un exemple agronomique et spatial

L'adaptation spatiale est illustrée par un exemple tiré du domaine agronomique, sur l'allocation de miscanthus, une plante pérenne, actuellement promue en Europe comme une source d'énergie renouvelable permettant d'obtenir un haut rendement de biomasse avec peu d'intrants [START_REF] Clifton-Brown | Miscanthus biomass production for energy in Europe and its potential contribution to decreasing fossil fuel carbon emissions[END_REF]. Sa capacité à réduire les émissions de gaz à effet de serre est liée à sa localisation spatiale dans les territoires agricoles [START_REF] Hillier | Greenhouse gas emissions from four bioenergy crops in England and Wales : Integrating spatial estimates of yield and soil carbon balance in life cycle analyses[END_REF] et il est donc très intéressant de modéliser les changements d'usage de l'espace liés à son introduction dans ces territoires.

Le RàPC peut être utilisé pour modéliser l'allocation spatiale du miscanthus. Un problème est constitué d'une quantité de miscanthus à produire et de la description d'une exploitation agricole ; la solution est constituée de la localisation spatiale de la culture. La description de l'exploitation comporte l'assolement (la liste des cultures pratiquées et leur localisation) et les caractéristiques spatiales du territoire de l'exploitation (par exemple, les relations spatiales entre les champs et des zones bâties, des bois ou des rivières).

Dans l'exemple illustré par la figure 1, on considère un agriculteur voulant produire du miscanthus. Le cas d'une exploitation produisant du maïs est remémoré, à partir d'un ensemble de cas obtenus par des enquêtes menées en France [START_REF] Martin | L'insertion territoriale des cultures biomasses pérennes : le cas du miscanthus par dix agriculteurs de Côte d'Or[END_REF] et en accord avec des connaissances expertes assimilant les besoins du miscanthus et du maïs vis-à-vis de la température et de l'humidité du sol.

Si on remplace le maïs par du miscanthus (qui est habituellement récolté de février à mars en France), on se trouve confronté à des contraintes agronomiques. En effet, l'accès des machines à la parcelle peut être rendu impossible en hiver à cause de l'excès d'eau dans les sols. Le miscanthus ne doit donc pas être implanté dans une zone inondable, alors que le maïs, lui, peut être implanté légalement jusqu'à 5 mètres du lit d'une rivière.

Ainsi, le processus d'adaptation doit non seulement remplacer le maïs par le miscanthus, mais aussi réduire la taille de la parcelle de miscanthus de sorte qu'elle soit disjointe de la zone inondable de toute rivière voisine.

Une adaptation parfaite devrait couper la parcelle originelle en deux, la partie proche de la rivière restant plantée en maïs, de sorte d'être toujours productive.

Un exemple culinaire et temporel

L'adaptation temporelle est illustrée par l'adaptation d'une recette de cuisine, dans l'esprit du projet TAAABLE [START_REF] Cojan | Knowledge extraction for improving case retrieval and recipe adaptation[END_REF], une application culinaire du RàPC. Si un utilisateur interroge le système TAAABLE pour obtenir une recette de risotto aux carottes et que cette recette n'existe pas dans la base, TAAABLE proposera d'adapter une recette de risotto aux champignons en remplaçant les champignons par des carottes.

Supposons que, dans cette recette, les champignons soient ajoutés deux minutes avant la fin de cuisson du riz et que, selon les connaissances du domaine, les carottes doivent cuire 25 minutes tandis que le riz doit cuire 18 minutes. Une bonne adaptation devra donc non seulement allonger la cuisson des légumes, mais également réordonner les actions de la recette adaptée de façon à la rendre utilisable.

Fondements

Cette section présente quelques définitions et quelques résultats qui seront utilisés dans la suite de l'article.

Adaptation de cas

Dans cet article, Source, Cible et CD dénotent respectivement le cas à adapter, le cas cible et les connaissances du domaine. Source and Cible sont tenus d'être cohérent avec CD. 1 Étant donné Source et Cible, l'adaptation a pour but de construire un nouveau cas, CasAdapté. Ce cas est construit par addition de certaines informations au cas cible (intuitivement, Cible spécifie seulement la « partie problème » de la requête) qui doivent être cohérentes avec CD.

Il est supposé qu'une étape d'appariement précède le processus d'adaptation lui-même, ce qui fournit certains liens entre Source et Cible, représentés par une substitution σ. σ associe certains descripteurs de Source à certains descripteurs de Cible. À titre d'exemple, dans le système TAAABLE, l'appariement est effectué durant la remémoration [START_REF] Cojan | Knowledge extraction for improving case retrieval and recipe adaptation[END_REF]. Dans la suite, cette étape de prétraitement de l'adaptation est considérée comme donnée. Ainsi, σ est une entrée du processus d'adaptation décrit dans la section 4.

Dans un formalisme de représentation donné, un opérateur de révision associe à deux bases de connaissances ψ et µ une base de connaissances ψ µ, la révision de ψ par µ. Intuitivement, ψ µ est obtenu en faisant un changement minimal de ψ en ψ , de sorte que la conjonction de ψ et µ, ψ ∧ µ, est cohérent. ψ µ est alors la conjonction. La notion de changement minimal pouvant être modélisée de différentes manières, il existe divers opérateurs de révisions. Cependant, certains postulats ont été proposés pour un tel opérateur, tel que les postulats AGM [START_REF] Alchourrón | On the Logic of Theory Change : partial meet functions for contraction and revision[END_REF]. Ces postulats ont été appliqués à la logique propositionnelle [START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF] et profondément étudiés dans ce formalisme. En particulier, étant donné une distance dist sur l'ensemble d'interprétation U, un opérateur dist peut être uniquement défini (à l'équivalence logique près) comme suit : l'ensemble des modèles de ψ dist µ est l'ensemble des modèles de µ qui ont une distance minimale à l'ensemble des modèles de ψ.

Y X {DC} Y X Y X {EC} Y X Y X {PO} Y XY X {EQ} Y Y X X {TPP} Y Y {TPPi} X Y X X {NTPP} Y Y {NTPPi} X

Adaptation fondée sur la révision.

Étant donné un opérateur de révision , la -adaptation consiste simplement à utiliser cet opérateur de révision pour effectuer l'adaptation, prenant en compte le domaine de connaissances :

CasAdapté = (CD ∧ Source) (CD ∧ Cible) (1)
L'intuition derrière l'adaptation à partir de révision est de réduire l'adaptation en une réparation des incohérences. Ceci a été étudié en logique propositionnelle [START_REF] Lieber | Application of the Revision Theory to Adaptation in Case-Based Reasoning : the Conservative Adaptation[END_REF] et, plus généralement, dans les espaces métriques [START_REF] Cojan | Conservative Adaptation in Metric Spaces[END_REF]. Le même principe a aussi été appliqué à l'adaptation dans la logique de descriptions expressive [START_REF] Cojan | An Algorithm for Adapting Cases Represented in ALC[END_REF]. Cet article l'applique, avec quelques différences, aux réseaux de contraintes qualitatives.

Représentation qualitative de connaissances spatiales et temporelles

Définitions.

Une algèbre qualitative est une algèbre de relations qui définit un ensemble B de relations binaires applicables entre deux variables, représentant généralement des points, des intervalles ou des régions. L'algèbre des intervalles de Allen [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF], par exemple, introduit 13 relations de base entre intervalles, correspondant aux 13 arrangements possibles des bornes inférieures et supérieures de deux intervalles. 7 relations sont illustrées dans la figure 2a. Les 6 autres sont l'inverse des 6 premières (eq est symétrique).

IN DU [START_REF] Pujari | INDU : An interval & duration network[END_REF] étend l'ensemble des relations de Allen en les combinant avec des relations sur la durée des intervalles. Pour 7 relations de Allen, il y a seulement une relation possible de durée (p.ex. i {d} j implique que la durée de i est plus courte que la durée de j). Pour les 6 autres, les trois relations de durées <, = et > sont possibles. Cela donne un total de 25 relations de base. Elles sont notées r s , où r est une relation de Allen et s est une relation de durée. La famille des algèbres RCC [START_REF] Randell | A spatial logic based on regions and connection[END_REF] comprend des algèbres spatiales biens connues. La plus usuelle, RCC8, introduit 8 relations entre régions, représentées dans la figure 2b.

Les connaissances qualitatives peuvent être représentées comme des réseaux de contraintes qualitatives (RCQ). Un RCQ est une paire (V, C), où V est un ensemble de variables, et C est un ensemble de contraintes de la forme Dans IN DU, les raccourcis de notation r ? et ? s représentent respectivement le produit cartésien de r et de toutes les relations de durées possibles, et le produit de s et de toutes les relations de Allen possibles.

V i C ij V j , avec V i , V j ∈ V , et C ij
(p.ex., {o, d} une valuation peut être fournie pour les variables de telle sorte que toutes les contraintes soient respectées ; et, par extension, un RCQ est cohérent s'il a un scénario cohérent. Deux RCQ sont dits équivalents si tout scénario du premier est un scénario du second et vice-versa.

? = {o < , o = , o > , d < }). Un scénario est un RCQ S = (V S , C S ) tel que, pour chaque V i , V j ∈ V S , il existe une contrainte V i {r} V j ∈ C S . S satisfait le RCQ N = (V N , C N ) si S et

Révision de RCQ.

Un RCQ est une base de connaissance et, ainsi, le problème de la révision d'un RCQ ψ par un RCQ µ peut être traité. Dans [START_REF] Condotta | A framework for merging qualitative constraints networks[END_REF], un opérateur de révision sur les RCQ est défini,2 suivant l'idée d'un opérateur dist (cf. section 3.2), où une interprétation est un scénario, un modèle d'un RCQ est un scénario qui le satisfait, et une distance dist entre scénarios/interprétations est définie comme suit.

Premièrement, une distance d entre les relations de base de l'algèbre considérée est définie. Formellement, un graphe connexe non dirigé, dont les noeuds sont les relations de l'algèbre, est donné, et d(r, s) est la longueur du plus petit chemin entre r et s dans ce graphe. Ce graphe, nommé graphe de voisinage, n'est pas arbitraire : il représente la proximité entre relations. Par exemple, b et m sont proches (d(b, m) = 1) puisqu'ils expriment des conditions similaires sur les bornes des intervalles qui sont comparés (pour la borne inférieure : = pour les deux ; pour la borne supérieure : < pour b et = pour m). La figure 3 présente de tels graphes, tels que proposé par [START_REF] Ligozat | On generalized interval calculi[END_REF] pour l'algèbre de Allen et par [START_REF] Randell | A spatial logic based on regions and connection[END_REF] pour RCC8, en s'appuyant sur un principe de changement minimal. d permet de définir dist, une distance entre deux scénarios S = (V, C S ) etT = (V, C T ) basée sur le même ensemble de variables V, que :

dist(S, T ) = V i ,V j ∈V,i =j d(r S (V i , V j ), r T (V i , V j )) (2) où r S (V i , V j ) est la relation r telle que V i {r} V j ∈ C S .
Étant donné deux RCQ ψ et µ, la révision de ψ par µ donne l'ensemble R des scénarios satisfaisant µ qui sont les plus proches à l'ensemble des scénarios satisfaisant ψ. Il est tenu pour acquis que les variables du RCQ considéré peuvent être paramétrées par les éléments de l'ensemble P donné. Un paramètre p ∈ P est soit un paramètre concret, p ∈ CP, ou un paramètre abstrait, p ∈ AP : P = CP ∪ AP, CP ∩ AP = ∅. Un paramètre concret dénote un concept du domaine d'application, par exemple champignons ∈ CP pour l'exemple culinaire. Dans cet exemple, l'intervalle formel cuire(champignons) représente l'intervalle temporel correspond à la cuisson des champignons. Les connaissances du domaine constituent un RCQ CD = (V CD , C CD ) correspondant à un ensemble de contraintes, par exemple :

C CD =    cuire(riz) ? = 18_min
(le riz doit cuire pendant 18 min) cuire(x) {m} ? cuites(x) (quand l'action de cuire x est terminée, x est cuit) 18_min ? < 25_min (18 min sont plus courtes que 25 min)

   (3)
où riz ∈ CP et x ∈ AP. Chaque intervalle correspond à la réification d'une action, d'un état ou d'une durée. Un paramètre abstrait doit être compris comme une quantification universelle sur les paramètres concrets ; par exemple cuire(x) {m} ? cuites(x) implique cuire(champignons) {m} ? cuites(champignons).

Soit

N 1 et N 2 deux RCQ. Leur conjonction N 1 ∧ N 2 est le RCQ N = (V, C) tel que V = V 1 ∪ V 2 et que C renferme les contraintes de C 1 ,
les contraintes de C 2 , et les contraintes qui sont déduites par l'instanciation des paramètres abstraits par les paramètres concrets apparaissant dans

N 1 et N 2 . Par exemple, si N 1 = C CD défini par l'équation (3) et N 2 = ({cuire(tomates), cuites(tomates)}, ∅), alors N 1 ∧ N 2 = (V, C) avec C = C CD ∪ {cuire(tomates) {m} ? cuites(tomates)}.

Substitutions.

La substitution atomique σ = p q, où p, q ∈ P, est la fonction de P dans P définie par σ(a) = q si a = p a sinon . Une substitution est une composition σ 1 ; . . . ; σ n de substitutions atomiques σ i . 4 Soit σ = p q une substitution atomique. σ est concrète si p, q ∈ CP. σ est une abstraction atomique si p ∈ CP et q ∈ AP. σ est un raffinement atomique si p ∈ AP et q ∈ CP. Une substitution concrète (resp., une abstraction, un raffinement) est une composition de substitutions atomiques concrètes (resp., d'abstractions atomiques, de raffinements atomiques). Toute substitution concrète σ peut s'écrire σ = α ; où α est une abstraction et est un raffinement, comme illustré par cette équation :

champignons carottes = champignons x ;
x carottes où champignons, carottes ∈ CP et x ∈ AP. Ceci peut être démontré comme suit. Premièrement, σ peut s'écrire p 1 q 1 ; . . . ; p n q n avec p i , q i ∈ CP et p i = p j if i = j. 5 Soit x 1 , . . . , x n n paramètres abstraits, soit α i = p i x i , soit i = x i q i , soit α = α 1 ; . . . ; α n , et soit = 1 ; . . . ; n . α est une abstraction, est un raffinement et σ = α ; . Soit σ une substitution. σ est étendue aux variables qualitatives en l'appliquant à leurs paramètres. Par exemple, si σ = champignons carottes alors σ(cuire(champignons)) = cuire(carottes). Ensuite, σ est étendue à une contrainte c = (

V i C ij V j ) par σ(c) = (σ(V i ) C ij σ(V j )). Finalement, σ est étendue à un RCQ en l'appliquant à ses variables et contraintes : σ((V, C)) = (σ(V ), σ(C)) où σ(V ) = {σ(V i ) | V i ∈ V } et σ(C) = {σ(c) | c ∈ V }.

Problème d'adaptation.

Un problème d'adaptation est un tuple (Source, Cible, CD, σ). Source et Cible sont la représentation des cas source et cible par des RCQ dotés de variables concrètes (c'est-à-dire non paramétrées par quelque paramètre abstrait). CD est un RCQ représentant les connaissances du domaine. σ = p 1 q 1 ; . . . p n q n est une substitution concrète telle que chaque p i (resp., q i ) paramètre une variable de Source (resp., Cible). CD ∧ Source et CD ∧ Cible sont considérés comme cohérents (cf. section 3.1). Le but de l'adaptation est de construire un RCQ CasAdapté cohérent qui implique CD ∧ Cible, dont les variables qualitatives sont obtenues en appliquant σ sur les variables qualitatives de Source, et qui est obtenu par un changement minimal de CD ∧ Source.

4. La composition de σ et de σ , notée σ ; σ , est la fonction qui associe à p ∈ P, σ ; σ (p) = σ (σ(p)) ∈ P. 5. Ce qui peut être démontré par induction grâce aux lemmes suivants : (1) si p = q alors p q ; p q = p q, (2) p q ; q r = p r, et (3) si p = p , q = p et q = p, alors p q ; p q = p q ; p q.

Principes de l'adaptation fondée sur la révision d'un RCQ

Une idée initiale pour effectuer l'adaptation, étant donné un tuple (Source, Cible, CD, σ), est d'appliquer σ à Source, obtenant ainsi un RCQ CD∧σ(Source) qui pourrait être incohérent, puis de rétablir la cohérence. Bien que cette idée fournisse une bonne intuition de l'adaptation fondée sur la révision d'un RCQ, elle n'est pas cohérente avec le principe de la non pertinente de la syntaxe (qui est généralement pris en compte, par exemple pour la révision des croyances [START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF]). En effet, toutes les bases de connaissances incohérentes (par exemple, deux RCQ incohérents) sont équivalentes : l'ensemble de leurs modèles est vide. Donc, d'un point de vue sémantique (par opposition à un point de vue syntaxique), réparer une base de connaissances incohérentes n'a aucun sens. La révision, de son côté, a pour but de modifier une base de connaissances cohérente à l'aide d'une autre base de connaissances cohérente, mais dont la conjonction pourrait être incohérente. C'est l'une des raisons pour laquelle nous ne suivons pas directement cette idée initiale. Il existe une autre raison, plus pragmatique : la révision des RCQ rend possible la réutilisation du travail de [START_REF] Condotta | A framework for merging qualitative constraints networks[END_REF].

L'adaptation fondée sur la révision consiste en premier lieu à décomposer σ en une abstraction α et en un raffinement : σ = α ; (cf. section précédente). Puis, α est appliquée à Source : un RCQ CD ∧ α(Source) est construit, et est nécessairement cohérente puisque CD ∧ Source est cohérent et que chaque contrainte CD∧α(Source) correspond à une contrainte de CD∧Source. En d'autres termes, CD∧Source est cohérent et est plus ou également contraint que CD ∧ α(Source), donc CD ∧ α(Source) est cohérent.

La troisième étape implique la révision. L'idée est d'effectuer la révision de ψ par µ où ψ = CD ∧ α(Source) et µ = CD ∧ Cible ∧ N , où N représente l'affirmation suivante : « Chaque variable qualitative V i de α(Source) est contrainte de la même manière que son raffinement (V i ). » À cette fin, la relation eq pour l'égalité est utilisée 6 :

V i eq (V i ). Donc, N = (V , C ) où V = α(V ) ∪ σ(V ) C = {V i eq (V i ) | V i ∈ α(V )}
µ est cohérent puisque CD ∧ Cible l'est et que chaque contrainte V i eq (V i ) de N soit est une tautologie (lorsque V i ne contient aucun paramètre abstrait raffiné par ), ou bien lie un variable V i qui n'apparaît pas dans CD ∧ Cible à (V i ).

Finalement, ψ µ donne un ensemble de scénarios et CasAdapté est choisi parmi ceux-ci.

Algorithme et mise en oeuvre

Dans cette section, l'algorithme exécutant la solution décrite dans la section précédente est détaillé.

Entrée et sortie.

L'algorithme de révision prend en entrée ψ = CD ∧ α(Source), µ = CD ∧ Cible ∧ C , ainsi que la relation du graphe de voisinage et la table de transitivité pour l'algèbre utilisée. Le graphe de voisinage permet de définir une distance d entre les relations et la table de transitivité définit une fonction de compositions de relations • : B × B → 2 B , par exemple, m • mi = {eq, f, fi} dans l'algèbre de Allen.

L'algorithme de révision retourne un ensemble de scénarios de µ et leur distance à ψ.

Algorithme.

Premièrement, il est nécessaire de faire en sorte que toutes les variables dans l'un des RCQ soient présentes dans l'autre RCQ. Tout couple de variables qui n'a pas de relation associée reçoit la relation Bla relation non spécifiée.

L'algorithme doit ensuite générer tous les scénarios de µ et de ψ et mesurer leur distance paire par paire. La quantité de scénarios pour un RCQ donné est de l'ordre de O |B|

|V |•(|V |-1) 2
. Pour chaque paire de scénarios, la distance est calculée en utilisant l'équation [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF]. La distance entre un scénario S de µ et le RCQ ψ est la plus petite distance entre S et n'importe quel scénario de ψ. La distance entre le RCQ µ et ψ est la plus petite 6. eq est eq = pour IN DU et EQ pour RCC8.

distance entre un scénario de µ et le RCQ ψ. Une fois que tous les scénarios de µ et de ψ ont été comparés paire par paire, la distance entre µ et ψ est connue et les scénarios de µ correspondant à cette distance sont retournés.

Seuls les scénarios cohérents doivent être considérés. La chemin-cohérence d'un scénario, comme défini dans [START_REF] Mackworth | Consistency in networks of relations[END_REF], est une condition nécessaire et suffisante pour la cohérence. 7 Cette condition est vérifiée en temps

O(|V | 3 ) si, pour chaque V i , V j , V k ∈ V , r(V i , V k ) ∈ r(V i , V j ) • r(V j , V k ).
Tous les scénarios incohérents sont écartés.

Optimisations.

A cause de la complexité, il est essentiel de limiter l'espace de recherche. Considérant que le minimum des sommes n'est jamais inférieur à la somme des minimums, une borne inférieure sur la distance entre deux RCQ peut être obtenue en temps O(|V | 2 • |B| 2 ) en calculant la distance minimale entre relations paire par paire pour chaque contrainte et en additionnant ces distances. Empiriquement, il apparaît que la distance effective est habituellement plus proche de cette borne inférieure que de la borne supérieure, qui est une fonction de la longueur du plus long chemin dans le graphe de voisinage.

Par conséquent, il est souvent profitable de fixer une borne supérieure initiale sur la distance entre ψ et µ qui est égale à la borne inférieur, et de chercher itérativement. Cette recherche peut être encore optimisée en calculant la borne inférieure sur la distance entre un scénario S de µ et ψ, qui peut être donné en temps O(|V | 2 ). Cette borne permet d'écarter directement certains scénarios de µ et ainsi d'éviter d'avoir à générer tous les scénarios de ψ à nouveau. Bien sûr, dès qu'un scénario de µ est trouvé à une distance acceptable d'un scénario de ψ, la recherche itérative fait en sorte qu'il n'est pas nécessaire d'examiner d'autre scénario de ψ.

Une autre optimisation utile dans les problèmes de taille plus grande que quelques variables est le calcul de la fermeture algébrique du RCQ, qui est obtenue en forçant la chemin-cohérence. C'est-à-dire que, pour chaque

V i , V j , V k ∈ V , C ik est remplacé par C ik = C ik ∩ (C ij • C jk ) où • est étendu sur 2 B × 2 B → 2 B par R • S = r∈R,s∈S r • s.
Ceci est répété jusqu'à atteinte de la stabilité, c'est-à-dire jusqu'à ce qu'aucune relation ne soit changée après avoir considéré tous les 3-tuples de variables.

Application sur les exemples

Cette section revient sur les deux exemples présentés en section 2. Tout d'abord, l'exemple agronomique pris dans sa forme simple (seul le miscanthus est cultivé) pour illustrer l'algorithme. Ensuite, nous discutons de la formalisation et des résultats obtenus sur l'exemple agronomique complet et sur l'exemple culinaire.

Un problème agronomique simplifié

Soit un exploitant agricole qui cultive une parcelle de maïs adjacente à une rivière. Dans la suite, nous distinguons deux zones -dont l'usage agricole est différent -la rivière elle-même, dénotée lit_mineur, et la zone inondable, dénotée lit_majeur. Le lit_mineur est une partie propre intérieure du lit_majeur ce qui peut s'exprimer de la façon suivante en RCC8 : lit_mineur {NTPP} lit_majeur. Le fait que la parcelle de maïs est adjacente à la rivière est représenté par parcelle(maïs) {EC} lit_mineur.

Soit un problème où un agriculteur veut cultiver du miscanthus dans une configuration similaire, conduisant à la remémoration du cas décrit précédemment. Une substitution doit être appliquée : σ = maïs miscanthus = maïs

x ; x miscanthus. Une connaissance importante concernant le miscanthus est qu'il ne doit pas être cultivé dans une zone inondable, ce qui peut être exprimé de la façon suivante : parcelle(miscanthus) {DC, EC} lit_majeur.

Dans cet exemple, ψ contient les contraintes :

C CD = {parcelle(miscanthus) {DC, EC} lit_majeur} C α(Source) = lit_mineur{NTPP} lit_majeur parcelle(x) {EC} lit_mineur 7.
La même chose n'est pas vraie pour les RCQ en général, comme démontré dans [START_REF] Allen | Maintaining knowledge about temporal intervals[END_REF].

et µ contient les contraintes :

C CD = {parcelle(miscanthus) {DC, EC} lit_majeur} C Cible = {lit_mineur {NTPP} lit_majeur} C = {parcelle(x) {EQ} parcelle(miscanthus)}
La première étape de l'algorithme est d'ajouter les variables et les contraintes manquantes. Dans cet exemple les quatre variables sont présentes dans les deux RCQ, mais il manque des relations, par exemple entre les variables parcelle(miscanthus) et lit_mineur. On ajoute donc à la fois à µ et à ψ la contrainte : parcelle(miscanthus) {DC, EC, PO, TPP, NTPP, TPPi, NTPPi, EQ} lit_mineur.

Cette manipulation peut conduire à complexifier les RCQ, et c'est une des raisons pour lesquelles il est intéressant de calculer leur clôture algébrique. Dans cet exemple le nombre de scénarios potentiels est réduit de 1024 à 16 pour ψ, et de 1024 à 4 pour µ.

Dans une deuxième étape, on calcule la distance minimale entre ψ et µ. Ici, ce minimum vaut 3, qui est la distance entre ψ et µ. À cette distance, on trouve un seul scénario T de µ :

ψ µ = {T } = {(V T , C T )} avec C T =               
lit_mineur{NTPP} lit_majeur lit_mineur{DC} parcelle(x) lit_mineur{DC} parcelle(miscanthus) lit_majeur{EC} parcelle(x) lit_majeur{EC} parcelle(miscanthus) parcelle(x) {EQ} parcelle(miscanthus)

              
La valeur de la distance est obtenue par la somme des valeurs des remplacements suivants : EC devient DC entre parcelle(x) et lit_mineur (d = 1), {TPP, NTPP, PO} devient EC entre lit_majeur et parcelle(x) (d = 1) et {DC, EC, NTPPi, PO} devient EQ entre parcelle(x) et parcelle (miscanthus) (d = 1).

Dans ce scénario, la région parcelle(x) a été réduite de sorte à ne pas recouvrir le lit_majeur quand elle a été assimilée à parcelle (miscanthus). Cela correspond à la configuration présentée figure 1b. On peut voir que la modification est en effet minimale, puisque la parcelle devient extérieurement connectée à la zone inondable, maximisant ainsi la surface utilisée par la culture de miscanthus. À l'inverse, un résultat incluant lit_majeur {DC} parcelle(miscanthus) serait cohérent avec les connaissances du domaine mais ne serait pas une modification minimale de ψ. Ainsi l'algorithme produit la meilleure adaptation.

Un problème agronomique complet

Pour obtenir une adaptation plus réaliste (où tout le territoire est utilisé) telle que décrite dans la section 2.1, la parcelle est scindée en deux parties parcelle1(x) et parcelle2(y) avec σ = x miscanthus ; y maïs. Dans ψ, la seule information disponible sur ces deux parcelles est qu'elles sont connectées extérieurement au lit_mineur.

L'algorithme de révision produit 5 scénarios. Tous résolvent les contraintes de sorte à maximiser la taille de la parcelle de miscanthus, mais la part allouée au maïs varie. La figure 1c présente la configuration obtenue pour un des scénarios. Les autres sont similaires.

Un problème culinaire

La plupart des informations temporelles présentes dans les recettes peuvent être représentées avec le modèle IN DU en réifiant les actions, les états des ingrédients et les durées sous la forme d'intervalles. Par exemple, les énoncés suivants peuvent être insérés dans les connaissances du domaine : cuire(carottes) {m} ? cuites(carottes) et cuire(carottes) ? = 25_min, avec également, par exemple, 18_min ? < 25_min.

Dans un problème simple comme cela, on peut combiner directement les contraintes et ainsi limiter le nombre de variables. Ainsi le problème décrit en section 2.2 peut être ramené à 4 variables en remplaçant les intervalles de durée par des relations de durée entre les actions correspondantes. Dans cette représentation, ψ contient : Dans les deux scénarios, l'allongement de la cuisson des légumes est associé à l'inversion de la relation entre les légumes et le riz, i.e. f < devient fi > , ce qui correspond à l'inversion attendue de l'ordre entre le démarrage des deux actions. Ainsi l'adaptation a réussi.

C CD =    cuire(

Travaux connexes

Plusieurs travaux récents combinent le RÀPC et le raisonnement spatial qualitatif, par exemple pour améliorer des services web d'informations spatiales [START_REF] Osman | Semantic spatial web services with case-based reasoning[END_REF] ou pou prédire des lieux d'apparition d'événements en territoires hostiles [START_REF] Li | Spatial event prediction by combining value function approximation and case-based reasoning[END_REF]. D'autres travaux plus anciens avaient déjà souligné l'intérêt du RÀPC pour l'analyse de données géographiques, par exemple pour la classification des sols [START_REF] Holt | Case-Based Reasoning and Spatial Analysis[END_REF]. Nous mêmes avons développé un système de RÀPC pour aider des agronomes dans l'analyse et la comparaison d'enquêtes en exploitations [START_REF] Ber | Modeling and comparing farm maps using graphs and case-based reasoning[END_REF]. Ce système utilisait des graphes conceptuels, dont les sommets et les arêtes sont étiquetés, pour représenter l'organisation spatiale de territoires agricoles. L'hypothèse était que des organisations similaires avaient des fonctionnements similaires. Les cas spatio-fonctionnels étaient implantés dans un système de logique de description et le raisonnement s'appuyait sur une combinaison de classification hiérarchique (au sens des logiques de description), de RÀPC et de raisonnement spatial qualitatif.

La représentation du temps a été plus largement étudiée pour le raisonnement à partir de cas. La plupart des travaux s'intéressent à l'analyse ou la prédiction de processus temporels (diagnostic de pannes ou de maladies à partir d'observations régulières ou d'événements successifs, par exemple). L'aspect temporel est pris en compte via l'enchaînement des événements ou éventuellement des dates relatives ou absolues [START_REF] Dojat | Scenario recognition for temporal reasoning in medical domains[END_REF][START_REF] Ma | A Framework for Historical Case-Based Reasoning[END_REF][START_REF] Sánchez-Marré | An approach for temporal case-based reasoning : Episode-based reasoning[END_REF]. Seuls les travaux décrits dans [START_REF] Jaczynski | WWW assisted browsing by reusing past navigations of a group of users[END_REF][START_REF] Dørum Jaere | Representing temporal knowledge for case-based prediction[END_REF], à notre connaissance, utilisent une représentation du temps à base d'intervalles et de relations de Allen. Dans [START_REF] Dørum Jaere | Representing temporal knowledge for case-based prediction[END_REF], les cas sont représentés par des graphes temporels et la remémoration s'appuie sur un appariement de graphes. Dans [START_REF] Jaczynski | WWW assisted browsing by reusing past navigations of a group of users[END_REF], les cas sont indexés par des chroniques et des contraintes temporelles qui sont décrites par quelques relations de Allen. Notons également les travaux récents de S. Laborie et al., sur l'adaptation de documents multimédia, qui comprend à la fois des aspects spatiaux et des aspects temporels représentés au moyen des algèbres qualitatives [START_REF] Laborie | Semantic adaptation of multimedia documents[END_REF].

La planification à partir de cas (PÀPC, voir par exemple [START_REF] Munoz-Avila | Case-Based Plan Adaptation : An Analysis and Review[END_REF]) est également un domaine qui traite d'aspects temporels. La différence principale entre la PÀPC et notre approche est que les connaissances manipulées sont de natures différentes : la PÀPC traite de la réalisation de buts et modélise des actions en fonction de leur applicabilité et de leurs effets. Notre approche en revanche s'applique à des procédures représentées par des contraintes temporelles entre actions, et traite de ces contraintes et d'actions réifiées sous la forme d'intervalles de temps. En théorie ces approches pourraient être combinées mais elles ont des objectifs différents : la PÀPC classique se veut d'abord efficace et utilise des connaissances complètes de résolution de problème tandis que notre approche s'intéresse à la manipulation de connaissances incomplètes (par exemple les effets de chaque action d'une recette sont formalisés de façon incomplète).

Conclusion

Les algèbres qualitatives constituent un domaine important dans le champ de la représentation des connaissances. Elles sont notamment utilisées pour le raisonnement spatial et temporel. Cependant, elles ont encore peu été utilisées dans le cadre du raisonnement RÀPC.

Cette article propose une approche pour l'adaptation de cas représentés à l'aide d'une algèbre qualitative. Il présente deux exemples : un exemple utilisant de l'algèbre spatiale RCC8 appliquée dans le domaine agronomique et un autre exemple utilisant de l'algèbre temporelle IN DU appliquée dans le domaine culinaire. L'adaptation présentée dans cet article repose sur les principes de l'adaptation par révision, combinant celle-ci avec un appariement entre le cas source et le cas cible.

Un prototype pour l'adaptation de cas représentés à l'aide d'une algèbre qualitative a été mise en oeuvre en Perl. Il a été appliqué aux exemples, mais nécessite un temps de calcul trop important. De nombreuses optimisations devront être faites pour permettre son intégration dans un système opérationnel comme TAAABLE. Plusieurs sont déjà prévues.

Premièrement, le programme peut être optimisé grâce à certaines caractéristiques du problème de révision qui ne sont pas prises en compte dans le prototype actuel :

-Le fait que le cas source représente souvent un épisode spécifique de résolution de problème qui conduit le RCQ Source à n'avoir que peu de scénarios. -Le fait que la différence entre les RCQ est causée par σ, qui doit donc être considérée comme la source possible de toute incohérence. Deuxièmement, une étude sur la conception d'un processus de « propagation des réparations » dans les RCQ est prévue. Celui-ci serait similaire à l'algorithme classique de propagation de contraintes dans les RCQ, qui est similaire au processus d'adaptation décrit dans [START_REF] Cojan | An Algorithm for Adapting Cases Represented in ALC[END_REF].

Comme l'exemple agronomique le montre, le RCQ peut apparaître dans la requête du système de RÀPC. Cela signifie que, pour une telle application, la comparaison des RCQ doit aussi se faire durant l'étape de recherche du cas source. Un travail en perspective serait d'étudier comment implanter un tel processus de recherche.

  Cas adapté avec du maïs et du miscanthus.

FIGURE 1 :

 1 FIGURE 1: Exemple d'allocation spatiale de cultures.

  Les relations de base de l'algèbre de Allen.

X

  (b) Les relations de base de RCC8.

FIGURE 2 :

 2 FIGURE 2: Deux algèbres qualitatives courantes.

  un ensemble de relations basiques définies par l'algèbre (C ij est une relation qui est une disjonction des relations de base, c.-à.-d. que i {r 1 , r 2 } j signifie que i est lié à j par la relation r 1 ou bien par la relation r 2 ).

  N ont les mêmes ensembles de variables et si chaque contrainte dans S est un sous-ensemble de la contrainte correspondante dans N . Un scénario est cohérent si

FIGURE 3 :

 3 FIGURE 3: Les graphes de voisinage de relations de deux algèbres qualitatives courantes.

3

 3

4 Formalisation 4 . 1

 441 Représentation du problème d'adaptation 4.1.1 RCQ paramétré.

  riz) ? < cuire(carottes) cuire(riz) {m} ? servir cuire(carottes) {m} ? servir   C α(Source) = {cuire(x){f < }servir}Dans TAAABLE, il n'y a pas d'adaptation stable des contraintes de Cible (C Cible = ∅), µ contient donc simplement les contraintes suivantes :C CD =    cuire(riz) ? < cuire(carottes) cuire(riz) {m} ? servir cuire(carottes) {m} ? servir    C = {cuire(x) ? = cuire(carottes)} L'algorithme de révision renvoie deux scénarios qui ne se distinguent que par la relation de durée entre servir et les autres actions, puisque cette relation est peu importante selon les connaissances du domaine. Le scénario T = (V T , C T ) est tel que C T vaut :    cuire(x){m > }servir, cuire(x){eq = }cuire(carottes) cuire(carottes){m > }servir, cuire(x){fi > }cuire(riz) cuire(riz){m > }servir, cuire(carottes){fi > }cuire(riz)   

Si un cas Source de la base de cas est incohérent avec les connaissances du domaine, un processus de la maintenance de la cohérence doit être lancé pour restaurer la cohérence. Si une requête du système de RÀPC est incohérente avec les connaissances du domaine, elle doit soit être rejetée (par exemple, une requête comme « Je veux une recette avec des pommes mais sans fruit » est rejetée par TAAABLE puisque les connaissances du domaine impliquent que les pommes sont des fruits), soit entraîner une modification du CD.

Techniquement, les auteurs de[START_REF] Condotta | A framework for merging qualitative constraints networks[END_REF] définissent un opérateur de fusion prenant un RCQ coercitif en paramètre. Un opérateur de révision utilisant cet opérateur de fusion peut être défini.

Cela diffère légèrement de la définition de la révision donnée en section 3.2 où ψ µ est une base de connaissances, et non un ensemble de modèles. Ceci est dû au fait qu'il peut ne pas y avoir de RCQ ayant R comme ensemble de scénarios le satisfaisant.


Da-Yan Liu
email: dayan.liu@kaust.edu.sa

Olivier Gibaru
email: olivier.gibaru@ensam.eu

Wilfrid Perruquetti
email: wilfrid.perruquetti@inria.fr

Non-asymptotic fractional order differentiators via an algebraic parametric method

. Exact and simple formulae for these differentiators are given where a sliding integration window of a noisy signal involving Jacobi polynomials is used without complex mathematical deduction. The efficiency and the stability with respect to corrupting noises of the proposed fractional order differentiators are shown in numerical simulations.

I. INTRODUCTION

Fractional models arise in many practical situations ( [START_REF] Cugnet | On Lead-acid battery resistance and cranking capability estimation[END_REF], [START_REF] Pommier | CRONE control of a nonlinear hydraulic actuator[END_REF] for example). Such fractional order systems may also be used for control purposes: CRONE control is known to have good robustness properties (see [START_REF] Oustaloup | The CRONE control of resonant plants : application to a flexible transmission[END_REF], [START_REF] Oustaloup | From fractal robustness to the CRONE approach[END_REF], [START_REF] Oustaloup | From fractal robustness to the CRONE control[END_REF], [START_REF] Pommier | CRONE control of a nonlinear hydraulic actuator[END_REF]). In order to implement such controller one needs to have a good digital fractional order differentiator from noisy signals, which is the scope of this paper.

The fractional derivative has a long history and has often appeared in science, engineering and finance (see, e.g., [START_REF] Oldham | The Fractional Calculus[END_REF], [START_REF] Podlubny | Fractional Differential Equations[END_REF], [START_REF] Hotzel | On linear systems with a fractional derivation: Introductory theory with examples[END_REF], [START_REF] Fliess | Sur les systèmes linéaires à dérivation non entière[END_REF]). Different from classical integer order derivative, there are several kinds of definitions for the fractional derivative which are generally not equivalent with each other [START_REF] Podlubny | Fractional Differential Equations[END_REF], [START_REF] Kilbas | Theory and Applications of Fractional Differential Equations[END_REF]. Among these definitions, the Riemann-Liouville derivative and the Caputo derivative are often used [START_REF] Podlubny | Fractional Differential Equations[END_REF]. Recently, a new modified Riemann-Liouville derivative is proposed by Jumarie [START_REF] Jumarie | Table of some basic fractional calculus formulae derived from a modified Riemann-Liouville derivative for non-differentiable functions[END_REF]. This new definition of fractional derivative has two main advantages: firstly comparing with the Caputo derivative, the function to be differentiated is not necessarily differentiable, secondly different from the Riemann-Liouville derivative the Jumarie's modified Riemann-Liouville derivative of a constant is defined to zero. Moreover, a fractional Taylor series expansion [START_REF] Jumarie | Modified Riemann-Liouville derivative and fractional Taylor series of nondifferentiable functions further results[END_REF] was invented by using this new definition. Thanks to these merits, the Jumarie's modified Riemann-Liouville derivative was successfully applied (see, e.g., [START_REF] Jumarie | Fourier's transform of fractional order via Mittag-Leffler function and modified Riemann-Liouville derivative[END_REF], [START_REF] Jumarie | Laplac's transform of fractional order via the Mittag-Leffler function and modified Riemann-Liouville derivative[END_REF], [START_REF] Wu | Fractional Variational Iteration method and Its Appliation[END_REF]). The fractional order differentiator is concerned with estimating the fractional order derivatives of an unknown signal from its noisy observed data. Because of its importance, various methods have been developed during the last years ( [START_REF] Chen | Digital Fractional Order Savitzky-Golay Differentiator[END_REF], [START_REF] Machado | Calculation of fractional derivatives of noisy data with genetic algorithms[END_REF] for example). However, the obtained fractional order differentiators were usually based on the Riemann-Liouville derivative and the Caputo derivative. To our knowledge, there is no one based on the Jumarie's modified Riemann-Liouville derivative.

Recent algebraic parametric estimation method for linear systems [START_REF] Fliess | An algebraic framework for linear identification[END_REF], [START_REF] Fliess | Closed-loop parametric identification for continuous-time linear systems via new algebraic techniques[END_REF], [START_REF] Tian | Fast state estimation in linear time-varying systems: an algebraic approach[END_REF] has been extended to various problems in signal processing (see, e.g., [START_REF] Fliess | Questioning some paradigms of signal processing via concrete examples[END_REF], [START_REF] Fliess | Compression différentielle de transitoires bruités[END_REF], [START_REF] Mboup | Parameter estimation for signals described by differential equations[END_REF], [START_REF] Neves | An Algebraic Receiver for Full Response CPM Demodulation[END_REF], [START_REF] Neves | Algebraic parameter estimation of damped exponentials[END_REF], [START_REF] Ushirobira | Estimation algébrique des paramètres intrinsèques d'un signal sinusoïdal biaisé en environnement bruité[END_REF], [START_REF] Trapero | An algebraic frequency estimator for a biased and noisy sinusoidal signal[END_REF], [START_REF] Liu | Parameters estimation of a noisy sinusoidal signal with time-varying amplitude[END_REF], [START_REF] Liu | An error analysis in the algebraic estimation of a noisy sinusoidal signal[END_REF]). Let us emphasize that this method is algebraic and non-asymptotic, which provides explicit formulae and finite-time estimates. Moreover, it exhibits good robustness properties with respect to corrupting noises, without the need of knowing their statistical properties (see [START_REF] Fliess | Analyse non standard du bruit[END_REF], [START_REF] Fliess | Critique du rapport signal à bruit en communications numériques -Questioning the signal to noise ratio in digital communications[END_REF] for more theoretical details). The robustness properties have already been confirmed by numerous computer simulations and several laboratory experiments. Very recently, this method was used to solve the ill-posed numerical differentiation problem in [START_REF] Mboup | A revised look at numerical differentiation with an application to nonlinear feedback control[END_REF], [START_REF] Mboup | Numerical differentiation with annihilators in noisy environment[END_REF]. The main idea is to apply a differentiator called integralannihilator to a truncated Taylor series expansion which is a local approximation of the signal to be differentiated. Stable non-asymptotic differentiators of integer order were exactly given by the integrals of noisy signals involving the Jacobi orthogonal polynomials. The associated estimation errors were studied in [START_REF] Liu | Error analysis for a class of numerical differentiator: application to state observation[END_REF], [START_REF] Liu | Error analysis of Jacobi derivative estimators for noisy signals[END_REF], [START_REF] Liu | Convergence Rate of the Causal Jacobi Derivative Estimator[END_REF]. An extension of these differentiators for multivariate numerical differentiation were proposed in [START_REF] Riachy | Multivariate numerical differentiation[END_REF], [START_REF] Riachy | An algebraic method for multi-dimensional derivative estimation[END_REF], [START_REF] Riachy | Différenciation numérique multivariable I: estimateurs algébriques et structure[END_REF]. However, this method has not been used to estimate fractional order derivatives.

The aim of this paper is to introduce non-asymptotic fractional order differentiators for the Jumarie's modified Riemann-Liouville derivative by using the algebraic parametric method. In Section II, we recall how to apply the algebraic parametric method to obtain an integer order differentiator from a truncated Taylor series expansion. Section III begins with the definition of the Jumarie's modified Riemann-Liouville derivative. Then, two fractional order differentiators are obtained by applying integral-annihilators to truncated fractional Taylor series expansions with different truncated orders. Moreover, it is shown that the differentiator obtained from higher order truncated expansion can be expressed as an affine combination of the ones obtained from lower order truncated expansion. Numerical tests are given in Section IV. They help us to show the efficiency and the stability of the proposed fractional order differentiators. Finally, we give some conclusions and perspectives for our future work in Section V.

II. METHODOLOGY

Let y = x + ̟ be a noisy signal observed in an open interval I ⊂ R, where x ∈ C n (I) with n ∈ N and the noise 1 ̟ is bounded and integrable. In this section, we are going to recall how to use an algebraic parametric method to estimate the integer order derivatives of x [START_REF] Mboup | A revised look at numerical differentiation with an application to nonlinear feedback control[END_REF], [START_REF] Mboup | Numerical differentiation with annihilators in noisy environment[END_REF].

For any t 0 ∈ I, we introduce the set D t0 := {t ∈ R + ; t 0 + t ∈ I}. By using the famous Taylor's formula formulated by Hardy ([11] p. 293), we obtain that ∀ t 0 ∈ I, t ∈ D t0 ,

x(t 0 + t) = n j=0 t j j! x (j) (t 0 ) + O(t n ), as t → 0. (1)
In a similar way to classical numerical differentiation methods, the algebraic parametric method uses the n th order derivative of a polynomial to estimate the one of x. Here, we consider the following truncated Taylor series expansion of

x on R + ∀ t ∈ R + , x n (t 0 + t) := n j=0 t j j! x (j) (t 0 ). (2)
Different from the other methods, the n th order derivative of the approximation polynomial x n is calculated by applying algebraic manipulations to x n in the operational domain.

Precisely, we apply a differential operator with the following form [START_REF] Liu | Error analysis of Jacobi derivative estimators for noisy signals[END_REF] Π

n k,µ = 1 s n+1+µ • d n+k ds n+k • s n , (3)
where -1 < µ ∈ R and k ∈ N. This differential operator was introduced in [START_REF] Mboup | Numerical differentiation with annihilators in noisy environment[END_REF] with µ ∈ N.

Let us mention that the operation d n+k ds n+k • s n is used to annihilate all the terms containing x (j) (t 0 ) with 0 ≤ j ≤ n-1 in x n in the operational domain, and the rational term

1 s n+1+µ
permits to obtain a Riemann-Liouville integral [START_REF] Loverro | Fractional calculus, history, definitions and applications for the engineer[END_REF] expression for x (n) (t 0 ) in the time domain (see the next section for more details). Thus, the differential operator Π n k,µ is called integralannihilator for x (n) (t 0 ) via x n [START_REF] Mboup | Numerical differentiation with annihilators in noisy environment[END_REF]. Finally, if we replace x n by y in the obtained integral expression, then we can obtain the following estimator for x (n) (t 0 ) (see [START_REF] Liu | Error analysis of Jacobi derivative estimators for noisy signals[END_REF] and [START_REF] Mboup | Numerical differentiation with annihilators in noisy environment[END_REF] for more details)

∀ t 0 ∈ I, ỹ(n) t0 (k, µ, T ) := n! T n γ n,k,µ 1 0 w µ,k (τ )P (µ,k) n (τ ) y(t 0 + T τ ) dτ, (4)
1 More generally, the noise is a stochastic process, which is bounded with certain probability and integrable in the sense of convergence in mean square (see [START_REF] Liu | Error analysis of Jacobi derivative estimators for noisy signals[END_REF]).

where

T ∈ D t0 , γ n,k,µ = 1 B(n+k+1,n+µ+1) , B(•, •) is the classical beta function ([1], p. 258), P (µ,k) n
is the n th order Jacobi polynomial ( [START_REF] Abramowitz | editeurs. Handbook of mathematical functions[END_REF] p. 775) defined on [0, 1] as follows

P (µ,k) n (τ ) = n j=0 n + µ j n + k n -j (τ -1) n-j (τ ) j , (5)
and w µ,k (τ ) = (1τ ) µ τ k is the associated weight function.

Hence, this differentiator depends on three parameters k, µ, T . Moreover, it is a non-asymptotic pointwise differentiator using the sliding integration window [t 0 , t 0 + T ]. Since ỹ(n) t0 (k, µ, T ) is obtained by taking an n th order polynomial where n is the order of the derivative estimated, we call it minimal Jacobi differentiator.

III. NON-ASYMPTOTIC FRACTIONAL ORDER DIFFERENTIATOR

In this section, we are going to propose two fractional order differentiators by applying the algebraic parametric method to different truncated expansions of the fractional Taylor series based on the Jumarie's modified Riemann-Liouville derivative [START_REF] Jumarie | Table of some basic fractional calculus formulae derived from a modified Riemann-Liouville derivative for non-differentiable functions[END_REF], [START_REF] Jumarie | Modified Riemann-Liouville derivative and fractional Taylor series of nondifferentiable functions further results[END_REF].

A. The Jumarie's modified Riemann-Liouville derivative

Let f be a continuous function defined on R, then the Jumarie's modified Riemann-Liouville derivative of f is defined as follows [START_REF] Jumarie | Table of some basic fractional calculus formulae derived from a modified Riemann-Liouville derivative for non-differentiable functions[END_REF]

f (α) (t) := 1 Γ(l -α) d l dt l t 0 f (τ ) -f (0) (t -τ ) α+1-l dτ, (6)
where 0 ≤ l -1 ≤ α < l with l ∈ N * . This fractional order derivative is in fact defined through the fractional difference [14]

f (α) (t) := lim h→0 ∆ α [f (t) -f (0)] h α , (7)
where h > 0, F W f (t) = f (t + h) and

∆ α f (t) = (F W -1) α f (t) = ∞ i=0 (-1) i α i f [t + (α -i)h] . (8)
Let us recall that the Riemann-Liouville derivative is defined as follows ( [START_REF] Podlubny | Fractional Differential Equations[END_REF] p. 62)

0 D α t f (t) := 1 Γ(l -α) d l dt l t 0 f (τ ) (t -τ ) α+1-l dτ, (9)
where 0 ≤ l -1 ≤ α < l with l ∈ N * . If we take f (t) = t n with n ∈ N and t ∈ R * + , then we obtain (see [START_REF] Podlubny | Fractional Differential Equations[END_REF] p. 72)

0 D α t t n = Γ(n + 1) Γ(n + 1 -α) t n-α , with α ∈ R + . (10)
Consequently, the Jumarie's modified Riemann-Liouville derivative can be expressed as follows

∀ t ∈ R * + , f (α) (t) = 0 D α t f (t) - t -α Γ(1 -α) f (0). (11)
One of some useful properties of the Jumarie's modified Riemann-Liouville derivative is the fractional Leibniz derivative rule [START_REF] Jumarie | Table of some basic fractional calculus formulae derived from a modified Riemann-Liouville derivative for non-differentiable functions[END_REF]

(f g) (α) = f (α) g + g (α) f. (12)
Moreover, since x ∈ C n (I), a generalized Taylor series expansion based on the Jumarie's modified Riemann-Liouville derivative of x is given as follows [START_REF] Jumarie | Table of some basic fractional calculus formulae derived from a modified Riemann-Liouville derivative for non-differentiable functions[END_REF], [START_REF] Jumarie | Modified Riemann-Liouville derivative and fractional Taylor series of nondifferentiable functions further results[END_REF]

: ∀ t 0 ∈ I, t ∈ D t0 , x(t 0 + t) = n j=0 t j j! x (j) (t 0 ) + +∞ j=1 t jγ+n Γ(jγ + n + 1) x (jγ+n) (t 0 ), (13)
where γ = αn with n < α ≤ n + 1.

Let us remark that the fractional order derivative x (jγ+n) in ( 13) should be understood as (x (n) ) (jγ) which is different from (x (jγ) ) (n) [START_REF] Jumarie | Table of some basic fractional calculus formulae derived from a modified Riemann-Liouville derivative for non-differentiable functions[END_REF].

B. Minimal Jacobi fractional differentiator

By using (13), we take the following truncated fractional Taylor series expansion of x on R + : ∀ t 0 ∈ I, t ∈ R + ,

x α (t 0 + t) := n j=0 t j j! x (j) (t 0 ) + t α Γ(α + 1) x (α) (t 0 ). ( 14
)
Then, by using the algebraic parametric method we can give the following proposition. Proposition 1: Let y = x+̟ be a noisy signal observed on an open interval I ⊂ R, where x ∈ C n (I) with n < α ≤ n+1, n ∈ N, and ̟ be a bounded and integrable noise. Then an estimator for the α th order derivative value x (α) (t 0 ) is given by: ∀ t 0 ∈ I,

ỹ(α) t0 (k, µ, T ) := (n + 1)! T α γ n,k,µ,α 1 0 w µ,k (τ )P (µ,k) n+1 (τ ) y(t 0 + T τ ) dτ, (15)
where

T ∈ D t0 , γ n,k,µ,α = Γ(α-n) B(α+1+k,n+µ+2
) , and

P (µ,k)
n+1 is the Jacobi polynomial defined by [START_REF] Fliess | Analyse non standard du bruit[END_REF] with k ∈ N and -1 < µ ∈ R. Proof. By applying the Laplace transform to (14), we get

xα (s) = n j=0 s -(j+1) x (j) (t 0 ) + s -(α+1) x (α) (t 0 ), (16)
where xα (s) is the Laplace transform of x α (t 0 + t), and s is the Laplace variable.

We are going to apply some algebraic manipulations to [START_REF] Jumarie | Laplac's transform of fractional order via the Mittag-Leffler function and modified Riemann-Liouville derivative[END_REF]. Firstly, we apply the operation d n+1+k ds n+1+k • s n+1 to (16) so as to annihilate the terms containing x (j) (t 0 ) with 0 ≤ j ≤ n in xα . Thus, we get

d n+1+k ds n+1+k s n+1   n j=0 s -(j+1) x (j) (t 0 ) + s -(α+1) x (α) (t 0 )   =(-1) n+1+k Γ(α + 1 + k) Γ(α -n) 1 s α+k+1 x (α) (t 0 ).
Secondly, if we apply the Leibniz derivative rule to d n+1+k ds n+1+k s n+1 xα (s), then the highest order of s in the obtained sum is n + 1. Hence, we choose the rational term

1 s n+2+µ with µ > -1 such that 1 s n+2+µ • s n+1 = 1
s 1+µ with µ + 1 > 0. This permits to obtain a Riemann-Liouville integral [START_REF] Loverro | Fractional calculus, history, definitions and applications for the engineer[END_REF] expression of x α in the time domain. Consequently, we construct an integral-annihilator for x (α) (t 0 ) via x α which corresponds to the operator Π n+1 k,µ defined by (3). Consequently, by applying the inverse Laplace transform and the classical rules of operational calculus, we get

L -1    Π n+1 k,µ   n j=0 s -(j+1) x (j) (t 0 ) + s -(α+1) x (α) (t 0 )      (T ) = (-1) n+1+k Γ(α + 1 + k) Γ(α -n) T n+α+2+k+µ Γ(n + α + k + µ + 3) x (α) (t 0 ), L -1 Π n+1 k,µ xα (s) (T ) = (-1) n+1+k Γ(n + µ + 2) T 0 (T -τ ) n+µ+1 τ n+k+1 x (n+1) α (t 0 + τ )dτ. ( 17
)
By applying a change of variable τ → T τ and n + 1 times integrations by parts, we get

(-1) (n+1) T α γ n,k,µ,α x (α) (t 0 ) = 1 0 d n+1 dτ n+1 (1 -τ ) n+µ+1 τ n+k+1 x α (t 0 + T τ ) dτ. (18)
Finally, this proof can be completed by substituting x α in (18) by y and applying the Rodrigues formula ([1] p. 785) to the right side of [START_REF] Liu | An error analysis in the algebraic estimation of a noisy sinusoidal signal[END_REF]. Since the differentiator ỹ(α) t0 (k, µ, T ) involves a Jacobi polynomial, and it is obtained by taking the minimal order (j = 1) truncated fractional Taylor series expansion in (13), we call it minimal Jacobi fractional differentiator. The corresponding truncated error part comes from the truncated term +∞ j=2 t (jγ+n) Γ(jγ + n + 1)

x (jγ+n) (t 0 ). If we take α = n + 1 in (15), then it is easy to obtain that

ỹ(α) t0 (k, µ, T ) = ỹ(n+1) t0 (k, µ, T ), (19)
where ỹ(n+1) t0 (k, µ, T ) is the minimal Jacobi differentiator for x (n+1) (t 0 ) given in [START_REF] Fliess | Sur les systèmes linéaires à dérivation non entière[END_REF]. Moreover, in a similar way to the minimal Jacobi differentiator method, the minimal Jacobi fractional differentiator ỹ(α) t0 (k, µ, T ) can also be obtained by using the classical orthogonal properties of the Jacobi polynomials to [START_REF] Jumarie | Table of some basic fractional calculus formulae derived from a modified Riemann-Liouville derivative for non-differentiable functions[END_REF] (see [START_REF] Liu | Differentiation by integration with Jacobi polynomials[END_REF] for more details). Consequently, as done in [START_REF] Liu | Error analysis of Jacobi derivative estimators for noisy signals[END_REF], the parameter k which is defined on N can also be extended to ] -1, +∞[.

Finally, let us recall that the affine Jacobi differentiator being an affine combination of the minimal Jacobi differentiators was introduced in [START_REF] Mboup | A revised look at numerical differentiation with an application to nonlinear feedback control[END_REF], [START_REF] Mboup | Numerical differentiation with annihilators in noisy environment[END_REF] by applying the algebraic parametric method to a higher order truncated Taylor series expansion than [START_REF] Chen | Digital Fractional Order Savitzky-Golay Differentiator[END_REF]. Hence, the convergence rate for the Jacobi differentiator was improved. Similarly to the integer derivative case, we are going to introduce an Affine Jacobi fractional differentiator in the next subsection.

C. Affine Jacobi fractional differentiator

In this subsection, we take a new truncated fractional Taylor series expansion in [START_REF] Jumarie | Modified Riemann-Liouville derivative and fractional Taylor series of nondifferentiable functions further results[END_REF]

up to j = 2: ∀ t 0 ∈ I, t ∈ R + , x 2α-n (t 0 + t) = n j=0 t j j! x (j) (t 0 ) + t α Γ(α + 1) x (α) (t 0 ) + t 2α-n Γ(2α -n + 1) x (2α-n) (t 0 ). (20)
In order to obtain an estimator for x (α) (t 0 ) from this truncated expansion, we introduce the following differential operator

Π n+1 k,µ,α = 1 s 2α+k+µ+3 • d ds • s 2α-n+1+k • d n+k+1 ds n+k+1 • s n+1 , (21)
where

-1 < µ ∈ R, k ∈ N and n < α ≤ n + 1 with n ∈ N.
Then, we give the following proposition. Proposition 2: The differential operator Π n+1 k,µ,α defined in ( 21) is an integral-annihilator for x (α) (t 0 ) via x 2α-n defined in [START_REF] Liu | Error analysis for a class of numerical differentiator: application to state observation[END_REF]. Proof. Applying the Laplace transform to (20), we get

x2α-n (s) = n j=0 s -(j+1) x (j) (t 0 ) + s -(α+1) x (α) (t 0 ) + s -(2α-n+1) x (2α-n) (t 0 ), (22)
where x2α-n (s) is the Laplace transform of x 2α-n (t 0 + t).

We are going to apply Π n+1 k,µ,α to [START_REF] Liu | Error analysis of Jacobi derivative estimators for noisy signals[END_REF]. Firstly, we apply the operation d n+1+k ds n+1+k • s n+1 to ( 22) so as to annihilate the terms containing x (j) (t 0 ) with 0 ≤ j ≤ n in x2α-n . Thus, we obtain

d n+1+k ds n+1+k s n+1 (x 2α-n (s)) = (-1) n+1+k Γ(α + 1 + k) Γ(α -n) 1 s α+k+1 x (α) (t 0 ) +(-1) n+1+k Γ(2α -n + 1 + k) Γ(2α -2n) x (2α-n) (t 0 ) s 2α-n+k+1 . (23)
Secondly, we apply the operator d ds • s 2α-n+1+k to (23) so as to annihilate the term containing

x (2α-n) (t 0 ) in x2α-n . This yields d ds s 2α-n+1+k d n+1+k ds n+1+k s n+1 (x 2α-n (s)) = (-1) n+1+k Γ(α + 1 + k) Γ(α -n) (α -n)s α-n-1 x (α) (t 0 ). (24)
Thirdly, if we apply the Leibniz derivative rule to d ds s 2α-n+1+k d n+1+k ds n+1+k s n+1 x2α-n (s), then the highest order of s in the obtained sum is 2α + n + k + 2. Hence, we apply the rational term

1 s 2α+n+k+3+µ with µ > -1 such that 1 s 2α+n+k+3+µ • s 2α+n+k+2 = 1
s 1+µ with µ + 1 > 0. This allows us to obtain a Riemann-Liouville integral expression of x 2α-n in the time domain. Consequently, Π n+1 k,µ,α is an integralannihilator for x (α) (t 0 ) via x 2α-n . Moreover, we have

(-1) n+1+k L -1 Π n+1 k,µ,α x2α-n (s) (T ) = Γ(α + 1 + k) Γ(α -n) (α -n) T n+α+3+k+µ Γ(n + α + k + µ + 4) x (α) (t 0 ), (25)
where T ∈ D t0 .

Similarly to Proposition 1, by substituting x 2α-n by y in the obtained Riemann-Liouville integral L -1 Π n+1 k,µ,α x2α-n (T ), we obtain a new estimator for x (α) (t 0 ). We denote it by ỹ(α) t0 (k, µ, T, α). Then, we get the following proposition.

Proposition 3: Let y be a noisy signal defined as in Proposition 1, then we have the following affine relation

ỹ(α) t0 (k, µ, T, α) = λ α,k,n ỹ(α) t0 (k, µ + 1, T ) + (1 -λ α,k,n ) ỹ(α) t0 (k + 1, µ, T ), (26)
where λ α,k,n = 2α-n+1+k α-n

. The differentiator ỹ(α) t0 (k, µ, T, α) is thus called affine Jacobi fractional differentiator.

In order to prove the above proposition, we need the following lemma.

Lemma 1: Let f be the Laplace transform of an analytic function f defined on I, Π n+1 k,µ,α and Π n+1 k,µ be the integralannihilators defined in ( 21) and ( 3) respectively, then we have

Π n+1 k,µ,α f (s) = (2α -n + 1 + k) Π n+1 k,µ+1 f (s) + Π n+1 k+1,µ f (s). (27)
Proof. By applying the Leibniz derivative rule, we get

Π n+1 k,µ,α f (s) = 1 s 2α+k+µ+3 (2α -n + 1 + k)s 2α-n+k d n+k+1 ds n+k+1 s n+1 f (s) + 1 s 2α+k+µ+3 s 2α-n+k+1 d n+k+2 ds n+k+2 s n+1 f (s) =(2α -n + 1 + k)Π n+1 k,µ+1 f (s) + Π n+1 k+1,µ f (s).
Proof of Proposition 3. According to [START_REF] Machado | Calculation of fractional derivatives of noisy data with genetic algorithms[END_REF], we obtain

L -1 Π n+1 k,µ,α x2α-n (s) (T ) =L -1    Π n+1 k,µ,α   n j=0 s -(j+1) x (j) (t 0 ) + s -(α+1) x (α) (t 0 )      (T ) =L -1 Π n+1 k,µ,α xα (s) (T ) =(-1) n+1+k Γ(α + 1 + k) Γ(α -n) (α -n)T n+α+3+k+µ Γ(n + α + k + µ + 4) x (α) (t 0 ). (28)
By substituting x α by x in the Riemann-Liouville integrals L -1 Π n+1 k,µ,α xα (s) (T ) and L -1 Π n+1 k,µ xα (s) (T ) given in [START_REF] Mboup | Numerical differentiation with annihilators in noisy environment[END_REF] and ( 17) respectively, we get

x(α) t0 (k, µ, T, α) := c n,k,µ,α,T α -n L -1 Π n+1 k,µ,α x(s) (T ) x(α) t0 (k, µ + 1, T ) :=c n,k,µ,α,T L -1 Π n+1 k,µ+1 x(s) (T ) x(α) t0 (k + 1, µ, T ) := - c n,k,µ,α,T α + 1 + k L -1 Π n+1 k+1,µ x(s) (T ), (29)
where c n,k,µ,α,T = (-1) n+1+k Γ(α-n) Γ(α+1+k) Γ(n+α+k+µ+4)

T n+α+3+k+µ . Hence, by using Lemma 1 we obtain

x(α) t0 (k, µ, T, α) = λ α,k,n x(α) t0 (k, µ + 1, T ) + (1 -λ α,k,n ) x(α) t0 (k + 1, µ, T ). (30)
Finally, this proof can be completed by substituting x by y in x(α) t0 (k, µ, T, α), x(α) t0 (k + 1, µ, T, α) and x(α) t0 (k, µ + 1, T, α).

IV. NUMERICAL SIMULATIONS

In order to show the efficiency and the stability of the proposed fractional order differentiators, we give some numerical results in this section. We assume that y(t i ) = x(t i ) + ̟(t i ) is the discrete noisy observation of x on I = [0, 4] where x(t i ) = exp(0.2t i ) sin(5t i ), ̟ is a zero-mean white Gaussian noise, and t i = T s i for i = 0, • • • , 4 × 10 3 with T s = 1 10 3 . The variance of ̟ is adjusted in such a way that the signalto-noise ratio SN R = 10 log 10

|y(ti)| 2 |̟(ti)| 2
is equal to SN R = 28.07dB. We can see the original signal x and its noisy observation y in Figure 1. The exact Jumarie's modified Riemann-Liouville derivative of x can be calculated by using [START_REF] Hotzel | On linear systems with a fractional derivation: Introductory theory with examples[END_REF], [START_REF] Hardy | A course of pure mathematics[END_REF] and the Riemann-Liouville derivative of the functions sin(•) and exp(•) (see [START_REF] Miller | An Introduction to the Fractional Calculus and Fractional Differential Equations[END_REF], p. 83). We estimate the derivatives x (α) with α = 0.5 and 0.7 respectively. We apply the trapezoidal numerical integration method to approximate the integrals in our differentiators where we use m + 1 (T = mT s ) discrete observation values in each sliding integration window.

The formal derivatives and their estimated values are shown in Figure 2 and Figure 3, where the parameters k and µ are set to zero for the Jacobi fractional differentiators. On one hand, the error due to the noise for the minimal Jacobi fractional differentiator can be negligible with respect to the truncated error part which produces a time-shift in the estimate. On the other hand, the noise error for the affine Jacobi fractional differentiator is larger than the one for the minimal Jacobi fractional differentiator, but the truncated error part is much smaller. Hence, the time-shift is significant reduced.

V. CONCLUSION

In this paper, two non-asymptotic fractional order differentiators called minimal and affine Jacobi fractional differentiators are proposed by applying an algebraic parametric method to truncated expansions of fractional Taylor series. They can be used to estimate the recently invented Jumarie's modified Riemann-Liouville derivative. Numerical simulations are given so as to show their efficiency and stability with respect to corrupting noises. It is shown that these differentiators can also be obtained by using the classical orthogonal properties of the Jacobi polynomials [START_REF] Liu | Differentiation by integration with Jacobi polynomials[END_REF]. By using this method, a generalized affine Jacobi fractional differentiator will be obtained from a truncated fractional Taylor series expansion with an arbitrary truncated order in the future work. Moreover, in a similar way to [START_REF] Liu | Differentiation by integration with Jacobi polynomials[END_REF] and [START_REF] Liu | Error analysis of Jacobi derivative estimators for noisy signals[END_REF], the noise errors and the truncated errors in these differentiators will be analyzed. In particular, we will study the influence of the parameters k, µ and T to these errors so as to give a guideline for choosing the optimal parameters.

Fig. 1 .

 1 Fig. 1. Signal x and noisy signal y.

  Fig. 2. ỹ(0.5) t 0 (0, 0, T ) with T = 0.25 and ỹ(0.5) t 0 (0, 0, T, 0.5) with T = 0.26.

  Fig. 3. ỹ(0.7) t 0 (0, 0, T ) with T = 0.25 and ỹ(0.7) t 0(0, 0, T, 0.7) with T = 0.28.


Dominik Pisarski

Carlos Canudas-De-Wit

Analysis and Design of Equilibrium Points for the Cell-Transmission Traffic Model

The problem of equilibrium points for the Cell Transmission Model is studied. The structure of equilibrium sets is analyzed in terms of model parameters and boundary conditions. The goal is to determine constant input flows, so that the resultant steady state of vehicle density is uniformly distributed along a freeway. The necessary and sufficient conditions for the existence of one-to-one relation between input flow and density are derived. The equilibrium sets are described by formulas that allow to design a desired balanced density. A numerical example for the case of a two-cell system is presented.

I. INTRODUCTION

Mobility plays an important role in economy as well as in quality of human living. Every day the global impact of well organized transportation is counted in millions of tons fuel saved, thousands of fewer traffic accidents and thousands of kilograms carbon dioxide less emitted. These facts motivate even more intensive research on modeling and control of freeway systems. A good number of different control techniques, based on ramp metering and variable speed limiting, has been developed and put into practice. Most of these techniques enhance the exploitation of traffic systems by optimizing suitable metrics.

The most common metrics in use is the Total Travel Spent (TTS) and the Total Travel Distance (TTD). The former is to decrease the time of travel incurred by all drivers while the latter is to increase the usage of a freeway. TTS and TTD are often mixed with some extra terms, that penalize abrupt variations in ramp metering and speed limiting signals [START_REF] Lu | Combining Variable Speed Limits with Ramp Metering for Freeway Traffic Control[END_REF].

Most of the gradient optimization methods lead to openloop solutions [START_REF] Gomes | Globally Optimal Solutions to the On-Ramp Metering Problem -Part 1[END_REF], [START_REF] Jacquet | Optimal Control of Systems of Conservation Laws and Application to Non-Equilibrium Traffic Control[END_REF], [START_REF] Jacquet | Optimal Ramp Metering Strategy with Extended LWR Model[END_REF]. The Model Predictive Control procedure to coordinate both variable speed limits and ramp metering was presented in [START_REF] Hegyi | Optimal Coordination of Ramp Metering and Variable Speed Control -An MPC Approach[END_REF]. Optimization procedure based on the Powell's method was used to tune a close-loop regulator in [START_REF] Alessandri | Optimal Control of Freeways via Speed Signalling and Ramp Metering[END_REF]. A close-loop control system based on neural network was proposed in [START_REF] Di Febbraro | Neural Approximation for Feedback Optimal Control of Freeway Systems[END_REF]. The sliding mode control method to prevent the propagation of shock waves was presented in [START_REF] Chiang | Decentralized Control of Freeway Traffic Flow with Neighboring Cellular Information[END_REF]. The authors elaborated a decentralized scheme that exploits neighboring cellular information. ALINEA [START_REF] Papageorgiou | ALINEA: A Local Feedback Control Law for On-ramp Metering[END_REF], one of the most common in use freeway regulators, optimizes the traffic flow by using a local control law. Some other optimization techniques for freeway systems can be found in [START_REF] Kushner | Optimal and Approximately Optimal Control Policies for Queues in Heavy Traffic[END_REF], [START_REF] Gugat | Optimal Control for Traffic Flow Networks[END_REF]. Dominik Pisarski is with NeCS team INRIA, Grenoble, France, dominik.pisarski@inria.fr C. Canudas-de-Wit is a director of reearch at the CNRS, GIPSA-Lab. NeCS team, Grenoble, France, carlos.canudas-de-wit@gipsa-lab.grenobleinp.fr

In this paper, we consider the problem of state balancing for freeway traffic system. The state of such a system is represented by distribution of vehicle density while on-ramp demands are assumed for the inputs. The objective is to find input flows that result in a uniform distribution of density. In practice, this uniform distribution can be understood as an equal interdistance between vehicles. The equal interdistance can be attractive to driver's point of view. It reduces the number and intensity of acceleration and deceleration events and therefore, it makes a travel more safety and comfortable, while decreasing emissions.

The problem of state balancing is also studied for other applications. For example, in the paper [START_REF] Baric | Distributed Averaging with Flow Constraints[END_REF] the authors address the problem of averaging of a stored resource in batteries. They propose a distributed algorithm for flow control. The algorithm guarantees asymptotic convergence of states to the same value that is equal to the average of initial values.

In this paper, we investigate equilibrium sets for freeway system represented by the Cell Transmission Model (CTM). The goal for analysis is to explore balanced equilibria. The results will be crucial for future design of ramp metering strategy. A wide analysis of a behaviour of CTM was previously presented in [START_REF] Gomes | Behavior of The Cell Transmission Model and Effectiveness of Ramp Metering[END_REF]. The authors proved, that for CTM, every trajectory converges to some equilibrium state. They also showed, that for some cases, a unique input flow may produce an infinite set of equilibrium densities. The following questions then arise. What condition can assure the uniqueness of equilibrium states? What is the input that guarantees the balanced equilibrium state?

The contribution of this paper is the analysis of equilibrium sets for CTM in the context of design of balanced density equilibria. Both the qualitative and quantitative analysis is provided. In particular, the necessary and sufficient conditions for the existence of balanced equilibria are formulated. For the sake of steady state design, a relevant description of the equilibrium sets is given. Results are illustrated in a numerical example.

The organization of the paper is as follows. In the Section II, we give a brief description of CTM, together with its representation as a switched system. The preliminaries and definitions are introduced in the Section III. The Section IV is to analyse the structure of equilibrium sets. In the Section V we address the problem of design of balanced equilibrium density. Finally, conclusions are given.

ρ 0 ρ 1 φ 0 φ 1 r 0 r 1 s 0 φ n s n-1 ρ n-1
Fig. 1. Freeway divided into n cells. Each cell is accompanied with one on-ramp and one off-ramp.

II. THE CELL TRANSMISSION MODEL AND STATE SPACE REPRESENTATION

In this paper, we consider a section of a freeway divided into cells as depicted in Fig. 1. Each cell is assumed to be equipped with one on-ramp and one off-ramp. For such a system, we adopt Daganzo's Cell Transmission Model (CTM), introduced in [START_REF] Daganzo | The Cell Transmission Model: A Dynamic Representation of Highway Traffic Consistent with the Hydrodynamic Theory[END_REF].

For the cell i we assume the following notation: ρ i -vehicle density, φ i -mainstream flow entering the cell, r i -on-ramp flow entering the cell, s i -off-ramp flow leaving the cell, v ifree flow speed, w i -congestion wave speed, F i -capacity, ρijam density, l i -cell length. The relation between flow and density is represented by the triangular fundamental diagram (see Fig. 2).

CTM describes the evolution of the system in discrete time t k = k ∆t, with k ∈ N. Time step ∆t > 0 is taken small enough to provide convergence condition (for details see [START_REF] Leveque | Numerical Methods for Conservation Laws[END_REF]). For the cell i the governing equation is:

ρ i (k + 1) = ρ i (k) + ∆t l i Φ + i (k) -Φ - i (k) . (1)
Here Φ + i (k) and Φ - i (k) are total flows entering and leaving the cell i, i.e.:

Φ + i (k) = φ i (k) + r i (k) , Φ - i (k) = φ i+1 (k) + s i (k) . (2)
By introducing Demand D i and Supply S i functions:

D i (k) = min βi v i ρ i (k), F i , S i (k) = min {w i (ρ i -ρ i (k)), F i } (3)
according to Daganzo's merge connection model mainstream and on-ramp flows for i = 0, 1, ..., n-1 are given as follows:

if D i-1 (k) + u i (k) ≤ S i (k) : φ i (k) = D i-1 (k) , r i (k) = u i (k) otherwise : φ i (k) = mid {D i-1 (k), S i (k) -u i (k), (1 -p i ) S i (k)} , r i (k) = mid {u i (k), S i (k) -D i-1 (k), p i S i (k)} . (4)
Here the function mid {•} returns the middle value. We will say, that the cell i is in free state if

ρ i v i ≤ F i . Otherwise, it is in congested state.
In (4) we introduced on-ramp demands u i that will appear later as the inputs for the control system. By p i ∈ [0, 1] we denote a parameter, that captures the priorities between mainstream flow φ i and on-ramp flow r i when merging in a cell during the congestion. In order to determine the value for p i we should consider geometrical properties of on-ramp as well as drivers' behaviour. For the most of the cases, we can assume, that the priority is for the mainstream flow, and therefore we set p i < 0.5 .

The boundary conditions are determined by some demand function D(k) = D -1 (k) for the cell 0 and some supply function S(k) = S n (k) for the cell n -1. For the flow φ n we adopt the simple connection model, and therefore:

φ n (k) = min D n-1 (k), S(k) . (5)
Finally, for the off-ramp flows we assume:

s i (k) = 1 -βi βi φ i+1 (k) . (6)
Here βi = 1-β i , where β i ∈ [0, 1) stands for the split ratio, which is the parameter, that specifies a number of vehicles leaving the cell i.

For the convenience of our further investigation, we rewrite the governing equation (1) in a form of a switched control system:

x(k + 1) = A s(k) x(k) + B s(k) u(k) + C s(k) (k) , s(k) = f (x(k), u(k)) . (7)
Here the state vector x ∈ X and the input vector u ∈ U stand for vehicle densities and input flows (on-ramp demands), respectively:

x = (ρ 0 , ρ 1 , ..., ρ n-1 ) , u = (u 0 , u 1 , ..., u n-1 ) . ( 8
)
The sets X ∈ R n and U ∈ R n respect minimum and maximum values for densities and on-ramp demands. The switching variable s ∈ S = {1, 2, ..., m} indicates a mode of the system, and it determines terms in the matrices A n×n , B n×n and for the vector C n×1 (k). The vector C n×1 (k) consist of the boundary functions D(k) and S(k). Notice that m is a total number of all possible modes generated by nonlinear formulas for mainstream and on-ramp flows.

III. PROBLEM FORMULATION

As it was stated in the introduction, the goal of this paper is to analyse the structure of equilibrium sets for CTM. In particular, we will investigate sets of balanced equilibrium points. Before going into the analysis, we first introduce some formal definitions.

Definition

The equilibrium set ∆ for CTM described by ( 7) is a set of pairs (x * , u * ) that under a fixed boundary conditions solve the following equilibrium equation:

(A s -I) x * + B s u * + C s = 0 , s = f (x * , u * ) , s ∈ S . (9)
Here I stands for the identity matrix. In terms of (1) the steady state is reached when for every cell, the total flow entering and leaving are equal. Notice that vectors C s becomes constant, when boundary conditions have fixed value, i.e.: D(k) = D and S(k) = S. By ∆ x and ∆ u we denote the set of equilibrium density and equilibrium input flow, respectively. In order to analyse the structures of ∆ we need to represent it in a more convenient way. This can be done by introducing a relevant set of inequalities. First, we decompose ∆ into subsets that correspond to the modes of the system. For every s ∈ S we define the following set:

∆ s = {(x * , u * ) : (A s -I) x * + B s u * + C s = 0 , s = f (x * , u * )} . ( 10
)
Then we have ∆ = 3)- [START_REF] Hegyi | Optimal Coordination of Ramp Metering and Variable Speed Control -An MPC Approach[END_REF]. Therefore, by introducing relevant inequalities we can rewrite every ∆ s as:

∆ s = {(x * , u * ) : (A s -I) x * + B s u * + C s = 0 , K s x * + L s u * + M s ≤ 0} . ( 11
)
Here the matrices K s , L s and the vector M s are constant.

To illustrate how to build inequalities in [START_REF] Gugat | Optimal Control for Traffic Flow Networks[END_REF] we give an example for the case of a two-cell system. Using (1)-( 6) we can write:

for s = 1 : D + u * 0 = 1 β0 D 0 , D 0 + u * 1 = 1 β1 D 1 , D + u * 0 ≤ S 0 , D 0 + u * 1 ≤ S 1 , D 1 ≤ S , for s = 2 : S 0 = 1 β0 D 0 , D 0 + u * 1 = 1 β1 D 1 , D + u * 0 ≥ S 0 , D 0 + u * 1 ≤ S 1 , D 1 ≤ S , and so forth, till s = m . ( 12
)
Inserting relevant formulas for Demand and Supply functions for s = 1 we have:

-v 0 0 β0 v 0 -v 1 x * 0 x * 1 + 1 0 0 1 u * 0 u * 1 + D 0 = 0 ,   w 0 0 β0 v 0 w 1 0 β1 v 1   x * 0 x * 1 +   1 0 0 1 0 0   u * 0 u * 1 +   D -w 0 ρ0 -w 1 ρ1 - S   ≤ 0 . (13)
For the set ∆ we will pay the special attention to these points (x * , u * ), where x * are balanced. Before we describe this balance, let us introduce a set of admissible balanced density:

C = c : 0 ≤ c ≤ min{ ρi } n-1 i=0 . ( 14
)
Then the set of balanced equilibrium points ∆ B ⊂ ∆ is defined as follows:

Definition ∆ B is a set of equilibrium points (x * , u * ), such that the equilibrium density is balanced, i.e.:

x * = c 1 , c ∈ C . ( 15
)
Here 1 n×1 stands for all-ones vector. By analogy to the set ∆ we will denote by ∆ xB and ∆ uB the set of balanced equilibrium densities and the set of related equilibrium input flows, respectively. The objectives of this paper are as follows. To determine how the shape of ∆ corresponds to model parameters. To derive a condition, that ensures the existence of the set ∆ B . To provide formulas, that enable us to find input flows u * , so that the resulting equilibrium density x * is balanced.

Before we go further, we need to recall some basic facts on the relation between the sets ∆ u and ∆ x . In the paper [START_REF] Gomes | Behavior of The Cell Transmission Model and Effectiveness of Ramp Metering[END_REF], it was presented, that in general the mapping ∆ u -→ ∆ x is not one-to-one. The authors provided a simple example, where they fixed values for demands and input flows. The resulting equilibrium density was not a unique point. It was represented by some set of points instead. It was shown, that the steady state was determined not only by the input but also by the initial state. Therefore, for such a case, the design of density equilibria is not feasible. In this paper, we consider only these cases for which any fixed input flow results in a unique equilibrium density. Moreover, we focus only on these points of (x * , u * ) ∈ ∆ such that the mapping ∆ u -→ ∆ x is bijective. Notice that ∆ u -→ ∆ x is bijective for the mode s iff both (A s -I) and B s are invertible.

IV. STRUCTURE OF EQUILIBRIUM SETS

In this section, we describe the structure of the set ∆. As stated before, we limit our investigation to these equilibria that respect the one-to-one property. From (4) we can observe that matrix B s is invertible iff the following conditions are satisfied:

D + u * 0 ≤ S 0 , D i-1 + u * i ≤ S i , i = 1, 2, ..., n -1 . (16)
Under this assumption, the equilibrium equation in ( 9) is represented by:

D + u * 0 = 1 β0 D 0 , D i-1 + u * i = 1 βi D i , i = 1, 2, ..., n -2 , D n-2 + u * n-1 = 1 βn-1 min D n-1 , S (17)
To ensure the invertibility of (A s -I) we need to impose additional conditions, i.e.:

D n-1 ≤ S , βi v i x * i ≤ F i , i = 0, 1, ..., n -1 . ( 18
)
Under the condition (18) we can rewrite (17) as follows:

D + u * 0 = v 0 x * 0 , βi-1 v i-1 x * i-1 + u * i = v i x * i , i = 1, 2, ..., n -1 . ( 19
)
Let us define Γ as the one-to-one mapping ∆ u -→ ∆ x described by (19).

Based on ( 16)-( 18) we can formulate the necessary condition for the existence of Γ in terms of boundary and input flows.

Proposition 4.1:

There exist the mapping Γ only if :

n-1 i=0 βi D + n-1 i=0   n-1 j=i βj u * i   ≤ S ( 20
)
Proof: From (18) we have:

D n-1 ≤ S . ( 21
)
Inserting D n-1 from ( 17) we obtain:

βn-1 D n-2 + βn-1 u * n-1 ≤ S . ( 22
)
Repeating this substitution from D n-2 to D 0 we get (20).

For the analysis of the equilibrium set we consider only two special cases. In the first case we assume, that all cells are in the free state. Then we describe the shape of ∆ in terms of system parameters. The second case is to show, that for the congested state, the conditions ( 16)-( 18) drive to contradiction.

A. Set of free equilibrium points

Definition The set of free equilibrium points ∆ f ⊂ ∆ is a set of pairs (x * , u * ) where x * is the free state, i.e.:

v i x * i ≤ F i , i = 0, 1, ..., n -1 . ( 23
)
Consistently, we will denote by ∆ f x and ∆ f u the sets of free equilibrium densities and sets of corresponding equilibrium input flows, respectively Now we will formulate the sufficient condition for the existence of Γ under x * ∈ ∆ f

x . First we show, that the condition:

βi v i x * i ≤ F i , i = 0, 1, ..., n -1 . ( 24
)
F 0 v 0 1 ∆ f x x * 0 F 1 v 1 x * 1 v 1 β0 v 0 β0 D v 1 D v 0
Fig. 3. An example of the set of free equilibrium densities for the case of two-cell system. The grey trapezium is for the set ∆ f

x . The blue line indicates balanced states.

∆ f u u * 1 u * 0 F 0 - D F 1 -β0 D
Fig. 4. An example of the set of free equilibrium input flows for the case of two-cell system. The grey triangle is for the set ∆ f u .

is satisfied. Indeed, it is because for βi ≤ 1 we have:

βi v i x * i ≤ v i x * i ≤ F i , i = 0, 1, ..., n -1 . ( 25
)
Proposition 4.2: Let x * be some free state equilibrium. Then, there exist the mapping Γ if the following conditions hold:

D + u * 0 ≤ F 0 , βi-1 v i-1 x * i-1 + u * i ≤ F i , i = 1, 2, ..., n -1 , βn-1 v n-1 x * n-1 ≤ S . (26)
Finally, we can describe the sets ∆ f x and ∆ f u as follows:

∆ f x = {x * ∈ X : v i x * i ≤ F i , i = 0, 1, ..., n -1 , x * 0 = D + u * 0 v 0 , x * i = βi-1 v i-1 x * i-1 + u * i v i , i = 1, 2, ..., n -1 , u * ∈ ∆ f u } , (27)
∆ f u = {u * ∈ U : u * 0 ≤ F 0 -D , u * 1 ≤ F 1 -β0 ( D + u * 0 ) , u * 2 ≤ F 2 -β1 ( β0 (φ 0 + u * 0 ) + u * 1 ) and so forth } . (28)
In Fig. 3 we present the shape of ∆ f x (grey trapezium) for the case of a two-cell system. The corresponding set ∆ f u is represented by grey triangle depicted in Fig. 4. We can observe how the system parameters affect on ∆ f

x . For instance, if the slope of the left bound (indicated by red line) is less then 1, then the set is represented by a triangle placed below the blue line indicating balanced states. Therefore, in this case the set ∆ xB would be empty. We will explore this fact in details in the section V.

B. Set of congested equilibrium points

Definition The set of congested equilibrium points ∆ c ⊂ ∆ is a set of pairs (x * , u * ) where x * is the congested state, i.e.:

v i x * i > F i , i = 0, 1, ..., n -1 . (29)
Now we will show, that under the conditions ( 16)-(18) the set ∆ c is empty. For the congested case (S i < F i for all i) the condition in ( 16) is as follows:

D + u 0 ≤ S 0 < F 0 . (30)
On the other we have assumed that:

x * 0 v 0 > F 0 . (31)
Thus the equality:

D + u 0 = x * 0 v 0 ( 32
)
is a contradiction and therefore, for the congested case the mapping Γ does not exist.

V. DESIGN OF BALANCED EQUILIBRIUM STATES

So far, we have derived the necessary and sufficient conditions for the existence of Γthe relation, that allows as to design equilibrium densities x * ∈ ∆ x . In order to design balanced equilibrium x * ∈ ∆ xB , we need to impose some additional requirements.

In the previous section, we proved that Γ exists only for the free state case. Therefore, for the admissible balanced densities we consider only these points c ∈ C that satisfy the condition:

c ≤ min F i v i n-1 i=0 . (33)
Then the set of balanced equilibrium points ∆ B can be defined as a set of pairs (u * , c), that solve the equations:

D + u * 0 = v 0 c , βi-1 v i-1 c + u * i = v i c , i = 1, 2, ..., n -1 . (34)
Respecting real freeway scenarios we have to assume:

u * ≥ 0 . (35)
Then we can formulate the necessary condition for the existence of balanced equilibria.

Proposition 5.1: Let u * i ≥ 0 for i = 0, 1, ..., n -1. Then, there exists a balanced free equilibrium point only if :

βi-1 v i-1 ≤ v i , i = 1, 2, ..., n -1 . ( 36
)
Proof: Let us assume βi-1 v i-1 > v i for i = 1, 2, ..., n -1. Then (34) is a contradiction under u ≥ 0.

Remark A practical fact comes up with the Proposition 5.1. In order to design a balanced equilibrium point we may need to apply the variable speed limiting, where the speed limits depend on actual values of the split ratios.

Finally, we can describe the sets of balanced equilibrium points: ∆ f uB = {u * ∈ U :

∆ f xB = {x * = c1 : c ≤ min F i v i n-1 i=0 , c = D + u * 0 v 0 , u * ∈ ∆ f uB } , (37)
u * 0 ≤ v 0 min F i v i n-1 i=0 -D , u * i ≤ (v i -βi-1 v i-1 ) min F i v i n-1 i=0 , D + u * 0 v 0 = u * i v i -βi-1 v i-1 , i = 1, 2, ..., n -1 } , (38)
A. Optimal balanced equilibrium point Among the points x * ∈ ∆ f xB we can find the one that optimizes some objective function. For example, we can consider the balanced equilibrium state that maximizes the total input volume (TIV). We define TIV as follows:

J T IV = n-1 i=0 u * i . (39)
Then the optimal balanced equilibrium density is:

x * * = D + u * * 0 v 0 1 , (40)
where u * * 0 solves the following optimization problem:

F ind u * * 0 = max u * 0 , under u * ∈ U , u * 0 ≤ v 0 min F i v i n-1 i=0 -D , u * i ≤ (v i -βi-1 v i-1 ) min F i v i n-1 i=0 , D + u * 0 v 0 (v i -βi-1 v i-1 ) ≤ u * i , i = 1, 2, ..., n -1 .
(41)

B. Numerical example

To illustrate the results, we present the numerical example for a two-cell system. We assume that all cells have the same free flow speeds and there is no off-ramps ( β0 = β1 = 1). In this case, from (34) we immediately conclude, that a In Fig. 6 we present the state trajectories for the case of u * 0 = 500 (veh/h) and u * 1 = 0. The attractive point is x * 0 = x * 1 = 91.6 (veh/km).

VI. CONCLUSIONS AND FUTURE WORKS

In this paper, the analysis of structure of equilibrium sets for the Cell Transmission Traffic Model has been presented. We have limited our attention to the case, that provides one-to-one mapping between inputs and equilibrium states. This case requires two conditions to be satisfied. First, total demand weighted with split ratios must not exceed supply for the downstream boundary. Second, all cells are in the free state. Under these conditions, we have shown, that the balanced state exists only if the additional relation between free flow velocities and split ratios holds. This suggests that in practical design of balanced equilibria, we may need to use both ramp metering and variable speed limiting, where speed limits depend on actual values of split ratios. For the special case, where parameters for all cells are equal and there is no off-ramps, the balanced state is possible only if the first on-ramp is serving cars while others are closed. In future works, we will address the problem of state balancing for the cases, where the necessary conditions presented here are not fulfilled. The idea is to approach near balanced state while staying within the equilibrium set. This will be formulated as an optimization problem. Further step will be to find near balanced state, so that some objective (for example, TTD) is optimized.

Fig. 2 .

 2 Fig.2.The fundamental diagram. The shape is determined by the parameters: F -capacity, v -free flow velocity, w -congestion wave speed.

∆

  s . The function f results from mid{•} and min{•} terms in (

Fig. 5 .

 5 Fig. 5. Numerical example for the set ∆ f xB (color line). The left end of the line corresponds to the input flow vector: u * 0 = 0, u * 1 = 0 while the right one is for u * 0 = 1000, u * 1 = 0.

Fig. 6 .

 6 Fig. 6. State orbits (color curves) and balanced equilibrium density (green dot) for the case of u * 0 = 500, u * 1 = 0.

VII. ACKNOWLEDGMENTS

The research leading to these results has received funding from the European Union Seventh Framework Programme [FP7/2007-2013] under grant agreement n 0 257462 HYCON2 Network of excellence.