[en] A multiagent system should be capable of fast and flexible decision-making to successfully manage the uncertainty, variability, and dynamic change encountered when operating in the real world. Decision-making is fast if it breaks indecision as quickly as indecision becomes costly. This requires fast divergence away from indecision in addition to fast convergence to a decision. Decision-making is flexible if it adapts to signals important to successful operation, even if they are weak or rare. This requires tunable sensitivity to input for modulating regimes in which the system is ultrasensitive and in which it is robust. Nonlinearity and feedback in the decision-making process are necessary to meeting these requirements. This article reviews theoretical principles, analytical results, related literature, and applications of decentralized nonlinear opinion dynamics that enable fast and flexible decision-making among multiple options for multiagent systems interconnected by communication and belief system networks. The theory and tools provide a principled and systematic means for designing and analyzing decision-making in systems ranging from robot teams to social networks. Expected final online publication date for the Annual Review of Control, Robotics, and Autonomous Systems, Volume 7 is May 2024. Please see http://www.annualreviews.org/page/journal/pubdates for revised estimates.
Disciplines :
Engineering, computing & technology: Multidisciplinary, general & others
Author, co-author :
Leonard, Naomi Ehrich; Department of Mechanical and Aerospace Engineering, Princeton University, Princeton, New Jersey, USA,
Bizyaeva, Anastasia; Department of Mechanical Engineering and National Science Foundation AI Institute in Dynamic Systems, University of Washington, Seattle, Washington, USA,
Franci, Alessio ; Université de Liège - ULiège > Département d'électricité, électronique et informatique (Institut Montefiore) > Brain-Inspired Computing ; WEL Research Institute, Wavre, Belgium
Language :
English
Title :
Fast and Flexible Multiagent Decision-Making
Publication date :
28 November 2023
Journal title :
Annual Review of Control, Robotics, and Autonomous Systems
Ren W, Atkins E. 2007. Distributed multi-vehicle coordinated control via local information exchange. Int. J. Robust Nonlinear Control 17(10–11):1002–33
Rios-Torres J, Malikopoulos AA. 2016. Automated and cooperative vehicle merging at highway on-ramps. IEEE Trans. Intell. Transp. Syst. 18(4):780–89
Vilca J, Adouane L, Mezouar Y. 2018. Stable and flexible multi-vehicle navigation based on dynamic inter-target distance matrix. IEEE Trans. Intell. Transp. Syst. 20(4):1416–31
Fiorelli E, Leonard NE, Bhatta P, Paley DA, Bachmayer R, Fratantoni DM. 2006. Multi-AUV control and adaptive sampling in Monterey Bay. IEEE J. Ocean. Eng. 31(4):935–48
Leonard NE, Paley DA, Lekien F, Sepulchre R, Fratantoni DM, Davis RE. 2007. Collective motion, sensor networks, and ocean sampling. Proc. IEEE 95(1):48–74
Hu J, Niu H, Carrasco J, Lennox B, Arvin F. 2022. Fault-tolerant cooperative navigation of networked UAV swarms for forest fire monitoring. Aerosp. Sci. Technol. 123:107494
Liu Y, Nejat G. 2013. Robotic urban search and rescue: a survey from the control perspective. J. Intell. Robot. Syst. 72:147–65
Arnold RD, Yamaguchi H, Tanaka T. 2018. Search and rescue with autonomous flying robots through behavior-based cooperative intelligence. J. Int. Humanit. Action 3(1):18
Drew DS. 2021. Multi-agent systems for search and rescue applications. Curr. Robot. Rep. 2:189–200
Kolling A, Walker P, Chakraborty N, Sycara K, Lewis M. 2015. Human interaction with robot swarms: a survey. IEEE Trans. Human-Mach. Syst. 46(1):9–26
Wang X, Wang Y. 2017. Co-design of control and scheduling for human–swarm collaboration systems based on mutual trust. In Trends in Control and Decision-Making for Human–Robot Collaboration Systems, ed. Y Wang, F Zhang, pp. 387–413. Cham, Switz.: Springer
Ajoudani A, Zanchettin AM, Ivaldi S, Albu-Schäffer A, Kosuge K, Khatib O. 2018. Progress and prospects of the human–robot collaboration. Auton. Robots 42:957–75
Gerkey BP, Matarić MJ. 2004. A formal analysis and taxonomy of task allocation in multi-robot systems. Int. J. Robot. Res. 23(9):939–54
Korsah GA, Stentz A, Dias MB. 2013. A comprehensive taxonomy for multi-robot task allocation. Int. J. Robot. Res. 32(12):1495–512
Khamis A, Hussein A, Elmogy A. 2015. Multi-robot task allocation: a review of the state-of-the-art. In Cooperative Robots and Sensor Networks, ed. A Koubâa, J Martínez-de Dios, pp. 31–51. Cham, Switz.: Springer
Valentini G, Ferrante E, Dorigo M. 2017. The best-of-n problem in robot swarms: formalization, state of the art, and novel perspectives. Front. Robot. AI 4:9
Dörfler F, Chertkov M, Bullo F. 2013. Synchronization in complex oscillator networks and smart grids. PNAS 110(6):2005–10
Rinaldi S, Della Giustina D, Ferrari P, Flammini A, Sisinni E. 2016. Time synchronization over heterogeneous network for smart grid application: design and characterization of a real case. Ad Hoc Netw. 50:41–57
Chu CC, Iu HHC. 2017. Complex networks theory for modern smart grid applications: a survey. IEEE J. Emerg. Sel. Top. Circuits Syst. 7(2):177–91
Conradt L, Roper TJ. 2005. Consensus decision making in animals. Trends Ecol. Evol. 20(8):449–56
Couzin ID, Krause J, Franks NR, Levin SA. 2005. Effective leadership and decision-making in animal groups on the move. Nature 433(7025):513–16
Sumpter DJ, Krause J, James R, Couzin ID, Ward AJ. 2008. Consensus decision making by fish. Curr. Biol. 18(22):1773–77
Pagliara R, Gordon DM, Leonard NE. 2018. Regulation of harvester ant foraging as a closed-loop excitable system. PLOS Comput. Biol. 14(12):e1006200
Sridhar VH, Li L, Gorbonos D, Nagy M, Schell BR, et al. 2021. The geometry of decision-making in individuals and collectives. PNAS 118(50):e2102157118
Papadopoulou M, Fürtbauer I, O’Bryan LR, Garnier S, Georgopoulou DG, et al. 2023. Dynamics of collective motion across time and species. Philos. Trans. R. Soc. B 378(1874):20220068
Zeng L, Skinner SO, Zong C, Sippy J, Feiss M, Golding I. 2010. Decision making at a subcellular level determines the outcome of bacteriophage infection. Cell 141(4):682–91
Weitz JS, Mileyko Y, Joh RI, Voit EO. 2008. Collective decision making in bacterial viruses. Biophys. J. 95(6):2673–80
Balázsi G, Van Oudenaarden A, Collins JJ. 2011. Cellular decision making and biological noise: from microbes to mammals. Cell 144(6):910–25
Stewart I, Elmhirst T, Cohen J. 2003. Symmetry-breaking as an origin of species. In Bifurcation, Symmetry and Patterns, ed. J Buescu, SBSD Castro, AP da Silva Dias, IS Labouriau, pp. 3–54. Basel: Birkhäuser
Waters CM, Bassler BL. 2005. Quorum sensing: cell-to-cell communication in bacteria. Annu. Rev. Cell Dev. Biol. 21:319–46
Bogacz R. 2007. Optimal decision-making theories: linking neurobiology with behaviour. Trends Cogn. Sci. 11(3):118–25
Deco G, Rolls ET, Albantakis L, Romo R. 2013. Brain mechanisms for perceptual and reward-related decision-making. Prog. Neurobiol. 103:194–213
Collins AG, Shenhav A. 2022. Advances in modeling learning and decision-making in neuroscience. Neuropsychopharmacology 47(1):104–18
Fontan A, Altafini C. 2021. A signed network perspective on the government formation process in parliamentary democracies. Sci. Rep. 11(1):5134
Siegenfeld AF, Bar-Yam Y. 2020. Negative representation and instability in democratic elections. Nat. Phys. 16(2):186–90
Bokhari A, Cliff D. 2022. Studying narrative economics by adding continuous-time opinion dynamics to an agent-based model of co-evolutionary adaptive financial markets. SSRN 4316574. https://doi.org/10.2139/ssrn.4316574
Zha Q, Kou G, Zhang H, Liang H, Chen X, et al. 2020. Opinion dynamics in finance and business: a literature review and research opportunities. Financ. Innov. 6:44
Morrison M, Kutz JN, Gabbay M. 2022. Transitions between peace and systemic war as bifurcations in a signed network dynamical system. Netw. Sci. 11(3):458–501
Baumann F, Lorenz-Spreen P, Sokolov IM, Starnini M. 2020. Modeling echo chambers and polarization dynamics in social networks. Phys. Rev. Lett. 124(4):048301
Santos FP, Lelkes Y, Levin SA. 2021. Link recommendation algorithms and dynamics of polarization in online social networks. PNAS 118(50):e2102141118
Leonard NE, Lipsitz K, Bizyaeva A, Franci A, Lelkes Y. 2021. The nonlinear feedback dynamics of asymmetric political polarization. PNAS 118(50):e2102149118
Gajewski ŁG, Sienkiewicz J, Hołyst JA. 2022. Transitions between polarization and radicalization in a temporal bilayer echo-chamber model. Phys. Rev. E 105(2):024125
Levin SA, Weber EU. 2023. Polarization and the psychology of collectives. Perspect. Psychol. Sci. https://doi.org/10.1177/17456916231186614
Leung HCH, Li Z, She B, Paré PE. 2023. Leveraging opinions and vaccination to eradicate networked epidemics. In 2023 European Control Conference. Piscataway, NJ: IEEE. https://doi.org/10.23919/ECC57647.2023.10178234
Yanga L, Constantino SM, Grenfell BT, Weber EU, Levin SA, Vasconcelos VV. 2022. Sociocultural determinants of global mask-wearing behavior. PNAS 119(41):e2213525119
Constantino SM, Weber EU. 2021. Decision-making under the deep uncertainty of climate change: the psychological and political agency of narratives. Curr. Opin. Psychol. 42(41):151–59
Converse PE. 2006. The nature of belief systems in mass publics (1964). Crit. Rev. 18(1–3):1–74
Seeley TD, Passino K, Visscher K. 2006. Group decision making in honey bee swarms. Am. Sci. 94(3):220–29
Seeley TD, Visscher PK, Schlegel T, Hogan PM, Franks NR, Marshall JAR. 2012. Stop signals provide cross inhibition in collective decision-making by honeybee swarms. Science 335(6064):108–11
Guckenheimer J, Holmes P. 1983. Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields. New York: Springer
Golubitsky M, Schaeffer DG. 1985. Singularities and Groups in Bifurcation Theory. New York: Springer
Strogatz S. 1994. Nonlinear Dynamics and Chaos. Boca Raton, FL: CRC
Golubitsky M, Stewart I, Shaeffer D. 1988. Singularities and Groups in Bifurcation Theory, Vol. 2. New York: Springer
Golubitsky M, Stewart I. 2002. The Symmetry Perspective. Basel: Birkhäuser
Elmhirst T. 2004. SN-equivariant symmetry-breaking bifurcations. Int. J. Bifurc. Chaos 14(3):1017–36
Franci A, Golubitsky M, Stewart I, Bizyaeva A, Leonard NE. 2023. Breaking indecision in multiagent, multioption dynamics. SIAM J. Appl. Dyn. Syst. 22(3):1780–817
Golubitsky M, Stewart I. 2023. Dynamics and Bifurcation in Networks: Theory and Applications of Coupled Differential Equations. Philadelphia: Soc. Ind. Appl. Math.
Wilson HR, Cowan JD. 1972. Excitatory and inhibitory interactions in localized populations of model neurons. Biophys. J. 12(1):1–24
Wilson HR, Cowan JD. 1973. A mathematical theory of the functional dynamics of cortical and thalamic nervous tissue. Kybernetik 13(2):55–80
Hopfield JJ. 1982. Neural networks and physical systems with emergent collective computational abilities. PNAS 79(8):2554–58
Hopfield JJ. 1984. Neurons with graded response have collective computational properties like those of two-state neurons. PNAS 81(10):3088–92
Hodgkin AL, Huxley AF. 1952. A quantitative description of membrane current and its application to conduction and excitation in nerve. J. Physiol. 117(4):500–44
Dalege J, Galesic M, Olsson H. 2023. Networks of beliefs: an integrative theory of individual-and social-level belief dynamics. OSF Preprints 368jz. https://doi.org/10.31219/osf.io/368jz
Gardner TS, Cantor CR, Collins JJ. 2000. Construction of a genetic toggle switch in Escherichia coli. Nature 403(6767):339–42
Smith HL. 2008. Monotone Dynamical Systems: An Introduction to the Theory of Competitive and Cooperative Systems. Providence, RI: Am. Math. Soc.
Elhashash A, Szyld D. 2008. On general matrices having the Perron-Frobenius property. Electron. J. Linear Algebra 17:389–413
DeGroot MH. 1974. Reaching a consensus. J. Am. Stat. Assoc. 69(345):118–21
Abelson RP. 1964. Mathematical models of the distribution of attitudes under controversy. In Contributions to Mathematical Psychology, ed. N Frederiksen, H Gulliksen, pp. 142–60. New York: Holt, Rinehart, & Winston
Olfati-Saber R, Fax JA, Murray RM. 2007. Consensus and cooperation in networked multi-agent systems. Proc. IEEE 95(1):215–33
Garin F, Schenato L. 2010. A survey on distributed estimation and control applications using linear consensus algorithms. In Networked Control Systems, ed. A Bemporad, M Heemels, M Johansson, pp. 75–107. London: Springer
Cao Y, Yu W, Ren W, Chen G. 2012. An overview of recent progress in the study of distributed multiagent coordination. IEEE Trans. Ind. Inform. 9(1):427–38
Qin J, Ma Q, Shi Y, Wang L. 2016. Recent advances in consensus of multi-agent systems: a brief survey. IEEE Trans. Ind. Electron. 64(6):4972–83
Mei W, Bullo F, Chen G, Hendrickx JM, Dörfler F. 2022. Micro-foundation of opinion dynamics: rich consequences of the weighted-median mechanism. Phys. Rev. Res. 4(2):023213
Friedkin NE, Johnsen EC. 1990. Social influence and opinions. J. Math. Sociol. 15(3–4):193–206
Friedkin NE, Johnsen EC. 1999. Social influence networks and opinion change. In Advances in Group Processes, Vol. 16, ed. SR Thye, EJ Lawler, MW Macy, HA Walker, pp. 1–29. Stamford, CT: JAI
Friedkin NE, Bullo F. 2017. How truth wins in opinion dynamics along issue sequences. PNAS 114(43):11380–85
Parsegov SE, Proskurnikov AV, Tempo R, Friedkin NE. 2017. Novel multidimensional models of opinion dynamics in social networks. IEEE Trans. Autom. Control 62(5):2270–85
Jia P, MirTabatabaei A, Friedkin NE, Bullo F. 2015. Opinion dynamics and the evolution of social power in influence networks. SIAM Rev. 57(3):367–97
Friedkin NE. 2011. A formal theory of reflected appraisals in the evolution of power. Adm. Sci. Q. 56:501–29
Altafini C. 2013. Consensus problems on networks with antagonistic interactions. IEEE Trans. Autom. Control 58(4):935–46
Proskurnikov AV, Matveev AS, Cao M. 2015. Opinion dynamics in social networks with hostile camps: consensus versus polarization. IEEE Trans. Autom. Control 61(6):1524–36
Zhang H, Chen J. 2017. Bipartite consensus of multi-agent systems over signed graphs: state feedback and output feedback control approaches. Int. J. Robust Nonlinear Control 27(1):3–14
Hegselmann R, Krause U. 2002. Opinion dynamics and bounded confidence models, analysis, and simulations. J. Artif. Soc. Soc. Simul. 5(3):121–32
Lorenz J. 2006. Continuous opinion dynamics of multidimensional allocation problems under bounded confidence: More dimensions lead to better chances for consensus. Eur. J. Econ. Soc. Syst. 19:213–27
Dandekar P, Goel A, Lee DT. 2013. Biased assimilation, homophily, and the dynamics of polarization. PNAS 110(15):5791–96
Xia W, Ye M, Liu J, Cao M, Sun XM. 2020. Analysis of a nonlinear opinion dynamics model with biased assimilation. Automatica 120:109113
Pais D, Hogan PM, Schlegel T, Franks NR, Leonard NE. 2013. A mechanism for value-sensitive decision-making. PLOS ONE 8(9):e73216
Reina A, Marshall JA, Trianni V, Bose T. 2017. Model of the best-of-N nest-site selection process in honeybees. Phys. Rev. E 95(5):052411
Gray R, Franci A, Srivastava V, Leonard NE. 2018. Multiagent decision-making dynamics inspired by honeybees. IEEE Trans. Control Netw. Syst. 5(2):793–806
Usher M, McClelland JL. 2001. The time course of perceptual choice: the leaky, competing accumulator model. Psychol. Rev. 108(3):550–92
Brown E, Holmes P. 2001. Modeling a simple choice task: stochastic dynamics of mutually inhibitory neural groups. Stochast. Dyn. 1(2):159–91
Bogacz R, Usher M, Zhang J, McClelland JL. 2007. Extending a biologically inspired model of choice: multi-alternatives, nonlinearity and value-based multidimensional choice. Philos. Trans. R. Soc. B 362(1485):1655–70
Angeli D, Sontag ED. 2003. Monotone control systems. IEEE Trans. Autom. Control 48(10):1684–98
Altafini C. 2012. Dynamics of opinion forming in structurally balanced social networks. PLOS ONE 7(6):e38135
Bizyaeva A, Amorim G, Santos M, Franci A, Leonard NE. 2022. Switching transformations for decentralized control of opinion patterns in signed networks: application to dynamic task allocation. IEEE Control Syst. Lett. 6:3463–68
Bizyaeva A, Sorochkin T, Franci A, Leonard NE. 2021. Control of agreement and disagreement cascades with distributed inputs. In 2021 60th IEEE Conference on Decision and Control, pp. 4994–99. Piscataway, NJ: IEEE
Franci A, Bizyaeva A, Park S, Leonard NE. 2021. Analysis and control of agreement and disagreement opinion cascades. Swarm Intell. 15:47–82
Qin J, Fu W, Zheng WX, Gao H. 2016. On the bipartite consensus for generic linear multiagent systems with input saturation. IEEE Trans. Cybernet. 47(8):1948–58
Franci A, Srivastava V, Leonard NE. 2015. A realization theory for bio-inspired collective decision-making. arXiv:1503.08526 [math.OC]
Gray R, Franci A, Srivastava V, Leonard NE. 2017. An agent-based framework for bio-inspired, value-sensitive decision-making. IFAC-PapersOnLine 50(1):8238–43
Abara PU, Ticozzi F, Altafini C. 2017. Spectral conditions for stability and stabilization of positive equilibria for a class of nonlinear cooperative systems. IEEE Trans. Autom. Control 63(2):402–17
Fontan A, Altafini C. 2017. Multiequilibria analysis for a class of collective decision-making networked systems. IEEE Trans. Control Netw. Syst. 5(4):1931–40
Bizyaeva A, Matthews A, Franci A, Leonard NE. 2021. Patterns of nonlinear opinion formation on networks. In 2021 American Control Conference, pp. 2739–44. Piscataway, NJ: IEEE
Bizyaeva A, Franci A, Leonard NE. 2022. Nonlinear opinion dynamics with tunable sensitivity. IEEE Trans. Autom. Control 68(3):1415–30
Bizyaeva A, Franci A, Leonard NE. 2023. Sustained oscillations in multi-topic belief dynamics over signed networks. In 2023 American Control Conference, pp. 4296–301. Piscataway, NJ: IEEE
Bizyaeva A, Franci A, Leonard NE. 2023. Multi-topic belief formation through bifurcations over signed social networks. arXiv:2308.02755 [physics.soc-ph]
Park S, Bizyaeva A, Kawakatsu M, Franci A, Leonard NE. 2022. Tuning cooperative behavior in games with nonlinear opinion dynamics. IEEE Control Syst. Lett. 6:2030–35
Musslick S, Bizyaeva A, Agaron S, Leonard NE, Cohen JD. 2019. Stability-flexibility dilemma in cognitive control: a dynamical system perspective. In Proceedings of the 41st Annual Meeting of the Cognitive Science Society, pp. 2420–26. Seattle, WA: Cogn. Sci. Soc.
Nabet B, Leonard NE, Couzin ID, Levin SA. 2009. Dynamics of decision making in animal group motion. J. Nonlinear Sci. 19:399–435
Cathcart C, Santos M, Park S, Leonard NE. 2023. Proactive opinion-driven robot navigation around human movers. In 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 4052–58. Piscataway, NJ: IEEE
Hu H, Nakamura K, Hsu KC, Leonard NE, Fisac JF. 2023. Emergent coordination through game-induced nonlinear opinion dynamics. In 2023 IEEE 62nd Conference on Decision and Control, pp. 8122–29. Piscataway, NJ: IEEE
Sepulchre R, Drion G, Franci A. 2019. Control across scales by positive and negative feedback. Annu. Rev. Control Robot. Auton. Syst. 2:89–113
Douglas R, Martin K. 2007. Mapping the matrix: the ways of neocortex. Neuron 56(2):226–38
Riquelme JL, Hemberger M, Laurent G, Gjorgjieva J. 2023. Single spikes drive sequential propagation and routing of activity in a cortical network. eLife 12:e79928
