There are links to some papers on D* here, but they're a bit too mathematical for me. Is there any information on D*/D* Lite more geared towards beginners?
views:
415answers:
4
+1
A:
I came up with this
http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf and this
http://www.cs.cmu.edu/~maxim/docs/dlitemap_iros02.pdf
I hope those link will help you :)
Edit: After posting I noticed that the links I gave you were in the link you pointed out as well. Nevertheless I found those directly on Google. Anyway I've looked them up a bit and they don't seem to be that complicated. If you know A* well you should manage to understand D* as well.
From experience I can tell you that A* can be used for what you want as well.
Sanctus2099
2010-07-27 13:44:56
Yeah, those are the whitepapers I've found myself by googling. The explanations are in impenetrable maths jargon and the pseudocode isn't much better. As for using A*, I have a highly optimized implementation in my RTS game, but it's not fast enough such a highly dynamic world.
Trillian
2010-07-27 15:48:12
+3
A:
Wikipedia has an article on the topic: http://en.wikipedia.org/wiki/D*
Also a D* Lite implementation in C is available from Sven Koenig's page: http://idm-lab.org/code/dstarlite.tar However I find the impenetrable math much easier to read than the C source code ;-)
Another implementation of D* Lite (in C++) is available here: http://code.google.com/p/dstarlite/
michid
2010-07-28 21:12:52
@michid: +1 I haven't searched myself, but judging from the answers here, and reading the wiki article, this seems to be the closest thing available to what the OP wants.
Merlyn Morgan-Graham
2010-08-02 21:51:04
+4
A:
Well if pseudo code is hard for you (you don't have to read theorems and proofs - pseudo code is pretty straight forward if you know standard algorhitms) and you complain against published C and C++ code then I guess you'll need to go doing something else :-)
Seriously, don't expect that someone can teach you a top grade algorithm in a few web paragraphs. Take a pen and paper and write, draw and follow on paper what's going on. You may have to read something twice and google one or two references to get to know a few concepts around it, and there's no need to dig in the theorems and proofs at all - unless you hope to prove the author wrong that is :-))
Can't go forward without some more math - c'est la vie. Imagine that you asked someone to teach you what on earth is matrix inversion but you don't know what are vectors. No one could help you till you learned enough of the math context first.
ZXX
2010-07-29 14:31:42
There are so many clear explanations of A* on the net that I'm really surprised that there are none for D*. I know D* is a step over A* in terms of complexity, but I expected someone would write an explanation for the layman. Yeah, this is laziness, I know, and as there are no suitable answers I'll dive in the papers again. I just feel a math-full whitepaper isn't the best way to develop an intuitive understanding of an algorithm.
Trillian
2010-08-02 14:31:40
There's a step between asking about matrix inversions when you don't know about vectors and asking about D* when you _know_ about A*.
zneak
2010-08-02 21:42:55
+1
A:
Having said that, why not add a few more papers, yes they have math as well :-) but I'll try to get some more recent stuff. People usually get better at explaining their own work as the time goes by, so the focus is on Stentz, Likhachev and Koenig
- Stentz,2007 - Field D* - claims to be better than D* Lite :-)
- Stentz,2010 - Imitation Lerning- mostly talk about combining Field D* and LEARCH
- Ratliff,2009 - LEARCH - also talks about combining with Field D* - yes a cyclic ref :-)
- Likhachev,2005 - Anytime D* - with Stentz as well
- Yanyan,2009 - BDD-Based Dynamic A*
- Koenig,2008 - Comparing real-time and incremental heuristic search
ZXX
2010-07-30 00:23:51
Thanks for the more practical answer. I hadn't found out most of those papers. I might just award this answer the bounty to prevent your other answer to get it automatically. After all, your other answer is more of an opinion than an answer, even if it motivated me to dive back in the whitepapers, if only to prove I can do so :)
Trillian
2010-08-02 14:43:00
You'll need to be on academic or corp net that is Springer "subscriber" if you want PDF-s the easy way. Some authors publish slightly changed papers with other journals, some don't. That's why my search heuristics is to try to follow authors first and Springer site is the easy way to get fresh info fast. The first one might even be worth buying if you are into that stuff not just for the algo but for reading a Stantz paper stating that his new algo is based on D* Lite - very hard thing for a researcher to admit even implicitly.
ZXX
2010-08-02 23:35:28