Discrete collective estimation in swarm robotics with distributed Bayesian belief sharing
Tóm tắt
Multi-option collective decision-making is a challenging task in the context of swarm intelligence. In this paper, we extend the problem of collective perception from simple binary decision-making of choosing the color in majority to estimating the most likely fill ratio from a series of discrete fill ratio hypotheses. We have applied direct comparison (DC) and direct modulation of voter-based decisions (DMVD) to this scenario to observe their performances in a discrete collective estimation problem. We have also compared their performances against an Individual Exploration baseline. Additionally, we propose a novel collective decision-making strategy called distributed Bayesian belief sharing (DBBS) and apply it to the above discrete collective estimation problem. In the experiments, we explore the performances of considered collective decision-making algorithms in various parameter settings to determine the trade-off among accuracy, speed, message transfer and reliability in the decision-making process. Our results show that both DC and DMVD outperform the Individual Exploration baseline, but both algorithms exhibit different trade-offs with respect to accuracy and decision speed. On the other hand, DBBS exceeds the performances of all other considered algorithms in all four metrics, at the cost of higher communication complexity.
Tài liệu tham khảo
Alanyali, M., Venkatesh, S., Savas, O., & Aeron, S. (2004). Distributed Bayesian hypothesis testing in sensor networks. In Proceedings of the 2004 American Control Conference, vol 6, pp. 5369–5374 vol. 6, https://doi.org/10.23919/ACC.2004.1384706
Bartashevich, P., & Mostaghim, S. (2019). Benchmarking collective perception: New task difficulty metrics for collective decision-making. In: Moura Oliveira P., Novais P., Reis L.P. (eds) Progress in Artificial Intelligence. EPIA 2019. Lecture Notes in Computer Science, Springer, Cham, pp 699–711, https://doi.org/10.1007/978-3-030-30241-2_58
Brambilla, D. (2015). Environment classification: an empirical study of the response of a robot swarm to three different decision-making rules. Master’s thesis, Polytechnic University of Milan, Piazza Leonardo da Vinci, 32, 20133 Milano MI, Italy.
Camazine, S., Franks, N. R., Sneyd, J., Bonabeau, E., Deneubourg, J. L., & Theraulaz, G. (2001). Self-Organization in Biological Systems. USA: Princeton University Press.
Crosscombe, M., Lawry, J., & Bartashevich, P. (2019). Evidence propagation and consensus formation in noisy environments. In: Ben Amor N., Quost B., Theobald M. (eds) Scalable Uncertainty Management. SUM 2019. Lecture Notes in Computer Science, Springer, Cham, vol 11940, pp 310–323, https://doi.org/10.1007/978-3-030-35514-2_23
Ebert, J. T., Gauci, M., Mallmann-Trenn, F., & Nagpal, R. (2020). Bayes bots: Collective Bayesian decision-making in decentralized robot swarms. (pp. 7186–7192). https://doi.org/10.1109/ICRA40945.2020.9196584
Garnier, S., Combe, M., Jost, C., & Theraulaz, G. (2013). Do ants need to estimate the geometrical properties of trail bifurcations to find an efficient route? a swarm robotics test bed. PLOS Computational Biology, 9(3), 1–12. https://doi.org/10.1371/journal.pcbi.1002903.
Hoballah, I., & Varshney, P. (1989). Distributed Bayesian signal detection. IEEE Transactions on Information Theory, 35(5), 995–1000. https://doi.org/10.1109/18.42208
Lee, C., Lawry, J., & Winfield, A. (2018a). Combining opinion pooling and evidential updating for multi-agent consensus. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence, AAAI Press, IJCAI’18, p 347–353, https://doi.org/10.5555/3304415.3304465
Lee, C., Lawry, J., & Winfield, A. (2018b). Negative updating combined with opinion pooling in the best-of-n problem in swarm robotics. In: Dorigo, M., Birattari, M., Blum, C., Christensen, A.L., Reina, A., & Trianni, V. (eds) Swarm Intelligence. ANTS 2018. Lecture Notes in Computer Science, Springer, Cham, vol 11172, pp 97–108, https://doi.org/10.1007/978-3-030-00533-7_8
Mondada, F., Bonani, M., Raemy, X., Pugh, J., Cianci, C., Klaptocz., A., Magnenat, S., Zufferey, J.C., Floreano, D., & Martinoli, A. (2009). The e-puck, a robot designed for education in engineering. Proceedings of the 9th Conference on Autonomous Robot Systems and Competitions 1(1):59–65, http://infoscience.epfl.ch/record/135236
Olfati-Saber, R., Franco, E., Frazzoli, E., & Shamma, J. S. (2006). Belief Consensus and Distributed Hypothesis Testing in Sensor Networks (pp. 169–182). Berlin Heidelberg, Berlin, Heidelberg: Springer. https://doi.org/10.1007/11533382_11.
Reina, A., Valentini, G., Fernández-Oto, C., Dorigo, M., & Trianni, V. (2015). A design pattern for decentralised decision making. PLoS ONE, 10(10), 1–18. https://doi.org/10.1371/journal.pone.0140950
Şahin, E. (2005). Swarm robotics: From sources of inspiration to domains of application. In: Şahin E, Spears WM (eds) Swarm Robotics. SR 2004. Lecture Notes in Computer Science, Springer Berlin Heidelberg, vol 3342, pp 10–20, https://doi.org/10.1007/978-3-540-30552-1_2
Scheidler, A., Brutschy, A., Ferrante, E., & Dorigo, M. (2016). The k-unanimity rule for self-organized decision-making in swarms of robots. IEEE Transactions on Cybernetics, 46(5), 1175–1188. https://doi.org/10.1109/TCYB.2015.2429118
Shan, Q. & Mostaghim, S. (2020). Collective decision making in swarm robotics with distributed Bayesian hypothesis testing. In Dorigo, M., Stützle, T., Blesa, M.J., Blum, C., Hamann, H., Heinrich, M.K., & Strobel, V. (eds) Swarm Intelligence. ANTS 2020. Lecture Notes in Computer Science, Springer, Cham, vol 12421, pp 55–67, https://doi.org/10.1007/978-3-030-60376-2_5.
Strobel, V., & Dorigo, M. (2018). Blockchain technology for robot swarms: A shared knowledge and reputation management system for collective estimation. In: Swarm Intelligence: 11th International Conference, ANTS 2018, Rome, Italy, October 29–31, 2018, Proceedings, Springer, vol 11172, p 425.
Strobel, V., Castelló Ferrer, E., & Dorigo, M. (2018). Managing byzantine robots via blockchain technology in a swarm robotics collective decision making scenario. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, AAMAS ’18, p 541–549, https://doi.org/10.5555/3237383.3237464.
Talamali, M. S., Marshall, J. A. R., Bose, T., & Reina, A. (2019). Improving collective decision accuracy via time-varying cross-inhibition. In 2019 International Conference on Robotics and Automation (ICRA), pp 9652–9659, https://doi.org/10.1109/ICRA.2019.8794284.
Valentini, G., Hamann, H., & Dorigo, M. (2014). Self-organized collective decision making: The weighted voter model. In Proceedings of the 2014 International Conference on Autonomous Agents and Multi-Agent Systems, International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, AAMAS ’14, p 45–52, https://doi.org/10.5555/2615731.2615742.
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, International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC, AAMAS ’15, p 1305–1314, https://doi.org/10.5555/2772879.2773319.
Valentini, G., Brambilla, D., Hamann, H., & Dorigo, M. (2016a). Collective perception of environmental features in a robot swarm. In Dorigo, M., Birattari, M., Li, X., López-Ibáñez, M., Ohkura, K., Pinciroli, C., & Stützle, T. (eds) Swarm Intelligence. ANTS 2016. Lecture Notes in Computer Science, Springer, Cham, vol 9882, pp 65–76, https://doi.org/10.1007/978-3-319-44427-7_6.
Valentini, G., Ferrante, E., Hamann, H., & Dorigo, M. (2016b). Collective decision with 100 kilobots: Speed versus accuracy in binary discrimination problems. Autonomous Agents and Multi-Agent Systems, 30(3), 553–580. https://doi.org/10.1007/s10458-015-9323-3
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
Varshney, P. K., & Al-Hakeem, S. (1991). Algorithms for sensor fusion, decentralized Bayesian hypothesis testing with feedback (Vol. 1). Kaman Sciences Corp Colorado Springs CO: Tech. rep.
Wang, L., & Xiao, F. (2010). Finite-time consensus problems for networks of dynamic agents. IEEE Transactions on Automatic Control, 55(4), 950–955. https://doi.org/10.1109/TAC.2010.2041610