Pathfinding mit voronoi

Ich habe eine Sackgasse mit meinem Universitätsprojekt erreicht und ich kann keine Lösung finden. Das Problem ist:Pathfinding mit voronoi

einen Kreisroboter (grüner Kreis) mit dem Radius r gegeben Ich brauche einen Weg zu finden (jeden Pfad nicht die beste) bis zum Endpunkt, das der blaue Punkt ist.

Bild unten

Die Hindernisse sind die roten Polygone und um sie herum die cyanfarbene Linien die Minkowski-Summe darstellt.
Die schwarzen Punkte repräsentieren das Voronoi-Diagramm.
Die blaue Box ist um die äußere Grenze

Also zuerst obwohl ich, ich sollte die näher Punkte auf den Startpunkt (Roboter) und dem Endpunkt der Voronoidiagramm Punkte finden. Und diese Punkte werden im Bild angezeigt (cyan dots).

Dann dachte ich mit einigen König des Algorithmus wie der A * nach dem Pfad für die cyan Punkte oben entlang der Voronoi Punkte suchen, auf diese Weise werde ich die sicherste Weg Art finden.

Das Problem ist, dass ich keine Möglichkeit habe zu wissen, welche Nachbarn die einzelnen Punkte im Voronoi-Diagramm sind. Denn wie Sie in den einzelnen Teilen des Diagramms sehen können, gibt es große Lücken.

Was schlagen Sie vor?

Vielen Dank für Ihre Zeit.

Quelle

2016-07-04 George P

gibt es eine Grenze für die Größe der Karte? – Saikios

Das blaue Polygon um die Hindernisse ist die Grenze. Seine Abmessungen sind etwa 1000x700 Pixel (abhängig von der Fenstergröße). –

so schlimmsten Fall Szenario, wenn Sie keine Möglichkeit haben, nichts über die Karte zu wissen ist, durch alle Punkte gehen, nur in eine obere Ecke oder unten gehen und beginnen von dort aus alles Wenn es eine Karte was war Am besten funktionierte es für mich in der Vergangenheit, immer nach links zu gehen, aber in diesem Fall mit unregelmäßigen Karten ist es manchmal besser, einfach alle Punkte durchzugehen. – Saikios

erstellen Schwarz-Weiß-Bild, das Ihre Karte darstellt. Es sollte als ganz schwarz beginnen.
Rendern Sie Ihre Hindernisse als weiß.
Erweitern Sie das Bild mit einem kreisförmigen Filter von der Größe Ihres kreisförmigen Roboters.
Suchen Sie den kürzesten Weg von A nach B, der nur schwarze Pixel durchquert.

Quelle

2016-07-07 18:52:24

Wirklich cooler einzigartiger Ansatz. Wie schnell ist das in der Praxis? Haben Sie Sichtbarkeitsgraphen oder andere traditionelle Bewegungsplanungsansätze (RRT, PRM, Potenzialfelder) berücksichtigt? – AndyG

Ich mag diese Lösung sehr, obwohl ich bereits das Problem mit Sichtbarkeit Grafik und A * Suche gelöst habe Ich bin interessiert zu wissen, ob eine ähnliche Vorgehensweise für Ihren nächsten Teil des Problems verwendet werden kann, die ein zweidimensionaler Roboter ist kann sich drehen. Wenn nicht, können Sie etwas empfehlen, das relativ einfach zu implementieren ist? –

@GeorgeP Zum Beispiel: Erstellen Sie N-rotierte-rotierte-Roboterformen-Filter für N verschiedene Rotationen, um N Navigationsbilder zu erzeugen (eines für jeden Rotationsbereich). Mit N = 8 würden Sie einen Filter erzeugen, der der Form entspricht, die Ihren Roboter von 0 bis 45 Grad, von 45 bis 90, ..., von 315 bis 360 darstellt. Dann können Sie eine Graphensuche durchführen, um einen Pfad zu finden , wo Sie auch zwischen den N Bildern springen können (entsprechend der Roboterrotation, die ein Vielfaches von 45 Grad Grenze kreuzt). –

Das Problem ist, dass ich keine Möglichkeit habe zu wissen, welche Nachbarn die einzelnen Punkte im Voronoi-Diagramm sind. Denn wie Sie in den einzelnen Teilen des Diagramms sehen können, gibt es große Lücken.

gibt es wahrscheinlich eine bessere Lösung, aber hier ist ein einfacher Algorithmus Sie könnten versuchen:

Suche (oder manuell eingestellt) die längste Strecke zwischen „verbunden“ Punkte, D.
Machen Sie eine Tabelle der Abstände zwischen jedem Punktepaar Ihres Voronoi-Diagramms, wobei dieser Abstand kleiner oder gleich D ist.
Verbinden Sie alle Punkte beginnend mit kürzeren Dist mit Ausnahme, wenn ein Pfad kürzer als D bereits vorhanden ist (um unnötige kleine Schleifen und Schnitte zu vermeiden).
Finden Sie den nächsten Punkt zu Ihrem Roboter und dem nächsten Punkt zu Ihrem Ziel.
Führen Sie den Algorithmus für den kürzesten Pfad in der Grafik aus, die Sie in Schritt 3 erstellt haben.

Quelle

2016-07-04 13:08:11 user5226582

Antwort

Verwandte Themen