MODÉLISATION ET sYNTHÈsE DE CONTRÔLEURS DES SYSTÈMES HYBRIDES L I N É ~ S

mémoire présenté au Département de mathematiques

et d'informatique en vue de l'obtention du grade de maître ès scienoes (M-Sc.)

FACULTÉ DES SCIENCES

UNIVERSIT* DE SHERBROOKE

Sherbrooke, Québec, Canada, décembre 1999

National Library 1+1 ofcanada Bibliothèque nationale du Canada

Acquisitions and Acquisitions et Bibliogmphic Services services bibliographiques

395 Wellington Street 395, rue Wellington Ottawa ON K1A ON4 Ottawa ON K1A ON4 Canada Canada

Your file Voire réference

Our Ne Notre refBrenœ

The author has granted a non- exclusive licence dowing the National Lïbrary of Canada to reproduce, loan, distribute or sell copies of this thesis in microfom paper or electronic formats.

The author retains ownership of the copyright in this thesis. Neither the thesis nor substantial extracts from it may be printed or othewïse reproduced without the author's permission.

L'auteur a accorde une licence non exclusive permettant à la Bibliothèque nationale du Canada de reproduire, prêter, distribuer ou vendre des copies de cette thèse sous la forme de microfiche/film, de reproduction sur papier ou sur format électronique.

L'auteur conserve la propriété du droit d'auteur qui protège cette thèse. Ni la thèse ni des extraits substantiels de celle-ci ne doivent être imprimés ou autrement reproduits sans son autorisation.

Sommaire

Ce mémoire présente, d'abord, une méthode de modélisation des systèmes hybrides

linéaires. Le modèle adopté pour la modélisation d'un procédé physique ayant une com-

posante continue et une composante discréte est un automate hybride linéaire qui définit

une sousclasse des automates hybrides. Ce travail se situe dans le cadre des travaux de

Thomas Henzinger.

Ensuite, une procédure de synthèse de contrôleurs des systQnes hybrides linéaires a

été développée. Cette procédure consiste à transformer une procédure de vgification.

en une procédure de synthèse. D'où, la présentation d'un outil de vérification nommé

HYTECH ainsi que son adaptation en un outil de synthèse.

Dans ce mémoire, nous considérons un système de positionnement d'antennes comme

exemple d'application-

Remerciements

Il m'est très agréable de pouvoir exprimer toute la reconnaissance que je porte à

mon directeur de recherche, Monsieur Richard St-Denis, pour ses conseils, son profes-

sionnalisme et sa participation à la réalisation de ce projet,

Je tiens à remercier mon codirecteur de recherche, Monsieur Moncef Tajina, qui m'a

toujours fait confiance et qui a su m'encourager à surmonter les difficultés. Sa grande

patience, sa disponibilité, son professio~alisme, ses &tés méthodique et scientifique

m'ont perrnis de développer les qualités requises pour la réalisation de ce mémoire.

Je ne peux passer sous silence le soutien moral et les encouragements de Madame

Alia Takb chef du département d'inf'ormatique de l'université Libre de Tunis.

Je tiens égaiement à remercier mes enseignants Monsieur Yahya Slimani, Monsieur

L a s s d Mejri et tout le personnel du département d'informatique de 1'ULT pour leur

disponibilité et amabilité. Je saisis cette occasion pour exprimer mes reconnaissances à

la bibliothécaire Madame Raja Kaœm pour ses conseils et sa sympathie.

Enfin, qu'il me soit permis d'exprimer ma gratitude à mes parents, mon k&e et mes

soeurs qui m'ont incité et permis d'entreprendre des étudeç supérieures.

... 111

Table des matières

Sommaire

Remerciements

Table des matières

Liste des tableaux

Liste des figures

iii

iv

vii

viii

Introduction 1

Problème . . . . . . - . . . . . . . . . . - . . . . . . . . . . . . . . . . . . . . 8

Méthodologie . . . . . . . . . . . . - . . . - - . . . . . . . . . - . . . . . . . 9

Résultats , . - . . . - . . - . . . . . . . . - . . . . . . - . . . - - . . . . . . . 10

Organisation du mémoire . . . . . . . . . . . . . . . . . . . . . - . . . . . . . 11

1 Modélisation des systèmes hybrides 12

1.1 Un automate hybride . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.1.1 Définition d'un automate hybride . - . . . . . . . . . . . . . . . . 13

1.2 Système de transitions . . . . . . . . . . . . - . . . . . . - . - . . . . . . 17

1.3 L'exécution d'un système hybride . . . . . . . . . . . . . . . . . . . . . . 19

1.4 Système hybride linéaire . . . . . . . . . . . . . . . . . . . . . - . . . . . 21

. . . . . . . . . . . . . . . . . . . 1.5 Exemple d'un système hybride linéaire 21

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 Conclusion 24

2 Modélisation d'un système de positionnement d'antennes 25

2.1 Spécification du système . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.2 Modélisation du rotor de l'azimut . . . . . . . . . . . . . . . . . . . . . . 30

2.3 Différentes composantes de l'automate du rotor de l'azimut . . . . . . . . 32

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Conclusion 36

3 Synthèse de contrôleurs des systèmes hybrides linéaires 37

. . . . . . . . . . . . . . . 3.1 Aperçu sur le contrôle des SEDs .. . . . . . . 38

3.1.1 Préliminaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.1.2 Approches et concepts de synthèse de contrôleurs des SEDs . . . . 41

3.2 Présentation de l'outil de vérification HyTech . . . . . . . . . . . . . . . 44

3.2.1 Définitions préliminaires . . . . . . . . . . . . . . . . . . . . . . . 45

3.2.2 Propriété du langage de description ICTL . . . . . . . . . . . . . 48

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Syntaxe .. 48

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.4 Sémantique 50

3.2.5 Systèmes de transition . . . . . . . . . . . . . . . . . . . . . . . . 52

3.2.6 Opérateurs précondition . . . . . . . . . . . . . . . . . . . . . . . 53

3.2.7 Modèle de vérification symbolique . . . . . . . . . . . . . . . . . . 58

3.3 Procédure de synthèse de contrôleurs . . . . . . . . . . . . . . . . . . . . 60

. . . . . . . . . . . . . . . . . . . . . . 3.3.1 Structure d'un contrôleur 60

3.3.2 Adaptation d'une procédure de vérification en une procédure de

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . synthèse 62

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Conclusion 75

4 Synthèse de contrôleur du système de positionnement d'antennes

4.1 Définition des propriétés du procédé . . .

4.2 Application de la procédure de synthèse

4.3 Stratégie de commande

4.4 Conclusion . - . . . . .

Conclusion

Annexe A

Bibliographie

Liste des tableaux

1 Stratégie de commande . . . . . . . . . . . . . . . . . . . . . . . . - . . . 84

Liste des figures

Évolution d'un système à événements discrets dans le temps . . . . . . . 2

Évolution d'un système continu dans le temps . . . . . . . . . . . . . . . 4

Commande en boucle ouverte . . . . . . . . . . . . . . . . . . . . . . . . 5

Commande en boucle fennée . . . . . . . . . . . . . . . . . . . . . . . . . 6

Système de commande hybride . . . . . . . . . . . . . . . . . . . . . . . . 7

Automate hybride d'une pompe . . . . . . . . . . . . . . . . . . . . . . . 13

Évolution de la température d'une chambre . . . . . . . . . . . . . . . . 23

Automate hybride linéaire du thermostat . . . . . . . . . . . . . . . . . . 23

Architecturedusystènie . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Automate du rotor de l'azimut . . . . . . . . . . . . . . . . . . . . . . . . 33

Machine à états . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

Boucleferrrtée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

Ekemple de l'automate hybride du thermostat . . . . . . . . . . . . . . . 46

Ejcemple de régions de dom& . . . . . . . . . . . . . . . . . . . . . . . 46

L'opQateurtime-préconditionprey . . . . . . . . . . . . . . . . . . . . 36

. . . . . . . . . . . . . . . . . . . . . . . . . . . Illustration de l'exemple 58

hemple d'un cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

. . . . . . . . . . . . . . . . . . . . . Concat6nation de deux trajectoires 65

Proc4du.e vérification-cycle . . . . . . . . . . . . . . . . . . . . . . . . . 67

Procédure vérification-propriété . . . . . . . . . . . . . . . . . . . . . . . 68

. . . . . . . . . . . . . . . . . . . . . . . . . . . . Ehcemple de trajectoires 68

. . . . . . . . . . . . . . . . . . . . . Procédure tirne-précondition .. . 70

. . . . . . . . . . . . . . . . . . . . . Procédure transition-précondition 71

. . . . . . . . . . . . . . . . . . . . . . . Procédure synt hèse-contrôleur 73

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Pro&ramme principal 74

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . D&nition d'un cycle 76

. . . . . . . . . . . . . . . . . . . . . . . . . . . Représentation des cycles 81

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cyclei 82

Simulation du comportement du système de positionnement d'antennes . 85

Introduction

Un syst&me hybride est un système dynamique qui présente un comportement à la

fois discret et continu. Les systèmes hybrides trouvent leur application au niveau des sys-

tèmes industriels comme les robots, les sysernes micr&lectroniques et les équipements

médicaux [l].

Les caractéristiques d'un système hybride sont issues de celles de ces parties discrète

et continue.

Un système à événements discrets est un système dynamique qui évolue en fonction

d'occurrences d'événement qui surviennent dans le temps d'une fqon plus ou moins

régulière et plus ou moins connue. La modélisation des systèmes à événements discrets

(SEDs) varie selon leurs domaines d'application et des di£Férentes caractêristiques de leur

comportement.

La figure 1 représente le comportement d'un SED. Dans cette figure, l'abscisse repré-

sente l'évolution du temps, l'ordonnée représente les différents états du système et les seg-

ments représentent les intervalles de temps entre deux occurrences d'évknement. Général-

ement, le système change d'etat à chaque occurrence d'événement.

Ce modèle peut être simplifié si l'on ne considère pas les intervalles de temps entre

les événements (cas du modèle logique), ou si les intervalles de temps étaient réguliers

et connus (cas des équations de récurrence). Dans ce cas, le comportement du système

est représenté par des suites d'événements. Les modéles qui utilisent cette représentation

1 I t 1 1 I 1 I I I I a 1 I

tl t 2 temps

Figure 1: fivolution d'un syst&xne à événements discrets dans le temps

sont des modèles logiques ou récurrents. Il y a d'autres modèles qui tiennent compte du

temps d'occurrence de chaque &&nement. Ces modèles sont des modèles de performance.

Les modèles logiques sont utilisés avec succès pour étudier les propriétés qualitatives

des SEDs, c'est-à-dire l'ordre d'occurrence des événements. Ils peuvent être utilisés pour

étudier les syst&mes suivants : les protocoles de communication, les circuits numériques,

les systèmes distribués et les protocales d'interrogation de base de données.

Le comportement d'un SED modélisé logiquement comme une suite d'événements

peut être représenté selon trois approches différentes : les systèmes de transitions (au-

tomate, réseau de Pet ri, grafcet ), les approches algébriques ( Communicating Sequentiaal

Processes) et les approches logiques (logique des prédicats du premier ordre, logique tem-

porelle) [2]. Dans la suite de notre travail, nous nous intéressons à la modélisation de la

partie discrète sous forme d'un automate.

Un système continu est un système dynamique qui évolue de façon continue dans le

temps. La modélisation des systèmes continus doit répondre aux exigences du domaine

d'application et du cahier des charges. Selon que nous désirons étudier la comrnandabilité,

l'observabilité, l'analyse structurelle ou la su~eillance d'un système, nous op tons pour

un modèle sous la forme d'équations d'état (équations différentielles), de fonctions, de

matrices de transfert, de blocs diagrammes ou de graphes de fluence.

La figure 2 représente le comportement d'un systhme continu du premier ordre soumis

à une entrée en échelon. Dans la suite de notre travail, nous nous intéressons à la

modélisation sous forme d'équations diff'rentielles,

A partir des définitions informelles des systèmes à événements discrets et des systèmes

continus, on introduit le concept des systèmes hybrides. En &et, le comportement d'un

système hybride comprend un comportement discret et un comportement continu. Le

fonctionnement d'un système hybride est une séquence de deux phases : la première

correspond à une transformation continue d'états du système pendant un certain temps

et la deuxième à un changement d'état discret d'une durée de temps nulle [II.

état

@ 1 1 1 t I I

I I I 8 r I I I I

tl t2 t n temps

Figure 2: Évolution d'un syst5me continu dans le temps

Afin qu'un système ou procéàB se comporte d'une manière correcte par rapport à un

ensemble de contraintes imposées sur ce procédé, un contrôleur est nécessaire pour guider

ce dernier.

Nous distinguons deux types de commande : la commande en boucle ouverte et la

co~~ l~~ lande en boucle fermée. La commande en boude ouverte (voir la figure 3) consiste

à envoyer au système une séquence de commandes ou une entrée de consigne (selon la

nature du système) en l'absence de tout retour d'information sur l'évolution de la sortie

(l'ensemble des variables à considérer du systbe) .

Entrée Sortit

Figure 3: Commande en boucle ouverte

Concernant la commande en boucle fermée, oela consiste à concevoir un procédé où

la sortie du système doit être comparée avec l'objectif désiré en entrée. Une rétroaction

de la sortie s u l'entrée est appliquée en utilisant un capteur placé sur les variables

essentielles de sortie, un comparateur entre la sortie souhaitée et la sortie effective ainsi

qu'une commande sur les variables d'action du procédé (voir la figure 4).

Aussi bien pour les systèmes continus que pou. les systèmes discrets, la commande doit

satisfaire un objectif (atteindre une consigne, avoir un comportement désiré : rapidité,

st abilit6 et précision) ou optimiser un crit&re (eiergie consommée, temps d'acécut ion).

La figure 5 représente un système de commande hybride [3]. Ce dernier comprend trois

composantes : un contrôleur, une interface et un pro&dé. La particularité hybride du

cornparateur variables d'action

sorti e + Procé d i

I F

w entrée de consigne : 4 - objectif souhaité

I i

Capteur

Figure 4: Commande en boucle fermée

système tient à ce que la commande de ce dernier est basée sur une boucle de régulation.

Le rSle du contrôleur est de superviser le fonctionnement du procédé, c'est-à-dire de

contraindre son comportement afin de satisfaire les contraintes imposées sur le procédé.

Le contrôleur procède à l'exécution de sa tâche grâce aux variables de contrôle et à une

stratégie de commande pour exécuter une action de contrôle.

Les variables de contrôle contiennent des données qui sont nécessaires pour la prise

de décision du wntraleur. En fonction de chaque prise de décision, le contrôleur met à

jour les variables de positionnement, ce qui a pour effet de produire un événement au

niveau du procédé [4].

Le procédé et le contrôleur ne communiquent pas directement, puisque chacun utilise

un signal de type diffkrent de l'autre. Cependant, une interface est utile pour convertir

l ~ s signaux du procédé en des séquences de symboles et vice versa.

Le contrôleur d'un systi5me hybride peut être un contrôleur autonome intelligent [3].

Dans ce cas, il permet de f&e face considérablement aux changements imprévus et non

entrées sorti es

variables de contrôle variables I<ie positionnement

r I

Figuxe 5: Système de commande hybride

Capteurs Interface Actionneurs

9

modélisés au niveau du procédé, c'est-à-dire, qu'il utilise des processus intelligents de prise

de décision en vue de la génération des actions de commande adéquates au comportement

du procédé. Cependant, cette commande n'est pas forcement optimale (selon des critères

d'énergie ou de temps d'exécution) et n'intervient pas sur les caractéristiques dynamiques

du système (rapidité, stabilité et précision).

Problème

Le probl&me comporte deux volets : d'une part, la représentation de procédés sous

la forme d'un modèle hybride et, d'autre part, la synthèse de contrôleurs,

Le modèle hybride doit tenir compte des caractéristiques de la partie continue ainsi

que celles de la partie discr&te.

Pour la synthèse de contrôleurs, le problème consiste, d'abord, à exprimer des pro-

priétés sur le procédé cornnie étant des contraintes, ensuite, à modifier son comportement

en l'incluant daas une boucle avec le contrôleur et, enfin, à vérifier si les proprié tés désirées

sont satisfkites. Si c'est le cas, alors il existe un contrôIeur permettant de guider ou de

forcer le procédé en respectant les propriétés qui lui sont imposées.

Le contrôle d'un système hybride ne peut s'effectuer en boucle ouverte, car nous avons

besoin à chaque instant du retour d'information. Donc à ce niveau, le problème consiste à

construire ou à dériver un contrôleur qui surveille de fqon continue l'état du changement

du procédé. Ce contrôleur procède, en fonction de sa strathgie de commande, à l'exécution

des actions de commande a h de maintenir le procédé dans des états désirables.

Dans le problème de synthèse, nous sommes tenus de vérifier que le comportement

du procéde satisfait toutes les propriétés. D'une certaine faCon, le problème de synthèse

peut se tranformer en un problème de vérification, puisque, si toutes les propriétés sont

vérifiées, alors un contrôleur peut &re gknér6.

Le modéle hybride doit permettre une analyse facile de l'espace d'états du procédé afin

de vérifier que le comportement de celui-ci respecte les contraintes qui lui sont imposées.

Alors, le problème consiste à adapter le problème de v&rification au probkme de

synthèse. Pour ce faire, nous avons donc besoin d'une méthode de vérification.

Méthodologie

La première extension du modèle de transitions à états discrets (automate) vers

un modèle d e d'un wmportement discret et continu est un automate temporisé. Ces

automates sont analogues aux automates finis, mais ils sont équipés de variables représen-

tées par des horloges. Ces variables évoluent dans le temps de façon linéaire avec une

pente unit aire.

Pour une modélisation g6n6rale des systèmes hybrides, nous utilisons un automate

hybride, c'est-à-dire un automate fini ayant des variables dont les valeurs évoluent d'une

fqon continue à travers le temps [5].

Un système hybride est un système dynamique et son comportement décrit des

changements discrets et continus. Un automate hybride est un modèle mat hématique

pour modéliser un système hybride. Il se présente comme un seul formalisme qui combine

un automate de transitions pour représenter les changements discrets et des équations

différentielles pour représenter les changements continus [6]. Dans ce mémoire, nous

nous intéressons aux automates hybrides linéaires qui constituent une sous-classe des

automates hybrides.

Afin de modéliser un système, nous d o n s procéder à la spécification d'un modèle

selon les étapes suivantes :

définition des différents 6tats possibles du système,

définition des équations d'évolution du système au niveau de chaque ktat ,

0 d6finition des conditions n6cessaires pour les transitions du système d'un 6tat à un

autre.

Ces étapes doivent satisfaire les formalismes imposés par le modèle d'automate hy-

bride. Nicollin et al. [1] et Alur et al. [7] ont déh i des approches d'analyse et de

description des systèmes hybrides. Les méthodes d'analyse sont principalement basées

sur des transformateurs de prédicats pour le calcul des prédécesseurs et des successeurs

d'un ensemble d'gtats donné.

Le problème de synthèse revient d'abord à s'assurer que le procédé vérifie certaines

propriétés qui lui sont imposées, ensuite, si toutes les propriktés sont satisfaites alors un

contraleur est ghéré. En fait, nous procédons de la manière suivante pour la génération

d'un contrôleur :

exprimer des propriétés sur le procédé,

vérifier si toutes les propriétés sont satisfaites par le procédé,

générer le contrôleur correspondant.

Dans ce mémoire, nous d o n s utiliser la procédure de calcul d'un outil nommé HyTech

[8]. Ce dernier est un outil de vérification automatique et symbolique des systèmes em-

barqués. I1 permet de vérifier si un système, modélisé sous forme d'un automate hybride

linéaire, verifie certaines propriétés. Ces dernières sont exprimées en logique temporelle

par le langage de spécScation Inkgrator Cornputution %. Logic. Un contrôleur existe

si toutes les propriétés sont satisfaites.

Résultats

Nous avons adopté le modèle d'un automate hybride linéaire [6] comme étant un

mod5le mathématique adéquat pour la modélisation d'un système hybride linéaire. Ce

modèle impose des contraintes de linéarité sur la partie discr&te et la partie continue.

Une procédure de synthèse de contr61ews a été développée. Cette procédure revient

A adapter la procêdure de vérification présentée par HyTech [8] au problème de synthèse.

Elle consiste à générer un contrôleur à partir d'un automate hybride, modélisant un

procédé, et des contraintes, imposées sur ce dernier. Les contraintes sont acprimées

en terme de propriétés d'accessibiité. Si toutes les propriétés sont satisfaites par le

procédé, alors il existe un contrôleur qui force le procédé à agir correctement en présence

d'kvénements contraiables.

Organisation du mémoire

Dans le chapitre 1, nous présentons une methode de modélisation des systemes hy-

brides linéaires. Au niveau du chapitre 2, nous appliquons la procédure de modélisation

de f i e dans le chapitre 1 pour modéliser un système de positionnement d'antennes sous

la forme d'un système hybride linéaire. Le chapitre 3 présente les principaux concepts

propres aux langages formels ainsi qu'un aperçu générzl sur le contrdle des SEDs. Nous

présentons aussi l'outil de vériûcation HyTech et une procédure de synthèse de con-

tr6leurs. Le chapitre 4 présente l'application de la procédure de synthèse d'une manière

globale au système de positionnement d'antennes (le détail du calcul est présenté en an-

nexe A). Enfin, nous concluons le mémoire avec les résultats et les critiques de ce travail

de même que des remarques sur les travaux futurs.

Chapitre 1

Modélisation des systèmes hybrides

Dans ce chapitre, nous nous intéressons à la modélisation des systèmes hybrides. Un

syst&ne hybride est un système dynamique ayant un comportement discret et continu.

Nous d o n s adopter la méthode de modeisation proposée par Henzinger [6] et Henzinger

et al. [4] qui consiste à représenter un système hybride sous forme d'un automate hybride.

Un automate hybride est un objet mathématique qui permet à la fois la modélisation de

la partie discste et la partie wntinue d'un système hybride (ou mixte). Les systèmes à

modéliser sont des syst4mes linéaires que nous représentons par des automates hybrides

linéaires. Ces derniers constituent une sous-classe des automates hybrides ; ils imposent

des contraintes de linéarité aussi bien sur la partie discr&te que sur la partie continue.

1.1 Un automate hybride

Nous définissons un automate hybride pour modéliser un système mixte. InformeUe-

ment, un automate hybride consiste en un ensemble fini X de variables et un multigraphe

(V, E) . Les a n s E représentent les transitions discrètes qui comportent des conditions

d'affectation (garded assignments) sur X. Les sommets de V décrivent l'évolution con-

tinue du système sous des contraintes dynamiques. L'état de l'automate change soit

instantankment à travers une transition discr&te ou selon le temps écoulé en fonction de

I'évolut ion continue.

Nous utilisons l'exemple d'un automate hybride d'une pompe [4] (voir la figure 6)

pour illustrer la définit ion formelle d'un automate hybride.

La pompe est un mécanisme utilisé pour vider l'eau d'un réservoir. Elle ne passe

à l'état actif qu'aprb l'expiration d'une période de temps égale à cinq secondes, d'où

- l'introduction d'un &at intermédiaire pour décrire le passage de la pompe de l'état d'arrêt

à l'état actif,

Figure 6: Automate hybride d'une pompe

1.1.1 Définition d'un automate hybride

Soit un ensemble fini X de variables. Un prédicat sur X est une combinaison

booléenne d'inegaiités en fonction des variables de l'ensemble X. Un automate hybride

A est composé des éléments suivants :

a Variables

Les variables sont définies à l'aide d'un vecteur X = (xi, ..., xn) de variables réelles et

d'un vecteur Y = (yl, . . . , yk) de variables commandables tel que Y C X. Une évaluation

de X est définie par un vecteur a = (al, ..., a,,) de l'espace vectoriel réel tRn qui associe à

chaque variable xi f X une d e n réelle ai E 8.

Exemple : l'automate hybride de la pompe possède deux variables commandables P

et c qui représentent respectivement le volume pompé et le temps écoulé.

Modes de commande (wntml modes)

Un ensemble fini V contient des sommets qui sont appelés modes de commande.

L'automate hybride de la pompe présente trois modes de commande, on, 08 et going-on

utilisés pour modéliser la pompe à l'état actif, à l'état d'arrêt et à l'état intermédiaire.

a Conditions d'invariance

Une fonction Inv affecte à chaque mode de commande v de l'ensemble V une condi-

tion d'invariance Inv(v) définie par un prédicat sur X. Un état (v, a) est admissible si

Inv(v) [X = a] est vrui. Le contrôle d'automate hybride réside au niveau d'un mode de

commande v si et seulement si la condition d'invariance Inv(v) est satisfaite. Ainsi, la

condition d'invariance peut être utilisee afin de forcer la progression.

Ekemple : au niveau de l'automate hybride de la pompe, la condition d'invariance

c 5 5 du mode de commande going-on assure que le contrôle de l'automate doit quitter

ce mode de commande une fois que la valeur de l'horloge c a atteint la valeur 5.

Conditions de flux

Une fonction Flow affecte à chaque mode de commande u E V une condition de flux

Flow (v) définie par un prédicat sur l'ensemble de -ables x ux tel que x = (xi, . . . , &).

Chaque variable x i représente la d&%e premiére par rapport au temps de la variable xi

(xi = dxi/dt) . Tant que le contrôle d'un automate hybride réside au niveau d'un mode

de commande v , les valeurs des variables changent selon des trajectoires différentielles

dont les dérivées premières satisfont les conditions de flux Formellement, pour chaque

réel b 2 O, nous définissons la relation de flux binaire v6 sur des états admissibles tels

que pour q = (v, a ) et q' = (vf , a'), nous avons (v, a ) -' (VI, a') si d = v et il existe une

