Der Cuber ist ein Roboter, gebaut um einen verdrehten Zauberwürfel (3x3x3) lösen zu können. Dabei führt er sowohl die Berechnungen als auch die Bewegungen aus, ähnlich wie die Roboter, die in dem folgenden Video gezeigt sind: https://www.youtube.com/watch?v=qTq2V1aPAp8 Ein Zauberwürfel ist gelöst, wenn alle neun Kacheln auf jeder der 6 Seiten die gleiche Farbe haben. Vor dem Lösen wir der Würfel zufällig verdreht. Damit der Cuber erkennen kann wie die Kacheln angeordnet sind, berechnen kann wie der Würfel gelöst wird und anschließend auch verdrehen kann, verwenden wir eine Kamera, vier Hubmagneten, vier getriebemotoren, vier Greifer, einen Raspberry Pi, sowie Holz für das Gerüst des Cubers.

Der Cuber besteht im Wesentlichen aus zwei Teilen. Der Grundplatte, auf der sowohl die Kamera, der Raspberry Pi mit komplett gelöteter Schaltung, als auch die vier beinahe identisch aufgebauten orthogonal zur Grundplatte geschraubten Seitenwände. Damit diese auch immer in der gleichen Position bleiben, haben wir einen zusätzlichen Rahmen an der Oberseite angebracht, der alle vier Seitenwände verbindet. Die Seitenwände haben eine Innen- und Außenseite. Auf den Außenseiten sind jeweils ein Hubmagnet und ein Getriebemotor angeschraubt. Auf den Innenseiten sitzen die vier aus LEGO gebauten Greifarme, die durch Achsen mit den Hubmagneten verbunden sind.(2 Bilder 1. Schaltung 2. gesamter Cuber)

Bei der Bildverarbeitung haben wir auf dem Bild 9 Flächen definiert. Auf diesen Flächen wählen wir jeweils 100 zufällige Pixel und bestimmen die RGB Werte . Daraus bilden wir dann den Durchschnitt. Das machen wir mit allen Seiten des Würfels.

Berechnung der durchschnittlichen Farben. Wird für jedes der 6 Bilder einmal aufgerufen

void durchschnittliche_farbe(QImage Image){
 
    // Anzahl der Pixel
    constexpr int samples = 100;
 
    // Iteriere durch alle vorgegebenen Rechtecke
    for(int i = 0; i < 9; i++){
 
        // Initialisiere die Summe mit dem RGB Tripel (0, 0, 0)
        QVector3D color { 0, 0, 0 };
 
        // Wiederhole fuer jeden Testpixel
        for(int a = 0; a < samples; a++){
            // Wähle einen zufaelligen Pixel im rechteck. (rand() % a) gibt eine Zufallszahl zwischen 0 und a zurueck
            int x = rects[i].x() + rand() % rects[i].width();
            int y = rects[i].y() + rand() % rects[i].height();
 
            // Lese die Farbe aus dem Bild
            QColor farbe =  Image.pixelColor(x,y);
 
            // Wandle die Farbe in einen RGB-Vektor um. Nutzte dazu den Anteil, d.h. Fliesskommazahl zwischen 0 und 1
            color += QVector3D{
                    static_cast<float>(farbe.redF()),
                    static_cast<float>(farbe.greenF()),
                    static_cast<float>(farbe.blueF())};
        }
        // dividiere durch die Anzahl der Pixel, um den Durchschnitt zu erhalten,
        // Fuege das ergebnis in am Ende des Arrays scanned_colors ein
        scanned_colors.push_back(color / samples);
    }
}

Die Mittelsteine sind immer an einer festen Position und können nicht untereinander vertauscht werden. Zudem gibt es genau ein Mittelstein pro Farbe. Diese Eigenschaft machen wir uns zu Nutze und verwenden die durchschnittlichen Farben der Mittelsteine als Referenz für die anderen Steine. Dazu müssen wir zunächst den Abstand zwischen zwei Farbvektoren definiern. Dieser soll einfach nur Aussagen, wie ähnlich sich zwei Farben sind. Es hat sich durch Experimente gezeigt, dass der Code

