1. Introduction

Toute personne ayant une fois eu accès à un Rubik’s cube a déjà joué avec, tournant les faces pour voir le résultat, puis enfin a eu le courage de le mélanger dans l’espoir d’ensuite reconstituer toutes les faces. Si vous êtes une de ces personnes-là, vous avez sûrement réussi à reconstruire une des six faces du cube, et vous vous êtes dit : « chouette, ce n’était pas si difficile que ça, essayons de faire le reste… ». Hé bien le problème est que construire une face n’est pas si compliqué, le plus difficile, c’est de faire de même pour les cinq autres faces du cube sans détruire ce que vous aviez fait pour la première face. Voici où certaines personnes, peut-être après quelques heures de frustration devant ce petit puzzle qui vous semblait si simple, sont arrivés à la conclusion que c’était impossible, sûrement dû à l’énervement. Je suis une de ces personnes, mais un an après ma première rencontre avec ce cube, j’ai décidé d’y dédier un peu de temps, et à la suite de quelques recherches sur internet (et une bonne heure de suivre attentivement un tutoriel en ligne), j’ai réussi à résoudre mon Rubik’s cube pour la première fois.

Plus tard, je me suis procuré une boite du LEGO Mindstorm NXT 2.0. Après avoir construit tous les robots possibles et programmé quelques suites d’opérations basiques dans l’environnement de développement Lego NXT, je me suis demandé ce que je pouvais faire de plus avec ce kit de pièces Lego et ces moteurs. C’est un robot, donc il devrait savoir résoudre un Rubik’s cube, n’est-ce-pas ? Sur le site de LEGO Mindstorm, j’ai trouvé un dossier de construction ainsi qu’un code à faire exécuter au robot qui le ferait résoudre le Rubik’s cube. J’ai donc construit le robot, et fait exécuter le code… Comment vous dire que ça ne marchait pas très bien, et j’ai de nouveau abandonné l’idée.

Aujourd’hui, je résous un Rubik’s cube en environ une minute, ce qui est loin d’être un record du monde (3.47 secondes… oui je sais, c’est absolument incroyable), mais j’en suis assez fier. En parcourant une fois le web, je suis tombé sur une vidéo d’un robot qui résolvait le Rubik’s cube en seulement 0.637 secondes, et cela a revigoré mes envies de construire un robot pouvant résoudre un Rubik’s cube, que je construisais et programmait moi-même, d’où l’idée de ce projet informatique.

La limitation principale serait la bonne luminosité dans la pièce lors de l’exécution du programme. En effet, le code fait prendre une image à la caméra en format RGB, puis calcule la couleur de chaque pièce grâce à une moyenne arithmétique de la quantité de rouge, vert et bleu pour chaque pixel. En faible luminosité, les différences entre les couleurs seraient diminuées, ce qui pourrait induire à des erreurs d’analyse de la couleur de la pièce. Une autre limitation serait la précision du moteur mobilisant le bras, qui est imprécis et qui doit être recalibré à chaque nouvelle utilisation.

Les enjeux principaux seraient de créer un robot commandé par un Raspberry Pi, ainsi qu'un algorithme de résolution du Rubik's cube. Cet algorithme serait découpé en plusieurs parties : programmer les moteurs du robot pour faire une certaine suite de mouvement permettant de faire tourner tous les côtés du cube, puis grâce à ceux-ci définir des suites de ces suites pour les algorithmes ; créer un programme pouvant capturer un image du cube et diviser cette image en huit pour chaque sticker, puis analyser les huit images pour savoir les couleurs de chaque sticker.
L'objectif final serait d'obtenir un algorithme complet permettant de résoudre un Rubik’s cube selon la méthode de résolution CFOP (référence en annexe) qui, de lui-même, saurait résoudre le cube.

2. Matériel

2.1. Hardware

  • 1 x boîte de LEGOs LEGO Mindstorm NXT 2.0 (toute collection de LEGO Technic devrait suffir, si on sait improviser et construire un robot plus ou moins ressemblant)
  • 1 x Rasberry Pi 3 Model B V1.2
  • 1 x Adafruit DC & Stepper Motor HAT for Raspberry Pi - Mini kit
  • 1 x Alimentation 9V
  • 1 x Nema 23 Bipolar Stepper Motor 7.6V 1.8deg 1.26Nm (4fils si possible pour être compatible avec le HAT Adafruit, même si la plupart de s moteurs 6 fils sont aussi compatibles avec le HAT)
  • 1 x Makeblock mbot Ranger Ranger Motor Accessories 180 Photocoding Motor
  • 1 x câble adapté au moteur Makeblock (6 fils)
  • 1 x 5MP Raspberry Pi Camera Module Rev 1.3
  • Fil conducteur

