I sistemi multi-agente e gli algoritmi di consenso

Giacomo Como; Fabio Fagnani; Sandro Zampieri

La Matematica nella Società e nella Cultura. Rivista dell'Unione Matematica Italiana (2012)

  • Volume: 5, Issue: 1, page 1-29
  • ISSN: 1972-7356

Abstract

top
Recently, multi-agent systems have become a central study topic in many different disciplines including biology, engineering, physics, and social science. This has led to the emergence of large and constantly growing interdisciplinary research field, known as network science. The analysis of the mathematical models describing such systems has achieved significant results, but remains mostly an open research field, where many fundamental breakthroughs are expected in the next years. Such analysis is especially motivated by the quest for the development of tools for control and design of such systems. In this paper, we deal with consensus algorithms, an important example of design of multi-agent systems that has been inspired by the dynamics of cooperative systems in natural and social sciences.

How to cite

top

Como, Giacomo, Fagnani, Fabio, and Zampieri, Sandro. "I sistemi multi-agente e gli algoritmi di consenso." La Matematica nella Società e nella Cultura. Rivista dell'Unione Matematica Italiana 5.1 (2012): 1-29. <http://eudml.org/doc/291252>.

@article{Como2012,
abstract = {Recentemente, i sistemi multi-agente sono diventati oggetti di studio in molte differenti discipline, quali la biologia, l'ingegneria, la fisica, l'economia e le scienze sociali, facendo emergere un campo di ricerca interdisciplinare vasto ed in costante espansione, la scienza delle reti. L'analisi dei modelli matematici che descrivono tali sistemi ha raggiunto risultati significativi, ma rimane per lo più un campo di ricerca molto aperto, nel quale è facile prevedere importanti sviluppi nei prossimi anni. Tale analisi è motivata in particolare dalla necessità di sviluppare strumenti per il controllo ed il progetto di tali sistemi. In questo articolo ci occupiamo degli algoritmi di consenso, un importante esempio di progettazione di sistemi multi-agente che ha tratto spunto dalla dinamica di sistemi di cooperazione esistenti nelle scienze naturali e sociali.},
author = {Como, Giacomo, Fagnani, Fabio, Zampieri, Sandro},
journal = {La Matematica nella Società e nella Cultura. Rivista dell'Unione Matematica Italiana},
language = {ita},
month = {4},
number = {1},
pages = {1-29},
publisher = {Unione Matematica Italiana},
title = {I sistemi multi-agente e gli algoritmi di consenso},
url = {http://eudml.org/doc/291252},
volume = {5},
year = {2012},
}

TY - JOUR
AU - Como, Giacomo
AU - Fagnani, Fabio
AU - Zampieri, Sandro
TI - I sistemi multi-agente e gli algoritmi di consenso
JO - La Matematica nella Società e nella Cultura. Rivista dell'Unione Matematica Italiana
DA - 2012/4//
PB - Unione Matematica Italiana
VL - 5
IS - 1
SP - 1
EP - 29
AB - Recentemente, i sistemi multi-agente sono diventati oggetti di studio in molte differenti discipline, quali la biologia, l'ingegneria, la fisica, l'economia e le scienze sociali, facendo emergere un campo di ricerca interdisciplinare vasto ed in costante espansione, la scienza delle reti. L'analisi dei modelli matematici che descrivono tali sistemi ha raggiunto risultati significativi, ma rimane per lo più un campo di ricerca molto aperto, nel quale è facile prevedere importanti sviluppi nei prossimi anni. Tale analisi è motivata in particolare dalla necessità di sviluppare strumenti per il controllo ed il progetto di tali sistemi. In questo articolo ci occupiamo degli algoritmi di consenso, un importante esempio di progettazione di sistemi multi-agente che ha tratto spunto dalla dinamica di sistemi di cooperazione esistenti nelle scienze naturali e sociali.
LA - ita
UR - http://eudml.org/doc/291252
ER -

References

top
  1. ACEMOGLU, D. - OZDAGLAR, A., Opinion dynamics and learning in social networks, Dynamic Games and Applications, 1 (1) (2011), 3-49. Zbl1214.91091MR2800784DOI10.1007/s13235-010-0004-1
  2. ACEMOGLU, D. - COMO, G. - FAGNANI, F. - OZDAGLAR, A., Opinion fluctuations and disagreement in social networks, Mathematics of Operation Research, sottomesso (2011). Zbl1297.91130MR3029476DOI10.1287/moor.1120.0570
  3. ALON, N. - ROICHMAN, Y., Random Cayley graphs and expanders, Random Structures & Algorithms, 5 (2) (1994), 271-284. Zbl0798.05048MR1262979DOI10.1002/rsa.3240050203
  4. AXELROD, R., The dissemination of culture, J. of Conflict Resolution, 42 (2) (1997), 203-226. 
  5. BAI, H. - ARKAC, M. - WEN, J., Cooperative control design: a systematic, passivity-based approach, Communications in Control and Engineering, Springer, New York, 2011. MR3222616DOI10.1007/978-1-4614-0014-1
  6. BOYD, S. - GHOSH, A. - PRABHAKAR, B. - SHAH, D., Randomized gossip algorithms, IEEE Transactions on Information Theory, 52 (6) (2006), 2508-2530. Zbl1283.94005MR2238556DOI10.1109/TIT.2006.874516
  7. BOYD, S. - PARIKH, N. - CHU, E. - PELEATO, B. - ECKSTEIN, J., Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3 (1) (2011), 1-124. 
  8. CAO, M. - SPIELMAN, D. A. - YEH, E. M., Accelerated gossip algorithms for distributed computation, in Proceedings of the 44th Annual Allerton Conference on Communication, Control, and Computation, Monticello, IL, USA, Sep. 2006. 
  9. CARLI, R. - FAGNANI, F. - SPERANZON, A. - ZAMPIERI, S., Communication constraints in the average consensus problem, Automatica, 44 (3) (2008), 671-684. Zbl1283.93014MR2527065DOI10.1016/j.automatica.2007.07.009
  10. CARLI, R. - ZAMPIERI, S., Networked clock synchronization based on second order linear consensus algorithms, IEEE Conference on Decision and Control, 2010. MR3164884DOI10.1109/TAC.2013.2283742
  11. Robustness of trans European gas networks, Physical Review E, 80 (2009), 016-106. 
  12. CASTELLANO, C. - FORTUNATO, S. - LORETO, V., Statistical physics of social dynamics, Review of Modern Physics, 81 (2009), 591-646. 
  13. CHIANG, M. - LOW, S. H. - CALDERBANK, A. R. - DOYLE, J. C., Layering as optimization decomposition: A mathematical theory of network architectures, Proceedings of the IEEE, 95 (1) (2007), 255-312. 
  14. CORTÉS, J. - MARTINEZ, S. - BULLO, F., Robust rendezvous for mobile autonomous agents via proximity graphs in arbitrary dimensions, IEEE Transactions on Automatic Control, 51 (8) (2006), 1289-1298. Zbl1366.93400MR2248722DOI10.1109/TAC.2006.878713
  15. CUCKER, F. - SMALE, S., Emergent behavior in flocks, IEEE Transactions on Automatic Control, 52 (5) (2007), 852-862. Zbl1366.91116MR2324245DOI10.1109/TAC.2007.895842
  16. CURRARINI, S. - JACKSON, M. O. - PAOLO, P., An economic model of friendship: homophily, minorities, and segregation, Econometrica, 77 (4) (2009), 1003-1045. Zbl1183.91150MR2547067DOI10.3982/ECTA7528
  17. DEFFUANT, G. - NEAU, D. - AMBLARD, F. - WEISBUCH, G., Mixing beliefs among interacting agents, Advances in Complex Systems, 3 (2000), 87-98. 
  18. FAGNANI, F. - ZAMPIERI, S., Randomized consensus algorithms over large scale networks, IEEE Journal on Selected Areas of Communications, 26 (2008), 634-649. 
  19. FAX, J. A. - MURRAY, R. M., Information flow and cooperative control of vehicle formations, IEEE Transaction on Automatic Control, 49 (9) (2004), 1465-1476. Zbl1365.90056MR2086912DOI10.1109/TAC.2004.834433
  20. FRANCESCHELLI, M. - GIUA, A. - SEATZU, C., Consensus on the average on arbitrary strongly connected digraphs based on broadcast gossip algorithms, 1st IFAC Workshop on Estimation and Control of Networked Systems, Venice, Italy, Sett. 2009. 
  21. GALTON, F., Vox populi, Nature, 75 (1907), 450-451. 
  22. GANTMACHER, F. R., The theory of matrices, Chelsea Publishers, New York, 1959. Zbl0085.01001MR107649
  23. GOLUB, B. - JACKSON, M. O., Naïve learning in social networks and the wisdom of crowds, American Economic Journal: Microeconomics, 2 (1) (2010), 112-149. MR3629223DOI10.1016/j.jmp.2017.01.001
  24. JADBABAIE, A. - LIN, J. - MORSE, A. S., Coordination of groups of mobile autonomous agents using nearest neighbor rules, IEEE Transactions on Automatic Control, 48 (6) (2003), 988-1001. Zbl1364.93514MR1986266DOI10.1109/TAC.2003.812781
  25. JACKSON, M. O., Social and economic networks, Princeton University Press, 2008. Zbl1149.91051MR2435744
  26. JI, M. - FERRARI-TRECATE, G. - EGERSTEDT, M. - BUFFA, A., Containment control in mobile networks, IEEE Transactions on Automatic Control, 53 (8) (2008), 1972-1975. Zbl1367.93398MR2454767DOI10.1109/TAC.2008.930098
  27. KANSKY, K. J., Structure of transportation networks: relationships between network geometry and regional characteristics, University of Chicago, 1963. 
  28. KRAUSE, U., A discrete nonlinear and non-autonomous model of consensus formation, Communications in Difference Equations, pp. 227-236, S. Elaydi, G. Ladas, J. Popenda, and J. Rakowski editors, Gordon and Breach, Amsterdam, 2000. Zbl0988.39004MR1792007
  29. LORENZ, J., Continuous opinion dynamics under bounded confidence: A survey, International Journal of Modern Physics C, 18 (12) (2007), 1819-1838. Zbl1151.91076
  30. MACKAY, D. J. C., Sustainable energy: without the hot air, UIT Cambridge LTD, 2009. 
  31. MOREAU, L., Stability of multiagent systems with time-dependent communication links, IEEE Transactions on Automatic Control, 50 (2005), 169-182. Zbl1365.93268MR2116423DOI10.1109/TAC.2004.841888
  32. MUTHUKRISHNAN, S. - GHOSH, B. - SCHULTZ, M. H., First- and second-order diffusive methods for rapid, coarse, distributed load balancing, Theory of Computing Systems, 31 (1998), 331-354. Zbl0904.68137MR1628784DOI10.1007/s002240000092
  33. NEWMAN, M. E. J., Networks: an introduction, Oxford University Press, 2010. Zbl1195.94003MR2676073DOI10.1093/acprof:oso/9780199206650.001.0001
  34. NIYOGI, P., The Computational nature of language, learning, and evolution, MIT Press, 2006. MR2330651
  35. OLFATI-SABER, R. - FAX, J. A. - MURRAY, R. M., Consensus and cooperation in networked multi-agent systems, Proceedings of the IEEE, 95 (1) (2007), 215-233. Zbl1376.68138
  36. RODRÌGUEZ-ITURBE, I. - RINALDO, A., Fractal river basins: chance and self-organization, Cambridge University Press, 1997. 
  37. SCARDOVI, L. - SEPULCHRE, R., Synchronization in networks of identical linear systems, Automatica, 45 (2009), 2557-2562. Zbl1183.93054MR2889312DOI10.1016/j.automatica.2009.07.006
  38. STROGATZ, S. H., From Kuramoto to Crawford: Exploring the onset of synchronization in populations of coupled oscillators, Physica D: Nonlinear Phenomena, 143 (1-4) (2000), 1-20. MR1783382DOI10.1016/S0167-2789(00)00094-4
  39. STROGATZ, S. H., Sync: The emerging science of spontaneous order, Hyperion, 2003. MR2394754
  40. SUROWIECKI, J., The wisdom of crowds: why the many are smarter than the few and how collective wisdom shapes business, economies, societies and nations, Little, Brown, 2004. Traduzione italiana: La saggezza della folla, Fusi Orari, 2007. 
  41. TSITSIKLIS, J., Problems in decentralized decision making and computation, Ph. D. thesis, Department of EECS, MIT, 1984. 
  42. VICSEK, T. - CZIRŒK, A. - BEN-JACOB, E. - SHOCHET, O., Novel type of phase transition in a system of self-driven particles, Physical Review Letters, 75 (1995), 1226-1229. MR3363421DOI10.1103/PhysRevLett.75.1226
  43. WOLFERS, J. - ZITZEWITZ, E., Prediction markets, Journal of Economic Perspectives, 18 (2) (2004), 107-126. 
  44. WARDROP, J. G., Some theoretical aspects of road traffic research, ICE Proceedings: Engineering Divisions, 1 (1952), 45-53. 
  45. WIELAND, P. - SEPULCHRE, R. - ALLGÖVER, F., An internal model principle is necessary and sufficient for linear output synchronization, Automatica, 47 (2011), 2557-2562. MR2878379DOI10.1016/j.automatica.2011.01.081
  46. XIAO, L. - BOYD, S. - LALL, S., A scheme for robust distributed sensor fusion based on average consensus, International Conference on Information Processing in Sensor Networks (2005), 63-70. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.