💘 🐺 👨‍👨‍👦‍👦 Rubik's Cube Machine basé sur FAC 🙌 🖕🏼 🤘

Il n'y a pas si longtemps, avec Wilbert Swinkels, nous avons terminé de travailler sur une machine qui collecte le Rubik's Cube. Ils ont écrit sur nous sur le blog officiel de Raspberry Pi et nous avons reçu beaucoup de critiques élogieuses. Néanmoins, dans le segment russe du réseau, le projet est en quelque sorte passé inaperçu. J'ai donc décidé de corriger cette omission en publiant ici une version traduite et augmentée de l'article d' origine .

Sous la coupe, on va parler (principalement) de la partie logicielle de cette machine, la partie mécanique peut être lue sur la page officielle du projet (oui, on sait que c'est un peu "old school")

TL; DR

Pour les impatients, quelques liens:

introduction

Tout a commencé avec le fait qu'en mai de cette année, j'ai rencontré accidentellement Wilbert Swinkels. J'ai été tout simplement choqué en voyant ses créations : chacun de ces mécanismes, du plus petit au plus grand, peut en toute sécurité être qualifié d'oeuvre d'art. Et plus vous regardez leur appareil de près, plus vous êtes frappé par leur beauté.

Bien sûr, lorsque Wilbert m'a invité à l'aider avec la machine d'assemblage de Rubik's Cube, je n'ai pas hésité une seconde, d'autant plus qu'à cette époque j'avais déjà découvert une passion pour les cubes colorés. A cette époque, il travaillait déjà sur la machine depuis plus de 4 (!) Ans, mais la partie logicielle était encore à écrire.

Je n'avais aucune expérience de la programmation pour Raspberry Pi et Arduino, mais dans l'ensemble, la tâche m'a semblé assez simple. Bien sûr, j'avais tort :)

Matériel

La machine elle-même est construite à l'aide d'un système FAC modulaire . C'est quelque chose comme un designer soviétique, mais créé pour prototyper des mécanismes sérieux et complexes. Dans la seconde moitié du siècle dernier, il a été très activement utilisé dans les laboratoires de Philips et d'autres entreprises et universités.

Au moment où j'ai rencontré Wilbert, il avait déjà essayé à deux reprises de «faire revivre» la voiture. Les deux fois, des étudiants de l'Université d'Amsterdam ont repris l'affaire et, malheureusement, les deux fois, ils se sont désintéressés du projet après plusieurs tentatives infructueuses. L’un d’eux a même défendu un diplôme de licence sur ce sujet, malgré le fait que la machine n’ait pas pu récupérer le cube (levez la main à ceux qui se reconnaissent ici).

Microcontrôleur

Tout d'abord, nous avons décidé d'utiliser le Raspberry Pi au lieu de l'Arduino. Cela est principalement dû au fait que les algorithmes «intelligents» pour résoudre le Rubik's Cube nécessitent une quantité importante de mémoire et de puissance de processeur. Dans les tentatives précédentes, un algorithme primitif à trois couches a été utilisé , mais cette fois, nous avons décidé d'utiliser l'algorithme de Kotsemba . De plus, je ne voulais pas vraiment tout écrire en do (bien que je devais en partie le faire).

Dans la version standard du Raspberry Pi, nous n'avions pas suffisamment de broches pour connecter tous les moteurs disponibles, nous avons donc commandé le kit de développement . Au fait, je conseille fortement: non seulement plus de broches, mais elles sont, à mon avis, plus logiques à part. De plus, cette carte a deux connecteurs pour la caméra au lieu d'un.

La première version du scanner

Pour lire la configuration initiale du cube, un périphérique de numérisation était nécessaire. L'idée est très simple: à son tour, nous éclairons la surface du cube avec trois LED: rouge, verte et bleue. Chaque fois, nous mesurons la lumière réfléchie à l'aide d'une résistance photosensible. Théoriquement, nous devrions obtenir des valeurs RVB qui peuvent être utilisées pour reconnaître la couleur du carré. D'après les programmeurs précédents, nous avons encore du code de preuve de concept pour Arduino, qui, semble-t-il, fonctionnait même sous certaines conditions.

