An alle, denen der Titel nichts sagt:
Es geht um einen Roboter, der einen Rubik's Cube vollautomatisch richtet.

Anreiz dafür ist u.a. ein Roboter, der es zu ziemlicher Berühmtheit geschafft hat, aber einie Reihe Eigenschaften hat, die mir nicht gefallen:

- er ist nicht aus fischertechnik
- er braucht einen manipulierten Würfel
- er verwendet einen geklauten Algorithmus

Ich hab deshalb das etwas zu ehrgeizige Ziel, sowas aus ft hinzubekommen.

Einen ersten Versuch könnt ihr in diesem Video sehen:
http://www.ftcommunity.de/forum/ftcs_grinder2_divx.avi
(am besten mit rechtsklick-speichern unter runterladen, die Datei ist über 6MB groß)

Das einlesen der Farben und der eigentliche Algorithmus fehlen noch, da muss ich mir erst ausführlich überlegen, wie ich das genau mache. Wenn ihr Ideen dazu habt, wäre ich dankbar.

Was bereits funktioniert: Das Modell wird in dem Video autonom vom Robo-Interface gesteuert, ohne Kabel.
Das RoboPro-Programm kann absolute Zugfolgen nach dem Motto "obere scheibe um 180°drehen, untere scheibe um 180° drehen" bereits in Drehbewegungen umsetzen - da ich diesen Prototyp so gebaut habe, dass die zu drehende Scheibe immer unten liegen muss, muss das Programm umrechnen.
Außerdem wird schon mitgerechnet, wie die Farbverteilung nach dem drehen ist, wenn die Farben vorher bekannt waren.

wenn ich das richtig verstanden habe, dann muß die Farbverteilung nur ein einziges mal aufgenommen werden. Danach verfolgt der Rechner ja die Drehungen und kennt die Farbverteilung. Ich weiß jetzt leider nicht, ob man alle sechs Seiten aufnehmen muß oder nur 5.

Ich mache einmal einen verwegenen Vorschlag: wenn es möglich ist, eine WebCam an den Computer anzuschließen und von einem eigenen Programm aus eine Aufnahme auszulösen und diese als Bitmap zu speichern, dann ist der größte Schritt gemacht.

Bei einer Bitmap weiß man nämlich, wo die Pixel sind. Jetzt muß man den Würfel in eine bekannte, reproduzierbare Position bringen und die Aufnahme machen. Aus der Bitmap-Datei werden jetzt 9 Pixel herausgesucht, die jeweils eine Farbseite repräsentieren. Im Pixelwert stehen die Farbanteile für Rot, Grün und Blau drin. Damit sind die Farben bekannt.

Schaut die Kamera schräg von oben auf den Würfel, dann kann die zugewandte Seite aufgenommen werden und die Oberseite. Nach drei 90-Grad-Drehungen sind fünf Seiten klar. Die sechste Seite ist leider unten die. Jetzt kommt es drauf an, ob man aus der Farbverteilung von 5 Seiten die 6. erschließen kann. Das ist was für die Theoretiker hier.

Vielleicht ist mein Vorschlag ja ein kleiner Anfang.

Bis dann
Remadus

@remadus: Ja, du hast sogar recht, es reichen 5 Seiten. Allerdings ist das kein größeres Problem, weil der Würfel ja sowieso in alle Richtungen gedreht werden kann - ich würde also die Kamera auf eine Seite (die Oberseite ) ausrichten, dann nach einer aufnahme die nächst seite nach oben drehen lassen usw.

Bilder einer Kamera ins Programm zu kriegen ist kein Problem, das dazu notwendige Wissen habe ich mir schon vor knapp zwei Jahren angeeignet.
Allerdings gibt's zwei Probleme:
1) Das Licht. Ich brauche eine gleichmäßige Beleuchtung, die recht hell ist, aber keine hellen Reflexionen erzeugt, die auf dem Kamerabild weiß werden würden. Ist's zu dunkel kann ich die Farben nicht zuverlässig unterscheiden.

