Mohamed Khalid Didi Alaoui

This report concerns the modeling and analysis of timed and time Event Graphs (EG), by means of algebraic tools like the dioïds or algebra of topical functions. The mathematical modeling of these Discrete Event Dynamic Systems (DEDS) leads to equations and inequations systems using minimum, maximum and addition operations. In the first part, the general form obtained is called an "interval model" which allows making a classification of different EG considered, according to an analysis of these functions. The algebraic model of time stream EG for two semantics, includes the different time EG models which model time on the places, the transitions or the arcs (timed, p-time, t-time, time arcs ...). In the second part, we analyze the liveness of time EG. The study of the synchronization phenomena enables the verification of the existence of the state vector by two approaches: the first uses the spectral theory of the (min, max, +) functions and can be applied to time stream EG; the second one exploits a matrices series and concerns p-time EG. The DEDS are subjected to disturbances like failures which can generate a bad determination of the state vector. Then We deal the problem of the state estimate in timed and time stream EG. The estimator proposed also allows the development of a new approach for the fault detection. Finally, the optimal control for time stream EG is studied. The determination of the control is made by applying a fixed point approach like the one used for estimation. The particularization of this approach to the timed EG case, allows finding the traditional "Backward" equations. The verification of the existence of an optimal control is made by exploiting the spectral theory of the (min, max, +) homogeneous functions.

Key-words: Discrete event dynamic systems, time and timed event graphs, algebra of topical functions, dioids, fixed point, liveness, estimate, control.

Les travaux de recherche portent sur la modélisation et l'analyse de Réseaux de Petri du type graphes d'événements temporisés et temporels au moyen d’outils algébriques comme l'algèbre des dioïdes et topicale. Les graphes d'événements p-temporels et à flux temporels permettent en particulier, l’introduction de contraintes de temps sous forme d'intervalles et l’expression d’un certain non-déterminisme. La modélisation mathématique de ces systèmes dynamiques à événements discrets conduit à des systèmes d'équations et d’inéquations utilisant les opérations minimum, maximum et addition.

Une première partie traite de la modélisation de différents graphes d’événements temporels dans ces nouvelles structures algébriques. La forme générale est un modèle dit d’intervalle qui permet de faire une classification des différents graphes considérés selon une analyse des fonctions.

Un autre centre d’intérêt est l’analyse de la vivacité des graphes d'événements en particulier p-temporels. L’étude des phénomènes de synchronisation permet de vérifier l'existence du vecteur d'état. On en déduit un fonctionnement ne présentant pas de mort de jetons et conservant la vivacité des transitions. Dans le cas contraire, on pourra détecter les désynchronisations, isoler les transitions en cause et déterminer le nombre d’événements correspondant. Deux approches sont présentées. La première utilise le vecteur spectral en se basant sur le graphe de calcul. Cependant, ce dernier présente une dimension infinie. L’introduction d’une série particulière de matrices permet de résoudre cette difficulté pour les P-temporels.

Un autre problème étudié est la commande des graphes d’événements temporisés et temporels. La vérification de l’existence d’un contrôle optimal de la classe modèle d’intervalle est faite en exploitant la propriété d’homogénéité des fonctions (min, max, +). La détermination de la commande est faite en appliquant une méthode du type point fixe. Cette démarche est appliquée sur les graphes d’événements à flux temporels. Comme pour la vivacité, la gestion du caractère infini du graphe de calcul doit être réalisée. Pour les graphes d’événements p-temporels, nous proposons une approche permettant de déduire les trajectoires extrémales et la commande optimale du système. Ces deux approches généralisent de manière naturelle les équations backward appliquées classiquement pour synthétiser la commande des graphes d’événements temporisés.

La dernière partie traite de l’estimation d’état. L’existence de perturbations peut en effet générer une mauvaise détermination du vecteur d’état. Le problème de l'estimation d'état des graphes d’événements temporisés est résolu grâce à une approche duale de celle de la commande. Une technique similaire aux méthodes des observateurs utilisés dans le cas des systèmes continus a été développée pour estimer le plus grand état. De même, le vecteur spectral permet d’exprimer des relations similaires à celles obtenues dans l’espace de parité classique. Se basant sur une approche du type propagation de contraintes, des algorithmes spécifiques aux graphes d’événements temporisés et à flux temporels sont proposés. Les tests montrent que ces approches permettent la détection de défaillances et par exemple de détecter un biais dans une temporisation.