KI-Projekt WS20/21 Puzzle@Home

Donnerstag, Januar 21, 2021

Schiebepuzzle@Home: zuhause konstruiert, online diskutiert und vorgeführt

Das Schiebepuzzle ist ein bekanntes Beispiel zur Aktionsplanung. Das Puzzle besteht aus einem 3x3-Feld in dem 8 Plättchen in einer Stellung angeordnet sind. Die Plättchen können horizontal oder vertikal in Richtung auf die freie Stelle bewegt werden. Die Aufgabe besteht darin, in der Ausgangsstellung die Plättchen sukzessive solange zu verschieben, bis die Zielstellung erreicht wird. In jeder Stellung gibt es mindestens zwei und höchstens vier Schiebemöglichkeiten. Wenn wir von durchschnittlich drei Möglichkeiten ausgehen, so ergibt dies einen Suchbaum der Verzweigungsrate 3. Bei einem typischen Lösungsweg der Länge 20 ergibt dies eine Gesamtmenge von 3^20, also etwa 3,5 Milliarden Knoten in der untersten Ebene des Suchbaumes. Dies ist mit reiner Tiefensuche oder Breitensuche nicht mehr zu bewältigen - oder vielleicht doch? PS: Sie haben 7000 Byte Speicher für Ihre Datenstrukturen.

Aufgabe

Konstruieren Sie mit dem AKSEN-Board ein autonomes System (Roboter), das eine 3x3-Version des Schiebepuzzles repräsentiert und dieses lösen kann. Das Puzzle sollte dabei stets gut sichtbar sein, so dass alle Zwischenstellungen des Lösungsvorgangs gut wahrgenommen werden können. Eine Anzeige auf dem LCD-Display reicht nicht aus. Die Stellung soll mechanisch visualisiert werden, idealerweise mit tatsächlichen Puzzleteilen.

Und natürlich muss ein Robotersystem mit Stromversorgung, Motoren, Getrieben, geeigneten Sensoren und das Puzzle gebaut werden. Falls die Probleme zu groß werden (und groß werden sie auf jeden Fall), besteht die Fallback-Möglichkeit beim Abschlusswettbewerb mit einem manuellen Plan zu starten.

Wettbewerb online am 14. Januar 2021

Es traten 5 Roboter zum Wettbewerb an: Tilting Eggs, QWRTY, IR-06, OptoBotV2.2 und Kubus. Das Finale IR-06 (37 Punkte) gegen Kubus (31 Punkte) gewann fehlerlos IR-06.

Projektdokumentation Jan Philipp Seeland