{'fraction_non_alphanumeric': 0.03478217723528828, 'fraction_numerical': 0.009477026892924482, 'mean_word_length': 4.601723179544191, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Consensus in networks of mobile communicating agents

Populations of mobile and communicating agents describe a vast array of technological and natural systems, ranging from sensor networks to animal groups. Here, we investigate how a group-level agreement may emerge in the continuously evolving network defined by the local interactions of the moving individuals. We adopt a general scheme of motion in two dimensions and we let the individuals interact through the minimal naming game, a prototypical scheme to investigate social consensus. We distinguish different regimes of convergence determined by the emission range of the agents and by their mobility, and we identify the corresponding scaling behaviors of the consensus time. In the same way, we rationalize also the behavior of the maximum memory used during the convergence process, which determines the minimum cognitive/storage capacity needed by the individuals. Overall, we believe that the simple and general model presented in this paper can represent a helpful reference for a better understanding of the behavior of populations of mobile agents.


I. INTRODUCTION
Autonomous mobile and communicating agents provide extremely efficient solutions to a wide range of technological problems by guaranteeing robustness, flexibility, and dynamic adaptability [1]. A typical case is that of a population of robots that have to explore an unknown environment and cope with situations that by definition cannot be foreseen [2,3]. For example, robots could have to negotiate a common lexicon to name different places of the environment they are surveying, and then use this shared linguistic knowledge to carry out goal-directed behavior [4,5]. In the same way, the performances of sensor networks [6] can also be enhanced by the introduction of mobile agents [7,8]. In natural systems, on the other hand, mobile populations that coordinate through chemical or audible signals are obviously widespread, ranging from cell populations [9] to animal groups [10].
In all of these cases, mobile agents locally broadcast their signal to nearby nodes [11][12][13]. Thus, communication takes place on a continuously evolving network whose properties are determined by such parameters as the emission range of the individuals, their mobility, or their density. Network theory [14][15][16][17][18] is therefore the natural framework to investigate the emerging population-scale properties of the system. However, previous research has so far focused mainly on static random geometric networks [11,12], or on the opposite case of rapidly changing structures [19,20]. Only very recently has the more general case of time-dependent networks been fully addressed, for the specific case of the synchronization of mobile oscillators [21].
In this paper, we address the fundamental problem of social consensus. To this end, we model individuals that move in a two-dimensional plane and have to agree on a given convention by performing standard language games [22,23]. For example, they might be in need of creating or selecting autonomously a key for encrypted communication [12], or to independently elect a leader [24]. We then study how different parameters of the mobile agents, in particular their velocity and their communication range, affect the overall agreement process. We are able to identify different regimes ruling the consensus dynamics, and we rationalize our findings by considering the properties of the communication networks.

II. THE MODEL
We model the mobility of the agents according to the general scheme put forth in Ref. [21]. A population of N individuals moves in a two-dimensional L × L box with periodic boundary conditions. The velocity of each agent is v. The angle of the ith agent's motion is ξ i (t k ) ∈ [0,2π ], and it changes randomly at discrete time steps t k (t k+1 − t k = τ M ). Thus, the evolution in time of the ith agent's position is where t τ M . The motion of the individuals is therefore diffusive, the diffusion coefficient being D ∼ v 2 τ M . The agents play the minimal naming game (NG) [25,26] implemented with local broadcasting without feedback [13]. Each agent is characterized by an inventory of words (or "conventions," "opinions," "forms," or "states"). At the beginning, all inventories are empty. At discrete time steps of duration τ S , an agent is randomly selected as speaker. She selects randomly a word from her inventory and transmits it to all the agents within a distance d from her position (if the inventory is empty, she invents a brand new word and stores it into her own inventory before broadcasting it). Each receiving agent updates her state depending on whether her inventory contains the transmitted word. In the first case, the agent deletes all the competing synonyms and keeps only that word into her inventory. In the latter case, on the other hand, she adds the new received word to her inventory. The speaker receives no feedback about her emission, and consequently does not modify her inventory. Figure 1 summarizes the rules of the model. . All the agents within a distance d (gray circles) receive the word and update their inventories as shown in the schematic representation below the box. If an agent already knows that word, she deletes all the competing synonyms in her inventory, otherwise she simply adds the new word to it. No feedback is provided to the speaker, whose inventory is not altered.
For simplicity, in this paper we choose t = τ M = τ S = 1. This means that in a time step (i) all agents move in straight line, (ii) all agents are reassigned a random angle, and (iii) one agent broadcasts to her neighbors.

III. PATHS TO CONSENSUS
The NG is an ordering process. An initially disordered configuration ends up in a consensus, ordered, state in which everybody has the same unique word [25,27]. The consensus (or "convergence") time, t conv , is therefore a crucial quantity. Also important is the maximum number of words that agents have to store, M, which describes the global amount of memory needed by the system to reach a consensus. Previous studies on quenched graphs have shown that both quantities depend dramatically on the topology of the social network describing the possible interactions between the individuals [28]. Consequently, to investigate the properties of a mobile population, it is convenient to focus on the properties of the static network describing the instantaneous communications of the agents. This is the graph that is obtained, at any time, by drawing an undirected link between any two agents that are closer than the emission range d. Recalling that the average degree (i.e., the average number of neighbors of a randomly selected node) of the network is simply k = πNd 2 /L 2 , these values of d identify the following different scenarios: (i) d 1 ≡ d k =1 is the range above which the average degree is larger than 1, so that every emission is received on average by some agent.
(ii) d c ≡ d k 4.51 is the critical value for a percolation transition, yielding a giant component of size N [29].
(iii) d N/2 ≡ d k =N/2 is the point where every communication involves on average the majority of the population.
(iv) d max ≡ d k =N is the value that yields a fully connected network. It holds that d max = L 2 /2.
Of course, it holds that d 1 < d c < d N/2 < d max . In this paper, we set L = 200 and N = 100 unless explicitly stated, so that d 1 11.3, d c 24.1, d N/2 79.8, and d max 141.4. Figure 2 shows the dependence of the average degree and the size of the giant component on the parameter d for this choice of L and N .
For a qualitative partitioning of the observed phenomenology in terms of distinct regimes, it is convenient to consider two time scales. One describes the stability of a cluster of agents, and the other accounts for the time over which a consensus is reached within the same cluster. 1 Their ratio η assesses, therefore, the impact of local, intracluster, activity on global, intercluster, dynamics. For the robustness of a cluster, we consider the average number of time steps needed by an individual to leave a group of size n(d) (an increasing function of d for d < d c ) that scales as t 1 ∼ n(d)/v 2 [21]. For the within-cluster average consensus time, on the other hand, we note that it can be treated as independent from the cluster size n(d), t conv ∼ const, both when the considered groups are densely connected and when they are very small. The reason is that in the first case, the broadcasting rule brings about a very fast consensus time, which becomes instantaneous in fully connected graphs [13], while in the latter case, consensus is quick simply because just a few agents have to agree [13,25]. This approximation is appropriate for our purposes since we aim to define a qualitative index able to discriminate between extreme regimes. Moreover, as we shall see, it is further validated by the results discussed in Sec. III C. Therefore, for the ratio η between the two time scales, it holds that which is obviously an increasing function of d as d < d c .  everybody receives the word transmitted by the first speaker), but it increases for shorter ranges, in a way that crucially depends upon the v parameter. We can identify three regimes.

