Robert L. STEWART, R. Andrew Russell And Lindsay KLEEMAN

Modelling a Deposition Process in Collective Construction

During collective construction tasks, swarm robots coordinate their actions in space and time to build structures that conform to some given design or specification. In this paper, a simulation model and a mathematical model (based on a Markov chain) are introduced to describe the deposition process of a previously detailed robotic swarm system that uses templates and feedback to facilitate construction. The models are based on the behaviour and geometry of real robots and predict the dynamics observed during practical trials as well as explaining the occurrence of different spatial patterns of building blocks. Furthermore, the models provide an insight into the swarm system and a solid basis for understanding the feedback mechanism that is fundamental to its operation. The theoretical models are verified with practical trials performed by physical robots.

Anahtar Kelimeler:

Turk. J. Elec. Eng. & Comp. Sci., 15, (2007), 227-255. Full text: pdf Other articles published in the same issue: Turk. J. Elec. Eng. & Comp. Sci., vol.15, iss.2.

Modelling a Deposition Process in Collective Construction

Keywords:

Turk. J. Elec. Eng. & Comp. Sci., 15, (2007), 227-255. Full text: pdf Other articles published in the same issue: Turk. J. Elec. Eng. & Comp. Sci., vol.15, iss.2.,

PDF

___

W. M. Wheeler, The Social Insects: Their Origin and Evolution, London, Kegan Paul, Trench, Trubner and Co., Ltd., 1928.
E. O. Wilson, Insect Societies, Cambridge, MA, The Belknap Press of Harvard University Press, 1974.
E. Bonabeau, M. Dorigo, G. Theraulaz, Swarm Intelligence: From Natural to ArtiŞcial Systems, NY, Oxford University Press, 1999.
M. Dorigo, E. S¸ahin, “Guest editorial,” Autonomous Robots, Vol. 17, pp. 111–113, 2004.
R. L. Stewart, Construction with a Swarm of Minimalist Robots using Templates and Feedback, PhD thesis, Monash University, 2006.
A. J. Ijspeert, A. Martinoli, A. Billard, L. M. Gambardella, “Collaboration through the exploitation of local interactions in autonomous collective robotics: the stick pulling experiment,” Autonomous Robots, Vol. 11, pp. 149–171, 2001.
A. Martinoli, A. J. Ijspeert, F. Mondada, “Understanding collective aggregation mechanisms: From probabilistic modelling to experiments with real robots,” Robotics and Autonomous Systems, Vol. 29, pp. 51–63, 1999.
A. Martinoli, A. J. Ijspeert, L. M. Gambardella, “A probabilistic model for understanding and comparing collective aggregation mechanisms,” in D. Floreano, J.-D. Nicoud, F. Mondada, eds., Advances in ArtiŞcial Life: 5th European Conference, ECAL99, Lausanne, Switzerland, September 13-17, 1999. Proceedings, Vol. 1674 of Lecture Notes in ArtiŞcial Intelligence (Subseries of Lecture Notes in Computer Science), pp. 575–584, NY, Springer-Verlag, 1999.
C. A. C. Parker, H. Zhang, C. Ronald Kube, “Blind bulldozing: Multiple robot nest construction,” in Proc. of the 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’03), pp. 2010–2015,
W. M. Spears, D. F. Spears, J. C. Hamann, R. Heil, “Distributed, physics-based control of swarms of vehicles,” Autonomous Robots, Vol. 17, pp. 137–162, 2004.
G. Theraulaz, E. Bonabeau, “Modelling the collective building of complex architectures in social insects with lattice swarms,” Journal of Theoretical Biology, Vol. 177, pp. 381–400, 1995.
C. Melhuish, J. Welsby, C. Edwards, “Using templates for defensive wall building with autonomous mobile ant-like robots,” in Proc. of Towards Intelligent Mobile Robots (TIMR’99), 1999.
J. Wawerla, G. S. Sukhatme, M. J. Matari´c, “Collective construction with multiple robots,” in Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’02), pp. 2696–2701, 2002.
J. K. Werfel, “Building blocks for multi-robot construction,” in Proc. of the 7th International Symposium on Distributed Autonomous Robotic Systems (DARS’04), 2004.
E. O. Wilson, Sociobiology: The New Synthesis, Cambridge, MA, The Belknap Press of Harvard University Press, 1975.
P.-P. Grass´e, “La reconstruction du nid et les coordinations interindividuelles chez Bellicositermes Natalensis et Cubitermes Sp. la th´eorie de la stigmergie: Essai d’interpr´etation du comportement des termites constructeurs,” Insectes Sociaux, Vol. 6, pp. 41–80, 1959.
C. Jones, M. J. Matari´c, “From local to global behavior in intelligent self-assembly,” in Proc. of the 2003 IEEE
International Conference on Robotics and Automation (ICRA’03), pp. 721–726, 2003.
G. Li, H. Zhang, “A rectangular partition algorithm for planar self-assembly,” in Proc. of the 2005 IEEE/RSJ
International Conference on Intelligent Robots and Systems (IROS’05), pp. 3213–3218, 2005.
J. Bishop, S. Burden, E. Klavins, R. Kreisberg, W. Malone, N. Napp, T. Nguyen, “Programmable parts: a demonstration of the grammatical approach to self-organization,” in Proc. of the 2005 IEEE/RSJ International
Conference on Intelligent Robots and Systems (IROS’05), pp. 3684–3691, 2005.
J. K. Werfel, Y. Bar-Yam, R. Nagpal, “Building patterned structures with robot swarms,” in Proc. of the 19th International Joint Conference on ArtiŞcial Intelligence (IJCAI’05), pp. 1495–1502, 2005.
R. L. Stewart, R. A. Russell, “Emergent structures built by a minimalist autonomous robot using a swarm- inspired template mechanism,” in Proc. of the First Australian Conference on ArtiŞcial Life (ACAL’03), pp. 216– , 2003.
R. L. Stewart, R. A. Russell, “Building a loose wall structure with a robotic swarm using a spatio-temporal varying template,” in Proc. of the 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS’04), pp. 712–716, 2004.
R. L. Stewart, R. A. Russell, “A generalised technique for building 2D structures with robot swarms,” in H. A. Abbass, T. Bossomaier, J. Wiles, eds., Recent Advances in ArtiŞcial Life - Advances in Natural Computation - Vol. 3, pp. 265–277, Singapore, World ScientiŞc Publishing Co. Pte. Ltd, 2005.
R. L. Stewart, R. A. Russell, “A distributed feedback mechanism to regulate wall construction by a robotic swarm,” Adaptive Behavior, Vol. 14, pp. 21–51, 2006.
O. H. Bruinsma, An Analysis of Building Behaviour of the Termite Macrotermes subhyalinus (Rambur), PhD thesis, The Netherlands, Landbouwhogeschool te Wageningen, 1979.
G. Theraulaz, E. Bonabeau, J.-L. Deneubourg, “The mechanisms and rules of coordinated building in social insects,” in C. Detrain, J.-L. Deneubourg, J. M. Pasteels, eds., Information Processing in Social Insects, pp. 309– , Basel, Switzerland, Birkh¨auser Verlag, 1999.
R. A. Brooks, “A robust layered control system for a mobile robot,” IEEE Journal of Robotics and Automation, Vol. 2, pp. 14–23, 1986.
J. H. Conway, N. J. A. Sloane, Sphere Packings, Lattices and Groups, NY, Springer-Verlag, 1988.
A. Ostebee, P. Zorn, Multivariable Calculus from Graphical, Numerical, and Symbolic Points of View, Fort Worth, Saunders College Publishing, Harcourt Brace College Publishers, (revised preliminary edition), 1998.
S. M. Ross, Introduction to Probability Models, San Diego, Academic Press, 6th edition, 1997.
W. Feller, An Introduction to Probability Theory and its Applications, Vol. I, NY, John Wiley and Sons, Inc., rd edition, 1968.
J. G. Kemeny, J. L. Snell, Finite Markov Chains, NY, Springer-Verlag, 1983.
N. R. Franks, A. Wilby, B. W. Silverman, C. Tofts, “Self-organizing nest construction in ants: sophisticated building by blind bulldozing,” Animal Behaviour, Vol. 44, pp. 357–375, 1992.
N. R. Franks and J.-L. Deneubourg, “Self-organizing nest construction in ants: individual worker behaviour and the nest’s dynamics,” Animal Behaviour, Vol. 54, pp. 779–796, 1997.
C. Detrain, J.-L. Deneubourg, J. M. Pasteels, eds., Information Processing in Social Insects, Basel, Switzerland, Birkh¨auser Verlag, 1999.
R. Beckers, O. E. Holland, J.-L. Deneubourg. “From local actions to global tasks: stigmergy and collective robotics,” in R. A. Brooks, P. Maes, eds., ArtiŞcial Life IV: Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems, pp. 181–189, Cambridge, MA, MIT Press, 1994.