Was ist eine effiziente Möglichkeit, jeden erreichbaren Bereich in einem Raster mit unbekannten Hindernissen zu besuchen?

Ich versuche, mithilfe der Exploration eine Karte der Hindernisse in einem relativ groben 2D-Rasterraum zu erstellen. Ich erkenne Hindernisse, indem ich versuche, mich von einem Feld in ein benachbartes Feld zu bewegen. Wenn dies fehlschlägt, befindet sich ein Hindernis im Zielfeld (in diesem Problem gibt es kein Konzept für einen Entfernungsmesssensor).

Beispielraster http://www.eriding.net/resources/general/prim_frmwrks/images/asses/asses_y3_5d_3.gif (zum Beispiel)

Der Vorgang ist abgeschlossen, wenn alle erreichbaren Felder besucht wurden. Mit anderen Worten, manche Räume sind möglicherweise nicht erreichbar, selbst wenn sie keine Hindernisse haben, weil sie umgeben sind. Dies wird erwartet.

Im einfachsten Fall könnte ich einen DFS-Algorithmus verwenden , aber ich befürchte, dass dies zu lange dauern wird - der Roboter verbringt mehr Zeit mit der Rückverfolgung als mit der Erkundung von Neuland. Ich erwarte, dass dies besonders problematisch ist, wenn versucht wird, die nicht erreichbaren Felder zu erreichen, da der Roboter jede Option ausschöpfen wird.

Bei der ausgeklügelten Methode scheint die Zersetzung der Boustrophedon-Zellen das Richtige zu sein .

Ich kann jedoch keine gute Beschreibung des Boustrophedon-Zellzerlegungsalgorithmus finden (dh eine vollständige Beschreibung in einfachen Worten). Es gibt Ressourcen wie diese , oder diese allgemeinere auf vertikale Zelle Zersetzung aber sie bieten nicht viel Einblick in die High-Level - Algorithmen noch die Low-Level - Datenstrukturen beteiligt.

Wie kann ich dieses Raster effizient besuchen (abbilden)? Wenn es existiert, würde ich mir einen Algorithmus wünschen, der in Bezug auf die Gesamtzahl der Gitterquadrate eine bessere Leistung als $O(n^2)$ erbringt ( dh für ein n ∗ n- Gitter eine bessere Leistung als $O(n^4)$ ).$n*n$

Die Zersetzung von Boustrophedon-Zellen unterteilt eine Umgebung einfach in Bereiche, die durch einen Boustrophedon-Pfad effizient abgedeckt werden können. Eine trapezförmige Zerlegung ist ausreichend und kann unter Verwendung eines Zeilenabtastungsalgorithmus durchgeführt werden. Siehe [Choset 2000], Diese Website oder (ich empfehle!) Das ausgezeichnete Buch "Computational Geometry" von Mark de Berg, et. Für eine vollständige Beschreibung der erforderlichen Datenstrukturen und Algorithmen.

Choset, Howie. "Abdeckung bekannter Räume: Die Zersetzung von Boustrophedon-Zellen" Autonomous Robots , 2000.

Betrachten Sie beispielsweise die Menge der Hindernisse als Kanten und Scheitelpunkte. Angenommen, die Umgebung wird auch von einem speziellen Polygon begrenzt. Wir haben so etwas wie das Folgende. Um diesen Raum zu zerlegen, fügen wir einfach vertikale Kanten zwischen jedem Scheitelpunkt und der nächsten Linie oder dem nächsten Scheitelpunkt hinzu.

Um dies im Code zu erreichen, benötigen Sie nur einen Schnittpunkttest für Liniensegmente, eine sortierte Liste von Kanten und eine sortierte Liste von Scheitelpunkten.

1. $v_i$
2. $l_i$$v_i$ , die bis zur ersten Kante oder dem ersten Scheitelpunkt, den sie schneidet, verlängert wird
3. Erstellen Sie an jeder Kreuzung einen neuen Scheitelpunkt.

In diesem Fall werden in der Menge der neuen Kanten und Eckpunkte nur Trapezoide eingeschlossen. Ich betone jedoch, dass dies nicht online möglich ist (ohne vorherige Kenntnis der Hindernisse). Wenn Sie ohne Vorkenntnisse eine solide Berichterstattung durchführen möchten, sollten Sie sich "Fehleralgorithmen" ansehen. Insbesondere ist hier ein einfacher Algorithmus unter der Annahme, dass die Umgebung begrenzt ist.

