# Information socialtaxis and efficient collective behavior emerging in groups of information-seeking agents

Edited by Curtis G. Callan Jr., Princeton University, Princeton, NJ, and approved April 17, 2017 (received for review October 31, 2016)

## Significance

From bacteria to humans, individual foraging has been a key example of complex behavior, often analyzed experimentally and theoretically, in terms of a trade-off between exploration and exploitation. Finding a source in a nonturbulent environment can be done by following the gradient of a signal, but in noisy environments, moving to maximize information about the source results in efficient searches. We present a model for group foraging, in which each agent aims to maximize its own information and minimize its informational overlap with others. The result is a highly efficient, robust, biologically plausible, and nearly optimal collective group behavior. This suggests information maximization from sensory and social sources as an optimization principle that can direct individual and group behavior.

## Abstract

Individual behavior, in biology, economics, and computer science, is often described in terms of balancing exploration and exploitation. Foraging has been a canonical setting for studying reward seeking and information gathering, from bacteria to humans, mostly focusing on individual behavior. Inspired by the gradient-climbing nature of chemotaxis, the infotaxis algorithm showed that locally maximizing the expected information gain leads to efficient and ethological individual foraging. In nature, as well as in theoretical settings, conspecifics can be a valuable source of information about the environment. Whereas the nature and role of interactions between animals have been studied extensively, the design principles of information processing in such groups are mostly unknown. We present an algorithm for group foraging, which we term “socialtaxis,” that unifies infotaxis and social interactions, where each individual in the group simultaneously maximizes its own sensory information and a social information term. Surprisingly, we show that when individuals aim to increase their information diversity, efficient collective behavior emerges in groups of opportunistic agents, which is comparable to the optimal group behavior. Importantly, we show the high efficiency of biologically plausible socialtaxis settings, where agents share little or no information and rely on simple computations to infer information from the behavior of their conspecifics. Moreover, socialtaxis does not require parameter tuning and is highly robust to sensory and behavioral noise. We use socialtaxis to predict distinct optimal couplings in groups of selfish vs. altruistic agents, reflecting how it can be naturally extended to study social dynamics and collective computation in general settings.

### Sign up for PNAS alerts.

Get alerts for new articles, or get an alert when an article is cited.

Foraging is fundamental for survival and reproduction in numerous species and is often based on sparse and noisy sensory cues in complex environments. Understanding how organisms represent space and navigate and the utility functions and computations that underlie movement patterns and social behavior (1–6) critically depends on characterizing the nature of foraging. Theoretical models of foraging have been pivotal in economics, physics (7, 8), and machine learning (9) as a general framework for decision making, exploration and exploitation, optimization, and learning (10).

Climbing the gradient of a sensory signal is an efficient foraging strategy for finding a strong source in nonturbulent environments or on a microscopic scale, as demonstrated, for example, by theoretical and experimental studies of bacterial chemotaxis (1, 11). However, for weak sources, or on a macroscopic scale that is characterized by turbulent flows, the signal coming from a source is typically broken into random, sparse, and disconnected patches (12). Without a continuous gradient, a different strategy is needed to read and use information from these patches about the location of the source (13). Vergassola et al. (14) presented a foraging algorithm based on maximizing the information that an agent has about the location of a source and showed that it is highly efficient in finding a sparsely signaling source in a turbulent environment. These infotaxis search trajectories resemble the paths of foraging insects, suggesting a biological implication of this model.

In nature, many species, including bacteria (15), amoebae (16), insects (17, 18), fish (19), birds (3), and mammals (20, 21), display complex group behavior, including foraging. The mechanisms that underlie group behavior have been of great experimental and theoretical interest, focusing on the computation that each individual performs (22–24) and emergent collective behavior (24, 25). In terms of social behavior, such models have been used to describe exploration and exploitation of the environment, finding food or mates, decision making (26–29), and altruistic and opportunistic behavior, as well as the design of systems of conflicting components (30) and distributed algorithms (31).

We present a model of foraging in a group that combines infotaxis and social interactions, using information as a unifying principle. In this socialtaxis model, agents seek a signal-emitting source, using the information they receive through their own “senses” and information they receive from other agents or that they infer from the behavior of their conspecifics. We show that certain forms of socialtaxis allow a collection of opportunistic individuals to find the source considerably faster than a collection of independent agents and comparable to the case of agents sharing all their sensory information and decision making using a centrally managed strategy (which is exponentially more expensive). Moreover, we find that coordinated group behavior emerges in a collection of selfish individuals each maximizing their own goal. We further present biologically plausible versions of socialtaxis, in which agents share little or no information, and its robustness to various forms of noise. Finally, we show socialtactic optimal behaviors in game theory-like settings of competing and opportunistic agents, suggesting a wide range of applications for this model.

## From Individual Infotaxis to Socialtaxis

The infotaxis algorithm (14) describes a strategy for individual foraging in space, where an agent (or animal) moves to maximize the information it has about the location of a stationary source that emits signals (or particles) in random directions at a low rate. In its discretized version, the search space is divided into “cells,” and the agent estimates at each time $t$ a probability map of the possible locations (

**r**) of the source ${P}_{t}(\text{\mathbf{r}})$. The entropy of the map at time $t$, given by $S\left[{P}_{t}(\text{\mathbf{r}})\right]=-{\mathrm{\Sigma}}_{\text{\mathbf{r}}}{P}_{t}(\text{\mathbf{r}}){\mathrm{log}}_{2}{P}_{t}(\text{\mathbf{r}})$ (32), measures the uncertainty or missing information about the location of the source, in bits. At each time point, the agent may (*i*) find the source, (*ii*) detect a signal from the source (“hit”), or (*iii*) detect nothing. The agent then updates its probability map over the space based on one of these three events and uses the new map to decide whether to move to a neighboring cell or stay still. This decision is based on the expected information it would gain from each possible move, which is given by the expected change in entropy of each of the possible events in that location (finding the source, getting a hit, or not getting a hit), weighted by the probability of occurrence of each event (*Materials and Methods*). Fig. 1*A*shows the trajectories of two agents who are independently searching the source using infotaxis in a 2D arena, completely ignoring one another (Movie S1). The paths of these independent agents are typical of individual infotaxis searches (14), resembling trajectories of insects in nature.Fig. 1.

