3
$\begingroup$

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

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jeremy Apr 2 '13 at 9:41
  • $\begingroup$ 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. see also flocking, wikipedia. also a useful search term is "boids" $\endgroup$ – vzn Apr 2 '13 at 15:22
  • 1
    $\begingroup$ @vzn My interest in this started from a very practical problem, but I'm now interested in this from a general science perspective. $\endgroup$ – David Chouinard Apr 2 '13 at 17:32
3
$\begingroup$

Bernard Chazelle has done some work on the convergence of bird flocking, and he's considered models such as follow-the-leader and variants.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

this area was pioneered by Reynolds in 1986 who devised the 1st computational model for biological/algorithmic "flocking" behavior he dubbed "boids" and later research uses the same term. at the time it fit into the new emerging fields of artificial life and 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), Reza Olfati-saber

[2] Reynolds Boids/Flocking

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.