Analisi dei fallimenti

Lo 0.22% dei casi in cui non si arriva ad una identicazione entro 5 conitti è divisibile in due parti: • Una prima parte è composta da agenti caratterizzati da combinazioni di partenza sempre uguali

nei conitti che si susseguono. Partendo da valori di priorità di accesso pubblica o privata uguali nel corso dei conitti, questi agenti lasciano dopo un numero di passi uguale dopo ogni scontro, rendendo impossibile l'identicazione.

• L'altra parte è composta da combinazioni di partenza diverse tra loro alle quali, però, corrispon- dono risposte uguali nel corso dei successivi conitti, non aumentando le informazioni per l'agente identicante.

Entrambi queste parti sono conseguenze possibili del metodo usato e non è possibile ridurre a 0 il loro numero. Aumentando il numero di conitti e, quindi, il numero di combinazioni possibili di partenza, può diminuire la percentuale di agenti non identicati, ma non è possibile annullarli totalmente, specialmente per quanto riguarda il primo gruppo di errori. Questo è possibile solo se viene imposto nell'algoritmo che ogni conitto eettuato preveda l'agente avversario partire da una distanza diversa o avere una urgenza di accesso dierente, in modo da mostrare risposte diverse dopo ogni scontro. E' quindi possibile notare, quindi, che tale sistema di identicazione non è applicabile per la Leader Election, in quanto la priorità di accesso privata e la posizione iniziale non varia in conitti successivi.

Capitolo 5

Conclusioni e sviluppi futuri

Il presente lavoro di tesi ha avuto come oggetto la progettazione di un algoritmo distribuito capace di gestire i conitti per una risorsa condivisa nei sistemi multi-agente in assenza di comunicazione attiva. Il metodo proposto si basa sull'applicazione della Teoria dei Giochi per la modellazione della realtà e per la scelta, partendo dal modello creato, delle strategie da compiere da parte dell'agente in autonomia dalla squadra di cui fa parte. Il metodo è stato formalizzato per risolvere conitti in base alla priorità degli agenti coinvolti in ambienti diversi tra loro e caratterizzati da un numero elevato di elementi, quali squadre di veicoli, reti di processori o tra elementi di una Smart-Grid. Tra questi scenari di applicazione è stato analizzato in maniera più approfondita il primo tra questi ambienti, caratterizzato da veicoli in competizione per il raggiungimento di un punto nello spazio. Per questo scenario è stata progettata opportunamente la forma dei gioco da sfruttare per la determinazione dei comandi, a partire dalla denizione delle azioni possibili no ai valori dei guadagni ottenibili.

Attraverso simulazioni è stato analizzato il comportamento dell'algoritmo all'interno di due diversi conitti, riguardanti due veicoli in competizione per un target, ma che dieriscono per il calcolo delle priorità necessarie per il possesso della risorsa. Nell'ambito delle simulazioni e opportunamente tarato nei suoi parametri, l'algoritmo ha mostrato un elevato numero di successi in entrambi gli scenari, consentendo all'agente a priorità più elevata di accedere per primo alla risorsa e limitando i casi di fallimento a situazioni in cui i veicoli lasciano entrambi il conitto in maniera cautelativa.

E' stato anche proposto e testato un metodo di identicazione degli avversari basato sulla lettura del loro comportamento all'interno di una serie di conitti successivi. Questo ha presentato risultati sucienti, pur richiedendo molti scontri tra agenti prima di arrivare ad una conclusione, anche se risulta applicabile solo negli scenari riguardanti i veicoli in competizione.

Sono individuabili alcune vie di sviluppo futuro del lavoro che è stato presentato. Un primo ambito riguarda l'applicazione del medesimo algoritmo in scenari diversi da quello degli agenti in movimento, quali quelli già individuati dei sistemi Multi-Core e delle Smart Grid. Per tali ambienti, all'interno di questa tesi, sono già state indicate alcune linee guida per l'adattamento del metodo. Un'altra via di sviluppo è legata all'implementazione su agenti reali di quanto presentato, in modo da studiare il comportamento dell'algoritmo in questi casi . Un terzo ambito riguarda l'aumento del numero di agenti presenti, aspetto che questa tesi aronta nello sviluppo dell'algoritmo, ma non nel caso simulativo.