Le premier problème que nous avons rencontré était un décalage de tension. Comme vous le savez, l'unité logique sur les broches Arduino est de 5 V, tandis que le Raspberry Pi est de 3,3 V. Heureusement, les contrôleurs de pilote de moteur pas à pas que nous avons utilisés ont continué de fonctionner malgré la modification de l'amplitude des impulsions.

Il s'est avéré beaucoup plus critique que le Raspberry Pi ne dispose pas d'entrées analogiques. Pour cette raison, la framboise ne peut pas simplement prendre et lire la tension à la photorésistance. C'est probablement évident pour ceux qui ont au moins rencontré cela, mais au début je n'y ai même pas pensé. À la recherche d'une solution sur le net, nous sommes tombés sur cet article. En bref, nous ajoutons un condensateur au circuit et mesurons le temps pendant lequel il sera chargé de zéro à une unité logique (nous pouvons le détecter à l'aide d'une broche numérique). Le temps de charge sera proportionnel à la résistance de la photorésistance, nous pouvons donc juger de la quantité de lumière.

Cette approche est non seulement terriblement peu fiable (prendre du temps dans un script Python Python sur Linux avec un tas de processus d'arrière-plan est une chose ingrate), mais elle est également impossible à long. Afin de lisser les écarts aléatoires dans les lectures, nous avons dû lire plusieurs fois, nous débarrasser des valeurs aberrantes et faire la moyenne des valeurs restantes. Cependant, nous avons quand même réussi à faire fonctionner ce scanner:

La deuxième version (finale) du scanner

Le scanner à condensateur fonctionnait assez bien, mais il était très lent. Il a fallu environ deux minutes pour analyser l'intégralité du Rubik's Cube, et au moment où l'analyse a été terminée, le spectateur avait perdu tout intérêt. Par conséquent, nous avons décidé de revenir à l'Arduino et avons acheté un petit Arduino Mini spécifiquement pour contrôler le scanner.

Se faire des amis Arduino avec le Raspberry Pi s'est avéré incroyablement simple: deux fils, un convertisseur de tension entre eux et le tour est joué - nous avons une interface série. Et si vous vissez un protocole Min simple , la programmation de cette entreprise est un plaisir.

J'ai transféré toute la logique de contrôle du scanner vers l'Arduino. La vitesse de numérisation a considérablement augmenté. Grâce aux entrées analogiques, nous pouvons lire la tension directement à partir des photorésistances, et ces valeurs sont très précises. De plus, comme l'Arduino est monté directement sur le scanner, nous avons besoin de beaucoup moins de fils du scanner au Raspberry Pi!

Algorithme de construction

Assembler le Rubik's Cube d'un point de vue mathématique est une tâche assez laborieuse . Bien sûr, nous parlons de trouver la solution optimale, et non "certains". J'ai été surpris quand j'ai découvert que le nombre de Dieu (la limite inférieure exacte du nombre de mouvements nécessaires pour résoudre un cube arbitraire) n'a été trouvé qu'en 2010 .

Dans ce projet, nous voulions réduire le temps total nécessaire au calcul de la solution et à l'assemblage, donc ni un simple algorithme à trois couches ne nous a approchés (il fonctionne rapidement, mais donne des solutions d'une centaine de coups), ni un algorithme optimal (les solutions sont courtes, mais le processus de rendu sur Raspberry Pi prendrait une éternité). En conséquence, nous nous sommes installés sur le magnifique algorithme "en deux phases"Le mathématicien allemand Herbert Kociemba. Il est capable de prendre des décisions sous-optimales (en moyenne 20 coups), tout en respectant un délai raisonnable.

