Hallo,
für ein Roboterprojekt möchte ich den Weg von A nach B berechnen. Es ist
jedoch nicht immer eine Gerade, denn zwischen A und B können auch
Hindernisse sein. Flächen, die nicht überquert werden dürfen.
Diesen Weg würde ein PC System anhand einer Karte mit den
eingezeichneten Hindernissen planen. Im Prinzip ein 2D Array. Also wie
eine Bitmap Grafik mit ausgegrauten Flächen.
Ergebnis wäre also etwas in der Art: Fahre nicht direkt zu B, sondern
erst zum Punkt C,D,E und dann nach B.
Da ich mit so was nicht der erste bin, suche ich Stichpunkte, nach was
ich suchen kann.
Neuhardt schrieb:> die Graphentheorie ist dafür mathematischer Overkill,
also das musst du mir erklären - die graphentheorie ist ein
themengebiet, das sich unter anderem mit dem finden von wegen
beschäftigt (sofern die struktur in der sich wege befinden als graph
modelliert ist bzw. modelliert werden kann). von daher ist der hinweis
darauf sicher nicht unangebracht.
klar gibt es einfachere und kompliziertere wege das problem zu lösen -
was du ja mit einem vorschlag gemacht hast...
Also die Grafik beim Wiki Eintrag zu A* ist eigentlich genau das, was
ich suchte. Danke schön.
Auch an die anderen. Welchen ich dann nehme, muss ich noch prüfen.
Prinzipiell habe ich jetzt aber gute Ansätze.
Omburg schrieb:> Also die Grafik beim Wiki Eintrag zu A* ist eigentlich genau das, was> ich suchte
Nein. Wenn Du ein festes Raster hast, wäre, wie jemand schon schrieb,
der Lee Maze Router Algorithmus wohl eine gute Wahl. Den nahmen ja auch
frühe PCB Autorouter, als man noch gerne feste Raster für Strukturen
verwendet hatte. Das ist einfache Wave Propagation, bei
http://en.wikipedia.org/wiki/Lee_algorithm
steht zwar nicht viel, aber mit Google hatte ich vor langer Zeit doch
einiges dazu gefunden.
Dijkstra wäre eher etwas, wenn man mit dem Auto irgend wohin fahren
will, zu jeder Stadt die Entfernung zu einigen Nachbarstädten kennt, und
den kürzesten Weg sucht. Auch einfach, bring dir aber keine Vorteile.
Und A* -- nunja ähnlich wie Dijkstra wenn eine Richtung präferiert wird.
Salewski schrieb:> Omburg schrieb:>> Also die Grafik beim Wiki Eintrag zu A* ist eigentlich genau das, was>> ich suchte>> Nein. Wenn Du ein festes Raster hast, wäre, wie jemand schon schrieb,> der Lee Maze Router Algorithmus wohl eine gute Wahl. Den nahmen ja auch> frühe PCB Autorouter, als man noch gerne feste Raster für Strukturen> verwendet hatte. Das ist einfache Wave Propagation, bei>> http://en.wikipedia.org/wiki/Lee_algorithm
Was auch nichts anderes als eine Form der Breitensuche ist und unter
bestimmten Bedingungen ist Dijkstras Algorithmus ebenso eine
Breitensuche und A* entspricht dem Dijkstra genau dann wenn die
Heuristik immer h(n) = 0 liefert bzw. ist A* ein verallgemeinerter
Dijkstra.
> Und A* -- nunja ähnlich wie Dijkstra wenn eine Richtung präferiert wird.
Ziemlich gute, interaktive Seite zum A* ist z.B.
http://www.redblobgames.com/pathfinding/a-star/introduction.html
Daniel F. schrieb:> Neuhardt schrieb:>> die Graphentheorie ist dafür mathematischer Overkill,>> also das musst du mir erklären - die graphentheorie ist ein> themengebiet, das sich unter anderem mit dem finden von wegen> beschäftigt (sofern die struktur in der sich wege befinden als graph> modelliert ist bzw. modelliert werden kann). von daher ist der hinweis> darauf sicher nicht unangebracht.
Das Hauptproblem dürfte eher sein, dass du von deiner Wohnung keinen
gerichteten Graphen hast, in dem dann auch noch umherliegende Schuhe als
Knoten modelliert sind.
Genau das ist aber das Standardproblem von autonomen Robotern: den Weg
von der Küche ins Bad zu finden, wobei die im Vorraum schlafende Katze
zu umrunden ist.
Ich wuerde auch mit dem Lee Algo anfangen.
Karl Heinz schrieb:> Das Hauptproblem dürfte eher sein, dass du von deiner Wohnung keinen> gerichteten Graphen hast, in dem dann auch noch umherliegende Schuhe als> Knoten modelliert sind.>> Genau das ist aber das Standardproblem von autonomen Robotern: den Weg> von der Küche ins Bad zu finden, wobei die im Vorraum schlafende Katze> zu umrunden ist.
Darauf wären dann u.a D* oder D* Lite spezialisiert. Die grob gesagt A*
für sich dynamisch verändernde Graphen sind.
Eingesetzt wurden die u.a. bei der Urban Challenge und beim Mars Rover.
Eine andere einfache Möglichkeit für bekannte "Terrains" wäre dynamische
programmierung.
Du müsstest nur Gewichte für jede Kachel anlegen und dann einen Weg mit
minimalem Wert auswählen.
RRT – http://en.wikipedia.org/wiki/Rapidly_exploring_random_treehttp://planning.cs.uiuc.edu/
Ansonsten gibt noch als Framework OMPL: http://ompl.kavrakilab.org/ (Was
aber vermutlich für 2D Navigaten etwas zu viel ist)
Hier würde ich A* bzw. besser D* empfehlen. Alternativ eine Roadmap und
per Graphensuche die grobe Richtung angehen (dann musst du dir ein
entsprechendes Modell bauen – irgendwie).
Das wirkliche Problem ist meist ja auch: Zu Beginn des weges im
Wohnzimmer kennt dein Roboter das Aussehen der Küche halt nicht. Also
musst du eh umplanen, bei Bedarf.
dasdasd schrieb:> Du müsstest nur Gewichte für jede Kachel anlegen und dann einen Weg mit> minimalem Wert auswählen.
Du bist ja ein ganz schlauer. Wenn dich jemand nach dem Weg zum Bäcker
fragt, antwortest du dann auch: "Du musst jeder Straße eine Länge
zuordnen, und dann einfach den kürzesten Weg nehmen."???
