Résolution d’un labyrinthe avec un robot Lego MindStorm

Mini Projet de Robotique mené au cours de la 4ème année au département informatique à Polytech’Tours (2012-2013) par :

Fabien BUDA fabien.buda@etu.univ-tours.fr
Alexandre LEFILLASTRE alexandre.lefillastre@etu.univ-tours.fr

Le but du projet est de concevoir et construire un robot mobile sur la base du système Légo MindStorm. Ce robot embarque un capteur ultra sonore. La seconde partie du projet consiste à implémenter une stratégie de résolution d’un labyrinthe.

L’objectif du projet était de permettre à un robot posé dans un labyrinthe, sans aucune information sur ce dernier, de trouver la sortie.

Si le labyrinthe ne comporte pas de sortie, le robot explore la totalité du labyrinthe avant de revenir à sa position de départ, dans le cas où le labyrinthe comporte une sortie (matérialisée par une surface rouge disposée au sol), le robot s’arrêtera sur la case en question.

Le type de robot nous a été imposé, cependant les autres aspects, tels que la forme du robot construit, le mode de déplacement, et le langage de programmation utilisé étaient laissés à notre choix. Notre choix, sur le langage de programmation utilisé pour notre robot, s’est porté leJOS, Java pour la plateforme NXT.

Le robot que nous avons construit est une version légèrement modifiée d’un des modèles de base indiqué dans le manuel de la boite Lego. Le modèle de base indiquait comment obtenir la structure du robot, mais ne comportait aucun capteur. Nous l’avons donc modifié pour pouvoir accrocher les capteurs dont nous avions besoin.

[…]
Parcours en profondeur

Pour parcourir le labyrinthe, nous utilisons le classique parcours en profondeur qui est adapté au cheminement d’un robot dans un labyrinthe : un parcours en largeur obligerait le robot à faire des aller-retours incessants pour explorer, alors que le parcours en profondeur permet d’explorer complètement une branche du labyrinthe avant de faire demi-tour pour retourner au dernier point visité qui possède des voisins non-explorés.

L’implémentation que nous avons faite explore les cases voisines dans un ordre arbitraire prédéfini (on privilégie les voisins du Nord, puis ceux du Sud, puis ceux de l’Ouest, et les voisins de l’Est sont explorés en dernier), mais pourrait être modifiée pour privilégier les déplacements en ligne droite. Cela aurait cependant pour effet de rendre le code moins lisible et de réduire sa maintenabilité.

[…]

En conclusion, ce projet de résolution d’un labyrinthe nous a tout d’abord permis de nous initier à la robotique, ce que nous n’avions jamais fait auparavant. De plus, la plateforme Lego NXT est un réel plaisir à utiliser et à programmer : elle propose différents types de capteurs ainsi que de nombreux langages de programmation. Les possibilités sont immenses.

Pour ce projet, nous avons donc eu le choix des technologies employées. Nous avons choisi des capteurs ultra sonores pour gérer les obstacles mais aussi un capteur de couleur pour détecter la sortie. Au départ, nos professeurs encadrants ont souhaité l’utilisation du langage C. Malheureusement, ce langage n’était pas adapté. Après discussion, la technologie Java fut employée. Nous avons réellement apprécié cette réelle autonomie.
Nous avons implémenté l’algorithme de parcours en profondeur pour pouvoir résoudre tout type de labyrinthe. Nous avons aussi géré les déplacements du robot en fonction de sa direction ainsi que l’utilisation des capteurs.

Télécharger le rapport

Retrouvez dans un prochain billet la vidéo du robot en pratique entrain de résoudre le labyrinthe.

 

Laisser un commentaire