Sur le site de l'auteur, vous trouverez l'implémentation de l'algorithme en Java. La première chose que j'ai faite a été de traduire ce code en Python. Ce n'était pas du tout difficile, car la plupart des programmes sont des opérations mathématiques et une énumération des options. Cependant, je n'ai pas pris en compte que l'algorithme nécessite vraiment beaucoup de ressources. Trouver une solution au premier lancement a pris plus d'une minute (!) Sur mon ordinateur portable.

Sous pypyavec JIT activé, la solution a pris 1 seconde sur l'ordinateur portable, mais sur le Raspberry Pi, cela a pris environ une minute. Après plusieurs tentatives pour accélérer le travail du programme Python (numpy, multiprocessing), j'ai décidé de réécrire l'algorithme en C. Néanmoins, la solution prend maintenant 1-2 secondes, même en Raspberry.

J'ai posté les deux implémentations de l'algorithme sur GitHub .

Commande de machine

L'étape suivante consistait à écrire un programme qui contrôlerait la partie mécanique: déplacer les moteurs, en tenant compte des rapports d'engrenage et des limitations du mécanisme (par exemple, les supports latéraux ne peuvent être tournés que lorsque le fond est dans une certaine position, sinon cela interfère).

En plus du programme principal, j'ai créé un shell interactif qui m'a fait gagner beaucoup de temps lors du débogage. En général, cette partie n'était pas inhabituelle en termes de programmation. Pour déboguer l'analyse, j'ai généré les résultats sous forme d'images.

Numérisation et reconnaissance des couleurs

Jusque-là, tout était intéressant, mais pas difficile. Deux semaines après le début des travaux, la machine pouvait déjà collecter un cube d'un état donné. Il ne restait plus qu'à apprendre à lire la configuration initiale du cube à l'aide d'un scanner. Nous avions déjà un programme «fonctionnel» pour Arduino, donc nous ne nous attendions pas à des surprises. Cependant, cette partie du projet s'est avérée être la plus difficile, et cela nous a pris encore 2 mois de travail.

Indications de la photorésistance

Comme je l'ai écrit ci-dessus, nous avons commencé avec un circuit de scanner avec des condensateurs. L'erreur de cette approche était horrible, donc pour obtenir des valeurs utilisables, j'ai dû prendre des mesures plusieurs fois, puis me débarrasser des émissions. Après cela, nous avons obtenu quelque chose comme ça (c'est le résultat de la numérisation du cube assemblé dans une pièce sombre):