If there are other agents (animals) around, then in addition to its own sensory information about the source, each agent may use information it receives from conspecifics or infers from their behavior. We therefore extended the infotaxis algorithm to consider the behavior of groups of agents. Here, each agent moved to minimize a combination of its own entropy (as in infotaxis) and some function of its relation to other agents. Thus, rather than minimizing entropy, each agent minimized a “free energy,” given bywhere $S[{P}_{i}]$ is the entropy of the probability map ${P}_{i}$ of agent $i$, as in the single-agent infotaxis above, ${G}_{i}$ is a social interaction term between agent $i$ and the rest of the group, and $\beta $ weighs the balance between the individual’s information and its coupling to others. The nature of this socialtaxis model is determined by ${G}_{i}$, or how individuals affect one another, and $\beta $, the coupling strength or inverse “temperature,” which balances individual information and social interactions: $\beta =0$ reduces socialtaxis to the standard individual infotaxis behavior of each agent, and $\beta \to \mathrm{\infty}$ implies pure socially driven behavior.

$${F}_{i}=S[{P}_{i}]+\beta {G}_{i}(\text{group}),$$

[1]

Following many models of collective behavior, a natural choice for the relation between individuals would be one that is determined by the physical distance between them. We consider here the case where the free energy of agent $i$ is given bywhere ${d}_{ij}$ is the Euclidean distance between agents $i$ and $j$, $\alpha >1$ is a tunable parameter that determines the scaling of the distance between agents, and the summation goes over all group members. We explored the behavior of groups of 2–20 agents searching for a single sparse source in a 2D arena and found that for each choice of $\alpha $, there was an optimal $\beta $ that was always positive and minimized the time needed for the first member of the group to find the source (

$${F}_{i}^{dist}=S[{P}_{i}]+\beta {\mathrm{\Sigma}}_{j}{d}_{ij}^{\alpha},$$

[2]

*Distance-Based Socialtaxis*). However, even for the optimal values, the improvement in search time compared with independent agents was very small (more below). Fig. 1*B*shows an example of the cohesive trajectories of two coupled agents with their optimal ${\beta}_{opt}$ (Movie S1).We then considered a socialtaxis model in which social interactions were based on the information that agents have and not their physical locations. Here each agent aims to minimize the combination of its entropy and the overlap in the information it has in common with the other agents,where ${P}_{i}$ and ${P}_{j}$ are the probability maps of agents $i$ and $j$, and ${D}_{KL}$ is the Kullback–Leibler divergence (32) between probability maps, which measures in bits the dissimilarity between the distributions. For positive $\beta $ this social term would drive agents to make their probability maps different from one another (constrained by the individual infotaxis term), whereas for negative $\beta $ the social term would drive agents to merge their knowledge and make their individual maps more similar. Fig. 1

$${F}_{i}^{info}=S[{P}_{i}]-\beta {\mathrm{\Sigma}}_{j}{D}_{KL}[{P}_{i}||{P}_{j}],$$

[3]

*C*shows the trajectories of two agents under this model with strong coupling $\beta =10$, reflecting their seemingly diverging yet highly time-efficient paths toward the source (Movie S1). The agents’ trajectories are qualitatively different from the independent or distance-based algorithm and are similar to the trajectories of fully cooperating agents who use a joint probability map based on their joint hits, and individual movements are determined by a joint infotaxis strategy (Fig. 1*D*, Movie S1, and*Materials and Methods*).We simulated the different socialtaxis models, under different parameter values, each with 3,000 randomly chosen initial configurations of the agents and the location of the source (to avoid any effects of specific choice of configuration, see also ref. 33). As the example trajectories in Fig. 1 reflect, the distance-based socialtaxis enabled the agents to find the source a little faster than in the case of independent agents, but they were much slower than the fully cooperating agents (Fig. 2

*A*), even with an optimal choice of ${\beta}_{opt}$, which we had to find numerically. A spring-like interaction between agents that drove them toward a nonzero distance gave qualitatively similar results, whereas negative $\beta $ values, typically resulted in failure to find the source at all.Fig. 2.

In clear contrast, the information-based socialtaxis showed a clear and abrupt decrease in search time compared with that of independent agents (Fig. 2

*A*). Importantly, the performance of agents improved monotonically as $\beta $ increased, and with large $\beta $ this model was on par with the case of fully cooperating agents. This optimal behavior did not require any tuning of model parameters, which we show analytically (*Analytical Analysis of the Functional Dependence of the Search Times on Coupling Strength*). Notably, negative $\beta $ values, which intuitively might seem to enable agents to average their information and filter noise, resulted in failure to find the source in almost all cases (compare Movie S2 for $\beta >0$ and Movie S3 for $\beta <0$).The nature of trajectories of the agents in the information-based socialtaxis delineates its efficiency: Because of the social information term, agents “repel” each other early on, more strongly as $\beta $ is increased (Fig. 2

*B*), which leads to an effective division of the search space. Later in the search, the social interaction is constrained by the individual knowledge, which results in faster and more accurate convergence toward the source. Accordingly, information coupling between agents reduced the characteristic long “overshoots” in the initial part of the trajectories seen in standard infotaxis that take them away from the source ($t\in [70,100]$ in Fig. 2*C*). This is further reflected by comparing the individual locations along the path, where infotactic and socialtactic agents would move in different directions (Fig. 2*D*). Notably, information-based socialtaxis is robust to different kinds of variations, such as the starting distances from source, the size and shape of the arena, strength of the source, and decay length of the signal from the source (*Socialtaxis Is Robust to a Multitude of Environments and Wrong Modeling of the Environment*and Fig. S1), as well as different forms of sensory, odometry, or computational noise (Figs. S2 and S3). It was also highly efficient in reducing search times in a 3D space compared with the case of independent agents (Fig. S1*E*).Fig. S1.

