Swarm Intelligence

“Swarm intelligence is the discipline that deals with natural and artificial systems composed of many individuals that coordinate using decentralized control and self-organization.”

Marco Dorigo and Mauro Birattari (2007) Swarm intelligence. Scholarpedia, 2(9):1462.

Self-organization

“Self-organization is a process in which pattern at the global level of a system emerges solely from numerous interactions among the lower-level components of the system. Moreover, the rules specifying interactions among the system’s components are executed using only local information, without reference to the global pattern”

Gerardo Beni. From swarm intelligence to swarm robotics. In Swarm Robotics, pages 1-9. Springer, 2005.

Taxonomie - Sur base de la nature des agents:

Naturel

Artificiel

Taxonomie - Sur base de l’objectif:

Flocking

Schooling

Comment ça marche?

Reynolds, Craig W. “Flocks, herds and schools: A distributed behavioral model.” ACM SIGGRAPH computer graphics. Vol. 21. No. 4. ACM, 1987. http://www.red3d.com/cwr/boids/

Synchronisation des metronomes

Synchronisation des lucioles

Comment ça marche?

while(True):
  counter +=1

  # Signaling part
  if counter > T:
    signal
    counter = 0
    
  # Synchronization
  if signal_detected:
    counter += alpha * counter

Robotique en essaim

“Swarm robotics is the study of how to design groups of robots that operate without relying on any external infrastructure or on any form of centralized control. In a robot swarm, the collective behavior of the robots results from local interactions between the robots and between the robots and the environment in which they act”

Marco Dorigo et al. (2014) Swarm robotics. Scholarpedia, 9(1):1463.

M. Brambilla, E. Ferrante, M. Birattari, and M. Dorigo. Swarm robotics: a review from the swarm engineering perspective. Swarm Intelligence, 7(1):1-41, 2013.

Propriètes desirées:

• Tolerance au défauts
• Scalabilité
• Flexibilité

Transport collectif

Auto-assemblage

Essaim héterogène

ACO

Ant colony optimization (ACO) is a population-based metaheuristic that can be used to find approximate solutions to NP-hard optimization problems.

Marco Dorigo (2007) Ant colony optimization. Scholarpedia, 2(3):1461.

Pseudo-code

1. Initialization fourmis
2. Selection route
3. Mise à jour phéromone

Equations

ACO - Pseudo-code

1. Initialization fourmis
2. Selection route
3. Mise à jour phéromone

Selection route

\[ p_{xy}^k = \frac { (\tau_{xy}^{\alpha}) (\eta_{xy}^{\beta}) } { \sum_{z\in \mathrm{allowed}_y} (\tau_{xz}^{\alpha}) (\eta_{xz}^{\beta}) } \]

Mise à jour pheromone

\[ \tau_{xy} \leftarrow (1-\rho)\tau_{xy} + \sum_{k}\Delta \tau^{k}_{xy} \]

où:

\(\eta_{xy}\) represente la valeur héuristique associé au problème

\(\tau_{xy}\) represente la valeur du pheromone

Application - Problème du commis voyageur (TSP)

Solution possible:

Permutation des villes: \[ [v_1, \cdots, v_n] \]

Formulation:

\[\eta_{xy} \rightarrow \frac{1}{d_{xy}}\]

Ici

http://www.wooclap.com/LDHHPB

Mais aussi chez vous!

ARGOS - Simulateur

http://www.argos-sim.info/

Simulations

http://iridia.ulb.ac.be/~lgarattoni/h-414/