Provable self-organizing pattern formation by a swarm of robots with limited knowledge
Tóm tắt
In this paper we present a procedure to automatically design and verify the local behavior of robots with highly limited cognition. All robots are: anonymous, homogeneous, non-communicating, memoryless, reactive, do not know their global position, do not have global state information, and operate by a local clock. They only know: (1) the relative location of their neighbors within a short range and (2) a common direction (North). We have developed a procedure to generate a local behavior that allows the robots to self-organize into a desired global pattern despite their individual limitations. This is done while also avoiding collisions and keeping the coherence of the swarm at all times. The generated local behavior is a probabilistic local state-action map. The robots follow this stochastic policy to select an action based on their current perception of their neighborhood (i.e., their local state). It is this stochasticity, in fact, that allows the global pattern to eventually emerge. For a generated local behavior, we present a formal proof procedure to verify whether the desired pattern will always eventually emerge from the local actions of the agents. The novelty of the proof procedure is that it is primarily local in nature and focuses on the local states of the robots and the global implications of their local actions. A local approach is of interest to reduce the computational effort as much as possible when verifying the emergence of larger patterns. Finally, we show how the behavior could be implemented on real robots and investigate this with extensive simulations on a realistic robot model. To the best of our knowledge, no other solutions exist for robots with such limited cognition to achieve this level of coordination with proof that the desired global property will emerge.
Tài liệu tham khảo
Achtelik, M., Achtelik, M., Brunet, Y., Chli, M., Chatzichristofis, S., Decotignie, J. D., et al. (2012). SFly: Swarm of micro flying robots. In 2012 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 2649–2650). Washington: IEEE Press.
Arbuckle, D. J., & Requicha, A. A. G. (2010). Self-assembly and self-repair of arbitrary shapes by a swarm of reactive robots: Algorithms and simulations. Autonomous Robots, 28(2), 197–211.
Arbuckle, D. J., & Requicha, A. A. G. (2012). Issues in self-repairing robotic self-assembly. In R. Doursat, H. Sayama, & O. Michel (Eds.), Morphogenetic engineering: Toward programmable complex systems (pp. 141–155). Berlin: Springer.
Basiri, M., Schill, F., Floreano, D., & Lima, P. U. (2014). Audio-based localization for swarms of micro air vehicles. In 2014 IEEE international conference on robotics and automation (ICRA) (pp. 4729–4734). Washington: IEEE Press.
Bonabeau, E., & Dessalles, J.-L. (1997). Detection and emergence. Intellectica, 2(25), 85–94.
Bonabeau, E., Guérin, S., Snyers, D., Kuntz, P., & Theraulaz, G. (2000). Three-dimensional architectures grown by simple ‘stigmergic’ agents. Biosystems, 56(1), 13–32.
Clarke, E. M, Jr., Grumberg, O., & Peled, D. A. (1999). Model checking. Cambridge, MA: MIT Press.
Conroy, J., Samuel, P., & Pines, D. (2005). Development of an MAV control and navigation system. In Infotech@ Aerospace, AIAA 2005, Arlington, Virginia (p. 7065).
Coppola, M., McGuire, K. N., Scheper, K. Y. W., & de Croon, G. C. H. E. (2018). On-board communication-based relative localization for collision avoidance in micro air vehicle teams. Autonomous Robots, 42(8), 1787–1805.
Darley, V. (1994). Emergent phenomena and complexity. Artificial Life, 4, 411–416.
de Marina Peinado, H. J. G. (2016). Distributed formation control for autonomous robots. Groningen: University of Groningen.
Derakhshandeh, Z., Gmyr, R., Richa, A. W., Scheideler, C., & Strothmann, T. (2016). Universal shape formation for programmable matter. In Proceedings of the 28th ACM symposium on parallelism in algorithms and architectures (SPAA ‘16) (pp. 289–299). New York, NY: ACM.
Di Luna, G. A., Flocchini, P., Santoro, N., Viglietta, G., & Yamauchi, Y. (2017). Shape formation by programmable particles. ArXiv Preprint. arXiv:1705.03538.
Dixon, C., Winfield, A. F. T., Fisher, M., & Zeng, C. (2012). Towards temporal verification of swarm robotic systems. Robotics and Autonomous Systems, 60(11), 1429–1441.
Engelen, S., Gill, E. K. A., & Verhoeven, C. J. M. (2011). Systems engineering challenges for satellite swarms. In 2011 aerospace conference, AERO ’11 (pp 1–8). Washington, DC: IEEE Computer Society.
Faigl, J., Krajník, T., Chudoba, J., Přeučil, L., & Saska, M. (2013). Low-cost embedded system for relative localization in robotic swarms. In 2013 IEEE international conference on robotics and automation (ICRA) (pp. 993–998). Washington: IEEE Press.
Falconi, R., Gowal, S., & Martinoli, A. (2010). Graph based distributed control of non-holonomic vehicles endowed with local positioning information engaged in escorting missions. In 2010 IEEE international conference on robotics and automation (ICRA) (pp. 3207–3214). Washington: IEEE Press.
Falconi, R., Sabattini, L., Secchi, C., Fantuzzi, C., & Melchiorri, C. (2011). A graph-based collision-free distributed formation control strategy. In IFAC proceedings volumes, 18th IFAC world congress (Vol. 44(1), pp. 6011–6016).
Falconi, R., Sabattini, L., Secchi, C., Fantuzzi, C., & Melchiorri, C. (2015). Edge-weighted consensus-based formation control strategy with collision avoidance. Robotica, 33(2), 332–347.
Flocchini, P., Prencipe, G., Santoro, N., & Widmayer, P. (2005). Gathering of asynchronous robots with limited visibility. Theoretical Computer Science, 337(1), 147–168.
Fox, M. J., & Shamma, J. S. (2015). Probabilistic performance guarantees for distributed self-assembly. IEEE Transactions on Automatic Control, 60(12), 3180–3194.
Gazi, V., & Passino, K. M. (2002). A class of attraction/repulsion functions for stable swarm aggregations. In Proceedings of the 41st IEEE conference on decision and control (CDC) (Vol. 3, pp. 2842–2847).
Gazi, V., & Passino, K . M. (2004). Stability analysis of social foraging swarms. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 34(1), 539–557.
Gerkey, B. P., & Matarić, M. J. (2004). A formal analysis and taxonomy of task allocation in multi-robot systems. The International Journal of Robotics Research, 23(9), 939–954.
Gjondrekaj, E., Loreti, M., Pugliese, R., Tiezzi, F., Pinciroli, C., Brambilla, M., et al. (2012). Towards a formal verification methodology for collective robotic systems. In T. Aoki & K. Taguchi (Eds.), Formal methods and software engineering: 14th international conference on formal engineering methods (ICFEM), Kyoto, Japan, November 12–16, 2012. Proceedings (pp. 54–70). Berlin: Springer.
Grushin, A., & Reggia, J. A. (2008). Automated design of distributed control rules for the self-assembly of prespecified artificial structures. Robotics and Autonomous Systems, 56(4), 334–359.
Grushin, A., & Reggia, J . A. (2010). Parsimonious rule generation for a nature-inspired approach to self-assembly. ACM Transactions on Autonomous and Adaptive Systems (TAAS), 5(3), 12:1–12:24.
Guo, K., Qiu, Z., Meng, W., Xie, L., & Teo, R. (2017). Ultra-wideband based cooperative relative localization algorithm and experiments for multiple unmanned aerial vehicles in GPS denied environments. International Journal of Micro Air Vehicles, 9(3), 169–186.
Haghighat, B., & Martinoli, A. (2017). Automatic synthesis of rulesets for programmable stochastic self-assembly of rotationally symmetric robotic modules. Swarm Intelligence, 11(3), 243–270.
Hamann, H. (2018). Swarm robotics: A formal approach. Berlin: Springer.
Ismail, A. S., Hasni, R., & Subramanian, K. (2009). Some applications of eulerian graphs. International Journal of Mathematical Science Education, 2(2), 1–10.
Izzo, D., & Pettazzi, L. (2005). Equilibrium shaping: Distributed motion planning for satellite swarm. In Proceedings of the 8th international symposium on artificial intelligence, robotics and automation in space.
Izzo, D., & Pettazzi, L. (2007). Autonomous and distributed motion planning for satellite swarm. Journal of Guidance, Control, and Dynamics, 30(2), 449–459.
Izzo, D., Simões, L. F., & de Croon, G. C. H. E. (2014). An evolutionary robotics approach for the distributed control of satellite formations. Evolutionary Intelligence, 7(2), 107–118.
Ji, M., & Egerstedt, M. (2007). Distributed coordination control of multiagent systems while preserving connectedness. IEEE Transactions on Robotics, 23(4), 693–703.
Joordens, M. A., & Jamshidi, M. (2010). Consensus control for a system of underwater swarm robots. IEEE Systems Journal, 4(1), 65–73.
Klavins, E. (2002). Automatic synthesis of controllers for distributed assembly and formation forming. In 2002 IEEE international conference on robotics and automation (ICRA) (Vol. 3, pp. 3296–3302). Washington: IEEE Press.
Klavins, E. (2007). Programmable self-assembly. IEEE Control Systems, 27(4), 43–56.
Koenig, N., & Howard, A. (2004). Design and use paradigms for Gazebo, an open-source multi-robot simulator. In 2004 IEEE/RSJ international conference on intelligent robots and systems (IROS) (vol. 3, pp. 2149–2154). Washington: IEEE Press.
Konur, S., Dixon, C., & Fisher, M. (2012). Analysing robot swarm behaviour via probabilistic model checking. Robotics and Autonomous Systems, 60(2), 199–213.
Krishnanand, K. N., & Ghose, D. (2005). Formations of minimalist mobile robots using local-templates and spatially distributed interactions. Robotics and Autonomous Systems, 53(3), 194–213.
Lerman, K., Galstyan, A., Martinoli, A., & Ijspeert, A. (2001). A macroscopic analytical model of collaboration in distributed robotic systems. Artificial Life, 7(4), 375–393.
Loncaric, S. (1998). A survey of shape analysis techniques. Pattern Recognition, 31(8), 983–1001.
McGuire, K. N., Coppola, M., de Wagter, C., & de Croon, G. C. H. E. (2017). Towards autonomous navigation of multiple pocket-drones in real-world environments. In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 244–249). Washington: IEEE Press.
McGuire, K. N., de Croon, G. C. H. E., de Wagter, C., Remes, B., Tuyls, K., & Kappen, H. (2016). Local histogram matching for efficient optical flow computation applied to velocity estimation on pocket drones. In 2016 IEEE international conference on robotics and automation (ICRA) (pp. 3255–3260). Washington: IEEE Press.
Mesbahi, M., & Egerstedt, M. (2010). Graph theoretic methods in multiagent networks (Vol. 33). Princeton: Princeton University Press.
Meyer, J., Sendobry, A., Kohlbrecher, S., Klingauf, U., & von Stryk, O. (2012). Comprehensive simulation of quadrotor UAVs using ROS and Gazebo. In I. Noda, N. Ando, D. Brugali, & J. J. Kuffner (Eds.), J. Simulation, modeling, and programming for autonomous robots (pp. 400–411). Berlin: Springer.
Nembrini, J., Winfield, A., & Melhuish, C. (2002). Minimalist coherent swarming of wireless networked autonomous mobile robots. In B. Hallam, D. Floreano, J. Hallam, G. Hayes, & J.-A. Meyer (Eds.), From animals to animats 7: Proceedings of the seventh international conference on simulation of adaptive behavior, ICSAB (pp. 373–382). Cambridge, MA: MIT Press.
Oh, K.-K., Park, M.-C., & Ahn, H.-S. (2015). A survey of multi-agent formation control. Automatica, 53(Supplement C), 424–440.
Pereira, A. R., & Hsu, L. (2008). Adaptive formation control using artificial potentials for euler-lagrange agents. IFAC Proceedings Volumes, 41(2), 10788–10793.
Prorok, A., Correll, N., & Martinoli, A. (2011). Multi-level spatial modeling for stochastic distributed robotic systems. The International Journal of Robotics Research, 30(5), 574–589.
Pugh, J., Raemy, X., Favre, C., Falconi, R., & Martinoli, A. (2009). A fast onboard relative positioning module for multirobot systems. IEEE/ASME Transactions on Mechatronics, 14(2), 151–162.
Quigley, M., Conley, K., Gerkey, B., Faust, J., Foote, T., Leibs, J., et al. (2009) ROS: An open-source robot operating system. In ICRA workshop on open source software (Vol. 3, p. 5).
Rahmani, A., Ji, M., Mesbahi, M., & Egerstedt, M. (2009). Controllability of multi-agent systems from a graph-theoretic perspective. SIAM Journal on Control and Optimization, 48(1), 162–186.
Roberts, J. F., Stirling, T., Zufferey, J. C., & Floreano, D. (2012). 3-D relative positioning sensor for indoor flying robots. Autonomous Robots, 33(1), 5–20.
Roelofsen, S., Gillet, D., & Martinoli, A. (2015). Reciprocal collision avoidance for quadrotors using on-board visual detection. In 2015 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 4810–4817). Washington: IEEE Press.
Rubenstein, M., Cornejo, A., & Nagpal, R. (2014). Programmable self-assembly in a thousand-robot swarm. Science, 345(6198), 795–799.
Sapin, E. (2010). Gliders and glider guns discovery in cellular automata. In A. Adamatzky (Ed.), Game of life cellular automata (pp. 135–165). London: Springer.
Saska, M., Vonásek, V., Chudoba, J., Thomas, J., Loianno, G., & Kumar, V. (2016). Swarm distribution and deployment for cooperative surveillance by micro-aerial vehicles. Journal of Intelligent & Robotic Systems, 84(1), 469–492.
Scheper, K. Y. W., & de Croon, G. C. H. E. (2016). Abstraction as a mechanism to cross the reality gap in evolutionary robotics. In E. Tuci, A. Giagkos, M. Wilson, & J. Hallam (Eds.), From animals to animats 14: 14th international conference on simulation of adaptive behavior, SAB 2016, Aberystwyth, UK, August 23–26, 2016, Proceedings (pp. 280–292). Cham: Springer.
Shiell, N., & Vardy, A. (2016). A bearing-only pattern formation algorithm for swarm robotics. In M. Dorigo, M. Birattari, X. Li, M. López-Ibáñez, K. Ohkura, C. Pinciroli, & T. Stützle (Eds.), Swarm intelligence (pp. 3–14). Cham: Springer.
Slavkov, I., Carrillo-Zapata, D., Carranza, N., Diego, X., Jansson, F., Kaandorp, J., et al. (2018). Morphogenesis in robot swarms. Science Robotics, 3(25), eaau9178.
Smith, B., Howard, A., McNew, J.-M., Wang, J., & Egerstedt, M. (2009). Multi-robot deployment and coordination with embedded graph grammars. Autonomous Robots, 26(1), 79–98.
Stegagno, P., Cognetti, M., Oriolo, G., Bülthoff, H. H., & Franchi, A. (2016). Ground and aerial mutual localization using anonymous relative-bearing measurements. IEEE Transactions on Robotics, 32(5), 1133–1151.
Tanner, H. G. (2004). On the controllability of nearest neighbor interconnections. In 2004 43rd IEEE conference on decision and control (CDC) (Vol. 3, pp. 2467–2472).
van der Helm, S., McGuire, K. N., Coppola, M., & de Croon, G. C. H. E. (2018). On-board range-based relative localization for micro aerial vehicles in indoor leader-follower flight. ArXiv Preprint. arXiv:1805.07171.
Van Steen, M. (2010). Graph theory and complex networks: An introduction. Amsterdam: Maarten van Steen.
Verhoeven, C. J. M., Bentum, M. J., Monna, G. L. E., Rotteveel, J., & Guo, J. (2011). On the origin of satellite swarms. Acta Astronautica, 68(7–8), 1392–1395.
Werfel, J., & Nagpal, R. (2008). Three-dimensional construction with mobile robots and modular blocks. International Journal of Robotics Research, 27(3–4), 463–479.
Werfel, J., Petersen, K., & Nagpal, R. (2014). Designing collective behavior in a termite-inspired robot construction team. Science, 343(6172), 754–758.
Wessnitzer, J., Adamatzky, A., & Melhuish, C. (2001). Towards self-organising structure formations: A decentralized approach. In J. Kelemen & P. Sosík (Eds.), Advances in Artificial Life (pp. 573–581). Berlin: Springer.
Winfield, A. F., Sa, J., Fernández-Gago, M., Dixon, C., & Fisher, M. (2005). On formal specification of emergent behaviours in swarm robotic systems. International Journal of Advanced Robotic Systems, 2(4), 39.
Winfield, A. F. T., & Nembrini, J. (2012). Emergent swarm morphology control of wireless networked mobile robots. In R. Doursat, H. Sayama, & O. Michel (Eds.), Morphogenetic engineering: Toward programmable complex systems (pp. 239–271). Berlin: Springer.
Winfield, A. F. T., Liu, W., Nembrini, J., & Martinoli, A. (2008). Modelling a wireless connected swarm of mobile robots. Swarm Intelligence, 2(2), 241–266.
Yamauchi, Y., & Yamashita, M. (2013). Pattern formation by mobile robots with limited visibility. In T. Moscibroda & A. A. Rescigno (Eds.), Structural information and communication complexity: 20th international colloquium, SIROCCO 2013, Ischia, Italy, July 1–3, 2013, Revised Selected Papers (pp. 201–212). Cham: Springer.
Yamauchi, Y., & Yamashita, M. (2014). Randomized pattern formation algorithm for asynchronous oblivious mobile robots. In F. Kuhn (Ed.), Distributed Computing (pp. 137–151). Berlin: Springer.