Em Caminho Constatação: uma descrição detalhada para um leigo do algoritmo D *

Question

A grande rede (de pequena tipo de gráfico mundo) eu gostaria de tratar é de natureza dinâmica, novos nós são adicionados e subtraídos freqüência. Presumivelmente usando D * sobre A * seria a melhor maneira de detectar caminhos neste ambiente dinâmico?

Como sólida é D *? teve qualquer experiência no mundo real? como um algoritmo de criptografia - é D * endurecido por lotes de revisão por pares e testes? Você usaria D * para este problema?

Answer 1

Como eu entendo, a primeira vez que executar D * ele encontra o mesmo caminho como A * com quase o mesmo tempo de execução. No entanto, quando um nó muda de valor borda ou nós são adicionados A * recomputes ALL do caminho, enquanto D * simplesmente recalcula os nós inconsistentes pela segunda vez, em vez da coisa toda.

D * algoritmo de Anthony Stentz (original whitepaper aqui ) tem sido largamente obsoleto por derivados de seu trabalho. D * Lite e LPA * são os mais comumente encontrados e são muito mais fáceis de código / implementar.

Quanto experiência no mundo real, Joseph Carsten e Art Rankin do Jet Propulsion Laboratory da NASA instalou uma versão do Campo D * usando elementos de D * Lite sobre os rovers "Spirit" e "Opportunity" (apresentação de slides de sondas usando D aqui ). Em fevereiro de 2007 foi usado para navegar plenamente as Mars Rover autonomamente.

alt texto http://asm.arc.nasa.gov/ galeria / images / generic / rover.jpg

Aparentemente D * é realmente útil no domínio da robótica porque os sensores dos robôs de bordo são constantemente re-avaliando os valores de ponta. Isso tornaria muito "batalha testada" na minha opinião.

Da mesma forma, eu encontrei um outro whitepaper que menciona o uso do algoritmo D * Lite em mobile Gaming.

Eu vou acabar com essa resposta, afirmando que eu nunca implementado D * antes, só A *. Por causa do aumento significativo na complexidade diria que D * (D * ou Lite) deve ser utilizado apenas em casos em que há uma alteração significativa e frequentes no gráfico. Você descreveu sua situação como sendo semelhante ao que então eu diria que definitivamente ir para D * Lite. Se a NASA usa-lo você pode apostar com segurança que foi exaustivamente investigado.

Answer 2

Eu tenho implementado tanto D * e A * algoritmo. Então, eu aconselhá-lo de que, se o seu mapa não tem obstáculos dinâmicos, você deve implementar A *. Else, implementar D *. Para a razão principal é: Na primeira pesquisa, D * calcula todos os nós no mapa, em seguida, mostra-lhe o caminho mais curto, enquanto que A * calcula apenas uma área limitada em torno de metas e começar pontos no mapa. Assim, é muito mais rápido do D *. No ambiente dinâmico, D * é mais rápido e mais eficiente do que a A *. Porque no caminho robô vai, se ele detecta um novo obstáculo, ele só atualiza alguns nós ao redor do obstáculo inesperado. Enquanto, A * calcula voltará a todas as coisas.