Sociogenesis in unbounded space: modelling self-organised cohesive collective motion

Systems exhibiting self-organised collective motion and spatial sorting are widespread across scales in nature [22], from flocking [5, 19] and separation with respect to social or physical characteristics [1, 11, 18] to territorial segregation [12, 16]. Of the existing models of collective movement, little attention has been given to the role of sociogenesis [23], the theory of how socio-spatial structures form as a result of agent interactions. In nature, however, there is a strong interplay between social dynamics, movement and space-use behaviour. Annular socio-spatial patterns have been widely observed in primate dominance hierarchies, where high ranking individuals occupy central locations in the group, while low ranking ones are found at the peripheries [11, 15].

While existing spatially explicit models of dominance hierarchy formation [7–9] generate correlations between social ranks and spatial centrality, they are restricted to agents that are reactive to social information at the microscopic scale. The work in [8] analysed the density-driven phase transition for the emergence of condensed clusters of agents, but did not study the mechanisms with which microscopic scale dynamics lead to cluster formation. Work in [7, 9] investigated how heterogeneity in agent repulsion generated by micro-scale collisions leads to spatial sorting. A common characteristic of these models is the imposition of periodic boundary conditions to maintain group cohesion. This is not surprising given that, in unbounded domains, cohesive collective random motion is known to require direct [5, 13, 21, 26] or effective [14] attractive interactions that share information at long range.

Here, we present a sociogenesis framework for self-organised cohesive collective motion in unbounded space. We posit that loss of cohesion occurs due to instabilities arising from agents who base their movement decisions on noisy motion-dependent information at the microscopic scale. As such, we model agents whose behaviour is determined by their belief state—a coarse-grained representation of the local environment. The belief enables agents to respond to socio-spatial information at the mesoscopic scale, which fluctuates at a slower time-scale than the microscopic states it encodes. Importantly, agent beliefs in our model represent spatial variations in internal variables that are not related to motion.

In view of our modelling approach, it is noted that while existing models of flocking [5, 19, 21] also leverage mesoscopic-level social interactions to achieve global collective patterns, internal representations have only made use of information corresponding to agent states that are position and motion-related. As a result, the functional form of the agent beliefs used in these models has been restricted to taking an average of positions and velocities of neighbouring agents. Models of spatial coordination in multi-agent systems and reinforcement learning have similarly focused on using internal representations of spatial information, computing Voronoi area partitions [4] and distributed path selection [3] based on neighbour positions that are directly sensed or propagated through message passing. Other approaches have focused on coordinating agent motion by optimising coarse-grained, position-related metrics over the agent communication network, such as the number of network connections with neighbours [25], or using shared neighbour information [24].

The model presented here offers a generalisation of the mesoscopic coarse-graining procedure by extending the functional form of agent beliefs beyond taking an average. This development is necessary for enabling agents to coordinate using dynamic internal variables that are not motion-related. Since coarse-graining via a simple average leads to a loss of spatial information, coordination of agents using a dynamic internal variable requires a belief which takes into account spatial variation. In this model, a spatially explicit regression model is used for coarse-graining. The form of this generalisation allows for further extension beyond regression to other statistical inference and machine learning approaches.

In fact, this generalisability is essential to the functionality of our model, since different functional forms of the belief generate different global socio-spatial configurations. Here, the beliefs are constrained to induce self-organisation into a desired global concave annular state. We consider a system in 1D space, and use the term radial to refer to the line segment extending from the central point to the outer bounds of a given 1D interval, meaning that the desired global state is radially sorted in the social variable.

In this section, we describe the model in terms of its key variables. Table 1 summarises the various symbols in the model with their definitions and parameter values. The system is made up of N randomly moving agents on a discrete, unbounded 1D lattice. Time, t, is discrete, and each agent, k, is described by its position, $x_k\in \mathbb{Z}$, and an internal variable describing its social rank, $S_k\geqslant 0$. Social rank dynamics are defined through pairwise repulsive interactions inspired by the Bonabeau-Theraulaz-Deneubourg model [2]. When two agents j and k are co-located, they interact with probability $P_{jk}(S_j,S_k)$. If an interaction occurs, the winner and loser are selected according to an outcome probability $Q_{jk}(S_j,S_k)$, where j wins with probability $Q_{jk}(S_j,S_k)$, and k with probability $Q_{kj}(S_k,S_j) = 1-Q_{jk}(S_j,S_k)$. The social ranks of the winner and loser are increased and decreased by $\delta^+$ and δ⁻, respectively. At the mesoscopic scale, these social dynamics produce a spatially explicit social field, $S(x, t)$, describing the expected value of S_k at position x and time t.

