Thèmes de recherche prioritaires

  Voici une liste de thèmes de recherche prioritaires du groupe. Ils constituent les noyaux à partir desquels des projets plus ciblés seront définis à l'issue de l'action présente. Ces thèmes étaient présentés dans la rédaction initiale de 1996: on reprend à dessin verbatim cette rédaction, en la faisant suivre à chaque fois d'un bref bilan des interventions.

1. Développement des modèles algébriques de systèmes à événements discrets. But: augmenter la classe des systèmes analysables.

   Des modèles très variés de nature algébrique ont été employés jusqu'ici pour représenter des SED. On a rappelé plus haut comment les systèmes dynamiques (max,+) et leurs extensions (systèmes , , automates à multiplicités) permettent de représenter diverses classes de SED. D'autres modèles ont été introduits. L'école fondée par Ramadge et Wonham verrait plutôt les mêmes systèmes comme des automates usuels (systèmes dynamiques booléens). Des modèles d'automates généralisés à la Alur-Dill sont aussi d'un emploi courrant pour les questions de vérification. Dans un autre esprit, la modélisation du parallélisme par des monoïdes et langages de traces est maintenant classique. Pour être complet, il faudrait aussi parler de la techniquement très différente modélisation de SED par des systèmes dynamiques sur des corps finis, motivée à l'origine par les problèmes de calcul d'horloge pour les systèmes temps réels.

   On a affaire ici à une multiplicité de points de vue qui reste mal comprise, souvent génante. Devant une application nouvelle, il est parfois difficile de discerner les modèles pertinents. Les questions susceptibles d'être examinées par l'une ou l'autre de ces approches ne se recoupent pas toutes. Une tâche urgente consisterait à mieux cerner les pouvoirs d'expression et d'analyse respectifs des différents modèles, afin d'étendre la classe des systèmes analysables.

   Bilan 97. Ce thème est l'un de ceux qui ont le plus progressé. Il intéresse de nombreuses équipes du groupe (particulièrement INRIA Rocq. et ENSMP, INRIA Sophia, LIAFA, Nantes). Exposés de: B. Gaujal, J.J. Loiseau, et exposé à venir J. Mairesse (Juin).

   À la question ``quels sont les systèmes analysables via le semianneau (max,+)'', on répondait naguère ``les graphes d'événements'', c'est à dire des phénomènes de synchronisation (assemblage), ne prenant pas en compte l'aspect combinatoire (ordonnancement des tâches, routage à optimiser), vital dans la majorité des applications. On répondrait volontiers aujourd'hui ``les réseaux de Petri à choix libre'' ``multilinéaires'' (min,+), ou les résaux de Petri safe, lesquels se modélisent par des automates-empilements de pièces, ce qui est beaucoup plus général, et donne lieu à des problèmes algorithmiques nouveaux.

