Abstract
We study collective decision-making in a swarm of robots. We consider the majority rule with differential latency: robots randomly form teams, make a decision following the majority rule, and then turn in a latent state whose duration depends on the decision made. While latent, robots do not participate in the decision mechanism, thus, the differential latency provides a positive feedback that favors the decision with the shortest latency. We analyze the dynamics using a discrete, time-homogeneous, absorbing Markov chain.
Access provided by Autonomous University of Puebla. Download conference paper PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
We study a collective decision-making mechanism for a swarm of robots. Swarm robotics [9] is a novel approach in robotics that takes inspiration from social insects to deal with large groups of relatively simple robots. Robots in a swarm act only on the basis of local knowledge, without any centralized director, hence, in a completely self-organized and distributed manner. The behavior of the swarm is a result of the interaction of its components, the robots. The analysis of collective decision-making mechanisms plays a crucial role in the design of swarm behaviors.
We analyze a swarm robotics system originally proposed by Montes de Oca et al. [7]. Robots in the swarm need to collectively decide between two possible actions to perform, henceforth referred to as action A and action B. Actions have the same outcome but different execution times. The goal of the swarm is to reach consensus on the action with the shortest execution time. In particular, Montes the Oca et al. studied this system in a collective transport scenario where robots in the swarm need to transport objects from a source area to a destination area. To this end, robots can choose between two possible paths. This corresponds to perform action A or action B. The two paths differ in length and thus in the traversal time. Each robot in the swarm has an opinion for a particular path. Moreover, an object is too heavy for a single robot to be transported. A team of 3 robots is needed. The team collectively decides which path to take considering the opinion favored by the majority.
Opinion formation models, such as the majority-rule model by Galam [2], allow us to study and analyze this kind of systems. Krapivsky and Redner [4] provided an analytical study of the majority-rule model under the assumption of a well mixedFootnote 1 population of agents. Later, Lambiotte et al. [5] extended the work of Krapivsky and Redner introducing the concept of latency. In the model of Lambiotte et al., when an agent switches opinion as a consequence of the application of the majority rule, it turns in a latent state for a latency period that has stochastic duration. A latent agent may still participates in voting, thus influencing other agents, but its opinion does not change as a result of the decision. This extension gives rise to a richer dynamics depending on the duration of the latency period. Based on these works, Montes de Oca et al. [7] proposed the differential latency model where the duration of the latency period depends on the particular opinion adopted. After a decision, differently from the model of Lambiotte et al., the team of agents become latent with a common latency period and is not involved in further voting until the end of the latency period. Montes de Oca et al. showed that the differential latency in the majority-rule model steers the agents towards consensus on the opinion associated to the shortest latency. Montes de Oca et al. applied these results to the study of the swarm robotics system described above by modeling actions of the robots as opinions and their execution times as the latency periods of different duration.
In the context of swarm robotics, a number of works has been devoted to the differential latency model. Montes de Oca et al. [7] first proposed a fluid-flow analysis of this model—using a system of ODEs—aimed at studying the dynamics leading to consensus. This analysis, derived in the limit of an infinite population, deterministically predicts consensus as a function of the initial configuration of the system. However, in a finite population, random fluctuations may drive the system to converge to the long path, even when the fluid-flow model predicts that it should converge to the short one. Later, Scheidler [10] extended the previous analysis using methods from statistical physics—e.g., master equation and Fokker-Planck equation—to derive continuous approximations of a system with a finite population size. With this approach, Scheidler was able to study the exit probability, i.e., the probability that the system eventually reaches consensus on the opinion associated to the shortest latency, and the expected time necessary to reach consensus. Finally, Massink et al. [6] provided a specification of the system using a stochastic process algebra. On the basis of this specification, the authors obtained a statistical model checking and a fluid-flow analysis.
Continuous approximations provide reliable predictions only when the number of robots is relatively large—e.g., thousands of robots. However, swarm robotics aims to design scalable control policies that operate for swarms of any size, ranging from tens to millions of robots. These models cover only the upper part of this range. Besides, from a continuous approximation model, it is usually hard to derive statistics different from the expected value, which in turn, often gives a poor representation of the underlying distribution—e.g., when the variance is large compared to the expected value or when the distribution is not symmetric.
The aim of this work is to study the majority rule with differential latency with an approach able to cope with the limitations of previous approaches. Inspired by the work of Banish et al. [1], we use the formalism of time homogeneous Markov chains with finite state space [3]. In particular, it results that the Markov chain describing the system is absorbing [3]. This approach allows us to consider systems of any finite size and to derive reliable estimations of both the exit probability and the distribution of the number of decisions necessary to reach consensus.
1 Markov Chain Model
We model the majority rule with differential latency in a system of M robots as an absorbing Markov chain [3]. Robots can be latent or non-latent. Only non-latent robots, once grouped in a team of 3 members, take part to the decision-making mechanism. As in Montes de Oca et al. [7], we consider a scenario where the number k of latent teams is constant, and where the latency period follows an exponential distribution whose expected value depends on the team’s opinion. Without loss of generality, we consider the expected latency periods to be 1 for opinion A and 1/λ with 0⩽λ⩽1 for opinion B. Moreover, we are interested in the number ϑ of applications of the majority rule, thus, we consider each application of the decision-making mechanism as one step of the process along the chain. At each step ϑ we consider 3 stages:
-
(1)
A latent team becomes non-latent (it finishes its latency period).
-
(2)
A new team of 3 robots is randomly formed out of the set of non-latent robots.
-
(3)
The team applies the majority rule to decide the team’s opinion. Next, it turns in a latent state.
We are interested in the evolution over ϑ of the number of robots with opinion A—the opinion associated to the shortest latency. Let \(\mathbb{N}\) be the set of naturals. The state of the Markov chain is a vector s=(s l,s n), where \(s^{l} \in \{l: l \in \mathbb{N}, 0 \leqslant l \leqslant k \}\) is the number of latent teams with opinion A and \(s^{n} \in \{ n: n \in \mathbb{N}, 0 \leqslant n \leqslant M-3k \}\) is the number of non-latent robots with opinion A. The state space of the Markov chain consists of m states, where m=(k+1)(M−3k+1) is the cardinality of the Cartesian product of the domains of s l and s n. By s i and s j we refer to two generic states. By s a and s b we refer to the consensus states in which the whole swarm agrees on opinion A and B, respectively. Notice that s a and s b are the absorbing states of the chain, that is, states that once reached can never be left [3].
At the generic step ϑ, the process moves from s(ϑ)=s i to s(ϑ+1)=s j following the aforementioned 3 stages. At stage (1), a latent team finishes its latency period, becomes non-latent and disbands. The probability p i that this team has opinion A is:
The set of non-latent robots with opinion A increases of c=3 units, if the disbanding team has opinion A; and of c=0, otherwise. At stage (2), 3 random robots form a new team in the set of non-latent robots. We are interested in the probability q i that the new team has a number 0⩽d⩽3 of preferences for opinion A. This probability is given by the hyper-geometric distribution
of the M−3k+3 preferences in the current set of non-latent robots, composed of \(s_{i}^{n} + c\) votes for opinion A and \(M-3k-s_{i}^{n}+3-c\) votes for opinion B. At stage (3), the majority rule is applied and the outcome is determined by the value of d. Eventually, the process moves to the next state s(ϑ+1)=s j .
Equations (79.1) and (79.2) allow us to define the transition probabilities between each possible pair of states s i and s j . These probabilities are the entries of the stochastic transition matrix P, which completely defines the dynamics of a Markov chain, cf. Kemeny and Snell [3]. However, not all pairs of states define a feasible move of the process along the chain according to the rules of the system, i.e., not all pair of states are adjacent. Two states s i and s j are adjacent if Δ ij s=(Δ ij s l,Δ ij s n)=s j −s i appears in the first column of the following table. The correspondent transition probability P ij is given in the second column:
(Δ ij s l,Δ ij s n) | P ij | Stage (1) | Stage (2) |
---|---|---|---|
(−1,3) | p i q i (3−Δ ij s n;3) | A | 3B |
(−1,2) | A | A2B | |
(0,1) | A | 2AB | |
(0,0) | p i q i (3−Δ ij s n;3)+(1−p i )q i (|Δ ij s n|;0) | A | 3A |
B | 3B | ||
(0,−1) | (1−p i )q i (|Δ ij s n|;0) | B | A2B |
(1,−2) | B | 2AB | |
(1,−3) | B | 3A |
Columns three and four provide the corresponding events observed in stages (1) and (2), respectively: the opinion of the robots in the next latent team finishing its latency period and the opinions of the robots that randomly form a new team in the set of non-latent robots. For values of Δ ij s not included in column one, the transition probability is P ij =0.
The probabilistic interpretation of P is straightforward: at any step ϑ, if the process is in state s(ϑ)=s i it will move to state s(ϑ+1)=s j with probability P ij . It is worth noticing that, being the consensus states s a and s b two absorbing states, the probability mass of s a and s b is concentrated in the corresponding diagonal entries of P, that is: P aa =1 and P bb =1.
2 Analysis of Opinion Dynamics
In order to analyze the dynamics of the majority rule with differential latency, we define, on the basis of P, the matrices Q, R, and N of Kemeny and Snell [3]. Q describes transitions between transient states, R gives the probability to move from a transient state to an absorbing state, and N=(I−Q)−1 is the fundamental matrix with I being the identity matrix. From matrices Q, R, and N of the Markov chain model we study the behavior of the system. We validate the predictions of the model with the results of Monte Carlo simulationsFootnote 2 averaged over 1000 independent runs for each choice of the parameters of the system.
First, we derive the exit probability E(s i ), i.e., the probability that a system of M robots that starts in the initial configuration s(ϑ 0)=s i reaches consensus on the opinion associated to the shortest latency—opinion A. This probability is given by the entries associated to the consensus state s a of the product NR, which corresponds to the matrix of the absorption probabilities [3].
Figure 79.1 reports the predictions of the exit probability over the initial density \(\delta=(3s_{i}^{l}+s_{i}^{n})/ M\) of robots favoring opinion A for several configurations of the system. As found by Scheidler [10], the larger is the expected latency period 1/λ associated to opinion B, the smaller is the initial number of preferences for opinion A such that the exit probability is E(s i )>0.5. Moreover, when the number of robots M increases, the exit probability approaches a step function around the critical density. It is worth noticing that the Markov chain model predicts the outcome of the simulations with great accuracy, regardless of the number of robots. A result that in general cannot be achieved using continuous approximations approaches.
Next, we analyze the number τ of applications of the majority rule necessary to reach consensus. As stated above, we consider each step along the chain as one application on the decision-making mechanism. The expected value of τ is given by \(\hat{\tau} = \xi N\), where ξ is a column vector of all 1s. The entries of \(\hat{\tau}\) correspond to the row sums of the fundamental matrix N. In turn, N gives the mean sojourn time for each transient state of a Markov chain [3], that is, the expected number of times that a process started in state s(ϑ 0)=s i passes from state s j . The variance of τ is given by \(\hat{\tau}_{2} = (2N - I)\hat{\tau} - \hat{\tau}_{sq}\), where I is the identity matrix and \(\hat{\tau}_{sq}\) is \(\hat{\tau}\) with squared entries [3].
Figures 79.2(a) and 79.2(b) show the predictions of the expectation \(\hat{\tau}\) and the variance \(\hat{\tau}_{2}\) of the number of decisions necessary before consensus for a system with M=50 robots. Again, the Markov chain model predicts the Monte Carlo simulations with great accuracy. Similarly to the findings of Scheidler [10] for the consensus time, the value of \(\hat{\tau}\) is maximum near the critical density of the initial number of robots favoring opinion A. However, the expected number of decisions, which is related to the consensus time in Scheidler [10], is not a reliable statistics for this system. Indeed, the variance \(\hat{\tau}_{2}\) is about three orders of magnitude larger than \(\hat{\tau}\).
Finally, we derive the cumulative distribution function P(τ⩽ϑ;s i ) of the number of decisions before consensus as well as its probability mass function P(τ=ϑ;s i ). From a swarm robotics perspective, we are interested in the dynamics of a system initially unbiased, i.e., a system that starts with an equal proportion of preferences for the opinions A and B. Let s(ϑ 0)=s u represents this initial unbiased configuration. Recalling that Q is the matrix of the transition probabilities for the transient states, we have that the entries \(Q_{uj}^{\vartheta}\) of the ϑth power of Q give the probabilities to be in the transient state s j at step ϑ when starting at s u . Thus, the row sum of the uth row of Q ϑ gives the probability to still be in one of the transient states. From this probability, we can derive the cumulative distribution function P(τ⩽ϑ;s u ) simply by computing the series \(\{1 - \sum_{j} Q^{\vartheta}_{uj}\}\) for values of ϑ such that Q ϑ→0.
Figure 79.2(c) shows the cumulative distribution function P(τ⩽ϑ;s u ) for a system of M=50 robots that starts unbiased. Obviously, the longer is the latency period 1/λ of opinion B, the larger is the number of applications of the majority rule necessary to reach consensus. Figure 79.2(d), provides the probability mass function P(τ=ϑ;s u ), together with details of mode, median, and mean values of τ. As we can see, the values of the mode, median and mean statistics diverge for increasing values of the ratio 1/λ of the two expected latency periods. Moreover, when 1/λ→∞ the shape of the distribution P(τ=ϑ;s u ) tends to a flat function, thus revealing that the variance dominates the system.
3 Conclusion
We designed an absorbing Markov chain model for collective decisions in a system with a finite number of robots based on the majority rule with differential latency. Using our model, we derived: the probability that a system of M robots reaches consensus on the opinion associated to the shortest latency period, and the distribution of the number of applications of the majority rule necessary to reach consensus. This latter reveals that the system is characterized by a large variance of the number of decisions necessary before consensus, and thus, that its expected value, which was mainly adopted in previous studies, is a poor statistic for this system. In contrast to continuous approximations, we explicitly model the state space of the system—which is discrete—and the transition probabilities governing its dynamics. This approach allows us to always derive reliable predictions of a system regardless of its size.
Our contribution is relevant from a swarm robotics perspective not only for the reliability of its predictions; but also, because it allows us to perform a deeper analysis of the system. The analysis of our Markov chain model, with particular regard to the distribution of the number of decisions necessary to consensus, gives the possibility to perform statistical inference on certain interesting aspects of the system. Moreover, the approach can be easily extended to other voting schemata, allowing the comparison at design time of different choices for the decision-making mechanism.
In real-robot experiments, latency periods are unlikely to be exponentially distributed. Moreover, it is hard to ensure a constant number of teams in time. These assumptions represent hard constraints for a swarm robotics system. Massink et al. [6] propose to cope with these constraints modeling the latency period with an Erlang distribution. We plan to extend our approach in a similar way and to validate the resulting model with physics-based simulations and real-robot experiments.
Notes
- 1.
In a well mixed population each agent has the same probability to interact with each other agent [8].
- 2.
We simulated two sets of robots: latent teams characterized by an opinion and a latency, and non-latent robots described only by their opinions. The simulation proceeds as follow until consensus is reached: (1) the latent team having minimum latency is disbanded and its component robots are added to the set of non-latent robots, (2) 3 robots are randomly sampled from the set of non-latent robots and the majority rule is applied among them, (3) the new team is added to the set of latent teams and its latency is drawn from the exponential distribution according to the team’s opinion.
References
Banisch S, Lima R, Araujo T (2011) Agent based models and opinion dynamics as Markov chains. arXiv:1108.1716v2
Galam S (1986) Majority rule, hierarchical structures, and democratic totalitarianism: a statistical approach. J Math Psychol 30(4):426–434
Kemeny JG, Snell JL (1976) Finite Markov chains. Springer, New York
Krapivsky PL, Redner S (2003) Dynamics of majority rule in two-state interacting spin systems. Phys Rev Lett 90:238701
Lambiotte R, Saramaki J, Blondel VD (2009) Dynamics of latent voters. Phys Rev E 79:046107
Massink M, Brambilla M, Latella D, Dorigo M, Birattari M (2012, in press) Analysing robot decision-making with bio-pepa. In: Proceedings of the eighth international conference on swarm intelligence, ANTS 2012. Lecture notes in computer science. Springer, Berlin
Montes de Oca M, Ferrante E, Scheidler A, Pinciroli C, Birattari M, Dorigo M (2011) Majority-rule opinion dynamics with differential latency: a mechanism for self-organized collective decision-making. Swarm Intell 5:305–327. doi:10.1007/s11721-011-0062-z
Nowak MA (2006) Five rules for the evolution of cooperation. Science 314(5805):1560–1563
Şahin E (2005) Swarm robotics: from sources of inspiration to domains of application. In: Şahin E, Spears W (eds) Swarm robotics. Lecture notes in computer science, vol 3342. Springer, Berlin, pp 10–20
Scheidler A (2011) Dynamics of majority rule with differential latencies. Phys Rev E 83:031116
Acknowledgements
The research leading to the results presented in this paper has received funding from the European Research Council under the European Union’s Seventh Framework Programme (FP7/2007–2013)/ERC grant agreement no. 246939. Mauro Birattari and Marco Dorigo acknowledge support from the F.R.S.-FNRS of Belgium’s Wallonia-Brussels Federation.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Valentini, G., Birattari, M., Dorigo, M. (2013). Majority Rule with Differential Latency: An Absorbing Markov Chain to Model Consensus. In: Gilbert, T., Kirkilionis, M., Nicolis, G. (eds) Proceedings of the European Conference on Complex Systems 2012. Springer Proceedings in Complexity. Springer, Cham. https://doi.org/10.1007/978-3-319-00395-5_79
Download citation
DOI: https://doi.org/10.1007/978-3-319-00395-5_79
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-00394-8
Online ISBN: 978-3-319-00395-5
eBook Packages: Physics and AstronomyPhysics and Astronomy (R0)