Capitolo 6

Bibliograa

[1] L. Atzori, A. Iera, G. Morabito, The Internet of Things: a survey, Comput. Netw., 54, pp. 27872805, 2010.

[2] F. Mattern, C. Flörkemeier, From the Internet of Computers to the Internet of Things, Informatik- Spektrum, 2010.

[3] I.F. Akyildiz, D. Pompili, T. Melodia Underwater acoustic sensor networks: research challenges, Ad Hoc Networks, pp. 257279, 2005.

[4] I.F. Akyildiz, D. Pompili, T. Melodia, State of the art protocol research for underwater acoustic sensor networks, ACM Mobile Comput. Commun., pp. 1122, 2007.

[5] L. N. Foner, A security architecture for multi-agent matchmaking ,ICMAS-96, 1996.

[6] Navneet Malpani, Jennifer L. Welch, and Nitin Vaidya, Leader election algorithms for mobile ad hoc networks. In DIALM '00: Proceedings of the 4th international workshop on Discrete algorithms and methods for mobile computing and communications, pages 96103, New York, NY, USA, 2000. ACM Press

[7] Patrone Fioravante, Decisori (Razionali) Interagenti. Una introduzione alla teoria dei giochi, Edizioni PLUS, Pisa, 2006.

[8] Martin J. Osborne, Ariel Rubinstein, A Course in Game Theory, MIT Press, Cambridge, 1994. [9] J. C. Harsanyi , Games with Incomplete Information Played by `Bayesian' Players, Parts I, II, and

III, Management Science, Vol. 14, No. 3, Theory Series, 1967.

[10] Luca Lambertini, Teoria dei Giochi: Storia e Metodologia, thesis, Dipartimento di Scienze Economiche. Università di Bologna, 2000.

[11] P. Remagnino , A. I. Shihab, G. A. Jones Distributed intelligence for multi-camera visual surveil- lance, Pattern Recognition, vol. 34, no. 7, pp.675 -689, 2004.

[12] D.Keil, D. Goldin, Indirect interaction in environments for multi-agent systems, In 2nd Interna- tional Workshop on Environments for Multi-Agent Systems (pp. 6887), 2005.

[13] V.P. Hadeli, C.B. Zamrescu, H.V. Brussel, B.S. Germain, T. Holvoet, E. Steegmans, Self- organising in multi-agent coordination and control using stigmergy, Proceedings of the Inter- national Workshop on Engineering Self- Organising Applications, 2003.

[14] Hadeli, P. Valckenaers, M. Kollingbaum, H. Van Brussel, Multi-Agent Coordination and Control Using Stigmergy Computers in Industry, 53, pp. 7596, 2004.

[15] R. Vidal, O. Shakernia, H. J. Kim, D. H. Shim,S. Sastry. Probabilistic pursuit-evasion games: theo- ry, implementation, and experimental evaluation, Robotics and Automation, IEEE Transactions on, pp. 662-669, 2002.

[16] T. Shima, J. Shinar, Time-Varying Pursuit-Evasion Game Models with Bounded Controls. AIAA Journal of Guidance, Control, and Dynamics, pp. 425-432, 2002.

[17] S. M. LaValle and S. A. Hutchinson Game theory as a unifying structure for a variety of robot tasks, IEEE International Symposium on Intelligent Control, pp.429 -434, 1993.

[18] K. Skrzypczyk, Game theory based target following by a team of robots, Proceedings of Forth International Workshop on Robot Motion and Control, pp. 9196, 2004.

[19] Mehmet Eren Erdo§an, Obstacle Avoidance for a Game Theoreticaly Controlled Formation of Unmanned Vehicles, MS thesis, University of Pisa, Department of Electrical Systems and Auto- mation, 2011.

[20] K. Skrzypczyk, Game theory based task planning in multi robot systems. International Journal of Simulation, pp. :50-60, 2005.

[21] Y. Meng, K. Cao, Multi-Robot Searching for a Target using Game Theory, Robotics and Appli- cations, 2006.

[22] Y. Meng, Multi-robot searching using game-theory based approach. International Journal of Advanced Robotic Systems, pp. 341-350, 2008.

[23] L. Panait,S. Luke, Cooperative multi-agent learning: The state of the art, Auton. Agents Multi- Agent Syst., vol. 11, no. 3, pp.387 -434, 2005 .

[24] Y. Shoham, K. Leyton-Brown Multiagent Systems, Algorithmic, Game-Theoretic, and Logical Foundations, Cambridge Univ. Press, 2008.

[25] K. Spieser, E. Frazzoli, Cow-Path Games with Asymmetric Information: Life as a Cow Gets Harder, IEEE Conf. on Decision and Control, 2013.

[26] I. Ahmad, S. Ranka, S.U. Khan Using game theory for scheduling tasks on multi-core processors for simultaneous optimization of performance and energy, Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing (IPDPS), pp. 16, 2008

[27] M.A.I. Tsompanas, C. Kachris, G.C. Sirakoulis Optimization of shared-memory multicore systems using game theory and genetic algorithms on cellular automata lattices, IEEE 27th International on Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), pp. 482490, 2013.

[28] A. Mohsenian-Rad, V. Wong, J. Jatskevich, R. Schober, A. Leon-Garcia, Autonomous demand- side management based on game-theoretic energy consumption scheduling for the future smart grid, IEEE Trans. Smart Grid, vol. 1, no. 3, pp.320 -331, 2010.

[29] S. Bu, F. R. Yu, A game-theoretical scheme in the smart grid with demand-side management: To- wards a smart cyber-physical power infrastructure, IEEE Trans. Emerging Topics in Computing, 2013.

[30] W. Saad, H. Zhu, H. Poor and T. Basar, Game-theoretic methods for the smart grid: An overview of microgrid systems, demand-side management, and smart grid communications, IEEE Signal Process. Mag., vol. 29, no. 5, pp.86 -105, 2012.

[31] W.W. Weaver, P.T. Krein Game-theoretic control of small-scale power systems, IEEE Transac- tions on Power Delivery, pp. 15601567, 2009.

[32] P. Smets, Belief functions: The disjunctive rule of combination and the generalized Bayesian theorem, Int. J. Approx. Reason. 9, pp. 135, 1993.

[33] Johann Pfanzagl, Parametric Statistical Theory, De Gruyter Textbook, 1994.

[34] Srihari Govindan, Robert Wilson, A Global Newton Method to Compute Nash Equilibria, Journal of Economic Theory, Volume 110, Issue 1, pp. 6586, 2003.

[35] Ben Blum , Christian R. Shelton , Daphne Koller, A continuation method for Nash equilibria in structured games, Proceedings of the 18th international joint conference on Articial intelligence, pp.757-764, 2003.

[36] Noam Nisan , Tim Roughgarden , Eva Tardos , Vijay V. Vazirani, Algorithmic Game Theory, Cambridge University Press, New York, NY, 2007.

[37] T. Basar, G. J. Olsder, Dynamic Noncooperative Game Theory, SIAM, 1999.

[38] J. Gaschnig. Performance Measurements and Analysis of Certain Search Algorithms. PhD thesis, Carnegie-Mellon University, Dept. of Computer Science, 1979.

Ringraziamenti

Sono molte le persone a cui devo tanto e colgo l'occasione della presente tesi per farlo. Ringrazio la mia famiglia, che mi ha fatto diventare ciò che sono e alla quale dedico questa tesi. Senza il loro supporto, questo e altri traguardi sarebbero stati per me impossibili da raggiungere. Ringrazio le persone che mi hanno supportato e sopportato in questi anni di università, cioè i miei amici più cari, che mi hanno distratto e aiutato nei momenti bassi e con i quali ho festeggiato nei momenti più belli. Ringrazio tutti i docenti che in questi anni, nella mia carriera scolastica, mi hanno fatto scoprire e conoscere il mondo che mi circonda.

Inne, ringrazio la Dott.ssa Lucia Pallottino e il Dott. Simone Nardi, con i quali ho collaborato per la presente tesi. Senza la loro continua spinta nel lavoro e il loro aiuto, questa tesi non sarebbe mai nata.

A voi tutti, grazie di cuore.