2.2. Software

  • Système d'exploitation Raspbian installé sur le Raspberry Pi
  • Python 3
  • Librairie adafruit_motorkit
  • Librairie numpy
  • Librairie picamera

2.3. Outils

  • Matériel de soudure électronique
  • Grande collection de tournevis cruciforme et plats
  • Limes
  • Cutter
  • Pinces

3. Méthode

3.1. Stratégie de résolution du Rubik’s cube

Pour résoudre le cube, nous allons utiliser la méthode de résolution CFOP, qui se décompose en quelques étapes clés :

  1. Création d’une croix blanche, qui s’aligne avec les couleurs du milieu des faces adjacentes.
  2. Insertion des coins avec un sticker blanc dans les places respective dans la première couche du cube
  3. Insertion des pièces du bord dans la deuxième couche grâce à un algorithme
  4. Résolution de la dernière couche du cube en deux parties : OLL (orientation of the last layer) et PLL (permutation of the last layer) avec des algorithmes

Bien sûr, pour un être humain, cette méthode est très demandant en termes de mémorisation, dû aux nombreux algorithmes à mémoriser, mais un ordinateur n’a pas ce problème. Pour un tutoriel complet, voir le site : https://jperm.net/3x3/cfop

Il faut noter que le système de coordonnées utilisé dans le code est celui de des axes Ox, Oy et Oz définis par : leur origine mutuelle étant le centre du cube, l’axe x passe par l’avant du cube (la face verte qui est en direction du bras), l’axe y passe par la face orange du cube (droit par rapport au bras) et l’axe z passe par la face jaune (le haut du cube).

3.2. Hardware

La première étape dans la réalisation de ce projet est la construction du robot qui va nous permettre de passer du code au réel, en pouvant interagir avec le Rubik’s cube. Il y a plusieurs parties au robot que l’on peut différencier :

  1. Construction de la plateforme tournante sur le moteur pas à pas. Le principal problème rencontré ici était comment attacher la plateforme à l’axe tournant du moteur, car on n’utilise pas d’adaptateur (il est possible d’en utiliser un d’ailleurs). La solution trouvée était de créer une encoche dans un des trous d’une pièce LEGO Technic comme le montre la figure 3.2.1 grâce à un lime, ce qui nous permet donc de faire tourner la plateforme avec le moteur pas à pas.

IMG_20210202_110334.jpg, fév. 2021

Figure 3.2.1. Axe du moteur pas à pas avec adaptateur modifié

  1. Construction de la base. Ici faite avec des roues pour éviter tout glissement (d’une table entraînant à une chute par exemple) et isoler du sol pour éviter tout court-circuit exceptionnel.
  1. Construction du bras ainsi que son support. Plusieurs problèmes peuvent être rencontrés dans cette étape : il faut rendre le bras assez long pour qu’il puisse retourner le cube et revenir en arrière pour le permettre de ne pas empêcher le cube de pivoter avec la plateforme. De plus, le moteur qui est censé mobiliser le bras n’est pas assez puissant pour exercer le torque nécessaire à faire avancer et reculer le bras, il faut donc faire une rétrogradation et passer à une roue dentée de plus grand rayon et avec plus de dents, nous permettant ainsi d’exercer le torque nécessaire.

Enfin, il faut modifier le câble Makeblock pour pouvoir le relier au HAT adafruit (2 ports disponibles pour 6 fils). Le moteur Makeblock a six fils dont les fonctions sont de : faire tourner le moteur en avant ou en arrière, calculer la direction et l’intensité de la rotation, servir de mise à terre et servir d’entrée de courant. Pour ce robot, nous aurons seulement besoin des fils faisant tourner le moteur dans les deux sens. Ceux-ci correspondent au outputs M+ et M- sur le petit circuit intégré dans le moteur accessible en enlevant 3 vis. Lorsqu’on aura trouvé les deux fils qui correspondent aux bornes « + » et « - » du moteur, coupons l’autre bout du câble et découpons 3 millimètres du caoutchouc entourant le fil en cuivre.

