Veranschaulichung mathematischer Konzepte am Beispiel der Bewegungssteuerung mit externer Kontrolle

Wir möchten modellieren, wie sich eine Murmel in einem Labyrinth bewegt. Dazu gehen wir davon aus, dass das Labyrinth in quadratische Felder aufgeteilt ist, die gerade der Größe der Murmel entsprechen. Mittels eines Zugs können wir die Murmel zwischen den Feldern bewegen, indem wir das Labyrinth in eine Richtung kippen, entweder nach links, rechts, oben oder unten. Dadurch bewegt sich die Murmel so weit wie möglich in die gewählte Richtung, bis sie gegen den Rand stößt. Dies lässt sich in folgender Abbildung ausprobieren, indem man der Abbildung erst Fokus gibt und dann die Pfeiltasten auf der Tastatur zum Kippen benutzt.

Wenngleich die Beschreibung mit Murmeln und Labyrinth gewollt spielerisch ist, basiert die Idee auf mathematischen Modellen aus der Robotik zur Beschreibung von Partikelschwärmen, schön illustriert in diesem Video.

Relationen und Funktionen

Um das Verhalten der Murmel mathematisch zu analysieren, definieren wir Relationen zwischen den Feldern des Labyrinths. Für zwei Felder \(p\) und \(q\) aus einer Menge \(M\) von Feldern eines Labyrinths soll \(p \rightarrow_M q\) bedeuten, dass die Murmel sich mittels eines Zuges von \(p\) zu \(q\) bewegen kann. Wir sagen dann auch, dass \(q\) von \(p\) aus in einem Zug erreichbar ist. Gibt es eine (möglicherweise leere) Folge von Zügen, welche die Murmel von \(p\) zu \(q\) bewegt, schreiben wir \(p \rightarrow_M^* q\) und sagen, dass \(q\) von \(p\) aus erreichbar ist. Für das vorherige Beispiel lassen sich die Relationen in folgender Abbildung darstellen. Ein einfacher Linksklick auf ein Feld markiert alle Felder in rot, die von dort aus in einem Zug erreichbar sind; ein Doppelklick markiert alle von dort aus (in beliebig vielen Zügen) erreichbaren Felder.

Umgekehrt kann man sich fragen, von welchen Feldern aus ein gegebenes Feld (in einem Zug) erreichbar ist. Darüber geben die Umkehrrelationen von \(\rightarrow_M\) und \(\rightarrow_M^*\) Aufschluss. In folgendem Bild markiert ein Linksklick auf ein Feld alle Felder, von denen es in einem Zug aus erreichbar ist; ein Doppelklick erweitert die Relation wieder auf beliebig lange Folgen von Zügen.

Noch präziser können wir das Verhalten der Murmel beschreiben, indem wir jeden Zug als eine Abbildung zwischen Mengen von Feldern betrachten. Für eine Menge \(M\) von Feldern sei \(\ldir_M: M \to M\) so definiert, dass \(p \mapsto q\), \(p, q \in M\), genau dann gilt, wenn sich eine auf \(p\) platzierte Murmel beim Kippen nach links zu \(q\) bewegt. Analog definieren wir \(\rdir_M\), \(\udir_M\) und \(\ddir_M\) für die Richtungen rechts, oben („up“) und unten („down“). Wenn die Menge aus dem Kontext klar ist, lassen wir Indizes weg.

Betrachtet man die Funktionen auf allen Feldern eines Labyrinths, sind sie im Allgemeinen nicht injektiv. Dies sieht man leicht an folgendem Beispiel, bei dem überall Murmeln platziert sind, die sich so bewegen, als wären sie allein in dem Labyrinth. Jeder mögliche Zug sorgt dafür, dass sich mindestens zwei Murmeln zum selben Feld bewegen.

