Abstract
This paper addresses a special type of graph, the k-neighbourhood graph, for the usage in huge multi agent systems. It can be used to establish slim communication structures in extensive groups of agents as they are present e.g. in swarm applications. We will prove some properties of k-neighbourhood graphs in two- and three-dimensional Euclidean space, i.e. we show that the maximum number of incoming connections per agent is limited to a value independent from the overall number of agents in the system. For the two-dimensional case we prove a maximum in-degree of 6 ·k. Furthermore, for agents interacting in three dimensions an upper and a lower bound for this value is presented.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ferber, J.: Multi-agent systems: An introduction to distributed artificial intelligence. Addison-Wesley, Harlow (1999)
Bonabeau, E., Dorigo, M., Theraulaz, G.: Swarm Intelligence - From natural to artificial Systems. Oxford University Press, Oxford (1999)
Matarić, M.J.: Using communication to reduce locality in distributed multi-agent learning. In: Weiss, G. (ed.) Journal of Experimental and Theoretical Artificial Intelligence, special issue on Learning in DAI Systems 10(3), 357–369 (1998)
Nii, H.P.: Blackboard systems, part one: The blackboard model of problem solving and the evolution of blackboard architectures. AI Magazine 7, 38–53 (1986)
Gao, J., Guibas, L., Hershberger, J., Zhang, L., Zhu, A.: Geometric spanner for routing in mobile networks (2001)
Eppstein, D.: Spanning trees and spanners. Technical Report Technical Report 96-16, University of California, Dept. Information and Computer Science (1996)
Schindelhauer, C., Volbert, K., Ziegler, M.: Spanners, weak spanners, and power spanners for wireless networks. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol. 3341, pp. 805–821. Springer, Heidelberg (2004)
Goebels, A., Büning, H.K., Priesterjahn, S., Weimer, A.: Towards online partitioning of agent sets based on local information. In: Proceedings of the International Conference on Parallel and Distributed Computing and Networks (PDCN), Innsbruck, Austria (2005)
Goebels, A.: Learning useful communication structures for groups of agents. In: Proceedings of the IFIP Conference on Biologically Inspired Cooperative Computing, BICC 2006, Santiago de Chile, Chile (2006)
Eppstein, D., Paterson, M.S., Yao, F.F.: On nearest-neighbor graphs. GEOMETRY: Discrete & Computational Geometry 17 (1997)
Vaidya, P.: An O(n logn) algorithm for the all-nearest-neighbors problem. Discrete and Computational Geometry (4), 101–115 (1989)
Callahan, P.: Optimal parallel all-nearest-neighbours using the well-separated pair decomposition. In: Proceedings of the 34th IEEE Symposium Foundations of Computer Science, pp. 332–340 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goebels, A. (2006). Studies on Neighbourhood Graphs for Communication in Multi Agent Systems. In: Jiao, L., Wang, L., Gao, X., Liu, J., Wu, F. (eds) Advances in Natural Computation. ICNC 2006. Lecture Notes in Computer Science, vol 4222. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11881223_56
Download citation
DOI: https://doi.org/10.1007/11881223_56
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-45907-1
Online ISBN: 978-3-540-45909-5
eBook Packages: Computer ScienceComputer Science (R0)