|
Vol: 54(68) No: 4 / December 2009 A Search and Collect Algorithm for a Robot Swarm Under the Constraint of Multi-hop Communication Connectivity T. Kovács Department of Informatics, Kecskemét College, Izsaki 10, 6000 Kecskemét, Hungary, e-mail: kovacs.tamas@gamf.kefo.hu A. Pásztor Department of Informatics, Kecskemét College, Izsaki 10, 6000 Kecskemét, Hungary, e-mail: pasztor.attila@gamf.kefo,hu Z. Istenes Eötvös Loránd University, Faculty of Informatics, Budapest, Hungary, e-mail: istenes@inf.elte.hu Keywords: robot swarm, ad-hoc network, connectivity Abstract The present paper investigates the reliability of the wireless multi-hop communication in an ad-hoc network formed by autonomous robots of a swarm, while the swarm accomplishes a typical searching and collecting task. This work also proposes a relatively simple algorithm for such a task that ensures a good communication connectivity of the swarm. Besides, the applicability and the limits of the proposed scheme are shown by the presented computer simulation. It was found that the expected value of the longest time while the communication network is disconnected increases exponentially with the radius of the searched area but does not depend considerably on the spatial density of the searched items. References C. Stachniss and W. Burgard, “Exploring unknown environments with mobile robots using coverage maps”, Proc. of the International Joint Conference on Artificial Intelligence (IJCAI), pp. 1127-1134, 2003. [2] S. Rutishauser, N. Correll and A. Martinoli, “Collaborative coverage using a swarm of networked miniature robots”, Robotics and Autonomous Systems, doi:10.1016/j.robot.2008.10.023. [3] M. N. Rooker and A. Birk, “Multi-robot exploration under the constraints of wireless networking”, Control Engineering Practice, vol. 15, pp. 435–445, 2007 [4] S. Nouyan and M. Dorigo, “Chain based path formation in swarms of robots”, Ant Colony Optimization and Swarm Intelligence, M. Dorigo et al., Eds., Springer-Verlag Berlin Heidelberg, pp. 120–131, 2006. [5] M. J. B. Krieger, J-B. Billeter, “The call of duty: Self-organised task allocation in a population of up to twelve mobile robots”, Robotics and Autonomous Systems, vol. 30, pp. 65–84, 2000. [6] E. Uozumi, Y. Sagawa and N. Sugie, ”Behavior patterns emerging among mobile robots with a diversity of personalities cooperating in collection and cleaning-up tasks”, Artif. Life Robotics, vol. 6, pp. 196–199, 2002. [7] R. Joiner and K. Issroff, ”Tracing success: graphical methods for analysing successful collaborative problem solving”, Computers & Education 41, pp. 369–378, 2003. [8] I. Rekleitis, A. P. New, and H. Choset, “Distributed coverage of unknown/unstructured environments by mobile sensor networks”, Multi-Robot Systems. From Swarms to Intelligent Automata, vol. III, L. E. Parker et al., Eds., Netherland: Springer, pp. 145–155, 2005. [9] B. K. Kim, H. M. Jung, J-B. Yoo, W. Y. Lee, C. Y. Park and Y. W. Ko, “Design and implementation of cricket-based location tracking system”, Proc. W. Acad. Sci. Eng. Tech., pp. 96-100, 2008. [10] T. C. H. Sit, Z. Liu, M. H. Ang, W. K. G. Seah, “Multi-robot mobility enhanced hop-count based localization in ad hoc networks”, Robotics and Autonomous Systems, vol. 55, pp. 244–252, 2007. [11] M. R. Pearlman and Z. J. Haas, “Determining the optimal configuration for the zone routing protocol, IEEE Journal on Selected Areas in Communications, vol. 17, no. 8, pp. 1395 – 1414, 1999. [12] X. Liu and R. Srikant, “Asymptotic uniform data-rate guarantees in large wireless networks”, Ad Hoc Networks, vol. 6, pp. 325–343, 2008. [13] F. Xue and P. R. Kumar, “The number of neighbors needed for connectivity of wireless networks”, Wireless Networks, vol. 10, pp. 169–181, 2004. |