|
Paolo Copello Un sistema multi-agente per lo scheduling on-line in ambito manifatturiero |
Indice tesi Home Page |
Introdotti nell’Intelligenza Artificiale Distribuita, gli agenti ed i sistemi multi-agente sono al centro di numerose ricerche nell’ambito dell’information technology, in particolare per quanto riguarda i problemi decisionali.
Una qualunque applicazione distribuita può essere efficacemente rappresentata come un insieme di agenti software cooperanti e un modello multi-agente può rappresentare un approccio euristico ai problemi di ottimizzazione, nel quale dal comportamento autonomo di singole entità decisionali deriva l’ottimizzazione di un obiettivo globale.
In questa tesi è stato applicato questo concetto sviluppando un modello MAS per lo scheduling di job in un contesto manifatturiero dinamico.
In definitiva è stato realizzato uno studio per l’utilizzo di architetture multi-agente nella risoluzione di problemi di controllo distribuito. Una volta definiti tutti gli agenti coinvolti nel sistema secondo uno standard comune (in questo caso lo standard FIPA), la logica decisionale è stata implementata attraverso il comportamento dei singoli agenti, che rappresentano entità concrete (job e macchine) e comunicano tra loro tramite due possibili protocolli di negoziazione.
Allo stato attuale, il sistema di scheduling ad agenti fornisce buone prestazioni: ulteriori sviluppi futuri comprendono estensioni dell’algoritmo e introduzione di capacità di apprendimento negli agenti.
Una possibilità per migliorare il sistema di scheduling consiste nel modificare il comportamento degli agenti macchina.
Attualmente i MA offrono sempre ai job il miglior slot possibile, e iniziano ad emettere le conferme a partire dal miglior agente job offerente, anche se ciò può condurre a perdere la contrattazione con altri JA. È possibile introdurre nei MA una nuova regola: se gli slot proposti a due job sono sovrapposti “di poco” (ovvero per un certo periodo di tempo minore di una data soglia) allora l’agente macchina propone due soluzioni sub-ottime non sovrapposte.
Questa soluzione è migliore rispetto al normale comportamento dei MA, che porterebbe alla generazione di una soluzione ottima per un JA e una soluzione molto più lontana dall’ottimo per un altro JA.
Un’altra possibilità (valida soltanto per il protocollo esteso) consiste nel modificare i criteri di annullamento delle promesse da parte dell’agente macchina, in modo da tenere in considerazione anche la funzione obiettivo e il numero di job serviti oltre all’offerta in denaro.
L’euristica di scheduling presentata è influenzata da una certa quantità di parametri, cioè quei valori che influenzano il comportamento dei job e delle macchine: il numero di questi parametri potrebbe sembrare a prima vista eccessivo. Tuttavia molti di essi possono essere fissati in maniera relativamente semplice e raramente modificati in seguito; inoltre tali parametri definiscono il comportamento di entità relativamente semplici (gli agenti) le cui azioni dovrebbero essere tracciabili ed analizzabili con semplicità, anche in una fase di prima sperimentazione, facendo riferimento all’interpretazione intuitiva (antropomorfa) di tale comportamento (per questo, parlando dei parametri, si parla di ansiosità, fretta, ecc.). Maggiore è l’autonomia, la proattività e la capacità di interagire che si vuole dare agli agenti, maggiori saranno le sfaccettature del loro carattere e quindi il numero di parametri che li caratterizzeranno.
Ad ogni modo, è evidente che dovrebbe essere possibile ottenere migliori prestazioni (ovvero schedule migliori) con un’appropriata fase di tuning di tali parametri. Le possibilità prese in esame sono due:
sviluppare di una procedura di addestramento off-line
incorporare nel MASS un sistema di self-tuning, ovvero dotare gli agenti di capacità di apprendimento.
Nel primo caso, il sistema di scheduling interagisce con un algoritmo di ottimizzazione basato su una local search non-lineare che tenta di minimizzare la funzione obiettivo modificando i valori dei diversi parametri.
Nel secondo scenario, il concetto di apprendimento è applicato al sistema di scheduling nella sua globalità piuttosto che ai suoi singoli elementi: non sono infatti i singoli agenti che imparano, ma la loro collettività o meglio la loro specie impara. Per questo forse si potrebbe parlare di evoluzione più che di apprendimento, e i parametri caratteristici potrebbero essere visti come una sorta di “codice genetico” degli agenti.
Tra le generazioni successive di agenti potrebbe dunque esistere un meccanismo di apprendimento in base al quale migliorare le prestazioni del sistema di scheduling risultante: gli agenti generatori (JGA e MGA) creerebbero ogni volta agenti con leggere variazioni dei parametri e regolarmente trasmetterebbero alle nuove generazioni di agenti i parametri che hanno ottenuto prestazioni migliori.
A loro volta, anche gli agenti generatori possono essere dotati di parametri caratteristici: ad esempio, un agente JGA può avere un parametro che rappresenta la probabilità di far nascere agenti JA con un comportamento “tranquillo” o “ansioso”.
L’evoluzione (ossia la sequenza di variazione dei parametri) può essere:
sincrona: i dati relativi al comportamento degli agenti di una specie possono essere conservati in database statici ed analizzati periodicamente (ad esempio utilizzando tecniche di data mining).
asincrona: sono gli agenti generatori ad istanziarla quando lo desiderano
continua: alla morte di una agente viene subito analizzato il suo comportamento in vita.
Quest’ultima possibilità dovrebbe essere messa in pratica in modo molto prudente per evitare variazioni troppo brusche nel comportamento di una specie (variazioni che renderebbero inutile l’analisi delle prestazioni, ovvero lo stesso meccanismo evolutivo): l’evoluzione, rispetto al periodo di vita degli agenti, dovrebbe impiegare tempi molto più lunghi (il comportamento di una specie dovrebbe essere modificalo solo sulla base di statistiche ben assestate).
Uno svantaggio di questo approccio potrebbe essere dato dal rischio di conservare a lungo un insieme di parametri che fornisce pessime prestazioni: questo inconveniente può essere risolto facendo evolvere il sistema degli agenti in maniera fittizia durante un periodo di tuning preliminare (simile in questo senso alla procedura di addestramento off-line descritta in precedenza) durante il quale viene sottoposta al sistema di scheduling una sequenza di problemi di prova (test fuori linea), lasciando evolvere il sistema sino ad assestare un insieme di parametri con prestazioni accettabili.
L’evidente vantaggio di questa architettura è dato dalla sua elevata dinamicità, in grado di evolvere per adattarsi ai mutamenti della domanda del mercato – condizione essenziale per le moderne imprese manifatturiere.
Capitoli: 1 2 3 4 5 6 7 Bibliografia
|
Paolo Copello Un sistema multi-agente per lo scheduling on-line in ambito manifatturiero |
Indice tesi Home Page |
HTML 4.01 compliant except for Javascript appended by hosting service.