AntPaP: Patrolling and Fair Partitioning of Graphs by A(ge)nts Leaving Pheromone Traces
DOI:
https://doi.org/10.15837/ijccc.2025.1.6907Keywords:
multi-agent system, partitioning, simple interactionsAbstract
A team of identical and oblivious ant-like agents – a(ge)nts – leaving pheromone traces, are programmed to jointly patrol an area modeled as a graph. They perform this task using simple local interactions, while also achieving the important byproduct of partitioning the graph into roughly equal-sized disjoint sub-graphs. Each a(ge)nt begins to operate at an arbitrary initial location, and throughout its work does not acquire any information on either the shape or size of the graph, or the number or whereabouts of other a(ge)nts. Graph partitioning occurs spontaneously, as each of the a(ge)nts patrols and expands its own pheromone-marked sub-graph, or region. This graph partitioning algorithm is inspired by molecules hitting the borders of air filled elastic balloons: an a(ge)nt that hits a border edge from the interior of its region more frequently than an external a(ge)nt hits the same edge from an adjacent vertex in the neighboring region, may conquer that adjacent vertex, expanding its region at the expense of the neighbor. Since the rule of patrolling a region ensures that each vertex is visited with a frequency inversely proportional to the size of the region, in terms of vertex count, a smaller region will effectively exert higher “pressure” at its borders, and conquer adjacent vertices from a larger region, thereby increasing the smaller region and shrinking the larger. The algorithm, therefore, tends to equalize the sizes of the regions patrolled, resembling a set of perfectly elastic physical balloons, confined to a closed volume and filled with an equal amount of air. The pheromone based local interactions of agents eventually cause the system to evolve into a partition that is close to balanced rather quickly, and if the graph and the number of a(ge)nts remain unchanged, it is guaranteed that the system settles into a stable and balanced partition.
References
Y. Elor, A. M. Bruckstein, "Multi-a(ge)nt graph patrolling and partitioning". Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology-Volume 02. IEEE Computer Society, 2009. https://doi.org/10.1109/WI-IAT.2009.125
I.A.Wagner, M. Lindenbaum, A. M. Bruckstein, "Efficiently searching a graph by a smell-oriented vertex process". Annals of Mathematics and Artificial Intelligence, 24(1-4):211-223, 1998. https://doi.org/10.1023/A:1018957401093
S. Even, "Graph Algorithms". Rockville, MD: Comput. Sci. Press, 1979
P. Berkhin, "A survey of clustering data mining techniques." Grouping multidimensional data. Springer Berlin Heidelberg, pp. 25-71, 2006. https://doi.org/10.1007/3-540-28349-8_2
C. J. Alpert, A. B. Kahng, "Recent directions in netlist partitioning: a survey", Integration, the VLSI Journal , 19(1-2):1-81,1995 https://doi.org/10.1016/0167-9260(95)00008-4
K. Schloegel, G. Karypis, V. Kumar, "Parallel static and dynamic multi-constraint graph partitioning", Concurrency and Computation: Practice and Experience, 14 (3):219-240,2002 https://doi.org/10.1002/cpe.605
R. G. Downey, V. Estivill-Castro, M. R. Fellows, E. Prieto, F. A. Rosamond, "Cutting Up Is Hard To Do: the Parameterized Complexity of k -Cut and Related Problems", Electronic Notes in Theoretical Computer Science, 78():209-222,2003 https://doi.org/10.1016/S1571-0661(04)81014-4
R. Tarjan, "Depth-First Search and Linear Graph Algorithms", SIAM, 1(2):146-160, 1972 https://doi.org/10.1137/0201010
J. D. McCaffrey. "Graph Partitioning using a Simulated Bee Colony Algorithm", IEEE Conference on Information Reuse and Integration (IRI) Las Vegas, USA, pp. 400-405, 2011 https://doi.org/10.1109/IRI.2011.6009581
F. Comellas, E. Sapena, "A multiagent algorithm for graph partitioning". EvoWorkshops, Lecture Notes in Computer Science 3907:279-285, 2006 https://doi.org/10.1007/11732242_25
Y. Chevaleyre, F. Sempe, G. Ramalho, "A theoretical analysis of multi-agent patrolling strategies." Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 3. IEEE Computer Society, pp. 1524-1525, 2004.
F. Lauri, F. Charpillet, "Ant colony optimization applied to the multi-agent patrolling problem." IEEE Swarm Intelligence Symposium, 2006.
M. Dorigo, V. M. Maniezzo, A. Colorni, "Ant system: optimization by a colony of cooperating agents." IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 26(1): 29-41, 1996. https://doi.org/10.1109/3477.484436
E. Gyori, "On division of graphs to connected subgraphs." Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely). Vol. 1, 1976.
R. G. Gallager, Stochastic processes: theory for applications. Cambridge University Press, 2013. https://doi.org/10.1017/CBO9781139626514
A. Nerode, "Linear automaton transformations." Proceedings of the American Mathematical Society 9(4): 541-544, 1958 https://doi.org/10.1090/S0002-9939-1958-0135681-9
Additional Files
Published
Issue
Section
License
Copyright (c) 2024 Gidon Elazar, Alfred Bruckstein
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
ONLINE OPEN ACCES: Acces to full text of each article and each issue are allowed for free in respect of Attribution-NonCommercial 4.0 International (CC BY-NC 4.0.
You are free to:
-Share: copy and redistribute the material in any medium or format;
-Adapt: remix, transform, and build upon the material.
The licensor cannot revoke these freedoms as long as you follow the license terms.
DISCLAIMER: The author(s) of each article appearing in International Journal of Computers Communications & Control is/are solely responsible for the content thereof; the publication of an article shall not constitute or be deemed to constitute any representation by the Editors or Agora University Press that the data presented therein are original, correct or sufficient to support the conclusions reached or that the experiment design or methodology is adequate.
