Como os algoritmos de busca de caminhos de última geração para alterar gráficos (D *, D * -Lite, LPA *, etc) diferem?

Muitos algoritmos de busca de caminhos foram desenvolvidos nos últimos anos, que podem calcular o melhor caminho em resposta a alterações de gráficos muito mais rapidamente que A * - o que são e como diferem? Eles são para situações diferentes, ou alguns outros obsoletos?

Estes são os que consegui encontrar até agora:

• D * (1994)
• Focado D * (1995)
• DynamicSWSF-FP (1996)
• LPA (1997)
• LPA * / Incremental A * (2001)
• D * Lite (2002)
• SetA * (2002)
• HPA * (2004)
• A qualquer momento D * (2005)
• PRA * (2005)
• Campo D * (2007)
• Teta * (2007)
• HAA * (2008)
• GAA * (2008)
• LEARCH (2009)
• BDDD * (2009 - Não consigo acessar este documento: |)
• Phi Incremental * (2009)
• GFRA * (2010)
• MTD * -Lite (2010)
• Árvore-AA * (2011)

Não tenho certeza de quais delas se aplicam ao meu problema específico - vou ler todas, se necessário, mas pouparia muito tempo se alguém pudesse escrever um resumo.

Meu problema específico: eu tenho uma grade com um começo, um acabamento e algumas paredes. Atualmente, estou usando A * para encontrar o melhor caminho do início ao fim.

O usuário moverá uma parede e eu tenho que recalcular todo o caminho novamente. A etapa "move-wall / recalculate-path" acontece várias vezes seguidas, por isso estou procurando um algoritmo capaz de recalcular rapidamente o melhor caminho sem precisar executar uma iteração completa de A *.

No entanto, não estou necessariamente procurando uma alteração em A * - poderia ser um algoritmo completamente separado.

Então, eu olhei os papéis, e é isso que eu brilhava. Se houver alguém mais qualificado no assunto, corrija-me se eu estiver errado (ou adicione sua própria resposta, e eu a aceitarei!) .

Os links para cada artigo podem ser encontrados no post de perguntas acima.

• Recálculos simples
  • D * (também conhecido como Dynamic A * ) (1994): Na execução inicial, o D * é executado de maneira muito semelhante ao A *, encontrando o melhor caminho do início ao fim muito rapidamente. No entanto, à medida que a unidade se move do início ao fim, se o gráfico mudar, o D * poderá recalcular muito rapidamente o melhor caminho da posição dessa unidade para o acabamento, muito mais rápido do que simplesmente executar o A * da posição dessa unidade novamente. D *, no entanto, tem uma reputação de ser extremamente complexo e foi completamente obsoleto pelo muito mais simples D * -Lite.
  • D * focado (1995): Uma melhoria no D * para torná-lo mais rápido / "mais em tempo real". Não consigo encontrar nenhuma comparação com o D * -Lite, mas, como isso é mais antigo e o D * -Lite é muito mais comentado, presumo que o D * -Lite seja de alguma forma melhor.
  • DynamicSWSF-FP (1996): Armazena a distância de cada nó ao nó final. Possui uma grande configuração inicial para calcular todas as distâncias. Após as alterações no gráfico, ele pode atualizar apenas os nós cujas distâncias foram alteradas. Não relacionado a A * e D *. Útil quando você deseja encontrar a distância de vários nós até o final após cada alteração; caso contrário, LPA * ou D * -Lite são normalmente mais úteis.
  • LPA * / Incremental A * (2001): LPA * (Planejamento ao longo da vida A *) , também conhecido como Incremental A * (e, às vezes, confusamente, como "LPA", embora não tenha relação com o outro algoritmo chamado LPA) é um combinação de DynamicSWSF-FP e A *. Na primeira execução, é exatamente o mesmo que A *. Após pequenas alterações no gráfico, no entanto, pesquisas subsequentes do mesmo par de início / término são capazes de usar as informações de execuções anteriores para reduzir drasticamente o número de nós que precisam ser examinados, em comparação com A *. Esse é exatamente o meu problema, então parece que o LPA * será o meu melhor ajuste. O LPA * difere de D *, pois sempre encontra o melhor caminho desde o mesmo início até o mesmo fim; não é usado quando o ponto inicial está se movendo(como unidades movendo-se ao longo do melhor caminho inicial) . Contudo...
  • D * -Lite (2002): Este algoritmo usa LPA * para imitar D *; ou seja, ele usa LPA * para encontrar o novo melhor caminho para uma unidade, à medida que se move ao longo do melhor caminho inicial e o gráfico muda. D * -Lite é considerado muito mais simples que D * e, como sempre é executado pelo menos tão rápido quanto D *, tem D * completamente obsoleto. Portanto, nunca há motivo para usar D *; use D * -Lite.