fonction différentielle (o : [O, 61 - En telle que :

1. les points extrânes de la fonction (o sont rp(0) = a et 4 6 ) = a' ;

2. pour tout réel t E [O, 61, la condition d ' indance Inv(v) [X = <p (t )] est vraie ;

3. pour tout réel t E [O, 61, la condition de flux Flow(v)[X, x = p(t), +(t)] est vraie

avec +(t) = (dp,(t)/dt, ..., dp,(t)/dt).

Le couple (q, qf ) est un flux et qf est appelé flux successeur de q.

Concemant l'exemple de l'automate hybride de la pompe, la condition de flux P =

O A k = 1 au niveau du mode de commande gozng-on assure que le volume de pompage

est inchangeable (puisque le débit P = O) et que l'horloge c mesure la dur& du temps

ému& (puisque l'évolution de l'horloge exprimée par 6 est constante unitaire).

0 Condit ions initiales

Une fonction h i t affecte à chaque mode de commande u E V une condition initiale

Init(v) définie par un prédicat sur X. Le contrale d'un automate hybride doit commencer

à partir d'un mode de commande v tel que Init (v) A 1m (v) est vrai. Un état (v , a) est

initial s'il est admissible et Init(v)[X = a] est vîaz Dans la représentation graphique

d'un automate hybride, nous omettons les conditions initiales de la forme faux

Ekemple : au niveau de l'automate hybride de la pompe, la condition initiale du mode

de commande off est vraie et les conditions initiales des autres modes de commande sont

fausses.

0 Commutations de commande (contml suritches)

Soit E est un ensemble fini d'arcs. Chaque élément de E est appelé commutation de

commande. Une commutation de commande (v, v') consiste en un mode de commande

source v E V et un mode de commande cible v' E V. Il existe des commutations de

commande en boucle (stutter) telles que (v' = v).

Ekemple : l'automate hybride de la pompe possède trois commutations de commande

(ofigoing-on), (going-on, on) et (on, off).

Conditions de saut ( jump condition)

Une fonction Jump affecte à chaque commutation de commande e E E -me condition

de saut Jump(e), représentée par un pr6dicat sur les variables de l'ensemble X U Y', où

Y = ( . . , ) Dans cette expression, yi représente la valeur relative à une variable

commandable avant la commutation de commande et ?/i représente sa valeur après la

commutation de commande. Seules les variables commandables sont mises à jour par

les commutations de commande. Formellement, pour une commutation de commande

e = (v, v'), nous définissons une relation de saut binaire -e sur des états admissibles

tel que pour q = (v, a) et q' = (vl, a'), nous avons (v, a) -+e (d, a') si et seulement si :

1. la condition de saut Jurn?(e) [X, Y' = a, a' [Y]] est vraie, où a' [Y] dbo te la restric-

tion de a' aux variables de Y ;

2. pour toutes les variables non commandables xi ci X\Y, ai = q.

Le couple (q, q') est un saut et q' est appelé état successeur de q.

Une commutation de commande e E E est permise au niveau d'une évaluation a s'il

existe un état (v', a') tel que (v, a) -e (v', a').

Nous utilisons la condition d'dectation (guards) 4 -, a pour l'écriture d'une condi-

tion de saut telle que q5 est un prédicat convexe sur X et a est un ensemble d'affectations

qui consiste à définir les nouvelles valeurs des variables yi une fois que le prédicat q5 est

Mai. Une commutation de commande e E E est permise à une évaluation a si &[X = a]

est m-.

Au niveau de la représentation graphique d'un automate hybride, les conditions de la

forme mai et les affectations identité sont omises.

Ekemple : au niveau de l'automate de la pompe, la commutation de commande à

partir de going-on à on possède la condition de saut c = 5 A P' = P A c' = c.

Soit un ensemble fini C d'évknements. Une fonction Event affecte à chaque commu-

tation de commande e E E un événement de l'ensemble C.

Ejcemple : dans l'automate hybride de la pompe, event(ofl going-on) = p -on.

1.2 Système de transitions

Le comportement d'un système hybride est défini par un système de traasitions

étiquetk S comportant les composantes suivantes :

- un espace d'état, c'est-à-dire un ensemble Q d'états et un sousensemble Qo E Q

des états initiaux ;

- une relation de transition, c'est-à-dire une relation binaire sur l'espace d'états Q

définie à partir d'un ensemble B d'étiquettes ; pour chaque étiquette ar E B, le

triplet q -" q' est appelé t r d t i o n .

Pour un système hybride, nous asocions un système de transitions étiquetées en

fonction de deux types d'étiquettes :

1. des actions qui déterminent les noms des transitions discrètes,

2. des nombres réels positifk qui représentent le temps écoulé.

Un systéme de transitions ktiquetées d'un système hybride A est oomposé des éléments

Q, Qo, B et qui sont définis par :

- Q> Qo V x Rn tel que (v, a) E Q si et seulement si le prédicat Inv(v)[X = a]

est vrai et (u, a) E Qo si et seulement si Init(u)[X = a] et Inv(v)[X = a] sont

satisfaits. L'ensemble Q est appelé espace d'états de A et les sous-ensembles de Q

sont appelés régions de A-

- Pour chaque événement o E C , (u, a) -tu (v', a') est défini si et seulement s'il

&te une commutation de wmmande e E E telle que :

1. la source de e est v et la cible de e est v',

2. le prédicat Jump(e) [X , Y' = a, a' [Y]] est vrai,

3. Evat (e ) = o.

- Pour chaque réel positif 6 E WR+, (v, a) -4 (v' , a') est d&ni si et seulement si

v = v' et il existe une fonction diffhntielle <p : [O, 61 --t 91" et sa dérivée première

p' : [O, 61 + Rn telles que :

1. <p(O) = a et (o(6) = a',

2. pour chaque réel E E [O, 61, la condition de flux ~ l a u (u) [x, X = @ (E)] et

la condition d'invariance Inv (v) [X = p ( ~ ) ] sont satisfaites. La fonction p est

appelée Witness flow.

Un sous-ensemble R C Q de l'espace d'états est appelé région. Soit une région R et

une étiquette a E B. La région a-successeurs de R est l'ensemble des états directement

accessibles à partir des états de R et de transit ions étiquetées a. Cet ensemble est défini

par post,(R) = {q' 1 3q E R, q q') ; la région a-préd&esseurs de R est L'ensemble

des états de R à partir desquels des états sont directement accessibles par des transitions

étiquetées a. Cet ensemble est défini par pre,(R) = { q 1 3q E R, q q').

1.3 L'exécution d'un système hybride

A chaque instant, l'état d'un s y s t h e hybride est défini par un mode de commande

et les valeurs de toutes les variables. Lëtat d'un système hybride peut changer selon

deux maniGres :

1. par une étape de saut (jump step), c'est-à-dire par une transition discrète et instan-

tanée qui entraine un changement au niveau du mode de commande et les valeurs

des variables selon la relation de transition ;

2. par une étape de flux (jlow step), c'est-à-dire par I'évolution du système continu en

fonction du temps qui entraîne seulement un changement au niveau des variables

selon la fonction uritness ftow du mode de commande courant.

L'exécution d'un système hybride est une séquence finie ou infinie d'étapes [9]. Chaque

étape présente deux phases : la première est la phase de progression du temps et la

deuxième est une transition discrète. En effet, l'exécution est une séquence d'états :

telle que pour chaque i > 0 ,

- (ui , ai) -6 (vil ai) (vi+i, ai+i) OU

- (ui , %) --+Oi (w, ai+1)

La trajectoire d'un automate hybride A est une séquence finie qo, QI, 42, --, Q* d'états

admissibles telle que :

1- le premier état qo de la séquence est un état initial de A,

2. chaque couple (G, qitl) d'états consécutifs de A représente soit un saut de A ou un

flux de A.

Un état q' est accessible à partir de q si et seulement s'il existe une trajectoire finie à

partir de q jusqu'à q'.

Soit une trajectoire r d'un système hybride A telle que r : (vo ,~) (v i , ai)--.(vk, ak).

Une position de la trajectoire T est définie par le couple ( i , ~ ) qui comprend un entier

positif i et un réel positif E 5 bi (bi représente la +ode de temps permise dans le mode

de commande vi). Les positions de T sont ordonnées lexicographiquement de façon telle

qu'une position (i, 6) précède une position ( j , E ) , noté (i, 6) < (j, e) , si et seulement si

(i < j ) ou (i = j ) et (6 < E). L'état de A à une position (i, s) de la trajectoire T est

défini par T(~,E) = (viy<pi(€)) [SI.

La valeur du temps écoulé depuis la position initiale n = (0,O) à la position K = (i, E )

de T est calcul& par la somme h i e t,(i, e) = 6j) fe. La durée d'une trajectoire T

est calculée par la somme infinie 6, = Xj2 , bj. La trajectoire T diverge si 6, = m. Nous

notons par I' l'ensemble des trajectoires de A et par l?" C r l'ensemble des trajectoires

divergentes de A,

Un automate hybride linéaire est nonzeno, si pour chaque état admissible p de A

il existe une trajectoire divergente T telle que ~ ( 0 ~ 0 ) = q. En d'autres termes, A est

nonzeno si et seulement si chaque préfixe fini d'une trajectoire est un préfixe d'une

trajectoire divergente. Dans ce mémoire, nous nous intéressons aux automates hybrides

linéaires nonzeno.

1.4 Système hybride linéaire

Les automates hybrides linéaires sont une sous-classe des automates hybrides dans

lesquels Ia dynamique des variables continues est définie par des inégalités difftkentielles

linéaires de la forme Ak - c, où x est le vecteur des dérivées premières des variables x,

A est une matrice d'état constante, c est un vecteur constant et NE (<, 2, =, 3, >}.

Un terme linéaire est une combinaison linéaire de variables affectées de co&cients

rationnels de la forme h; + Klxl + ... + Kmxm. Un prédicat linéaire convexe est une

conjonction d'inégalité entre des termes linéaires.

Un automate hybride A est linéaire si les deux conditions suivantes sont satisfaites

[SI -

1. Linéarité : pour chaque mode de commande v E V, la condition de flux Flozu(v),

la condition d'invarimce Inv(v) et la condition initiale Init(v) sont des prédicats

linéaires convexes. Pour chaque commutation de commande e E E, la condition de

saut Jump(e) est un prédicat linéaire convexe.

2. Indépendance de flux : pour chaque mode de commande v E V, la condition de flux

Flm(u) est un prédicat impliquant uniquement les variables de x et ne contient

aucune variable de X. Par exemple, on ne tolère pas des conditions de flux de la

forme x = x. Par contre, nous pouvons rencontrer des conditions de la forme x = 1

oii x E [l - E , 1 + E] POUT une certaine valeur de E.

1.5 Exemple d'un syst&me hybride linéaire

Dans cette section, nous d o n s procéder à La modélisation d'un thermostat [7] sous

la forme d'un automate hybride lin6aire.

Le rôle du thermostat est de contr61er la température d'une chambre, cela revient à

tester instantanément la valeur de la température et à mettre le radiateur à l'état on ou

OB Le thermostat doit maintenir la température x d'une chambre entre les deux valeurs

m et M, décrivant respectivement la température minimale et la température maximale.

L'exécution de ce système est une séquence d'étapes déterminées par les changements

alternat& d'états du radiateur de l'état on à I'état 08 et inversement. fiventuellement,

une transition se produit si une des conditions x = m ou x = M est satisfaite.

Entre deux transitions successives, la valeur de la température change en fonction des

règles dëvolut ions (équations différentielles) qui dépendent de l'kt at courant (l'et at o n

ou 08 du radiateur).

La figure 7 iflustre l'évohtion du système comme une alternance des étapes on et

OB Chacune de ces étapes est composée d'une transformation continue d'états suivie

d'une transition discrète. Dans un souci de respect de la linéarité du système hybride,

nous avons remplacé l'évolution exponentielle de la température par une interpolation

du premier degré.

Si le radiateur est à l'état on, la température évolue dans le temps jusqu'à atteindre

la valeur maximale. Au passage à l'état on, la température baisse dans le temps jusqu'à

atteindre la valeur minimale.

La figure 8 présente l'automate hybride correspondant au comportement du thenno-

stat.

Les clifErentes composantes de l'automate hybride linéaire du thermostat sont les

suivantes.

Variables : c'est L'ensemble X = {x) tel que x représente la température.

0 Modes de commande : c'est l'ensemble V = {on,ofl), les éléments de V

représentent respectivement l'état actif et l'état d'met.

0 Conditions de flux : les deux conditions de flux x = 2 et x = -1 sont associées

respectivement aux modes de commande o n et OB, ainsi que les fonctions clifferen-

tielles (o, et cps telles que <p,(t) = x + kt (avec 3: = m et x = 2) et v2(t) = x + 8

Temps

Figure 7: Évolution de la température d'une chambre

Figure 8: Automate hybride linéaire du thermostat

(avec x = M et x = -1).

Conditions d'invariance : Ies deux invariants x 5 M et x > m, représentent

respectivement les conditions d'invariance des modes de commande on et off.

Conditions initiales : le prédicat x = m est la condition initiale du mode de

commande on et faux représente celle du mode de commande off:

a Commutations de commande : c'est l'ensemble E = { (on ,o f l ) , (os,on)} qui

définit les diff&entes transitions discrètes possibles.

Conditions de saut : pour chaque commutation de commande, une condition

de saut est définie ; les prédicats x = M A I = x et x = m II 2 = x (tel que

d représente la valeur de x après k transition) représentent respectivement les

conditions de saut des commutations de commande (on ,o f l ) et (o f f , on).

fiv6nements : à chaque commutation de commande est &té un événement,

tum-on pour (off ,on) et tum-O ff pour ( o n , off).

1.6 Conclusion

Un automate hybride est un modde mathématique adéquat pour la modélisation

d'un système hybride. Ce modèle est doté d'un système de transitions permettant la

représentation des transitions discrètes et continues qui définissent le comportement du

système. Un automate hybride linéaire est une sous-classe des automates hybrides, il

impose des contraintes de linéarité sur la partie discr&te et la partie continue.

Dans le chapitre suivant, nous retenons le modèle d'un automate hybride linéaire pour

la représentation d'un système de positionnement d'antennes.

Chapitre 2

Modélisation d'un système de

positionnement d'antennes

Nous consacrons œ chapitre à la modélisation d'un système de poçitionnernent

d'antennes qui a été tiré de [IO] et qui a fait l'objet d'un cas d'étude de synthèse de

contralerus des systèmes à divénements discrets. Nous allons appliquer la procédure de

modélisation définie dans le chapitre 1 pour modéliser ce procédé sous la forme d'un sys-

tème hybride linéaire, tout en respectant les contraintes de linéarité imposées au niveau

de la partie discrZite (transition discrète du système) et au niveau de la partie continue

(évolution wnt hue de système).

D'abord nous allons commencer par la spkification du système de positionnement

d'antennes et ensuite nous d o n s procéder à sa modélisation sous la forme d'un automate

hybride linéaire.

Spécification du système

Le procéd6 à modéliser est une version simplifiée d'un système de contrale de rotors

d'antennes (SCRA) utilisé dans un laboratoire pour faire des expériences avec des satel-

lites mobiles de télécommunication (voir la figure 9). Le SCRA est responsable de mettre

à jour l'orientation des antennes dans la direction d'un satellite de téléwmmunicat ion.

Il comprend deux composantes principales :

1. un contrôleur de rotors pour l'azimut et l'élévation ( C M ) pour la su rvebce de

deux rotors qui activent le mouvement des antennes (partie physique),

2. un contrôleur de direction des antennes (CDA) qui active ou arrête le fonction-

nement des rotors pour orienter les antennes vers une direction donnée (partie

logique).

Dans ce syst&me, la direction des antennes est exprimée en terme d'azimut et d'éléva-

tion. Ces deux paramètres sont en degrés et leurs valeurs varient entre -180° et 180°. Le

CDA comprend trois modules : un contrôleur d'azimut (CA), m contrôleur d'élévation

(CE) et une interface qui lie la partie physique du système avec la partie logique.

L'interface est définie par des processus de captage et de commande pour le rotor de

l'azimut et le rotor de l'elévation. Elle extrait les informations concernant la position

des antennes relative à l'azimut cible et l'&vation cible et les envoie respectivement au

contrôleur d'azimut et au contrôleur d'élévation.

Le contrôleur d'azimut et le contraleur d'élévation sont responsables du fonction-

nement et de l'arrêt des moteurs des rotors dans une direction donnée. Les rotors sont

présentés comme des systèmes physiques continus. Dans ce chapitre, nous nous sommes

intéressés à étudier seulement le comportement de l'azimut, car l'étude du comportement

de l'él6vation suit exactement la même démarche d'analyse.

Figure 9: Architecture du système

Le CDA manipule deux variables de commande : curent et target, qui présentent

respectivement la position courante et la position cible des antennes. Les antennes sont

considérées à la position cible si la distance entre current et target est inférieure ou égale

à d. Dans notre étude, nous allons restreindre d à d / 2 aiin de nous assurer que la position

cible des antennes est dans un intervalle de tolérance acceptable [target-d/2, target+d/2]

et d'éliminer le cas où la distance entre cumnt et target est égale strictement à d. Des

hypothèses seront prises en considération telles que :

- la vitesse angulaire du satellite est inférieure à la vitesse de rotation des rotors de

telle sorte qu'après l'arrêt des rotors, les antennes seront dirigées vers la position

cible ;

- une fois que les antennes sont à la position cible, la nouvelle position sera extraite

après l'expiration d'une période de temps donnée (15 secondes).

Le changement continu de la valeur de la position courante de l'azimut représente

l'évolution continue du système dans le temps. La valeur de la position courante évolue

d'une façon continue jusqu'à atteindre la valeur de la position cible. Une fois que la

nouvelle valeur de la position cible est extraite, le système passe à un état d'arrêt. Après

l'expiration d'une période de temps de 2 secondes, le comportement du rotor de l'azimut

est décrit par les règles suivantes :

- Si la distance algébrique entre la position cible et la position courante (target -

current) est supérieure à d/2, alors le rotor de l'azimut passe de l'état d'arrêt à

un état de fonctionnement qui entraine un mouvement vers la gauche. Ce dernier

accroît la valeur de l'azimut. Le moteur reste actif jusqu'à œ que la distance entre

la position cible et la position courante soit inférieure ou égale à d / 2 . La valeur

de l'azimut évolue selon une fonction différentielle dont le coefficient d'évolution

est exprim6 à raison de deux degrés par seconde (mouvement uniforme de rotation

à vitesse constante). Une fois la position cible atteinte, k valeur de la position

courante est mise à jour par la valeur de la nouvelle position et le rotor de l'azimut

passe à l'état d'arrêt.

- Si la distance algébrique entre la position cible et la position courante (target -

clsrrent) est inférieure à - (d/2), alors le rotor de l'azimut passe de l'état d'arrêt à

un état de fonctionnement qui entraine un mouvement vers la droite. Ce dernier

diminue la valeur de l'azimut- Le moteur du rotor reste actif jusqu'à ce que la

distance entre la position cible et la position courante soit supérieure ou égale à

- (d/2) . La valeur de l'azimut diminue suivant un gradient négatif. Ce dernier est

é d u 6 à une rotation de deux degrés par seconde. La valeur courante de l'azimut

diminue jusqu'à atteindre la nouvelle valeur de la position cible. Une fois la position

cible atteinte, la valeur de la position courante est mise à jour et le rotor de l'azimut

passe à l'état d'arrêt.

- Si la valeur de la position cible est égale à la valeur de la position courante, alors

le système passe à un état de bonne position et attend l'expiration d'une période

de temps de 2 secondes pour qu'il revienne à l'état d'arrêt. Cette durée se base

sur la dynamique du satellite et des antennes. En effet, si la valeur de la position

courante se trouve dans l'intervalle [target - d/2 , target + d/2], alors nous sommes

certains que la position des antennes reste dans l'intervalle [target - d, target + d]

au moins pour 2 secondes encore.

- Aprh l'extraction de la nouvelle valeur de la position cible, le système attend

l'écoulement d'une période de temps de 2 secondes (ce qui exprime l'évolution

continue du système au niveau de l'état concerné) et passe de l'état d ' d t à un

état approprié en fonction de la valeur de la position cible et de la valeur de la

position courante, ensuite il revient à l'état d'met. A œ niveau, le système attend

l'expiration d'une période de temps de 2 secondes et passe à un état inconnu (c'est-

à-dire la nouvelle position exacte des antennes est inconnue) pour qu'il procède à

l'artraction de la nouvelle position cible après l'expiration d'une période de temps

de 15 secondes. Après l'extraction de la nouvelle position cible, le rotor peut être

activé afin d'orienter les antennes vers la position adéquate.

2.2 Modélisation du rotor de l'azimut

Le rotor de l'azimut présente cinq modes : unknown, idle, mouing-lefi, mouing-right

et good-position. La figure 10 présente l'automate hybride correspondant au rotor de

l'azimut. Nous d o n s commencer par la définition des variables impliquées au niveau de

l'au tomate :

- XI représente la valeur de la position courante de l'azimut,

- xz représente la videur de la position cible de l'azimut,

- 2 3 représente la valeur d'une horloge,

- xq représente une variable booléenne.

Au démarrage, le systGme se met dans le mode unknown. La valeur courante de

l'azimut commence à partir de la position O", la valeur de l'azimut cible est inconnue (par

défaut nous lui atfectons la valeur zéro) et les valeurs de toutes les autres variables sont

à zéro. Aprh l'expiration d'une période de temps égale à 15 secondes, le systéme passe

au mode idle en fonction d'un événement appelé new-position. La transition discrète du

mode u h o u n z au mode idle est exécutée une fois que la condition xs = 15 est vérifiée

c'est-à-dire après l'écoulement d'une période de temps de 15 secondes ; cette condition

produit l'affectation de la nouvelle valeur de la position cible à x2 et la mise à zéro de la

valeur de l'horloge x3. Le système ne passe jamais du mode idle au mode unknom sans

avoir passé soit par le mode rnoving-left ou par le mode mozring-nght ou par le mode

good-position. En effet, c'est à ce niveau qu'intdent le rôle de ki variable booléenne x4.

Après le passage du système par l'un de ces trois modes, la valeur de la variable booléenne

2 4 est mise à 1 et la valeur de l'horloge x3 est mise à O. A œ niveau, le système attend

l'expiration d'une période de temps de 2 secondes (x3 = 2) et passe au mode unknown

pour l'extraction d'une nouvelle valeur 2 2 de la position cible de l'azimut.

Après l'extraction de la nouvelle valeur de la position cible et le passage du système

au mode Zdle, le choix d'une transition 'après l'expiration d'une période de temps de 2

secondes est fait comme suit :

- si la condition x2 - x1 > d/2 est vérifiée alors le sens de rotation du rotor est activé

vers la gauche en fonction de l'événement start-moving-Zefi ;

- si la condition 22 - XI < - (d /2 ) est vérifiée alors le sens de rotation du rotor est

activé vers la droite en fonction de l'événement start-rnoving-right ;

- si la condition - (d/2) 5 x2 - XI 5 d / 2 est v&S& alors le syst&me passe au mode

good-position en fonction de l'événement set-good-position.

Dans le mode moving-left, la d e u r courante de l'azimut augmente dans le temps à

raison de deux degrés par seconde jusqu'à ce que la wndition x2 - XI 2 d / 2 n'est plus

vérifiée. Une transition discrète est déclenchée à partir du mode moving-left vers le mode

idle en fonction d'un événement appelé stop d&s que la condition xz-XI 5 d / 2 est vérifiée,

c'est-à-dire que la position cible est atteinte. Cette transit ion engendre l'affectation de

la valeur 1 à la variable boolêenne x4.

Dans le mode moving-right, la valeur courante de l'azimut diminue dans le temps à

raison de deux degrés par seconde jusqu'à ce que la condition xz - xl 5 - ( d / 2 ) n'est

plus vQifiée. Une transition discrète est déclenchée à partir du mode moving-right vers

le mode idle en fonction d'un événement appelé stop dès que la condition xz - sl 2 d / 2

est v6rifiée. Cette transition engendre l'af3ctation de la valeur 1 à la variable booléenne

x4 - Dans le mode good-position la position courante de l'azimut est dans la bonne position.

Le système attend l 'qiration d'une péride de temps de 2 secondes et passe au mode

i d e en fonction d'un événement appelé set-neu-position dès que la condition 23 = 2 est

vérifiée.

Une fois que le système revient au mode idle à partir du mode mouing-right ou du

mode moving-lefi ou du mode good-posz'tiœn et après l'expiration d'une période de temps

de 2 secondes, il passe au mode unk.nown en fonction d'un événement appelé set-wknown

d& que la valeur de la variable booléenne x4 est égale à 1 et que la valeur de l'horloge

2 3 est égale à 2, ce qui produit la mise à zéro de 23 et x4.

2.3 Différentes composantes de l'automate du rotor

de l'azimut

L'automate hybride linéaire (voir la figure 10) modélisant le rotor de l'azimut est

défini par les éléments suivants.

Variables : c'est l'ensemble X = {ln, x2, x3, x4} tel que les éléments de X représen-

tent respectivement la valeur courante de l'azimut, la valeur cible de l'azimut, la

valeur d'une horloge et un indicateur booken.

Modes de cmmmande : c'est l'ensemble V = { unknown, idle, moving-lefi, moving-

right,good-position) dont les éléments représentent respectivement l'état inconnu où

la nouvelle Vitleur cible de l'azimut es t inconnu, l'état d'met du rotor de l'azimut,

l'état de rotation des antennes vers la gauche, l'état de rotation des antennes vers

la droite et l'état de bonne position aKi la position courante de l'azimut est dans la

bonne position.

Figure 10: Automate du rotor de l'azimut

Conditions d'invariance : à chaque mode de commande est affectée une condi-

t ion d'invariance.

a Conditions de flux :

- Au mode de commande unknourn, nous affectons la condition de flux x = 1.

Le ternie x3 = 1 représente le coefficient d'évolution de l'horloge dans le temps

dont la trajectoire vl est telle que <pl(t) = x3 + t -

- Au mode de commande idle, nous affectons la condition de flux x3 = l A x l = 0.

Le ternie xl = O signifie que le moteur du rotor de l'azimut est inactif et le

terme x3 = 1 représente le coefficient d'évolution de l'horloge dans le temps.

- Au mode de commande rnoving-lefi nous afEectons la condition de flux Il = 2.

Le terme x1 = 2 signifie que le rotor est actX La fonction d'évolution de x1

est représentée par la trajectoire ~p, telle que %(t) = XI+ 2t-

- Au mode de commande mouing-right, nous affectons la condition de flux x1 =

- 2. Le terme x1 = -2 signifie que le rotor est actif. La fonction d'évolution

de xi est décrite par une trajectoire décroissante dont la fonction d'évolution

< ~ î est telle que %(t) = xl - 2t.

- Au mode de commande good-position, nous affectons la condition de flux k3 =

1 ce qui représente le coefficient d'évolution de l'horloge dans le temps.

Conditions initiales : au mode de commande unhown , nous affectons la condi-

tion initiale xl = O r\ 2 2 = O A x3 = O A x 4 = O et aux autres modes de commande

nous affectons la condition faux.

Cornmut at ions de commande : c'est l'ensemble E = {e l , e2, e3, e4, es, es, e7, ee )

tel que el = (unknown, idle) , e2 = (idle, unknown) , e3 = (idle, moving-le f t ) ,

e4 = (idle, moving-right), e5 = (idle, goai-posi t ia) , e6 = (moving-lef t , idle) , e7 =

(moving-right, id le) et ee = (good-position, id le ) ) définissent les dinérentes transi-

t ions discrètes possibles.

Conditions de saut : une condition de saut est définie pour chaque commutation

de commande.

- (unknown, idle)

~ 3 = 1 5 A ~ ; E [ 0 , 1 8 0 ] ~ 4 = O A X ; = x 1 A x ~ = x 4

- (idZe,unknown)

X ~ = I A X ~ = ~ A X ~ = O A ~ ~ = O A ~ ~ = X ~ A X ~ = Z ~

x 3 = 2 A x 2 - x 1 < - ~ / ~ A ~ J ~ = O A X ~ = X ~ A X ~ = X ~ A X ~ = X ~

- (id le, g ood-position)

x3 = ~ A x ~ - x ~ S ~ / ~ A X ~ - X ~ 2 -d/2Ad3 = O A X ~ = X ~ A X ; =x2cs>A4 = x4

- (mouing-left, idle)

X Z - X I ~ ~ / Z A X ' , = ~ A ~ ~ = O A X ~ = X ~ A X ~ = X ~

- ( moving-eght, idle)

X Z - X ~ ~ - ~ / ~ A ~ ~ = ~ A x ~ = O A X ~ = X ~ A X ~ = X ~

Évhements : à chaque commutation de commande, nous affectons un événement

approprié tel que :

- Event (unknown,idle) = new-position,

- Event (idle, rnoving-left ) = s tart-rnoving-left,

- Euent ( i de , momng-right) = s turt-moving-right,

- Event (idle,good-position) = s et-good-position,

- Event (idle, unknown) = set-unhoun,

- Event (mouing-Eeft,idle) = stop,

- Euent (rnouing-right,idle) = stop,

- Event (good-position, idle) = s et-new-position.

2.4 Conclusion

Dans ce chapitre, nous avons appliqué la méthodologie de modélisation sous forme

d'un automate hybride 1inéa.i.e au système de positionnement d'antennes. Ce modèle sera

exploité comme exemple d'application par une procédure de dérivation de contr8leur dans

le chapitre 4.

Chapitre 3

Synthèse de contrôleurs des

systèmes hybrides linéaires

Dans ce chapitre, nous nous intéressons à une procédure de calcul permettant la

synthèse de contrôleurs des systèmes hybrides linéaires. Dans le contexte de la théorie

de contrale, les problèmes de contrale consistent à déterminer une machine d'états effi-

cace qui contrôle et commande un procédé à travers des connexions permettant l'échange

d'information. Cette machine doit garantir que le comportement du procédé satisfait des

propriétés spécifiques à un comportement désiré. Un contrôleur observe d'une façon con-

tinue l'état d'un procédé ; il exécute alors une action de commande (transition discr&te)

ou il permet l'écoulement d'une pQiode de temps (évolution continue). Le procédé peut

exécuter une action de commande incontr6lable ou choisir une condition de flm [Il].

Plusieurs travaux ont été effectués concernant œ sujet. Maler et al. [12], Asarin

et al. [13] et Asarin et al [14] ont présenté des algorithmes de synthèse automatique

de contrBleurs qui permet tent de chercher des stratégies gagnantes ( winning strat egy )

applicables pour des jeux modélisés sous forme d'automates temporisés.

Dans ce mémoire, nous allons reformuler le problème de vérification en un problème

de synthèse. Autrement dit, nous d o n s transformer le problème de vérification qui

consiste à déterminer si un procédé vérifie certaines propriétés en un problème de synthèse

qui consiste à changer le comportement du procédé (en l'incluant dans une boucle de

rétroaction avec un contrôleur) de sorte qu'il satisfasse certaines propriétés.

Dans ce chapitre, nous allons introduire des concepts de base et des approches pour la

synthèse de contrôleurs des SEDs ; ensuite, nous allons présenter l'outil HyTech comme

étant une méthode de vérification des systèmes hybrides linéaires ; enfin, nous allons

essayer de transformer le probléme de vérification en un problème de synthèse tout en

tenant compte de la contrôlabilité des événements.

3.1 Aperçu sur le contrôle des SEDs

Dans cette partie, nous d o n s définir les principaux concepts relat& aux langages

formels et aux automates [15].

Définition 3.1 Une chahze sur zm ensemble le (appelé alphabet) est une suite fmie

d't?Zt5ments de C appelée aussi trace. Une chafne vide est m s e n t é e par le symbole

E .

Définition 3.2 Soit C un alphabet, l'ensemble de toutes les chafnes sur C , noté C*, est

defini par :

ii) s i s E C*et s E C , dors sa E C*.

Exemple 3.1 Si C = {a, b ) , dors C* = {E, a, b, ab, bu, aba, ... } .

Définition 3.3 Un langage L sur un alphabet C est un sous-ensemble de C*.

38

Exemple 3.2 Soit C = {a, 6). L'ensemble {ab, aabb, aaabbb, ...} est le langage de toutes

les chaînes contenant un certain nombre de a suiui par le meme nombre de b.

DéAnition 3.4 Soit d e w langages KI , K2 C C*.

rn L 'intersection de KI et K2, notée par Ki n K2, est le dangage

La concaténation de Kl et K2, notée par KI K2, est Ee langage

0 Le choix entre KI et K2, noté par Kl + K2, est le langage

Définition 3.5 Soit une chafne s E C*. La longueur de s noté Isl est définie comme

suit :

) I E I = O,

i ) Isol = Isl + 1, s E C.

Si t E C* est un préfie d e s, alors il est noté par t 5 S.

Exemple 3.3 Soit C = {a , b} .

Io1 = O) labl = 2 et labal = 3.

DéAnition 3.6 Soit un langage K C C, la femzeture de K , notée pr(K) C C*, est le

langage

pr(K) = {s E C* 1 3t E K : s 5 t )

Définition 3.7 Une machine à états est un quintuplet défini par G = (C, E, 29, eo, E,) tel

que E est un ensemble d'états, C est un ensemble finZ d'éudnements, 29 est une fonction

de transition d é f i e sur C x E - E, eo E E est un état initial et E, C_ E est un

ensemble d'états marqués (voir Z kxemple 3.4).

Pour que la machine à états concernée soit un automate dkterministe opkant sur des

chafnes au lieu d'opérer sur un alphabet, nous étendons la fonction de transition 6 sur

C' x E -+ E.

Definition 3.8 Soit G = (Z, E, 6, e ~ , E,) une machine à états. Le langage généré par

G , noté L(G), est défini w n m e suit (voir l'exemple 3.4) :

La notation d(s, eo)! est une abréviation de l'expression fi(s, ea) est définie.

Définition 3.9 Soit G = (C , E, -9, Q, E,) une machine ù états. Le langage marqué de

G, noté L(G) , est défini w m m e suit (voir l'exemple 3.4) :

Exemple 3.4 Cet exemple est tiré de [2]. L? modélise une machine ayant trois états

(voir la figum 11) : I (Idle), W ( WorLiing) et D (Doum) . Cette machine est modélisée par

la machine à états G = (C, E, $,a, E,) telle que C = {a, & f i , A} est l'ensemble des

événements, E = {1, W, D ) est l'ensemble des états, eo = I est l'état initial et E, = {1)

est l'ensemble des états marqués.

Le langage géné7é par G est l'ensemble de toutes les chafnes commençant à partir de

1 et suivant le graphe. Formellement, ce langage génén? est défini par le langage

Figure 11: Machine à &ats

L'état Idle repzésente un état marqué, c'est-à-dire une tdche complète. Le langage

marqué de G est l'ensemble de toutes les chatnes qui comrnençent et finissent à l'état I .

Formellement, le langage marqué est défini par le langage

3.1.2 Approches et concepts de synthèse de contrôleurs des

SEDs

Dans le contexte de la théorie de contrôle des SEDs [15,2,16], un environnement est

appelé procédé et son interconnexion avec un contrôleur forment un système en boucle

fermêe (closed-hop system) .

Dbflnition 3.10 Soit un automate G = (C, E, 6, a, E,) . Ce dentier est non bloquant

si L(G) = pr(t, (G)) .

L'expression L(G) = pr(L, (G) ) signifie que chaque chaine de L(G) peut &tre étendue

pour compléter une tache de Lm(G), c'est-à-dire que chaque sous-tâche de G peut être

complétée.

L'ensemble d'événements C d'un SED est divisé en deux sousensembles disjoints C , et

Cu qui représentent respectivement l'ensemble des événements contrôlables et l'ensemble

des événements incontr6lables. Soit A = P(C,), l'ensemble de tous les sous-ensembles de

Cc qui représentent les entrées de commande. Soit X tel que X E A ; si a E A, alors o

est prohibé, sinon a est permis. Un événement incontrôlable est toujours permis- Dans

un SED, une transition à partir d'un état e E E lors de l'occurrence d'un événement

o est permise si B(u,e)! et (T $ A. Le d e des e n t r k de commande est de guider

le comportement de G par rapport à un langage légal L sur l'alphabet C . Soit H un

automate h i déterministe (CI 2, c, a, 2,) tel que L = L,(H).

Étant donné un procédé G et un langage légal L, un contrôleur non bloquant doit être

construit de manière à ce que le comportement de G sous le contrôle d'un contrôleur C

soit restreint au plus grand nombre possible de suites d'événements légales. Le langage

défini par ces séquences est appelé le plus grand sous-langage contrôlable de L. Le procédé

et le contrôleur forment un système en boucle fermée, noté G/G, comme le montre la

figure 12.

Entrée de commande h

Figure 12: Boucle fermée

Les automates C et G évoluent d'une manière parall&le et intaagissent entre eux par

l'échange d'événements. Le procédé génère une suite d'événements qui seront envoyés

un par un au contrôleur ; œ dernier foumit à son tour une entrée de commande rela-

tive à chaque événement reçu- Le procédé et le contrôleur partagent le même ensemble

d'événements-

Dans la théorie du contrôle des SEDs, nous distinguons trois types de problèmes :

le problème du contrdle supervisé (SC) , le problème du contrôle supervisé non bloquant

et marque (MNSC) et le probkme du contrôle sup&é non bloquant (NSC). Dans le

probl&me SC, la notion d'état marque n'est pas pertinente. Dans le problème MN%,

certains états du contrôleur sont marqués- Ainsi, le contrôleur a le rôle de reconnaître

les thches complètes. Finalement, dans le problème NSC, le procédé détecte les tâches

cornpl& es.

Danition 3.11 Soit un procédk G. Un langage K C C* est contr6lable par rapport à

G si pr(K) Eu n L(G) pr(K).

La condition de contrôlabilité est 6quivale~te à la condition suivante :

Cette condition signifie que pour chaque préfix s E pr(K), si s est suivi d'un événe-

ment incontr8labie o E Cu tel que so E L(G) alors la chaîne so est aussi un p r 6 k

appartenant à pr(K). Autrement dit, K est contr6lable si pour toute sous-tâche s de K

suivie d'un événement incontrôlable CT E Cu possible dans Gy sa est aussi une sous-tâche

de K.

Soit S(Ln Lm (G) ) l'ensemble des souslangages de Ln Lm (G) contrôlables par rapport

A G :

L'ensemble 9 est non vide et contient un unique plus grand souslangage contrôlable

noté KT. Si Kr # 0, il existe un contrôleur C pour G tel que L,,,(C/G) = KT.

Du point de vue pratique, le contrôleur C est représenté par le couple (S, cl), où

S est un automate fini déterministe (C, Dy C, do, Dm) et +y : D - A une fonction de

rétroaction (control law). Le système en boucle fermée C/G représenté par l'automate

(Cl D x E, C x 19, (do, s) , Dm x E,) est le produit cartésien de S par G. La transition

de (d, e) à ( I ( q d), B(a, e)) sur l'événement CT est définie si 5(0, d)!, 6(0, e)! et o $ y(d) . La méthode la plus connue pour le calcul de Kf est celle de Wonham et Ramadge

[2]. Cette méthode se caractérise par la notion de point fixe (se référer à la méthode des

apprmimations successives). Soit l'opérateur 0 : P(C*) - P ( C ) défini par :

R(K) = Ln Lm(G) n sup{T C C' 1 T = pr(T), TC, fi L(G) p r ( K ) }

Dans cette équation, l'expression Ln Lm(G) garantit que le système en boucle fermée

inclut seulement les tgches complètes légales qui sont possible dans G. LYt5galité T =

pr(T) et l'inclusion TC, n L(G) pr(K) sont reliées respectivement aux concepts de

non blocage et de contrôlabilité. Il existe d'autres algorithmes pour le calcul de K f . Nous

référons le lecteur vers l'article de Barbeau et al. [l6].

3.2 Présentation de l'outil de vérification HyTech

Une méthode de vQification est une technique qui consiste à déterminer si les modèles

mathématiques représentant des syst&mes (procédés) vérifient des propriétés spécifiques

à un comportement désiré.

HyTech est un outil de vérification automatique et symbolique des systèmes embar-

qués, R permet de vkrifier si un système, modélisé sous forme d'un automate hybride

linéaire, vérSe des formules décrivant des propriétés exprimées en logique temporelle par

le langage de spécification Integrator C~m~vutation ï h Logic (ICTL) [8]. En plus de

la vgification, HyTech permet de calculer des contraintes s u f b n t e s et nécessaires sur

des pa.ram&tres des systèmes dont les valeurs n'ont pas été spécifiées et de générer une

trajectoire d'erreur qui illustre la séquence des transitions discr&tes qui ont produit la

violation d'une proprikt6 [5,4]. Ces contraintes sont utiles afin d'assurer que le système

v6rifie des propriétés désir-. Soit une formule ICTL et un automate hybride linéaire A.

L'outil HyTech calcule la région cible des états qui satisfont la formule par la méthode

des apprcocimations successives. Cette dernière consiste à calculer l'ensemble des états

vérifiant une formule ICTL comme étant une limite d'une séquence infinie de régions.

La séquence d'apprcocimations successives est générée par l'itération des opérateurs

booléens et des opérateurs de prémndition sur des régions. Pour un système hybride

linéaire, toutes les régions de la séquence d'appruxirnation sont linéaires dans le sens

qu'elles peuvent &tre définies par des formules de la théorie du groupe (31, +) muni de la

relation d'ordre 5. La procédure de vérification présentée par HyTech a été implantée

comme une partie de l'outil CorneII Hybrid TECHnology [17]. HyTech utilise l'outil de

calcd symbolique MATHEMATTCA [18] pour la manipulation et la simplification des

formules dans (a,+). La procédure du modèle de vérification de HyTech est une ex-

tension des approches de vérification présentées dans [19,1,9]. Ces dernières permettent

la vérification des propriétés exprimées par la logique Timed Computation The Logic

(TCTL) des systémes temps réel. La logique ICTL est une extension de la logique TCTL

par l'adoption des variables intégrateurs. Pour plus d'information sur H y T 6 nous

orientons le lecteur vers [20,21].

3.2.1 Définitions préliminaires

Nous d o n s utiliser l'exemple de l'automate hybride du thermostat (voir la figure

13) présenté dans le chapitre 1 afin d'illuster les définitions suivantes par des exemples.

DéAnition 3.12 Une région de données convexe est un polyédTe conveze sur !Rn. Soit

A ua automate hybride linéaire. Au niveau de chaque mode de commande u de A, une

région de donnkes est définie par le couple (v,%) tel que v est un mode de commande

Figure 13: Exemple de l'automate hybride du thermostat

et R, est la région de données corregpondante. Une région de données R peut &tre aussi

définie par une union finie de régions de données R, pour chaque mode de commande v,

telle que R = U (v, a). vEV

Exemple 3.5 D'aprés la figure Y , R1 et R2 définissent respectivement la région de

données du mode de commande on et la région de données d u mode de commande off

notées par (on, RI) et (on, R d L ' u n i o n de de= régions de données Ri et R2 definit une

région de données R telle que R = (on, Ri) U (off, R2).

Figue 14: Exemple de régions de données

Déflnition 3.13 Un pprédat de données (convexe) est une formule linéaire (convexe)

sur X . Soit A un automate hybride linnéairq P un prédicat de données qui définit une

+on de données R = [[Pl] E En et q = (v, a ) u n état de A. L'état q appartient à la

région R, c'est-à-dim a E [[Pl] si et seulement si P [[X =a]] est mi.

Exemple 3.6 La région RI est définie par le prédicat de données P = x 5 M , c'est-à-

dim qae Ri = [[Pl]. Soit u n état q = (a, a) tel que a est une éualuation de x. L 'état q

appartient à la région RI si a 5 M.

D6Anition 3.14 Soit A un automate hybride linéaire, R, une région de données définie

au niveau du mode de commande v notée par ( v , a) et P, u n prédicat de données tel

que R, = [[Pu]]. La région de données (v, & ) est définie par un prédicat d'état @ tel pue

O = (v, Pu). Un prédicat d'état O peut &tre aussi défini par une union de prédicats de

données Pu pour chape mode de commande v tel que O = U (v, P,) définit la m i o n de v E V

données [Pl1 = u (v, [[Pull). U E V

Exemple 3.7 Les de- modes de commande on et off sont définies respectivement par

les prédicats d'état = (on , Pl) et a2 = (off, P2) tels que Pl = x 5 M et P2 = x 2 rn

sont deux prédicats de données. La région de données R = (on, Ri) U (08, R2) est déinie

par le prédicat d'état <P = (on, Pl) U ( o E P2) telle que Ri = [[Pi]] et RÎ = [[PZ]].

DMinition 3.15 Soit A u n automate hybride linéai~e. QA définit l'ensemble des états

admissibles de A dgfini par le prédicat d'état CA = U (v, Inv(v)). VEV

Exemple 3.8 L'ensemble des états admissibles de l'automate hybride du thermostat est

défini par le prédicat d'état CA = (on, x 5 M ) U (og , x 2 m)

D&Bnition 3.16 Une formule linéaire convexe sur X est une conjonction d'inégalités

l i néa im sur X. Chaque formule linéaire peut &tre trunsfornée en une f o m e normale

disjonctive, c 'est-à-dim une disjonction finie de fornules linéaims convexes.

3.2.2 Propriété du langage de description ICTL

Une formule ICTL spécifiant une prop&té d'un sys the hybride linéaire A, peut

contenir deux types de variables : variables de données et variables intégrateurs [a]. Un intégrateur (ou stop watch) est une horloge (timer) qui peut être arrétée et redé-

marrée. Il sert à accumuler le temps et à spécifier une propriété de durée (duration). Par

exemple, une réponse est obtenue si la sonnerie a été pressée, même d'une façon inter-

mittente, pendant une durée minimale de d secondes. Une horloge définie par la Iogique

TCTL sert à exprimer des propriétés de temps borné ( timed-bounded). Par exemple, une

réponse est obtenue si la sonnerie a été pressée d'une façon cuntinue pendant une durée

minimale de d secondes. La logique ICTL présente un reset quantiFer (z : U) . p qui

introduit un intégrateur z, déclare son type par U et remet sa valeur à zéro. Le type de

z est un ensemble des modes de commande de A. La valeur d'un intégrateur de type U

évolue en fonction du temps une fois que le contrale d'automate est au niveau d'un mode

de commande appartenant à U, et sa valeur reste inchangeable une fois que le contrôle

d'automate est au niveau d'un mode de commande appartenant à U / V .

3.2.3 Syntaxe

Une formule ICTL est construite à partir des prédicats d'état, d'opérateurs booléens,

des opérateurs 3U et VU et d'un m e t quantifier pour les intégrateurs. Elle est interprétée

s u . l'espace d'états d'un automate hybride linéaire A.

Un état q vkrifie la formule ICTL p,3Up2, s'il &ste une exécution ou trajectoire

commençant à partir de q jusqu'à q' telie que q' v&ifie le prédicat d'état p, et la

formule p, V p2 est vérifiée pour tous les états intermediaires entre q et q'.

Un état q vérifie la formule ICTL p,tlUp,, si pour toute exécution ou trajectoire

commençant à partir de q jusqu'à q' telle que q' v a e le prédicat d'état p2 et la

formule p, V p2 est vérifiée pour tous les états intermédiaires entre q et q'.

Soit A un automate hybride linéaire ayant un vecteur de variables de données X,

un ensemble des modes de commande V et Z un vecteur de variables de valeurs réelles

appelées intégrateurs.

Un prédicat de données extension-Z de A est une formule linéaire sur X U 2. Un

prédicat d'état extension-Z de A est une union de prédicats de données extension4 Une

formule de la logique ICTL est définie par la grammaire suivante :

telle que @ est un prédicat d'état extension-Z de A, U C V est un ensemble de modes

de wmmande et r est un intégrateur appartenant à 2. Si tous les intégrateurs de p sont

de type V, alors p est une formule TCTL. Nous utilisons une combinaison booléenne des

modes de wmmande pour définir les types des intégrateurs.

Les abréviations typiques des formules ICTL utilisent les opézateurs temporels st an-

dard suivants :

Nous pouvons utiliser des opérateurs temporels de temps borné tels que QOs5p qui

est dquivalente à la formule (z : trile) (trueVU(z 5 5 A p ) ) .

Le langage de spécification ICTL permet d'exprimer certaines propriétés définies

comme suit :

Propri&é d9accessibilit6 : cela revient à déterminer la région de données à partir

de laquelle il est possible d'atteindre la 16gion de données définie par une formule

p, exprimée en ICTL par la formule 3 0 p .

Propriété de sûrete : elle est aussi appelée propriété d'invariance, cela consiste

à vérifier si la région de données de l'état initial d'un système hybride est incluse

dans la région de données définie par la formule 3Op.

0 Propriété de réponse temps borné : cette propriété dénote qu'un événement

donné doit se produire dans un i n t e d e de temps [O, t ] (c'est-à-dire au plus tard

à l'instant t) ; elle est exprimée en ICTL par la formule 3Octp. -

Propriété de vivacitb : cette propriété est exprimée en ICTL par la formule

v w p .

Propriété de du& : nous utilisons des variables de type intégrateur pour la

définition de ce genre de propriété. Un intégrateur sert à accumuler du temps au

niveau de certains modes de commande v, il est deh i par l'expression (2 : U) p

où U est un ensemble de modes de commande.

3.2.4 Sémantique

Chaque formule ICTL !D définit une région [ [ @ ] ] A de l'automate hybride A. La

région [[*]]A est appelée région-A caractéristique de 9. Elle est d&nie en trois étapes.

D'abord, nous étendons A à un automate Az dont les vèxriables de données incluent des

intégrateurs de 2. -te, nous interprétons !P sur les états de l'automate étendu AZ.

Enfin, nous convertissons les &ats de Az en états de A.

Soit Z = (zl , ... , h) le vecteur des intégrateurs qui apparaissent dans @ et Ui , . . . , U, les types correspondants. Nous dénnissons à partir de l'automate hybride linéaire A =

(X, V, Inv, Flow, Init, E, Jump, C) de dimension n, l'automate hybride linéaire Az =

( X U 2, V, Inv, Flow', Init, E, Jump, C) de dimension (n + m) tel que pour chaque mode

de commande v E V, nous avons,

Flow' (v) = FLow(v) A (&= 1) A (&= O) l _ < i h m 1 ( i _ < m

v E U. v e ui Au niveau de chaque mode de commande v, l'intégrateur z; 6volue dans le temps si

v E Ui et reste inchangeable si v $! Z&. Pour chaque état de données (évaluation de X U Z )

a E 8"- de Az il existe une projection-X a Rn qui définit un état de données de

A et une projection-Z a Iz€ Rm qui afFecte à chaque intégrateur de Z une valeur réelle.

Chaque état q = (v, a) de Az consiste en un état q lx= (v, a l x ) de A et une évaluation

des intégrateurs q l z = a lz. En particulier, QA, = QA x Sm (Qa est l'ensemble des états

admissibles de A).

Nous pouvons appliquer l'opération de projection l x sur les régions de données et

les trajectoires ; la projection-X d'une région de données R de Az définit une région de

données R' de A qui est obtenue par la projection-X de tous les états appartenant à R ;

la projection-X d'une trajectoire de AZ est une trajectoire de A.

Soit un ensemble I' des trajectoires de A, l'extension-Z rz est l'ensemble des tra-

jectoires étendues qui définit toutes les trajectoires de Az telles que la projection-X de

rz appartient à r. Soit un état q de AZ, la relation q kr @ est définie pour toutes les

formules \E de ICTL de la façon suivante :

O q br @ si et seulement si, q E [[a]], Q est un prédicat d'état.

0 q br i p si et seulement si q Fr p.

O q br p13Up, si et seulement si pour une trajectoire r € rz avec r (0 , O) = q, il

e s t e une position n dans T telle que T(T) kr p2 et pour toute position ir' de T, si

+ I alors ~ ( d ) Fr PI V pz-

0 q kr piVUp, si et seulement si pour toute trajectoire r E rz avec ~ ( 0 , O) = q, il

existe une position 7r dans T telle que T(T) kI. p2 et pour toute position 7 f de T , si

6 5 alors T(+) Cr PI V A-

q kr (z : U) - p si et seulement si q[z := U] br p.

3.2.5 Systèmes de transition

En plus des définitions qui ont été présentées dans le chapitre 1 concernant les

systèmes de transitions, nous d o n s aussi tenir compte des concepts présentés dans cette

section.

La trajectoire d'un système hybride est une séquence de deux étapes, time step et

tram'tion step, à travers un espace d'état. Soit Q = U (u, Q.) une région de A, nous v E V

définissons :

The step

Q Pour tout état ql = (vl, al) et q2 = (v2, a*) de A, q, - q2 est déhie si vl = v2 et iI

4 s t e une fonction différentielle p : [O, 61 -r Sn t e k que :

rn D a m i t i o n step

Q Pour tout état ql et q2 de A, ql H 92 est définie si a, q2 E ÇA n Q et il existe une

transition e = (v, vf ) E E telle que le prédicat Jump(e) définissant la condition de saut

entre v et tf est vraie.

3 -2 -6 Opérateurs précondition

Dans cette partie, nous d&nkions deux types d'opérateurs tinte-précondition pre,

et transition-précondition Fe,.

soit Q = U (v, Qu) et R = U (v, a) deux régions de do~mées d'un automate hybride v E V vEV

linéaire A qui sont définies respectivement par les deux prédicats d'état @ = U (v, q,) v E V

et x = U (v, r,) tels que pour chaque mode de commande v E V nous avons [[q,,]] = Qu v E V

et [[r,]] = R, (q, et r, sont deux prédicats de données qui défùiissent respectivement les

deux régions de données Qv et &). Les deux prédicats d'état définis par pre%(x) et

ppeo (x) définissent respectivement les deux rkgions de données preo (R) et prez (R).

Nous définissions la précondition-A (R) par l'union preo (R) U preo (R) . Étant

donné que les prédicats d'état O et x représentent respectivement les deux régions Q et

R, dors p e Z ( ~ ) est défini par le prédicat d'état

Dans la suite de ce mémoire, nous nous intéressons aux conditions d'invariance qui

sont définies par des formules convexes linéaires ce qui simplifie la construction du prédi-

cat preo (x)-

Précondition de temps La précondition pree (u; a) définit une région de données

R: à partir de laquelle un état q appartenant à la région R, est accessible en fonction Q d'une seule &ape p.

Étant donné que les régions de données Q = U (v, Q,) et R = (v, &) sont définies v E V V E V

respectivement par les deux prédicats d'état O = U (v, q, ) et x = U (v, r,,) tels que pour vEV v f V

chaque mode de commande v E V nous avons [[q,,]] = Qu et [[ru]] = & alors la région de

données pre- (u; &) est aussi définie par le prédicat de données prePY(v; ru). En terme

de prédicat d'état, nous définissons

et en terme de région de données nous d6hissons

p.eo (R) =vyv (W. reov (v; Ru))

Avant de procéder au calcul du prédicat de données pree (v; r,), nous allons d'abord

présenter une méthode de calcul du prédicat de données pre"(u; ru) que nous dons

utiliser par la suite. Cette méthode est définie par la proposition suivante.

Proposition 3.1 Soit A zm automate hybride finéaim, v un mode de commande et r,

un prédicat de données. Nous définissons

Alors

[ [p" (v; TV)]] = preyn"'v"' (v; [[r,]] )

Le produit 6 Flow(v) est calculé par la multiplication de chaque constante de la

condition de flux Flow(v) par la variable 6. Par exemple, si FZow(v) est définie par le

prédicat x1 = 6 h x3 = 1, alors b - Flm(v) = xi = 66 /\ S = 6.

La formule preLm(v; ru) est une formule de la théorie du groupe (W, +) munie de la

relation d'ordre 5. Puisque cet te théorie admet l'élimination des quant ificateurs, alors

la formule preFe(v; ru) est équivalente à un prédicat de données. La section suivante

présente une procédure d'élimination des quantificateurs utili& par HyTech.

Procédure d'blimination des quantificateurs

Nous &minons les quantificateur existentiels d'une formule un par un. Considérons

la formule 36.p où p est une formule linéaire sur X U (6). D'abord, nous convertissons la

formule 36.p en une formule équivalente Vi36.pi telle que pi est un prédicat de données

convsre sur X U (6). Ceci est possible car, le quantificateur existentiel est distributif par

rapport aux disjonctions. Ensuite, nous convertissons chaque inégalité linéaire de pi sous

la forme O -- e telle que e est un terme linéaire et -E {<, 5). Nous supposons que pi est

de la forme suivante :

telle que qi ne contient pas 6.

Par exemple, à ce niveau, nous convertissons certaines conjonctions oontenant b sous

la forme 9 6 ou sous la forme 6 w j ~ 5- Enfin, nous éliminons 6 par la combinaison

des conjonctions. Exemple, les conjonctions x + 3 5 6 et 6 < 4y forment une nouvelle

conjonction x + 3 4y. Alors nous obtenons la formule suivante :

I c + l < j f < m

telle que -jjt est de la forme < si m j OU N j f est de la forme < ; autrement -jjf est de la

forme 5.

Exemple 3.9 Nous allons pdsenter un exemple détaillé de calcul d u prédicat de données

preEue(v; r,) tout en utilisant la proposition 3.1. D'abord, nous supposons que l'automate

hybride linéaire A possède deux variables x et y , u n invariant Inv(v) = ( y 2 O ) et une

condition de flvz Flow(v) = (x = 1 A y = 2) pour le mode de commande v.

Considérons le prédicat de données r, = ( 1 5 x 5 2 A 2 5 y 5 3). D'apprès la

proposition 3.1,

N o w éliminons les quantijïcateurs existentiels. N o w obtenons (voir la figurz 15),

Figum 15: L 'opérateur time-précondition p r e y

Pour le calcul du prédicat de données pre%(v; ru), nous considérons v' un mode de

commande effectif ayant une condition d'indance Inv(uf ) = (Inv(v) A q,) et une con-

dition de flux Flow(v) . Alors,

En fait, par la proposition 3.1 nous obtenons

pre?(?") (v'; r,) = pre"(vl; r,)

Précondition de transition

La précondition preo (v; &,) d&it la région de données à partir de laquelle un état

appa,rtenant à (v,&) peut &tre atteint en une seule &tape A. Étant donné que les

régions de données Q = U (v, Q.) et R = u (v, a) sont définies respectivement par UEV VEV

les deux prédicats d'état 8 = U (v, q,) et x = U (v, r,,) tek que pour chaque mode vEV vEV

de commande v E V nous avons [[q,]] = Q, et [[T"]] = R, alors la région de données

pre? (v; R,,) est aussi définie par le prédicat d'état prez (v; r,). En terme de prédicat

ou en terme de région de données nous définissons

La proposition suivante construit preo(u; ru) comme étant une formule de la théorie

du groupe (33, +) munie de la relation d'ordre 5, à partir de laquelle, un prédicat de

données peut être obtenu par l'élimination des quant Scat eurs.

Proposition 3-2 Soit A un automate hybride linéazre, E un ensemble de transitions, v

un mode de commande, 8 = U (v, q,,) un p&icat d'état et ru un prédicat de données. v E V

Nous définissons

preo(v,r,,)= U ( ~ ' , q ~ ~ ~ ~ n v ( u ' ) A ( ~ ~ ~ ~ J u m p ( e ) ~ ( r ~ ~ q ~ ~ ~ n v ( v ) ) [ X ' = X ~ ) ) =(v',v)EE

(3-4) Alors

Proposition 3.3 Soit q,, q,, et ru des prédicats d'état et une commutation de commande

e = (ut, v). La tmnsition de préfondition au niveau de v par apport à e est cnlculée par

la fornule

Exemple 3.10 Nous allons présenter un mernple d&taillk de calcul du prédicat d'&tut

prez (v; ru) tout a utilisant la proposition 3.3. Soit un automate hybride linéaim A ayant

deux variables de données x et y, et devz tramrtS2tions discrètes el = (vr,v) et ea = (v, v)

(ea est appelée transition shtter). Supposons que Jump(ei) = ( x 5 3 A x' 2 5 A A = x) ,

Jwnp(e2) = (d = x, y' = y), et qv = qvl = Inv(v) = Inv(d) = true. Considérons le

pn2dicat de données rv = (x 1 6 A y $ 2 ) . Selon la proposition 3.3, nous avons,

prez(v;r,) = (z/,(M.3y'. x 5 3 A d 2 5 A yr = x A x r 2 6 /\y' 5 2)) v (v,(32.'.3y'.

x ' = x A y ' = y ~ d 2 6 ~ y ' S 2 ) )

La pmnaiére disjonction correspond à la transition el et la deuxième disjonction cor-

respond à la transition el (voir la figum 16). Nous éliminons les deux quantificateîlrs

existentiels. Nous obtenons

et finalement

Figure 16: Illustration de l'exemple

3.2.7 Modèle de vérification symbolique

Soit un automate hybride linéaire A et une formule \E de la logique ICTL, le problème

du modèle de vérification est de calculer la région caracteistique [ [ @ I l A par la construction

d'un prédicat d'état 8 tel que [[a]] = [[Q]la- Le prédicat d'btat 8 est appelé prédicat

~a;~actéristique de (A, 9).

La procédure M V S (mod&le de v6rification symbolique)

La procMure MVS calcul le prédicat caractéristique de (A, @) sous forme d'une

séquence de prédicats d'état. Si la séquence d'apprmchation successive converge en un

nombre fini d'étapes, alors La procédure MW3 aboutit et retourne un prédicat caractéris-

tique de (A, Q). La séquence d'appracïmations successives peut diverger, dans ce cas la

procédure MVS n'aboutit jamais. Cette procédure utilise un automate hybride Az. Si

un automate donné A est nonzeno alors aussi est l'extension-Z et Ca, = Ca tel que

CA = U (Y, Inv(v)). Le prédicat caractéristique de (Az, a) peut &tre simplifié par le VE V

prbdicat caractéristique de (A, Q) car le premier n'impose pas des contraintes sur les

intégrateurs de Z.

Procédure M V S

Input

- Un automate hybride héaire A.

- Une formule en logique ICTL.

Output

- Un prédicat caractéristique 1 Q 1 de (A, I) .

Le prédicat caractéristique 1 9 1 est calcul6 pour toutes les formules de ik :

I ( z : U) pl = lpl [z = O] (remplacer toutes les occurrences de r dans (pl par 0)

Nous dons limiter notre discussion sur l'équation (3.6) pour vérifier si un procédé

satisfait des propribt és d'accessibilité.

3.3 Procédure de synthèse de contrôleurs

Dans cette section, nous d o n s présenter la stmcture d'un contrôleur ainsi qu'une

reformulation d'une pro&ure de vérification [8] en une procédure de synthèse.

3.3.1 Structure d'un contrôleur

Le contrdleur observe de manière continue le comportement (l'évolution d'état) du

procédé. Nous supposons que l'ensemble des événements C est divisé en un ensemble

d'événements contrôlables Cc et en un ensemble d'événements incontrôlables Cu. Une

commutation de commande contrôlable est étiquetée par un événement contrôlable qui se

produit une fois qu'elle sera désignée par le contrôleur. Une commutation de commande

incontrôlable est étiquetée par un événement incontrôlable qui se produit une fois qu'elle

sera possible. Intuitivement, le contrôleur fore par un choix instantané une commutation

de commande contrôlable ou se contenter d'observer l'évolution de lëtat du procédé.

Le contrdleur (ou les lois de commande) d'un système hybride linéaire est défini par la

fonction f, : Q + Cc U (1) telle que le symbole 1 représente une action de commande

nulle. La sémantique de la fonction fc est définie comme suit :

Si fc(q) = I alors le contraleur ne choisit aucune action de commande et le temps

continue à progresser.

0 Si f,(q) = o alors il existe une commutation de commande contrôlable e = (v, v') E

E étiquetée par l'événement O E Cc.

Nous représentons l'interconnexion en boucle fermée d'un système hybride linéaire,

représenté par un automate hybride linéaire A, et d'un contrôleur C par le couple (C, A).

Soit q = (v, a) et q' = (d, a') deux états de A, le couple (q, q') représente soit :

un saut contrôlable

Pour chaque événement oc E Cc, le triplet (q, oc, q') représenté par q %(C,A) q' est

un saut contrôlable de (C, A) si et seulement si q %A q' et fc(q) = 0,.

un saut incontralable

Pour chaque événement incontrôlable ou E Cu, le triplet (q, ou, 6) représenté par

q QI est un saut incontr6lable si et seulement si q %A q'.

un flux contrdlable

6 Pour chaque valeur positive d E R+, le triplet (q, 6, q') représenté par q q'

est un flux contrdlable si et seulement si :

2. il existe une fonction dérivable <p : [O, 61 -r ?P telle que pour chaque d E [O, 61

nous avons fc(v, <p(d)) = 1.

3.3.2 Adaptation d'une procédure de vérification en une procé-

dure de synthèse

Une trajectoire contrôlable du système en boucle fermée (C, A) est une séquence

finie qo, ..., q k d'états admissibles telle que qo est un état initial et chaque paire d'états

cons6cuti.fk est soit un saut contr6lable ou un saut incontrôlable ou un flux contrôlable.

En se référant à la méthode de vérification de HyTech, le probl&me de synthèse con-

siste à détermii?.er des trajectoires contr8lables qui assurent un comportement désiré du

procédé et de générer les lois de commande correspondantes. Ce comportement est défhi

par des propriétés à sathfaLe par le procédé et qui sont exprimées en logique temporelle.

Autrement dit, le problème consiste à vérifier si le procédé vérifie des propriétés qui

représentent des contraintes sur son comportement. Dans ce mémoire, nous nous intéres-

sons à des propriétés d'accessibilité.

La vérification d'une propriété d'accessibilité consiste à vérifier si une région de don-

nées Ri définie par une formule de la forme 3@Di est incluse dans une région de données

& définie par un prédicat d'état Oo. En effet, nous notons par - 30@, la pro- * priété P à vérifier telle que et QI définissent respectivement son état initial et son

état final. En termes de trajectoires, cette formule revient à exprimer s'il existe une

trajectoire wmxnençant à partir des états appartenant à la région de données définie par

le prédicat d'état jusqu'awc états appa.rtenant à la région de don& définie par le

prédicat d'etat al. Ainsi, le problème de synthèse se transforme en un problème de véri-

fication. Une fois qu'une propriété P est vérifiée, c'est-à-dire qu'il existe une trajectoire

qui la vérifie, alors les lois de commande de la trajectoire correspondante sont générées

afin de garantir une acécution correcte du procédt5 par rapport à cette trajectoire. La

procédure de dérivation d'un contrôleur doit tenir compte des wntraintes imposées sur

le comportement du procédé. Le rôle du contr61eur est de guider l'exécution du procédé

afin de satisfaire toutes les propriétés. En fait, une propriété P est exprimée en fonction

d'un état initial et d'un 6tat final qui sont désignés respectivement par P.état - initial et

P.état - final. Chaque état de la propriété P est défini par un prédicat d'état qui consiste

en un couple (u, r,) tel que v est :m mode de conunande et ru est un prédicat de données

définissant une région de données R, du mode de commande conespondant. Les termes

v et r, sont désignés respectivement par P. état - (initial ou final).^ et P. état - (initial ou

frnuZ).ru tek que R, = [[P. état - (initial ou f i a l ) .rJ.

La formule 3081 est une abréviation de true3UGi qui consiste à calculer la région

de données à partir de laquelle la région de données définie par le prédicat d'état est

accessible. A ce niveau, nous allons reformuler la procédure de vérification définie par

l'équation (3.6) afin de l'adapter à la formule t r ~ e 3 l l @ ~ qui se présente comme suit :

En termes de régions de données, la verification de la propriété Qo --, 3Qa1 revient

à déterminer si la région de données calculée par est incluse dans la région de

données déhie par 90. Si c'est le cas, alors la propriété est vérifiée. La procédure de

vérification d'une propriété P revient à vérifier si la propriété P est satisfaite, c'est-à-dire

déterminer s'il existe des états intermédiaires à travers lesquels il existe au moins une

trajectoire commençant à partir des états appartenant à la région de données définie par

le prédicat d'état jusqu'aux états appartenant à la région de données définie par le

prédicat d'état al. Pour que le procéd6 ne s'arrête pas à un état, nous allons vérifier s'il existe une ou

plusieurs concaténations de trajectoires, définies par les propriétés, et constituant un ou

plusieurs cycles. Un cycle est représenté par l'ensemble des propriétés qui sont ordonnées

selon la trajectoire qui le définit. Il assure que chaque trajectoire qui y appartient peut

être un préfixe d'une autre trajectoire. Par exemple, soit un cycle c = (Pl, PÎ) tel

Figure 17: Exemple d'un cycle

La figure 17' présente un cycle obtenu par la concaténation de deux trajectoires

trajectoirel et erajed&ea qui vérifient respectivement la propriété Pl et la propriété

p2

Un ensemble de propriétés définit un cycle si les conditions suivaates sont satisfaites.

1. Toutes les gropriétés sont satisfaites (chaque propriété définit une trajectoire).

2. Chaque mode de commande v d'un état initial d'une propriété est un mode de

commande d'un état final d'une autre propriété.

3. La région de données calculée par une propriété d'accessibilité est incluse dans la

région de dionnées définie par l'état fuial de sa propriété prédécesseur. Cette con-

dition est nécessaire pour garantir que la trajectoire définie par une propriété peut

être un préfixe de la trajectoire de sa propriété successeur afin d'obtenir un cycle.

Par exemple, la figure 18 prknte deux trajectoires lmjectoire, et trajectoire, qui

vérifient respectivement deux propriétés f i et P2 telles que Pi = al --r 30a2 et

P2 = 4 - 30Q4. Les prédicats dëtat al, a2, et a4 sont dkfinis respective-

ment Par (vl,rv,), (v377&), ( ~ 3 7 P ' ~ ) et ( s 7 7 - , ) tels que % = [[r,,]], R, = [[rwll,

R& = [[r',]] et R, = [[TuJ]] sont des régions de données. Supposons que R est

la région de données définie par la formule alors la propriété P2 est v6rifiée

si la région de données R est incluse dans la région de données R& dé6nie par le

pr6dicat d'6tat a3. Pour que la tmjectolre, puisse &tre un préfke de la tmjectozre, ,

il faut que la région de dom& R, définie par a2 i'état final de la propriété Pl

soit incluse dans la région de données R.

Figure 18: Concaténation de deux trajectoires

La procédure v&riRcation - cyde (voir la figure 19) consiste à vérifier si un ensemble

donné de propriétés définit un cycle. Cette procédure reçoit en entrée le cycle à examiner

qui est déhi par un ensemble de propriétés. La variable région-début - cycle (ligne 3)

consiste à sauvegarder la région de donnée calcul& par la première propriété vérifiée du

cycle. Chaque région de données d'un état ha1 d'une propriété est sauvegardée dans la

variable r@ion - état-finalpropriété - prédecesseur (ligne 4). La boucle tant que vérifie

si toutes les propriétés appartenant au cycle sont satisfaites. Si une propriété ou le cycle

n'est pas vérifié alors la boucle tant que est am&& (lignes 10-12). Une fois que toutes

les propriétés sont vériûées, nous vérifions si mion-début cycle n'est pas incluse dans

la région de données définie par l'état final de la dernière propriété du cycle. Si c'est le

cas, alors les propriétés ne peuvent pas défml un cycle (lignes 14-20).

La vérincation d'un cycle revient à vgifier toutes les propriétés qui le définissent par

l'intermédiaire de la procédure vbrification - propriété (voir la figure 20). En effet,

au nivau de cette procédure, nous définissons un ensemble appelé ktats - à - traiter qui

contient tous les ktats à partir desquels nous d o n s calculer leurs préconditions de temps

définies par l'équation (3.1) et leurs préconditions de transition définies par l'équation

(3.3). Ce traitement est défini par les lignes (5-9). Au niveau de la ligne 4, l'ensemble

états - à- traiter est initialisé par l'état - final de la propriété P comme étant un état

de départ. Le traitement de la boucle tant que est arrêté une fois que l'ensemble

états- à- tmiter ne contient plus d'élément. A ce niveau, nous sauvegardons la région de

données définie par l'état final de cette propriété (ligne 10).

La procédure time - précondition (voir la figure 22) reçoit comme parametre tous

les états à traiter définis par l'ensemble états - à - traiter. Cette procédure consiste à

calculer pour chaque état (v, r,) de l'ensemble états - à-traiter la nouvelle valeur du

prédicat de dom& r, en fonction de l'opérateur défini par l'équation (3.2) (ligne 5). En

fait, nous obtenons un nouvel état (v, tu). Nous vaifions si ce dernier est déjà calculé par

cette procédure, c'est-à-dire qu'il existe dans l'ensemble ensemble- états - traités. Nous

l'éliminons alors de l'ensemble états - à - tmiter pour qu'il ne soit pas traité une autre fois

(ligne 6 et 7) (figure 21 a).

20 finsi 21 fin

Figure 19: Procédure v6rification-cycle

1 O &@on-é~~d~mpn'étégré&cessetlr t [[P.&zt&ol grr]] ( I l fin

Figure 20: Procédure vérification-propriété

Figure 21: Exemple de trajectoires

Si le nouvel état (v, ru) n'est pas déjà traité, alors il est ajouté à l'ensemble m e m -

6 - ktuts- tmités (ligne 9).

Le deuxième cas de la figure 2 1 montre qu'il peut exister plusieurs trajectoires entre

l'état initial et l'état final d'une propri6té. Dès que l'état initial est vérifié alors il existe

une trajectoire entre l'état initial et Mtat fmal (ligne Il), autrement dit, la propriété P

est vQifiée (ligne 14). Dans ce cas, la procédure de vérification de cette propriété est

arrêtée par l'affectation de l'ensemble vide à l'ensemble états - ù - traiter (ligne 15). Les

lignes (16-18) initialisent la vaxiable région - début - cycle. Ceci est fait une seule fois

à la vérification de la première propriété du cycle. Une fois qu'une propriété est vérifiée,

nous vérifions si la région de données satisfaisant la propriété courante n'est pas incluse

dans la région de données de l'état ha1 de la propriété précédente. Dans ce dernier cas,

il n'existe pas un cycle qui peut être d é h i par ces propriétés (ligne 19+21).

La procédure transition - prkondition (voir la figure 23) consiste à calculer pour

chaque état (v, r,) de l'ensemble états - à- traiter (lignes 4-6) ses états prédécesseurs

(II' , TL) en fonction des transitions discrètes. D'abord, cela revient à déterminer toutes

les commutations de commande e = (v', v) E E dont le mode de commande cible est v

(ligne 8). Ensuite, en fonction de chaque commutation de commande e nous calculons le

prédicat de données rb en fonction de l'équation (3.5) (ligne 10). La nouveau prédicat de

données rh peut définir une région de données vide, c'est-à-dire que (v, r,) n'est jarnais

atteint à partir de l'état (d , 4). Ce dernier ne fait pas alors l'objet d'un nouvel état

à traiter. Si le prédicat de données TL définit une région de données non vide, dors

nous obtenons un nouvel état. Nous sauvegardons pour le mode de commande v1 le

couple (e, v) par l'intermédiaire de la fonction transitions - successeurs (lignes 11 et 12).

Cette fonction définit l'ensemble de transitions successeurs d'un mode de commande

donné à partir desquelles l'état final de la propriété P peut Gtre atteint. Si l'état (vr, r:)

n'appartient pas à l'ensemble états_ à- tmiter alors il constitue un nouvel état à traiter

et il est ajouté à l'ensemble nouve- états_&-traiter (lignes 13---+15). Une fois que

1 Procédure timeqrec mditiai(~tafstafsOotroiter) 2 début

pour chaque (v, r.) de états-a-trui&r faire

r. + pdY(v . r . ) ; ri (v, rv) E ens~mbIe~dfof~~frmte's aiar s

eta&-à-trmt&r + éta&-li-frrai&r - {(y rv)} ; sinon

msembl e-états-traités + ensemble-irat s-trait& u ((& r,)} r finsi

si ( [hl ] C [[P.&rat_inidaL r, ]] etP.&lnt - Mb.al.v = V )

alms débnt

pmpn'été-wrn3ée + true ; états-d-fraiter t 0 ; si rogion_&bu-&e = O alars région-début-cycle = [[ r, ]] ;

finsi ri [[ r, ]] Q r é g i ~ n ~ é ~ ~ d g m p r i d t é ~ r é d e c e s ~ alors

v l e - ~ ~ n j é +fi= ; h P

fin finai

iïn faire

Figure 22: Procédure tirne-précondition

tous les états de l'ensemble états- à traiter sont traités, cet ensemble prend les Bléments

de l'ensemble nozlvels - états - &-traiter qui fera l'objet du paramGtre de la procédure

tirne - précondition (ligne 19).

Il1 si [[ r:]] définitune région de données non vide d a s

Figure 23: Procédure transit ion- précondit ion

Si tous les cycles définis par l'ensemble ensemble- cycles sont vérifiés alors il existe

un contrôleur. La procédure synthèse - contdleur (voir la figure 24) consiste à générer

le contrBleur ou les lois de commande relatives à dague cycle (ligne 3). Si à un mode

de commande donné, il existe plus qu'un événemeat alors l'arénement adéquat à ex&

cuter doix satisfaire la condition de saut qui lui est associé. Cette procedure accepte

comme pa,ram&tre d'entrée l'ensemble ensemble - cycles. Pour chaque propriété d'un cy-

cle (ligne 5), l'ensemble ensemble - modes - de - commande est initialisé par le mode de

commande de son état initial P.état - initia1.v (ligne 8). Chaque mode de commande

trait6 est mis dans l'ensemble ensemble- modes- de- commande- traités pour qu'il ne

soit pas traité une autre fois (ligne 22). Ainsi pour chaque mode de commande v de

ensemble modes- d e wmmande qui n'a pas été traité, nous parcourons toutes ses tran-

sitions successeurs (déjà calculées par la procédure transition - prkondition) (lignes

11--+14), si l'événement d'une transition est un événement contrôlable et il n'a pas fait

l'objet d'une loi de wmmande alors la fonction des lois de commande est mise à jour

(ligne 16-17). Le mode de commande successeur de v est ajouté à l'ensemble emem-

ble - modes_ de- commande pour qu'il soit traité à son tour (ligne 20). Chaque mode de

commande traité de ensemble - modes - de - commande est éliminé de cet ensemble (ligne

12).

Le programme principal (voir la figure 25) consiste d'abord à vérifier si tous les cy-

cles de l'ensemble ensemble - cycles sont vérifiés. Si un cycle n'est pas vé&é alors le

traitement représenté par les lignes (7-12) est forcé à terminer par le changement de

la valeur de la variable continu - synthèse à fdse en fonction d e la procédure vérifica-

tion - cycle. Ensuite, si une propriété ou un cycle n'a pas été vérifié alors il n'existe

pas un contrôleur (lignes 13 et 14). Dans le cas contraire, le contrôleur est généré (lignes

15-20).

Les entrées et les sorties du programme principal sont définies par :

Entrées

- Un automate hybride linéaire A-

- Un ensemble de cycles ensemble - cycles = (cyclei, cycle2, . .. , cydk}.

- Un ensemble d'événements incontrdlables Cu.

O Sortie

- .y lois de commande.

1 Procédure sgnthèse~contrôlenr(e);1~8mbZe~cyties) 2 Début

Pour chaque cycle de ensemble-&es faire Pour chaque P de cycle faire

Figure 24: Procédure synth&e-contrôleur

1 Programme principal 2 début

Figure 25: Programme principal

3.4 Conclusion

Dans ce chapitre nous avons présenté une méthode de vérification et nous l'avons

reformuk en un problème de synthèse. L'idée de base est d'exprimer des propriétés

d'accessibilité en logique ICTL de telle sorte qu'elles définissent des trajectoires qui for-

ment un ou plusieurs cycles afin cpe le procédé ne s'arrête jamais à un état. Un contrôleur

existe si tous les cycles sont verifiés et pour chacun de ces derniers, des lois de commande

sont générées.

L'algorithme de synthèse présenté dans ce chapitre permet la génération d'un con-

trôleur tel que si ce dernier est mis dans une boucle avec le système concerné, alors la

boucle satisfait des propriétés d'accessibiité exprimées en ICTL.

Un cycle est défini par un ensemble de propriétés d'accessibilité telles que si ces

dernières sont satisfaites, alors e h définissent des trajectoires qui peuvent former un

cycle. D'où, la vkrification d'un cycle revient d'abord à vérifier si toutes les propriétés

qui le définissent sont satisfaites ; ensuite, de vérifier si les trajectoires définies par les

propriétés peuvent former un cycle. Par exemple (voir la figure 26), soit deux propriétés

d'accessibilité à vérifier Pl et Pz telles que Pl = QI - 30a2 et P' = Q3 +

Les prédicats d'état ai, a*, a3 et a4 sont définis respectivement par (vl,r,,), (v4,rV4),

des rkgions de do~mées. Soit RI et R2 deux régions de données définies respectivement

par les formules 30a2 et 30iD4. Supposons que les deux régions de données R1 et R2 sont

incluses respectivement dans les régions de données définies par le prédicat d'état al et

par le prédicat d'état Q3, alors les propriétés Pl et Pz sont satisfaites. Soit tmjectoinz, et

trajectoire,, deux trajectoires qui vérifient respectivement les deux propriétés Pl et P2.

Ces deux trajectoires peuvent former un cycle si et seulement si,

1. la région de données déhie par la formule 30a4 est incluse dans la région de

données définie par le prédicat d'état de l'état b a l de la propriété Pl ;

2. la région de données définie par la formule est incluse dans la région de

données définie par le prédicat d'état de l'état final de la propriété Pz.

Si ces deux conditions sont satisfaites, alors Ies propriétés Pl et P2 d6finissent des

trajectoires qui peuvent former un cycle.

". tra~ectozre~ (Ps) \ -/

/' Figure 26: Définition d'un cycle

Cet algorithme génère un contr8leur si chaque ensemble de propriétés peut former un

cycle, alors il existe un contrôleur qui guide le comportement du système concerné afin

de respecter toutes les propriétés (propriétés d'accessibilité) qui lui sont imposées. Si une

propriété ou un cycle n'est pas v a & , alors il n'existe pas un contrôleur. Le contrôleur

généré est un contrôleur à commande forcée puisque le choix d'une action de commande

se fait en fonction de la condition de saut satisfaite, c'&-&-dire à un instant donné une

seule action de commande est tolkée.

Chapitre 4

Synthèse de contrôleur du système

de positionnement d'antennes

Dans ce chapitre nous appliquons fa procédure de synthèse présentée dans le chapitre

3 à un procédé physique. Le procedé auquel nous nous intéressons est le système de

positionnement d'antennes présenté dans le chapitre 2.

4.1 Définition des propriétés du procédé

Le système de positionnement d'antennes est mod6lisé sous forme d'un automate

hybride linéaire A ayant les composantes suivantes :

V = {lm known, idle, mm-ng-le f t , rnaving-right , g aod-position}

E = (el , e*, e3, e4, e5,es, e7, es) tel que el = (unknown, idle), en = (idle, unknown),

e3 = (idle, mouing-right) , e4 = (idle, good-position) , es = (idle, mouing-le f t ) , = (movzng-le f t , idle), e7 = (moving-right , idle) et es = (good-position, idle).

Jzlmp(unknmn, idle) = x3 = 15 A xk c; [O, 1801 A dj = O A xi = xl A z', = x4

L'ensemble d'événements Z = Cc U Cu tel que :

- Cc = {start-moving-le f t , start-maring-right , stop, set-gd-positza) définit

l'ensemble des événements contdables.

- Cu = { set-unknuwn , new-positionI set-new-position) définit l'ensemble des

événements incontrôlables.

Chaque événement est associé à une commutation de commande tel que :

Event(ei) = neur-position, Event(es) = set-unknuwn,

Event (e3) = start-maving-le f t, Event(e4) = set-go&-position,

Event (es) = start-mouing-ri&, Euent (es) = stop,

Event(e7) = stop et Euent(e8) = set-new-position.

La procédure de synthèse reçoit en entrée un ensemble de cycles, un automate hybride

linéaire A et un ensemble d'événements incontrSlables Cu. Chaque cycle est défini par

un ensemble de propriétés d'accessibilité.

Cette produre consiste d'abord, à vérifier si chaque ensemble de propriétés définit un

cycle. Cela revient à vérifier si toutes les propriétés définissent des trajectoires (propriétés

vérifiées), ensuite, à vérifier si ces trajectoires peuvent former un cycle (cycle vérifié).

L'obtention d'un cycle assure que chaque trajectoire qui y appartient est un préfixe d'une

autre trajectoire. Enfin, la procédure génère pour chaque cycle les lois de commande cor-

respondantes. Nous définisons trois cycles à verifier pour le système de positionnement

d'antenne. Si ces trois cycles sont vérifiés, dors un contrSleur est généré. Chaque

cycle est d e i par deux propriétés d'acoessibilitt5 à vériiîer, d'où ensemble cycles = - e dei Y c ~ d e 2 tel que '?del = {Pl 1 P2), cycle2 = {A P4) et c~de3 = {P5 Y PG}-

Le premier cycle (voir la figure 27 a) est défini par les deux propriétés Pl et Pz t e k que

Pl = ( u n k n m , x3 :3 15) -r 30(moving-le f t, x2 - xl > d / 2 ) et

f i = ( m * n g - l e f t , x2 - X I 2 d/2 ) -* 30 (unknown, x3 5 15).

Le deuxi&rne cycle (voir la figure 27 b) est d e par les propri6tés f i et P4 telles que

P3 = (unknuwn,x3 5 15) + 3Q(moving-right,x2 - x1 < -d/2) et

P4 = (mov~~ng-r ight , xz - x1 5 -d/2) --+ 30(unkn<wn7 x3 5 15).

Le troisième cycle (voir la figure 27 c) est déhi par les propriétés & et P6 telles que

P. = ( u n k n m n , x3 5 15) -r 3 0 (good-position, x3 5 2) et

P6 = (good-position, 23 < 2) 4 30(unknoum, x3 5 15).

4.2 Application de la procédure de synthèse

Dans cette partie, nous allons décrire d'une manière globale I'application de la procé-

dure de synthèse définie dans le chapitre 3 au syst5me de positionnement d'antennes.

L'application 6tape par étape de cette procédure est présentée en annexe A.

D'abord, le programme principal vérifie si tous les cycles cyclel, cyclen et cycle3 sont

vérifiés. Nous allons cornmenGer par le cyclel. Ce premier cycle est déh i par les deux

propriétés Pl et P2. La vMcation du cyclel consiste à vénfier si ces deux propriétés

sont satisfaites. Nous dons commencer par la propriété Pl telle que

Cette propriété est vérifiée si la r6gion de données définie par le prédicat d'état

( u n k n m n , 2 3 5 15) d e s a n t son état initial contient la région de données déf i e par

la formule 3 0 (maving - le f t ,x2 - xl 2 d/2 ) . Cet te derni&re calcule la région de données

à partir de laquelle la région de données déhie par le prédicat d'état (moving - le f t, x2 -

xl > 4 2 ) est accessible. Nous considérons que le prédicat d'ktat (moving -le f t , x2 -xl 3

d / 2 ) qui représente l'état final de la propri6té Pl comme un état de départ pou. lequel

nous appliquons la procédwe time - pnkondition et la procédure tnznsition_p&ondition.

Pour chaque nouvel état calculé par la procédure tirne-pmkondition, nous vérifions si la

Figure 27: Représentation des cycles

région de données qu'il d&&t est incluse dans la région de données (unknown, [[x3 5 1511)

définie par l'état initial de Pi. Si c'est le cas, alors la propriété Pl est vérifiée ; la rkgion

de données définie par le nouvel état et la région de données définie par l'état final de

Pi sont respectivement sauvegaxdées dans la variable région - début cycle et la variable -

*on- état-Mal-propnét<prédecesseur. Nous constatons qu'après certaines applica-

tions de la procédure tirne-précondition, il existe un état vérifiant l'état initial de Pl tel

que cet état est défini par le pr6dicat d'état (unknmn,x3 5 15). Alors nous conclu-

ons qu'il existe une trajectoire (trajectoirei) ou une exécution du procédé à partir des

états appartenant à la région de données dbfinie par l'état initial de Pi jusqu'aux états

appartenant à la rkgion de données définie par lY&tat final de Pl (voir la figure 28).

Figure 28: Cyclq

82

Une fois que la première propriété Pl est verifiée nous appliquons la même démarche

à la proprihté Pz telle que

P2 = (moving - le f t , xz - XI 2 d / 2 ) -t 30(unknoun, x3 5 15)

Après certaines applications de la procédure t h e - précondition, nous constatons qu'il

existe un état vérifiant Mat initial de P2 tel que cet état est défini par le prédicat

d'état (moving - le f t , x2 - xi 2 d/2) . A œ niveau, nous vérifions si la région de

données dêfinie par cet 6tat est incluse dans la région de données déhie par l'état &al

de la propriété & ( raion- état - final - proprikt& - prédecesseur) ce qui est le cas, dors la

trajectoire trajectoirel est un préfixe de la trajectoire définie par la propriété f i . Étant

donné que la propriété P2 est vérifiée, dors il existe une trajectoire (trajectoire2) ou une

exécution du procédé à partir des états appartenant à la région de données défmïe par

son état initial jusqu'aux états appartenant à la région de données définie par son état

hal (voir la figure 28). Enfin, nous vérifions si la région de données définie par l'état

final de la propriété P2 contient la région de données région- d é b u t cycle pour s'assurer

que les deux propriétés Pl et Pz peuvent former un cycle ce qui est le cas, alors le premier

cycle est vérifié.

Nous appliquons la même démarche aux deuxième et troisi&me cycles, nous constatons

que ces derniers sont v&ifiés. Une fois que tous les cycles sont vérifiés, nous générons les

lois de commande correspondantes. Cela revient à parcourir chaque trajectoire définie

par une propriété Pi à partir du mode de commande de son état initial jusqu7au mode de

commande de son état final par I'intermédiaire de la fonction transitions- successeurs ( ) . A chaque transition d'un mode commande à un autre, nous vériûons si cette transition

est étiquetée par un événement contrôlable. Si c'est le cas, alors la fonction des lois de

commande est mise à jour. Par exemple, considérons la propriété Pi. Il existe deux

transitions discrètes à partir du mode de wmmande unknown de son état initial jusqu'au

mode de commande moving-lefi de son état h a 1 (voir la figure 28). Ces deux transitions

sont respectivement étiquetées par l'événement nm-position et l'événement start-moving-

Zejt Ce dernier est un &&nement contrôlable, dors la fonction des lois de commande est

mise à jour l idle le) = s tart-moving-lefi) .

4.3 Stratégie de commande

Le tableau 1 présenté ci-dessous définit la stratégie de conunande du contrôleur

calculée par l'application de la procédure de synthèse présentée dans la section précédante.

TabIe 1: Stratégie de commande

I I - -

set-gd-position

Mode de commande idle

Si à un mode de commande, il d e plusieurs actions de commande alors le choix de

l'action de commande adéquate se fait en fonction de la satisfaction de la conditiori de

saut correspondante. L'implantation de cette stratégie par le logiciel MATLAB (version

4.0) de Mathworks donne le résultat illustré par la figure 29.

Cette figure montre l'évolution du comportement du procédé illustrée, par la courbe

désignant les positions courantes dans le temps. Nous remarquons que la courbe des

positions cibles est bornée par deux autres courbes qui déf%ssent la région des bonnes

positions des antennes par rapport aux positions cibles. En &et, lors de l'exécution du

procédé, le rdle du contrôleur est de ramener la position murante des antennes dans la

région des positions désirées ce que le montre la figure 29. Étant dom6 que la position

Actions de commande ~ ( v ) start-mming-le f t

start-rnoving-rig ht

Conditions de saut x3 = 2 A x 2 - x l > d l 2 x3 = 2 A 2 2 - XI < -d /2

courante est initialement à la valeur zéro, nous constatons une étape de transition avant

d'avoir cette position dans la région désirée.

temps

Figure 29: Simulation du comportement du système de positionnement d'antennes

4.4 Conclusion

Dans ce chapitre, nous avons appliqué la procédure de synthése présent& dans le

chapitre 3 à un système de positionnement d'antennes. Tous les cycles du procédé ont été

v&ifiés (voir annace A) ce qui implique qu'il existe un contr6leu.r permettant de guider

le comportement du procédé tout en respectant les contraintes exprimées en termes de

propriétés d'accessibilité. La figure 29 montre que le procédé se comporte correctement

par simulation.

Conclusion

Dans ce mémoire, nous nous sommes intéressés à la modélisation et à la synthése

de contrôleurs des systèmes hybrides linéaires. Nous avons appliqué la méthode de m-

délisation proposée par Henzinger [6]. Cette méthode consiste à modéliser un procédé

physique sous forme d'un automate hybride linéaire. Ce dernier impose des contraintes

de linéarité aussi bien sur la partie discrète que sur la partie continue.

Henzinger et al. [8] ont présenté un outil de veification nommé HYTECH. Cet outil

permet la vérification automatique et symbolique des systèmes embarqués. Cela revient

à définir des contraintes sur un procédé en termes de propriétés exprimées en langage de

description ICTL et de s'assurer que le procédé concerné vérifie ces dernières.

Dans le contexte de la théorie de contrôle, nous avons reformulé la procédure de

vérification HYTECH en une procédure de synthèse. Cette dernière consiste à déterminer

s'il existe un contrôleur permettant de guider le procédé tout au long d'un comportement

désirable spécifié en termes de contraintes.

La dérivation d'un contrôleur revient, d'abord, à exprimer des propriétés sur le

procédé, ensuite, à v M e r si ce dernier satisfait ces propriétés, enfin, si toutes les pro-

priétés sont satisfaites, alors un contrôleur est génér6.

Pou. que le procédk ne s7arr&te pas à un état donné, nous avons posé une condition

sur la spécification des propriétés telle que ces dernières doivent définir des trajectoires

qui peuvent former un ou plusieurs cycles.

Une premi5re faiblesse de ce travail est que la procédure de s y n t h k e t limitée à

la génkation de contrôleurs par rapport à des contraintes qui sont exprimées en termes

de propri6tés d'accessibilité. La prise en charge de propriétés de vivacité ou de sûreté

nécessite d'éviter des trajectoires incontrôlables qui conduisent à des situations ill6gales.

Dans ce cas, il faut introduire une procédure de retour arrière (backtmcking) qui empêche

ces situations en inhibant nécessairement des événements contrôlables. Une autre faib-

lesse consiste à ce que nous n'avons pas calculé le degré de complexité de l'algorithme de

synthèse,

Le travail entrepris dans ce mémoire peut être poursuivi dans au moins deux direc-

tions. Premièrement, de rendre la procédure de synthèse flexible pour des propriétés

de sûret6, de vivacité et de réponse temps born6. Deuxièniement, il serait intéressant

d'adapter cette procédure à la génération des contrôleurs répartis, dans ce cas, chaque

contraleur est doté d'une observation partielle du procédé à commander.

Annexe A

Danc cette partie du mémoire, nous présentons l'application étape par étape de la

procédure de synthèse définie dans le chapitre 3 au système de positionnement d'antennes

présenté dans le chapitre 2.

Programme principal

Continu - synthèse t- t r w

états-à - traiter t- 0

proprzoprzété-véri f zée t- f alse

cycle - vér i f ié c- tme

boucle tant que (ensable - cycles # 0 et catinu-synthèse = true) est vérifiée ***********************************************************************

1" cas

choix cyclel de ensemble-cycles ***********************************************************************

Vérification d u cyclel.

ensemble-cycles - ensemble - cycles - { cyde l ) = (cyde2, cycZe3)

appel p r o d u r e vbriflcation - cycle(cyclel)

région - début-cycle c- O

régiun-région-état - f inalqrcpiétégrédecesseur - O

boucle tant que (cycle # 0 et continu - synthèse = true) est vérifiée ***********************************************************************

Vérification de la propriété Pl du &el.

***********************************************************************

choix Pl de cycleI

cycle1 - wcle1 - {Pi} = {Pz)

appel procédure vérification - propri6t6(Pl)

ensemble états - traités c- 0

états-à-traiter - états - à - traiteru {(movzng-le f t , x2 -xi 2 d / 2 ) ) = {(maving-

Zef t , x2 - Xl 1 d / 2 ) ) ***********************************************************************

Nous vérifions si la région de données (moving-le f t , [[x2 - xl 2 d /2 ] ] ) déhie par

l'état final de la propriM f i est accessible à partir des états appartenant à la région de

données (unknmn, [[x3 5 1511) d4finie par l'état initial de la meme propriété.

***********************************************************************

boucle tant que (états-à-traiter # 0 ) est vbrifiée

appel procédure time - precondition(étut s-à-traiter )

pour chaque (v, r,) de états-à - traiter ************************************************************************

Cette boucle présente un seul cas : (v, r,) = (moving-le f t , x2 - XI 2 d / 2 ) . ************************************************************************

1" cas

(v, rv) = (nwuing-le f t , x2 - XI 2 d/2)

r, - pre"(m-ng-le f t , x2 - XI 2 d /2 ) = x2 - XI 2 d/2

ensemble-états - traités - e n s a b l e - états - traités U ((moving-le f t , x, - XI 2

d / 2 ) ) Retour B la procédure vérification - propribté

**** états - à - traiter = {(moving-Zef t , x2 - x1 2 d / 2 ) ) ***** boucle tant que (états-&-traiter # 0) est vérifiik

appel procédure transit ion - préoondition(états - à - traiter)

nmvels - états à traiter c- 0 - - **** états - à - traiter = {(maring-le f t , xi - xl 2 d / 2 ) ) ***** boucle tant que (états-à-traiter # 0) est v&-if& ***********************************************************************

Cette boucle présente un seul cas : (v, r,) = (moving-le f t , x2 - xl > d / 2 ) .

***********************************************************************

1" cas

choix (v, r,) = (muuing-le f t , xz - xi 2 d /2) de états - à - traiter

états - à - traiter - états - à - traiter - {(moving-left, x2 - el 2 d/2)} = 0

pour chaque e = (v' , moving-le f t)

***********************************************************************

Cette boucle présente un seul cas : es = ( idle, d n g - l e f t ) . ***********************************************************************

1" cas es = (idle, mming-le f t )

r: - pre"(moving-Zef t , x2 - XI 2 d/2) = (x3 = 2 A XQ - xi > d/2)

transitions-successeurs(idle) - transitions - successeu~s(id1e) U {(es, marikg-

Zef t ) )

nouvds - états - à - traiter - nouvels-états - à - traiter U {(idle, x3 = 2 A x2 - x1 >

d /2 ) ) = ((idle, x3 = 2 x2 - xl > d / 2 ) )

états - à - traiter - nuuvels - états - à - traiter = {(idle, xs = 2 A x2 - xi > d /2 ) )

Retour ii la procéàure vérification - propriété

appel procédure time - precondition(états - à-traiter)

pour chaque (v, ru) de états - à - traitet-

************************************************************************

Cette boucle présente un seul cas : (v,r,) = (idle,xs = 2 A x2 - xl > d / 2 ) .

************************************************************************

1" cas (v, 7;) = (idle, 23 = 2 h 22 - xl > d/2)

ru - pre42""e(idle,x3 = 2 A x2 - xl > d/2) = (x3 5 2 x2 - xl > d/2 )

ensemble - états - traités - ensemble - états - traités U {(idle, x.3 5 2 A x2 - XI 3

1 Retour à la procédure vérification - propriété

***** états - à - traiter = { ( i d l e , x ~ 5 2 h x2 - XI > d/2))*****

boucle tant que (états - à - traiter # 0) est v6riflée

appel procédure transition - précondit ion(états - à - traiter)

nmvels - états-à-traiter - 0 ***** états - à - traiter = ((idle, x3 5 2 A 22 - xl > d/2))*****

boucle tant que ( é t a t s à - traiter # 0) est v6rifiée *****+******************************************************************

Cette boucle présente un seul cas : (v, r,) = (idle, x3 5 2 A x2 - el > d/2).

************************************************************************ ler Cas

choix (v, r,) = (idle, x3 5 2 A x2 - xi > d/2) de états-à-traiter

états - à - traiter - états - à - traiter - {(idle, xs 5 2 A x2 - xl > d/2)) = 0

pour chaque e = (v', Mle)

Cet te boucle présente quatre cas : e E { ( u k n m , idle), (-ng-le f t , idle) , (good-

position, idle), (muuing-right , idle) }. ************************************************************************

1" cas

el = ( u n k m w n , idle)

1: - preC.e(idle,x3 5 2 2 x2 - xi > d/2) = (x3 = 15 A x2 - XI > d / 2 )

t r a n s i t i a s - successeurs(u7lknown) + transitions - successeurs(unknown) U {(el

, idle))

nmels-états-à-traiter - nouvels-états - à - traiter U {(unknown, x3 = 15 A xz

-xi > 4 2 ) )

2i- cas

es = (maring-le f t , idle)

+ p r e p ( i d l e , x 3 : 3 2 / \ x 2 -xl > d / 2 ) = (x2 -xl > d / 2 h x 2 -xl 5 d/2) = O

******* r' v définit une région de données vide *********** 3- cas

boucle tant que (états-à-traiter # 0) est vbrifiée

appel procédure time - precondition(états à-traiter) - pour chaque (u, r,) de états à traiter - - ************************************************************************

Cette boude présente un seul cas : ( u n k n o w n , ~ ~ = 15 A 2 2 - 2 1 > d/2 ) . ************************************************************************

1" cas

(u, r,) = (unknown, x3 = 15 A 2 2 - xi > d/2 )

r, - pre"e(unknown, x3 = 15 A 1 2 - XI > d/2 ) = (x3 < 15 A x2 - XI > d / 2 )

ensemble - états - traités +- nsemble-états traités U { ( u n k n m , x3 5 15 Ax2 - xl - > d / W ************************************************************************

A ce niveau la propriété Pl est vérifiée car la région de données (unknoun, [[x3 5 1511)

de son état initial contient la nouvelle région de données définie par le prédicat d'état

( u n k n w n , x3 5 15 A x2 - XI > d /2 ) .

************************************************************************

propriété - véri f iée c- true

états à traiter c- 0 - -

Puisque Pi est vérifiée alors la région de données du début du cycle cyclei est celle

de la nouvelle région qui vérifie la région de données de son état initial.

************************************************************************ région - début-cycle - [[x3 5 15 A x 2 - xi > d/2]]

retour B l a procédure v6rification - propriété

***** ktats-à-traiter = 0 ***** boucle tant que (états-à-traiter # 0 ) n'est plus v&riAée

************************************************************************

Sauvegarde de la région de données définie par l'état final de Pl, pour vérifier si elle

contient la région de données qui satisfait sa propriété successeur-

************************************************************************

r é g i a - état - f ltaalqropriétégrédecesseur - [[x2 - xi 2 d / 2 ] ]

Retour h la procédure ~Qri f l ca t ion - cycle

boucle tant que (cycle # 0 et catinu-synthèse = true) est vérifiée ************************************************************************

Vérification de la propriété P2 du cyclel.

************************************************************************

choix Pz de cyclel

cyclel - cycle1 - (P2) = 0

appel procédure vérification - propriét8(P2)

ensemble-états-traités - 0 états - à - traiter - états - à - traiter U ((unknourn, xs 5 15)) = {(zmknown, XJ 5

15) ) ************************************************************************

Nous dons vérifier si la région de données (unknown, [[x3 5 1511) définie par l'état

h a 1 de la propriéte P2 est accessible à partir des états appartenant à la région de données

(moving-le f t , [[x2 - xl 2 d/2 ] ] ) défiliie par l'état initial de la même propriété.

************************************************************************

***** états - à - traiter = {(unknoun, xr 5 15))*****

boucle tant que (états-à-traiter # 0 ) est v6rifiêe

appel procédure time - precondition(états-à - traiter)

p o u . chaque (v,r,) de états - à - traiter ************************************************************************ Cette boucle présente un seul cas : (v,r,) = (unknown,~~ ( 15).

******************+*****************************************************

1" cas

( v , ru) = (unknovn, x3 5 1 5 )

rv - p r e ~ ( u n k n o w n , x3 5 15) = (x3 5 15)

ensemble - états - traités + ensemble - états - traités iJ { (unknown, x3 5 15))

Retour & la procédure v4rification - propriété

***** états - à - traiter = { ( u n k n m , x3 5 15)} ***** boucle tant que (états - &-traiter # 0 ) est verifiée

appel prooédure t ransi t ion - précondit ion(états - à - traiter )

nozlvels - états - &-traiter *-- 0

***** états - à-traiter = C(unknwn, x3 5 15)) ***** boucle tant que (états-à-traiter # 0) est vbrifiée

************************************************************************ Cette boucle présente un seul cas : (v, r,) = (unknozun, x3 5 15). ************************************************************************

1" cas choix (v , ru) = (unkncnun, 23 5 15) de états - à - traiter

états - à - traiter - états à - traiter - {(unknown, x3 5 15)) = 0

pour chaque e = (v', unknown) ************************************************************************

Cette boucle présente un seul cas : e2 = (idle, unknown).

************************************************************************

1" cas e? = (idle, u k n m )

rv - preF(unknown, x3 5 15) = (2.4 = 1 A x3 = 2)

transit tas - successears(idle) - transitions - successeurs (idle) U { (e2 , unkn+

wn) 1 nouvels - états - à - traiter - nuuvels-états - à-traiter U ((idle,x4 = 1 A x3 = 2))

= ((idle, xd = 1 A x3 = 2))

états - à - traiter - nuuvels-états-àtraiter = {(idle, x4 = 1 A x3 = 2 ) )

Retour h la procédure v6rification - propriété

appel procédure time - precondition(états-à - traiter)

pour chaque (v , r,) de états-à - traiter ************************************************************************ Cette boude présente un seul cas : ( v , ru) = (zdle, x4 = 1 A xs = 2) .

************************************************************************

ler Cas

(v, T,,) = (idle, x4 = 1 A xs = 2 )

r, -pre"( id le ,x4 = 1 A x 3 =2) = (sJ 5 2 h x 4 = 1)

ensemble - états - traités +- ensemble - états - traités li {(idle, x3 5 2 A x4 = l)}

Retour ii la procédure vérification - propriéte

***** états - à - traiter = {(idle, x3 5 2 A x4 = 1) ) ***** boucle tant que (états-à - traiter # 0 ) est vbrifiée

appel procédure transition - précondition(états-à-traiter)

nouvels-états-à-traiter - 0 ***** états - à - traiter = {(idle, x3 < 2 h x4 = 1) ) ***** boucle tant que (états-à - traiter # 0 ) est vériflée ************************************************************************

Cette boucle présente un seul cas : (u, ru) = (idle, x3 5 2 2h x* = 1).

************************************************************************

1" cas choix (v, Y,,) = (idle, x3 5 2 h x4 = 1) de états-à-traiter

états-à-traiter - états-à-traiter - {(v, ru) = (idle, x3 5 2 A x4 = 1)) = 0

pour chaque e = (ut, idle) ************************************************************************

Cette boucle présente quatre cas : e E ((unknoum, idle), (moving-le f t , idle), (good-

pos i t ia , i d e ) , (mming -right , idle) } . ************************************************************************

1" cas

el = ( u n k n m , idle)

6 -pre"(idle,xa _( 2 hx4 = 1) = 0

******* r' definit une région de données vide ***IC******* v

2- cas es = (mming-le f t , idle)

< t pre,"'(idle, x3 5 2 A x4 = 1) = (x2 - X I = d/2)

transitions - successeu~s(mouing-le f t ) +- transitions successeurs(moving-le f t ) - u {(es, idle) 3 m v e l s - états-à-traiter - nouvels - états-à - traiterU{(movihg-left,xz-XI =

d/2) 1 3iè7ne

es = (good-position, idle)

< - p r e ~ ( Z d l e y x 3 < 2 ~ x 4 = 1 ) = ( - d / 2 ~ x 2 - x r ~ x z - x i ~ d / 2 ~ x 3 = 2 ) transitions - successeurs(good-positim) - transitions - successeurs(gOOCE-positi- on) u {(es, idle))

nouvels - états - à - traiter c nouvels états à traiter U {(goai-positiony -d/2 i - - - - X Z - X ~ ~ X ~ - Z ~ < d / 2 h x 3 = 2 ) }

W c a s

e7 = (movéng-rig ht , idle)

< + pet,-(idle,q 5 2 h x4 = 1) = (x2 - XI = -d /2 )

transzt ims - successeurs(mav2ng-right) +- transitions - successeurs(mming-rig-

ht) U {(eT, idle))

nouvels - états-&-traiter - notlvels - états - à-traiter~{(mauing-right,x2-x1 =

-dl21 1 Retour A la procédure v6riRcation - propribté

***** états - à - traiter = {(moving-right,x* -xl = -d/2), ( gd -pos i t i on , -d /2 5

xz - 11 A x2 - x1 5 d / 2 A x3 = 21, (moving-le ft, x2 - x1 = d / 2 ) ) ***** boucle tant que (é tats - &-traiter # 0 ) est v6riAée

appel procédure t ime - precondit ion(état s - à - traiter)

pour chaque (v, ru) de états - à - traiter

Cette boucle présente trois cas : ( v , rV ) E {(maving-right , 2 2 - ri = -d /2), (goad-

position, -dl2 < 2 2 - XI A x2 - x1 d / 2 A x3 = 21, (mowing-left, x2 - XI = d /2 ) ) . *********************************************************************** 1" cas (V , rv) = (mming-r ight , x2 - xl = -d/2)

ru - preF(rnoving-right ,x2 - xl = -d/2) = (x2 - xl 5 -d/2)

ensemble - états - t rai tés +- ensemble - états - traités u {(moving-right,x2 - XI

- d m ) 2- cas

(v, r") = (goad-position, -d l2 5 x2 - xi A x2 - xl 5 d / 2 A xs = 2 )

r, - p r e T ( g d - p o s i t i o n , -d l2 5 x2 - 11 A x2 - X I 5 d / 2 /\ x3 = 2) = (-dl2 5

x ~ - x ~ A x ~ - x ~ s d / 2 ~ ~ ~ < 2 )

ensemble - états - t rai tés - ensemble-états - traités U {(good-position, -dl2 - < xz

-XI A ~2 - XI < d / 2 A 23 5 2 ) ) 3 i h e cas

(v, ru) = (mming-le f t , 1 2 - x1 = d / 2 )

ru - pree(moving-Zef t , x2 - 11 = d / 2 ) = (x2 - x1 1 d /2 )

ensemble - états - tra2tés - ensemble-états - traités u {(maving-Zef t , x2 - XI 2

dl21 1

A ce niveau la propriété f i est vérifiée car la région de données définie par le prBdicat

d'état (moving-left, x2 - XI 2 d / 2 ) de son état initial contient la nouvelle région de

données (moving-le f t , [[x2 - XI > d /2 ] ] ) .

*********************************************************************** propriété - vérifiée t- true

états à traiter +- 0 - -

[[r,,]] C région-état - f i na l_propr ié té~ecesseur , c'est-à-dire que la trajectoire

définie par la propriété précédate peut etre un préfixe de la trajectoire définie par la

propriété courante,

************************************************************************

retour A la procédure v6rification - propribt6 ***** états - &-traiter = $ ***** boucle tant que (états - à-traiter # 0 ) n'est plus vérifiée ************************************************************************

Sauvegarde de la région de données déhie par l'ktat final de Pz, pour vérifier si elle

contient la région de données qui satisfait sa propriété successeur.

************************************************************************

région-état - finalqropriétéqrédecessevr - [[x2 - XI 2 d/2] ]

Retour B la prodidure vérification - cycle boucle tant que (cycle # 0 et continu-synthèse = true) n'est plus vérifiée ************************************************************************ A ce niveau, la condition de la procèdure vérification - cycle (continu-synthèse =

true et région - début - cyde c région - état - f inalqropn'été~édecesseur) est satis-

faite, alors cyclei est vénfié.

************************************************************************

retour au programme principal

boucle tant que (ensemble-cycles # 0 et continu - synthèse = true) est v6rifiée

2- cas

choix cycle2 de ensemble-cycles

************************************************************************ ************************************************************************ Vérification du cycle2. ************************************************************************

ensemble - cycles - ensemble - cycles - {cycle2} = {cycles)

appel produre v&iAcat ion - cycle(cycle2)

r é g i a - début - cycle t- O

région-état - f inalqropriétéqrédecesseur - O

boucle tant que (cycle # 0 et catinu - synthèse = true) est v&riflée

***********************************************************************

Vaification de la propriété P3 du cycle2. ***********************************************************************

choix P3 de cycle2

wde2 - cycle2 - (P3) = (P4)

appel procédure vérification - propriét&(P3)

ensemble-états - traités - 0 états - à - traiter - états-à-traiter U {(motring-right, 2 2 - XI 5 - d / 2 ) ) ************************************************************************

Nous allons vérifier si la région de données (moving-right, [[x2 - xi 5 -d/2]]) définie

par l'état &al de la propriété P3 est accessible à partir des états appartenant à la région

de données (unkncwn, [[x3 5 1511) définie par l'état initial de la même propriété.

************************************************************************

***** états - à - traiter = {(moving-right,x2 - xi 5 -d /2 ) ) ***** boucle tant que (étnts-à-traiter # 0) est vérifiée

appel procédure time - premndition(états - à - traiter)

pour chaque (v, rv) de états-&-traiter

************************************************************************

Cette boucle présente un seul cas : (u, r,) = (moving-right, x2 - XI 5 -d/2) . ************************%***********************************************

1" cas

(u7 rv) = (mming-right, x2 - XI < -d/2)

rv - pt-e~ue(mcnring-right,x2 - XI 5 -d/2) = (x2 - xl 5 - d / 2 )

ensemble - états - traités - ensemble - états - traités U {(mmhg-right , xz - xi 5

-W) ) Retour à la procédure v&rification - propriét4i

***** états - à - traiter = {(moving-right, x2 - XI 5 - d / 2 ) } ***** boucle tant que (états-à-traiter # 0) est v&ifiée

appel procédure transition - précondition(états - à - traiter)

nmuels-états - à - traiter + 0

***** états - à - traiter = {(mov2ng-right7 x2 - xl $ - d / 2 ) ) ***** boucle tant que (états - à-traiter # 0) est v&riAée ************************************************************************

Cette boude présente un seul cas : (u,r,) = (moving-right, x2 - XI -d /2 ) .

************************************************************************

ler Cas choix (v, rv) = (rnoving-right, x2 - x1 < - d / 2 ) de itats-à-traiter

états-à - traiter - états-à-traiter - {(mming-right, 2 2 - xi 5 - d / 2 ) ) = 0

pour chaque e = (d , moving-réght) ........................................................................

Cette boucle présente un seul cas : e3 = (idle, mming-right) . ************************************************************************ 1" Cas

transitions - successeurs (id1 e) +-- transitions - successeurs(id1e) U {(e3, m i n g -

right) 1 nmvds - états - à-traiter - nouvels états à traiter U {(idle, x3 = 2 A x2 - x1 < - - - 4 1 2 ) 1 états - à - traiter - notrvels - états - à - traiter = {(idle, x3 = 2 A x2 - xl < -d/2))

Retour z3 la procédure v6riAcation - propri6t8

appel procédure tirne - precondition(états-à-traiter) pour chaque (v, ru) de états - à - traiter

************************************************************************

Cette boucle présente un seul cas : (a, ru) = (id1 e, x3 = 2 A xz - xl < -d /2). ************************************************************************

1" cas (v, r,) = (idle, x3 = 2 2 2 - XI < -d/2)

1; - preF(idle,x3 = 2 A 2 2 - XI < -d/2) = (x3 5 2 r\ 2 2 - x1 < -d /2 )

ensemble - états - traités - ensemble - états-traités U {(idle, x3 5 2 A x2 - xl c

4 / 2 1 1 Retour B la procédure v6riAcation - propribtb

***** états-&-traiter = {(idle, x3 2 2 x2 - X I < -d/2)) ***** boucle tant que (états-à-traiter # 0 ) est vérifiée

appel procédure transition - précondition(états-à - traiter)

nmvels-états-à-traiter - 0 ***** états - à - traiter = {(idle, x3 5 2 2 x2 - XI c -d/2)} *****

boude tant que (états - &-traiter # 0 ) est vérifiée ***********************************************************************

Cette boucleprésenteunseulcas : (v,r,) = (idle7x3 5 2 A g - x i < -d/2).

***********************************************************************

1" cas

choix (v, r,) = (idle, 2.3 5 2 A x2 - x1 < -d /2) de états à traiter - - états - &-traiter - états - &-traiter - {(idle, xs 5 2 A x2 - XI < - d / 2 ) ) = 0

pour chaque e = (d , idle) ***********************************************************************

Cette boucle présente quatre cas : e E {(unknwn,idle), (m0zlzmOZlZng-left,idle), (good-

position, idle), (rnovzng-right , idle)).

***********************************************************************

el = (unknwn,idle)

< - preF(idle, 2 3 5 2 A x2 - X I < -d/2) = (x3 = 15 A x2 - zi < -d/2)

transitions - successeurs(unknown) + transitzms - successeurs(unknown) U {(el

, idle))

nmvels-états - à - traiter - nouvels - états-à - traiter u { (unknmn, x3 = 15 A x2

-11 < -d/2))

Zkne cas

es = (gd-position, i d e )

Sv - pre,"'(idle,x3 5 2 A x2 - XI < - d / 2 ) = 0

******* rk définit une région de d o n n h vide ***********

Pe C a s

e~ = (rnming-~ig ht , idle)

t pre"(idle,xs 5 2 A xz - XI < -d/2) = 0

******* < déiinit une région de données vide *********** états-à-traiter - nouvels - états - à - traiter = {(unkncnun, x3 = 15 A 2 2 - xl <

-dl21 1 1 Retour à la procédure v&rifkation - propriete

***** états - à - traiter = {(unknmn, x3 = 15 A x2 - xi < - d / 2 ) ) ***** boucle tant que (états - à - traiter # 0 ) est vérifiée

appel procédure t ime - precondit ion(ét at s -à-t rait er )

pour chaque (v, ru) de états-à-traiter

***********************************************************************

Cette boucle présente un seul cas : (v, r,) = ( u n k n m , 23 = 15 A x2 - XI < -d/2). ***********************************************************************

le+ C a s

(v,r,) = (unknown,~~ = 15 A xl - xi < -d/2)

r, +- pre"(unknoum,x3 = 15 A xz - XI < 4 2 ) = (x3 5 15 A x2 - XI < 4 2 )

ensemble - états - traités + ensemble-états-traités U {(unknown, x3 5 15 A x2-

xi -= -d/2)} ***********************************************************************

A ce niveau la propriété P3 est vérifiée car la région de données (unknmn, [[x3 5 1511)

de son état initial contient la nouvelle région de donnée définie par le prédicat d'état

(unknuwn, x3 5 15 A x2 - X I < -d/2).

************************************************************************ propriété - vérifiée t- true

états-à-trazter - 0 ************************************************************************

Puisque P3 est vérifiée alors la région du début du cyclel est celle de la nouvelle région

qui vérifie la r6gion de données de son état initial.

************************************************************************ région - début - cyde - [[x3 5 15 A x2 - xl < -dl211

retour & la procédure v&rification - propri6té

***** états à traiter = 0 ***** - - boucle tant que (états - à-traiter # 0 ) n'est plus v&rifiée ***************-*********************************************************

Sauvegarde de la région de données de l'état final de 5, pour vérifier si elle contient

la région de données qui satisfait sa propri6té successeur.

************************************************************************

région-état - f inalqrapriétéprédecesseur - [[x2 - 11 5 -dl211

Retour à la procédure vérification - cycle

boucle tant que (cycle # 0 et continu - synthèse = true) est vériftée ************************************************************************

V-cation de la propriété P4 du cycle2.

************************************************************************

choix P4 de cycle2

cycle2 +- q d e 2 - {P4) = 0 appel procédure vérification - propriété(P4)

ensemble - états traités t- 0 - états - à - traiter c états - à - traiter U {(unknown, xs < 15)) = {(unknown, x3 5

NOUS dons veifier si la région de donn6es (unknwn, [[x3 1511) définie par I'état

final de la propriété P4 est accessible à partir des 6tats appartenant à la région de données

(moving-nght, [[xz - xi 5 4/21]) définie par l'état initial de la même propriété.

**'** états-&-traiter = {(unknoum, x3 5 15) ) ***** boucle tant que (états - &-traiter # 0) est vérifiée

appel procédure time - precondition(états - à - traiter)

pour chaque (v,ru) de états - à - traiter f*************S*********************************************************

Cette boude présente un seul cas : (v, r,) = (zmknown, xs < 15). ************************************************************************

ler Cas (v, r,) = (unknown, x3 5 15)

r, - p r e ~ ( u n k n m u n , x3 5 15) = (x3 5 15)

ensemble-états - traités - ensemble - états - traités u ((unknolun, xs 5 15))

Retour A la procédure véritlcation - propriété

***** états - à - traiter = {(unknown, x3 5 15)) ***** boucle tant que (états - à - traiter # 0 ) est vérifiée

appel proœdure transit ion - précondition(états - à-traiter)

nouvels-états - à - traiter t 0

***** états - à - traiter = {(unknown, x3 5 15) ) ***** boucle tant que (états - à - traiter # 0 ) est v6riûée

Cette boucle présente un seul cas : (v,ru) = ( îmknovn, x3 5 15) .

************************************************************************

lW cas

choix (v, r,) = (unknoum, x3 5 15) de états-à-traiter

états - à - traiter - états - à - traiter - {(unknown, 353 5 15)) = 0

pour chaque e = (a', u n k n m )

************************************************************************

Cette boucle présente un seul cas : ea = (idle, unknawn).

************************************************************************

1" cas

e2 = (idle,unknoun)

6 + prep(unknown, xs 5 15) = (x4 = 1 A xs = 2)

transitions - successeurs(idle) - transitions - successeurs(idle) U {(e2, unkn*

wn)

nouvels - états - à - traiter + nouvels états à traiter u { (idle, 2 4 = 1 A xzg = 2 ) ) - - - = {(idle, x4 = 1 A x3 = 2))

états - à - traiter - nouvels - états - à - traiter = {(Zdle,x4 = 1 A33 = 2 ) )

Retour i!i la procédure vérifkation - propriét6

appel procédure time - precondition(état s - à - traiter )

pour chaque (v, r,) de états - à - traiter

************************************************************************

Cette boucle présente un seul cas : (v, r,) = (idle, z4 = 1 A z 3 = 2) .

************************************************************************

ler Cas

(v, ru) = (idle,x4 = 1 A x3 = 2) - preFe(idle, x4 = 1 A x3 = 2) = (x3 5 2 h x4 = 1)

ensemble - états traités c ensemble - états - traités U {(idle, x3 5 2 2 x4 = 1))

Retour ii la procédure vérification - propri&t&

***** états-à - traiter = {(idle, x3 5 2 x4 = 1)) ***** boucle tant que (états - à - traiter # 0 ) est vériAée

appel procédure transition - précondition(états-&-traiter) nouuels - états - à - traiter c- 0

***** états-à - traiter = {(idle, x3 5 2 A x~ = 1 ) ) ***** boucle tant que (états - à - traiter # 0 ) est vbrifiée

Cette boucle présente un seul cas : (v, ru) = (idle, x3 5 2 2 x4 = 1)-

*******************************************.*****************************

1" cas

choix (v, ru) = (idle, x3 _< 2 A x4 = 1) de états - à - traiter

états - Ù - traiter - états - à - traiter - {(u, ru) = (idle, x3 5 2 A x4 = 1 ) ) = 0

pour chaque e = (d , idle) ........................................................................ Cette boucle présente quatre cas : e E ( (unknoun, idle), (main-ng-le f t , idle), ( g d -

positia, idle), (moving-right , idle) }. ........................................................................

1- cas

el = (unknown,idle)

r: - preLm(idle, x3 5 2 r\ x4 = 1) = 0

******* < définit une région de données vide *********** 2- cas

e7 = (mouing-~ig ht , idle) - pre~e(zdle , x3 j 2 xd = 1) = (x2 - XI = -d /2)

transitions - successeurs(moving-right) - transitims-successezlr~ (rnoving-rig-

ht) u {(e7, idle))

3ihe cas

es = (moving-le f t , idle)

7: - prey(idle , x3 5 2 A x.4 = 1) = ( 2 2 - sl = d / 2 )

transitias-successeurs(mming-le f t ) - transitions - successeurs(moving-le f t )

~ { ( e a , idle))

nouvels-états - à - traiter c nouvels-états-à-traiter U { (mouing-le f t , x2 - xi =

d/2)

&- cas es = (good-position, tdle)

< - preL-(idZer x3 5 2 A x4 = 1) = ( -dl2 5 x 2 - X I ci x2 - xi 5 d / 2 A x3 = 2)

transitions - successeurs (good-position) - transitions - successeurs(go0d-positi-

m) u {(es, idle)}

nouvels-états-à-traiter + novvels - états - à traiter U {(good-position, -dl2 _<

x ~ - x ~ A x ~ - x ~ s d / 2 ~ ~ ~ = 2 ) )

Retour à la procédure v&iAcation - propriété

***** états-à-traiter = ((mov2ng-right, xz - cl = -d /2 ) , (maring-le f t , x2 - xl =

d/2), (go&-position, -d/2 5 xt - XI A x2 - XI 5 d/2 fr x3 = 2)) ***** boucle tant que (états - à-traiter # 0 ) est vérfiée

appel procédure time - precondit ion(état s - à - traiter)

pour chaque (v, r,) de états - à - traiter

************************************************************************

Cette boucle prknte trois cas : (v, ru) = {(mwing-right , xz -xi = -d/2), (moving-

le f t , x 2 - 11 = d/2), (good-position, -d l2 5 x 2 - X I A x 2 - X I 5 d/2 A x3 = 2)).

Nous commençons par le premier élément de cet ensemble. Nous obtenons le même

résultat si nous commençons par n'importe quel autre élément.

************************************************************************

let cas

(v, ru) = ( m ~ ~ ~ Z ? ~ g - ~ i g h t , 5 - xi = -d/2)

rv - preF(moving-right, x2 - XI = -d /2 ) = (x2 - XI 5 - d / 2 )

ensemble - états - traités - ensemble - états - traités U {(moving-right, 2 2 - 11 5

4 / 2 1 1

A ce niveau la propriété P4 est vérifiée car La région de données définie par le prédicat

d'état (moving-right, x2 - XI 5 -d/2) de son état initial contient la région de données

propriété - véri f Ge t- true

états-à-traiter - 0 ***************************************************************%********

[ [ T ~ ] ] C région-état- f ina lp ropr i é t é~édeces seur , c'est-à-dire que la trajectoire

définie par la. propriété précédante peut être un préfixe de la trajectoire définie par la

retour à la procédure vérification - propriété

***** états à traiter = 0 ***** - - boucle tant que (états - h - traiter # 0 ) n'est plus vérifiée ************************************************************************

Sauvegarde de la région de données de l'état final de P4, pour vérifier si elle contient

la région de données qui satisfait sa propriété successeur.

************************************************************************

région-état - f inalqropriétégrédecesseur - [[x2 - xi 5 -d/2]]

Retour à la procédure v6riftcation - cycle

boucle tant que (cycle # 0 et umtinu - synthèse = t m e ) n'est plus v6riAée ************************************************************************

A ce niveau, la condition de la proœdure vérification - cycle (catinu-synthèse =

true et région - début - cycle C régian-état- f i na l~opr ié t éqrédecesseur ) est satis

faite, alors cyclez est vérifié.

************************************************************************ retour au programme principal

boucle tant que (ensemble-cycles # 0 et continu - synthèse = true) est v8riftée

3ihe cas

choix &es de ensemble - cycles ************************************************************************

Vérification du cycle3.

ensemble-cycles - ensemble - cycles - {cycle3) = 0

appel procédure vérification - cycle(cycle3)

région - début-cycle c- O

région-état- f ind_prqpr ié té~édecesseur - O

boucle tant que (cycle # 0 et continu - synthèse = t m e ) est vbrifiée

************************************************************************ Vérification de la propriété P5 du cycle3.

************************************************************************

choix P5 de cycle3

cycle3 + cycle3 - {P5) = (PG)

appel prooédure v6riAcation - propriété(P5)

ensemble - états-traités + 0

états-à-traiter - états-à-traiter U {(gd-posi t ion, x3 5 2 ) ) -. . -. -. . . . . . . . . . . . . . . . ,- .--. ,--, ,- .- ,--,-. . . . . . . . . . . . . . . . . . 7 . - . . . . . . . . . . . . . . . . . - . , . , .

Nous allons vQifier si la région de dom& (gd-posit ion, [[x3 5 211) définie par l'état

h a 1 de la propriété P5 est accessible à partir des états appartenant à la région de données

(unknown, [[x3 5 1511) définie par l'état initial de la même proprieté.

boucle tant que (états-à - traiter # 0) est v&iA&e

***** états - à - traiter = (good-position, xs 5 2) ***** appel procédure t ime - precondition(états-à-traiter)

pour chaque (v, r,) de étatsà-traiter

************************************************************************ Cette boucle présente un seul cas : (v , r,) = (g oud-positia, x3 < 2).

************************************************************************

1" cas

(v, T,) = (goad-position, x3 2) rv - p r e F ( g d - p o s i t i m , x3 5 2) = (x3 5 2)

ensemble - états - traités - ensemble états traités u {(good-position, x3 5 2 ) ) - Retour B la procédure v6riAcation - propri6té

***** états-à-traiter = {(good-position, x3 5 2 ) ) ***** boucle tant que (états - à-traiter # 0 ) est v6rifiée

appel procédure transition - précondition(états - &-traiter)

nmvels-états - à - traiter - 0 ***** états - à - traiter = ((gd-posit ion, x3 1 2 ) ) ***** boucle t an t que (états à traiter # 0 ) est vbrifiée - - ************************************************************************

Cette boucle présente un seul cas : ( v , rv) = (good-position, x3 5 2).

************************************************************************

1" cas

choix (v, T,) = (good-position, xs :3 2) de états - à - traiter

états-&-traiter +- états - à - traiter - {(good-position, x3 5 2 ) ) = 0

pour chaque e = (d , guod-position)

*+********************************************************************** Cette boucle présente un seul cas : er = (idle, gd-position).

************************************************************************

ler C a s

e4 = (idle, good-position)

- preF(g0od-position, x3 2) = (23 = 2 h x2 - 11 5 d / 2 h -dl2 5 x2 - xzi)

transitions - successeurs(idle) - transitions - successeurs(idle) u {(e4, good-posi-

t ia) }

nozlvels - états - à - traiter - nwuvels états à traiter u {(idle, xs = 2 A 2 2 -XI 5 - - - dl2 A -d/2 5 ~2 - x1)}

états - à - traiter - nuuvels - ét-ats à traiter = {(idle, x3 = 2 A x2 - XI 5 d / 2 ~ - - -dl2 5 x* - x1) 3 Retour à la procédure v6rification - propriété

appel procédure time - precomdition(états - à - traiter)

pour chaque (v, ru) de états - à - - - traiter *****************************=*******************************************

Cette boucle présente un seul cas : (v, T,) = (idle, x3 = 2 r\ x2 - XI 5 d / 2 A -d / 2 5

x 2 - 5 1 ) -

*****************************=******************************************* ler cas

(v, r,) = (idle, x3 = 2 A x2 - xi C d/2 A -dl2 5 2 2 - xi)

r , - p r e ~ ( i d l e , x 3 = 2 ~ x 2 - x l < d / 2 h - d / 2 < x 2 - x i ) = ( x 3 < 2 A x 2 - x &

d/2 A -d/2 5 ~2 - xl)

ensemble états-traités c- ensb-emble - états - truités U {(idle, x3 5 2 A x2 - xi 5

d/2 A -dl2 5 X* - x ~ ) )

Retour & la procédure v&riActation - propri&t&

***** états - à - traiter = {(idle,~1:3 5 2 A x2 - X I 5 d /2 A -d/2 5 x2 - x l ) ) ***** boucle tant que (états-à-traider # 0 ) est vérifiée

appel p r o d d u r e transition - précondition(états-à-traiter)

n m e l s - états - à-traiter - 0 ***** états - à - traiter = {(idle, r c 3 5 2 A x2 - xl 5 d/2 A -dl2 5 x2 - xI)) ***** boucle tant que (états-à-traiâfer # 0 ) est v6riAée

Cette boucle présente un seul cas : (v, r,) = (idle, xs 5 2 A x2 - XI 5 d /2 A -d /2 5

x2 - -1)- ************************************************************************

1" cas

choix (v , ru) = (idle, x3 < 2 A xt - XI 5 d / 2 -d/2 < z 2 - xI,) de états-à-traiter

états-&-traiter + états - à - traiter - ((idle, xs 1 2 A x2 - x, 5 d / 2 A -d /2 5 x2

-21)) = 0

pour chaque e = (v', idle)

************************************************************************ Cette boucle présente quatre cas : e E {(unknoum, idle), ( W n g - l e f t , idle), (good-

position, idle), (rnoving-right , zdle) ). ************************************************************************

el = (unknown, idle)

< +prep( id le ,x3 5 Z A X ~ - X ~ s d / 2 ~ - d / 2 5 x 2 - x i ) = (x3 = 1 5 ~ x ~ - x ~ 5

d / 2 A -d/2 5 ~2 - x,)

transitions - successezlrs (unknown) - transitions - successeurs (unknoum) ü {(el

, idle) )

nouvels-états - à + traiter - nmvels - états - à-traiter U {(unknownx3 = 15 A x2

-X I 5 d/2 A -d/2 5 ~2 - x1) )

F"": cas es = (rnoving-le f t , idle)

ci--pre"(idle,x3 < 2 A x 2 - x l < d / 2 ~ - d / 2 5 x ~ - x ~ ) = 0

******* TL définit une de dom- vide *********** 3 i h e - es = (good-position, id1 e)

e7 = (mming-rig ht , idle)

< -pre"(idle,x3 2 A x 2 - x l < d / 2 h -d/2 5 x 2 - x i ) = a ******* r' v définit une région de données vide *********** états - à-traiter - nouuels - états à traiter = {(unknopun, x3 = 15 A x2 - XI 5 - - d / 2 A -d /2 < 2 2 - 2 1 ) )

Retour B la procédure vérification - propriété

** états-&-traiter = { (mknown, xa = 15 A 1 2 - xi 5 d / 2 /\ -dl2 5 x2 - x i ) } ** boucle tant que (états-à-tra2ter # 0) est v6rifiée

appel procédure time - precondit ion(état s - ù - traiter)

pour chaque (v , r,) de états - à-traiter ************************************************************************

Cette boucle présente un seul cas : (v'r,) = (unknouin,x3 = 15 /\ x2 - xl 5 d / 2 A

-dl2 5 2 2 - X I ) .

************************************************************************

ler Cas

(v, ru) = (unknown, x3 = 15 x2 - xi 5 d / 2 A -d l2 5 x2 - xzi)

r, + pre"(unknourn, x3 = 15 A 2 2 - xl 5 d / 2 A -dl2 5 x2 - x i ) = (x3 5 15 A x2

-11 (- d / 2 A -d l2 < 22 - x,)

ensemble - états - traités - ensemble-états - traités li {(unknuwn, x3 5 15 A x2-

X I 5 d / 2 A -d l2 5 2 2 - x i ) ) ************************************************************************

A ce niveau la propriété Ps est vérifiée car la région de données définie par le prédicat

d'état d e son état initial (unknmn,x3 5 15) contient la nouvelle région de donnees

( u n k n w n , [[x3 15 A xz - xi < dl2 A -dl2 5 x2 - x l ] ] ) -

propriété - vérifiée c- true

états - à - traiter - 0 ************************************************************************

Puisque P5 est vérifiée alors la région du début du cycle cycle3 est celle de la nouvelle

région qui vérifie la région de données de son état initial.

************************************************************************

région - début - cycle - [[x3 5 15 A x, - xi 5 d / 2 -d /2 5 xz - XI]] retour B la procédure vérification - propriétb

***** états à traiter = 0 ***** - - boucle tant que (états-à - traiter # 0 ) n'est plus vérifiée

Sauvegarde de la région de données de l'état ha1 de Psi pour vérifier si elle contient

la région de données qui satisfait sa propriété successeur.

************************************************************************

région - état - f i d q r u p r i é t é ~ é d e c e s s e u r - [[x3 5 211 Retour à la procédure vérification - cycle

boucle tant que (cycle # 0 et continu - synthkse = true) est vériAée ************************************************************************

Vérification de la propriété P6 de cycle3. ************************************************************************

choix Ps de cycle3

cycle3 - cycle3 - {Pi) = 0

appel procédure vérification - propriété(P6)

ensemble - états - traités - 0

états-à-traiter - états-à-traiter U ((unknown, x3 5 15)) = {(unknmn, x3 5

15) )

Nous dons vérifier si la région de données (unknouin, [[x3 5 1511) définie par l'état

h a 1 de la propriété P6 est accessible à partir des états appartenant à la région de données

(god-position, [[x3 5 211) définie par l'état initial de la même propriété.

************************************************************************

***** états - à - traiter = {(unknown,x3 _< 1 5 ) ) ***** boucle tant que (états-à-traiter # 0) est vérifiée

appel procédure time - precondition(états - à - traiter)

pour chaque (v, r,) de états - à - traiter ************************************************************************

Cette boucle présente un seul cas : (v, ru) = (unknmn, x3 5 15). ************************************************************************

lm Cas

(v, ru) = (zmknoum,x3 5 15)

r, t pre"(unknoum, x3 5 15) = (x3 5 15)

ensemble-états-traités - ensemble - états - traités U {(unknoun, xa 5 1 5 ) )

Retour B la procédure v6rification - propriété

***** états - à - traiter = {(unknwn,xs 5 15) ) ***** boucle tant que (états-à-traiter # 0) est vérifiée

appel procédure transition - prêcondition(états - à-tr aiter)

nmvels - états - à - traiter t- 0

***** états - à-traiter = { ( u n k n m , x 3 5 1 5 ) ) ***** boucle tant que (états-à-traiter # 0 ) est verifMe ************************************************************************

Cette boucle présente un seul cas : (u, r,) = (unknmn, 23 5 15). ************************************************************************

choix (v,r,) = ( u n k o w n , x ~ 5 15) de états - à - traiter

états-à-traiter - états-à-traiter - {(unknwn,x3 5 15)) = 0

pour chaque e = (dl unknown)

************************************************************************

Cette boucle présente un seul cas : es = (idle, lmknoun).

************************************************************************

ler Cas

ea = (idle,unknovn)

r: - p r e ~ ( u n k n a u i n , x3 5 15) = (x4 = 1 x3 = 2)

transitions - successeurs (idle) - transitions~successeurs(idle) U {(e,, unkn*

wn) 1 nouvels-états-à-traiter + nouuels - états-à - traiter U {(idle, sr = 1 A x3 = 2 ) )

= {(idle, x4 = 1 A x3 = 2 ) )

états - à - traiter - nmuels - états - à - traiter = {(idle,x4 = 1 A x ~ = 2))

Retour A la procédure vérification - propriéte

appel procédure time - precondition(états - à - traiter)

pour chaque (u, ru) de états - à - traiter

************************************************************************

Cette boucle présente un seul cas : (v, r,) = (idle, x4 = 1 A x3 = 2).

************************************************************************ 1" cas

(v , r,) = (idle, z* = 1 A xs = 2)

r, - pre"(idle,x4 = 1 h x3 = 2) = (x3 5 2 A x4 = 1)

ensemble - états - traités - ensemble-états-traités u {(idle, x3 5 2 A x4 = l)}

Retour à la procédure vérification - propriétê

***** états - à - traiter = ((idle,x3 2 A x4 = 1)) ***** boucle tant que (états-à-traiter # 0) est vérifiée

appel procédure transition - précondition(6tats - à - traiter)

nwuvds - états - à-traiter +- 0

***** états - à - traiter = {(idle, x3 5 2 A x4 = l)} ***** boucle tant que (états-à-traiter # 0 ) est vbrifiée ************************************************************************

Cette boucle présente un seul cas : (v, r,) = (idle, x3 5 2 A x4 = 1). ************************************************************************

1" cas choix (v , r , ) = (idle,x3 < 2 A x ~ = 1) de états - à - traiter

états - à - traiter - états - à - traiter - {(v, T ~ ) = (idle, x3 5 2 2h x4 = 1)) = 0

pour chaque e = (v', idle)

Cette boude présente quatre cas : e E {(unknoum, idle), (go&-position, idle) , (mov-

ing-le f t , idle), (good-posit ia, idle), (moving-right , id1 e) ). ************************************************************************

1" cas

el = (unknown, idle)

< - p r e F ( i d l e , x 3 5 W x 4 = 1) = @

******* fl dkfkiit une région de donn- vide *********** V

2- cas

es = (good-position, idle)

< - pre"(idle, x3 5 2 /\ x4 = 1) = ( -dl2 5 q - XI A x2 - XI 5 d / 2 A 2 3 = 2 )

transitions - successeurs(gd-position) c transitias-successeurs(gOOd-psiti-

04 u {@a, idle) 1 nouvels-états - à - traiter - m v e l s - états-&-traiter U {(good-position, -d l2

~2 - X I A ~2 - XI 5 d / 2 A x3 = 2 ) ) 3ième

e~ = (mming-right , idle)

1: - pre"(idle,x3 5 2 A x4 = 1) = (x2 - XI = -d/2)

transitions - successeurs (moving-rig ht) - transitions successeurs (moving-rig- - ht) U { ( e ~ , idle)}

4'"": cas

ea = (moving-te f t , idle) - pre"(idte, x3 5 2 A x4 = 1 ) = (x2 - xl = d/2)

transitCons - successeu~s(moving-le f t ) - transitions - s u c c e s s e u r s ( ~ n g - l e f t )

u { (e, , idle) )

nouvels - états - à - traiter - nuuvels états à-traiter u {(moving-le f t , x2 - xl = - - dl21

Retour A la procédure v6riAcation - propriétb

***** états - à - traiter = {(goal-position, -dl2 5 x2 - XI xz - z l < d/2 A x3 = 21,

(moving-right, x2 - xl = -d /2) , (moving-le f t , xz - xl = d / 2 ) } *-** boucle tant que (états-à-traiter # 0 ) est v6riAée

appel procédure t ime - precondition(état s-à-traiter)

pour chaque (v , r,) de états - à - traiter

************************************************************************

Cette boucle présente trois cas : (v, ru) = {(gd-posi t ion, -d/2 5 s 2 - xi ri x2 -xi < d / 2 A x3 = 2), (moving-right, x2 - X I = -d/2) , (rnovtng-le ft,x2 - xl = d /2 ) ) .

************************************************************************

ler Cas

(v, ru) = (good-position, -d/2 5 x2 - xl A xz - xi 5 d / 2 A x3 = 2 )

r, - pre"(gd-position, -dl2 5 x2 - xl h x2 - x1 5 d/2 A x3 = 2) = ( - d / 2 5 x2

- X ~ A X ~ - X ~ ~ ~ / ~ A X ~ < Z )

ensemble-états - traités + ensemble - états - traités U {(good-pœsitia, - d / 2 5 z2

- X I A ~2 - XI 5 d / 2 A ~3 < 2 ) )

A rie niveau la propriété Ps est vérifiée car la région de données déhie par le prédicat

d'état de son état initial (good-position, xs 5 2 ) contient la nouvelle région de données

(goud-position, [[-dl2 5 xa - XI h 352 - xs, 5 d / 2 A x3 5 211).

************************************************************************

propriété - vérifiée c-- trzle

états - à - traiter - 0 ************************************************************************

[[rv]] C rkgion-état - f znal qr o p r i é t é ~ é d e c e s s e w , c'est-à-dire que la trajectoire

définie par la propriété précédante peut &tre un préfixe de la trajectoire définie par la

propriété courante.

************************************************************************

retour B la procédure v&riAcation - propriétb

***** états à traiter = 0 ***** - - boucle tant que (états - à - traiter # 0 ) n'est plus vérifik

Sauvegarde de la région de données de l'état final de P6, pour vérifier si elle contient

la région de données qui satisfait sa propriété successeur.

************************************************************************

région-état- f i n a l ~ o p r i é t é ~ é d e c e s s e î l r - [[x3 5 211 Retour B la procédure vérification - cycle

boucle tant que (cycle # 0 et continu - synthèse = true) n'est plus v&iAée ........................................................................ A ce niveau, la condition de la procèdure vérification - cycle (catinu-synthèse =

true et région - début - cycle c région - état - f inal~gprzgprz6téqrédecesseur) est satis-

faite, alors cycles est vérifi6. *******************%****************************************************

Tous les cycles sont vénfi6s alors il existe un ~ontr61eu.r~ ************************************************************************

retour au programme principal

boucle tant que (ensemble - cycles # 0 et ccnatznu - synthèse = true) n'est plus

vérifiée

************************************************************************ ************************************************************************

Synthèse de contrôleur. ************************************************************************

appel procédure synthése - cont rOleur(ensemb1e-cycles)

boucle pour chaque cycle de ensemble - cycles

************************************************************************

Cette boucle présente trois cas : cycle = {cyclei, cycle?, cycle3).

************************************************************************

1" cas

cycle = q d e l

boucle pour chaque P de cyclel **** cyclei = {P l , Pz) **** l " c a s P = P ,

ensemble - mudes - de - commade - traités c- 0

ensemble-modes - de-cammande c {(unknown))

boucle tant que ensemble-modes - de - commande # 0 est vérifiée

choix v = (unknown) de ensemble - d e s - d e - c m m a d e

ensemble - modes - de - commande - ensernbl e-modes-de-conmande - {(unkn-

w n ) ) = 0 v = (unknoun) $ ensemble-modes - de - commande-traités

boucle pou. chaque (e, v') de transitions - successeurs(unknuwn)

........................................................................

Cette boucle présente un seul cas : (e, v') E {(el , idle)).

************************************************************************

Event (el) est un événement incontrôlable alors nous ne construisons pas la loi de

commande -((unknum) pour cet événement.

ensemble - modes - de - commande - ensemble - modes-de-commande ci {(idle)}

= {(idle))

ensemble - modes - de-commande - traités c ensemble-modes-de-commande-

traités u {(unknown)) = {(unknown))

boucle tant que ensemble-modes - de - commande # 0 est vbriflée

choix v = (idle) de ensemble-modes - de - commande

ensemble - mudes - de - commande - ensemble-modes-de-commande - {(idle))

v = (idle) $ ensemble modes - de - wmrnande - traités

boucle pour chaque (e, d) de transitions - successeurs(idle)

************************************************************************

Cette boucle présente quatre cas : (e, v') E {(el , unknown) , (es, moving-le f t ) , (e4,

good-posztion) , (e3, maving-right) }. ************************************************************************

1" cas

(e, v') = (e2, unknown)

Event(es) est un événement incontr6lable alors nous ne constmisuns pas la loi de

commande idle le) pour cet événement.

v' = ( u n k n m n ) E ensemble-modes - de - commande-traités

2ihe cas (e, ut) = (es, moving-le f t )

Event(es) est un événement contrôlable et i l ne fait pas l'objet d'une loi de commande.

idle le) - $idle) u { (start-mming-le f t ) } = { (start-mng-le f t ) }

afficher(idle, start-moving-le f t, Jurnp(idle, moving-le f t ) = (x3 = 2 Ax2 -xl > d/2A

d! = O A X\ = XI A x!! = 1 2 A d4 = x4)

ensemble-modes-de - commande - ensemble-modes - de - commandeu

{(moving-le f t ) } = m moukg-le f t ) }

3ikne CâS

(e, d ) = (e4, goad-position)

E v a t ( e r ) est un événement contrôlable et il ne fait pas l'objet d'une loi de commande.

y (idle) t ?(idle) U { (set-go&-position) } = {(start-nwving-le f t ) , (set-good-

positicm) }

afficher(idle, set-good-position, Jump(adle, go&-position) = ( 1 2 - XI 5 d / 2 ~

2 2 - 2 1 L - ~ / ~ A ~ = O A X ~ = X ~ A ~ = X ~ A X ~ = X ~ ) )

ensemble-modes-de-commande - ensemble - modes - de - commande U {(good-

position)) = { (mming-left ) , ( g d-posi t ion) }

Fe cas

(e, d ) = (ea , moving-right)

Event(e3) est un événement contralable et il ne fait pas l'objet d'une loi de commande.

m id le) - ?(idle) U { (start-moving-rig ht) ) = { (start-mming-right ) , (start-

moving-le f t ) , (set-go&-positia) )

afEcher(idle, start-moukg-îight , Jump(idle, moving-~ight) = (x3 = 2 A x2 - XI <

- d / 2 ~ ~ ' , = O A X ; = x ~ A x $ = x ~ A x ~ = x ~ ) )

ensemble-modes-de-cmmande c ensemble-modes-de-cmmande U {(mov-

ing-right) ) = {(moving-le f t ) , (go&-position) , (moving-rig ht) )

ensemble - modes - de - commande-traités c ensemble-modes-de-commandee

traités U {(idle)) = {(unknown), (idle))

boucle tant que ensemble - modes - de - commande # $ est vhrifiêe

Cette boucle présente trois cas :

v = { (mhng-le f t ) , (gd-position) , (moving-right) ) . ************************************************************************

choix v = (movâng-le f t ) de ensemble - modes - de-conmande

ensemble - modes - de - commande - ensemble modes de commande - {(mou- - - - ing-le f t ) ) = {(good-position) , (ming-r ight ) )

v = (mouing-le f t ) @ ensemble - modes-de-commande-traités

boucle pour chaque (e, d ) de transitions - s u c c e s s e ~ r s ( ~ n g - l e f t ) ************************************************************************

Cette boucle présente un seul cas : (e, v') E {(e6, idle) ) . ************************************************************************

1" cas (e, d) = (es, idle)

Event (e) est un événement contrôlable et il ne fait pas l'objet d'une loi de commande.

~(moving-le f t ) - ~(moving-le f t ) u {(stop)) = {(stop)}

anicher(moving-le f t , stop, Jump(maving-le f t , idle) = (x2 - XI 5 d / 2 A d, = 1 A xi

= O A ~ = X ~ A X ~ =xi))

ensemble - modes - de - commande t ensemble-modes-de-commande U ((idle))

= { (idle), (good-position) , (motring-right) )

ensemble - modes - d e - commande - traités - ensemble-modes de commande - - - traités u {(movi-ng-le f t ) ) = {(moving-le f t ) , (unknown) , (idle))

boucle tant que ensemble - modes - de - commande # 0 est v6rifiée ************************************************************************

Cette boucle présente trois cas : v = { (go&-position) , (moving-right) , (idle) } . ************************************************************************

choix v = (goud-position) de ensemble - modes - de-commande

ensemble-modes-de-cammande - ensemble - mudes - de - commande - {(good-

position)) = { (moving-right ) , (idle))

v = (go& - position) t$ ensemble-modes-de - commande-traités

boucle pour chaque (e, d ) de transitions - successeurs(good-position) ************************************************************************

Cette boucle présente un seul cas : (e, v') E { (ee , idle) ) .

1" cas

(e, J ) = (eg , idle)

E v a t ( e 8 ) est un événement incontrôlable alors nous ne construisons pas la loi de

commande +y(god-position) pour cet événement.

v' = (zmknown) E ensemble - modes-de - commande - traités

boucle tant que ensemble - modes - de - conamande # 0 est vérifiée ************************************************************************

Cette boucle présente deux cas : v = {(maving-right), (idle)).

************************************************************************ choix v = (molnng-right) de ensemble - modes - de-commande

ensemble-modes - de - commande - ensemble - modes - de - commande - {(mov-

ing-right) ) = ((id1 e) )

v = (moving-right) $ ensenable-modes - de-commande-traités

boucle pour chaque (e, v') de transitions- successeurs(moPnng-rig ht)

************************************************************************ Cet t e boude présente un seul cas : (e, ut) E {(e7, idle) ) . ************************************************************************

lm Cas

(e, VI) = (ei, idle)

Event (e7) est un événement contrôlable et il ne fait pas l'objet d'une loi de commande.

~(muuing-rig ht) - y(moving-right ) U {(stup) } = {(stup) }

afZicher(mavi*ng-right, stop, Jump(mouing-right, idle) = (2.2 - XI 2 -d/2 A d4 =

~ A X ~ = O A ~ ~ = X ~ A Z ' ~ = x ~ ) )

ensemble-modes - de - commande + ensemble - modes - de - commande U {(mm-

ing-right) ) = {(idle)}

boucle tant que ensemble - modes-de-commande # 0 est vérifiée ************************************************************************

Cette boucle présente deux cas : v = {(ide)) . ************************************************************************

choix v = (idle) de ensemble - modes-de-commande

ensemble-modes - de - commande - ensemble - modes-de - commande - {(idle)}

= 0

v = (idle) E ensemble - males-de-commande-traités

boucle pour chaque P de cyclel **** cyclel = {P1,P2} **** 3- cas P = P2 ************************************************************************

Nous appliquons la même démarche pour la propriété Pz et ainsi que pour les cycles

Bibliography

[l] X. NiCoIlin, A. Olivero, J. Sifakis, and S. Yovine. An approach to the description

and analysis of hybrid syçtems. In Hybrid Systems, R. L. Grossman, A. Nerode,

A. P. h, and H. Rischel, editors, Lecture Notes in Computer Science, vol. 736,

pages 149-1 78, S pringer-Verlag, 1993.

[2] P. J. Ramadge and W. M. Wonham. The control of discrete event systems. Pro-

ceedings of the IEEE, 7?(l) : 81-98, 1989.

[3] P. J. Antsaklis, J. A. Stiver and M. D. Lemmon. Hybrid system modeling and

autonomous control systems. Hybrid Systems, R. L. Grûssman, A. Nerode, A. P.

R m , and H. Rischel, editors, Lecture Notes in Computer Science, vol. 736, page

36fb392, Springer-Verlag, 1993.

[4] T. Henzinger and H. Wong-Toi. Using Hytech to synthesize control parameters

for a s t e m boiler. In Formal Methoàs for IndPtstniaZ Applications : SpecZfying and

Pmgmming the Steam Boéler Control, J.-R Abrial, E. Borger, and H. Langrnaack,

editors, Lecture Notes in Computer Science, vol. 1165, pages 265-282, Springer-

Verlag, 1996.

[5] T. A. Henzinger, P.-EL Ho, and H. Wong-Toi. HYTECH : a model checker for

hybnd systems. Software Tools for Teehnology %nsfer, l(1) : 110-122, 1997.

[6] T. HenPnger. The theory of hybrid automata In Proceedings of the 11th Annual

Symposium on Logic in Cornputer Science, pages 278-292, 1996.

[7] R. Alur, C. Courcoubetis, N. Halbwachs, T. Henzinger, and P.-H. Ho, X N i c o h ,

A. Olivero, J. Sifakis, and S. Yovine. The algorithmic analysis of hybrid systems.

Theoretid Computer Science, 138(1) : 3-34, 1995.

[8] R Alur, T. A. Henzinger, and P--H. Ho. Automatic symbolic verincation of em-

bedded systems, In Pmceedings of the 14th Annual Real-tine Sys tew Symposium,

pages 2-11. IEEE Computer Society Press, 1993. Full version appears in IEEE

T4ansactiow on Softwa~e Engin-g, 22(3) : 181-201, 1996.

[9] R Alur, C. Courcoubetis, T. Henzinger, and P.-H. Ho. Hybrid automata : an

algorithmic approach to the specification and verifkation of hybrid systemç. In

Hybrid System, R. L. Grossman, A. Nerode, A. P. Ravn, and R Rischel, editors,

Lecture Notes in Computer Science, vol 736, pages 209-229, Springer-Verlag, 1993.

[IO] M. Barbeau, F. Kabanza, and R St-Denis. A method for the synthesis of controllers

to handle &y, liveness, and rd-tirne constraints. BEE transaction on Automat ic

Control, 43(11) : 154S1559, 1998.

[Il] K. Wong-Toi. The synthesis of controllers for lin- hybrid automata. In Proc.

36th CDC, pages 4607-4612, 1997.

[12] 0. Maler, A. Pnueli, and J. Sifakis. On the synthesis of discrete controllers for

timed systems. In STACS 95 : Theoretical Aspects of Computer Science, E. Mayer

and C. Puech, editors, Lecture Notes in Computer Science, vol. 900, pages 229-242,

S pringer-Verlag, 1995.

[13] E. Asarin, O. Maler, and A. Pnueli. Symbolic controller synthesis for discrete and

timed systems. In Hybn'd s y s t e m IT, P. Antsaklis, A. Nemde, W. Kohn, and S.

Sasty, editors, M u r e Note in Cornputer Science, vol. 999, pages 1-20, Sprhger-

Verlag, 1995.

[14] E- Asarin, O. Maler, and A. Pnueli, and J. Sifakis. Controller synthesis for timed

automata. In Proc IFAC Symposium on System Structure and Control, pages 469-

474, Elsevier, 1998.

[15] R Kumar and V. K . Garg. Modelling and Control of Logical Discrete Event Sys-

t e m . Kluwer Academic F ublis hem, 1995.

[16] M. Barbeau, F. Kabanza, and R St-Denis. An scient algorithm for controller

synthesis under fidl observation. Journal of Algorithms, 25(1) : 144-161, 1997.

[l?] T. A. Henzinger and P.-H. Ho. HYTECH : The CorneIl Hybrid Technology Tool.

In Hybrid Systems II, P. Antsaklis, A. Nerode, W. K o h , and S. Sastry, editors,

Lecture Notes in Computer Science, vol. 999, pages 265-293, Springer-Verlag, 1995.

[18] S. WoIfram. Mathematica : A System for Doing Mathematics by Computer.

Addison-Wesley Publishing Company, 1988.

[19] T. A. Henzinger, X. Nicollin, J. Sifakk, and S. Yovine. Symbolic mode1 checking

for rd-tirne systems. Infornation and Computation, 111(2) : 19S244, 1994.

[20] T. A. Henzinger, P.-H. Ho, and H. Wong-Toi. HYTECH : the next generation. In

Pmceedings of the 16thtAnnual Red-time Systems Symposium, pages 5665, 1995.

[21] T. A. Henzinger, P.-H. Ho, and H. Wong-Toi. A user guide to HYTECH. In

TACAS 95 : Toots and Algorithms for the Constmction and Analyse of Systems,

E. Brinksma, W . R. Cleaveland, K. G. Larsen, T. Margaria, and B. SteEen, editors,

Lecture Notes in Computer Science, vol. 1019, pages 41-71, Springer-Valag, 19%.