Fig. S2.

Fig. S3.

## Distance-Based Socialtaxis

Extending the analysis of the distance-based socialtaxis introduced in Eq.

**2**of the main text, we present in Fig. S2 the mean search time vs. $\beta $ for different values of $\alpha =2,8,16$ and different group sizes $N=2,5,10,20$. For all values of $\alpha $ and all group sizes explored, search time had a minimum value we denoted as ${\beta}_{opt}$, which was evaluated numerically over a large range of values. For weaker couplings, namely $\beta <<{\beta}_{opt}$, agents’ performance was similar to the case of independent agents, whereas for strong coupling, $\beta >>{\beta}_{opt}$, the social term dominated, driving the agents toward each other rather than toward the source.We note that the optimal value ${\beta}_{opt}$ should occur when the contributions from the two terms in Eq. where $\mathrm{\Delta}$ refers to the differences between the possible directions the agent can move (for simplicity we consider the case of two agents). The difference in the social term from agent $i$ moving toward $j$ or away from it is given bywhere we used the binomial theorem and kept only the leading term. Substituting Eq. where we used $\mathrm{\Delta}S={10}^{-3}$ as a typical value for the difference in the reduction in entropy between possible movement directions. Substituting ${d}_{ij}=\lambda =50$ (37), we can find an approximate analytic value for ${\beta}_{opt}^{a}$ and compare it to the value found numerically, ${\beta}_{opt}^{numeric}$. Fig. S2

**1**are of the same order of magnitude, or when$$\mathrm{\Delta}S\approx \beta \mathrm{\Delta}G,$$

[S1]

$$\mathrm{\Delta}G={({d}_{ij}+1)}^{\alpha}-{({d}_{ij}-1)}^{\alpha}\approx 2\alpha {d}_{ij}^{\alpha -1},$$

[S2]

**S2**into Eq.**S1**, and solving for $\beta $, we get an analytic approximation for the optimal value of ${\beta}_{opt}^{a}(\alpha )$,$${\beta}_{opt}^{a}(\alpha )\approx \frac{\mathrm{\Delta}S}{2\alpha {d}_{ij}^{\alpha -1}}\approx \frac{{10}^{-3}}{2\alpha {d}_{ij}^{\alpha -1}},$$

[S3]

*D*shows this method provides a reasonable estimate and can serve as a good value to initialize a numeric search.## Analytical Analysis of the Functional Dependence of the Search Times on Coupling Strength

To further understand the behavior of information socialtaxis we can rewrite the free-energy Eq. The first term inside the brackets in Eq.

**3**,$${F}_{i}={S}_{i}-\beta {\mathrm{\Sigma}}_{j}{D}_{kl}[{p}_{i}||{p}_{j}]$$

[S4a]

$$=-{\mathrm{\Sigma}}_{\text{\mathbf{r}}}{p}_{i}(\text{\mathbf{r}}){\mathrm{log}}_{2}{p}_{i}(\text{\mathbf{r}})-\beta {\mathrm{\Sigma}}_{j}{\mathrm{\Sigma}}_{\text{\mathbf{r}}}{p}_{i}(\text{\mathbf{r}}){\mathrm{log}}_{2}\frac{{p}_{i}(\text{\mathbf{r}})}{{p}_{j}(\text{\mathbf{r}})}$$

[S4b]

$$=-(\beta +1)[{\mathrm{\Sigma}}_{j}{\mathrm{\Sigma}}_{\text{\mathbf{r}}}{p}_{i}(\text{\mathbf{r}}){\mathrm{log}}_{2}\left(\frac{{p}_{i}(\text{\mathbf{r}})}{{p}_{j}(\text{\mathbf{r}})}\right)+\frac{1}{\beta +1}{\mathrm{\Sigma}}_{j}{\mathrm{\Sigma}}_{\text{\mathbf{r}}}{p}_{i}(\text{\mathbf{r}}){\mathrm{log}}_{2}{p}_{j}(\text{\mathbf{r}})]$$

[S4c]

$$=(\beta +1)[-{\mathrm{\Sigma}}_{\text{\mathbf{r}}}{p}_{i}(\text{\mathbf{r}}){\mathrm{log}}_{2}{p}_{i}(\text{\mathbf{r}})+\frac{\beta}{\beta +1}{\mathrm{\Sigma}}_{j}{\mathrm{\Sigma}}_{\text{\mathbf{r}}}{p}_{i}(\text{\mathbf{r}}){\mathrm{log}}_{2}{p}_{j}(\text{\mathbf{r}})].$$

[S4d]

**S4c**is the Kullback–Leibler divergence (32) between ${p}_{i}$ and ${p}_{j}$, which obtains its minimal value when the two distributions are identical. The second term, or cross-entropy, obtains its maximal value when ${p}_{i}={p}_{j}$. Thus, we can interpret Eq.**S4c**as a combination of a term driving the distributions to be different and another term, which we can view as a constraint, driving the distributions to be more similar. The weight of the constraint decreases monotonically with $\beta $, which explains why the search time has a monotonic dependence on $\beta $. Eq.**S4d**shows that choosing a social term $G\equiv -{D}_{kl}[{p}_{i}||{p}_{j}]$ with coupling strength $\beta $ is equivalent to choosing $G\equiv \mathrm{\Sigma}{p}_{i}{\mathrm{log}}_{2}{p}_{j}$ with a weight factor $\widehat{\beta}\equiv \frac{\beta}{\beta +1}$, which is bounded between 0 when $\beta =0$ and 1 when $\beta \to \mathrm{\infty}$, implying that the behavior of the agents should converge asymptotically as $\beta \to \mathrm{\infty}$. We point out that this result does not necessarily mean that the search time should decrease, but that it should converge asymptotically toward some value.## Socialtaxis Is Robust to a Multitude of Environments and Wrong Modeling of the Environment