Figure 3.2.2 Moteur Makeblock permettant de mobiliser le bras

  1. Construction du support pour le module caméra pour le Raspberry Pi. Utilisation extrêmement esthétique du ruban adhésif d’électricien pour fixer la caméra en place.
  1. Assemblage. Cette partie est celle où l’on connecte tous les câbles au HAT adafruit et au Raspberry Pi (il y a une petite fente pour laisser passer le câble de la caméra). Branchons le moteur pas à pas et le moteur Makeblock au HAT. Prenons les câbles du moteur pas à pas et insérons les dans les trous M1.1, M1.2, on saute le port du milieu, M2.1 et M2.2 dans l’ordre Rouge – Bleu – Vert – Noir. Viser les ports pour bien fixer les câbles en place. Le moteur Makeblock se connecte de manière similaire au ports M3, avec la borne « + » du moteur dans le port de gauche et la borne « - » dans celui de droite. Pour connecter l’alimentation, identifier la borne positive et la borne négative et les connecter dans le port « + » et « - » respectivement.

IMG_20210202_110904.jpg, fév. 2021

Figure 3.2.3 Câblage du HAT adafruit

Figure 3.2.4 Montage final

3.3. Software

Maintenant que notre robot est construit, nous allons pouvoir commencer à le programmer. Pour ceci, commençons par installer les librairies que nous allons utiliser dans notre code.

3.3.1. Préparatifs

Vérifions tout d’abord que le protocole de communication I2C (inter-intergrated circuit) est activé sur notre Raspberry Pi. Pour faire ceci, allons dans le terminal et exécutons la commande :

    sudo raspi-config

Ceci ouvrira une nouvelle fenêtre, il s’agit du panneau de configuration de notre Raspberry Pi. Avec les flèches de notre clavier, allons sous :

   5 - Interfacing Options

Puis sur :

   A7 I2C - Enable/Disable automatic loading of I2C kernel module

Sélectionnons et activons I2C. Enfin, utilisons la commande :

   sudo reboot

Pour redémarrer votre Raspberry Pi avec le module I2C activé. Lorsque ceci est fait, installons également les librairies que notre code utilisera :

   sudo update
   sudo pip3 install adafruit-circuitpython-motorkit
   sudo apt-get install python3-numpy
   sudo apt-get install python-picamera python3-picamera

La première ligne est simplement la commande qui met à jour le Raspberry Pi. Nous avons donc installé toutes les librairies nécessaires à programmer notre robot. Procédons à la programmation.

3.3.2. Programmation

3.3.2.1. Caméra

Importons deux librairies dans notre code :

   from picamera import PiCamera
   import numpy as np
   cam = PiCamera()

Et définissons la caméra par cam = PiCamera()

La programmation de la caméra se sépare en deux fonctions principales.

La première permet de capturer une photo sous format RGB et de la stocker dans une matrice 3-dimensionelle (en utilisant la librairie numpy qui est spécialement créée pour manipuler des matrices) qui exprime la quantité de la couleur rouge, vert et bleu dans chaque pixel de l’image. Ensuite, elle subdivise cette matrice en sous-matrices restreintes qui correspondent aux pixels dans l’image représentant chaque sticker différent dans l’image.

La deuxième fonction permet de calculer la moyenne arithmétique de la quantité de rouge, vert et bleu de chaque pixel dans l’image, puis compare la moyenne de rouge, vert et bleu et détermine la couleur de l’objet capturé en photo en fonction de quelle moyenne est la plus grande. Ceci permet de savoir si l’objet est rouge, vert ou bleu, mais pas les trois autres couleurs présentes sur les faces du Rubik’s cube. Pour résoudre ce problème, construisons une petite suite de conditions et hop :

   def object_color(mean_array):
       if mean_arraynp.argmax(mean_array) <= 7.0 and np.argmax(mean_array) < 5 and mean_array1 < mean_array0:
           object_color = 'White'
       elif np.argmax(mean_array) == 0:
           if mean_array1 >= 0:
               object_color = 'Yellow'
           elif mean_array2 <= mean_array1 < 0:
               object_color = 'Orange'
           elif mean_array1 <= mean_array2:
               object_color = 'Red'
       elif np.argmax(mean_array) == 1:
           object_color = 'Green'
       elif np.argmax(mean_array) == 2:
           object_color = 'Blue'

Où mean_array est la moyenne arithmétique pour tous les pixels dans l'image des valeurs de rouge, vert et bleu par pixel respectif.

Maintenant le code peut analyser notre image et déterminer de quelle couleur elle est (rouge, verte, bleue, orange, jaune ou blanche). Notons ici que la caméra doit tout d’abord être calibrée sur un fond blanc pour calculer la pollution de couleur due à une luminosité possiblement légèrement teintée.