2. Algèbre effective et évaluation de performance. But: calculer rapidement, ou calculer tout court, le débit de systèmes à événements discrets (réseaux de transports, systèmes multiprocesseurs, ateliers, éventuellement stochastique).

   Il s'agit de voir de quelle manière l'algorithmique associée aux représentations algébriques (séries rationnelles (max,+) et semigroupes qui les sous-tendent, séries algébriques, variantes partiellement commutatives, arithmétique des ensembles semi-linéaires) peut s'appliquer à des calculs explicites de performance pour les systèmes à événements discrets déterministes et stochastiques. Par exemple, l'un des problèmes ouverts importants aujourd'hui consiste à calculer ou à approcher les exposants de Lyapunov (taux de croissance) de produits de matrices aléatoires (max,+), pour des classes suffisamment larges de systèmes. Une autre direction de recherche consisterait à voir de quelle manière les algorithmes de décision développés pour les langages à multiplicités sur le semianneau tropical peuvent s'appliquer à la vérification de SED. On fera aussi le point sur les outils de calcul formel et numérique (max,+), ceux-ci n'étant aujourd'hui disponibles que de manière parcellaire et faisant parfois défaut lorsqu'il s'agit de traiter une application de taille réaliste.

   Bilan 97. On a surtout traité le calcul de taux de production dans le cas stochastique (exposants de Lyapunov). Ce thème intéresse à la fois les plus combinatoriciens du groupe (LIAFA) et les probabilistes des SED (INRIA Sophia, Grenoble). La journée du 2 Décembre était dédiée à ce thème (exposés de F. Baccelli, D. Krob, J.M. Vincent, et P. Chretienne pour les problèmes d'ordonnancement reliés).

   Bizarrement, le problème ``le plus simple'' des SED stochastiques, i.e. le calcul du débit ou exposant de Lyapunov, est une mine de problèmes ouverts difficiles. Il y a semble t il des liens profonds entre ces calculs et la combinatoire des monoïdes de traces. On a un petit dictionnaire de modèles exactements résolus (techniques de chaînes de Markov, séries génératrices, méthodes de perturbations) qu'on a aperçu pendant la journée spécialisée du 2 Décembre, mais dont on est encore loin de comprendre la généralité.

   La partie purement algorithmique et logicielle sera abordée à partir de la réunion de Novembre.

3. Commande de Systèmes à Événements Discrets. Il s'agit de poursuivre l'étude des SED sur le modèle de l'Automatique classique. Parmi les problématiques familières qui n'ont pour l'instant que des analogues imparfaits en termes de SED (max,+) linéaires, citons les questions de commandabilité, observabilité (non structurelles), les questions de poursuite de trajectoire, de modèle, de rejet de perturbation, de stabilisation. C'est toute l'approche ``géométrique'' de la théorie des systèmes qui reste ici à faire. En liaison avec le point précédent, se pose dans ce contexte de façon cruciale la question du calcul effectif des lois de commande que prévoit la théorie et du développement d'une méthodologie de la commande des SED.

   Bilan 97. Ce thème intéresse les plus automaticiens du groupe (INRIA Rocq., Nantes, Angers). Il a aussi une composante purement algébrique (théorie des semimodules), essentielle pour comprendre la géométrie de ces systèmes dynamiques (ensembles d'états accessibles, réalisation) et très liée à des questions de théorie des semigroupes qui sont la spécialité du LIAFA (éléments réguliers --ici dans des semigroupes linéaires--, classes de Green). Exposés d'E. Wagneur (semimodules) et d'E. Menguy (commande).

4. Approche (max,+) de la commande optimale On continuera à développer cette théorie, et particulièrement, à faire le parallèle avec les SED (certains résultats connus pour les SED ayant des analogues nouveaux en optimisation, et réciproquement). Ces applications posent des questions d'Analyse Idempotente aujourd'hui imparfaitement comprises (par exemple autour de la discrétisation en espace de l'équation de Hamilton-Jacobi).

   Bilan 97. Il faudrait probablement rebaptiser ce thème majeur ``Analyse Idempotente et Commande Optimale''. C'est l'une des parties les plus neuves et actives. Trois exposés dont deux de synthèse ont été donnés: S. Samborski, M. Gondran, sur l'approche (min,+) linéaire des EDP de Hamilton-Jacobi, M. Akian, sur les probabilités (max,+) (ou comment utiliser le formalisme des probabilités pour résoudre des problèmes d'optimisation), illustré par un exposé de P. Bernhard, sur les analogues théorie des jeux--commande robuste du principe d'équivalence à la certitude bien connu en commande linéaire quadratique gaussienne. La synthèse d'H. Prade (versions (min,max) et (min,+) de la théorie de l'utilité) a mis en lumière un pan de littérature que beaucoup ignoraient.

   Il reste beaucoup à exposer sur ce thème. En particulier, les aspects asymptotiques très riches (grandes déviations) n'ont pas encore été traités.

5. Opérateurs (max,+) linéaires en dimension infinie et grands systèmes à événements discrets. Les travaux existants sur l'approche (max,+) des équations de Hamilton-Jacobi-Bellman devraient faire faire des progrès dans la compréhension des ``grands'' systèmes à événements discrets, donnant lieu aux mêmes équations par passage à la limite. On peut s'interroger aussi sur un ``calcul opératoriel'' (max,+) à la Maslov (calcul de solutions explicites à certaines équations de Hamilton-Jacobi-Bellman) ce qui rejoint les préoccupations d'algèbre effective évoquées plus haut.

   Bilan 97. Thème un peu jeune. Pas encore d'action.

6. Prospection d'applications issues de communautés voisines. On fera un effort d'exploration de ces applications, du moins lorsque les outils (max,+) semblent pertinents. On peut citer les problèmes d'ordonnancement (la compréhension algébrique des phénomènes de synchronisation devant conduire à des heuristiques ou à des bornes raisonnables), ainsi que les questions de vérification (garantie de temps de réponse) et de synthèse de systèmes temps réel qui préoccupent les communautés des langages synchrones et des automates temporisés.

   Bilan 97. Exposés de J. Mattioli (Detection de défauts dans des images) d'A. Benveniste (prévu à la réunion de Juin, lien (max,+) et systèmes temps réel).