A. Consensus time
(i) η 1 holds for small d and large v, and implies a rapidly evolving network. Agents continuously change their neighbors, and hence the partners of their communication acts, much like the case of an annealed network. Thus, consensus emerges through global agreement at the system size level after the agents have correlated their inventories so as to allow for successful communication to take place [30]. As d < d 1 , the behavior t conv ∼ 1/ k = 1/d 2 is observed [ Fig. 4(a)], describing the existence of empty communication acts (unheard emissions) when on average each node has fewer than one neighbor.
(ii) η > 1 and d < d c , on the other hand, imply smaller velocities. In this case, small and isolated clusters of agents locally reach an agreement on different conventions. Global consensus emerges at a later time through the competition between these words, in a situation reminiscent of what happens in low-dimensional lattices [31]. The intracluster movements determine the leading time scale, implying a scaling of the form t conv ∼ 1/v 2 [Figs. 4(b) and 4(c)].
(iii) η > 1 and d d c , finally, identify a scenario in which the whole population forms a single connected cluster, describing a random geometric graph. In Ref. [12], Lu and co-workers showed numerically that t conv ∼ 1/ k 2.6 ("when k N ") for static random geometric graphs. 2 Accordingly, in Fig. 5 we observe the behavior t conv ∼ 1/d 5.2 , which, as expected, degrades before d max , where k = N − 1. It may be further noted that, as d > d N/2 , the curves for different v behave identically (Fig. 5, inset). This is due to the fact that here the first speaker transmits her word to an absolute majority of the agents, which on their turn drive the system to consensus very rapidly thanks to the fact that the NG is a drift-driven process [26].