Table 1. Variable definitions and parameter values used in simulations of the model.

Variable	Name	Definition or value
N	Number of agents	100
ρ0	Initial density	0.05
xk	Position of agent k	–
Sk	Social rank of agent k	–
$\widehat{S}_k(x)$	Belief of agent k	–
$\Phi_k$	Model fidelity for belief of agent k	Equation (1)
$V_k(x_k;x^*_k,L)$	Potential acting on agent k	Equation (2)
$x^*_k$	Potential center of agent k	Equation (3)
L	Box potential radius	$5,10,15,\ldots, 120$
h	Sensory radius	$250, 500, 1000, 1500, \ldots, 8000$
r	Measurement probability	0.01
$P_{jk}(S_j,S_k)$	Probability agents j and k interact	$H_0(\Delta S_{\textrm {max}}-|S_j-S_k|)$
$Q_{jk}(S_j,S_k)$	Probability agent j wins an interaction with k	$H_{1/2}(S_j-S_k)$
$\Delta S_{\textrm {max}}$	Social interaction threshold	100
$\delta^+$	Winning social update	1
δ−	Losing social update	0
tc	Measurement waiting time	$3\times 10^6$

Our model makes several modifications to the original formulation in [2], to ensure that the generated hierarchies are stable. We define a bounded interaction probability, $P_{jk}(S_j,S_k) = H_0(\Delta S_{\textrm {max}}-|S_j-S_k|)$, where $H_0(S)$ is the Heaviside step function with ${H_0(0) = 0}$, so agents only interact if the difference in their social ranks is below the threshold, $|S_j-S_k|\lt\Delta S_{\textrm {max}}$. Without this threshold, higher density regions experience a faster growth of social ranks due to higher encounter rates, and the steepness of $S(x,t)$ may become unbounded. On the other hand, when $\Delta S_{\textrm {max}}$ is too small, the system does not have enough time to socially differentiate and attain the concave annular state. The hand-tuned value of $\Delta S_{\textrm {max}} = 100$ is used in all simulations. Furthermore, a deterministic outcome probability is used so that the higher rank agent always wins, ${Q_{jk}(S_j,S_k) = H_{1/2}(S_j-S_k)}$, where $H_{1/2}(S)$ is the Heaviside step function with ${H_{1/2}(0) = 1/2}$, so that a winner is selected at random when $S_j = S_k$. We set $\delta^+ = 1$ and $\delta^- = 0$, and there is no relaxation of social ranks towards zero in our model. Figure 1 shows a schematic of the model, demonstrating the belief computation and navigation procedures described below.

Zoom In Zoom Out Reset image size

Sensing and Belief Computation: A communication region with radius h is defined around each agent, k, within which the agent can sense the positions, x_j , and social ranks, S_j , of neighbours, j. At every time-step, each agent performs a sensing measurement over this region with probability r = 0.01. This makes agent sensing asynchronous and is computationally efficient. An agent computes its belief, $\widehat{S}_k(x)$, from sensed neighbour data using a weighted polynomial regression with functional form $\widehat{S}_k(x) = p(x) + \xi$ (supplementary material section II), estimating the coefficients of the polynomial p(x), where $\xi$ is a Gaussian white noise. Agents compute $\widehat{S}_k(x)$ as a second-order polynomial, ${\widehat{S}_k(x) = \beta_0 + \beta_1 x + \beta_2 x^2 + \xi}$, which captures turning points in $S(x,t)$. To destabilise minima and retain a single maximum, a first-order polynomial belief, ${\widehat{S}_k(x) = \beta_0 + \beta_1 x + \xi}$, is computed instead of a second-order belief whenever a minimum is measured, i.e. $\beta_2 \gt 0$. Each belief has an associated model fidelity, $\Phi_k\in (-\infty,1]$, that measures its accuracy, given by:

