<p>Bernard Chazelle has done some work on the <a href="http://arxiv.org/abs/0905.4241" rel="nofollow">convergence of bird flocking</a>, and he's considered models such as follow-the-leader and variants. </p>

CC BY-SA 3.0
2013-04-02T00:37:02.353Z
2013-04-02T00:37:02.353Z
Suresh Venkat
<p>this area was pioneered by Reynolds in 1986 who devised the 1st computational model for biological/algorithmic <a href="http://en.wikipedia.org/wiki/Flocking_%28behavior%29" rel="nofollow">"flocking"</a> behavior he dubbed <a href="http://en.wikipedia.org/wiki/Boids" rel="nofollow">"boids"</a> and later research uses the same term. at the time it fit into the new emerging fields of <a href="http://en.wikipedia.org/wiki/Artificial_life" rel="nofollow">artificial life</a> and <a href="http://en.wikipedia.org/wiki/Emergent_behavior" rel="nofollow">emergent behavior</a>. the related study is now very broad and has expanded into many fields such as biology, robotics, gaming, etc. </p>

<p>Reynolds [2] has a very large survey of links covering many different angles including a directory of many implementations. [1] has some survey along with a more abstract/mathematical TCS style analysis.</p>

<p>[1] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.135.5931" rel="nofollow">Flocking for multi-agent dynamic systems: Algorithms and theory (2006)</a>, Reza Olfati-saber</p>

<p>[2] <a href="http://www.red3d.com/cwr/boids/" rel="nofollow">Reynolds Boids/Flocking</a></p>

CC BY-SA 3.0
2013-04-02T15:39:57.493Z
2013-04-02T15:39:57.493Z
vzn
<p>In an AI strategy game simulation, I devised an algorithm for forming a group and swarming a known location without communication among soldiers (ie. every individual agent makes a locally optimum decision without general knowledge of the map).</p>

<p>I'm trying to get a more rigorous understanding of any background literature on similar algorithms. Surely this is not an original idea, but I don't even know what terms to start googling for.</p>

<p>Here is diagram of the functioning of the algorithm.</p>

<p><img src="https://i.sstatic.net/kvcOu.png" alt="swarm formation algorithm"></p>

<p>Every circle is a soldier, with the center number representing a uniquely assigned soldier_id. Soliders have finite vision range but know the global position of the "X".</p>

<p>When prompted to form a swarm, soldiers start looking for the soldier within its vision range that had the smallest soldier_id and follows it. If it is itself the lowest soldier_id in range, it starts going in direction of the X. This leads to an organic formation of all the soldiers, with the soldier with the lowest soldier_id at the helm.</p>

<p>As I said, I'm trying to get a sense of general literature on similar algorithms and I don't have nearly enough experience general knowledge of computer science to know where to start. Perhaps there are similar ideas in place in bee or ant colonies or other biological systems. Perhaps even in cell formation?</p>

<p>I'm not even sure this is the appropriate place to ask this question. If it isn't, any pointers would be appreciated.</p>

CC BY-SA 3.0
2013-04-02T09:41:47.940Z
I heard some talks about similar processes in the field of Genetic Algorithms (seach publications by Michele Sebag?). They should have references to relevant work.
J.y B.y
CC BY-SA 3.0
2013-04-02T15:22:37.757Z
this started out as abstract theoretical research into "artificial life" years ago but you probably more want applied algorithms from gaming field unless you have some more scientific and less practical interest. try [game dev](http://gamedev.stackexchange.com/). see also [flocking](http://en.wikipedia.org/wiki/Flocking_%28behavior%29), wikipedia. also a useful search term is ["boids"](http://en.wikipedia.org/wiki/Boids)
vzn
CC BY-SA 3.0
2013-04-02T17:32:09.690Z
@vzn My interest in this started from a very practical problem, but I'm now interested in this from a general science perspective.
David Chouinard
<ds.algorithms><reference-request><graph-algorithms><natural-computing><greedy-algorithms>
Follow-the-leader algorithm in swarm formation: literature on the subject?
David Chouinard
# Follow-the-leader algorithm in swarm formation: literature on the subject?

(Asked by: username_0 on 2013-04-02)

In an AI strategy game simulation, I devised an algorithm for forming a group and swarming a known location without communication among soldiers (ie. every individual agent makes a locally optimum decision without general knowledge of the map).

I'm trying to get a more rigorous understanding of any background literature on similar algorithms. Surely this is not an original idea, but I don't even know what terms to start googling for.

Here is diagram of the functioning of the algorithm.

![swarm formation algorithm](https://i.sstatic.net/kvcOu.png)

Every circle is a soldier, with the center number representing a uniquely assigned soldier\_id. Soliders have finite vision range but know the global position of the "X".

When prompted to form a swarm, soldiers start looking for the soldier within its vision range that had the smallest soldier\_id and follows it. If it is itself the lowest soldier\_id in range, it starts going in direction of the X. This leads to an organic formation of all the soldiers, with the soldier with the lowest soldier\_id at the helm.

As I said, I'm trying to get a sense of general literature on similar algorithms and I don't have nearly enough experience general knowledge of computer science to know where to start. Perhaps there are similar ideas in place in bee or ant colonies or other biological systems. Perhaps even in cell formation?

I'm not even sure this is the appropriate place to ask this question. If it isn't, any pointers would be appreciated.

**Tags:** ds.algorithms, reference-request, graph-algorithms, natural-computing, greedy-algorithms
> **Comments:**
> **username_1**: I heard some talks about similar processes in the field of Genetic Algorithms (seach publications by Michele Sebag?). They should have references to relevant work.  
> **username_2**: this started out as abstract theoretical research into "artificial life" years ago but you probably more want applied algorithms from gaming field unless you have some more scientific and less practical interest. try [game dev](http://gamedev.stackexchange.com/). see also [flocking](http://en.wikipedia.org/wiki/Flocking_%28behavior%29), wikipedia. also a useful search term is ["boids"](http://en.wikipedia.org/wiki/Boids)  
> **username_0**: @vzn My interest in this started from a very practical problem, but I'm now interested in this from a general science perspective.  

---

## 2 answers

### Answer by username_3 on 2013-04-02. Score: 3 | Accepted answer

Bernard Chazelle has done some work on the [convergence of bird flocking](http://arxiv.org/abs/0905.4241), and he's considered models such as follow-the-leader and variants.


---

### Answer by username_2 on 2013-04-02. Score: 2

this area was pioneered by Reynolds in 1986 who devised the 1st computational model for biological/algorithmic ["flocking"](http://en.wikipedia.org/wiki/Flocking_%28behavior%29) behavior he dubbed ["boids"](http://en.wikipedia.org/wiki/Boids) and later research uses the same term. at the time it fit into the new emerging fields of [artificial life](http://en.wikipedia.org/wiki/Artificial_life) and [emergent behavior](http://en.wikipedia.org/wiki/Emergent_behavior). the related study is now very broad and has expanded into many fields such as biology, robotics, gaming, etc.

Reynolds [2] has a very large survey of links covering many different angles including a directory of many implementations. [1] has some survey along with a more abstract/mathematical TCS style analysis.

[1] [Flocking for multi-agent dynamic systems: Algorithms and theory (2006)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.135.5931), Reza Olfati-saber

[2] [Reynolds Boids/Flocking](http://www.red3d.com/cwr/boids/)


---