In the main text, the analysis of the socialtaxis algorithm was shown for a source strength $R=1$, emitting one particle per time step, with correlation length of $\lambda =50$, as in ref. 14 (

*Materials and Methods*). Here we present the analysis of the robustness of the socialtaxis model following ref. 37 where we manipulated source strength, the layout of the arena, signal transport, particles’ lifetime, and more, for the case of two socialtaxis agents with a strong coupling of $\beta =10$. We found that the mean search time for socialtaxis agents is more efficient than that for independent infotaxis agents, except for very low emission rates (Fig. S1*A*). Socialtaxis was also much more efficient than independent infotaxis for a wide range of correlation lengths (Fig. S1*B*).Rodriguez et al. (33) demonstrated the considerable effect of the geometry of the arena on the search times in infotaxis. To avoid a bias resulting from an arbitrary choice of initial configurations the values presented in Figs. 2

*A*and 4 in the main text were the search times for randomly chosen initial configurations, but the size of the arena was fixed to a square arena of side length $L=64$. Testing socialtaxis and infotaxis under different arena sizes and in rectangular arenas showed clearly the superiority of socialtaxis (Fig. S1*C*). In all of these cases, we assumed that the agents had a correct estimate (or prior) for the strength of the source. We found that both infotaxis and socialtaxis demonstrated a sharp increase in search times as the difference between the agents’ model of $R$ and the real emission rates increased, and socialtaxis agents (who found the source for any value of ${R}_{model}$ tested) were more efficient than infotaxis agents except for very low model emission rates (Fig. S1*D*). Similarly, if the agents had a wrong prior for the correlation length of the source, then for most values of ${\lambda}_{model}$, socialtaxis agents were more efficient in finding the source, where ${\lambda}_{real}=50$ (Fig. S1*E*). In Fig. S1*F*we plot the mean search time vs. $\beta $ in a 3D search arena (36) and the qualitative behavior is similar to the case of 2D. Here, the side length of a the cubed arena is $L=32$, and $\lambda =20$. We note, however, that the search times of socialtaxis do not reach the values obtained by fully cooperating agents in this case. We conclude that socialtaxis works efficiently in a wide range of conditions (compare ref. 37) and is more efficient than infotaxis in almost all cases.## Emergent Group Behavior of Opportunistic Socialtaxis Agents Maximizing Their Information Gain

An emerging spatial collective behavior in the information-based socialtaxis becomes apparent when we study the trajectories of agents in larger groups (Fig. 3

*A*and Movie S4). For a given group size $N$, increasing the weight of the social term $\beta $ resulted in a faster finding of the source (Fig. 3*B*). For a given $\beta $ value, the dependency on group size showed monotonic improvement in search time, hinting at the possibility of a power-law scaling (Fig. 3*B*,*Inset*). Again, large groups of agents that relied on distance-based socialtaxis showed only a small improvement in search times compared with those of independent agents, even in the best case ($N\approx 15$), and required fine tuning of model parameters (Fig. S4).Fig. 3.

Fig. S4.

The socialtactic agents gain information about the source at a rate that is similar to that of independent agents in the initial parts of their search, but the social interactions boost the rate of information gain significantly later on (Fig. 3

*C*). Consequently, when the first agent finds the source, all other agents have also gathered much more information. The information socialtaxis keeps agents consistently less clustered spatially than independent agents (Fig. 3*D*), yet when the first agent finds the source (faster), they are all much closer to it than in the case of independent agents (Fig. 3*E*). Thus, whereas there is no obvious residual*N*dependence of information sharing in terms of time to source of the first agent, there is clear benefit for the rest of the group: Even if the other agents did not know that the first agent had found the source, they would still find it faster as the coupling becomes stronger (Fig. S5 and*Socialtaxis Is Efficient for the Group, Beyond the First “Finder”*). Consequently, the group demonstrates a spatial “social structure” and coherent movements, despite the lack of an explicit spatial term in the model.Fig. S5.

## Information Socialtaxis Is Efficient for the Group, Beyond the First “Finder”

Whereas information socialtaxis is efficient for the group in terms of the time it takes the first agent to find the source, we then asked how it affects the rest of the agents. We recall that Fig. 3

*E*showed that the other agents are closer to the source once the first agent has found it, compared with noninteracting groups. However, this does not necessarily mean they have more useful information at that point. We therefore simulated pairs of agents performing information socialtaxis, but when the first agent found the source, we made that agent “disappear,” and the other agent continued its search using the standard infotaxis search. Fig. S5*A*shows the second agent is also more efficient in finding the source when it used the social term in the beginning of the search, supporting the conclusion implied from Fig. 3*E*. Fig. S5*B*indicates that information socialtaxis is even more efficient for the group, showing the residual search time for the group, namely the time it took the second agent to find the source after it was found by the first agent, was also shorter for socialtactic groups.## Biologically Plausible Socialtaxis and Optimal Behavior of Selfish, Opportunistic, or Altruistic Agents

How relevant is socialtaxis for real animal groups? First, we considered a more biologically realistic case, where each individual may be coupled differently to its conspecifics—as these couplings may be innate or learned from experience. Focusing on pairs of agents, we find that for a given coupling value of agent 2 to agent 1, ${\beta}_{2\to 1}$, the mean time to find the source decreased monotonically as a function of the reciprocal coupling ${\beta}_{1\to 2}$ (Fig. 4

*A*). Thus, even when each agent can have an individually chosen coupling to the others, strong couplings are beneficial for the group as a whole. However, the optimal coupling value that would benefit an individual’s chances of finding the source are different from what would be good for the group: For a given value of ${\beta}_{2\to 1}$ the optimal ${\beta}_{1\to 2}$ that would raise the probability for agent $1$ to find the source first has a peak at ${\beta}_{1\to 2}\approx 0.5$, regardless of the value of ${\beta}_{2\to 1}$ (Fig. 4*B*). Thus, optimizing group success or individual success requires very different coupling values. Still, even the most opportunistic choice of coupling values was more efficient for the group than the case of independent agents and would benefit the group.Fig. 4.

