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.
Geht doch allgemein in Richtung Grapgentheorie.
A* ist der Algorithmus, der sehr oft für diese Probleme eingesetzt wird (http://de.wikipedia.org/wiki/A*-Algorithmus)
Hallo, die Graphentheorie ist dafür mathematischer Overkill, nimm den Lee-Algorithmus.
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.
Ich denke für deinen Zweck ist A* besser als der Dijkstra, der ist hier wahrscheinlich schneller.
Falls das Thema generell interessiert: Ab dem 12.1 läuft auf Coursera wieder AI Planning https://www.coursera.org/course/aiplan
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.
In meinem Fall weiss ich alles. Kenn also jedes "Hindernis" im Voraus.
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_tree http://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."???
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.