Schnellster Labyrinthalgorithmus für Roboter

Ich plane, einen vorgefertigten Roboter zu programmieren, um ein Labyrinth so schnell wie möglich zu lösen. Der Roboter verfügt über Vorwärtshindernissensoren (keine Seitensensoren) und einen 3-Achsen-Beschleunigungsmesser. Ich plane, den Wandverfolgungsalgorithmus zu verwenden. Ist das der schnellstmögliche Algorithmus? Da es keine Seitensensoren gibt, muss sich der Roboter kontinuierlich drehen, um zu prüfen, ob sich an der Seite eine Wand befindet. Gibt es also eine clevere Möglichkeit, den Beschleunigungsmesser und die Sensoren zu verwenden?

Sie können nicht viel über das Lösen eines Labyrinths sagen, es sei denn, Sie dürfen es zuerst erkunden oder das Labyrinth vorher kennen. Andernfalls ist es einfach, ein Labyrinth zu erstellen, dessen Lösung mithilfe der Wandverfolgung beliebig lange dauert, das jedoch eine einfache Lösung bietet. Siehe folgendes Beispiel.

In diesem Fall ist es im Durchschnitt schneller , nur zufällig Runden auszuwählen. Vielleicht ist dies ein schwieriges Problem, das etwas mehr Nachdenken erfordert. In einigen Kontexten ist ein iterativ vertiefender Ansatz nicht schlecht. Beginnen Sie dort mit Ihrer Recherche und kommen Sie zurück, wenn Sie spezielle Fragen haben.

Der Wandverfolgungsalgorithmus profitiert mehr von Sensoren auf einer Seite. Da Sie der Seite folgen, bis Sie eine Lücke finden, biegen Sie in diese Lücke ein. Sie können dann den Beschleunigungsmesser verwenden, um eine Beule zu erkennen, wenn Sie gegen die Wand vor Ihnen stoßen. Sie sind sich jedoch nicht sicher, wie Sie feststellen können, dass Sie sich außerhalb des Labyrinths befinden (falls Sie dies tun müssen). Nur eine Idee...

Für einen bestimmten Algorithmus (der das Labyrinth vorher nicht kennt) gibt es ein bestimmtes Labyrinth, in dem der Argorithmus beim ersten Versuch nicht den schnellsten Weg wählt.

Viele Algorithmen machen den Trick, dass sie zuerst alle Wege im Labyrinth zurücklegen und den Weg aufzeichnen, dann den optimalen Weg finden und beim zweiten Versuch nur auf dem schnellsten Weg zum Ziel fahren.

Wenn bekannt ist, dass Ihr Labyrinth ein Baum ist (keine Schleifen), dessen Bewegungsmöglichkeiten für den Roboter nur breit sind, aber nicht zu breit, und wenn er genau die richtigen Winkel aufweist (was viele einfache Labyrinthe sind), können Sie einige Tricks anwenden Löse es schneller beim zweiten Mal:

• Seitensensoren würden viel helfen, so dass Sie nicht gezwungen wären, sich ständig umzudrehen

• Wenn dies nicht möglich ist und Sie einen Entfernungssensor (normalerweise Ultraschall) anstelle eines Hindernissensors (möglicherweise einen einfachen Stoßfänger) haben, können Sie ihn auf einen schmalen Strahl beschränken und nur ein wenig winken und sehen, ob sich der Abstand konstant ändert, oder ob es ein Loch gibt (was seitlich bedeutet) und wie weit das Loch ist. Dann können Sie schnell in der Nähe der Kreuzung laufen und dann nur langsam und mit voller Reichweite drehen, um genau den Seitenweg zu finden.

• Wenn Sie den Sensor auch auf einer "tankartigen" rotierenden Basis haben, können Sie ruhig fahren und nur den Sensosr drehen, der schneller ist als der rotierende ganze Roboter

• Wenn die Wege eng sind, können Sie Stoßstangen an den Seiten anbringen und nur an den Seiten stoßen, um sie zu fühlen, anstatt sie an Ort und Stelle zu drehen, um sie richtig zu erfassen. Bonus, wenn Sie fehlerhafte Antennen haben können, um beide Seiten gleichzeitig zu fühlen (aber sie müssen flexibel sein, um nicht zu brechen, und Sie benötigen mindestens 3 Zustandssensoren für sie (2 Bit) - keine Berührung - leichte Berührung - harte Berührung : keine Berührung bedeutet seitlich, leichte Berührung bedeutet, dass Sie sich gerade in einer geraden Reihe in der Mitte befinden, harte Berührung bedeutet Hindernis oder zu viel zur Seite drehen)

Wie auch immer:

• Sie gehen Ihren gewohnten Weg "rechte Hand an der Wand", bis Sie das Ziel finden, und beginnen dann mit dem gleichen Stil, sodass Sie das erste Mal durch das ganze Labyrinth reisen.

• Sie markieren jede Kreuzung auf dem Weg und zählen sie, um eine Art Karte zu erstellen (Bonus, wenn Sie die Entfernung messen). Wenn Sie dann auf dem Rückweg die Karte in Erinnerung behalten und wenn Sie zu einer Kreuzung zurückkehren, wissen Sie, dass Sie kann den ersten Weg überspringen, den Sie dort gewählt haben, da er das Ziel nicht erreicht und zurückkehrt. Fahren Sie fort, bis Sie das Ziel gefunden haben und die Hälfte der Karte gelöst ist. Dann mache es umgekehrt vom Ende und löse die andere Hälfte der Karte. Sie sollten das gleiche Ergebnis erzielen - wenn nicht, haben Sie einen Fehler gemacht oder das Labyrinth ist kein Baum.

• Beim zweiten Versuch wissen Sie, welche Seitenwege Sie überspringen können und welchen Weg Sie an welcher Kreuzung wählen müssen, damit Sie den kürzeren Weg zum Ziel gehen.

• Wenn Sie auch die Entfernungen markiert haben, wissen Sie, wie weit die nächste Kurve sein sollte, und Sie können fast die gesamte Strecke sehr schnell fahren, bevor Sie präzise (und wahrscheinlich langsamer) nach der Kurve suchen müssen.

• Wenn Ihre Roboterkonstruktion dies zulässt, können Sie die Wände sogar ignorieren und sich von ihnen leicht in die Mitte des Weges zurückstoßen lassen, sodass Sie eine viel weniger empfindliche Navigation benötigen, damit Sie noch schneller laufen können.

• Das Gleiche gilt für Kurven, in denen Sie an der Wand kleben und die ganze Zeit ein wenig drücken können, wenn Sie glauben, dass Sie sich der Kurve nähern, bis Sie hineingehen, sodass Sie wissen, dass Sie an der Reihe sind. Wieder viel einfachere Navigation, viel weniger auszuwertende Daten, so viel schnellere Geschwindigkeit möglich.

• Wenn Sie besonders ultraschnell sein möchten, zeichnen Sie diesen Lauf ebenfalls auf und verwenden ihn für den dritten Lauf, bei dem Sie wissen, wie lange Sie vor dem Abbiegen laufen müssen entfielen.