3.3.2.2. Mouvements du Robot

Grâce à la librairie adafruit_motorkit et adafruit_motor, d’où l’on importe les suivant :

   import time
   import board
   from adafruit_motor import stepper
   from adafruit_motorkit import MotorKit
   kit = MotorKit(i2c=board.I2C())

on peut donc programmer nos moteurs à faire certains mouvements, comme par exemple :

   def cube_flip():  # function used to flip the cube once using the arm
       kit.motor3.throttle = 1.0  # pushing and flipping the cube
       sleep(0.40)
       kit.motor3.throttle = -1.0  # returning the arm to it's original place
       sleep(0.32) 
       kit.motor3.throttle = 0  # immobilising the arm

et

   def cube_rotation_clockwise():  # 90° clockwise rotation of the platform
       for i in range(50):
           kit.stepper1.onestep(direction=stepper.FORWARD, style=stepper.SINGLE)
           sleep(0.01)

Qui correspondent à la fonction qui fait se retourner le cube et la fonction qui font faire une rotation de 90° dans le sens horaire à la plateforme. Ces deux fonctions assez basiques nous permettent, en les combinant, de créer des chaînes de mouvement qui tournent une face du cube spécifique, parmi U (up), F (front), R (right), L (left), D (down) et B (back). Après avoir défini chaque suite de mouvements ci-dessus, on peut de nouveau les combiner pour créer des algorithmes qui vont ensuite nous permettre de résoudre le cube.

3.3.2.3. Algorithme de résolution

En utilisant les codes d'analyse des couleurs de la face du cube et le code contenant tous les algorithmes, on peut assez aisément créer une suite d'actions à faire accomplir au robot, qui alterne entre scanner la face pour trouver une pièce, puis la positionne grâce à un algorithme, puis scanne le cube pour trouver une deuxième pièce, etc. Grâce à cet algorithme, pour chaque phase de résolution selon la méthode CFOP, on va pouvoir créer faire exécuter une suite de commandes qui nous amènera à la phase suivante, jusqu’à la résolution complète du cube.

Je ne suis pas arrivé à ce stade, car mon code de détection de couleur ne fonctionnait pas pour des images décomposées, et ne pouvait donc pas reconnaître les couleurs de chaque sticker. De plus, les moteurs étaient tellement imprécis que malgré mes tentative de rectifier cette imprécision, après plusieurs mouvements, la plateforme n'est plus directement en face du bras, ce qui engendrait des erreurs comme ne pas pouvoir retourner le cube.

3. Résultats

Les objectifs fixés n’ont évidemment pas tous étés remplis, le robot est fonctionnel, et peut interagir avec le cube comme souhaité, mais la reconnaissance de couleur n’arrive pas à analyser les images réduites, ce qui l’empêche de dire la couleur de l’image. Sans cette partie essentielle à la résolution du Rubik’s cube, on ne peut pas aller bien loin ! Or, certains points ont quand mêmes étés accomplis. Le code qui analyse la couleur d’une image complète est fonctionnel. De plus, le robot marche parfaitement en ce qui concerne la mobilité et l’exécution des algorithmes demandés.

4. Discussion

La réalisation de ce projet est venue avec beaucoup de difficultés et de problème à surmonter, des solutions à improviser. Un des plus gros problèmes survenus est la question de comment exprimer une pièce du Rubik’s cube lorsque celui-ci est mélangé ? En observant le cube, j’ai pu établir une liste de composantes qui nous permettaient de noter et sauvegarder les infos du cube sous forme de variables. Ces composantes sont :

  • Le type de pièce (coin ou bord)
  • La position de la pièce (dépend du type de pièce)
  • L’identité de la pièce (sa position en état résolue)
  • L’orientation de la pièce (2 ou trois possibilités, dépendant du type de pièces).

Grâce à ses données, que le défini lors de l’analyse des couleurs de la caméra, on peut programmer les algorithmes qui nous permettront ensuite de résoudre le Rubik’s cube en entier.

