A geometric approach to deploying robot swarms. (English) Zbl 1185.68736
Summary: We discuss the fundamental problems and practical issues underlying the deployment of a swarm of autonomous mobile robots that can potentially be used to build mobile robotic sensor networks. For the purpose, a geometric approach is proposed that allows robots to configure themselves into a two-dimensional plane with uniform spatial density. Particular emphasis is paid to the hole repair capability for dynamic network reconfiguration. Specifically, each robot interacts selectively with two neighboring robots so that three robots can converge onto each vertex of the equilateral triangle configuration. Based on the local interaction, the self-configuration algorithm is presented to enable a swarm of robots to form a communication network arranged in equilateral triangular lattices by shuffling the neighbors. Convergence of the algorithms is mathematically proved using Lyapunov theory. Moreover, it is verified that the self-reparation algorithm enables robot swarms to reconfigure themselves when holes exist in the network or new robots are added to the network. Through extensive simulations, we validate the feasibility of applying the proposed algorithms to self-configuring a network of mobile robotic sensors. We describe in detail the features of the algorithm, including self-organization, self-stabilization, and robustness, with the results of the simulation.
MSC:
| 68T40 | Artificial intelligence for robotics |
| 93C85 | Automated systems (robots, etc.) in control theory |
References:
| [1] | Beni, G.: From swarm intelligence to swarm robotics. In: Sahin E., Spears W.M. (eds.) SAB 2004: Swarm Robotics. Lecture Notes in Computer Science, vol. 3342, pp. 1–9. Springer, New York (2005) |
| [2] | Sahinm, E.: Swarm robotics: from sources of inspiration to domains of application. In: Sahin E., Spears W.M. (eds.) SAB 2004: Swarm Robotics. Lecture Notes in Computer Science, vol. 3342, pp. 10–20. Springer, New York (2005) |
| [3] | Choset, H.: Coverage for robotics–a survey of recent results. Ann. Math. Artif. Intell. 31, 113–126 (2001) · Zbl 1314.68317 · doi:10.1023/A:1016639210559 |
| [4] | Cortes, J., Martinez, S., Karatas, T., Bullo, F.: Coverage control for mobile sensing networks. IEEE Trans. Robot. Autom. 20(2), 243–255 (2004) · doi:10.1109/TRA.2004.824698 |
| [5] | Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999) · Zbl 0940.68145 · doi:10.1137/S009753979628292X |
| [6] | Defago, X., Konagaya, A.: Circle formation for oblivious anonymous mobile robots with no common sense of orientation. In: Proc. 2nd ACM Intl. Workshop on Principles of Mobile Computing, pp. 97–104, Toulouse, 30–31 October 2002 |
| [7] | Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Pattern formation by autonomous robots without chirality. In: Proc. SIROCCO, pp. 147–162, Catalonia, 27–29 June 2001 |
| [8] | Carpin, S., Parker, L.E.: Cooperative leader following in a distributed multi-robot system. In: Proc. IEEE International Conference on Robotics and Automation, pp. 2994–3001, Washington, DC, 11–15 May 2002 |
| [9] | Cao, Z., Tan, M., Wang, S., Fan, Y., Zhang, B.: The optimization research of formation control for multiple mobile robots. In: Proc. 4th World Congress on Intelligent Control and Automation, pp. 1270–1274, Shanghai, 10–14 June 2002 |
| [10] | Mondada, F., Pettinaro, G.C., Guignard, A., Kwee, I., Floreano, D., Deneubourg, J.-L., Nolfi, S., Gambardella, L.M., Dorigo, M.: Swarm-bot: a new distributed robotic concept. Auton. Robots 17(2–3), 193–221 (2004) · doi:10.1023/B:AURO.0000033972.50769.1c |
| [11] | Baldassarre, G., Trianni, V., Bonani, M., Mondada, F., Dorigo, M., Nolfi, S.: Self-organized coordinated motion in groups of physically connected robots. IEEE Trans. Syst. Man Cybern. Part B 37(1), 224–239 (2007) · doi:10.1109/TSMCB.2006.881299 |
| [12] | Ikemoto, Y., Hasegawa, Y., Fukuda, T., Matsuda, K.: Graduated spatial pattern formation of robot group. Inf. Sci. 171(4), 431–445 (2005) · doi:10.1016/j.ins.2004.09.013 |
| [13] | Ishiguro, A., Kawakatsu, T.: Self-assembly through the interplay between control and mechanical systems. In: Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 631–638, Beijing, 9–13 October 2006 |
| [14] | Shimizu, M., Mori, T., Ishiguro, A.: A development of a modular robot that enables adaptive reconfiguration. In: Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 174–179, Beijing, 9–13 October 2006 |
| [15] | Werger, B., Mataric, M.J.: From insect to internet: situated control for networked robot teams. Ann. Math. Artif. Intell. 31, 173–198 (2001) · doi:10.1023/A:1016650101473 |
| [16] | Balch, T., Hybinette, M.: Social potentials for scalable multi-robot formations. In: Proc. IEEE International Conference on Robotics and Automation, pp. 73–80 (2000) |
| [17] | Howard, A., Mataric, M.J., Sukhatme, G.S.: Mobile sensor network deployment using potential fields: a distributed, scalable solution to the area coverage problem. In: Proc. 6th International Symposium on Distributed Autonomous Robotic Systems, pp. 299–308 (2002) |
| [18] | Spears, W.M., Gordon, F.D.: Using artificial physics to control agents. In: Proc. IEEE International Conference on Information, Intelligence, and Systems, pp. 281–288 (1999) |
| [19] | Spears, W., Spears, D., Hamann, J., Heil, R.: Distributed, physics-based control of swarms of vehicles. Auton. Robots 17(2–3), 137–162 (2004) · doi:10.1023/B:AURO.0000033970.96785.f2 |
| [20] | Fujibayashi, K., Murata, S., Sugawara, K., Yamamura, M.: Self-organizing formation algorithm for active elements. In: Proc. 21st IEEE Symposium on Reliable Distributed Systems, pp. 416–421 (2002) |
| [21] | McLurkin, J., Smith, J.: Distributed algorithms for dispersion in indoor environments using a swarm of autonomous mobile robots. In: Proc. 7th International Symposium on Distributed Autonomous Robotic Systems, pp. 831–890 (2004) · Zbl 1217.68221 |
| [22] | Shucker, B., Murphey, T., Bennett, J.K.: Switching rules for decentralized control with simple control laws. In: Proc. American Control Conference, pp. 1485–1492 (2007) |
| [23] | Reif, J., Wang, H.: Social potential fields: a distributed behavioral control for autonomous robots. Robot. Auton. Syst. 27(3), 171–194 (1999) · doi:10.1016/S0921-8890(99)00004-4 |
| [24] | Zou, Y., Chakrabarty, K.: Sensor deployment and target localization based on virtual forces. In: Proc. IEEE Infocom Conference, pp. 1293–1303 (2003) |
| [25] | Heo, N., Varshney, P.K.: A distributed self spreading algorithm for mobile wireless sensor networks. In: Proc. IEEE Wireless Communication and Networking Conference, pp. 1597–1602 (2003) |
| [26] | Cohen, R., Peleg, D.: Local algorithms for autonomous robots systems. In: Flocchini P., Gasieniec L. (eds.) SIROCCO 2006. Lecture Notes in Computer Science, vol. 4056, pp. 29–43. Springer, New York (2006) · Zbl 1222.68390 |
| [27] | Wang, G.-L., Cao, G., Porta, T.L.: Movement-assisted sensor deployment. In: Proc. IEEE Infocom Conference, pp. 2469–2479 (2004) |
| [28] | Martison, E., Payton, D.: Lattice formation in mobile autonomous sensor arrays. In: Sahin E., Spears W.M. (eds.) SAB 2004: Swarm Robotics. Lecture Notes in Computer Science, vol. 3342, pp. 98–111. Springer, New York (2005) |
| [29] | Ghosh, S., Basu, K., Das, S.K.: An architecture for next-generation radio access networks. IEEE Netw. 19(Is. 5), 35–42 (2005) · doi:10.1109/MNET.2005.1509950 |
| [30] | Fowler, T.: Mesh networks for broadband access. IEEE Rev. 47(Is. 1), 17–22 (2001) · doi:10.1049/ir:20010108 |
| [31] | Gurumohan, P.C., Hui, J.: Topology design for free space optical networks. In: Proc. 12th International Conference on Computer Communications and Networks, pp. 576–579 (2003) |
| [32] | Gazi, V., Passino, K.M.: Stability analysis of swarms. IEEE Trans. Automat. Contr. 48(4), 692–696 (2003) · Zbl 1365.92143 · doi:10.1109/TAC.2003.809765 |
| [33] | Olfati-Saber, R., Murray, R.: Distributed cooperative control of multiple vehicle formations using structural potential functions. In: Proc. 15th IFAC World Congress on Automatic Control, pp. 21–26 (2002) |
| [34] | Ogren, P., Fiorelli, E., Leonard, N.E.: Formations with a mission: stable coordination of vehicle group maneuvers. In: Proc. 15th International Symposium on Mathematical Theory Networks and Systems (2002) |
| [35] | Slotine, J.E., Li, W.: Applied Nonlinear Control. Prentice-Hall, Englewood Cliffs (1991) · Zbl 0753.93036 |
| [36] | Chen, C.-T.: Linear system theory and design, 3rd edn. Oxford University Press, Oxford (1999) |
| [37] | Dolev, S.: Self-Stabilization. MIT, Cambridge (2000) · Zbl 1026.93001 |
| [38] | Schneider, M.: Self-stabilization. ACM Comput. Surv. 25(1), 45–67 (1993) · doi:10.1145/151254.151256 |
| [39] | Lyengar, R., Kar, K., Banerjee, S.: Low-coordination topologies for redundancy in sensor networks. In: Proc. ACM MobiHoc, pp. 332–342 (2005) |
| [40] | Stojmenovic, I., Wu, J.: Broadcasting and activity scheduling in ad hoc networks. In: Basagini S., Conti M., Giordano S., Stojmenovic I. (eds.) Mobile Ad Hoc Networking, pp. 205–229. IEEE, Piscataway (2004) |
| [41] | Harary, F.: Graph Theory. Addison-Wesley, Reading (1972) · Zbl 0235.05105 |
| [42] | Lee, G., Chong, N.Y.: Decentralized formation control for a team of anonymous mobile robots. In: Proc. 6th Asian Control Conference, pp. 971–976 (2006) |
| [43] | Lam, M., Liu, Y.: ISOGIRD: an efficient algorithm for coverage enhancement in mobile sensor networks. In: Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1458–1463 (2006) |
| [44] | Nembrini, J., Winfield, A., Melhuish, C.: Minimalist coherent swarming of wireless networked autonomous mobile robots. In: Proc. International Conference on Simulation of Adaptive Behavior, pp. 373–382 (2002) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