The critical question of relevance of the socialtaxis model to real animals is the feasibility of information sharing between agents (34). Surprisingly, we found that even a very limited form of information sharing gives a highly efficient socialtaxis: If instead of sharing their full probability map at each time point (which is obviously biologically unrealistic), agents shared only the location of the peak of a Gaussian that approximates their current probability map, the search time of the group was comparable or even better than the case where the whole map was shared (Fig. 4

*C*). Interestingly, the difference between the sharing of just the peak and that of their full maps was most apparent for weak coupling between agents; for strong couplings the different models showed stable asymptotic behavior (Fig. S6 and*Exploring the Peak Inference Algorithm*).Fig. S6.

Whereas this limited-bandwidth information sharing could be relevant for animals that actively communicate with one another, we further asked whether socialtaxis could work without any form of communication between individuals. We found that even if agents did not share any information, but instead tried to infer information about the source from their conspecifics based only on observing their behavior, they were able to perform a highly beneficial socialtaxis. Here, each of the agents used a simple generalized linear model (GLM) that estimated the peak position of the map of the other agent, based on its trajectory, which led to a substantial decrease in search time. This GLM-based inference model was less efficient than the information-sharing socialtaxis, but was still able to get the agents to find the source in $84\%$ of the time needed by independent agents. We emphasize that this model is only a lower bound on how well inference-based socialtaxis can work, and therefore conclude that such an approach can be highly efficient with low computational cost for individual agents and is biologically feasible, in terms of memory and computational simplicity.

## Exploring the Peak Inference Algorithm

The most biologically plausible version of socialtaxis is probably the one displayed in Fig. 4

*C*, where agents do not communicate at all, but infer the position of the peak of their conspecifics based on their trajectories. The inference is described in*Materials and Methods*. In brief, the agents estimate the location of the peak from the other agent’s trajectory, using a GLM, with the agent’s position as the features of the model. The inference, and the use of the social term, is done only in the interval $t\in [50,150]$, and the estimated peak position is updated every five steps. To better understand the nature of the algorithm we plot in Fig. S6*A*the mean search time vs. the strength of coupling for the same search schemes as in Fig. 4*C*, now presenting the behavior at strong couplings.In Fig. S6

*B*we present the accuracy of the peak estimation at the optimal coupling ($\beta =0.15$) and for strongly coupled agents ($\beta =30$). The error in estimating the location of the other agent’s peak is very similar for both coupling strengths. This suggests that the increase in search times as $\beta $ is increased is not a result of a less accurate peak estimation, but of giving too strong a weight to an inaccurate peak position.## Discussion

We have introduced a model and algorithm for group foraging in complex environments where each agent aims to maximize the information from its own sensory perception and minimize the overlap in information it has with group members. Increasing the information diversity between members made the group highly efficient, similar to fully cooperating, optimally managed agents, in clear contrast to the small improvement achieved by models of group behavior that rely on the physical distance between individuals. Importantly, information socialtaxis did not require parameter tuning and was efficient under various variations of the model and robust to a multitude of noise sources. Most interestingly, biologically plausible versions of the model, based on limited or no information sharing, proved to be similar to or even better than the full model, making it a compelling framework for considering behavior of real animals.

Modeling individual behavior in a group, as an optimization problem combining self-information and group information, unifies the ideas of gradient-based search using sensory signals; social interactions; and game theory notions of opportunism, individualism, and group benefits. The success of our model challenges the commonly used models of group behavior based on distance or explicit spatial organization—suggesting information as key sufficient substance of sensory processing and collective behavior. In addition to being a biologically plausible, robust, and efficient model of group behavior in a variety of settings, socialtaxis suggests a potential design for new algorithms for distributed searching and learning.

Our framework also naturally exemplifies the benefits of diversity in groups and the qualitatively different collective behaviors that may arise from individual traits. Whereas these ideas have obvious parallels in game theory and behavioral economics, we note the relation of information-based socialtaxis to the studies of decorrelation and redundancy reduction as an optimization principle in neural coding (35). We thus suggest that information socialtaxis can be readily extended to explore animal groups; artificial agents; or other systems in which group relations can be learned or dynamically modulated; and groups in which individuals have different innate behaviors, preferences, or motivations.

## Materials and Methods

### Model of the Environment.

A single source at an unknown location ${\text{\mathbf{r}}}_{0}$ in a finite environment is emitting particles with finite lifetime ${\tau}_{p}$ at a rate of $R$ particles per second in random directions, advected by a mean wind $V$ and diffusing Brownianly, with diffusivity $D$; for other conditions, see where ${K}_{0}$ is the monotonically decreasing modified Bessel function of the second kind of order zero, and $\lambda $ is the correlation length of the source. Here we focus on the case with no wind $(V=0)$, which has been shown to be the most difficult one (14, 36).

*Effect of Noise on Independent and Social Agents*. The average concentration field at position**r**is a solution of the advection–diffusion equation, which for a constant diffusion coefficient $\nabla \cdot D=0$ and incompressible flow $\nabla \cdot \overrightarrow{v}=0$ gives (with advection flowing in the negative $y$ direction) in the two-dimensional case a hit rate of$${R}_{hits}(\text{\mathbf{r}}|{\text{\mathbf{r}}}_{0})=\frac{R}{ln\left(\frac{\lambda}{a}\right)}exp[-\frac{(y-{y}_{0})V}{2D}]{K}_{0}\left(\frac{|\text{\mathbf{r}}-{\text{\mathbf{r}}}_{0}|}{\lambda}\right),$$

[4]

### Infotaxis.

The infotaxis algorithm is described in the main text and in detail in ref. 14. Briefly, an agent searching for the source decides on its move at time $t$ based on the expected change in entropy of the probability distribution over the locations of the source, ${p}_{t}(\text{\mathbf{r}})$ from each of the possible moves from its location $\text{\mathbf{r}}(t)$. This is given by weighting the change of entropy from finding the source, getting a hit or “no hit” by their relative probabilitieswhere the first term on the right-hand side is the weighted value of the vanishing entropy from finding the source when moving to $\text{\mathbf{r}}\prime $ (“exploitation term”); and the second term is the sum of change in entropy from a hit and a no hit in that location weighted by their probabilities, where ${\rho}_{k}(\text{\mathbf{r}}\prime )$ is the probability to get $k$ hits at $\text{\mathbf{r}}\prime $. As in ref. 14, we neglect the case of $k>1$ due to sparseness of the source.