Un autre problème qui est apparue lors de la programmation du robot était que à cause d’une erreur de fabrication ou des dommages subit avant la procuration du moteur, le moteur pas à pas Nema 23 était défectueux et faisait une rotation complète en 202 exactement au lieu de 200. Ceci créait une imprécision dans les rotations de la plateforme, ce qui engendrait, après un grand nombre de ces rotations, un désaxage vraiment significatif, empêchant tout le reste du robot de fonctionner correctement. La solution à ce problème est d’introduire une variable « n » qui oscillait entre 0 et 1 à chaque rotation, en en faisant tourner le stepper moteur de 50+n = 50 pas une fois, puis celle d’après 50 + n = 51, puis 50, et ainsi de suite, on pouvait plus ou moins corriger cette imprécision et préserver une rotation de 90° pour une rotation. Or, dès que l'on s'engageait dans des suites plus longues de mouvements, la plateforme se décentrait, ce qui créait des problème quant aux interactions entre le bras et le cube (le cube était en diagonal et soit tombait de la plateforme, soit ne pouvait plus être maintenu en place pour tourner une seule face par exemple).

Encore un problème rencontré était dû à une imprécision dans le moteur contrôlant le bras. En effet, cette imprécision le faisait parfois ne pas revenir à sa position initiale, et il cachait donc le sticker de la pièce en-haut à gauche de la caméra, ce qui empêchait l’analyse de la couleur de cette pièce-là. Pour résoudre ce problème-ci, il a fallu faire revenir le bras légèrement plus loin qu’avant et le problème est résolu. La gestion du temps fut la plus grande épreuve à surmonter, ce que je n’ai pas réussi à faire. J’ai très mal calculé le temps qu’il me faudrait pour réaliser ce projet. En effet, j’avais estimé que le travail me prendrait 20 bonnes heures… En réalité cela serait plutôt de au-dessus de 100 heures de travail, en incluant les recherches (20 heures), la construction (25 heures), la programmation (25 heures) et le débugging (30 heures). Malgré le résultat décevant du projet, j’ai appris beaucoup de choses : la tout première est de savoir exactement ce que je souhaite faire et comment y parvenir, comment diviser le problème en parties et réaliser chacune des parties. J’ai également acquis des connaissances dans les librairies python de numpy, picamera, openCV (même si je ne l’utilise pas dans mon code final) et Pillow (aussi non-utilisé dans la version finale).

5. Conclusion

Pour conclure, notons premièrement que le but principal de ce projet, c’est-à-dire de construire un robot permettant de résoudre un Rubik’s cube a été partiellement atteint. En effet, le robot fonctionne bien si on lui fait exécuter une suite d'algorithme manuellement (ce n'étais pas le but, mais c'est déjà ça...). Il n’est pas encore autonome, et n’arriverait pas à résoudre un cube seul, car il ne peut pas analyser les couleurs de chaque sticker (faute de temps, je n’ai pas pu programmer le logiciel permettant de reconnaître la couleur de chaque pièce, même si j’y sui presque). Ainsi, ce projet est loin d’être un échec complet, je dirai même qu’il m’a amené plus que ce que je m’y attendais.

En général, ce projet à clairement démontré ma naïveté lorsqu'il s'agit de s'engager dans une nouvelle chose. En effet, j'ai fortement sous-estimé la quantité de travail que cela représentait, ainsi que la complexité physique des interactions entre le robot et le cube (une petite erreur mène inévitablement à un échec du programme.

Les améliorations possibles à mon projet seraient de trouver un autre moyen de reconnaître les couleurs des pièces du Rubik’s cube, comme un scanner RGB, au lieu d’une caméra. Il serait ainsi plus facile de reconnaître les couleurs de près, en ajoutant par exemple un moteur qui vient positionner le capteur couleur à quelques millimètres du cube, et faire tourner en scannant, puis reconnaître les couleurs individuellement. Une autre possibilité serait de scanner les six faces du cube une seule fois au début du programme, puis de créer une représentation 3D du cube dans autre code, et grâce à celui-ci savoir exactement quel algorithme utiliser. Les complications liées à cette méthode seraient de faire changer la représentation 3D du cube en temps réel en fonction des algorithmes. Enfin, on pourrait remplacer le moteur pas à pas par un système d'encoche et un moteur plus basique, qui ferait tourner la plateforme jusqu'à ce que l'encoche touche le bouton (encoches espacées de 90°). Ce système aurait de plus grandes chances de fonctionner malgré des petites erreurs dans les mouvements.

Références

  • Installation et codage des moteurs : https://learn.adafruit.com/adafruit-dc-and-stepper-motor-hat-for-raspberry-pi
  • Installation et codage de la caméra : https://picamera.readthedocs.io/en/release-1.12/install.html
  • Utilisation de la librairie numpy : https://numpy.org/
  • Création d'un logiciel de détection de couleur avec la caméra : https://makersportal.com/blog/2019/4/21/image-processing-using-raspberry-pi-and-python