Rubik's Cube Machine auf FAC-Basis
Vor nicht allzu langer Zeit haben wir zusammen mit Wilbert Swinkels die Arbeit an einer Maschine beendet, die den Zauberwürfel sammelt. Sie schrieb über uns auf der offiziellen Raspberry Pi - Blog und wir erhielten viele begeisterte Kritiken. Trotzdem blieb das Projekt im russischen Segment des Netzwerks irgendwie unbemerkt. Deshalb habe ich beschlossen, dieses Versäumnis zu korrigieren, indem ich hier eine übersetzte und erweiterte Version des ursprünglichen Beitrags veröffentlichte .Unter dem Schnitt werden wir (hauptsächlich) über den Software-Teil dieser Maschine sprechen, der mechanische Teil kann auf der offiziellen Seite des Projekts gelesen werden (ja, wir wissen, dass es eine kleine "alte Schule" ist)TL; DR
Für die Ungeduldigen ein paar Links:Einführung
Alles begann damit, dass ich im Mai dieses Jahres versehentlich Wilbert Swinkels getroffen habe. Ich war einfach schockiert, als ich seine Kreationen sah : Jeder dieser Mechanismen, von klein bis groß, kann sicher als Kunstwerk bezeichnet werden. Und je genauer Sie sich ihr Gerät ansehen, desto mehr beeindruckt Sie ihre Schönheit.Natürlich, wenn Wilbert mich eingeladen , ihn mit dem Zauberwürfel Montagemaschine zu helfen, zögerte ich keine Sekunde lang, zumal bis zu diesem Zeitpunkt hatte ich schon entdeckt eine Leidenschaft für farbige Würfel. Zu diesem Zeitpunkt hatte er bereits mehr als 4 (!) Jahre an der Maschine gearbeitet, aber der Software-Teil musste noch geschrieben werden.Ich hatte keine Erfahrung mit der Programmierung für Raspberry Pi und Arduino, aber im Großen und Ganzen schien mir die Aufgabe ziemlich einfach zu sein. Natürlich habe ich mich geirrt :)Hardware
Die Maschine selbst besteht aus einem modularen FAC-System . Dies ist so etwas wie ein sowjetischer Designer, aber geschaffen, um ernsthafte und komplexe Mechanismen zu prototypisieren. In der zweiten Hälfte des letzten Jahrhunderts wurde es in den Labors von Philips und anderen Unternehmen und Universitäten sehr aktiv eingesetzt.Als ich Wilbert traf, hatte er bereits zweimal versucht, das Auto wiederzubeleben. Beide Male haben Studenten der Universität Amsterdam den Fall aufgegriffen und leider beide Male nach mehreren erfolglosen Versuchen das Interesse an dem Projekt verloren. Einer von ihnen verteidigte sogar ein Bachelor-Diplom zu diesem Thema, obwohl die Maschine den Würfel nicht einsammeln konnte (heben Sie Ihre Hand zu denen, die sich hier wiedererkennen).Mikrocontroller
Zunächst haben wir uns für den Raspberry Pi anstelle des Arduino entschieden. Dies ist hauptsächlich auf die Tatsache zurückzuführen, dass „intelligente“ Algorithmen zum Lösen des Rubik's Cube eine erhebliche Menge an Speicher und Prozessorleistung erfordern. In früheren Versuchen wurde ein primitiver dreischichtiger Algorithmus verwendet , diesmal haben wir uns jedoch für den Kotsemba-Algorithmus entschieden . Außerdem wollte ich nicht wirklich alles in C schreiben (obwohl ich es teilweise musste).
In der Standardversion des Raspberry Pi hatten wir nicht genügend Stifte, um alle verfügbaren Motoren anzuschließen, und bestellten daher das Development Kit . Übrigens rate ich dringend: nicht nur mehr Stifte, sondern sie sind meiner Meinung nach logischer voneinander getrennt. Darüber hinaus verfügt diese Karte über zwei Anschlüsse für die Kamera anstelle von einem.Die erste Version des Scanners
Zum Lesen der Erstkonfiguration des Cubes wurde ein Scan-Gerät benötigt. Die Idee ist sehr einfach: Wir beleuchten wiederum die Oberfläche des Würfels mit drei LEDs: rot, grün und blau. Jedes Mal messen wir das reflektierte Licht mit einem lichtempfindlichen Widerstand. Theoretisch sollten wir RGB-Werte erhalten, mit denen die Farbe des Quadrats erkannt werden kann. Von früheren Programmierern haben wir noch Proof-of-Concept-Code für Arduino, der anscheinend sogar unter bestimmten Bedingungen funktioniert hat.Das erste Problem, auf das wir stießen, war eine Spannungsfehlanpassung. Wie Sie wissen, beträgt die logische Einheit an den Arduino-Pins 5 V, während der Raspberry Pi 3,3 V beträgt. Glücklicherweise arbeiteten die von uns verwendeten Schrittmotortreibersteuerungen trotz Änderung der Impulsamplitude weiter.Es stellte sich als viel kritischer heraus, dass der Raspberry Pi keine analogen Eingänge hat. Aus diesem Grund kann die Himbeere die Spannung am Fotowiderstand nicht einfach messen und ablesen. Dies ist wahrscheinlich für diejenigen offensichtlich, die mindestens einmal darauf gestoßen sind, aber zuerst habe ich nicht einmal darüber nachgedacht. Bei der Suche im Internet nach einer Lösung sind wir auf diesen Artikel gestoßen. Kurz gesagt, wir fügen der Schaltung einen Kondensator hinzu und messen die Zeit, während der er von Null auf eine logische Einheit geladen wird (wir können dies mithilfe eines digitalen Pins erkennen). Die Ladezeit ist proportional zum Widerstand des Fotowiderstands, sodass wir die Lichtmenge beurteilen können.
Dieser Ansatz ist nicht nur furchtbar unzuverlässig (es ist undankbar, sich Zeit in einem Python Python-Skript unter Linux mit einer Reihe von Hintergrundprozessen zu nehmen), sondern es ist auch unmöglich, zu lange zu dauern. Um zufällige Abweichungen in den Messwerten auszugleichen, mussten wir mehrmals lesen, Ausreißer entfernen und die verbleibenden Werte mitteln. Wir haben es jedoch trotzdem geschafft, diesen Scanner zum Laufen zu bringen:Die zweite (endgültige) Version des Scanners
Der Kondensatorscanner funktionierte ziemlich gut, war aber sehr langsam. Das Scannen des gesamten Zauberwürfels dauerte ungefähr zwei Minuten, und als der Scan abgeschlossen war, hatte der Betrachter jegliches Interesse verloren. Aus diesem Grund haben wir uns entschlossen, zum Arduino zurückzukehren und einen kleinen Arduino Mini speziell für die Steuerung des Scanners gekauft.
Es erwies sich als unglaublich einfach, Arduino mit dem Raspberry Pi anzufreunden : zwei Drähte, ein Spannungswandler zwischen ihnen und voila - wir haben eine serielle Schnittstelle. Und wenn Sie ein einfaches Min- Protokoll anschrauben , ist das Programmieren dieses Geschäfts ein Vergnügen.Ich habe die gesamte Scannersteuerlogik auf das Arduino übertragen. Die Scangeschwindigkeit hat erheblich zugenommen. Dank der analogen Eingänge können wir die Spannung direkt von den Fotowiderständen ablesen, und diese Werte sind sehr genau. Da der Arduino direkt am Scanner montiert ist, benötigen wir außerdem viel weniger Kabel vom Scanner zum Raspberry Pi!Algorithmus erstellen
Das Zusammensetzen des Zauberwürfels aus mathematischer Sicht ist eine ziemlich mühsame Aufgabe . Natürlich geht es darum, die optimale Lösung zu finden, und nicht um "einige". Ich war überrascht, als ich herausfand, dass die Anzahl Gottes (die genaue Untergrenze für die Anzahl der Bewegungen, die zum Lösen eines beliebigen Würfels erforderlich sind) erst 2010 gefunden wurde .In diesem Projekt wollten wir die Gesamtzeit reduzieren, die für die Berechnung der Lösung und das Zusammensetzen erforderlich ist. Daher kam weder ein einfacher dreischichtiger Algorithmus auf uns zu (er funktioniert schnell, liefert aber Lösungen mit einer Länge von hundert Zügen), noch ein optimaler Algorithmus (Lösungen sind kurz, aber der Renderprozess auf Raspberry Pi würde ewig dauern). Infolgedessen haben wir uns für den großartigen "Zwei-Phasen" -Algorithmus entschiedenDeutscher Mathematiker Herbert Kociemba. Er ist in der Lage, suboptimale Entscheidungen zu treffen (durchschnittlich 20 Züge), während er die angemessene Zeit einhält.Auf der Website des Autors finden Sie die Implementierung des Algorithmus in Java. Als erstes habe ich diesen Code in Python übersetzt. Es war überhaupt nicht schwierig, da der größte Teil des Programms aus mathematischen Operationen und der Aufzählung von Optionen besteht. Ich habe jedoch nicht berücksichtigt, dass der Algorithmus wirklich viele Ressourcen benötigt. Das Finden einer Lösung beim ersten Start dauerte mehr als eine Minute (!) Auf meinem Laptop.Unter PypyBei aktiviertem JIT dauerte die Lösung auf dem Laptop 1 Sekunde, auf dem Raspberry Pi jedoch noch etwa eine Minute. Nach mehreren Versuchen, die Arbeit des Python-Programms zu beschleunigen (Numpy, Multiprocessing), entschied ich mich, den Algorithmus auf C umzuschreiben. Trotzdem dauert die Lösung jetzt 1-2 Sekunden, sogar auf Raspberry.Ich habe beide Implementierungen des Algorithmus auf GitHub gepostet .Maschinensteuerung
Der nächste Schritt bestand darin, ein Programm zu schreiben, das den mechanischen Teil steuert: Bewegen Sie die Motoren unter Berücksichtigung der Übersetzungsverhältnisse und Einschränkungen des Mechanismus (z. B. können Seitenhalter nur gedreht werden, wenn sich der Boden in einer bestimmten Position befindet, da er sonst stört).
Zusätzlich zum Hauptprogramm habe ich eine interaktive Shell erstellt, die mir beim Debuggen viel Zeit gespart hat. Im Allgemeinen war dieser Teil in Bezug auf die Programmierung nicht ungewöhnlich. Um den Scan zu debuggen, habe ich die Ergebnisse als Bilder generiert.Scan- und Farberkennung
Bis zu diesem Punkt war alles interessant, aber nicht schwierig. Zwei Wochen nach Arbeitsbeginn konnte die Maschine bereits einen Würfel aus einem bestimmten Zustand sammeln. Es blieb nur zu lernen, wie man die anfängliche Konfiguration des Würfels mit einem Scanner liest. Wir hatten bereits ein "funktionierendes" Programm für Arduino, daher hatten wir keine Überraschungen erwartet. Dieser Teil des Projekts erwies sich jedoch als der schwierigste, und wir brauchten weitere zwei Monate Arbeit.Fotowiderstandsanzeigen
Wie ich oben geschrieben habe, haben wir mit einer Scannerschaltung mit Kondensatoren begonnen. Der Fehler dieses Ansatzes war schrecklich. Um brauchbare Werte zu erhalten, musste ich mehrmals Messungen durchführen und dann die Emissionen beseitigen. Danach haben wir so etwas bekommen (dies ist das Ergebnis des Scannens des zusammengesetzten Würfels in einem dunklen Raum):
Wie Sie sehen können, ist das Ergebnis alles andere als ideal. Erstens sind die Werte für dieselbe Farbe an verschiedenen Positionen unterschiedlich, da Fotowiderstände und LEDs in leicht unterschiedliche Richtungen „schauen“. Zweitens sind einige Farben im Farbraum sehr nahe beieinander, und manchmal überlappen sich die Wertebereiche (z. B. ergeben Orange und Rot manchmal den gleichen Wert). Und schließlich hängen die Messwerte stark von der Außenbeleuchtung ab.Visuell ist der Fehler des Scanners an den Kondensatoren in der folgenden Abbildung zu sehen (im Allgemeinen gibt es hier eine interaktive Version ):
Rückblickend frage ich mich, wie wir es geschafft haben, den Scan mit solchen Ergebnissen zum Laufen zu bringen, obwohl dies eine sorgfältige und schwierige Kalibrierung der fraglichen Werte erforderte wird etwas tiefer gehen.Wie gesagt, der Kondensatorscanner hat funktioniert, war aber sehr langsam. Als wir es durch ein anderes ersetzten, mit dem eingebauten Arduino, wurden die Messwerte viel „überfüllter“ (die interaktive Version ist hier ):
Kalibrierung und Clustering von Messwerten
Nachdem wir die rohen RGB-Werte von den Fotowiderständen erhalten hatten, mussten wir die Farben selbst identifizieren, um die Würfelkonfiguration dem Erstellungsalgorithmus zuzuführen. Hier wurden sofort zwei verschiedene Ansätze vorgeschlagen: die Verwendung von Farbintervallen und der Clustering-Algorithmus.Der erste Ansatz ist eine „frontale“ Lösung: Es war möglich, die Werteintervalle für jede Seite des Würfels experimentell zu bestimmen (um den Farbraum in disjunkte Bereiche zu unterteilen) und die Werte dann einfach entsprechend ihrer Zugehörigkeit zu einem bestimmten Intervall zu kombinieren. In diesem Fall sollte jede der 9 möglichen Positionen am Rand des Würfels separat betrachtet werden. Diese Methode ist sehr einfach zu programmieren, weist jedoch zwei wesentliche Nachteile auf. Erstens bindet es uns an bestimmte Farben, was bedeutet, dass wir nur einen genau definierten Zauberwürfel sammeln können. Und zweitens hängen die Intervalle möglicher Werte stark von der Außenbeleuchtung ab. Darüber hinaus haben wir festgestellt, dass je nach Umgebungslicht derselbe Messwert unterschiedlichen Farben entsprechen kann.Der zweite Ansatz erfordert eine vorläufige Kalibrierung der Werte, sodass dieselbe Farbe an allen 9 Positionen am Rand des Würfels zu denselben Ergebnissen führt. In diesem Fall können wir den Clustering-Algorithmus verwenden , um die Werte in 6 Gruppen zu kombinieren. Gleichzeitig spielt es keine Rolle, in welche Farben der Würfel gemalt wird, wenn sie nur unterschiedlich sind. Leider musste diese Methode auch wegen der Wahrscheinlichkeit von Clustering-Algorithmen "abgelehnt" werden: Sie können ein "gutes" Ergebnis liefern, garantieren jedoch nicht deren Genauigkeit.Beide Ansätze haben ihre Vor- und Nachteile. Daher haben wir etwas dazwischen verwendet:- Zunächst führen wir eine künstliche Kalibrierung der Scannerwerte durch, um die Werte zu normalisieren. Die Koeffizienten werden experimentell erhalten.
- Konvertieren Sie die resultierenden RGB-Werte in HSV
- , S ()
- , .
Selbst mit einem guten Clustering-Algorithmus schlug das Scannen häufig aufgrund von Umgebungsbedingungen fehl. Der in einem dunklen Raum kalibrierte Algorithmus konnte die Aufgabe bei Tagesbedingungen nicht bewältigen und umgekehrt. Wenn die Außenbeleuchtung sehr hell war (direktes Sonnenlicht), funktionierte der Scanner im Allgemeinen nicht mehr, da der Einfluss der LEDs kaum spürbar wurde. Wilbert hat sehr mühsam den Scanner vom Umgebungslicht isoliert. Ich musste drei Iterationen durchlaufen: jedes Mal, wenn wir dachten, dass dies ausreichen würde, und jedes Mal fanden wir eine weitere Lücke, durch die die externe Beleuchtung auf den Fotowiderstand fiel.
Fazit
Die Arbeit an diesem Projekt war unglaublich aufregend. Es ist großartig zu sehen, wie das Auto vor Ihren Augen zum Leben erweckt wird, und es ist besonders cool zu sehen, wie es funktioniert, was all Ihre Bemühungen rechtfertigt. Dies kann jedoch nicht mit dem Wissensspeicher verglichen werden, den wir dabei gewonnen haben. Ich hätte mir nicht vorstellen können, dass ich eine Reihe von Materialien zu Elektronik, Mechanik, Algebra und sogar mathematischer Statistik studieren und auf dem Weg ein Dutzend nützlicher Dienstprogramme und Bibliotheken finden müsste. Deshalb bin ich so froh, dass ich die Gelegenheit hatte, an diesem Projekt zu arbeiten.
Wie dem auch sei, dieses Auto ist nur ein Prototyp. Wir haben uns nicht das Ziel gesetzt, den Geschwindigkeitsrekord zu brechen, und sicherlich haben wir nicht das volle Potenzial der mechanischen Teile ausgeschöpft. Aber wir werden auf jeden Fall versuchen, dies in der nächsten Version der Maschine zu tun, an der wir bereits mit der Arbeit begonnen haben. Dort werden wir die Kamera zum Scannen verwenden, und das Design der Manipulatoren hat wesentliche Änderungen erfahren. Und wenn Sie Fragen, Anregungen oder Tipps haben, würde ich mich freuen, diese in den Kommentaren zu hören. Source: https://habr.com/ru/post/de384503/
All Articles