|
Pierandrea Secchi (piero.1979@libero.it)Pierandrea Secchi è nato a Cagliari il 16 marzo 1979. Ha conseguito la Laurea Specialistica in Ingegneria Elettronica nel Luglio del 2008 presso il Dipartimento di Ingegneria Elettrica ed Elettronica dell'Università degli Studi di Cagliari. La sua tesi è stata sviluppata presso il laboratorio di Automatica del DIEE. |
Tecniche di programmazione lineare per l'identificazione di reti di Petri
[pdf] [slides]
Prof. Alessandro Giua (DIEE-UNICA); Ing. Maria Paola Cabasino (DIEE-UNICA).
Oggetto di questa tesi è lo sviluppo di uno strumento software in Matlab per
l'identificazione di una rete posto/transizione, basato sulla programmazione
lineare. La procedura di identificazione riceve
in ingresso un linguaggio L finito e chiuso per prefisso e un intero k
maggiore o uguale alla lunghezza della stringa più lunga in esso contenuta,
e produce in uscita una rete il cui linguaggio delle parole generate di
lunghezza non superiore a k coincide con L.
La procedura viene eseguita nel seguente modo.
1. A partire da L costruisce gli insiemi delle condizioni di abilitazione E e
di disabilitazione D.
2. Da questi estrae un insieme di vincoli lineari, le cui incognite sono gli
elementi della marcatura iniziale M0 e delle matrici Post e Pre. Il numero
di posti della rete è inizialmente pari alla
cardinalità di D o, eventualmente, minore se sono presenti particolari condizioni sugli
elementi di D, ma può essere ridotto in base ad informazioni aggiuntive
sulla struttura della rete (tecnica di pre-riduzione).
3. L'insieme di vincoli così costruito, a cui eventualmente si possono aggiungere
nuovi vincoli se sono presenti altre informazioni sulla rete, viene risolto mediante l'ausilio
della libreria software GLPK, determinando la rete con
marcatura iniziale M0 e struttura Post e Pre che genera il linguaggio dato L.
4. Infine i posti ridondanti possono essere rimossi (tecnica di
post-riduzione) senza modificare il linguaggio generato.
Le funzioni Matlab che costituiscono lo strumento software eseguono
automaticamente i vari passaggi sopra descritti. La funzionalità
dei programmi e la correttezza della procedura sono state testate su varie reti.
I dati più importanti ricavati dai test riguardano i limiti di affidabilità dei risolutori
di GLPK, i linguaggi generati dalla rete, la complessità del problema di programmazione lineare,
la variazione del numero di posti durante i vari passi, i tempi di computazione e il limite
di applicabilità della procedura dal punto di vista della memoria utilizzata
da Matlab.
Parole chiave: identificazione, reti di Petri, programmazione lineare, linguaggio, posti.