$$\begin{align} \Phi_k &= 1- \frac{\sum_{j=1}^n \left(S_j - \widehat{S}_k({x}_j)\right)^2}{\sum_{j=1}^n \left(S_j - \bar{S}\right)^2}, \end{align} \tag{ 1 }$$

where S_j are the social ranks of the n sensed neighbours of k, and $\bar{S} = \sum_i S_i/n$ is the average of the sensed social ranks. A value of $\Phi_k\rightarrow 1$ indicates a good fit, and $\Phi_k\rightarrow -\infty$ indicates a worse fit (supplementary material section II C).

Agent Navigation: Agents perform random walks on the lattice, subject to an individual potential, $V_k(x;x_k^*,L)$, here taken to be the box potential with radius L and discrete-valued center, $x^*_k\in \mathbb{Z}$,

$$\begin{equation} V_k(x;x^*_k,L) = \begin{cases} 0 & \text{if}~|x-x^*_k| < L, \\ \infty & \text{if}~|x-x^*_k|\geqslant L. \end{cases} \end{equation} \tag{ 2 }$$

The bounded potential is chosen so as to limit rare events of complete mixing that occur when agents drift into the sensory field of others beyond their nearest neighbours. This ensures a broader region of cohesion stability in the state-space.

Each agent, k, computes their potential center, $x_k^*$, by solving (supplementary material section III):

$$\begin{equation} x_k^*(t)={\textrm{argmin}}_{x} \left( |S_k(t) - \widehat{S}_k(x)| \right), \end{equation} \tag{ 3 }$$

so that $x_k^*$ is the location that $\widehat{S}_k(x)$ predicts an agent with social rank S_k should occupy. Each $x^*_k$ is kept discrete by rounding it to the nearest integer. Finally, if the data sensed by an agent is of insufficient quantity or quality for regression to be performed (supplementary material section II D), the belief is re-set to zero, $\widehat{S}_k(x) = 0$, and $x_k^*$ is not updated.

The mean nearest-neighbour distance is used as a measure of cohesion and dispersion stationarity. This is defined as [26]:

$$\begin{equation} \Delta(t) = \left\langle \frac{1}{N}\sum_{j=1}^{N} \min_{k\neq j}\bigg(\big|x_j(t)-x_k(t)\big|\bigg) \right\rangle, \end{equation} \tag{ 4 }$$

where $\langle \cdot \rangle$ is an ensemble average over different system realisations. The system is considered to be stationary when $\Delta(t)$ converges to a constant value. We also study the system cohesion in terms of the mean proportion of sensed neighbours, $n_s(t)\in[0,1]$, given by:

$$\begin{align} n_s(t) = \left\langle \frac{1}{N(N-1)}\sum_{j=1}^{N}\sum_{\substack{k=1,\\ k\neq j}}^{N} \unicode{x1D7D9}\bigg(\big|x_j(t)-x_k(t)\big|\leqslant h\bigg)\right\rangle, \end{align} \tag{ 5 }$$

were the indicator function, i.e. ${\unicode{x1D7D9}(A) = 1}$ when A is true and ${\unicode{x1D7D9}(A) = 0}$ otherwise, counts the number of sensed neighbours of each agent.

We introduce a global order parameter called the socio-spatial correlation (SSC) that measures how agent social ranks change radially away from the group center of mass. The SSC, $C(t) \in [-1,1]$, is given by:

$$\begin{equation} C(t) = \bigg \langle\mbox{Corr}\Big(\big|x_k(t)-\bar{x}(t)\big|,S_k(t)\Big)\bigg\rangle, \end{equation} \tag{ 6 }$$

where $x_k(t)$ and $S_k(t)$ are the agent positions and social ranks, and $\bar{x}(t) = \sum_j x_j(t)/N$ is the group center of mass. The Spearman rank correlation is used in $\mbox{Corr}(\cdot, \cdot)$, which captures non-linear correlations, and alternative measures do not appreciably change the SSC values obtained. A value of $C(t) = 0$ signifies no correlation, while the extreme values of $C(t) = \pm1$ are attained when social ranks are perfectly radially increasing or decreasing. Hence, $C(t) = -1$ signifies convergence to the concave annular state.

