View
217
Download
0
Category
Preview:
Citation preview
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 1
Logique linéaire et réseaux de Petri:application au
raisonnement temporel
Brigitte PRADIN-CHEZALVIELLAAS-CNRS (Groupe OLC)
Robert VALETTE
Etudiants, Doctorants
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 2
PLAN
• Logique linéaire et Réseaux de Petri– problématique– différentes étapes
• équivalence accessibilité RdP / prouvabilité LL• recherche ordre partiel• recherche causalité
– application aux réseaux de Petri temporels– bilan/perspectives
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 3
Modèles et outils
Modélisation systèmes distribués
temps
Etat
Evénement
synchronisation
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 4
Caractéristiques des modèles
• Orientés états/événementsgraphe d’états, automates (explosion combinatoire)processus
• Non déterminismereprésentation instant choix
• Parallélismeentrelacement ⇒ confusion avec non déterminisme + explosion
• Compositionnalitéraisonnement partiel
• Prise en compte du temps
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 5
Réseaux de Petri
• Modèle dual places/transitions– espace d’états
• parallélisme ⇒ entrelacement• vérification (« model checking »)• techniques d’abstraction (réduction, symétrie, projection,..)
– transitions: invariants et M’ = M + C.s• pas d’ordre, condition nécessaire mais non suffisante
⇒ travail orienté événementsdirectement sur le réseau, sans construction graphe d’états
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 6
Logique linéaire (J.Y. Girard 1987)
• StructureA implique B ET A implique C
• FonctionnementA implique (B ET C)
A
B C
A implique (B OU C) (A ET A) implique (B ET C)
& ⊗« ET additif » « ET multiplicatif »
• Déduire le fonctionnement de lastructure
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 7
Principes de la logique linéaire
• Suppression règles d’affaiblissement et de contraction A ⇒ A ET A A ET B ⇒ A
• Eclatement connecteurs ET et OU ET OU ⊗ & ℘ ⊕ multiplicatifs / additifs
• Implication linéaire oA o B : consommation A permet production B
Logique des ressources Connecteurs exponentiels: contrôle affaiblissement/contraction
Négation linéaire: inversion sens utilisation des ressources
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 8
Preuve: calcul des séquents
• Règles « d’introduction » des connecteurs• Arbre de preuve: débute par séquent à prouver
• Preuve correcte: toute feuille est un axiome (séquent identité)
→ Cas particulier: règle « de coupure » élimination des coupures: propriété sous-formule
LIdId
o B B oA ,A
B BA A
|||
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 9
Différentes étapes de notre travail
Recherche Ordre Partiel
Réécriture arbre de preuve
RechercheCausalité
Etats « perdus »durant la preuve
Arbre de preuve « canonique »sans coupure
Analyse temporelle symbolique
Etats « retrouvés » parlabels temporels
labels temporelssymboliques
Séquent= Transition
Pasd’états
Causalité =
coupure
PAS parallélisme
dû au marquage
Séquent= Scénario
Etats +événements
Parallélisme dû au marquage
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 11
CA )Co B(A ,BAAt1
⊗|⊗⊗⊗ 44 344 21
CA:'MBAA:M
⊗⊗⊗
'MM 1t→
Notre approche: scénario
PAS d’axiomes propres
– marquage est un monôme exprimé par ⊗– transition exprimée par o– franchissement exprimé par un séquent prouvable
Co BA:1t ⊗
EDo C:2t ⊗A
B
DC
E
t1 t2
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 12
Multi-ensemble de franchissements
EDA t2 , 1t ,BAA ⊗⊗|⊗⊗EDA:'M
BAA:M⊗⊗⊗⊗
A
B
DC
E
t1 t2 Co BA:1t ⊗
EDo C:2t ⊗
M M’t1;t2
• EQUIVALENCE Accessibilité et ProuvabilitéThèse de F. GIRAULT
'Mtn,,1t,M −−≡ L
'Ms,M −−
M M’t1;t2; …; tn
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 13
Scénario
• Scénario = état de départ + état d ’arrivée +ensemble de transitions AVEC ordre partiel
Pas d ’ordre Ordre Total Ordre non exprimé
scénario = {séquences}
'Mtn,,1t,M −−Ls.CM'M +=
• L’ordre peut être extrait de l’arbre de preuve du séquentobtenu en restreignant les règles utilisées à 2 règles
– séquence (Cut)
– parallèle (⊗R)
Restrictions du calcul des séquents
M M’t1;t2; …; tn
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 14
Règles pour construire l’arbre de preuve
• Exécution en séquence de 2 scénarios s = (s1 ; s2)
• Exécution en parallèle de 2 scénarios s = (s1 // s2)
PARA4M2 M 2 , s1 , s3M1M
4 M 2 , s3M 2 M 1 , s1M⊗|⊗||
SEQ3 M 2 , s1 , s1M
3 M 2 , s2M 2 M 1 , s1M|
||
PARA MMs , MMM s , M M M
2 11
2 11
⊗|⊗||
èExécution d’un scénario dans un contextesupérieur au marquage nécessaire s = s1
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 16
Exemple de scénario
Marquage de départ = A ⊗ B ⊗ Cs = { t1 , t2 }
• Cas où l’arbre de preuve n’est pas unique– scénario est ( t1 ; t2)
Co BA:1t ⊗
EDo C:2t ⊗
PARAEDC 2 t, 1 , tCBA
C CSEQ E D 2 t, 1 , tBA
E D 2C , t C 1B, tA
⊗⊗|⊗⊗
|⊗|⊗
⊗||⊗
PARA ED C 2t,1C , tBA
E D 2C , t C 1B , tA⊗⊗|⊗⊗
⊗||⊗
– scénario est ( t1 // t2)
A
B
DC
E
t1 t2
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 17
Méthode pour obtenirparallélisme maximal
Repousser « coupure » vers le haut de l ’arbre
Thèse de L.A. KUNZLE
• Construire un arbre de preuvequelconque
• Transformer arbre de preuve:– règle de base parallélisme structurel
( t1 // t3) ; ( t2 // t4)en
( t1 ; t2) // ( t3 ; t4)– règle de base parallélisme dû au marquage
(t1 ; t2) en (t1 // t2)– règles annexes
B FDt3 t4
A ECt1 t2
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 18
Limites
• Impossible caractériser le scénario avec OP série-parallèleseulement « séquence » et « parallèle »
relations d ’ordre ajoutées
tdeb ; (t1 // t3) ; (t2 // t4) ; tfin t3 ; t2tdeb ;( (t1 ; t2) // t3) ; t4 ; tfin t2 ; t4tdeb ; t1 ; ( (t3 ; t4) // t2 ) ; tfin t1 ; t3
M
B C Dt1
E F Gt4
tdeb tfinA Z
t3
t2
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 20
LMoMBAMBA
MoMBAMBA⊗
|−−⊗⊗⊗|−−⊗
''),2(,1''),2(,1,,
σσ
Construire l’arbre de preuve
• Transformer marquage en liste d’atomes
• Franchir une transition
èLe séquent à prouver a été réduitèPreuve valide: toutes feuilles = séquent identitéèPlus d’états mais liste d’atomesèArbre canonique
oLMoMBAMBA
MMMR
BABABBAA
|−−⊗
|⊗
⊗|||
''),2(,1,,'',2,1
......,
σσ
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 21
Conflits
• Arbre linéaire si scénario complètement spécifié(pas de conflit transition ni multi-sensibilisation)
→ profondeur = « taille » du scénario
• Si conflit, nécessité d’envisager les différentesrésolutions:→ dédoublement de l’arbre
• Prototype développé (stage ingénieur E. Kaboré)
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 23
Dates dans l’arbre de preuve
• Dates imprécises de production et de consommation (Dp,Dc)(d,.) : date de consommation non connue
• Transformer marquage en liste d ’atomes
LMoMBA(d,.)MBA
MoMBA(d,.)MB(d,.)A(d,.)⊗
|−−⊗⊗⊗|−−⊗
''),2(,1''),2(,1,,
σσ
• Franchir une transition : date de consommation= max (dates production des atomes) + durée de transition
d ’ = max (d1,d2)
oLMoMBAdMdBdA
MdMdMR
BAddBddABddBAddA
−−|−−⊗
|∆+⊗
⊗|∆+∆+|∆+|∆+
''),2(,.),3(1,.),2(,.),1('',.),'(2,.),3(1
......)',2(),',1(
)',2()',1(
σσ
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 24
Durée associée aux états
• Dates production/consommation imprécises (floues) [deb , fin]• Durée séjour dans un atome = DC - DP
⇒ manipulation symbolique d ’expressions
(D + d) - (D + d’) = d - d’ pas de cumul d’imprécision
la causalité est prise en compte : passé commun
ETAT « virtuel »• Date production ETAT = MAX (DP des atomes) = DPe• Date consommation ETAT = MIN (DC des atomes) = DCe• Durée séjour dans un ETAT = DCe - DPe
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 25
Accessibilité des états
Durée séjour dans un ETAT = d - d’
⇒ calcul d - d’• durée maximum < 0 état INACCESSIBLE [*,*]• durée maximum ≥ 0
durée minimum < 0 état POTENT. ACCESSIBLE [*, dmax]• durée minimum et maximum ≥ 0
état ACCESSIBLE [dmin, dmax]
calcul symboliqueq ≤ 0 (-d’) ⇒ inaccessibilité structurelleq > 0 (d) ⇒ accessibilité structurelleq autres cas ⇒ accessibilité dépend des valeurs
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 26
Exemple : accessibilité
Durée de B⊗E = min(d2 , d4+max(d2,d3)) - d3 = d2 - d3= [1-β , α-2] = [∗ , α-2] ⇒ potentiel si α ≥ 2
⇒ inaccessible si α < 2
A
B
E
C
D
F
[1,α]
[2,β]
t2t1 t4
t3
Durée de C⊗D = min(d3 , d4+max(d2,d3)) - d2 = d3 - d2= [2-α , β-1] ⇒ potentiel si α ≥ 2
⇒ accessible si α < 2
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 28
Bilan démarche suivie
• Traduction RdP en LL (scénario ) +équivalence accessibilité RdP/ prouvabilité LL: socle
• Méthodes de preuve→ extraire ordre partiel de l’arbre de preuve (transformation)
◊ analyse temporelle à partir Ordre Partiel◊ limité aux OP série-parallèle◊ raisonnement seulement avec états
→ arbre unique + labels temporels symboliques : causalité(pendant la construction de l ’arbre)
◊ raisonnement sans les états◊ analyse temporelle efficace (parallélisme)◊ accessibilité états par labels temporels symboliques
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 29
... Bilan
Analyse temporelle RdP (sans graphe d’états)
Application aux RdP temporels ⇒ RdP ordinaires
• Méthodes orientées événements (complémentarité)
• Parallélisme traité sans entrelacement• Choix mis en exergue durant preuve (conflits)
• Raisonnement sur réseau partiel• Manipulation symbolique du temps
→ raisonnement conduit sur réseau non temporel
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 30
LL et RdP
• Plusieurs façons de travailler:
– règle Cut appliquée à des états ⇒ SIMULATION
– règles ⊗R et Cut pour parallélisme (états)⇒ caractériser indépendance
– règle o L pour causalité (atomes)⇒ caractériser dépendance
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 31
Travail en cours
• Expression symbolique– marges temporelles
• dates au plus tôt, au plus tard• attentes• relâcher contraintes temporelles, imprécision
– causalité, raisonnement arrière
– différents types de modèles• temporisés• p-temporels ou mixtes
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 32
Perspectives ...
• Logique linéaire– connecteurs additifs (choix)– raisonnement arrière (négation linéaire, ℘)
• marges temporelles• explication comportement observé
• Situations de conflit + multi-sensibilisation• utilisation information sur accessibilité des ETATS et leur
durée pour valider ou non les 2 arbres• jetons différenciés par dates• conflits potentiels éliminés: dates incompatibles• conflits réels mis à jour: intervalles de présence simultanée
Journée « Réseaux de Petri, Logique et Vérification » 19 janvier 2001 33
… Perspectives
• Domaines d ’application– systèmes coopératifs (thèse qui débute)
• travaux existants sur LL et coopération• aspects temporels
– systèmes distribués: ordonnancement, supervision• contraintes temporelles
• Mise en oeuvre– outil existant à développer– exemples
Recommended