Meetings: Tech L550, Tuesdays 3:30 - 5:00, Winter 2005
This reading group focuses primarily on the following problem: Given a set of agents (e.g., mobile robots), design a control law to run on each agent to achieve a desired collective "emergent" global behavior of the system. In other words, the global dynamical system defined by the interaction of the many individual robots should have the desired behavior as an attractor (preferably a global attractor).
The performance of the system depends on the global behavior of the system (i.e., it must be evaluated over all the robots). Example tasks include: sensor coverage (place robots in the environment so that the furthest point in the environment from any robot is minimized, or so that all points in the environment are visible from one of the robots, or so that the "information" received from the environment is maximized [where some areas are less interesting than others]); rendezvous (bring all robots to a common meeting point); flocking and swarming (attain a desired formation and keep the formation stable in response to disturbances); and multi-agent pursuer-evader (use a swarm of robots to catch an evader).
The key constraints are that each robot has limited sensing, computation, motion, and communication capabilities. For example, each robot might only be able to sense other robots within a radius R, or communicate with other robots within a radius r, and sensing and communication might incur a delay. The behavior of the swarm should improve/degrade gracefully as robots are added or killed; in other words, the approach should be scalable and robust. These constraints mean that there can be no single "leader" robot. We might also require that each robot run the same control algorithm.
Papers below are mostly from a control viewpoint. Missing are any work on how small-world networks enjoy improved convergence time over locally connected networks and papers from pattern formation and associated techniques (Silber, Bertozzi, Amaral...)
Readings
An easy-to-read background on ideas in emergence of collective behavior.
Abstract In a recent Physical Review Letters article, Vicsek et al. propose a simple but compelling discrete-time model of n autonomous agents (i.e., points or particles) all moving in the plane with the same speed but with different headings. Each agent's heading is updated using a local rule based on the average of its own heading plus the headings of its "neighbors." In their paper, Vicsek et al. provide simulation results which demonstrate that the nearest neighbor rule they are studying can cause all agents to eventually move in the same direction despite the absence of centralized coordination and despite the fact that each agent's set of nearest neighbors change with time as the system evolves. This paper provides a theoretical explanation for this observed behavior. In addition, convergence results are derived for several other similarly inspired models. The Vicsek model proves to be a graphic example of a switched linear system which is stable, but for which there does not exist a common quadratic Lyapunov function.
Problems Analysis of the convergence of the noiseless Vicsek model (each robot averages the heading direction of nearby robots), also with follow-the-leader
Tools Graph theory, Laplacian, adjacency matrix, stochastic and ergodic matrices, common quadratic Lyapunov function
Abstract We construct a continuum model for the motion of biological organisms experiencing social interactions and study its pattern-forming behavior. The model takes the form of a conservation law in two spatial dimensions. The social interactions are modeled in the velocity term, which is nonlocal in the population density and includes a parameter that controls the interaction length scale. The dynamics of the resulting partial integrodifferential equation may be uniquely decomposed into incompressible motion and potential motion. For the purely incompressible case, the model resembles one for fluid dynamical vortex patches. There exist solutions which have constant population density and compact support for all time. Numerical simulations produce rotating structures which have circular cores and spiral arms and are reminiscent of naturally observed phenomena such as ant mills. The sign of the social interaction term determines the direction of the rotation, and the interaction length scale affects the degree of spiral formation. For the purely potential case, the model resembles a nonlocal (forwards or backwards) porous media equation. The sign of the social interaction term controls whether the population aggregates or disperses, and the interaction length scale controls the balance between transport and smoothing of the density profile. For the aggregative case, the population clumps into regions of high and low density. The characteristic length scale of the density pattern is predicted and confirmed by numerical simulations.
Problems
Tools
Abstract We present a self-organizing model of group formation in three-dimensional space, and use it to investigate the spatial dynamics of animal groups such as fish schools and bird flocks. We reveal the existence of major group-level behavioural transitions related to minor changes in individual-level interactions. Further, we present the first evidence for collective memory in such animal groups (where the previous history of group structure influences the collective behaviour exhibited as individual interactions change) during the transition of a group from one type of collective behaviour to another. The model is then used to show how differences among individuals influence group structure, and how individuals employing simple, local rules of thumb, can accurately change their spatial position within a group (e.g. to move to the centre, the front, or the periphery) in the absence of information on their current position within the group as a whole. These results are considered in the context of the evolution and ecological importance of animal groups.
Problems
Tools
Abstract In this paper, we discuss consensus problems for networks of dynamic agents with fixed and switching topologies. We analyze three cases: 1) directed networks with fixed topology; 2) directed networks with switching topology; and 3) undirected networks with communication time-delays and fixed topology. We introduce two consensus protocols for networks with and without time-delays and provide a convergence analysis in all three cases. We establish a direct connection between the algebraic connectivity (or Fiedler eigenvalue) of the network and the performance (or negotiation speed) of a linear consensus protocol. This required the generalization of the notion of algebraic connectivity of undirected graphs to digraphs. It turns out that balanced digraphs play a key role in addressing average-consensus problems. We introduce disagreement functions for convergence analysis of consensus protocols. A disagreement function is a Lyapunov function for the disagreement network dynamics. We proposed a simple disagreement function that is a common Lyapunov function for the disagreement dynamics of a directed network with switching topology. A distinctive feature of this work is to address consensus problems for networks with directed information flow.We provide analytical tools that rely on algebraic graph theory, matrix theory, and control theory. Simulations are provided that demonstrate the effectiveness of our theoretical results.
Problems Consensus problems on graphs (e.g., agreeing on centroid of formation), convergence time as a function of time delays, changing or fixed communication topology, undirected or directed
Tools Network connectivity (Fiedler eigenvalue), graph theory, common Lyapunov function, directed and undirected graphs, balanced digraphs
Abstract Heterogeneous, "aggregated" patterns in the spatial distributions of individuals are almost universal across living organisms, from bacteria to higher vertebrates. Whereas specific features of aggregations are often visually striking to human eyes, a heuristic analysis based on human vision is usually not sufficient to answer fundamental questions about how and why organisms aggregate. What are the individual-level behavioral traits that give rise to these features? When qualitatively similar spatial patterns arise from purely physical mechanisms, are these patterns in organisms biologically significant, or are they simply epiphenomena that are likely characteristics of any set of interacting autonomous individuals? If specific features of spatial aggregations do confer advantages or disadvantages in the fitness of group members, how has evolution operated to shape individual behavior in balancing costs and benefits at the individual and group levels? Mathematical models of social behaviors such as schooling in fishes provide a promising avenue to address some of these questions. However, the literature on schooling models has lacked a common framework to objectively and quantitatively characterize relationships between individual-level behaviors and grouplevel patterns. In this paper, we briefly survey similarities and differences in behavioral algorithms and aggregation statistics among existing schooling models. We present preliminary results of our efforts to develop a modeling framework that synthesizes much of this previous work, and to identify relationships between behavioral parameters and group-level statistics.
Problems Review of swarming and flocking behavior in animals
Tools Simulation study
Abstract We consider the problem of cooperation among a collection of vehicles performing a shared task using intervehicle communication to coordinate their actions. Tools from algebraic graph theory prove useful in modeling the communication network and relating its topology to formation stability.We prove a Nyquist criterion that uses the eigenvalues of the graph Laplacian matrix to determine the effect of the communication topology on formation stability. We also propose a method for decentralized information exchange between vehicles. This approach realizes a dynamical system that supplies each vehicle with a common reference to be used for cooperative motion. We prove a separation principle that decomposes formation stability into two components: Stability of the is achieved information flow for the given graph and stability of an individual vehicle for the given controller. The information flow can thus be rendered highly robust to changes in the graph, enabling tight formation control despite limitations in intervehicle communication capability.
Problems Relation of network topology to stability of a formation, consensus problems
Tools Algebraic graph theory, graph Laplacian and its eigenvalues, Nyquist criterion for SISO linear systems, separation principle (local controller, information flow in the network), discrete-time linear systems and z-transform
Abstract Inspired by the so-called "bugs" problem from mathematics, we study the geometric formations of multivehicle systems under cyclic pursuit. First, we introduce the notion of cyclic pursuit by examining a system of identical linear agents in the plane. This idea is then extended to a system of wheeled vehicles, each subject to a single nonholonomic constraint (i.e., unicycles), which is the principal focus of this paper. The pursuit framework is particularly simple in that the n identical vehicles are ordered such that vehicle pursues vehicle i+1 modulo n. In this paper, we assume each vehicle has the same constant forward speed. We show that the system's equilibrium formations are generalized regular polygons and it is exposed how the multivehicle system's global behavior can be shaped through appropriate controller gain assignments. We then study the local stability of these equilibrium polygons, revealing which formations are stable and which are not.
Problems Stability of quilibria of formations where each vehicle pursues another (in a ring)
Tools Circulant matrices, local linear stability analysis, Routh array
Abstract This paper presents coordination algorithms for networks of mobile autonomous agents. The objective of the proposed algorithms is to achieve rendezvous, that is, agreement over the location of the agents in the network. We provide analysis and design results for multi-agent networks in arbitrary dimensions under weak requirements on the switching and failing communication topology. The novel correctness proof relies on proximity graphs and their properties and on a general LaSalle Invariance Principle for nondeterministic discrete-time dynamical systems.
Problems Rendezvous of robots with switching communication topologies
Tools Proximity graphs, nondeterministic discrete-time LaSalle Invariance Principle