Hay enlaces a algunos documentos en D * here, pero son un poco demasiado matemáticos para mí. ¿Hay alguna información sobre D */D * Lite más orientada a los principiantes?¿Dónde puedo encontrar información sobre el algoritmo de determinación de ruta D * o D * Lite?
me ocurrió con esta
http://idm-lab.org/bib/abstracts/papers/aaai02b.pdf y esto
http://www.cs.cmu.edu/~maxim/docs/dlitemap_iros02.pdf
espero que los enlace le ayudará a :)
Editar: Después de publicar me di cuenta de que los enlaces que he dado estabas en el enlace que señaló fuera también Sin embargo, los encontré directamente en Google. De todos modos los he buscado un poco y no parecen ser tan complicados. Si conoces bien A *, también debes entender D *.
Por experiencia, puedo decirle que A * también se puede usar para lo que desee.
Sí, esos son los libros blancos que he encontrado al buscar en Google. Las explicaciones están en una jerga matemática impenetrable y el pseudocódigo no es mucho mejor. En cuanto a usar A *, tengo una implementación altamente optimizada en mi juego RTS, pero no es lo suficientemente rápido como un mundo altamente dinámico. – Trillian
Wikipedia tiene un artículo sobre el tema: http://en.wikipedia.org/wiki/D*
También una aplicación D * Lite en C está disponible en la página de Sven Koenig: http://idm-lab.org/code/dstarlite.tar Sin embargo me parece la matemática impenetrable mucho más fácil de leer que el código fuente de C; -)
Otra aplicación de D * Lite (en C++) está disponible aquí: http://code.google.com/p/dstarlite/
+1 No he buscado yo mismo, pero a juzgar por las respuestas aquí, y leyendo el artículo de la wiki, esto parece ser lo más cercano a lo que OP quiere. –
Bueno, si pseudo código es difícil para usted (usted no tiene que leer teoremas y demostraciones - pseudo código es bastante sencillo si conoce algorhitms estándar) y se queja contra el código C y C++ publicado, entonces supongo que tendrá que hacer otra cosa :-)
En serio, no espere que alguien le pueda enseñar un algoritmo de grado superior en unos pocos párrafos web. Tome un bolígrafo y papel y escriba, dibuje y siga en papel lo que está sucediendo. Puede que tenga que leer algo dos veces y buscar en Google una o dos referencias para conocer algunos conceptos a su alrededor, y no hay necesidad de profundizar en los teoremas y pruebas, a menos que espere probar que el autor está equivocado :-))
No se puede avanzar sin más matemáticas - c'est la vie. Imagina que le pides a alguien que te enseñe qué es la inversión de matrices, pero no sabes qué son vectores. Nadie podría ayudarlo hasta que haya aprendido lo suficiente sobre el contexto matemático primero.
Hay tantas explicaciones claras de A * en la red que estoy realmente sorprendido de que no haya ninguna para D *. Sé que D * es un paso más que A * en términos de complejidad, pero esperaba que alguien escribiera una explicación para el profano. Sí, esto es pereza, lo sé, y como no hay respuestas adecuadas, volveré a bucear en los periódicos. Siento que un libro blanco completo de matemáticas no es la mejor manera de desarrollar una comprensión intuitiva de un algoritmo. – Trillian
Hay un paso entre preguntar acerca de las inversiones de la matriz cuando no sabe acerca de los vectores y preguntar acerca de D * cuando conoce _ acerca de A *. – zneak
Habiendo dicho eso, ¿por qué no agregar algunos documentos más, sí, también tienen matemática :-) pero intentaré obtener algunas cosas más recientes.La gente por lo general mejoran en explicar su propio trabajo como el que pasa el tiempo, por lo que la atención se centra en Stentz, Likhachev y Koenig
Gracias por la respuesta más práctica. No había encontrado la mayoría de esos documentos. Tal vez otorgue a esta respuesta la recompensa para evitar que tu otra respuesta la obtenga automáticamente. Después de todo, tu otra respuesta es más una opinión que una respuesta, incluso si me motivó a bucear en los libros blancos, aunque sea para demostrar que puedo hacerlo :) – Trillian
Tendrás que estar en una red académica o de corp que es "suscriptor" de Springer si quiere PDF-s de la manera más fácil. Algunos autores publican trabajos ligeramente modificados con otras revistas, otros no. Es por eso que mi heurística de búsqueda es intentar seguir a los autores primero y el sitio de Springer es la manera fácil de obtener información actualizada rápidamente. El primero incluso podría valer la pena comprarlo si te interesan esas cosas no solo por el algo, sino por leer un artículo de Stantz que dice que su nuevo algoritmo está basado en D * Lite, algo muy difícil de admitir para un investigador, incluso implícitamente. – ZXX
D * Lite Explicación para el lego
D * comienza con un cuervo moscas, el recorrido de idealista entre Start y Goal; maneja los obstáculos solo cuando los encuentra (usualmente moviéndose a un nodo adyacente). Es decir - D * Lite no tiene conocimiento de ningún obstáculo hasta comienza a moverse a lo largo de esa ruta ideal.
El santo grial con cualquier implementación de pathfinding es hacerlo rápido al obtener el camino más corto, o al menos un camino decente (así como manejar [todas sus diversas condiciones especiales aquí - para D * Lite se trata de una mapa desconocido como un Mars Rover podría hacer]).
Así que uno de los grandes desafíos de D * Lite es adaptarse a los obstáculos a bajo costo a medida que se alcanzan. Encontrarlos es fácil: simplemente verifica el estado del nodo de los vecinos mientras te mueves. Pero, ¿cómo adaptamos las estimaciones de costos del mapa existente sin recorrer todos los nodos ... lo que podría ser muy costoso?
LPA * utiliza un ingenioso truco para adaptar los costos, un truco que D * Lite ha dado buen uso. El nodo actual pregunta a sus vecinos: Me conoces mejor, ¿crees que soy realista acerca de mí mismo? Específicamente, pregunta esto sobre su valor g, que es el costo conocido de obtener desde el nodo inicial a sí mismo, es decir, el nodo actual. Los vecinos miran su propio g, miran dónde está el nodo actual en relación con ellos, y luego ofrecen una estimación de qué ellos piensan que su costo debería ser. El mínimo de estas ofertas se establece como el valor rhs del nodo actual que luego se usa para actualizar su valor g; al estimar, los vecinos tienen en cuenta los obstáculos descubiertos recientemente (s) (o espacios libres), de modo que cuando las actualizaciones actuales g usan rhs, lo hacen con los nuevos obstáculos (o espacios libres) contabilizados.
Y una vez que tenemos valores g realistas en todos los ámbitos, por supuesto, aparece una nueva ruta más corta.
D * Lite supuestamente obsoleto D *, así que no he incluido este último aquí. –
D * no es un tipo de algoritmo para principiantes, y su caso de uso es bastante limitado. ¿Estás seguro de que no solo necesitas A * para tu aplicación? – Donnie
Necesito un bot para navegar por las paredes hacia un objetivo. El jugador puede colocar obstáculos en el camino del bot y el robot debería ser capaz de encontrar una nueva ruta en tiempo real. D * es bueno para entornos cambiantes como este, ¿verdad? – tehalynn
Estoy totalmente de acuerdo. Implementé A * muchas veces y en una amplia variedad de gráficos y he estado deseando implementar D * (lite) durante algún tiempo también. Hay dos o tres libros blancos en la red, pero todavía tengo que gestionar la obtención de algo útil a partir de esas descripciones de matemáticas ilegibles. – Trillian