2) Wie krieg ich meinen C-Kamera-"Treiber" in RoboPro rein? Eine Möglichkeit ist, auf eine "Plugin"-Schnittstelle von RoboPro zu warten. Dann geht aber der Betrieb im Downloadmodus mit Garantie nimmer.
Überhaupt würde ich gerne mal wissen, wieviel Platz mein Programm bisher auf dem Interface belegt, und was noch frei ist... wenn das schon zur Hälfte voll ist kann ichs mit dem Downloadmodus sowieso vergessen.

Alternative wäre, da über den COM-Port des Interfaces was zu drehen, weil man den ja irgendwann von RoboPro ansprechen können soll. Da wäre dann der Bastlergeist gefragt.
Dritte Möglichkeit: gar keine Kamera, sondern mit Fotowiderständen messen. Da reichen Stücker zwei, durch drehen des Würfels können dann alle Felder abgetastet werden.

fishfriend, du hattest doch mal Versuche mit LDRs und Farbe gemacht, oder?

leider kann ich Dir mangels eigener Erfahrung bei der Farberkennung keinen Tipp geben, aber ich möchte meiner Begeisterung über den bisherigen Stand Deiner Maschine Ausdruck verleihen! Die Handhabung des Würfels scheint doch schon recht gut zu funktionieren. Jedenfalls so gut, dass es sich lohnen sollte, den Ansatz weiter zu verfolgen.

der Tip von Holger geht in eine gute Richtung. Als Lichtquelle schlage ich Leuchtdioden vor, weil die ziemlich spektralrein sind, das heißt, daß sie 'saubere' Farben liefern. Nacheinander damit die Flächen beleuchten und mittels LDR oder Fototransistor den Grauwert aufnehmen. So liefert jede Farbe einen Zahlentripel, der charakteristisch sein sollte.

Das Video habe ich inzwischen auch gesehen. Beeindruckend, kann ich da nur sagen. Das Drehen und Kippen geschieht ziemlich flott. Alle Achtung.

Falls der obere Halterahmen in der Höhe verstellt werden könnte, dann wäre die Drehmechanik in der Lage, eine oder zwei Reihen zu drehen. Eventuell könnte das zwei mal kippen ersparen.

Nur mal so erwähnt.

Das wird. Das sieht jetzt schon sehr gut aus.

Bis dann
Remadus

Respekt, MarMac! Sowohl für die Konstruktion als auch für den Anspruch, das nur mit RoboPro und im autonomen Modus machen zu wollen.

Mir würde als Algorhytmus nichts anderes einfallen als ein brute force Backtracking-Algorhytmus. Ähnlich vielleicht dem alten Problem, 8 Damen so auf einem Schachbrett anzuordnen, dass keine die andere direkt schlagen kann. Erste Dame probieren. Nächste wandern lassen, bis sie von unten her nicht mehr geschlagen werden kann. Falls dies möglich ist, weiter zur nächsten - bis man bie der 8. angekommen ist, dann hat man eine Lösung. Gibt es für eine Dame keine unschlagbare Position: eine Dame zurück. Ist dies bei der 1. Dame wieder angekommen, sind wir fertig. Das ganze ist also ein rekursives Problem und kann sehr elegant auch mit einem rekursiven Algorhytmus gelöst werden.

So ein Algorhytmus ist recht einfach und führt auf einem modernen Prozessor überraschend schnell zu Lösungen. Rubic's Cube ist natürlich komplexer: Mehr Stufen müssen durchgerechnet werden. Was mir im Moment aber gar nicht einfällt, ist eine Ende-Bedingung: Wann hat es keinen Sinn mehr, den probierten Weg weiter zu verfolgen? Der möglichst frühe Abbruch ist sehr wichtig für die Gesamtperformance.

Letztlich würde ich dazu tendieren, lieber mehr Rechenzeit zu nehmen und wirklich die kürzestmögliche Zugfolge (vielleicht sogar optimiert durch Einbeziehen der Dauer der verschiedenen Vorgänge an der Maschine) zu finden. Ich würde vermuten, dass die aufgewendete Rechenzeit immer noch kleiner ist als die Zeit für die Mechanik.

