Abstract
Building structures is a remarkable collective process but its automation remains an open challenge. Robot swarms provide a promising solution to this challenge. However, collective construction involves a number of difficulties regarding efficient robots allocation to the different activities, particularly if the goal is to reach an optimal construction rate. In this paper, we study an abstract construction scenario, where a swarm of robots is engaged in a collective perception process to estimate the density of building blocks around a construction site. The goal of this perception process is to maintain a minimum density of blocks available to the robots for construction. To maintain this density, the allocation of robots to the foraging task needs to be adjusted such that enough blocks are retrieved. Our results show a robust collective perception that enables the swarm to maintain a minimum block density under different rates of construction and foraging. Our approach leads the system to stabilize around a state in which the robots allocation allows the swarm to maintain a tile density that is close to or above the target minimum.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Project on the Open Science Framework: https://osf.io/n7kr3/.
- 2.
Complete run of a simulation (video): https://osf.io/6mgys/.
References
Allwright, M., Bhalla, N., Dorigo, M.: Structure and markings as stimuli for autonomous construction. In: Eighteenth International Conference on Advanced Robotics - ICAR 2017, pp. 296–302. IEEE Press, Piscataway (2017)
Allwright, M., Bhalla, N., Pinciroli, C., Dorigo, M.: Simulating multi-robot construction in ARGoS. In: Dorigo, M., Birattari, M., Blum, C., Christensen, A.L., Reina, A., Trianni, V. (eds.) ANTS 2018. LNCS, vol. 11172, pp. 188–200. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-00533-7_15
Allwright, M., Zhu, W., Dorigo, M.: An open-source multi-robot construction system. HardwareX 5, e00049 (2019)
Bartashevich, P., Mostaghim, S.: Benchmarking collective perception: new task difficulty metrics for collective decision-making. In: Moura Oliveira, P., Novais, P., Reis, L.P. (eds.) EPIA 2019. LNCS (LNAI), vol. 11804, pp. 699–711. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-30241-2_58
Bonabeau, E., Dorigo, M., Theraulaz, G.: Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York (1999)
Brutschy, A., Pini, G., Pinciroli, C., Birattari, M., Dorigo, M.: Self-organized task allocation to sequentially interdependent tasks in swarm robotics. Auton. Agent. Multi-Agent Syst. 28(1), 101–125 (2012). https://doi.org/10.1007/s10458-012-9212-y
Ebert, J., Gauci, M., Mallmann-Trenn, F., Nagpal, R.: Bayes bots: collective Bayesian decision-making in decentralized robot swarms. In: International Conference on Robotics and Automation (ICRA) (2020)
Garnier, S., Gautrais, J., Theraulaz, G.: The biological principles of swarm intelligence. Swarm Intell. 1(1), 3–31 (2007). https://doi.org/10.1007/s11721-007-0004-y
Gray, R., Franci, A., Srivastava, V., Leonard, N.E.: Multiagent decision-making dynamics inspired by honeybees. IEEE Trans. Control Netw. Syst. 5(2), 793–806 (2018)
Gutiérrez, A., Campo, A., Monasterio-Huelin, F., Magdalena, L., Dorigo, M.: Collective decision-making based on social odometry. Neural Comput. Appl. 19(6), 807–823 (2010). https://doi.org/10.1007/s00521-010-0380-x
Hamann, H., Schmickl, T., Wörn, H., Crailsheim, K.: Analysis of emergent symmetry breaking in collective decision making. Neural Comput. Appl. 21(2), 207–218 (2012). https://doi.org/10.1007/s00521-010-0368-6
Hamann, H., Valentini, G., Khaluf, Y., Dorigo, M.: Derivation of a micro-macro link for collective decision-making systems. In: Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds.) PPSN 2014. LNCS, vol. 8672, pp. 181–190. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-10762-2_18
Huang, M., Seeley, T.: Multiple unloadings by nectar foragers in honey bees: a matter of information improvement or crop fullness? Insectes Sociaux 50(4), 330–339 (2003). https://doi.org/10.1007/s00040-003-0682-4
Khaluf, Y.: Edge detection in static and dynamic environments using robot swarms. In: IEEE 11th International Conference on Self-Adaptive and Self-Organizing Systems (SASO), pp. 81–90. IEEE (2017)
Khaluf, Y., Allwright, M., Rausch, I., Simoens, P., Dorigo, M.: Construction task allocation through the collective perception of a dynamic environment (2020). https://osf.io/n7kr3/
Khaluf, Y., Birattari, M., Hamann, H.: A swarm robotics approach to task allocation under soft deadlines and negligible switching costs. In: del Pobil, A.P., Chinellato, E., Martinez-Martin, E., Hallam, J., Cervera, E., Morales, A. (eds.) SAB 2014. LNCS (LNAI), vol. 8575, pp. 270–279. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08864-8_26
Khaluf, Y., Dorigo, M.: Modeling robot swarms using integrals of birth-death processes. ACM Trans. Auton. Adapt. Syst. (TAAS) 11(2), 1–16 (2016)
Khaluf, Y., Pinciroli, C., Valentini, G., Hamann, H.: The impact of agent density on scalability in collective systems: noise-induced versus majority-based bistability. Swarm Intell. 11(2), 155–179 (2017). https://doi.org/10.1007/s11721-017-0137-6
Khaluf, Y., Rammig, F.: Task allocation strategy for time-constrained tasks in robots swarms. In: Artificial Life Conference Proceedings, vol. 13, pp. 737–744. MIT Press (2013)
Kim, S.H., Whitt, W.: Choosing arrival process models for service systems: tests of a nonhomogeneous poisson process. Naval Res. Logist. (NRL) 61(1), 66–90 (2014)
Meyer, B.: Optimal information transfer and stochastic resonance in collective decision making. Swarm Intell. 11(2), 131–154 (2017). https://doi.org/10.1007/s11721-017-0136-7
Montes de Oca, M.A., Ferrante, E., Scheidler, A., Pinciroli, C., Birattari, M., Dorigo, M.: Majority-rule opinion dynamics with differential latency: a mechanism for self-organized collective decision-making. Swarm Intell. 5(3–4), 305–327 (2011)
Pais, D., Hogan, P.M., Schlegel, T., Franks, N.R., Leonard, N.E., Marshall, J.A.: A mechanism for value-sensitive decision-making. PloS One 8(9), e73216 (2013)
Pini, G., Brutschy, A., Frison, M., Roli, A., Dorigo, M., Birattari, M.: Task partitioning in swarms of robots: an adaptive method for strategy selection. Swarm Intell. 5(3–4), 283–304 (2011). https://doi.org/10.1007/s11721-011-0060-1
Prasetyo, J., De Masi, G., Ferrante, E.: Collective decision making in dynamic environments. Swarm Intell. 13(3–4), 217–243 (2019). https://doi.org/10.1007/s11721-019-00169-8
Ratnieks, F.L., Anderson, C.: Task partitioning in insect societies. ii. use of queueing delay information in recruitment. Am. Nat. 154(5), 536–548 (1999)
Rausch, I., Khaluf, Y., Simoens, P.: Collective decision-making on triadic graphs. In: Barbosa, H., Gomez-Gardenes, J., Gonçalves, B., Mangioni, G., Menezes, R., Oliveira, M. (eds.) Complex Networks XI. SPC, pp. 119–130. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-40943-2_11
Reina, A., Miletitch, R., Dorigo, M., Trianni, V.: A quantitative micro-macro link for collective decisions: the shortest path discovery/selection example. Swarm Intell. 9(2–3), 75–102 (2015). https://doi.org/10.1007/s11721-015-0105-y
Reina, A., Valentini, G., Fernández-Oto, C., Dorigo, M., Trianni, V.: A design pattern for decentralised decision making. PloS One 10(10), e0140950 (2015)
Schmickl, T., Möslinger, C., Crailsheim, K.: Collective perception in a robot swarm. In: Şahin, E., Spears, W.M., Winfield, A.F.T. (eds.) SR 2006. LNCS, vol. 4433, pp. 144–157. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-71541-2_10
Strobel, V., Castelló Ferrer, E., Dorigo, M.: Managing byzantine robots via blockchain technology in a swarm robotics collective decision making scenario. In: Dastani, M., Sukthankar, G., André, E., Koenig, S. (eds.) Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, International Foundation for Autonomous Agents and Multiagent Systems, pp. 541–549 (2018)
Theraulaz, G., Bonabeau, E.: A brief history of stigmergy. Artif. Life 5(2), 97–116 (1999)
Trianni, V., De Simone, D., Reina, A., Baronchelli, A.: Emergence of consensus in a multi-robot network: from abstract models to empirical validation. IEEE Robot. Autom. Lett. 1(1), 348–353 (2016)
Valentini, G., Hamann, H.: Time-variant feedback processes in collective decision-making systems: influence and effect of dynamic neighborhood sizes. Swarm Intell. 9(2–3), 153–176 (2015). https://doi.org/10.1007/s11721-015-0108-8
Valentini, G.: Achieving Consensus in Robot Swarms. SCI, vol. 706. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-53609-5
Valentini, G., Brambilla, D., Hamann, H., Dorigo, M.: Collective perception of environmental features in a robot swarm. In: Dorigo, M., et al. (eds.) ANTS 2016. LNCS, vol. 9882, pp. 65–76. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44427-7_6
Valentini, G., Ferrante, E., Hamann, H., Dorigo, M.: Collective decision with 100 kilobots: speed versus accuracy in binary discrimination problems. Auton. Agent. Multi-Agent Syst. 30(3), 553–580 (2016)
Werfel, J., Petersen, K., Nagpal, R.: Designing collective behavior in a termite-inspired robot construction team. Science 343(6172), 754–758 (2014)
Wolff, R.W.: Poisson arrivals see time averages. Oper. Res. 30(2), 223–231 (1982)
Acknowledgements
This work is partially supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 846009. Marco Dorigo acknowledges support from the Belgian F.R.S.-FNRS, of which he is a Research Director.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Khaluf, Y., Allwright, M., Rausch, I., Simoens, P., Dorigo, M. (2020). Construction Task Allocation Through the Collective Perception of a Dynamic Environment. In: Dorigo, M., et al. Swarm Intelligence. ANTS 2020. Lecture Notes in Computer Science(), vol 12421. Springer, Cham. https://doi.org/10.1007/978-3-030-60376-2_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-60376-2_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-60375-5
Online ISBN: 978-3-030-60376-2
eBook Packages: Computer ScienceComputer Science (R0)