Comme vous pouvez le voir, le résultat est loin d'être idéal. Premièrement, les valeurs pour la même couleur sont différentes à différentes positions, car les photorésistances et les LED «regardent» dans des directions légèrement différentes. Deuxièmement, certaines couleurs sont très proches les unes des autres dans l'espace colorimétrique, et parfois les plages de valeurs se chevauchent (par exemple, l'orange et le rouge donnent parfois la même valeur). Et enfin, les lectures sont très dépendantes de l'éclairage extérieur.

Visuellement, l'erreur du scanner sur les condensateurs peut être vue dans le diagramme suivant (en général, il y a une version interactive ici ):

Avec le recul, je me demande comment nous avons réussi à faire fonctionner le scan avec de tels résultats, bien que cela ait nécessité un étalonnage soigneux et délicat des valeurs en question ira un peu plus bas.

Comme je l'ai dit, le scanner à condensateur a fonctionné, mais il a été très lent. Lorsque nous l'avons remplacé par un autre, avec l'Arduino intégré, les lectures sont devenues beaucoup plus «encombrées» (la version interactive est ici ):

Étalonnage et regroupement des lectures

Maintenant que nous avions les lectures RGB brutes des photorésistances, nous devions identifier les couleurs nous-mêmes afin d'alimenter la configuration du cube à l'algorithme de construction. Deux approches différentes ont été immédiatement suggérées ici: l'utilisation d'intervalles de couleurs et l'algorithme de clustering.

La première approche est une solution «frontale»: il a été possible de déterminer expérimentalement les intervalles de valeurs de chaque côté du cube (en fait, de diviser l'espace colorimétrique en zones disjointes), puis de combiner simplement les valeurs selon leur appartenance à un certain intervalle. Dans ce cas, chacune des 9 positions possibles sur le bord du cube doit être considérée séparément. Cette méthode est très facile à programmer, mais elle présente deux inconvénients importants. Premièrement, il nous lie à des couleurs spécifiques, ce qui signifie que nous ne pouvons collecter qu'un cube Rubik strictement défini. Et deuxièmement, les intervalles de valeurs possibles dépendent beaucoup de l'éclairage extérieur. De plus, nous avons constaté que, selon la lumière ambiante, la même lecture peut correspondre à des couleurs différentes.

La deuxième approche nécessite un étalonnage préliminaire des valeurs afin que la même couleur donne les mêmes résultats dans les 9 positions sur le bord du cube. Dans ce cas, nous pouvons utiliser l'algorithme de clustering pour combiner les valeurs en 6 groupes. En même temps, peu importe les couleurs dans lesquelles le cube est peint, si seulement elles sont différentes. Malheureusement, cette méthode a également dû être «rejetée» en raison de la nature probabiliste des algorithmes de clustering: ils peuvent produire un «bon» résultat, mais ne garantissent pas sa précision.

Les deux approches ont leurs avantages et leurs inconvénients, nous avons donc utilisé quelque chose entre les deux:

Tout d'abord, nous effectuons un étalonnage artificiel des lectures du scanner pour normaliser les valeurs. Les coefficients sont obtenus expérimentalement.
convertir les valeurs RVB résultantes en HSV
, S ()
, .

Même avec un bon algorithme de clustering, l'analyse échouait souvent en raison des conditions environnementales. L'algorithme, calibré dans une pièce sombre, ne pouvait pas faire face à la tâche dans des conditions diurnes, et vice versa. De plus, si l'éclairage extérieur était très lumineux (lumière directe du soleil), le scanner cessait généralement de fonctionner, car l'influence des LED devenait à peine perceptible. Wilbert a fait un travail très minutieux en isolant le scanner de la lumière ambiante. J'ai dû passer par 3 itérations: chaque fois nous pensions que ce serait suffisant, et chaque fois nous trouvions un autre espace à travers lequel l'éclairage externe tombait sur la photorésistance.

Conclusion

Travailler sur ce projet était incroyablement excitant. C'est tellement génial de voir la voiture prendre vie sous vos yeux, et c'est particulièrement cool de voir comment elle fonctionne, justifiant tous vos efforts. Cependant, cela ne peut pas être comparé à la réserve de connaissances que nous avons réussi à acquérir dans le processus. Je n'aurais pas pu imaginer que je devrais étudier un tas de matériaux sur l'électronique, la mécanique, l'algèbre et même les statistiques mathématiques, et en chemin pour trouver une douzaine d'utilitaires et de bibliothèques utiles. C'est pourquoi je suis si heureux d'avoir eu l'opportunité de travailler sur ce projet.

Quoi qu'il en soit, cette voiture n'est qu'un prototype. Nous ne nous sommes pas fixé pour objectif de battre le record de vitesse, et nous n'avons certainement pas réalisé tout le potentiel des pièces mécaniques. Mais nous allons certainement essayer de le faire dans la prochaine version de la machine, sur laquelle nous avons déjà commencé à travailler. Là, nous allons utiliser l'appareil photo pour la numérisation, et la conception des manipulateurs a subi des changements importants. Et bien sûr, si vous avez des questions, des suggestions ou des conseils, je serai heureux de les entendre dans les commentaires.

Rubik's Cube Machine basé sur FAC