B. Memory usage
The agents get to know different words at the same time during the process that eventually leads them to a consensus, and the NG rules do not fix a limit to the size to their inventory. Therefore, it is important to look at the maximum memory consumption that the population experiences during the whole process, corresponding to the maximum number of words, M, present in the system, i.e., to the sum of the inventory sizes of the N agents. Gaining quantitative insights into the behavior of this quantity is more difficult than for t conv , but some hints can be gained from numerical investigations. Figure 6 shows the average maximum memory per agent as a function of d, and for different values of v.
Again, to understand what goes on in the case of mobile agents, it is helpful to recall the results obtained in static networks. It turns out that a finite connectivity implies finite memory requirements [28], while a fully connected graph would require infinite inventories (in the thermodynamic limit) [25]. In general, a larger average degree requires a bigger memory effort for the agents [28]. Of course, however, the broadcasting rule implies an immediate consensus on fully connected graphs, entailing a minimal amount of memory. Moreover, ordered low-dimensional lattices determine an extremely reduced use of memory, since convergence is reached through the competition of different clusters of agents who have reached a local consensus and therefore store one word only [30,31]. In light of these results, it is possible to rationalize the findings presented in Fig. 6. As expected, when the dominant process is global agreement (η 1, small d and large v), more memory is needed [region (i), above]. Every agent is exposed to a large number of words due to the high mobility of the population. As the velocity is decreased and the system enters the phase of isolated clusters, on the other hand, consensus is reached with a smaller memory demand, due to the early onset of regions of local agreement [region (ii)]. As the emission range is increased and one single connected cluster emerges, finally, curves for different values of v become more and more similar and collapse as d > d N/2 (Fig. 6, inset), as observed for t conv [region (iii)]. Curves for small v exhibit a peak somewhere in the region d c < d < d N/2 (more precisely, for 50 < d < 60 in Fig. 6), separating the memory-favorable cases of a fully connected graph and a collection of isolated clusters. However, as d is further decreased, the memory requirements grow again. Qualitatively, this behavior can be understood considering that when d < d 1 , local clusters are in general treelike, so that more words can coexist in each of them before a local agreement emerges.

