Annuaire|Bibliothèques|Cours en ligne|Plan d'accès|Emploi|Agenda|Actualités|U tv|Contact
Fr
UMONS>Faculté des sciences>Département de Mathématique>Étudiant>Projets>Robots (2008)

Quand les mathématiciens construisent des robots...

Cette interview est parue dans le magazine Élément 01.

Si vous avez eu l'occasion de traverser le couloir du Département de mathématique entre septembre 2007 et mars 2008, vous avez surement rencontré trois étudiants de première maîtrise en sciences mathématiques (Julie De Pril, Marc Ducobu et Dany Maslowski) derrière un écran d'ordinateur ou construisant des robots. Que faisaient-ils exactement ?

Sous la direction du Professeur Troestler, ces étudiants ont partiellement mis de côté, l'espace de quelques mois, leurs cours théoriques afin de réaliser un projet concret de robotique. L'idée était simple mais non moins ambitieuse : comment créer des robots « intelligents » capable de sortir seul d'un labyrinthe ou de résoudre le Rubik's cube, ce casse-tête sur lequel nous avons tous séché au moins une fois ? Cerise sur le gâteau, ils ont eu l'occasion de présenter leur projet à des étudiants du secondaire lors de la « Journée Math Sciences » et l'ont exposé également à l'hôtel de ville de Mons. Interview des étudiants...

Q : Quand, comment et pourquoi ce projet est-il né ? R : Le projet s'insrit dans le cadre des projets intégrés que les étudiants de première maîtrise doivent réaliser. Dès le début de l'année académique, le Professeur Troestler a proposé un sujet de robotique. Pour mener à bien ce projet, il avait besoin de trois étudiants. Vu le caractère assez « fun » du projet et la bonne entente entre nous trois, nous n'avons pas hésité longtemps à nous proposer. L'envie d'apprendre de nouveaux langages et styles de programmation ainsi que mettre en pratique les connaissances mathématiques théoriques acquises durant trois années de baccalauréats2 étaient des motivations supplémentaires.

Q : Combien de temps cela vous a-t-il pris ? R : Nous n'avons pas compté. Il ne valait mieux pas d'ailleurs (rire) ! ! ! Au début, nous ne savions pas trop à quoi nous attendre, ni même où nous allions et ce que nous demanderions à terme au robot. Après un premier temps d'adaptation (bien légitime du reste), l'apprentissage des bases de la robotique nous prenait une moyenne de 8 heures de travail semaine. Ensuite, vers la fin du projet, les différents objectifs se rapprochant, nous passions quasiment la totalité de notre temp à développer les codes et construire les différents robots.

Q : Parlons des deux projets proprement dits. Comment sont construits les robots ? R : Il s'agit de Legos Mindstorms. C'est un projet de Lego basé sur une brique intelligente programmable. En plus des briques Legos traditionnelles, nous avons un processeur pour traiter nos programmes, une mémoire interne et nous pouvons utiliser différents senseurs (contact, lumière, rotation,...).

[Robot sortant d'un labyrinthe]

Q : En trois phrases, comment le projet « Labyrinthe » marche-t-il ? R : Mécaniquement parlant, le robot est composé de senseurs capables d'évaluer la distance et les nuances de gris. Lorsqu'il arrive à une intersection (représenté par un disque gris, voir la photo du labyrinthe), il détecte la présence de murs ou non et analyse les différents chemins possibles. Si une des possibilités n'a pas été suivie précédemment (le robot retient en mémoire les différentes coordonnées par lesquelles il est déjà passé et les différents choix qu'il a pris), il la suit. Sinon, il se dirige vers le carrefour (intersection avec direction accessible non explorée) le plus proche. Le labyrinthe étant inconnu à priori, il n'est pas capable de connaître son chemin à l'avance mais, à terme, il finira par explorer tous les chemins et trouver la sortie (ou constater qu'il n'y en a pas).

Q : Sur quoi se base l'algorithme ? R : En fait, il s'agit de programmation événementielle* et de programmation récursive permettant de repérer le carrefour le plus proche.

Q : Et pour le Rubik's cube ? R : Mécaniquement parlant, le robot est doté d'une pince et d'un socle rotatif capable de tourner (toujours dans le même sens) chaque face du cube. Comme il y a six faces et trois rotations possible par face, le robot a 18 possibilités qui s'offrent à lui. Après avoir introduit la configuration de départ, le robot définit les différents mouvements à effectuer afin d'arriver au cube final. Il connait donc la stratégie globale avant d'effectuer son premier mouvement.