1. Bewegen Sie sich von der Startposition nach oben und links, bis Sie die obere linke Ecke der Umgebung erreichen. Wenn Sie zuerst auf ein Hindernis stoßen, müssen Sie es umfahren. Sie wissen, dass etwas ein Hindernis ist, wenn es umfahren werden kann (Stoßen und Bewegen).

2. Bewegen Sie sich von links oben nach rechts, bis Sie auf die Grenze stoßen. Bewegen Sie sich dann nach unten und links (wir machen eine Boustrophedon des gesamten Raums).

3. Wenn Sie sich auf einer Linie von links nach rechts befinden und auf ein Hindernis stoßen, haben Sie zwei Möglichkeiten. (i) Wir können umrunden, bis wir die Links-Rechts-Linie erreichen, die wir abdecken wollen, und dann weitermachen. (ii), Wir können uns umdrehen und eine neue Links-Rechts-Linie abdecken, bis wir uns am Hindernis vorbei finden oder wieder in dieser Situation enden. Ich werde es veranschaulichen.

Links bewegen wir uns um das Hindernis herum, bis wir zu der "Linie" zurückkehren können, der wir folgen wollten. Rechts fahren wir fort, den (kleineren) Bereich auf der einen Seite des Hindernisses abzudecken.

Der Vorteil der ersten Methode besteht darin, dass Sie das Hindernis immer vollständig abbilden, bevor Sie eine Entscheidung darüber treffen, wie Sie es umgehen möchten. Auf diese Weise können Sie den kürzeren Weg einschlagen. Der Vorteil der zweiten Methode ist, dass Sie das Hindernis überhaupt nicht umgehen müssen. Sie können einfach den Bereich abdecken, in dem Sie sich befinden.

Beachten Sie, dass dies Ihre Boustrophedon-Zersetzung online definiert : Sie decken den Bereich zwischen den Hindernissen oder zwischen den Hindernissen und der Grenze ab.

Soweit ich weiß, ist die erste Methode jedoch einfacher zu analysieren. Die komplizierteren Algorithmen (wie BFS usw.) werden entweder ausgewählt, weil die Umgebung unbegrenzt ist (Sie möchten nicht für immer nach einer Grenze suchen), oder es gibt ein wirklich unangenehmes Hindernis in der Art und Weise, in der die Umgebung grundsätzlich partitioniert wird. Warum ist das so schlimm? schau dir dieses Beispiel an:

Wenn Sie sich von links nach rechts bewegen und dann jedes Hindernis umkreisen, entsteht ein Weg zwischen den einzelnen Hindernissen zu viele Abdeckungen der kleinen Teile. In der Tat können Sie dies ohne globale Pfadplanung so schlecht wie die Auflösung Ihres Rasters machen, indem Sie diese Spalten 1 px breit, so hoch wie die gesamte Umgebung und 1 px voneinander entfernt platzieren. Dann müsstest du dich jedes Mal um das Hindernis bewegen, wenn du es triffst.

Aus diesem Grund habe ich Sie gefragt, ob Sie eine Vorstellung davon haben, wo Sie sich in der Umgebung befinden oder ob Sie eine globale Pfadplanung durchführen können. Aber die Online- gegen- Offline- Diskussion und die optimalen Algorithmen dafür sind nicht das, was Sie wirklich wollten.

Update: Ich musste die Bilder entfernen (nicht https) und werde dies veröffentlichen, was häufig in praktischen Anwendungen verwendet wird. http://www.cs.cmu.edu/~motionplanning/papers/sbp_papers/integrated1/yamauchi_frontiers.pdf

Am Ende fand ich, dass der beste Weg, dies zu tun, darin bestand, ein sehr einfaches Konzept zu verwenden: Flood Fill . Ich habe einen stapelbasierten iterativen Ansatz anstelle der rekursiven Option verwendet und ihn für den physischen Raum mithilfe einer A * -Suche geändert, um einen Pfad von der aktuellen Position zur nächsten Position im Stapel zu finden (wobei nur die bereits vorhandenen Rasterquadrate verwendet wurden) besucht worden, da ich garantiert einen Weg zwischen ihnen habe).

Die Effizienz scheint ziemlich vernünftig.