Tesi di Laurea Specialistica in Ingegneria Elettronica Dipartimento di Ingegneria Elettrica ed Elettronica Università degli Studi di Cagliari Implementazione di un nuovo algoritmo per la diagnosticabilità di reti posto/transizione mediante marcature di base Rita Perria Relatori: Alessandro Giua Maria Paola Cabasino ANNO ACCADEMICO 2009-2010 Tesi di Laurea Specialistica in Ingegneria Elettronica Dipartimento di Ingegneria Elettrica ed Elettronica Università degli Studi di Cagliari Implementazione di un nuovo algoritmo per la diagnosticabilità di reti posto/transizione mediante marcature di base Rita Perria Relatori: Alessandro Giua Maria Paola Cabasino ANNO ACCADEMICO 2009-2010 Dedicato ai miei genitori, ai miei fratelli e a mia zia Ringraziamenti Vorrei ringraziare tutte le persone che in questi anni mi hanno sempre sostenu- to, incoraggiato e hanno sempre creduto in me, permettendomi di raggiungere questotraguardo. DesideroringraziareProfessorGiuaperipreziosiinsegnamentiricevutidurante questiannidistudioepericonsigliel’aiutoricevutoduranteillavoroditesi. RingrazioinoltreMariaPaolaCabasino,chemihaseguitocostantementeduran- te tutta la tesi, è sempre stata disponibile a chiarire i miei dubbi e mi ha sempre incoraggiato. Ilringraziamentopiùgrandevaallamiafamigliasenzalaqualenonavreisaputo enonsapreicomefare. GrazieaimieigenitoriNannieMariaeamiaZiaMalle- na,chemihannosostenutoinognimodo,nonmihannomaifattomancarenulla ehannosemprecredutoinme,incoraggiandomineimomentidifficili. Grazieai miei fratelli Pietro e Gianni e alla mia cognatina Graziella, che mi sono sempre stativicinoemihannosempretiratosudimorale. Graziedicuore. Ringrazio inoltre le mie zie, i miei zii e i miei cugini, insomma tutta la mia famiglia,peravermifattosempresentirelaloropresenzaeilloroaffetto. Ringrazio di cuore i miei tesori Eli, Vale, Stefy e Pina, siete le persone migliori che potessi incontrare. Grazie per tutto quello che avete fatto per me e che so checontinuereteafare,pertuttiiconsiglichemiavetedatoechecontinueretea darmi. Graziepertuttiibeimomentipassatiinsieme. Un grazie speciale va alla mia amichetta Lauretta. Grazie per avermi confortato e sopportato sempre soprattutto in questi mesi. Grazie per tutti i consigli, per i tutte le risate e anche per i rimproveri. Mi hai aiutato tanto. Grazie veramente di tutto. Desidero anche ringraziare Signora Cenzina, Signor Luigi e la loro famiglia, che mi hanno accolto come una figlia rappresentando per me un punto diriferimento. Ringrazio Patrizietta, per essermi sempre stata vicino in tutti questi anni univer- sitari,perl’aiutoeilconfortoreciproco,peravermidatosempreiconsigligiusti epertuttiimomentidiallegriaespensieratezzapassatiinsieme. Grazie a tutti i miei colleghi, per l’aiuto reciproco in questi anni di studio e per tuttiipiacevoliricordicheporteròsempreconme. RingraziolemiecoinquilineRobieJessi,peraversopportatoimieimomentidi pazziainquestimesi. Per ultimo, ma non per importanza, ringrazio Fabrizioper l’affetto, la compren- sioneelapazienzachemihadimostratoinquestimesi. Indice 1 Introduzione 1 1.1 Statodell’arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Approccioproposto . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Strutturadellatesi . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Contributidellatesi . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2 Introduzionealleretiposto/transizione 9 2.1 IntroduzionealleretidiPetri . . . . . . . . . . . . . . . . . . . . . 9 2.2 Definizioneestruttura . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Marcaturaesistemadirete . . . . . . . . . . . . . . . . . . . . . . 12 2.4 Abilitazioneescatto . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.5 Equazionedistato . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.6 ProprietàdiunaretediPetri . . . . . . . . . . . . . . . . . . . . . . 15 2.7 RetidiPetrietichettate . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 DiagnosticabilitàdelleretidiPetrilimitate 21 3.1 DiagnosticabilitàmedianteretidiPetri . . . . . . . . . . . . . . . . 21 3.1.1 Inquadramentodelproblema . . . . . . . . . . . . . . . . . 22 3.1.2 Definizionidibase . . . . . . . . . . . . . . . . . . . . . . . 23 3.1.3 DiagnosiusandoleretidiPetri . . . . . . . . . . . . . . . . 25 3.1.4 ModifiedBasisReachabilityGraph-MBRG . . . . . . . . 28 3.1.5 MBRDvsBRD . . . . . . . . . . . . . . . . . . . . . . . . 31 3.1.6 CondizioneN&Sperladiagnosticabilità . . . . . . . . . . 35 4 AlgoritmodiJohnson 39 4.1 Esempidifunzionamentodell’algoritmo . . . . . . . . . . . . . . . 42 4.2 ComplessitàcomputazionaleCFCeCICLI . . . . . . . . . . . . . 50 iii iv INDICE 5 ToolboxdiMatlab 55 5.1 Introduzioneaiprogrammi . . . . . . . . . . . . . . . . . . . . . . 55 5.2 ProgrammaMBRD.m . . . . . . . . . . . . . . . . . . . . . . . . . 56 5.3 ProgrammashowMBRD.m . . . . . . . . . . . . . . . . . . . . . . 59 5.4 ProgrammiMBRD_diag_ott.meMBRD_diag.m . . . . . . . . . . 62 5.4.1 ProgrammaMBRD_graph.m . . . . . . . . . . . . . . . . . 65 5.4.2 ProgrammaMBRD_mod.m . . . . . . . . . . . . . . . . . 66 5.4.3 Programmascc.m . . . . . . . . . . . . . . . . . . . . . . . 67 5.4.4 Programmacfc.m . . . . . . . . . . . . . . . . . . . . . . . 67 5.4.5 Programmaalgoritmo_Johnson.m . . . . . . . . . . . . . . 68 6 Esempieconfrontotraleduemetodologie 71 6.1 EsempidifunzionamentodelToolbox . . . . . . . . . . . . . . . . 71 6.1.1 Esempio1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 6.1.2 Esempio2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 6.2 Testdelsoftware . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.3 Confrontotraleduemetodologie . . . . . . . . . . . . . . . . . . . 80 6.3.1 Modellod’esempio . . . . . . . . . . . . . . . . . . . . . . 80 6.3.2 Risultatinumerici . . . . . . . . . . . . . . . . . . . . . . . 81 7 Conclusioni 87 A Listatideiprogrammi 89 A.1 MBRD.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 A.2 showMBRD.m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 A.3 algoritmo_Johnson.m. . . . . . . . . . . . . . . . . . . . . . . . . . 99 A.3.1 UNBLOCK.m . . . . . . . . . . . . . . . . . . . . . . . . . 101 A.3.2 CIRCUIT.m . . . . . . . . . . . . . . . . . . . . . . . . . . 102 A.4 MBRD_diag_ott.m . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 Bibliografia 115