We quantify $S(x,t)$ macroscopically using an integrated sigmoid that we call the shape function,

$$\begin{equation} F(x; \alpha, m, K)= -\frac{2m}{\alpha}\ln\left({1+e^{-\alpha x}} \right) - m x + K. \end{equation} \tag{ 7 }$$

This is a concave function that interpolates between quadratic and absolute value functions, with ${\alpha, K, m \gt 0}$. While the scale of equation (7) depends mostly on K and m, its shape can be characterised by the parameter ${J = K\alpha/m - \ln(4)}$. For large J, ${F(x; \alpha, m, K)}$ approaches the absolute value function. When J ≈ 0, ${F(x; \alpha, m, K)}$ becomes a quadratic function (supplementary material section IV).

4.1. Control parameters

4.2. Transient dynamics

The system dynamics are investigated using Monte Carlo simulations (supplmentary material section I). At t = 0, agents are initialised with density $\rho_0 = N/A_0$ by randomly drawing agent positions from a uniform distribution of width A₀, $x_k(0) \sim U(-A_0/2,A_0/2)$. Initially, all agents have $S_k(0) = 0$, $x_k^*(0) = x_k(0)$ and $\widehat{S}_k(x) = 0$. Figure 2 shows the system convergence to a concave annular state in terms of the socio-spatial correlation. The inset shows the time evolution of a single simulation, where it can be seen that the system is initially disordered in x_k and S_k , and after some time converges to a concave annular state that continues to grow until all nearest-neighbour agents j and k have a difference of social ranks equal to $|S_j-S_k| = \Delta S_{\textrm {max}}$.

Zoom In Zoom Out Reset image size

The system convergence is explained by the presence of information cascades, which occur in multi-agent settings where actions of agents are influenced by socially acquired information [20]. When all agents are simultaneously adjusting their behaviour in response to that of their neighbours, a high correlation of information is generated between agent states. This information propagates through the agents in the system due to positive feedback effects as follows. Initially, agents measure a weak relationship in the x_j and S_j data of their neighbours, j, as represented by the belief, $\widehat{S}_k(x)$. The motion of an agent, k, becomes biased according to its belief when it updates its position, x_k , so that $\widehat{S}_k(x_k)\approx S_k$. In doing this, the agent, k, implicitly transfers information about its belief to any neighbours who observe its state, $(x_k,S_k)$. As belief information propagates between agents in the system, neighbours become increasingly more likely to compute the same belief states, ultimately leading to a form of local consensus.

Information cascades result in positive (accurate) or negative (inaccurate) consensus decisions. While convergence occurs as a result of positive information cascades in the system, we also observe negative information cascades that result from inaccurate belief estimates made by agents during early system dynamics [20], as signified by a negative model fidelity, $\Phi_k\lt0$ (supplementary material section II C). These early measurement errors may lead to configurations that have radially increasing edges, so that $S(x,t)$ converges to an 'N' or 'W' shape.

To address this, we introduce a two-stage dynamics that prevents the use of early, error-prone belief measurements. Our choice here is inspired by biological systems, where multiple time-scales in the formation and maintenance of social ranks have been observed [10]. The two stages are defined by a waiting time, t_c , such that for all $t \lt t_c$, measurements with an associated model fidelity, $\Phi_k \lt 0$, are not retained by agents. This requires agents to have globally synchronised internal clocks, however, the agents' choice of whether to use their computed belief is local and asynchronous, as this information comes from using the model fidelity, $\Phi_k$, which is locally evaluated.

After $t\gt t_c$, the use of beliefs with $\Phi_k\lt0$ becomes necessary for system convergence. Agents located at local minima of $S(x,t)$ tend to compute first-order polynomial beliefs with $\Phi_k\lt0$. In order to destabilise the minima and establish a global maximum characteristic of the concave annular configuration, the agents must make use of these measurements. This use of $\Phi_k\lt0$ measurements when $t\gt t_c$ does not lead to negative information cascades because, by this time, radially decreasing edges are established which are stable with respect to perturbations caused by erroneous belief measurements (supplementary material section V). In subsequent simulations, the hand-tuned value of $t_c = 3\times 10^6$ is used, to allow the system sufficient time to develop radially decreasing edges.