$$\u27e8\mathrm{\Delta}S(\text{\mathbf{r}}(t)\to \text{\mathbf{r}}\prime )\u27e9={p}_{t}(\text{\mathbf{r}}\prime )[-S]+(1-{p}_{t}(\text{\mathbf{r}}\prime ))[{\rho}_{0}(\text{\mathbf{r}}\prime )\mathrm{\Delta}{S}_{0}+{\rho}_{1}(\text{\mathbf{r}}\prime )\mathrm{\Delta}{S}_{1}],$$

[5]

### Estimating and Updating the Probability Map of an Agent.

At each time point, an agent estimates the expected number of hits at position where $h=1(0)$ stands for the agent obtaining (not obtaining) a hit during this $dt$ time step, $Z$ is a normalization factor of the posterior probability, and the probability in visited sites is set to zero.

**r**by $h(\text{\mathbf{r}})\equiv \mathrm{\Delta}t\int {p}_{t}({\text{\mathbf{r}}}_{0})R(\text{\mathbf{r}}|{\text{\mathbf{r}}}_{0})d{\text{\mathbf{r}}}_{0}$. Assuming independent hits the probability to obtain $k$ hits is given by a Poisson distribution, and then using the posterior map of a hit trace, the updated map is given by$${p}_{t+1}({\text{\mathbf{r}}}_{0})=\frac{1}{Z}{p}_{t}({\text{\mathbf{r}}}_{0})\{\begin{array}{cc}\hfill {e}^{-R(\text{\mathbf{r}}(t)|{\text{\mathbf{r}}}_{0}),}& \text{if}\hspace{0.17em}k=0\hfill \\ \hfill {e}^{-R(\text{\mathbf{r}}(t)|{\text{\mathbf{r}}}_{0})}R(\text{\mathbf{r}}(t)|{\text{\mathbf{r}}}_{0}),& \text{if}\hspace{0.17em}k=1\hfill \end{array},$$

[6]

### Model of Fully Cooperating Groups.

Following Masson et al. (37), we consider the case of fully cooperating groups where agents shared a single probability map, updated at each step based on the hits/no hits of all agents,where $N$ denotes the number of agents in the group, ${\text{\mathbf{r}}}_{i}$ denotes the position of agent $i$, ${h}_{i}=1(0)$ corresponds to agent $i$ obtaining (not obtaining) a hit during this time step, $Z$ is the normalization factor, and the superscript $sh$ indicates this map is shared by all agents. The decision on where to move is also coordinated as the agents evaluate all of the possible joint moves of the group. We note that the number of possible actions the group can take on a 2D square lattice is ${5}^{N}$, which limits the size of the group that could use this algorithm due to the exponential growth in computational cost.

$${p}_{t+1}^{sh}(\text{\mathbf{r}})=\frac{1}{Z}{p}_{t}^{sh}(\text{\mathbf{r}})\cdot {\mathrm{\Pi}}_{i=1}^{N}\{\begin{array}{cc}\hfill {e}^{-R({\text{\mathbf{r}}}_{i}(t)|{\text{\mathbf{r}}}_{0}),}& \text{if}\hspace{0.17em}{k}_{i}=0\hfill \\ \hfill {e}^{-R({\text{\mathbf{r}}}_{i}(t)|{\text{\mathbf{r}}}_{0})}R({\text{\mathbf{r}}}_{i}(t)|{\text{\mathbf{r}}}_{0}),& \hfill \text{if}\hspace{0.17em}{k}_{i}=1\end{array},$$

[7]

### Spatial Organization of Groups of Agents.

Analyzing behavior of large groups, “in cluster” and “isolated” agents were defined according to the number of conspecifics ${n}_{nbr}$ inside the neighborhood of an agent, which was defined as a circle of radius $d$ around it. In cluster was defined as ${n}_{nbr}\ge {n}_{cluster}$ and ${n}_{nbr}\le {n}_{isolated}$ was defined as isolated. Here we used $d=10$, ${n}_{cluster}=10$, and ${n}_{isolated}=3$, but different choices of parameters $d$, ${n}_{cluster}$, and ${n}_{isolated}$ gave qualitatively similar results.

### Inference Model of Another Agent’s Probability Map Based on Its Trajectory.

Two inference models of the map of other agents were used to explore socialtaxis without sharing of information between agents. In the full-map inference model, agent $i$ iteratively used its current model of the map of agent $j$, ${\widehat{P}}_{i}^{j}(t)$, to assess the likelihood that the recent move of $j$ was the result of a hit, and from the inferred hits, it estimated the probability map of the other agent (in the common case where both events would result in the same movement we assumed that $i$ assigned a hit to $j$ with a probability based on the map that $i$ had at that time). Trying to infer hits using longer memory of past behavior of the other agents gave a small improvement of performance, but at an exponential computational cost. In the peak inference case, each agent tried to infer the location of the peak of the probability map of other agents, using a GLM. The $x$ and $y$ coordinates of the peak were estimated independently of each other with different models, where the past positions of the other agent were weighted and fed to a nonlinear function, to estimate the $x$ or $y$ location of the peak. We learned a separate model for a different starting region of the agents (space was split into 64 different 7×7 starting regions), and each model was trained using ${10}^{5}$ simulated trajectories. This procedure was performed separately for every coupling strength $\beta $. In that case, the inferred map that $i$ has of $j$, ${\widehat{P}}_{i}^{j}(t)$, was a Gaussian fit to the estimated peak position at $t$, with variance predetermined as in the regular Gaussian case described in the main text. To make this algorithm more stable and computationally compact, we used a limited temporal window for the social term, $t\in [\mathrm{50,150}]$, and the estimate of the location of the peak was updated only every five steps.

## Effect of Noise on Independent and Social Agents

An animal (agent) searching for a source might be influenced by several sources of noise. These include sensory noise in perceiving the stimulus, inaccuracy in estimating its own location, or, in the case of socialtaxis, receiving inaccurate or noisy information from other group members. We therefore explored the effect of several noise sources on independent and socialtactic agents: We simulated the noise in the agents’ sensory perception by assigning a random probability for missing a hit, which we denote as

*p*(missing a hit). In Fig. S3*A*we plot the mean search time for two independent and two socialtactic agents vs. the probability to miss a hit and find that for low noise socialtactic agents are more efficient at finding the source, whereas for high noise the inverse holds. The probability to miss a hit is equivalent to having a weaker source; hence these results are in agreement with those shown in Fig. S1*A*, which demonstrated that for very weak sources infotaxis is slightly more efficient than socialtaxis. Another form of potential noise that might affect the agents is odometry noise, meaning the agent’s estimate of its own location is inaccurate. Fig. S3*B*shows that for independent agents the search time increases with odometry noise, whereas for coupled agents, the information arriving from the other agent corrects these errors, and their search time is practically independent of the odometry noise we simulated.Another source of noise may be social, which in this case would mean that the social information sent by the other agent or received from it may be corrupt. We simulated this scenario by adding Gaussian white noise to the probability map of agent $j$, ${\stackrel{\sim}{P}}_{j}$; noise was added independently to each cell. Thus, the social term of agent $i$ was now given by the $KL$ divergence from the noisy map, ${G}_{i}=-{D}_{KL}[{P}_{i}|{\stackrel{\sim}{P}}_{j}]$. We found that socialtaxis is more efficient up to very large noise levels (Fig. S3

*C*). An analogous situation may occur when agents use the Gaussian approximation of the other agent’s map in the social term, captured here by randomly shifting the peak position. Fig. S3*D*demonstrates again that for low and moderate noise levels socialtaxis is more efficient, whereas at very high noise levels the use of an inaccurate social term increases search times. We note that we assumed here that agents trusted their conspecifics completely. Adding an uncertainty about the information coming from others would probably improve the results even more.Another possible social noise may arise in the case where agents have different models of the environment. We focus on the case of two agents, where one of the agents has the correct estimate of the strength of the source ${R}_{1}={R}_{real}=1$, whereas the other agent has a wrong estimate of the source emission rate ${R}_{2}$. In Fig. S4

*A*we plot the mean search time vs. $\beta $ for different values of ${R}_{2}$ and note that in all cases the search time decreases monotonically with $\beta $. Furthermore, we note that if one of the agents overestimates the source strength, there is a decrease in the mean search time. In Fig. S4*B*we note that if an agent underestimates the strength of the source, it had a higher probability to find it, for the case of weak couplings between the agents (whereas overestimating the strength of the source decreases the agent’s probability to find it). For strong couplings, these differences vanish, and the probability to find the source becomes independent of the model emission rate ${R}_{2}$ for all values explored.## Acknowledgments

We thank Roy Harpaz, Ori Maoz, Oren Forkosh, Aia Haruvi, Rachel Ludmer, Amir Bar, Ofer Feinerman, and Gasper Tkacik for discussions. This work was supported by a Human Frontier Science Program, European Research Council Grant 311238 and an Israel Science Foundation Grant 1629/12, as well as research support from Martin Kushner Schnur and Mr. and Mrs. Lawrence Feis.

## Supporting Information

Supporting Information (PDF)

- Download
- 841.24 KB

Movie S1.

Full trajectories of the two agents from Fig. 1. Agents begin their search at the top left corner (purple triangles), and their trajectories are marked by blue and green paths; the flashes on top of the trajectories indicate positions where hits were obtained (main text). (Top Left) Each agent is foraging according to infotaxis and ignores the other agent, as in Fig. 1A. (Top Right) Agents use distance-based socialtaxis, as in Fig. 1B. (Bottom Left) Agents use information-based socialtaxis, as in Fig. 1C. (Bottom Right) Fully cooperating agents, who share their hits and coordinate their movements, using a joint infotaxis algorithm as in Fig. 1D.

- Download
- 18.39 MB

Movie S2.

An example of the full trajectories of the two agents using information-based socialtaxis with their time-dependent probability map of the location of the source, for β=10. Agents are searching for a source located in the center (purple square), and begin their search at the top left corner (purple triangles). The agents’ trajectories are marked by blue and green paths; flashes on top of the trajectories indicate positions where hits were obtained.

- Download
- 5.86 MB

Movie S3.

Full trajectories of the two agents using information-based socialtaxis with their time-dependent probability map of the location of the source, for β=−1. Other details are as in Movie S2.

- Download
- 8.78 MB

Movie S4.

Full search paths of groups of 30 agents (Fig. 3). Every dot represents a single agent; agents begin their search close to each other at the top left corner (purple triangles), trying to locate the source placed in the center (purple square). (Left) A group performing independent infotaxis. (Right) A strongly coupled group using information-based socialtaxis, with β=10.

- Download
- 2.49 MB

## References

1

HC Berg, EM Purcell, Physics of chemoreception.

*Biophys J***20**, 193–219 (1977).2

N Barkai, S Leibler, Robustness in simple biochemical networks.

*Nature***387**, 913–917 (1997).3

A Cavagna, et al., Scale-free correlations in starling flocks.

*Proc Natl Acad Sci USA***107**, 11865–11870 (2010).4

M Nagy, Z Akos, D Biro, T Vicsek, Hierarchical group dynamics in pigeon flocks.

*Nature***464**, 890–893 (2010).5

BL McNaughton, FP Battaglia, O Jensen, EI Moser, M Moser, Path integration and the neural basis of the cognitive map.

*Nature***7**, 663–678 (2006).6

S Egnor, K Branson, Computational analysis of behavior.

*Annu Rev Neurosci***39**, 217–236 (2016).7

G Viswanathan, et al., Levy flight search patterns of wandering albatrosses.

*Nature***381**, 413–415 (1996).8

GM Viswanathan, et al., Levy optimizing the success of random searches search patterns of wandering albatrosses.

*Nature***401**, 911–914 (1999).9

P Pirolli

*Information Foraging Theory: Adaptive Interaction with Information*(Oxford Univ Press, New York, 2007).10

E Bonabeau, M Dorigo, G Theraulaz

*Swarm Intelligence: From Natural to Artificial Systems*(Oxford Univ Press, New York, 1999).11

HC Berg

*Random Walks in Biology*(Princeton Univ Press, Princeton, 1993).12

BI Shraiman, ED Siggia, Scalar turbulence.

*Nature***405**, 639–646 (2000).13

A Mafra-Neto, RT Carde, Fine-scale structure of pheromone plumes modulates upwind orientation of flying moths.

*Nature***369**, 142–144 (1994).14

M Vergassola, E Villermaux, BI Shraiman, Infotaxis as a strategy for searching without gradients.

*Nature***445**, 406–409 (2007).15

CM Waters, BL Bassler, Quorum sensing: Cell-to-cell communication in bacteria.

*Annu Rev Cell Dev Biol***21**, 319–346 (2005).16

T Gregor, K Fujimoto, N Masaki, S Sawai, The onset of collective behavior in social amoebae.

*Science***328**, 1021–1025 (2010).17

DM Gordon, The organization of work in social insect colonies.

*Nature***380**, 121–124 (1996).18

A Gelblum, et al., Ant groups optimally amplify the effect of transiently informed individuals.

*Nat Commun***6**, 7729 (2015).19

DJT Sumpter

*The Principles of Collective Animal Behaviour*(Princeton Univ Press, Princeton, 2010).20

A Strandburg-Peshkin, DR Farine, ID Couzin, MC Crofoot, Shared decision-making drives collective movement in wild baboons.

*Science***348**, 1358–1361 (2015).21

Y Shemesh, et al., High-order social interactions in groups of mice.

*Elife***2**, e00759 (2013).22

T Vicsek, A Czirok, E Ben-Jacob, I Cohen, O Shochet, Novel type of phase transition in a system of self-driven particles.

*Phys Rev Lett***75**, 1226–1229 (1995).23

M Ballerini, et al., Interaction ruling animal collective behavior depends on topological rather than metric distance: Evidence from a field study.

*Proc Natl Acad Sci USA***105**, 1232–1237 (2007).24

ID Couzin, J Krause, R James, GD Ruxton, NR Franks, Collective memory and spatial sorting in animal groups.

*J Theor Biol***218**, 1–11 (2002).25

T Mora, W Bialek, Are biological systems poised at criticality?

*J Stat Phys***144**, 268–302 (2010).26

ID Couzin, J Krause, NR Franks, SA Levin, Effective leadership and decision making in animal groups on the move.

*Nature***433**, 513–516 (2005).27

NR Franks, SC Pratt, EB Mallon, NF Britton, DJT Sumpter, Information flow and opinion polling and collective intelligence in house-hunting social insects.

*Philos Trans R Soc Lond B Biol Sci***357**, 1567–1583 (2002).28

AM Simons, Many wrongs: The advantage of group navigation.

*Trends Ecol Evol***19**, 453–455 (2004).29

C List, Democracy in animal groups: A political science perspective.

*Trends Ecol Evol***19**, 168–169 (2004).30

A Livnat, N Pippenger, An optimal brain can be composed of conflicting agents.

*Proc Natl Acad Sci USA***103**, 3198–3202 (2005).31

KM Passino, Biomimicry of bacterial foraging for distributed optimization and control.

*IEEE Contr Syst***22**, 52–67 (2002).32

DJC MacKay

*Information Theory, Inference and Learning Algorithms*(Cambridge Univ Press, Cambridge, UK, 2003).33

JD Rodriguez, D Gomez-Ullate, C Mejia-Monasterio, Geometry-induced fluctuations of olfactory searches in bounded domains.

*Phys Rev E***89**, 042145 (2014).34

A Korman, E Greenwald, O Feinerman, Confidence sharing: An economic strategy for efficient information flows in animal groups.

*PLoS Comput Biol***10**, e1003862 (2014).35

H Barlow, Redundancy reduction revisited.

*Network***12**, 241–253 (2001).36

C Barbieri, S Cocco, R Monasson, On the trajectories and performance of infotaxis and an information-based greedy search algorithm.

*Europhys Lett***94**, 20005 (2011).37

JB Masson, M Bailly-Bechet, M Vergassola, Chasing information to search in random environments.

*J Phys A Math Theor***42**, 434009 (2009).## Information & Authors

### Information

#### Published in

#### Classifications

#### Submission history

**Published online**: May 15, 2017

**Published in issue**: May 30, 2017

#### Keywords

#### Acknowledgments

We thank Roy Harpaz, Ori Maoz, Oren Forkosh, Aia Haruvi, Rachel Ludmer, Amir Bar, Ofer Feinerman, and Gasper Tkacik for discussions. This work was supported by a Human Frontier Science Program, European Research Council Grant 311238 and an Israel Science Foundation Grant 1629/12, as well as research support from Martin Kushner Schnur and Mr. and Mrs. Lawrence Feis.

#### Notes

This article is a PNAS Direct Submission.

### Authors

#### Competing Interests

The authors declare no conflict of interest.

## Metrics & Citations

### Metrics

#### Citation statements

#### Altmetrics

### Citations

#### Cite this article

*Proc. Natl. Acad. Sci. U.S.A.*

114 (22) 5589-5594,

Export the article citation data by selecting a format from the list below and clicking Export.

#### Cited by

Loading...

## View Options

### View options

#### PDF format

Download this article as a PDF file

DOWNLOAD PDF#### Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Personal login Institutional Login#### Recommend to a librarian

Recommend PNAS to a Librarian#### Purchase options

Purchase this article to access the full text.