Natural Algorithms

Our ultimate goal is to understand the paper by Chazelle.

As a warm-up, we start with the papers by Vicsek et al, Jadbabaie et al, Cucker and Smale.

Vicsek et al. propose the following model. They consider a set of particles (= points in the plane) in the plane. The particles move with constant velocity v. The direction of particle i at time t+1 is the average of the directions of the neighboring particles (= all particles with distance at most one) plus some random noise. The model is studied through computer simulations.

Jadbabaie et al. (partially) analyse Vicsek's model. They assume a neighborhood graph G(t) on the particles at any time t. The direction of a particle i at time t+1 is the average of the directions of i's neighbors in G(t). They prove convergence if G(t) has nice properties for all t. For example, if G(t) is connected for all t.

Cucker and Smale assume that any particle is influenced by all other particles at any time unit. However, the weight of the influence depends on the distance. They prove convergence.

Chazelle does not only prove convergence, but estimates the time to convergence. He proves upper and lower bounds.

For the first meeting on Monday March 2nd, you should read the paper by Vicsek et al. and skim through the 9 pages of the paper by Jadbaie et al.

Last modified: Mon Mar 2 14:54:16 CET 2009