C. Role of the population density
In finite static networks, the global consensus is reached only if d > d c , when all the nodes belong to the same unique giant connected component. Previous studies [12], conducted adopting a slightly modified NG protocol, showed an N α , with α 2.1, dependence of the consensus time on the population size N in random geometric graphs with fixed average connectivity (and consequently varying L), and, as mentioned above, an important role also for the average degree, t conv ∼ k −2.6 (as far as k N ) for fixed L. The scaling of t conv with the population size agrees well with a theoretical argument put forth in Ref. [12], which is in turn very similar to the analysis of the NG in low-dimensional lattices [31]. The crucial point is that different clusters of local consensus emerge rapidly, and the global agreement is the result of a cluster-cluster competition. The presence of mobility causes this whole argument to break down, and the increased population mixing yields a faster scaling of the consensus (data not shown), in agreement with what is observed in small-world networks [12,32].
Crucially, on the other hand, mobility guarantees that the consensus is always reached, at least asymptotically, independently from the emission range of the individuals. However, it is important to note that population size and average degree are intimately connected in the framework we are addressing, where the box side L is kept constant. Indeed, as discussed above, it holds that k ∝ N , and therefore with d N/2 being the only characteristic length surviving in the thermodynamic limit. The "small" range regimes we have described would therefore vanish for very large population size.
Concretely, the case of very large population densities is quite unrealistic from the point of view of any application involving mobile individuals. However, for the sake of completeness, we report in Fig. 7 the results of numerical investigations for different values of d and v. For small velocities (left column), very small population sizes are not efficient since the individuals waste time in finding each other. As d grows, however, t conv saturates. After a certain threshold, the broadcasting rule makes the actual number of agents present in the population irrelevant. A similar behavior is observed for the case of a larger mobility of the individuals (right column). Here, however, smaller population sizes converge slightly faster since agents get more easily in contact, and the dynamic of the NG favors a smaller number of competing conventions. In addition, the augmented population mixing is responsible for the fact that (i) the consensus time does not reach a plateau but keeps increasing very slowly with the system size, as t conv ∼ N α , with α < 0.05, and (ii) the memory consumption is larger, in agreement with what is observed in the case of static networks for the NG with pairwise interactions [28]. Finally, it is worth noting that the very weak dependence of the consensus time on N validates, a posteriori, the assumption on the constant behavior of t conv that yielded Eq. (3).

IV. CONCLUSION
In this paper, we have analyzed the consensus problem in a population of autonomous mobile agents. We have focused on the crucial case of a self-organized agreement process, to be established without any central control or coordination. Agents move with the same velocity and different, randomly changing, angles in a two-dimensional space, and communicate through the NG protocol, locally broadcasting in a circle of radius d. We have shown that different characteristic emission ranges exist, defining, together with the mobility rates of the agents, the boundaries between different consensus regimes. In particular, we have highlighted three main mechanisms ruling the onset of consensus. If the emission range is small, a rapidly mixing population will undergo a global agreement process, while a slower mobility will bring about the appearance of isolated clusters in which a local consensus on different conventions forms rapidly, the final consensus resulting from the competitions of these clusters. Finally, large emission ranges establish a single connected cluster where the static limit of random geometric networks is recovered. Accordingly, we have pointed out the scaling relations of the consensus time in each region and rationalized the memory needs of the agents. Finally, we have considered the role of the population density, showing that, due to the broadcasting rule, even unrealistically high densities have a small impact on both the consensus time and the memory consumption of the agents.
Examples of populations of mobile and communicating agents pop out in many natural contexts, chiefly in cases of groups of animals or micro-organisms. Yet, it is perhaps the technological advancement in the fields of robotics and telecommunications that makes the investigation of this issue increasingly urgent. From this point of view, the results presented in this paper may be far-reaching. Both the mobility and the communication models we have adopted are indeed straightforward and might serve as a reference to gain insights into more complex and realistic models. At the same time, the scheme we have introduced can be extended in the future so as to address such issues as the coupling between motion and communication. For example, our results show that the larger the agents' mobility, the shorter is the consensus time, so that changing neighbors frequently turns out to be an efficient strategy. Thus, agents with a tendency to move apart from each other after a success could expedite convergence, preventing the formation of local clusters. On the contrary, individuals with a tendency to reinforce existing links by aligning their direction of motion after a successful interaction would probably lead to the emergence of different swarms or flocks, internally agreeing on different conventions, that would move apart from each other and hinder the onset of a global agreement. Along the same lines, finally, another possibility for future work could imply the adoption and study of higher level communication protocols, such as spatially oriented language games [4,5].