float color_distance(QVector3D a, QVector3D b) {
	return std::abs(a.x() - b.x()) + std::abs(a.y() - b.y()) + std::abs(a.z() - b.z());
}

dafür gut funktioniert.

Wichtig ist, dass der Algorithmus im Enddefekt jeder Fläche in eine der Farbklassen einteilt, und dass jede Farbklasse mit Mittelstück zum Schluss 9 Flächen umfasst. Um dabei Möglichst gute Ergebnisse zu erziehlen, beginnen wir mit den Flächen, deren farbliche Einordnung besonders eindeutig ist. Eindeutig bedeuted, dass der Abstand zu dem best passenden Mittelstück klein ist, und der Abstand zu den anderen Farben der Mittelstücken groß ist. Dann werden die Flächen nach Eindeutigkeit sortiert und die eindeutigsten Flächen werden zuerst den Mittelstücken zugeordnet. Sobald von einer Farbklasse 9 Flächen gefunden werden, muss für die restlichen Flächen die Eindeutigkeit neu bewerted werden.

Der Code dafür sieht folgendermaßen aus

/* enthaelt die durchschnittlichen Farbwerte */
std::vector<QVector3D> scanned_colors;
 
/* gibt zurueck, wie Eindeutig eine Flaeche einem Mittelstueck zugeordnet werden kann */
float clarity_of_piece(const int piece, const std::array<int, 6> & free_slots_on_centerpiece) const {
 
	/* summe der distanzen */
	float sum = 0.;
 
	/* bester Abstand zu Mittelstueck, initialisiert mit ganz grosser zahl **/
	float best = std::numeric_limits<float>::max();
 
	/* fuer alle Mittelstuecken **/
	for (int i = 0; i < 6; i++) {
 
		/* ignoriern, falls schon neun Flaechen mit der Farbklasse identifiziert wurden */
		if (free_slots_on_centerpiece[i] < 1) {
			continue;
		}
 
		/* berechne den abstand */
		float distance = color_distance(
			scanned_colors[get_center_piece_id(i)], // get_center_piece_id gibt den Index des n-ten Mittelstuecks in scanned_colors zurueck
			scanned_colors[piece]);
 
		/* aktualisier sum und best */
		sum += distance;
		best = std::min(best, distance);
	}
 
	/* berechne Eindeutigkeit */
	float  clarity = sum - best * 8.f;
	return clarity;
}
 
/* Bewerte alle flaechen und sortiere sie, so dass die Eindeutigsten am Ende des Arrays stehen */
void rearrange_pieces(std::vector<std::pair<int, float>> & pieces_to_match, const std::array<int, 6> & free_slots_on_centerpiece) const {
	for (auto & elem: pieces_to_match) {
		/* elem.second speichert die Eindeutigkeit */
		elem.second = clarity_of_piece(elem.first, free_slots_on_centerpiece);
	}
 
	/* sortiere alle flaechen nach der in second gespeicherten Eindeutigkeit */
	std::sort(pieces_to_match.begin(), pieces_to_match.end(), [](const auto & a, const auto & b){ return a.second < b.second; });
}
 