Q : Sur quoi se base l'algorithme ? R : En deux mots, on utilise la théorie des groupes étudiée en première bac et la programmation récursive de nouveau. Un algorithme récursif nous permet de calculer les différents coups à effectuer. Bien sûr, le nombre de possibilités étant énorme (notons que le nombre de configurations de départ est connue et estimée quand même à 43 × 1018), nous ne pouvons vérifier l'ensemble. Nous devons donc faire preuve de stratégies supplémentaires. Pour cela, nous nous aidons de différents travaux déjà existants et de tables précalculées permettant d'évaluer préalablement en combien de mouvements il est possible de trouver le cube final.

Q : Vous avez parlé plusieurs fois de programmation récursive. De quoi s'agit-il ? R : Il s'agit d'une façon de programmer où la fonction s'appelle elle-même. Le principe est en quelque sorte basé sur celui des preuves par récurrence. Si je connais l'étape de base d'un problème et comment on peut passer d'une étape à la suivante, je connais l'entiereté du problème. Le meilleur moyen de comprendre est de considérer un exemple : le calcul de la factorielle n! = 1 × 2 × 3 ×…× N est un cas typique. factorielle(n): si n = 1, factorielle(n) = 1; sinon factorielle(n) = factorielle(n-1)*n;

Q : Quelles ont été les principales difficultés rencontrées ? R : Les contraintes additionnelles liées au matériel. Une fois l'algorithme implémenté, il reste encore beaucoup de problèmes techniques à résoudre. C'est un peu comme lorsque que l'on construit une maison où une fois le gros oeuvre terminé, il reste tout l'intérieur à aménager. Pour le labyrinthe, il fallait définir correctement à quel moment se produirait le freinage en fonction de la vitesse du robot, gérer la vitesse des roues au moment des virages, tenir compte du jeu dans les roues dentées (afin d'obtenir des mouvements précis),... Pour le Rubik's cube, pas mal de problèmes de gestion de mémoire liés à la taille des différentes tables utilisées était à résoudre, ainsi que des problèmes de précision dans la rotation du cube.

[Robot résolvant le Rubik's cube]

Q : Vous avez présenté votre projet lors de la « Journée Math Sciences » organisée à l'UMH le jeudi 13 mars et à l'hôtel de ville de Mons le samedi 15 et dimanche 16 mars. Que proposiez-vous exactement ? R : Après quelques mots d'explication, nous avons proposé au public de tester le robot. Ainsi, nous avons construit un labyrinthe à murs variables de quatre mètres carrés (le robot peut s'adapter à la taille des labyrinthes mais il fallait bien en fixer une). Nous tenons d'ailleurs à remercier l'équipe technique d'Emile Bachy pour leur aide matérielle. Le public avait la possibilité de créer environ 15 × 1023 labyrinthes différents et de remarquer en combien de temps le robot trouvait la sortie ou se rendait compte qu'elle était bouchée.
Pour le Rubik's cube, nous avons organisé un concours de vitesse entre les étudiants et le robot. Les étudiants sont trop modestes pour l'avouer mais nul doute que le robot gagnait la majorité du temps...

Q : Quelle a été la réaction du public ? R : Positive. Ils avaient l'air assez impressionnés que le robot puisse s'auto-gérer pour résoudre les problèmes proposés.

Q : Et la vôtre ? R : Un sentiment de fierté. C'est agréable, après de longues heures de travail et parfois de doutes, de pouvoir présenter son travail.

Q : Si c'était à refaire ? Conseilleriez-vous l'expérience à la future génération ? R : Sans aucun doute, oui. D'ailleurs, nous ne savons pas encore vraiment comment, mais cela serait chouette que le travail puisse continuer dans les années à venir avec de futurs étudiants.

C. Grumiau

P.S. Vous pouvez découvrir plus de photos sur flickr. Le code est disponible sous licence libre.

P.P.S. Vous pouvez également lire l'interview des étudiants qui ont construit un robot qui joue à Puissance 4.


* Définition des tâches que le robot doit effectuer suivant la configuration du moment (j'accélère, je freine, je tourne la tête et je prends une décision sur la prochaine destination,...)