Communications of the ACM
Home/Magazine Archive/December 2012 (Vol. 55, No. 12)/Technical Perspective: Natural Algorithms in a Networked.../Full Text
Research highlights
Technical Perspective: Natural Algorithms in a Networked World
How do birds flock and fish school? How do individuals in a social network reach agreement, even though they are often only influenced by other like-minded individuals? How do fireflies flash synchronously? How can one engineer a swarm of robots to behave like bird flocks?
These are some of the questions that have occupied the minds of many researchers across a diverse set of disciplines over the past two decades, from computer graphics to statistical physics to evolutionary biology, and from control theory to robotics, mathematics, and computer science. Most of the early research, which happened in computer graphics and statistical physics, was on modeling and simulation of collective behavior. Over the past decade the focus has shifted to rigorous theory, leading to what one might call a theory of collective phenomena in multiagent systems. This theory blends dynamical systems, graph theory, Markov chains, and algorithms.
The collective phenomena are often modeled as many-degrees-of-freedom (discrete-time or continuous time) dynamical systems with an additional twist that the interconnection structure between individual dynamical systems change, since the motion of each node in a flock (or opinion of an individual) is affected primarily by those in the node's local neighborhood. The twist here is that the local neighborhood is not fixed: neighbors are defined based on the actual state of the system: For example, in case of opinion dynamics, sociological models indicate that individuals are often influenced by those whose opinions are close to them. In other words, as opinions evolve, neighborhood structures change as the function of the evolving opinion, resulting in a catch 22. Similarly, as birds aggregate their directions with their neighbors, the set of their neighbors change.
When the neighborhood structures stay intact throughout the evolution of the dynamics, the behavior of the model is easy to analyze. Using Perron-Frobenius theory, one can easily show that connectivity of the network induced by the local neighborhood relations is in fact enough to result in global agreement (in opinions, direction of motion in a flock, or frequency of oscillations in coupled oscillators). One can extend the analysis to the case of time varying or switching networks. If the network change is modeled exogenously, in order to get agreement all that is needed is to make sure the underlying graphs that encode the neighborhood structure stay connected over time, that is, over time the union of the edges of the resulting graphs corresponds to a connected graph for all times. The focus on the case where the neighborhood change is exogenous is not without its merits, but this is mostly done for convenience. How can we take the explicit dependence of the graph on the state of the evolving dynamical system into account? This is where the following paper by Bernard Chazelle makes a major contribution.
This paper is a unique exception in the literature, where the endogenous change is explicitly taken into account, leading to the beginnings of a general theory of influence systems: where a dynamical system sits on top of nodes of a graph and the edges of the graph change endogenously as the function of the node states. What is the behavior of this (undoubtedly complex) dynamical system? What tools do we need to analyze such systems? These are the questions the paper aims to address. As it turns out, even in the simplest of cases (where the graph is a geometric graph in one dimension and the update is piece-wise linear) this is not an easy question to answer.
First, Chazelle introduces us to the notion of the s-Energy: A parameterized family of Lyapunov functions that represent the evolution of global misalignment between flockmates. Via a tour de force roller coaster ride through dynamical systems, computational geometry, combinatorics, complexity theory, and algorithms, Chazelle creates an "algorithmic calculus" for diffusive influence systems: He shows us surprisingly, that the orbit or flow of such systems are attracted to a fixed point in the bidirectional case, and a limit cycle for almost all arbitrarily small random perturbations. But wait, there is more: the convergence time can also be bounded in both cases and the bounds are essentially optimal.
The impressive setup of the diffusive influence system developed by Chazelle creates a near universal setup for analyzing various problems involving collective behavior in networked multi-agent systems, from flocking, opinion dynamics, information aggregation, to synchronization problems. This is as close as one can get to a domain-independent analysis of such networked systems. In short, we need more tools and methods like this to study natural algorithms in an increasingly networked world. To make progress on natural algorithms, we might need to rethink the siloed view of education as partitioned into current academic departments. Chazelle's work shows that we can no longer afford to separate algorithms, complexity, combinatorics, and graphs from systems theory and dynamical systems.
©2012 ACM 0001-0782/12/12
Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.
No entries found