• Qualquer ângulo de movimento
  • Campo D * (2007): Uma variante de D * -Lite que não restringe o movimento a uma grade; isto é, o melhor caminho pode fazer com que a unidade se mova em qualquer ângulo, e não apenas 45 (ou 90) graus entre os pontos da grade. Foi usado pela NASA para encontrar os rovers de Marte.
  • Theta * (2007): Uma variante de A * que fornece caminhos melhores (mais curtos) que o Campo D *. No entanto, como é baseado em A *, e não em D * -Lite, ele não possui os recursos de replanejamento rápido que o Campo D * possui. Veja também .
  • Phi Incremental * (2009): O melhor dos dois mundos. Uma versão do Theta * que é incremental (também conhecida como replanejamento rápido)
• Mover pontos de destino
  • GAA * (2008): GAA * (Adaptativo generalizado A *) é uma variante de A * que lida com pontos de destino em movimento. É uma generalização de um algoritmo ainda mais antigo chamado "Moving Target Adaptive A *"
  • GRFA * (2010): GFRA * (Recuperação generalizada de franjas A *) parece (?) Ser uma generalização do GAA * para gráficos arbitrários (isto é, não restrito a 2D) usando técnicas de outro algoritmo chamado FRA *.
  • MTD * -Lite (2010): MTD * -Lite (Alvo Móvel D * -Lite) é "uma extensão do D * Lite que usa o princípio por trás do Generalized Fringe-Retrieving A *" para realizar buscas de alvos móveis de replanejamento rápido.
  • Tree-AA * (2011): (???) Parece ser um algoritmo para pesquisa de terrenos desconhecidos, mas é baseado no Adaptive A *, como todos os outros algoritmos desta seção, então coloquei aqui. Não tenho certeza de como ele se compara aos outros nesta seção.
• Rápido / Subótimo
  • A qualquer momento D * (2005): Esta é uma variante "A qualquer momento" do D * -Lite, feita pela combinação do D * -Lite com um algoritmo chamado Anytime Repairing A * . Um algoritmo "a qualquer momento" é aquele que pode ser executado sob restrições de tempo - ele encontrará um caminho muito abaixo do ideal muito rapidamente para começar, e depois aprimora esse caminho quanto mais tempo ele recebe.
  • HPA * (2004): HPA * (Hierarchical Path-Finding A *) destina-se a encontrar um grande número de unidades em um gráfico grande, como em jogos de vídeo RTS (estratégia em tempo real) . Todos eles terão locais de partida diferentes e locais finais potencialmente diferentes. O HPA * divide o gráfico em uma hierarquia para encontrar rapidamente caminhos "quase ótimos" para todas essas unidades muito mais rapidamente do que executar o A * em cada uma delas individualmente. Veja também
  • PRA * (2005): Pelo que entendi, o PRA * (Refinamento Parcial A *) resolve o mesmo problema que o HPA *, mas de uma maneira diferente. Ambos têm "características de desempenho semelhantes".
  • HAA * (2008): HAA * (Hierarchical Annotated A *) é uma generalização do HPA * que permite a passagem restrita de algumas unidades em alguns terrenos (por exemplo, um pequeno caminho pelo qual algumas unidades podem percorrer, mas as maiores não podem; ou um buraco que somente unidades voadoras possam atravessar; etc.)