/* rechnet die Farbklassen aus */
std::array<int, 54> detect_colors() {
	if (scanned_colors.size() != 54) {
		throw std::runtime_error("incorrect number of scanned tiles");
	}
 
	/* Ergebnis, wird spaeter beschrieben, initialisier mit -1, damit Fehler gesehen werden können */
	std::array<int, 54> result;
	result.fill(-1);
 
	/* das array pieces_to_match speichert alle Flaechen (als index) inklusive ihrer Eindeutigkeit (als float), die noch nicht zugeteilt wurden */
	std::vector<std::pair<int, float>> pieces_to_match;
 
	/* speichert wie viele Flaechen pro Farbklasse frei sind, initialisiere mit 8, da Mittelstuecke nicht zugeordnet werden muessen */
	std::array<int, 6> free_slots_on_centerpiece;
	free_slots_on_centerpiece.fill(8);
 
	/* fuer jeden Flaeche */
	for (int i = 0; i < 54; i++) {
 
		/* falls Mittelstueck */
		if (is_center_piece(i)) {
 
			/* speicher Farbklasse von Mittelstueck in result */
			result[i] = i % 9;
 
			/* fahre mit naechster Flaeche fort */
			continue;
		}
 
 
		/* nur ausgefuehr, falls kein Mittelstueck. Speichere die aktuelle Flaeche als Stueck, das noch zugeordnet werden muss */
		pieces_to_match.emplace_back(i, 0);
	}
 
	/* bewerte und sortiere Flaechen nach Eindeutigkeit */
	rearrange_pieces(pieces_to_match, free_slots_on_centerpiece);
 
	/* solange es noch Flaechen gibt, die noch zugeordnet werden muessen */
	while (pieces_to_match.size()) {
 
		/* nehme das Element mit der hoechsten Eindeutigkeit und entferne es aus dem Array */
		auto elem = pieces_to_match.back();
		pieces_to_match.pop_back();
 
		/* lese durchschnittlich Farbe zu vom Element ein */
		auto & color = scanned_colors[elem.first];
 
		/* suche bestes, freies Mittelstueck, Code sollte aus clarity_of_piece bekannt sein */
		float best = std::numeric_limits<float>::max();
		int best_id = 0;
		for (int i = 0; i < 6; i++) {
			/* ignoriere, falls Farbklasse voll */
			if (!free_slots_on_centerpiece[i]) {
				continue;
			}
 
			const auto & center_piece = scanned_colors[get_center_piece_id(i)];
			float distance = color_distance(color, center_piece);
			if (distance < best) {
				best = distance;
				best_id = i;
			}
		}
 
		/* ein freier Platz in Farbklasse weniger */
		free_slots_on_centerpiece[best_id]--;
 
		/* schreibe zugeordnete Farbklasse in result */
		result[elem.first] = best_id;
 
		/* falls Farbklasse vollgemacht wurde, muss neu bewerted werden */
		if (!free_slots_on_centerpiece[best_id]) {
			rearrange_pieces(pieces_to_match, free_slots_on_centerpiece);
		}
	}
 
	return result;
}

Ein wichitger Bestandteil des Programmes nach dem Einscannen des Würfels ist die Berechnung, welche Züge zu tun sind, damit der Würfel gelöst wird. Dafür wird ein Algorithmus namens Two-Phase Algorithmus benutzt. Der Algorithmus ist auch unter dem Namen Kociemba's Algorithmus bekannt. Da dieser Algorithmus allerdings extrem komplex und aufwändig zu implementieren ist, haben wir dafür die Bibliothek https://github.com/muodov/kociemba benutzt. Sie ist in der Programmiersprache C geschrieben und kann dadurch einfach in unseren C++ Code intergriert werden. Eine ausführliche Erklärung über die Funktionweise des Algorithmus möchten wir an der Stelle nicht bringen, sondern verweisen für den interessierten Leser auf Herbert Kociemba's Homepage http://kociemba.org/cube.htm, auf der er seinen Algorithmus ausführlich und bis in jedes Detail in einem ca. 15 Seitigen Artikel erklärt.

Die Hubmagneten werden mithilfe einer Mosfetschaltung gesteuert. Ein Problem das mit den Hubmagneten aufgetreten ist, ist dass sie einen sehr hohen Strom ziehen. Da wir vier Stück verbaut haben, kommen wir dabei Schnell an die Grenzen unserer Stromquellen. Um dies zu Umgehen, nutzen wir die Eigenschaft der Hubmagneten, dass sie eine deutlich höhere Kraft aufbringen, wenn der Kern innerhalb der Spule ist. Dies ist immer dann der Fall wenn der Greifer zu ist und damit der häufigste Fall. Da der Greifer also in dem Fall eine deutlich höhere Kraft aufbringt, kann man während der Zeit, die der Greifer zu ist, den Stromfluss mit Hilfe von Pulsweitenmodulation (PWM) reduzieren. Das bedeutet, dass man in kurzen zeitlichen Abständen den Hubmagneten an- und ausschaltet. Dadurch entsteht die Illusion, der Hubmagnet würde weniger Strom verbrauchen und dafür an Kraft einbüßen. Das dabei Kraft eingebüßt ist kein Problem, da der Hubmagnet in dieser Stellung mehr Kraft hat. Die Mechanik in dem Greifer ist außerdem so konstruiert, dass sie den Greifer in dieser Stellung so weit Unterstützt, dass er nur seine Feder überwinden muss. Eine hoher Strom ist also nur kurzfristig nötig um den Greifer zu schließen. Danach kann der Stromverbrauch mit Hilfe von PWM reduziert werden.

