Research ArticleNETWORK SCIENCE

Optimal network topology for responsive collective behavior

See allHide authors and affiliations

Science Advances  03 Apr 2019:
Vol. 5, no. 4, eaau0999
DOI: 10.1126/sciadv.aau0999
  • Fig. 1 Collective frequency response for a ring network.

    (Left) Response of N = 2048 agents performing distributed linear consensus over a regular periodic 1D grid with fixed degree k. Larger degrees yield a higher response at low frequency (ω < 2 × 10−3), while the opposite is true at high frequency (ω > ωhigh = 0.278). (Right) Optimal degree k* for maximum collective response as a function of the frequency ω for a system of N agents distributed on a ring. For low frequency, the optimal k* corresponds to an all-to-all connectivity. At higher frequencies, k*(ω) follows the “bulk” behavior from Eq. 1 (fit, black line) up to its lowest possible value, k* = 2, at ω = ωhigh.

  • Fig. 2 Optimal networks for collective response.

    (Top left) Optimal degree k* for maximum collective response as a function of the frequency ω for a system of N = 1024 arranged in different network topologies (N = 840 for the caveman topology). Note that some networks display a sudden transition from all-to-all to minimal connectivity, while others have an intermediate range of frequencies where k* follows a scaling law of the form Eq. 1. (Top right) Optimal connection weights wij as a function of topological distance for a system of N = 4096 agents at a given frequency ω. The inset shows the optimal number of connections k* obtained by fitting a Heaviside function to the weight distributions. (Bottom) Optimal network topologies for a system of N + 1 = 11 agents obtained by stochastic numerical discrete optimization over the space of unweighted, undirected graphs. Instead of fixing the leader to be a particular agent, the optimization maximizes the collective frequency response averaged over all the possible leaders (allowing disconnected graphs to be optimal). Note that the mean degree of these networks is consistently reduced with increased frequency ω.

  • Fig. 3 Distributed heading consensus experiment with a swarm of 11 robots.

    Evolution of the robots’ heading in an experiment with one leader (black line) rotating at frequency ω = 0.04 Hz (top) or ω = 0.06 Hz (bottom) when each robot has either k = 2 neighbors (left column) or k = 10 (right column). The degree by which each agent is following the leader at a given instant is Hi(t) (Eq. 18), and the square of the mean value (displayed in the lateral bar) is its frequency response.

  • Fig. 4 Collective response in leader-follower heading consensus for a system of N + 1 = 11 agents.

    (A) Experimental collective frequency response (Eq. 19, normalized) obtained with 10 robots performing distributed heading consensus plus one leader rotating at a fixed frequency ω. (B) Response for the equivalent LTI distributed linear consensus (Eq. 5, normalized) with the same N. (C) Response obtained with simulations of the heading consensus algorithm (Eq. 16).

  • Fig. 5 Robotic platform used in the experiments.

    The SBC and XBee module attached to the robot provides autonomy and distributed communications to the unit, making it able to swarm and perform decentralized collective motion such as heading consensus. (Photo credit: David Mateo, Singapore University of Technology and Design.)

Supplementary Materials

  • Supplementary material for this article is available at http://advances.sciencemag.org/cgi/content/full/5/4/eaau0999/DC1

    Movie S1. Experiment to measure the collective response in leader-follower heading consensus of a swarm of N + 1 = 11 land robots with a low-frequency input signal.

    Movie S2. Experiment to measure the collective response in leader-follower heading consensus of a swarm of N + 1 = 11 land robots with a high-frequency input signal.

  • Supplementary Materials

    Download PDF

    Other Supplementary Material for this manuscript includes the following:

    • Movie S1 (.mp4 format). Experiment to measure the collective response in leader-follower heading consensus of a swarm of N + 1 = 11 land robots with a low-frequency input signal.
    • Movie S2 (.mp4 format). Experiment to measure the collective response in leader-follower heading consensus of a swarm of N + 1 = 11 land robots with a high-frequency input signal.

    Files in this Data Supplement:

Stay Connected to Science Advances

Navigate This Article