• Outro / Desconhecido
  • LPA (1997): O LPA (algoritmo de localização de caminhos sem loop) parece ser um algoritmo de roteamento apenas marginalmente relacionado aos problemas que os outros algoritmos aqui resolvem. Eu apenas o mencionei porque este documento é referenciado de maneira confusa (e incorreta) em vários locais da Internet como o documento que introduz o LPA *, o que não é.
  • LEARCH (2009): LEARCH é uma combinação de algoritmos de aprendizado de máquina, usados ​​para ensinar aos robôs como encontrar caminhos quase ótimos por conta própria. Os autores sugerem a combinação do LEARCH com o Campo D * para obter melhores resultados.
  • BDDD * (2009): ??? Não consigo acessar o papel.
  • SetA * (2002): ??? Aparentemente, essa é uma variante de A * que pesquisa sobre o modelo "gráfico de decisão binária" (BDD) do gráfico? Eles alegam que ele executa "várias ordens de magnitude mais rapidamente que A *" em alguns casos. No entanto, se estou entendendo corretamente, esses casos são quando cada nó no gráfico tem muitas arestas?

Diante de tudo isso, parece que o LPA * é o mais adequado para o meu problema.

Há uma grande ressalva ao usar D *, D * -Lite ou qualquer um dos algoritmos incrementais nesta categoria (e vale a pena notar que essa ressalva é raramente mencionada na literatura). Esses tipos de algoritmos usam uma pesquisa invertida. Ou seja, eles calculam os custos para fora do nó da meta, como uma ondulação se espalhando para fora. Quando os custos das arestas mudam (por exemplo, você adiciona ou remove uma parede no seu exemplo), todos eles têm várias estratégias eficientes para atualizar apenas o subconjunto dos nós explorados (também conhecidos como 'visitados') que são afetados pelas alterações.

A grande ressalva é que a localização dessas mudanças em relação à localização da meta faz uma enorme diferença para a eficiência dos algoritmos. Eu mostrei em vários artigos e minha tese que é perfeitamente possível que o pior desempenho de qualquer um desses algoritmos incrementais seja pior do que jogar fora todas as informações e começar de novo com algo não incremental, como o simples A * antigo.

Quando as informações de custo alteradas estão próximas do perímetro da frente de pesquisa em expansão (a região 'visitada'), poucos caminhos precisam ser alterados e as atualizações incrementais são rápidas. Um exemplo pertinente é um robô móvel com sensores conectados ao seu corpo. Os sensores apenas veem o mundo perto do robô e, portanto, as mudanças ocorrem nesta região. Essa região é o ponto de partida da pesquisa, não o objetivo, portanto tudo funciona bem e os algoritmos são muito eficientes na atualização do caminho ideal para corrigir as alterações.

Quando as informações de custo alteradas estão próximas do objetivo da pesquisa (ou o seu cenário vê os locais de alteração do objetivo, não apenas o início), esses algoritmos sofrem uma desaceleração catastrófica. Nesse cenário, quase todas as informações salvas precisam ser atualizadas, porque a região alterada está tão próxima da meta que quase todos os caminhos pré-calculados passam pelas alterações e devem ser reavaliados. Devido à sobrecarga de armazenar informações e cálculos extras para fazer atualizações incrementais, uma reavaliação nessa escala é mais lenta que um novo começo.

Como o cenário de exemplo parece permitir ao usuário mover qualquer barreira que desejar, você sofrerá esse problema se usar D *, D * -Lite, LPA * etc. O desempenho do tempo do seu algoritmo será variável, dependendo do usuário entrada. Em geral, "isso é uma coisa ruim" ...

Como exemplo, o grupo de Alonzo Kelly na CMU tinha um programa fantástico chamado PerceptOR, que tentava combinar robôs terrestres com robôs aéreos, todos compartilhando informações de percepção em tempo real. Quando tentaram usar um helicóptero para fornecer atualizações de custos em tempo real ao sistema de planejamento de um veículo terrestre, eles enfrentaram esse problema porque o helicóptero podia voar à frente do veículo terrestre, vendo mudanças de custo mais próximas da meta e, assim, diminuindo a velocidade abaixo seus algoritmos. Eles discutiram essa observação interessante? Não. No final, o melhor que conseguiram foi fazer o helicóptero voar diretamente acima do veículo terrestre - tornando-o o mastro de sensor mais caro do mundo. Claro, estou sendo mesquinho. Mas é um grande problema que ninguém quer falar - e deveria,

