A Design Pattern for Decentralised Decision Making

Abstract

The engineering of large-scale decentralised systems requires sound methodologies to guarantee the attainment of the desired macroscopic system-level behaviour given the microscopic individual-level implementation. While a general-purpose methodology is currently out of reach, specific solutions can be given to broad classes of problems by means of well-conceived design patterns. We propose a design pattern for collective decision making grounded on experimental/theoretical studies of the nest-site selection behaviour observed in honeybee swarms (Apis mellifera). The way in which honeybee swarms arrive at consensus is fairly well-understood at the macroscopic level. We provide formal guidelines for the microscopic implementation of collective decisions to quantitatively match the macroscopic predictions. We discuss implementation strategies based on both homogeneous and heterogeneous multiagent systems, and we provide means to deal with spatial and topological factors that have a bearing on the micro-macro link. Finally, we exploit the design pattern in two case studies that showcase the viability of the approach. Besides engineering, such a design pattern can prove useful for a deeper understanding of decision making in natural systems thanks to the inclusion of individual heterogeneities and spatial factors, which are often disregarded in theoretical modelling.

Fig 1. Probabilistic Finite State Machines (PFSMs) describing the microscopic behaviour of an agent in average.

Here, the notation ${\mathcal{P}}_{{\lambda }_i}$ is a shorthand for ${\mathcal{P}}_{\lambda }\left(v_i\right)$ (A) PFSM describing the basic commitment dynamics. Spontaneous transitions are represented by solid lines, interactive transitions by dashed lines. For a complete version with n + 1 states, see panel A in S1 Fig (B) PFSM describing the dynamics of activity change as agents switch from latent to interactive states. Latent states are indicated in grey, while changes in the activity state are represented by dash-dotted arrows. (C) PFSM describing the coupled dynamics of commitment and activity change. For a complete version with 2(n + 1) states, see panel B in S1 Fig.

Fig 2. Collective decisions on a fully-connected network: comparison between the micro and the macro dynamics and scaling properties.

(A,C) Comparison between the stochastic finite-size macroscopic model (black lines) and the multiagent implementation with both the homogeneous strategy (red lines) and the heterogenous strategy (green lines). Results are displayed for varying system size N. For each possible configuration (v _A, v _B), 500 independent runs are performed. We show results for configurations with effectivity $\mathcal{E}>0.7$. The plot is divided in two parts: in the bottom-right triangle, we consider the success rate $\mathcal{S}$ for each configuration (v _A, v _B), where v _A ≥ v _B. For each group size N, we show the isolines at $\mathcal{S}=0.9$. The gray triangle indicates quality value pairs below the target resolution R = 0.15 (i.e., configurations in which the two options are considered equivalent). In the top-left half of the plot, we consider the convergence time $\mathcal{C}$ for each configuration (v _A, v _B), where v _B ≥ v _A (i.e., the symmetric problems with respect to the bottom-right plot). For each group size N, we show the isolines at $\mathcal{C}=\widehat{\mathcal{C}}$. (B, D) Scaling of the convergence time $\mathcal{C}$ with the system size N. For each configuration (v _A, v _B), we fit the curve $\mathcal{C}=b{N}^a$ and we show the heat-map for the fitted coefficient a (see the bottom-right triangle showing the coefficient value for each configuration (v _A, v _B), v _A ≥ v _B) and b (see the top-left triangle showing the coefficient value for symmetric configurations (v _A, v _B), v _B ≥ v _A) across the decision space. Also in this case we show only configurations where $\mathcal{E}>0.7$ for all N, and the white space indicates configurations with low effectivity. (A,B) Results for case-study 1A with v _i ∈ [0, 1], γ _i = 0.6v _i, α _i = 0, ρ _i = 0.1v _i, σ _i = 1 and i ∈ {A, B}, $\widehat{\mathcal{C}}=50s$. (C,D) Results for case-study 1B with v _i ∈ [1, 10], γ _i = ρ _i = v _i, α _i = 1/v _i, σ _i = 10 and i ∈ {A, B}, $\widehat{\mathcal{C}}=1s$.

Fig 3. Collective decisions in a search and exploration problem: comparison between the micro and the macro dynamics.

The state space of the system is presented as a ternary plot characterised by Ψ_U + Ψ_A + Ψ_B = 1, so that vertices correspond to fully-uncommitted or fully-committed populations. Macroscopic dynamics are indicated by trajectories and equilibrium points from the ODE model of Eq (1), parametrised according to the specific configuration. The bold yellow trajectory indicates the behaviour starting from a fully-uncommitted population (Ψ_U = 1). Stable equilibrium points are indicated as blue empty circles, while unstable points are indicated as green empty diamonds. The density map in the background represents the results of homogeneous multiagent simulations (1000 runs). The inset shows the success rate $\mathcal{S}$ for macroscopic Gillespie simulations (white bars) and multiagent simulations (homogeneous in light gray and heterogeneous in dark grey). (A) Micro-macro link for a decision problem in which the best option is also the farthest one (v _A = 0.7 < v _B = 1 and d _A = 1.5 m < d _B = 2.5 m). The magnify-glass effect allows to appreciate the close correspondence between the stable point predicted by the macroscopic model and the results from the multiagent simulations. (B) Micro-macro link for a completely symmetric decision problem (v _A = v _B = 1 and d _A = d _B = 2.5 m).