Paper detail

AntPaP: Patrolling and Fair Partitioning of Graphs by A(ge)nts Leaving Pheromone Traces

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.