Insolite : des robots-souris résolvent des labyrinthes complexes

Depuis les années 1970 sévit une discipline à peu près inconnue en France : la micromouse. Cette compétition est pourtant très populaire au Royaume-Uni, au Japon, en Inde et en Corée du Sud. L'épreuve consiste à fabriquer un petit robot, la souris (mouse), qui doit trouver le centre du labyrinthe le plus rapidement possible. La compétition se déroule en deux étapes : l'apprentissage et le run. Mais regardez plutôt en image.  

Le labyrinthe est un grand plan carré de 2,88 mètres carrés composé de seize cellules de 180 millimètres de côté par 50 millimètres de hauteur. Les cellules ont tendance à se multiplier avec les années, complexifiant la compétition. Le petit robot ne doit pas excéder 250 millimètres de large et de long. En revanche, il n'y a pas de hauteur limite. Il ne peut pas endommager les mursmurs (ce qui serait trop facile) et il doit utiliser des sources d'énergieénergie non polluantes.  

Comment font-ils pour reconnaître leur chemin?

Ils se basent sur un algorithme. Le A*(A star) est un algorithme de recherche de chemin. Il l'indique d'ailleurs très rapidement mais n'indique pas nécessairement la solution optimale. Autrement dit, pour aller d'un point à un autre, le robot commence par se diriger vers le point d'arrivée. Il choisit donc la cellule la plus proche de l'arrivée au détriment d'autres cellules. Cependant, il les garde quand même en mémoire pour les utiliser en cas d'impasse. 

La méthode de l'algorithme de remplissage par diffusiondiffusion est différente. Chaque case possède une valeur au départ qui est égale au nombre minimal de cases à parcourir pour rejoindre l'arrivée s'il n'y avait pas d'obstacles. En avançant dans chaque case, l'algorithme recalcule la valeur de la case en fonction des obstacles et des cases voisines. Donc, quand il a parcouru la totalité du labyrinthe, il donnera le chemin le plus faible, autrement dit celui qui aura la valeur la plus faible.