Es gibt Links zu einigen Dokumenten auf D * here, aber sie sind ein bisschen zu mathematisch für mich. Gibt es Informationen zu D */D * Lite, die eher auf Anfänger zugeschnitten sind?Wo finde ich Informationen zum Pfadfindungsalgorithmus D * oder D * Lite?
kam ich mit diesem
http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf und diese
http://www.cs.cmu.edu/~maxim/docs/dlitemap_iros02.pdf
Ich hoffe, dass diejenigen, Link wird Ihnen helfen :)
Edit: Nach der Buchung Ich habe bemerkt, dass die Links Ich habe Ihnen in der Verbindung waren Sie darauf hinaus auch. Trotzdem habe ich diese direkt bei Google gefunden. Jedenfalls habe ich ein wenig nachgeschaut und sie scheinen nicht so kompliziert zu sein. Wenn Sie A * gut kennen, sollten Sie auch D * verstehen.
Aus Erfahrung kann ich Ihnen sagen, dass A * auch für das verwendet werden kann, was Sie wollen.
Ja, das sind die Whitepaper, die ich selbst durch Googeln gefunden habe. Die Erklärungen sind im undurchdringlichen Mathejargon und der Pseudocode ist nicht viel besser. Was die Verwendung von A * betrifft, habe ich eine sehr optimierte Implementierung in meinem RTS-Spiel, aber es ist nicht schnell genug, eine so dynamische Welt. – Trillian
Wikipedia hat einen Artikel zum Thema: http://en.wikipedia.org/wiki/D*
Auch in C ein D * Lite Implementierung von Sven Koenig Seite verfügbar: http://idm-lab.org/code/dstarlite.tar Jedoch habe ich die undurchdringliche Mathe viel einfacher finden den C-Quellcode zu lesen, als, -)
Eine weitere Implementierung von D * Lite (in C++) finden Sie hier: http://code.google.com/p/dstarlite/
+1 Ich habe mich selbst nicht durchsucht, aber nach den Antworten hier zu urteilen, und den Wiki-Artikel zu lesen, scheint dies die nächste Sache zu sein, die dem OP zur Verfügung steht. –
Nun, wenn Pseudo-Code für Sie hart ist (Sie Sätze und Beweise nicht lesen müssen - Pseudo-Code ziemlich geradlinig ist Wenn Sie Standardalgorithmen kennen und Sie sich beschweren gegen veröffentlichten C- und C++ - Code, dann denke ich, du musst etwas anderes machen :-)
Ernsthaft, erwarte nicht, dass jemand dir einen erstklassigen Algorithmus in ein paar Webabsätzen beibringen kann. Nimm einen Stift und Papier und schreibe, zeichne und folge auf dem Papier, was los ist. Vielleicht müssen Sie etwas zweimal lesen und ein oder zwei Referenzen googlen, um ein paar Konzepte kennenzulernen, und es gibt keine Notwendigkeit, die Theoreme und Beweise zu studieren - es sei denn, Sie möchten dem Autor beweisen, dass das falsch ist :-))
Kann nicht ohne etwas mehr Mathe vorwärts gehen - c'est la vie. Stellen Sie sich vor, Sie hätten jemanden gebeten, Ihnen beizubringen, was in der Welt Matrixinversion ist, aber Sie wissen nicht, was Vektoren sind. Niemand konnte dir helfen, bis du genug von dem mathematischen Kontext gelernt hast.
Es gibt so viele klare Erklärungen von A * im Netz, dass ich wirklich überrascht bin, dass es für D * keine gibt. Ich weiß, D * ist in Bezug auf die Komplexität ein Schritt über A *, aber ich erwartete, dass jemand eine Erklärung für den Laien schreiben würde. Ja, das ist Faulheit, ich weiß, und da es keine passenden Antworten gibt, tauche ich wieder in die Zeitung ein. Ich finde nur, dass ein mathematisches Whitepaper nicht der beste Weg ist, um ein intuitives Verständnis eines Algorithmus zu entwickeln. – Trillian
Es gibt einen Schritt zwischen der Frage nach Matrixinversionen, wenn Sie nichts über Vektoren wissen und nach D * fragen, wenn Sie über A * wissen. – zneak
Nachdem gesagt, warum nicht noch ein paar Papiere hinzufügen, ja, sie haben auch Mathe :-), aber ich werde versuchen, einige neuere Sachen zu bekommen.Menschen in der Regel besser auf ihre eigene Arbeit zu erklären, wie die Zeit vergeht, so liegt der Schwerpunkt auf Stentz, Likhachev und Koenig
Danke für die praktischere Antwort. Ich hatte die meisten dieser Papiere nicht gefunden. Ich könnte diese Antwort nur mit dem Kopfgeld versehen, um zu verhindern, dass Ihre andere Antwort es automatisch erhält. Schließlich ist deine andere Antwort eher eine Meinung als eine Antwort, auch wenn es mich motiviert hat, zurück in die Whitepaper zu tauchen, um nur zu beweisen, dass ich das tun kann. – Trillian
Du musst auf akademischem oder Corp-Netz sein Springer ist "Abonnent", wenn Sie PDF-s auf einfache Weise möchten. Einige Autoren veröffentlichen leicht geänderte Artikel mit anderen Zeitschriften, andere nicht. Deshalb ist meine Suchheuristik, zu versuchen, Autoren zuerst zu folgen, und Springer Aufstellungsort ist der einfache Weg, um neue Informationen schnell zu erhalten. Der erste könnte sogar einen Kauf wert sein, wenn man sich nicht nur für den Algo interessiert, sondern auch für ein Stantz-Papier, in dem er feststellt, dass sein neuer Algo auf D * Lite basiert - für einen Forscher sogar eine implizite Tatsache. – ZXX
D * Lite Erklärung für den Laien
D * beginnt mit einem Krähe-Fliegen, idealistischen Weg zwischen Start und Goal; Es behandelt Hindernisse nur dann, wenn sie auf sie treffen (normalerweise, indem sie sich in einen benachbarten Knoten bewegen). Das ist - D * Lite kennt keine Hindernisse bis beginnt es entlang dieser idealen Pfad zu bewegen. Der heilige Gral mit jeder Pfadfinderimplementierung ist, es schnell zu machen, während man den kürzesten Pfad oder zumindest einen anständigen Pfad (sowie alle Ihre speziellen Bedingungen hier - für D * Lite das geht mit einem unbekannte Karte als Mars Rover könnte]].
Eine der großen Herausforderungen von D * Lite ist die kostengünstige Anpassung an Hindernisse, wenn diese erreicht werden. Sie zu finden ist einfach - Sie überprüfen nur den Knotenstatus der Nachbarn, während Sie sich bewegen. Aber wie passen wir die Kostenschätzungen der vorhandenen Karte an, ohne jeden Knoten zu durchlaufen ... was sehr teuer sein könnte?
LPA * nutzt einen cleveren Trick, um die Kosten anzupassen, ein Trick, den D * Lite genutzt hat. Der aktuelle Knoten fragt seine Nachbarn: Du kennst mich am besten, denkst du, dass ich realistisch bin? Spezifisch fragt es dies nach seinem g Wert, der die bekannten Kosten des Erhaltens von dem anfänglichen Knoten zu sich selbst, d. H. Dem aktuellen Knoten, ist. Nachbarn schauen auf ihre eigenen g, schauen, wo der aktuelle Knoten in Bezug auf sie ist, und bieten dann eine Schätzung, was sie denken, ihre Kosten sollten sein. Das Minimum dieser Angebote wird als der rhs Wert des aktuellen Knotens gesetzt, der dann verwendet wird, um seinen g Wert zu aktualisieren; Beim Schätzen berücksichtigen Nachbarn die neu entdeckten Hindernisse (oder Freiräume), so dass bei aktuellen Aktualisierungen g mit rhs dies mit den neuen Hindernissen (oder Freiräumen) Rechnung getragen wird.
Und sobald wir realistische g Werte auf der ganzen Linie haben, erscheint natürlich ein neuer kürzester Weg.
D * Lite veraltet angeblich D *, also habe ich letzteres hier nicht aufgenommen. –
D * ist kein Anfänger-Algorithmus, und der Anwendungsfall ist ziemlich eng. Sind Sie sicher, dass Sie nicht nur A * für Ihre Bewerbung benötigen? – Donnie
Ich brauche einen Bot, um die Wände zu einem Ziel zu navigieren. Der Spieler kann Hindernisse auf dem Bot platzieren und der Bot sollte in der Lage sein einen neuen Pfad in Echtzeit zu finden. D * ist gut, um solche Umgebungen zu verändern, oder? – tehalynn
stimme ich vollständig zu. Ich habe das A * viele Male und auf einer Vielzahl von Graphen implementiert, und ich wollte D * (lite) auch für einige Zeit implementieren. Es gibt zwei oder drei Whitepaper im Netz, aber ich habe es noch nicht geschafft, aus diesen unlesbaren mathematischen Beschreibungen etwas Nützliches herauszuholen. – Trillian