Rein gefühlsmäßig würde ich persönlich den Algorhytmus erstmal mit einer konventionellen Programmiersprache entwickeln (einfach weil ich vermute, dass ich damit schneller als mit RoboPro ans Ziel käme) und erst später sehen, ob und wie man das in RoboPro gießen kann.

Gruß,
Stefan

Begeistert bin ich von der Methode, nur mit ft-Teilen Farben zu erkennen! Diese Idee muss ich nächstens mal selber ausprobieren. Ich würde dazu die alten Leuchtsteine mit den farbigen Kappen verwenden.

Gruß,
Stefan

ob sich die Farbkappen von Fischertechnik eigenen, ist schnell festgestellt. Beleuchte den Farbwürfel damit und fotografiere den Würfel mit einer Webcam, die du auf Schwarzweiß umgestellt hast.

Nimm ein Rot-, ein Grün- und ein Blaubild in Schwarzweiß auf. Wenn die sich nicht erheblich voneinander unterscheiden, dann wird es schwierig.

Sind die Farbcharakteristiken der einzelnen Farbkappen nur schwach ausgeprägt, dann ist es so ähnlich, als wollte man Farben im Nebel erkennen.

Als dann
Remadus

Werds demnächst mal probieren, danke für die Tipps!

@Stefan: Den Würfel mit dem Microcontroller des Interface zu "bruteforcen" halte ich für eher aussichtslos. Was ich aber machen könnte, wäre, das ganze halbwegs intelligent zu gestalten, d.h. z.b. erstmal nur ein "Stockwerk" mit roher Rechenleistung richten zu lassen, und danach für das zweite Stockwerk nur noch Zugfolgen zulassen, die das erste nicht weider zerstören etc. - das gibt zwar niemals eine optimale Lösung, aber müsste mit verhältnismäßig wenigen Programmbausteinen zu machen sein.
Und das ist derzeit Hauptpriorität.

Ich bin bei meinen Überlegungen zur Hardware immer wieder bei mindestens zwei, im 90°-Winkel zueinander angeordneten, Zangen gelandet. Die dritte, wie beim Lego-Cube-Solver, ist nicht unbedingt notwendig, auch wenn einige Züge (verdrehen der mittleren Ebene - kommt schon ab und an vor) dadurch vereinfacht werden.
Hmpf - schon Wochen ohne ft zugebracht. Mußte sogar heute am Samstag arbeiten... Grummel.

Das Video vom normalen 3x3x3er gibt's übrigens noch:
http://www.ftcommunity.de/forum/wuerfel.avi

Ich hab da weniger als 2 minuten gebraucht seh ich grad... die ersten 10 sekunden so sind wildes verdrehen, nach der kurzen Pause dann gehts los.

Natürlich wär's ne Möglichkeit, diesen von mir verwendeten Algorithmus auch dem Programm beizubringen, allerdings ist der mit so ca. 150 Drehungen (grobe Schätzung, wer auf dem Video mitzählen will, gerne!) nicht gerade der effizienteste - soweit ich weiß gehts theoretisch mit weniger als 30.

Mit "bruteforcen" wirds allerdings nichts, ich habe berechnet, dass ich mit meiner bisherigen Implementierung nur max. 5000 virtuelle Drehoperationen/sekunde schaffen würde, womit man in einer Minute gerade mal alle Kombinationen für 6 aufeinanderfolgende Drehungen berechnen könnte - das reicht nichtmal für die ersten 4 Kantenwürfel.

Edit:
Ich meine, daß es mal ein JF-Projekt gab, in dem ein Cube-Solver mit einer Art Roboter gelöst wurde. Dieses Projekt ist schon ewig alt, ich muß mal bei Gelegenheit surfen - da gabs einiges zu sehen.

Gruß Thomas Bild

fischertechnik forum

© 2000 Snitz Communications