Answers.Body: <p>There has been quite a few approaches to achieve such kind of distributed coordination. I present here one of them, for its generality and simplicity (that makes it easy to remember too). But first, the general idea behind these approaches is pretty interesting, around a mechanism called <a href="https://en.wikipedia.org/wiki/Stigmergy">stigmergy</a>.</p>
  
  <p>Stigmergy is a behaviour coordination mechanism mediated by the environment. It was first described for termites, and the most famous example pertains to ants. Ants form trails when going out for food, but they often do not interact <em>directly</em>. It turns out they leave pheromones on the ground as they walk away from their hills. The pheromone allows them to find their way home, and it also guides where they are going: If they find a pheromone trace from one of their peers, they follow it and their own pheromones <em>add up</em>, reinforcing the signal of the trail. In stage, more and more ants get "together as they move", forming a trail. Coordination has been achieved.</p>
  
  <p>Among the various implementation derived from stigmergy, there is the "field-based motion coordination model" (FBMCM). The idea is to create a (maybe virtual) environment that maintains some states of the world. Each object registers in the environment a signal that is maximum at the object position (its edges) and then decreases with distance. Moving objects (e.g. robots) each emit a signal relayed by the environment. They can then sense each other's field and act accordingly: E.g., when signals are strong, move away; when weak, it is safe to get closer, etc. Several complex group moves have been demonstrated in software simulators (platoon formation in games, drill simulations) and with robots. The benefit of this approach is that it can be cheap to compute even complex behaviours. For example, avoiding clashes requires simple "logic" code based on summing-up nearby fields value. FBMCM is pretty slick, used in video-games, but hard to implement in physical settings (to my <em>dating</em> knowledge), as it can be challenging to build a reliable environment. See for example the work from <a href="https://www.researchgate.net/publication/2949751_Field-based_Motion_Coordination_In_Quake_3_Arena">Mamei and Zambonelli</a>, as well as one of the first industrial implementations for robots by <a href="https://www.researchgate.net/publication/221456459_Decentralized_control_of_E%27GV_transportation_systems">Weyns et al.</a>. Note that the implementation for robots required significant work on the environment infrastructure, made somewhat more feasible as it was a controlled warehouse.</p>
  
  <p>The advantage of stigmergy-like models is that they are often <em>simple</em> and <em>resilient</em>: You can lose an ant without impact on the food-finding trail. On the downside, these models are usually <em>slow</em>, as the coordination takes time to emerge from indirect interactions. This can be improved upon by adding extra direct interactions (e.g. empowering ants with a GPS and a grocery store map, or just a magnetic-North sense).</p>
  
  <p>In practice, these models can collapse if the environment implementation is not reliable. It can be difficult for robots or, say, self-driving cars, if they expect some transponders put on their way, as these devices are expensive to set and maintain, and they can be broken or stolen. It would be better to endow robots with radars, sonars or other proximity sensors to implement stigmergic models. One related example is the decision by Tesla to add radars to its cars, instead of assuming reliable transponders on the road (<em>note</em>: This is just a parallel; there is no official relation).</p>
  
  <p>Other implementations and related models are, for example, tuple-based coordination languages such as <a href="https://en.wikipedia.org/wiki/Linda_(coordination_language)">Linda</a>, and network protocols like <a href="https://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf">Chord</a>. As you see, these works are not necessarily in the "AI domain".</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-08-07T10:13:49.460Z
Answers.LastActivityDate: 2016-08-07T10:13:49.460Z
Answers.UserDisplayName: Eric Platon
Body: <p>How can a swarm of small robots (like Kilobots) walking close to each other achieve collaboration without bumping into each other? For example, one study shows <a href="http://science.sciencemag.org/content/345/6198/795.abstract" rel="noreferrer">programmable self-assembly in a thousand-robot swarm</a> (see <a href="http://robohub.org/thousand-robot-swarm-self-assembles-into-arbitrary-shapes/" rel="noreferrer">article</a> &amp; <a href="https://vimeo.com/103329200" rel="noreferrer">video</a>) which are moving without GPS-like system and by measuring distances to neighbours. This was achieved, because the robots were very slow.</p>
  
  <p>Is there any way that similar robots can achieve much more efficient and quicker assembly by using more complex techniques of coordination? Not by walking around clock-wise (which I guess was the easiest way), but I mean using some more sophisticated way. Because waiting half a day (~11h) to create a simple star shape using a thousand-robot swarm is way too long!</p>
  
