Was ist der beste Weg, um Hindernisse für einen Serviceroboter zu navigieren und zu vermeiden?
Roboter sind mechanische und Softwaresysteme, die mit der realen Welt interagieren. Für einen Serviceroboter ist es äußerst wichtig, Ihre aktuelle Position im Weltraum, die Position des Ziels und die Fähigkeit zu verstehen, eine Route zum Ziel unter Umgehung möglicher Hindernisse zu erstellen. Wir entwickeln einen
Roboter zum Sammeln von Golfbällen auf der Driving Range . Wir haben verschiedene Optionen für den Bau einer Route in Betracht gezogen, um die beste für uns selbst zu finden. Vielleicht sind diese Informationen für jemanden interessant.
Der einfachste Weg, den Roboter dazu zu bringen, sein Ziel im zweidimensionalen Raum zu erreichen. Der Rover selbst ist hier ein kleiner Punkt, vor dem es keine Hindernisse gibt. Daher bewegt sich der Roboter in dieser Situation in einer geraden Linie und stoppt, wenn er das Ziel erreicht.
Diese Methode ist geeignet, wenn es nur einen Roboter auf der Welt gibt und das Ziel, das er erreichen muss. Mit Direct können Sie so schnell wie möglich zur endgültigen Konfiguration gelangen.
Dieser Algorithmus kann jedoch nicht angewendet werden, wenn plötzlich ein Hindernis vor dem Roboter auftritt. Wenn sich der Rover in einer geraden Linie bewegt, kann er diese nicht umgehen oder durchfahren. In diesem Zusammenhang bleibt er einfach vor einem Hindernis stehen und bewegt sich nicht weiter.
Wie komme ich um ein Hindernis herum? Der einfachste Weg, um das Problem zu lösen, ist die Verhaltensoption „Vermeidung von Hindernissen“. In der Praxis wird es durch verschiedene Algorithmen dargestellt.
Gehen Sie zum Algorithmus
Wenn das Ziel nicht erreicht wird:
- Gehen Sie auf das Ziel zu.
- Ansonsten: aufhören.
Diese Methode ist geeignet, wenn es nur einen Roboter auf der Welt gibt und das Ziel, das er erreichen muss. Mit Direct können Sie so schnell wie möglich zur endgültigen Konfiguration gelangen. Aber welcher Algorithmus sollte angewendet werden, wenn ein Hindernis vor dem Ziel vor dem Roboter auftritt?
Ein Hindernis erlaubt dem Roboter nicht, sein Ziel in einer geraden Linie zu erreichen, der Rover hält in dieser Situation einfach vor ihm an. In diesem Fall können Sie auch den Algorithmus „Walk To“ verwenden, der jedoch ergänzt werden muss.
Fehleralgorithmus
Im normalen Leben umgeht ein Mensch es einfach, wenn er von einem Punkt zum anderen zum Ziel geht und auf ein Hindernis stößt. Dieses Verhalten wird als „Vermeiden von Hindernissen“ bezeichnet. Es wird sich herausstellen, dass es angewendet wird, um das Ziel des Roboters zu erreichen. Der einfachste Weg, den Käfer-Algorithmus anzuwenden.
Der Bug-Algorithmus wird von Experten auf diese Weise aufgerufen, da hier das Verhalten des Käfers zugrunde gelegt wird - wenn er ein Hindernis sieht, umgeht er es.
Die Schritte, die der Roboter unternimmt, während er sich auf das Ziel zubewegt (auch wenn er um ein Hindernis herumgeht), werden als Flugbahn bezeichnet.
Der Fehleralgorithmus diente als Grundlage für die Konzepte, die beim Erstellen von Routen eines komplexeren Typs verwendet werden. Dazu gehören:
Flugbahnkonzept. Dies ist eine einfache Abfolge von Bewegungen des Roboters, die er ausführt, um das endgültige Ziel zu erreichen. Der Käfer-Algorithmus ist auch ein "Trajektorienplaner". Nachdem der Algorithmus die Koordinaten der Punkte erhalten hat, an denen sich der Roboter und sein Ziel befinden, entwickelt er eine geeignete Bewegungsbahn.
Richtlinienkonzept . Wenn unter Verwendung des Käferalgorithmus bestimmte Bewegungsanweisungen an den Roboter übertragen werden, wird diese Art der Routenkonstruktion als „Verwaltungsrichtlinie“ bezeichnet.
Heuristisches Konzept. Dies ist der Name der Regel, mit der der Roboter über die nächste Stufe des Algorithmus informiert wird. In dieser Situation ist die Heuristik die Linie, entlang der sich das Objekt bewegt. Wenn Sie einen Pfad erstellen, müssen Sie die Heuristik korrekt bestimmen. Wenn dies falsch gemacht wird, ist die konstruierte Route nicht funktionsfähig.
Ein solcher Algorithmus schränkt den Entwickler jedoch ein, da mit seiner Hilfe eine Route erstellt werden kann, deren Größe begrenzt ist. Wenn Sie einen solchen Algorithmus zum Erstellen eines Pfades verwenden, müssen alle Hindernisse die Form eines konvexen Polygons haben.
Der Bug-Algorithmus hat auch Einschränkungen:
- Hindernisse sollten in einem bestimmten Abstand voneinander sein, es ist unmöglich, dass sie Gemeinsamkeiten haben;
- Die Grenzen von Hindernissen sind geschlossene Kurven, während sie so sein müssen, dass die gerade Linie, entlang der sich der Roboter bewegt, jede von ihnen für eine begrenzte Anzahl von Malen schneidet.
- Ein Roboter ist ein unverhältnismäßig kleiner Punkt, sodass er sich unabhängig vom Durchgang zwischen ihnen zwischen Hindernissen bewegen kann.
Einige dieser Einschränkungen können mithilfe des erweiterten DH-Bug-Algorithmus überwunden werden. Sein Merkmal ist, dass der Roboter mit seiner Hilfe in der Lage ist, sich bewegende Hindernisse zu bewältigen. Darüber hinaus besteht ein solcher Algorithmus aus zwei Schichten. Der erste ist beratend. Sie können die Route ohne zusätzliche Informationen vorab auswerten. Die zweite Schicht ist adaptiv. Dank ihm reagiert der Roboter rechtzeitig auf Hindernisse, die ursprünglich nicht im Programm festgelegt waren.
CBUG-Algorithmus
Der CBUG-Algorithmus ist eine Version der Routenkonstruktion, bei der alle Details berücksichtigt werden. Während der Entwicklung berücksichtigten Spezialisten die Größe des Roboters und lösten auch Probleme im Zusammenhang mit der Optimierung des erstellten Pfads. Ein charakteristisches Merkmal eines solchen verbesserten Algorithmus ist, dass zum Erzeugen einer Route der Startpunkt immer im Speicher des Objekts verbleiben muss. Ausnahmslos für den CBUG-Algorithmus ist nur für seine Anwendung eine feste Speichermenge erforderlich.
Dijkstra-Algorithmus
Der für Grafiken verwendete Algorithmus wurde von E. Dijkstroy in der zweiten Hälfte des letzten Jahrhunderts erstellt. Mit seiner Hilfe wird es möglich sein, den kürzesten Weg von einem der Eckpunkte des Graphen zu anderen zu bestimmen. Ein solcher Algorithmus endet, wenn der Roboter alle Spitzen besucht hat. Wenn diejenigen, die er noch nicht besucht hat, fahren, wird ein Gipfel mit einer Mindestpunktzahl ausgewählt.
Die Vorteile des Deister-Algorithmus umfassen:- Achten Sie auf die Länge des Pfades und seine Kosten.
- Knoten werden aktualisiert, wenn ein optimalerer gefunden wird.
Der Nachteil dieser Methode zur Erstellung einer Route besteht darin, dass sie nur für Diagramme geeignet ist, bei denen keine Kanten mit negativem Gewicht vorhanden sind. Es ist unpraktisch, dass er bei der Suche in der Breite schlecht orientiert ist.
Bellman-Ford-Algorithmus
Aber oft treten Situationen auf, in denen es notwendig ist, eine Route zu bauen, auf der Rippen mit negativem Gewicht vorhanden sind. Der Bellman-Ford-Algorithmus hilft bei der Lösung eines solchen Problems. Wenn infolgedessen die Summe der Gewichte der Kanten des endgültigen Pfades einen negativen Wert annimmt, wird dies als negativer Zyklus bezeichnet.
Johnson-Algorithmus
Dieser Algorithmus wurde von DB eingeführt Johnson, um alle kürzesten Routen von einem Gipfel zum anderen zu identifizieren. In diesem Fall kann die Methode für Kanten mit sowohl positiven als auch negativen Gewichten verwendet werden. Der einzige Nachteil des Algorithmus ist, dass es keine negativen Zyklen gibt.
Algorithmus A *
Um den optimalen Weg mit Grafiken zu finden, müssen Sie den A * -Algorithmus anwenden. Sie können die beste Route vom Roboter zum Ziel durch die erste Übereinstimmung in der Grafik bestimmen. Die Basis dieses Algorithmus ist die heuristische Formel, die wie folgt lautet:
f(n)=g(n)+h(n).
f(n) - , n.
g(n) - n .
h(n) - .Mit diesem Algorithmus können Sie den kürzesten Weg zum Ziel finden, bis h (n) den maximal zulässigen Wert annimmt. Ein Merkmal des A * -Algorithmus ist seine Flexibilität. Meistens ist der Zustand die Zelle oder der Ort des Roboters. Es kann aber auch Geschwindigkeit oder Orientierung sein.
Gleichzeitig variieren die nahe gelegenen Staaten je nach Einzelfall.
Die Flexibilität des Algorithmus zeigt sich auch darin, dass das Ziel, das der Roboter erreichen muss, aus mehreren Positionen gleichzeitig bestehen kann. In einer solchen Situation sollte die heuristische Näherung h (n) für alle verfügbaren Zwecke sofort gültig sein.
Wie gut der Algorithmus A * funktioniert, hängt vom Exponenten h (n) ab. Je besser die heuristische Approximationsqualität ist, desto höher ist die Effizienz. Auch die Menge an freiem Speicher und die Prozessorzeit beeinflussen den Betrieb des Algorithmus.
Wellenverfolgungsalgorithmus
Außerdem wird häufig ein Wellenalgorithmus verwendet, um eine Route in einem Diagramm zu zeichnen. Wenn Sie einen Pfad auf diese Weise erstellen, wird die Breitensuchmethode verwendet.
Der Algorithmus selbst umfasst die folgenden Schritte:- Initialisierung
- Wellenbau;
- Wiederherstellung der Route.
In der Anfangsphase wird das Bild vieler Zellen erstellt, von denen jede für den Roboter entweder passierbar oder unpassierbar wird.
Der Roboter, der sich von einer Zelle zur anderen bewegt, bestimmt nacheinander, ob es möglich ist, sie zu passieren, und ob er sie zuvor nicht markiert hat.
Danach wird der kürzeste Weg von der Startzelle zur letzten durch rohe Gewalt geschaffen, deren Erreichung der Zweck des Rovers ist.
Raumalgorithmus diskretisieren
- Der Konfigurationsraum hat in allen Dimensionen eine konstante Größe.
- Diskretisieren Sie alle Messungen so, dass sie eine konstante Anzahl von Zellen haben.
- Alle Zellen im Konfigurationsraum innerhalb des Hindernisses sollten als unpassierbar markiert werden.
- Infolgedessen wurden alle passablen Zellen zu Knoten.
- Jeder Knoten stellt eine Verbindung zu allen Nachbarn im Diagramm her.
Randomized Path Finder
Die schwierigsten Aspekte bei der Planung einer Route sind die Berechnung des Konfigurationsraums und die Bestimmung des bequemsten Pfades beim Durchlaufen dieses Raums. Dank Roadmaps können diese Probleme gelöst werden. Die Essenz der Methode besteht darin, den Raum in identische Quadrate zu unterteilen und alle nächsten Eckpunkte zu verbinden. Durch alle Pfade iterieren. Sortieren Sie alle Pfade, um den Pfad mit dem geringsten Wert zu finden.
Probabilistischer Roadmaps-Algorithmus
- 1. Erstellen Sie ein leeres Diagramm G.
- 2. Fügen Sie dem Diagramm G die Knoten des Roboters und sein Endziel hinzu.
- 3. Für die N-te Anzahl von Integrationen:
- Suchen Sie eine einheitliche Zufallsstichprobe des Konfigurationsraums und geben Sie ihm den Namen R.
- Wenn der Roboter mit der R-Konfiguration in Konflikt steht, können Sie fortfahren.
- Andernfalls: Fügen Sie R zu Spalte G hinzu.
- 4. Identifizieren Sie alle Knoten im Diagramm, die sich innerhalb der Punkte d und R befinden.
- 5. Für alle N Knoten, die zu diesem Parameter passen:
Schneller Erkundung des Algorithmus für randomisierte Bäume
Manchmal müssen Sie einen Pfad erstellen, ohne vorherige Planungsabfragen anzuwenden. In solchen Situationen müssen Sie die folgende Methode anwenden:
- Erstellen Sie einen leeren T.-Baum
- Zu T anfängliche Roboterkonfiguration hinzufügen.
- Bis das Ziel erreicht ist:
- Abrufen für Knoten R.
- Definieren Sie in T den Knoten, der R am nächsten liegt. Gib ihm den Namen K.
- Bewegen Sie den Roboter von K nach R, bis die folgende Bedingung erfüllt ist:
- Fahren Sie im Falle einer Kollision mit der Definition einer Zufallsstichprobe fort.
- Andernfalls: Fügen Sie in dieser Konfiguration einen neuen Knoten zu T hinzu.
- Wenn der maximale Abstand zwischen d und K erreicht ist, beginnen Sie erneut mit der Zufallsstichprobe.
- Die Lösung wird erhalten, wenn sich der Kettenknoten innerhalb des Abstands d von einem beliebigen Knoten T befindet.
Fazit
Für uns ist es optimal, das Thema Streckenbau in globale und lokale zu unterteilen. Eine globale Route ist eine Liste von Zielpunkten, um das Feld oder das Ziel der Rückkehr zur Basis zu umgehen. Eine lokale Route beginnt, wenn Ultraschallsensoren oder ein Stoßfänger ein Hindernis erkennen.
Da in unseren Besonderheiten alle Hindernisse konvex sind, verwenden wir den einfachsten und noch einfacheren BUG-Algorithmus. Eine bestimmte "junge" Navigationsmethode. Wenn ein Ultraschall ein Hindernis erkennt, dreht sich der Rover um 90 Grad im Uhrzeigersinn, passiert 1 m und dreht sich um 90 gegen den Uhrzeigersinn. Wenn der Stoßfänger ein Hindernis erkennt, drehen Sie den Roboter 0,5 Meter zurück.
Pläne
Zu Beginn des Projekts im Sommer 2018. Eine große Anzahl von Ereignissen ist passiert. Wir bereiten einen Beitrag zur Entwicklung unseres Projekts vor. Vielen Dank für Ihre Aufmerksamkeit!
Referenzen