Existem apenas alguns documentos que discutem isso, principalmente por mim. Dos artigos escritos pelos autores ou estudantes dos autores dos artigos originais listados nesta pergunta, posso pensar em apenas um que realmente mencione esse problema. Likhachev e Ferguson sugerem tentar estimar a escala de atualizações necessárias e liberar as informações armazenadas se estima-se que a atualização incremental leve mais tempo do que um novo começo. Esta é uma solução bastante sensata, mas também existem outras. Meu doutorado generaliza uma abordagem semelhante em uma ampla gama de problemas computacionais e está indo além do escopo desta pergunta. No entanto, você pode achar úteis as referências, pois ele tem uma visão geral completa da maioria desses algoritmos e muito mais. Veja http://db.acfr.usyd.edu.au/download.php/Allen2011_Thesis.pdf?id=2364 para detalhes.

A idéia principal é usar um algoritmo incremental, capaz de tirar proveito dos cálculos anteriores quando a rota calculada inicial for bloqueada. Isso é frequentemente investigado no contexto de robôs, navegação e planejamento.

Koenig & Likkachev, replanejamento rápido para navegação em terrenos desconhecidos, IEEE Transactions on Robotics, vol. 21, nº 3, junho de 2005 apresenta o D * Lite. Parece seguro dizer que D * está desatualizado no sentido de que D * Lite é sempre tão rápido quanto D *. Além disso, o D * é complexo, difícil de entender, analisar e estender. A Figura 9 fornece o pseudocódigo para D * Lite, e a Tabela 1 mostra resultados experimentais com D * Lite em comparação com BFS, Backward A *, Forward A *, DynamicSWSF-P e D *.

Não conheço os algoritmos mais recentes que você listou (A qualquer momento D *, Campo D *, LEARCH). Muito recentemente, vi um robô que usava o D * Lite para planejar em um ambiente com caminhantes aleatórios. Nesse sentido, não acho que o D * Lite esteja desatualizado. Para o seu problema prático, acho que não há mal em tentar a maneira usual de engenharia: adote alguma abordagem e, se ela não atender às suas necessidades, tente outra coisa (mais complexa).

Gostaria de acrescentar algo sobre árvores aleatórias de exploração rápida, ou RRTs. A idéia básica tem boa discussão em toda a Internet, mas provavelmente é seguro começar com os links da página da Wikipedia e com os documentos originais de Kuffner e LaValle sobre o assunto.

A característica mais importante dos RRTs é que eles podem lidar com espaços com valor real de dimensão extremamente alta sem asfixia. Eles podem lidar com a dinâmica, não são ideais, mas são probabilisticamente completos (garantido que terão sucesso, se possível, à medida que o tempo de computação chegar ao infinito) e são capazes de lidar com alvos em movimento. Existem algumas extensões que permitem trabalhar em espaços não estáticos, o melhor dos quais parece ser o trabalho multipartido de RRT que eu vinculei abaixo.

• http://en.wikipedia.org/wiki/Rapidly_exploring_random_tree
• http://swing.adm.ri.cmu.edu/pub_files/pub4/zucker_matthew_2007_1/zucker_matthew_2007_1.pdf

As estruturas de dados chamadas oráculos a distância lidam com esses problemas. No entanto, a maioria dos resultados de pesquisa é apenas para gráficos estáticos .

Se os gráficos são grades (e, portanto, planares), existem algumas estruturas de dados dinâmicas (não está claro se as constantes são pequenas o suficiente para o aplicativo em questão):

Caminhos mais curtos exatos:

Jittat Fakcharoenphol, Satish Rao: Gráficos planares, arestas de peso negativo, caminhos mais curtos e tempo quase linear. J. Comput. Syst. Sci. 72 (5): 868-889 (2006)

Caminhos mais curtos aproximados:

Philip N. Klein, Sairam Subramanian: Um esquema de aproximação totalmente dinâmico para caminhos mais curtos em gráficos planares. Algoritmica 22 (3): 235-249 (1998)

Ittai Abraham, Shiri Chechik, Cyril Gavoille: Oráculos de distância aproximada totalmente dinâmicos para gráficos planares por meio de etiquetas de distância proibidas. STOC 2012: 1199-1218

Na escola, me envolvi com a otimização de colônias de formigas . Em alguns textos, foi apresentada como uma solução para a mudança contínua de gráficos, redes de roteamento, etc. Não é uma solução projetada, mas uma adaptação de como as formigas navegam em torno de obstáculos, espalhando feromônios para marcar bons e maus caminhos. Não tenho idéia se funciona para o seu problema, mas acho que é um ponto de vista interessante.