Ci sono collegamenti ad alcuni documenti su D * here, ma sono un po 'troppo matematici per me. C'è qualche informazione su D */D * Lite più orientata verso i principianti?Dove posso trovare informazioni sull'algoritmo di ricerca del percorso D * o D * Lite?
sono arrivato fino a questo
http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf e questo
http://www.cs.cmu.edu/~maxim/docs/dlitemap_iros02.pdf
Spero che coloro link aiuterà :)
Edit: Dopo aver postato ho notato che i link che ti ho dato eri nel link lei ha fuori pure. Tuttavia ho trovato quelli direttamente su Google. Ad ogni modo, li ho cercati un po 'e non sembrano così complicati. Se conosci A * beh, dovresti riuscire a capire anche D *.
Per esperienza posso dirti che A * può essere usato anche per quello che vuoi.
Sì, quelli sono i white paper che mi sono trovato su google. Le spiegazioni sono in gergo matematico impenetrabile e lo pseudocodice non è molto meglio. Per quanto riguarda l'utilizzo di A *, ho un'implementazione altamente ottimizzata nel mio gioco RTS, ma non è abbastanza veloce un mondo così dinamico. – Trillian
Wikipedia contiene una voce sul tema: http://en.wikipedia.org/wiki/D*
anche un'implementazione di D * Lite in C è disponibile dalla pagina di Sven Koenig: http://idm-lab.org/code/dstarlite.tar Tuttavia trovo la matematica impenetrabile molto più facile da leggere rispetto al codice sorgente C; -)
Un'altra implementazione di D * Lite (in C++) è disponibile qui: http://code.google.com/p/dstarlite/
+1 Non ho cercato me stesso, ma a giudicare dalle risposte qui, e leggendo l'articolo wiki, questa sembra essere la cosa più vicina a ciò che l'OP vuole. –
Beh, se il codice pseudo è difficile per voi (non c'è bisogno di leggere teoremi e dimostrazioni - pseudo codice è piuttosto semplice se conosci gli algoritmi standard) e ti lamenti contro il codice C e C++ pubblicato quindi suppongo che dovrai fare qualcos'altro :-)
Seriamente, non aspettarti che qualcuno possa insegnarti un algoritmo di prima qualità in pochi paragrafi web. Prendi carta e penna e scrivi, disegna e segui su carta cosa sta succedendo. Potrebbe essere necessario leggere qualcosa due volte e google uno o due riferimenti per conoscere alcuni concetti attorno ad esso, e non c'è bisogno di scavare nei teoremi e nelle dimostrazioni - a meno che non si speri di dimostrare che l'autore ha torto :-))
Non posso andare avanti senza un po 'di matematica - c'est la vie. Immagina di aver chiesto a qualcuno di insegnarti cosa diavolo è l'inversione di matrice, ma non sai quali sono i vettori. Nessuno ti può aiutare finché non hai appreso abbastanza del contesto matematico prima.
Ci sono così tante spiegazioni chiare di A * sulla rete che sono davvero sorpreso che non ce ne siano per D *. So che D * è un passaggio su A * in termini di complessità, ma mi aspettavo che qualcuno avrebbe scritto una spiegazione per il profano. Sì, questa è pigrizia, lo so, e poiché non ci sono risposte adeguate mi tufferò di nuovo sui giornali. Sento che un whitepaper pieno di matematica non è il modo migliore per sviluppare una comprensione intuitiva di un algoritmo. – Trillian
C'è un passo avanti tra chiedere informazioni sulle inversioni di matrice quando non si conoscono i vettori e si chiede di D * quando si _know_ su A *. – zneak
Detto questo, perché non aggiungere altri documenti, sì hanno anche la matematica :-) ma proverò a ottenere alcune cose più recenti.La gente di solito arriva meglio a spiegare il proprio lavoro come il passare del tempo, in modo che il fuoco è sul Stentz, Likhachev e Koenig
Grazie per la risposta più pratica. Non avevo scoperto la maggior parte di quei documenti. Potrei semplicemente assegnare a questa risposta la taglia per evitare che l'altra tua risposta ottenga automaticamente la risposta. Dopotutto, la tua altra risposta è più un'opinione che una risposta, anche se mi ha motivato a tornare nei white paper, se non altro per dimostrare che posso farlo :) – Trillian
Devi essere accademico o di gruppo che è Springer "abbonato" se vuoi PDF in modo semplice. Alcuni autori pubblicano documenti leggermente modificati con altre riviste, altri no. Ecco perché la mia euristica di ricerca è cercare di seguire gli autori prima e il sito Springer è il modo semplice per ottenere rapidamente nuove informazioni. Il primo potrebbe anche valere la pena di comprarlo se si fa parte di quella roba non solo per l'algo ma per la lettura di un articolo di Stantz che afferma che il suo nuovo algo è basato su D * Lite - una cosa molto difficile da ammettere anche in modo implicito da parte di un ricercatore. – ZXX
D * Lite Spiegazione per il laico
D * inizia con aria-mosche, percorso idealistica tra Start e Goal a; gestisce gli ostacoli solo se e quando li incontra (di solito spostandosi in un nodo adiacente). Cioè - D * Lite non ha conoscenza di eventuali ostacoli fino al inizia a muoversi lungo quel percorso ideale.
Il Santo Graal con qualsiasi implementazione di percorso è quello di renderlo veloce mentre ottiene il percorso più breve, o almeno un percorso decente (oltre a gestire [tutte le varie condizioni speciali qui - per D * Lite si tratta di un mappa sconosciuta come potrebbe fare Mars Rover]).
Quindi una delle grandi sfide di D * Lite è adattarsi agli ostacoli a poco prezzo quando vengono raggiunti. Trovarli è facile: basta controllare lo stato del nodo dei vicini mentre ti sposti. Ma come adattiamo le stime dei costi della mappa esistente senza attraversare tutti i nodi ... il che potrebbe essere molto costoso?
LPA * utilizza un trucco intelligente per adattare i costi, un trucco che D * Lite ha fatto buon uso. Il nodo corrente chiede ai suoi vicini: Mi conosci meglio, pensi di essere realista riguardo me stesso? In particolare, chiede questo sul suo valore g, che è il costo noto di ottenere dal nodo iniziale a se stesso, cioè il nodo corrente. I vicini guardano il proprio g, guardano dove il nodo corrente è in relazione con loro, e quindi offrono una stima di cosa loro pensano che il suo costo dovrebbe essere. Il minimo di queste offerte è impostato come valore del rhs del nodo corrente che viene quindi utilizzato per aggiornare il suo valore g; quando stimano, i vicini tengono conto degli ostacoli scoperti (o degli spazi liberi), in modo tale che quando vengono aggiornati gli aggiornamenti g utilizzando rhs, lo fa con i nuovi ostacoli (o spazi liberi) considerati.
E una volta che abbiamo valori realistici g su tutta la linea, ovviamente, viene visualizzato un nuovo percorso più breve.
D * Lite reputato obsoleti D *, quindi non ho incluso quest'ultimo qui. –
D * non è un tipo di algoritmo per principianti e il suo caso d'uso è piuttosto limitato. sei sicuro di non aver bisogno di A * per la tua applicazione? – Donnie
Ho bisogno di un bot per navigare intorno ai muri verso un obiettivo. Il giocatore può mettere ostacoli nel modo del robot e il bot dovrebbe essere in grado di trovare un nuovo percorso in tempo reale. D * è buono per cambiare ambienti come questo, giusto? – tehalynn
Sono completamente d'accordo. Ho implementato A * molte volte e su un'ampia varietà di grafici e ho voluto implementare D * (lite) per qualche tempo. Ci sono due o tre white paper sulla rete, ma devo ancora riuscire a ricavare qualcosa di utile da quelle illeggibili descrizioni matematiche. – Trillian