{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T05:18:58Z","timestamp":1775193538742,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2021,6,1]],"date-time":"2021-06-01T00:00:00Z","timestamp":1622505600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,2]],"date-time":"2021-06-02T00:00:00Z","timestamp":1622592000000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/R004757\/1"],"award-info":[{"award-number":["EP\/R004757\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Swarm Intell"],"published-print":{"date-parts":[[2021,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Decentralised autonomous systems rely on distributed learning to make decisions and to collaborate in pursuit of a shared objective. For example, in swarm robotics the best-of-<jats:italic>n<\/jats:italic> problem is a well-known collective decision-making problem in which agents attempt to learn the best option out of <jats:italic>n<\/jats:italic> possible alternatives based on local feedback from the environment. This typically involves gathering information about all <jats:italic>n<\/jats:italic> alternatives while then systematically discarding information about all but the best option. However, for applications such as search and rescue in which learning the ranking of options is useful or crucial, best-of-<jats:italic>n<\/jats:italic> decision-making can be wasteful and costly. Instead, we investigate a more general distributed learning process in which agents learn a preference ordering over all of the <jats:italic>n<\/jats:italic> options. More specifically, we introduce a distributed rank learning algorithm based on three-valued logic. We then use agent-based simulation experiments to demonstrate the effectiveness of this model. In this context, we show that a population of agents are able to learn a total ordering over the <jats:italic>n<\/jats:italic> options and furthermore the learning process is robust to evidential noise. To demonstrate the practicality of our model, we restrict the communication bandwidth between the agents and show that this model is also robust to limited communications whilst outperforming a comparable probabilistic model under the same communication conditions.<\/jats:p>","DOI":"10.1007\/s11721-021-00191-9","type":"journal-article","created":{"date-parts":[[2021,6,2]],"date-time":"2021-06-02T19:20:40Z","timestamp":1622661640000},"page":"145-170","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Collective preference learning in the best-of-n problem"],"prefix":"10.1007","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5287-0249","authenticated-orcid":false,"given":"Michael","family":"Crosscombe","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3488-5682","authenticated-orcid":false,"given":"Jonathan","family":"Lawry","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,6,2]]},"reference":[{"key":"191_CR1","doi-asserted-by":"publisher","unstructured":"Baronchelli, A. (2018). The emergence of consensus: A primer. Royal Society Open Science, 5(2), 172189. https:\/\/doi.org\/10.1098\/rsos.172189.","DOI":"10.1098\/rsos.172189"},{"issue":"10","key":"191_CR2","doi-asserted-by":"publisher","first-page":"1137","DOI":"10.1287\/mnsc.28.10.1137","volume":"28","author":"RF Bordley","year":"1982","unstructured":"Bordley, R. F. (1982). A multiplicative formula for aggregating probability assessments. Management Science, 28(10), 1137\u20131148. https:\/\/doi.org\/10.1287\/mnsc.28.10.1137.","journal-title":"Management Science"},{"issue":"1","key":"191_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11721-012-0075-2","volume":"7","author":"M Brambilla","year":"2013","unstructured":"Brambilla, M., Ferrante, E., Birattari, M., & Dorigo, M. (2013). Swarm robotics: A review from the swarm engineering perspective. Swarm Intelligence, 7(1), 1\u201341.","journal-title":"Swarm Intelligence"},{"key":"191_CR4","unstructured":"Brill, M., Elkind, E., Endriss, U., & Grandi, U. (2016). Pairwise diffusion of preference rankings in social networks. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence (IJCAI 2016) (pp. 130\u2013136)."},{"key":"191_CR5","doi-asserted-by":"crossref","unstructured":"Britton, N. F., Franks, N. R., Pratt, S. C., & Seeley, T. D. (2002). Deciding on a new home: How do honeybees agree? In Proceedings: Biological Sciences (Vol. 269(1498), pp. 1383\u20131388).","DOI":"10.1098\/rspb.2002.2001"},{"key":"191_CR6","doi-asserted-by":"crossref","unstructured":"Cho, J., & Swami, A. (2014). Dynamics of uncertain opinions in social networks. In 2014 IEEE Military Communications Conference (pp. 1627\u20131632).","DOI":"10.1109\/MILCOM.2014.267"},{"key":"191_CR7","unstructured":"Crosscombe, M., & Lawry, J. (2021). The impact of network connectivity on collective learning. In Proceedings of the 15th International Symposium on Distributed Autonomous Robotic Systems (DARS). Cham: Springer International Publishing."},{"key":"191_CR8","doi-asserted-by":"crossref","unstructured":"Crosscombe, M., Lawry, J., Hauert, S., & Homer, M. (2017). Robust distributed decision-making in robot swarms: Exploiting a third truth state. In 2017 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS) (pp. 4326\u20134332).","DOI":"10.1109\/IROS.2017.8206297"},{"key":"191_CR9","doi-asserted-by":"crossref","unstructured":"DeGroot, M. H. (1974). Reaching a consensus. Journal of the American Statistical Association, 69(345), 118\u2013121.","DOI":"10.1080\/01621459.1974.10480137"},{"key":"191_CR10","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/j.artint.2019.06.002","volume":"275","author":"I Douven","year":"2019","unstructured":"Douven, I. (2019). Optimizing group learning: An evolutionary computing approach. Artificial Intelligence, 275, 235\u2013251. https:\/\/doi.org\/10.1016\/j.artint.2019.06.002.","journal-title":"Artificial Intelligence"},{"issue":"2","key":"191_CR11","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10670-011-9295-x","volume":"75","author":"I Douven","year":"2011","unstructured":"Douven, I., & Kelp, C. (2011). Truth approximation, social epistemology, and opinion dynamics. Erkenntnis, 75(2), 271. https:\/\/doi.org\/10.1007\/s10670-011-9295-x.","journal-title":"Erkenntnis"},{"key":"191_CR12","doi-asserted-by":"crossref","unstructured":"Hassanzadeh, F. F., Yaakobi, E., Touri, B., Milenkovic, O., & Bruck, J. (2013). Building consensus via iterative voting. In 2013 IEEE International Symposium on Information Theory (pp. 1082\u20131086).","DOI":"10.1109\/ISIT.2013.6620393"},{"issue":"1","key":"191_CR13","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1177\/0278364912468636","volume":"32","author":"S Kernbach","year":"2013","unstructured":"Kernbach, S., H\u00e4be, D., Kernbach, O., Thenius, R., Radspieler, G., Kimura, T., & Schmickl, T. (2013). Adaptive collective decision-making in limited robot swarms without communication. The International Journal of Robotics Research, 32(1), 35\u201355. https:\/\/doi.org\/10.1177\/0278364912468636.","journal-title":"The International Journal of Robotics Research"},{"key":"191_CR14","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/978-3-030-29765-7_25","volume-title":"Symbolic and Quantitative Approaches to Reasoning with Uncertainty","author":"J Lawry","year":"2019","unstructured":"Lawry, J., Crosscombe, M., & Harvey, D. (2019). Epistemic sets applied to best-of-n problems. In G. Kern-Isberner & Z. Ognjanovi\u0107 (Eds.), Symbolic and Quantitative Approaches to Reasoning with Uncertainty (pp. 301\u2013312). Cham: Springer International Publishing."},{"key":"191_CR15","doi-asserted-by":"publisher","unstructured":"Lee, C., Lawry, J., & Winfield, A. (2018a). Combining opinion pooling and evidential updating for multi-agent consensus. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-2018 ), International Joint Conferences on Artificial Intelligence Organization (pp. 347\u2013353), https:\/\/doi.org\/10.24963\/ijcai.2018\/48.","DOI":"10.24963\/ijcai.2018\/48"},{"key":"191_CR16","doi-asserted-by":"crossref","unstructured":"Lee, C., Lawry, J., & Winfield, A. (2018b). Negative updating combined with opinion pooling in the best-of-n problem in swarm robotics. In M. Dorigo, M. Birattari, C. Blum, A. L. Christensen, A. Reina, & V. Trianni (Eds.), Swarm Intelligence, LNCS (Vol. 11172, pp. 97\u2013108). Cham: Springer International Publishing.","DOI":"10.1007\/978-3-030-00533-7_8"},{"key":"191_CR17","unstructured":"Lehrer, K., & Wagner, C. (1981). Rational consensus in science and society: A philosophical and mathematical study. Pallas paperback, Springer Netherlands."},{"issue":"1518","key":"191_CR18","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1098\/rstb.2008.0277","volume":"364","author":"C List","year":"2009","unstructured":"List, C., Elsholtz, C., & Seeley, T. D. (2009). Independence and interdependence in collective decision making: An agent-based model of nest-site choice by honeybee swarms. Philosophical Transactions of the Royal Society B: Biological Sciences, 364(1518), 755\u2013762.","journal-title":"Philosophical Transactions of the Royal Society B: Biological Sciences"},{"key":"191_CR19","doi-asserted-by":"publisher","unstructured":"Parker, C. A. C., & Zhang, H. (2009). Cooperative decision-making in decentralized multiple-robot systems: The best-of-N problem. IEEE\/ASME Transactions on Mechatronics, 14(2), 240\u2013251. https:\/\/doi.org\/10.1109\/TMECH.2009.2014370.","DOI":"10.1109\/TMECH.2009.2014370"},{"issue":"5","key":"191_CR20","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1177\/0278364910397621","volume":"30","author":"CAC Parker","year":"2011","unstructured":"Parker, C. A. C., & Zhang, H. (2011). Biologically inspired collective comparisons by robotic swarms. The International Journal of Robotics Research, 30(5), 524\u2013535. https:\/\/doi.org\/10.1177\/0278364910397621.","journal-title":"The International Journal of Robotics Research"},{"key":"191_CR21","doi-asserted-by":"publisher","unstructured":"Perron, E., Vasudevan, D., & Vojnovi\u0107, M. (2009). Using three states for binary consensus on complete graphs. In Proceedings\u2014IEEE INFOCOM (pp. 2527\u20132535), https:\/\/doi.org\/10.1109\/INFCOM.2009.5062181.","DOI":"10.1109\/INFCOM.2009.5062181"},{"issue":"3\u20134","key":"191_CR22","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/s11721-019-00169-8","volume":"13","author":"J Prasetyo","year":"2019","unstructured":"Prasetyo, J., De Masi, G., & Ferrante, E. (2019). Collective decision making in dynamic environments. Swarm Intelligence, 13(3\u20134), 217\u2013243.","journal-title":"Swarm Intelligence"},{"key":"191_CR23","doi-asserted-by":"publisher","unstructured":"Reina, A., Valentini, G., Fern\u00e1ndez-Oto, C., Dorigo, M., & Trianni, V. (2015). A design pattern for decentralised decision making. PLoS ONE, 10(10), e0140950. https:\/\/doi.org\/10.1371\/journal.pone.0140950.","DOI":"10.1371\/journal.pone.0140950"},{"key":"191_CR24","doi-asserted-by":"publisher","first-page":"052411","DOI":"10.1103\/PhysRevE.95.052411","volume":"95","author":"A Reina","year":"2017","unstructured":"Reina, A., Marshall, J. A. R., Trianni, V., & Bose, T. (2017). Model of the best-of-n nest-site selection process in honeybees. Physical Review, 95, 052411. https:\/\/doi.org\/10.1103\/PhysRevE.95.052411.","journal-title":"Physical Review"},{"issue":"7","key":"191_CR25","doi-asserted-by":"publisher","first-page":"966","DOI":"10.1016\/j.robot.2013.08.006","volume":"62","author":"M Rubenstein","year":"2014","unstructured":"Rubenstein, M., Ahler, C., Hoff, N., Cabrera, A., & Nagpal, R. (2014). Kilobot: A low cost robot with scalable operations designed for collective behaviors. Robotics and Autonomous Systems, 62(7), 966\u2013975.","journal-title":"Robotics and Autonomous Systems"},{"key":"191_CR26","doi-asserted-by":"publisher","unstructured":"Schranz, M., Umlauft, M., Sende, M., & Elmenreich, W. (2020). Swarm robotic behaviors and current applications. Frontiers in Robotics and AI, 7, 36. https:\/\/doi.org\/10.3389\/frobt.2020.00036.","DOI":"10.3389\/frobt.2020.00036"},{"key":"191_CR27","doi-asserted-by":"publisher","first-page":"416","DOI":"10.1007\/s002650000299","volume":"49","author":"TD Seeley","year":"2001","unstructured":"Seeley, T. D., & Buhrman, S. C. (2001). Nest-site selection in honey bees: How well do swarms implement the \u201cbest-of-n\u201d decision rule? Behavioral Ecology and Sociobiology, 49, 416\u2013427.","journal-title":"Behavioral Ecology and Sociobiology"},{"key":"191_CR28","doi-asserted-by":"crossref","unstructured":"Stone, M. (1961). The opinion pool. The Annals of Mathematical Statistics, 32(4), 1339\u20131342.","DOI":"10.1214\/aoms\/1177704873"},{"issue":"1518","key":"191_CR29","doi-asserted-by":"publisher","first-page":"743","DOI":"10.1098\/rstb.2008.0204","volume":"364","author":"DJ Sumpter","year":"2009","unstructured":"Sumpter, D. J., & Pratt, S. C. (2009). Quorum responses and consensus decision making. Philosophical Transactions of the Royal Society B: Biological Sciences, 364(1518), 743\u2013753. https:\/\/doi.org\/10.1098\/rstb.2008.0204.","journal-title":"Philosophical Transactions of the Royal Society B: Biological Sciences"},{"key":"191_CR30","unstructured":"Valentini, G., Hamann, H., & Dorigo, M. (2015). Efficient decision-making in a self-organizing robot swarm: On the speed versus accuracy trade-off. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2015) (pp. 1305\u20131314). Richland, SC: International Foundation for Autonomous Agents and Multiagent Systems."},{"issue":"3","key":"191_CR31","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1007\/s10458-015-9323-3","volume":"30","author":"G Valentini","year":"2016","unstructured":"Valentini, G., Ferrante, E., Hamann, H., & Dorigo, M. (2016). Collective decision with 100 Kilobots: Speed versus accuracy in binary discrimination problems. Autonomous Agents and Multi-Agent Systems, 30(3), 553\u2013580. https:\/\/doi.org\/10.1007\/s10458-015-9323-3.","journal-title":"Autonomous Agents and Multi-Agent Systems"},{"key":"191_CR32","doi-asserted-by":"publisher","unstructured":"Valentini, G., Ferrante, E., & Dorigo, M. (2017). The best-of-n problem in robot swarms: Formalization, state of the art, and novel perspectives. Frontiers in Robotics and AI, 4, 9. https:\/\/doi.org\/10.3389\/frobt.2017.00009.","DOI":"10.3389\/frobt.2017.00009"}],"container-title":["Swarm Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11721-021-00191-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11721-021-00191-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11721-021-00191-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,26]],"date-time":"2021-06-26T14:10:33Z","timestamp":1624716633000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11721-021-00191-9"}},"subtitle":["From best-of-n to ranking n"],"short-title":[],"issued":{"date-parts":[[2021,6]]},"references-count":32,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2021,6]]}},"alternative-id":["191"],"URL":"https:\/\/doi.org\/10.1007\/s11721-021-00191-9","relation":{},"ISSN":["1935-3812","1935-3820"],"issn-type":[{"value":"1935-3812","type":"print"},{"value":"1935-3820","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6]]},"assertion":[{"value":"24 April 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 June 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}