# Micromouse

Une compétition de type micromouse est une compétition dans laquelle de petites souris robotiques s’affrontent pour résoudre un labyrinthe composé d’une grille de 16×16 cellules.

## Historique
### Le précurseur Theseus

Le concept de souris résolvant mécaniquement un labyrinthe remonte à l’expérience de « Theseus » imaginée par Claude Shannon en 1950. La grille ne faisait alors qu’une taille de 5×5 cellules, et la souris n’était pas encore autonome mais en bois, munie d’un aimant et contrôlée magnétiquement par une machine sous le labyrinthe. Cette machine composée d’une série de circuits de relais téléphonique surcyclés par Shannon pouvait apprendre la disposition du labyrinthe en manipulant la souris et une fois fait, résoudre le labyrinthe peut importe l’endroit où l’on redéposait la souris. L’expérience est considérée comme l’un des premiers exemples d’apprentissage automatique et comme une source d’inspiration pour le domaine de l’intelligence artificielle, établie en tant que discipline en 1956.

### Micromouse

Les compétitions micromouse ont commencé à la fin des années 1970.
La première compétition est annoncée en 1977 par l’Institute of Electrical and Electronics Engineers (IEEE) dans son magazine IEEE Spectrum. La grille était alors de taille 10×10.
Les compétitions ont lieu dans le monde entier et sont plus populaires au Royaume-Uni, aux États-Unis, au Japon, à Singapour, en Inde, en Corée du Sud et deviennent populaires dans les pays du sous-continent tels que le Sri Lanka.
Des compétitions$^,$ et conférences sont organisées régulièrement. Il existe désormais plus de 100 compétitions micromouse chaque année (pour la plupart parrainées par des universités ou l’IEEE), entre autres.

## Fonctionnement et variante
### Dimensions et fonctionnement

Le labyrinthe est constitué d’une grille de 16 × 16 cellules, chacune formant un carré de 180 mm$^2$ avec des parois de 50 mm de hauteur. Les souris sont des robots complètement autonomes qui doivent se frayer un chemin sans aide depuis une position de départ prédéterminée vers la zone centrale du labyrinthe. La souris doit savoir où elle se trouve, découvrir les murs au fur et à mesure qu’elle explore, cartographier le labyrinthe et détecter quand elle a atteint l’objectif. Une fois l'objectif atteint, la souris effectuera généralement des recherches supplémentaires dans le labyrinthe jusqu'à ce qu'elle ait trouvé un itinéraire optimal du début à la fin. Une fois l'itinéraire optimal trouvé, la souris parcourra cet itinéraire dans les plus brefs délais.
Le labyrinthe est un carré de 2,88 m$^2$ de surface composé de seize « cellules » carrées de 180 millimètres de côté et de 50 millimètres de haut. Il peut y avoir 16×16 cellules, ou 32×32 cellules.
Le robot ne doit pas faire plus de 250 millimètres de large et de long (il n’y a pas de hauteur limite).

### Half-size Micromouse

Une version de micromouse appelée Half-Size Micromouse est introduite lors du 30e All Japan Micromouse Competition en 2009$^,$. Au lieu d'un labyrinthe 16×16, la compétition Half-Size utilise un labyrinthe 32×32. Les dimensions des cellules et des parois sont réduites de moitié, ce qui représente un nouveau défi.
Il y a eu des compétitions de cette version en Europe, en Hongrie en 2015 et au Royaume-Uni en 2018.

## Technologie
### Résolution de labyrinthe

Les robots utilisés dans les compétitions font appel aux éléments fondamentaux de la navigation robotique, notamment la cartographie, la planification et la localisation. De plus, ils optimisent leur parcours dans le labyrinthe à l’aide de divers algorithmes de recherche. Les algorithmes de recherche courants utilisent des variantes de la méthode de remplissage par diffusion de Bellman, de l'algorithme de Dijkstra, de l'algorithme A*, parmi divers algorithmes de parcours de graphe et de parcours d'arbre.

### Performances

Les robots peuvent courir à plus de trois mètres par seconde, selon la conception du labyrinthe. Certains des meilleurs constructeurs de microsouris sont Yusuke Kato, Ng Beng Kiat et Fumitaka Nakashima. Le record du monde actuel de 3,921 secondes est détenu par Ng Beng Kiat.
Les performances se sont considérablement améliorées ces dernières années. À partir de 2015, les robots gagnants courent avec une accélération et un freinage avant bien supérieurs à 10 m/s$^2$. Des virages avec une accélération centripète pouvant atteindre 2 g sont possibles. Les microsouris font partie des robots autonomes les plus performants.
Plus récemment, les robots sont équipés d'un aspirateur pour créer un vide partiel sous la souris pendant sa course$^,$$^,$. L'appui supplémentaire disponible a permis une énorme amélioration des performances. Comparés à un robot sans aspirateur, les robots les plus récents seront probablement capables d'atteindre des accélérations centripètes de 6g ou plus. Les accélérations en ligne droite peuvent facilement dépasser 2,5g.