Um die Getriebemotoren anzusteuern, werden zwei Dual MC33926 Motor Treiber https://www.pololu.com/product/1213 von Pololu verwendet. Mithilfe eines Treibers lassen sich dabei zwei Motoren ansteuern. Ein Motor wird dabei an die Ausgänge OUT1 und OUT2 angeschlossen. Zur Kontrolle der Motoren sind von Seiten des Raspberrys nur die Pins IN1 und IN2 wichtig. Diese Ermöglichen die logische Kontrolle der Ausgänge OUT1 bzw. OUT2. Das bedeutet, dass wenn man an IN1 3V+ anschließt, wird an OUT1 mit der Eingangspannung Vin verbunden, andernfalls mit GND. Je nach dem, ob man jetzt an IN1 oder an IN2 eine Spannung anschließt, kann man den Motor vorwärts oder Rückwärts drehen lassen, da die Verpolung dann genau umgekehrt wäre. Zusätzlich erlaubt es die Platine auch, dass man an IN1 und IN2 ein PWM Signal anlegt. Dadurch kann man dann den Motor auch unterschiedlich schnell drehen lassen.

Die Motoren zu drehen reicht allerdings nicht, da wir den Greifer immer genau um 90 Grad drehen müssen. Dafür nutzen wir die am Motor angebrachten Encoder https://www.pololu.com/product/2285, welche immer eine Rückmeldung geben, wenn die Primärachse des Motors das 48 einer Drehung, d.h. einen Schritt getätigt hat. Dies geschieht durch zwei Rechteckwellen, die um eine Phase von 90 Grad verschoben sind. Diese Messen wir über zwei GPIOs am Raspberry. Die Versetzung der beiden Wellen erlaubt uns nachzuverfolgen, in welche Richtung dieser Schritt geschehen ist. Hier ein Beispiel: Wir nennen den Momentan Werte der beiden Rechteckwellen A und B. Wenn wir zum Anfang an beiden LOW messen, und kurz darauf an A HIGH messen, können wir darauf schließen, dass der Motor einen Schritt vorwärts gemacht hat. Wenn allerdings anstelle von A B HIGH ist, muss der Motor einen Schritt Rückwärts gemacht haben. Indem wir im Programm die einzelnen Schritte zusammenaddieren, können wir auf die aktuelle Rotation schließen, in dem wir mit dem Getriebeverhältnis multiplizieren. Mithilfe dieser Information können wir dann im Programm solange nachregeln, bis wir die gewünschte Position des Motors erreicht haben.

Im Großen und Ganzen haben wir alle unsere „must have“- Ziele und „nice to have“- Ziele umgesetzt. Zum einen das der Cuber den Zauberwürfel einscannen und von alleine lösen kann. Allerding haben wir das nicht in der geplanten Zeit geschafft, denn wir hatten einige Probleme. Das erste große Problem war, dass wir zu spät mit dem Bau des Cubers begonnen haben. Auch das speziell beim Verkabeln haben wir den Zeitaufwand unterschätzt. Aus diesen gründen haben wir es leider nicht geschafft rechtzeitig mit dem Projekt fertig zu werden.

In der Zukunft könnte man leistungsstärkere Motoren verwenden, um die Lösungsdauer zu verkürzen. Auch das Gerüst könnte genauer und stabiler konstruiert werde, da wir zwischenzeitlich das Problem hatten, dass sich alles verzogen hatte und der Würfel nicht mehr gegriffen werden konnte.

Code