4.3. Long Time Dependence

With Monte Carlo simulations carried out up to $t = 10^9$, the system exhibits three distinct regimes in the $(k_L,k_h)$-state-space, shown in figure 3. While the Full and Partial Sensing regimes maintain cohesive distributions of agent positions, the Unstable regime results in a break-up of the agents (supplementary material section VI). As can be seen by the contours in figure 3, a sharp transition is observed between the Full and Partial Sensing regimes, followed by a more gradual transition between the Partial Sensing and Unstable regimes.

Zoom In Zoom Out Reset image size

In the Full Sensing regime, the system maintains a similar density to the initial density, ρ₀, with every agent able to sense all others. In the Partial Sensing regime, the system expands by several orders of magnitude beyond its initial density, before reaching a dynamically stable cohesive state. This expansion means that even when agents can initially sense all others in the system, at long times the mean proportion of sensed neighbours in equation (5) lies in the range ${n_s(t) \in [0.2, 0.4]}$. In the Unstable regime, the system instead exhibits an expansion that does not stop until the group has completely dispersed and the agent density falls below that required for measurements to take place (supplementary material section II D).

In figure 4(a), we plot the length of the agent occupation region defined by each box potential, $2L-1$ (the central site at $x_k^*$ is only counted once), against the estimated mean number of sensed neighbours, $2h/\Delta(t)$. The macroscopic shape parameter, J, and the microscopic mean nearest-neighbour distance, $\Delta(t)$, are properties of the system that are not externally imposed, but emerge as a result of the system dynamics following the choice of the microscopic parameters, h and L. The existence of voids in figure 4(a) indicates that only certain values of $2h/\Delta(t)$ can emerge for each selected box potential length and sensory radius. Namely, there is a jump in the mean number of sensed neighbours between the two cohesive regimes, with the data points around $2h/\Delta(t) = N-1\approx 10^2$ belonging to the transition cusp. Similarly, there are no points in the top right-hand region of panel (a), since no states were found in the Full Sensing regime beyond L > 45 for all tested values of h.

Zoom In Zoom Out Reset image size

The cluster of points to the right of $2h/\Delta(t) = 10^2$ corresponds to the Full Sensing regime. The emerging mean nearest-neighbour distances, $\Delta(t)$, lead to fully shared sensory information, so that all agents compute the same belief. Macroscopically, the system assumes a quadratic shape in $S(x,t)$, as measured by low values of the fitted shape parameter, J ≈ 0. The values of $\Delta(t)$ are independent of h in this regime, as shown in panel (b), where the clustering of $\Delta(t)$ only depends on $2L-1$.

In the Partial Sensing regime, the system self-selects values of $\Delta(t)$ that keep the mean number of sensed neighbours invariant under L and h. This is shown in panel (a), where data in the Partial Sensing regime is aligned vertically. Macroscopically, the configurations produced here are closer to absolute value functions, with sharper turning points at their center, as measured by higher J values. The emerging $\Delta(t)$ in this regime depend both on L and h, as seen in panel (c).

The incorporation of sociogenesis into models of collective motion using internal agent beliefs gives insight into how social structure can influence, and be influenced by, the motion decisions of individuals. The model presented achieves cohesive collective motion in unbounded space with sensory radii spanning $12.5\%$ of the initial group spread ($k_h = 0.125$). The success of this model suggests that biasing agent motion using internal variables prevents diffusion in unbounded space, an important problem to solve for future real-world deployment of multi-agent and swarm robotic systems [6, 17]. The approach of modelling intelligent agents that use statistical inference methods to locally estimate and adaptively respond to mesoscopic system states opens up avenues for understanding agents who base their decisions on incomplete system information.

This work was carried out using the computational facilities of the Advanced Computing Research Centre, University of Bristol. We acknowledge funding of an Amazon Research Award to L G. L G also acknowledges funding from BBSRC Grant No. BB/T012196/1 and NERC Grant No. NE/W00545X/1.

The data cannot be made publicly available upon publication because the cost of preparing, depositing and hosting the data would be prohibitive within the terms of this research project. The data that support the findings of this study are available upon reasonable request from the authors.