Auf Teilmengen von Feldern kann eine Folge von Zügen durchaus injektiv sein. Sei in folgendem Beispiel \(M\) die Menge aller Felder und \(M' \subseteq M\) die Menge der Felder, auf denen zu Beginn Murmeln platziert sind. Dann ist die Verkettung \(\udir \circ \ldir \circ \ddir \circ \rdir: M' \to M'\) (von Zügen nach rechts, unten, links und oben) eine Bijektion mit Umkehrabbildung \(\ldir \circ \udir \circ \rdir \circ \ddir: M' \to M'\). Wenn etwa in dem Beispiel erst nach rechts, unten, links und oben gekippt wird, gefolgt von unten, rechts, oben und links, sieht man, dass man wieder im ursprünglichen Zustand landet.

Schaltalgebra

Wir können Murmeln und Labyrinthe benutzen, um damit Logikgatter darzustellen und prinzipiell zu komplexen Schaltungen zu kombinieren, siehe dieses Video. Hierzu wird wiederholt nach unten, links, oben, rechts und unten gekippt (\(\ddir \circ \rdir \circ \udir \circ \ldir \circ \ddir\) als Verkettung von Zügen, wobei bei mehreren Wiederholungen ein \(\ddir\) weggelassen werden kann, weil wiederholtes Kippen in dieselbe Richtung keinen Unterschied macht). Dies funktioniert ähnlich wie der Takt einer elektronischen Schaltung. Das folgende Beispiel stellt logische Negation dar. Oben sind, von links nach rechts, ein Eingang \(A\) und der negierte Eingang \(\overline{A}\). Am unteren Ende wird die Reihenfolge getauscht, somit wird der Wahrheitswert negiert.

Spannender sind Konstruktionen mit mehr Ein- und Ausgängen und mehreren Murmeln, die sich bei Kollisionen gegenseitig blockieren. Das folgende Gatter kombiniert mehrere logische Funktionen. Die Eingänge sind, von links nach rechts, \(A\), \(\overline{A}\), \(B\) und \(\overline{B}\). Als Ausgänge ergeben sich, ebenfalls von links nach rechts, \(A \wedge B\), \(A \vee B\), \(\overline{A \vee B}\) und \(\overline{A \wedge B}\). Im Beispiel links sind zu Beginn \(A\) und \(B\) gesetzt, wodurch sich die Murmeln in einem Zyklus zu den Ausgängen \(A \wedge B\) und \(A \vee B\) bewegen. Rechts sind hingegen \(A\) und \(\overline{B}\) zu Anfang gesetzt und am Ende \(A \vee B\) und \(\overline{A \wedge B}\).

Matrizen

Stellen wir uns vor, es ist eine einzige Murmel in einem Labyrinth, aber wir wissen nicht, auf welchem Feld. Unser Ziel ist es, eine Verkettung von Zügen zu finden, sodass die Murmel danach nur an einer bestimmten Stelle sein kann, unabhängig davon, wo sie zu Anfang war. Durch Ausprobieren sieht man leicht, dass dies in folgendem einfachen Beispiel möglich ist, z.B. durch Kippen nach unten, links und oben.

Wir brauchen im Folgenden eine feste Reihenfolge der Felder, also nummerieren wir sie durch.

Unser Wissen darüber, wo die Murmel sich gerade befinden könnte, stellen wir als Spaltenvektor mit Einträgen aus \(\{0,1\}\) dar, wobei eine \(1\) in der \(i\)-ten Komponente bedeutet, dass die Murmel sich womöglich auf dem Feld \(p_i\) befindet. Der Zustand zu Beginn in unserem Beispiel ist somit \[ S = \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{pmatrix}. \]

Die Funktionen \(\ldir, \rdir, \udir\) und \(\ddir\) lassen sich nun als \((7 \times 7)\)-Matrizen über \(\{0,1\}\) darstellen, indem wir in Zeile \(i\) genau dann in Spalte \(j\) eine \(1\) setzen, wenn die zugehörige Funktion \(p_i\) auf \(p_j\) abbildet. Für das Beispiel ergeben sich folgende Matrizen. \[ Z_{\ldir} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0\\ \end{pmatrix} Z_{\rdir} = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{pmatrix} \] \[ Z_{\udir} = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0 & 0\\ \end{pmatrix} Z_{\ddir} = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{pmatrix} \]

Wenn wir statt zu addieren das Maximum zweier Zahlen nehmen, sowie das Minimum anstatt zu multiplizieren, wird die Verkettung von Zügen damit zur Multiplikation von Matrizen. (Streng genommen rechnen wir damit nicht wie gewöhnlich mit Matrizen über einem Körper, sondern über einem Halbring, aber das soll uns nicht weiter stören.) Wir müssen allerdings aufpassen, dass sich in der von uns gewählten (und üblicherweise benutzten) Ausrichtung die Reihenfolge der Verkettung und die der Multiplikation der Matrizen unterscheiden. Die Verkettung \(\ldir \circ \ddir\) entspricht z.B. dem Produkt \(Z_{\ddir} Z_{\ldir}\). Somit suchen wir nach einer Matrix, die den Vektor \(S\) auf einen Vektor mit einer \(1\) in genau einer Komponente abbildet. Im Fall dieser speziellen Matrizen sind das genau die Matrizen vom Rang \(1\).

Mit der oben bereits gefundenen Lösung \(\udir \circ \ldir \circ \ddir\) ergeben sich zum Beispiel \[ Z_{\ddir} Z_{\ldir} Z_{\udir} = \begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0\\ \end{pmatrix} \] und \[ Z_{\ddir} Z_{\ldir} Z_{\udir} S = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}. \]

Das Beispiel war natürlich absichtlich klein und einfach gewählt, damit die Matrizen übersichtlich bleiben. Als kleine Herausforderung kann folgendes Beispiel dienen, in dem ein paar Schritte mehr nötig sind, um auf ein einziges verbliebenes Feld zu kommen.

Gelegenheit zum Ausprobieren

In der letzten Abbildung können eigene Labyrinthe gebaut werden, indem mittels Rechtsklick Felder freigelegt oder blockiert werden. Ein Linksklick auf nicht blockierte Felder platziert (oder entfernt) Murmeln. Über die Pfeiltasten auf der Tastatur können die Murmeln wieder bewegt werden.