Logique linéaire et réseaux de Petri: application au ...homepages.laas.fr/francois/SVF/seminaires/inputs/bpcllrdp.pdf · • Prise en compte du temps. ... M1 , s1 M2 M 2 , s2

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


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


Modèles et outils

Modélisation systèmes distribués

temps

Etat

Evénement

synchronisation


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


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


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


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


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

|||


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

Etape 1:

Accessibilité RdP et prouvabilité LL


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


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


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


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

Etape 2:

Recherche de l’ordre partiel


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


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


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

Etape 3:

Arbre de preuve canonique:recherche de la causalité


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

......,

σσ


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é)

Etape 4:

Dates symboliques:application aux réseaux de Petri temporels


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(

σσ


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


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


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

Bilan démarche - Travail en cours

Perspectives


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


... 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


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


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


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


… 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

Documents

Logique linéaire et réseaux de Petri: application au ...homepages.laas.fr/francois/SVF/seminaires/inputs/bpcllrdp.pdf · • Prise en compte du temps. ... M1 , s1 M2 M 2 , s2