Tags: <robots><multi-agent-systems>
Title: How can thousand-robot swarm coordinate their moves without bumping into each other?
UserDisplayName: kenorb
ThreadText: # How can thousand-robot swarm coordinate their moves without bumping into each other?
  
  (Asked by: username_0 on 2016-08-07)
  
  How can a swarm of small robots (like Kilobots) walking close to each other achieve collaboration without bumping into each other? For example, one study shows [programmable self-assembly in a thousand-robot swarm](http://science.sciencemag.org/content/345/6198/795.abstract) (see [article](http://robohub.org/thousand-robot-swarm-self-assembles-into-arbitrary-shapes/) & [video](https://vimeo.com/103329200)) which are moving without GPS-like system and by measuring distances to neighbours. This was achieved, because the robots were very slow.
  
  Is there any way that similar robots can achieve much more efficient and quicker assembly by using more complex techniques of coordination? Not by walking around clock-wise (which I guess was the easiest way), but I mean using some more sophisticated way. Because waiting half a day (~11h) to create a simple star shape using a thousand-robot swarm is way too long!
  
  **Tags:** robots, multi-agent-systems
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2016-08-07. Score: 9 | Accepted answer
  
  There has been quite a few approaches to achieve such kind of distributed coordination. I present here one of them, for its generality and simplicity (that makes it easy to remember too). But first, the general idea behind these approaches is pretty interesting, around a mechanism called [stigmergy](https://en.wikipedia.org/wiki/Stigmergy).
  
  Stigmergy is a behaviour coordination mechanism mediated by the environment. It was first described for termites, and the most famous example pertains to ants. Ants form trails when going out for food, but they often do not interact *directly*. It turns out they leave pheromones on the ground as they walk away from their hills. The pheromone allows them to find their way home, and it also guides where they are going: If they find a pheromone trace from one of their peers, they follow it and their own pheromones *add up*, reinforcing the signal of the trail. In stage, more and more ants get "together as they move", forming a trail. Coordination has been achieved.
  
  Among the various implementation derived from stigmergy, there is the "field-based motion coordination model" (FBMCM). The idea is to create a (maybe virtual) environment that maintains some states of the world. Each object registers in the environment a signal that is maximum at the object position (its edges) and then decreases with distance. Moving objects (e.g. robots) each emit a signal relayed by the environment. They can then sense each other's field and act accordingly: E.g., when signals are strong, move away; when weak, it is safe to get closer, etc. Several complex group moves have been demonstrated in software simulators (platoon formation in games, drill simulations) and with robots. The benefit of this approach is that it can be cheap to compute even complex behaviours. For example, avoiding clashes requires simple "logic" code based on summing-up nearby fields value. FBMCM is pretty slick, used in video-games, but hard to implement in physical settings (to my *dating* knowledge), as it can be challenging to build a reliable environment. See for example the work from [Mamei and Zambonelli](https://www.researchgate.net/publication/2949751_Field-based_Motion_Coordination_In_Quake_3_Arena), as well as one of the first industrial implementations for robots by [Weyns et al.](https://www.researchgate.net/publication/221456459_Decentralized_control_of_E%27GV_transportation_systems). Note that the implementation for robots required significant work on the environment infrastructure, made somewhat more feasible as it was a controlled warehouse.
  
  The advantage of stigmergy-like models is that they are often *simple* and *resilient*: You can lose an ant without impact on the food-finding trail. On the downside, these models are usually *slow*, as the coordination takes time to emerge from indirect interactions. This can be improved upon by adding extra direct interactions (e.g. empowering ants with a GPS and a grocery store map, or just a magnetic-North sense).
  
  In practice, these models can collapse if the environment implementation is not reliable. It can be difficult for robots or, say, self-driving cars, if they expect some transponders put on their way, as these devices are expensive to set and maintain, and they can be broken or stolen. It would be better to endow robots with radars, sonars or other proximity sensors to implement stigmergic models. One related example is the decision by Tesla to add radars to its cars, instead of assuming reliable transponders on the road (*note*: This is just a parallel; there is no official relation).
  
  Other implementations and related models are, for example, tuple-based coordination languages such as [Linda](https://en.wikipedia.org/wiki/Linda_(coordination_language)), and network protocols like [Chord](https://pdos.csail.mit.edu/papers/chord:sigcomm01/chord_sigcomm.pdf). As you see, these works are not necessarily in the "AI domain".
  
  
  ---
  
  