En quoi les algorithmes de recherche de chemins à la fine pointe de la technologie pour changer les graphes (D *, D * -Lite, LPA *, etc.) diffèrent-ils?

De nombreux algorithmes de recherche de trajectoire ont été développés ces dernières années. Ils permettent de calculer la meilleure trajectoire en réponse aux changements de graphes beaucoup plus rapidement que A * - en quoi consistent-ils et en quoi diffèrent-ils? S'agit-il de situations différentes ou certaines obsolètes?

Ce sont ceux que j'ai pu trouver jusqu'à présent:

• D * (1994)
• D * ciblé (1995)
• DynamicSWSF-FP (1996)
• LPA (1997)
• LPA * / Incremental A * (2001)
• D * Lite (2002)
• SetA * (2002)
• HPA * (2004)
• À tout moment D * (2005)
• PRA * (2005)
• Champ D * (2007)
• Thêta * (2007)
• HAA * (2008)
• GAA * (2008)
• LEARCH (2009)
• BDDD * (2009 - Je ne peux pas accéder à ce document: |)
• Phi * incrémental (2009)
• GFRA * (2010)
• MTD * -Lite (2010)
• Arbre-AA * (2011)

Je ne sais pas lequel de ces problèmes s'applique à mon problème spécifique - je les lirai tous si nécessaire, mais cela me ferait gagner beaucoup de temps si quelqu'un pouvait rédiger un résumé.

Mon problème spécifique: j'ai une grille avec un début, une finition et quelques murs. J'utilise actuellement A * pour trouver le meilleur chemin du début à la fin.

L'utilisateur déplacera alors un mur et je devrai recalculer l'intégralité du chemin. L' étape "move-wall / recalculate-path" se produit plusieurs fois de suite; je recherche donc un algorithme capable de recalculer rapidement le meilleur chemin sans avoir à exécuter une itération complète de A *.

Cependant, je ne cherche pas nécessairement une modification de A * - il pourrait s'agir d'un algorithme complètement séparé.

Alors, j'ai feuilleté les journaux, et c'est ce que j'ai brillé. S'il y a quelqu'un de plus informé en la matière, corrigez-moi si je me trompe (ou ajoutez votre propre réponse, et je l'accepterai à la place!) .

Des liens vers chaque article peuvent être trouvés dans la question-post ci-dessus.

• Recalculs simples
  • D * (aka Dynamic A * ) (1994): Lors de la première exécution, D * fonctionne de manière très similaire à A *, trouvant le meilleur chemin du début à la fin très rapidement. Cependant, à mesure que l'unité se déplace de bout en bout, si le graphique change, D * est en mesure de recalculer très rapidement le meilleur tracé de la position de cette unité à la fin, beaucoup plus rapidement que d'exécuter à nouveau A * à partir de la position de cette unité. D *, cependant, a la réputation d'être extrêmement complexe et a été complètement obsolète par le beaucoup plus simple D * -Lite.
  • Focused D * (1995): Une amélioration de D * pour le rendre plus rapide / "plus de temps réel". Je ne trouve aucune comparaison avec D * -Lite, mais étant donné qu'il est plus ancien et que l'on parle beaucoup plus de D * -Lite, je suppose que D * -Lite est en quelque sorte meilleur.
  • DynamicSWSF-FP (1996): Stocke la distance entre chaque nœud et le nœud d'arrivée. A une grande configuration initiale pour calculer toutes les distances. Une fois les modifications apportées au graphique, il ne peut mettre à jour que les nœuds dont les distances ont changé. Sans lien avec A * et D *. Utile lorsque vous souhaitez trouver la distance entre plusieurs nœuds à l'arrivée après chaque modification; sinon, LPA * ou D * -Lite sont généralement plus utiles.
  • LPA * / incrémental A * (2001): LPA * (planification permanente A *) , également connu sous le nom incrémental A * (et parfois, prêter à confusion, comme "LPA" , mais il n'a aucun rapport avec l'autre algorithme nommé LPA) est un combinaison de DynamicSWSF-FP et A *. Au premier passage, c'est exactement la même chose que A *. Cependant, après des modifications mineures du graphique, les recherches ultérieures de la même paire début / fin peuvent utiliser les informations des exécutions précédentes pour réduire considérablement le nombre de nœuds à examiner, par rapport à A *. C’est exactement mon problème, il semble donc que LPA * sera mon meilleur ajustement. LPA * diffère de D * en ce sens qu'il trouve toujours le meilleur chemin du même début à la même arrivée; il n'est pas utilisé lorsque le point de départ se déplace(telles que les unités se déplaçant sur le meilleur chemin initial) . Pourtant...
  • D * -Lite (2002): Cet algorithme utilise LPA * pour imiter D *; c'est-à-dire qu'il utilise LPA * pour trouver le nouveau meilleur chemin pour une unité au fur et à mesure qu'elle avance sur le meilleur chemin initial et que le graphique change. D * -Lite est considéré comme beaucoup plus simple que D *, et comme il tourne toujours au moins aussi vite que D *, il est complètement obsolète. Ainsi, il n’ya jamais de raison d’utiliser D *; utilisez plutôt D * -Lite.
• Mouvement à tout angle
  • Champ D * (2007): variante de D * -Lite qui ne contraint pas le mouvement à une grille; c'est-à-dire que le meilleur chemin peut avoir l'unité se déplaçant selon n'importe quel angle, pas seulement 45 (ou 90) degrés entre les points de la grille. A été utilisé par la NASA pour rechercher les rovers martiens.
  • Thêta * (2007): variante de A * qui donne de meilleurs chemins (plus courts) que le champ D *. Toutefois, comme il est basé sur A * plutôt que sur D * -Lite, il ne dispose pas des fonctionnalités de réplication rapide proposées par Field D *. Voir aussi .
  • Incrémental Phi * (2009): Le meilleur des deux mondes. Une version de Theta * qui est incrémentale (aka permet une replanification rapide)
• Déplacement de points cibles
  • GAA * (2008): GAA * (A généralisé adaptatif *) est une variante de A * qui gère les points cibles en mouvement. C'est une généralisation d'un algorithme encore plus ancien appelé "Moving Target Adaptive A *"
  • GRFA * (2010): La GFRA * (A * généralisée de récupération de franges ) apparaît (?) Comme une généralisation de la GAA * à des graphes arbitraires (c'est -à -dire non restreints à la 2D) en utilisant les techniques d'un autre algorithme appelé FRA *.
  • MTD * -Lite (2010): MTD * -Lite (cible mobile D * -Lite) est "une extension de D * Lite qui utilise le principe de la récupération généralisée de franges A *" pour effectuer une réplication rapide des recherches de cibles mobiles.
  • Tree-AA * (2011): (???) Apparaît comme un algorithme de recherche de terrain inconnu, mais est basé sur Adaptive A *, comme tous les autres algorithmes de cette section, je l'ai donc mis ici. Je ne sais pas comment cela se compare aux autres de cette section.
• Rapide / Sous-optimal
  • Anytime D * (2005): Il s'agit d'une variante "Anytime" de D * -Lite, réalisée en combinant D * -Lite avec un algorithme appelé Anytime Repairing A * . Un algorithme "À tout moment" est un algorithme qui peut fonctionner avec toutes les contraintes de temps - il trouvera très rapidement un chemin très sous-optimal, puis l'améliorera au fur et à mesure que le temps imparti lui est attribué.
  • HPA * (2004): HPA * (recherche de trajectoire hiérarchique A *) permet de rechercher la trajectoire d'un grand nombre d'unités sur un graphique de grande taille, comme dans les jeux vidéo RTS (stratégie en temps réel) . Ils auront tous des emplacements de départ différents et potentiellement des lieux d'arrivée différents. HPA * divise le graphique en une hiérarchie afin de trouver rapidement des chemins "presque optimaux" pour toutes ces unités beaucoup plus rapidement que d'exécuter A * sur chacune d'elles individuellement. Voir également
  • PRA * (2005): D'après ce que j'ai compris, PRA * (Partial Refinement A *) résout le même problème que HPA *, mais d'une manière différente. Ils ont tous deux "des performances similaires."
  • HAA * (2008): HAA * (Hierarchical Annotated A *) est une généralisation de HPA * qui permet de limiter le franchissement de certaines unités sur certains terrains (par exemple, un petit chemin que certaines unités peuvent emprunter mais pas les plus grandes. ou un trou que seules les unités volantes peuvent traverser, etc.)
• Autre / Inconnu
  • LPA (1997): Le LPA (algorithme de recherche de parcours sans boucle) apparaît comme un algorithme de routage lié de manière marginale aux problèmes résolus par les autres algorithmes. Je ne le mentionne que parce que ce document est référencé de manière source de confusion (et à tort) à plusieurs endroits sur Internet en tant que document introduisant LPA *, ce qu'il n'est pas.
  • LEARCH (2009): LEARCH est une combinaison d'algorithmes d'apprentissage automatique utilisés pour apprendre aux robots à trouver par eux-mêmes des chemins quasi optimaux. Les auteurs suggèrent de combiner LEARCH avec le champ D * pour de meilleurs résultats.
  • BDDD * (2009): ??? Je ne peux pas accéder au papier.
  • SetA * (2002): ??? Apparemment, il s’agit d’une variante de A * qui effectue une recherche dans le modèle du "diagramme de décision binaire" (BDD)? Ils affirment qu'il fonctionne "plusieurs ordres de grandeur plus rapidement que A *" dans certains cas. Toutefois, si je comprends bien, il s’agit de cas où chaque nœud du graphique a plusieurs arêtes?

Compte tenu de tout cela, il semble que LPA * soit la meilleure solution à mon problème.

L'utilisation de D *, D * -Lite ou de l'un des algorithmes incrémentaux de cette catégorie constitue une grande réserve (et il est à noter que cette mise en garde est rarement mentionnée dans la littérature). Ces types d'algorithmes utilisent une recherche inversée. C'est-à-dire qu'ils calculent les coûts à partir du nœud de l'objectif, comme une ondulation se propageant vers l'extérieur. Lorsque les coûts des arêtes changent (par exemple, vous ajoutez ou supprimez un mur dans votre exemple), ils disposent de diverses stratégies efficaces pour ne mettre à jour que le sous-ensemble des nœuds explorés (autrement dit «visités») affectés par les modifications.

La grande mise en garde est que l'emplacement de ces changements par rapport à l'emplacement de l'objectif fait une énorme différence pour l'efficacité des algorithmes. J'ai montré dans divers articles et ma thèse qu'il était tout à fait possible que la pire performance de l'un de ces algorithmes incrémentaux soit pire que de jeter toute l'information et de recommencer à zéro avec quelque chose de non incrémental comme le vieil A *.

Lorsque les informations de coût modifiées se rapprochent du périmètre du front de recherche en expansion (la région "visitée"), peu de chemins doivent être modifiés et les mises à jour incrémentielles sont rapides. Un exemple pertinent est un robot mobile avec des capteurs attachés à son corps. Les capteurs ne voient que le monde à proximité du robot et, par conséquent, les changements se produisent dans cette région. Cette région est le point de départ de la recherche, et non l'objectif. Ainsi, tout se passe bien et les algorithmes sont très efficaces pour mettre à jour le chemin optimal pour corriger les modifications.

Lorsque les informations de coût modifiées sont proches de l'objectif de la recherche (ou si votre scénario voit les emplacements de changement d'objectif, et pas seulement le début), ces algorithmes subissent un ralentissement catastrophique. Dans ce scénario, presque toutes les informations enregistrées doivent être mises à jour, car la région modifiée est si proche de l'objectif que presque tous les chemins précalculés transforment les modifications et doivent être réévalués. En raison de la surcharge de stockage d'informations supplémentaires et de calculs pour effectuer des mises à jour incrémentielles, une réévaluation à cette échelle est plus lente qu'un nouveau départ.

Étant donné que votre exemple de scénario semble permettre à l'utilisateur de déplacer le mur de son choix, vous rencontrerez ce problème si vous utilisez D *, D * -Lite, LPA *, etc. Les performances temporelles de votre algorithme seront variables, en fonction de l'utilisateur. contribution. En général, "c'est une mauvaise chose" ...

À titre d'exemple, le groupe d'Alonzo Kelly à la CMU avait un programme fantastique appelé PerceptOR, qui tentait de combiner des robots terrestres avec des robots aériens, partageant tous des informations de perception en temps réel. Lorsqu'ils ont essayé d'utiliser un hélicoptère pour fournir des mises à jour des coûts en temps réel au système de planification d'un véhicule terrestre, ils se sont heurtés à ce problème, car l'hélicoptère pouvait voler en avant du véhicule au sol, les changements de coûts se rapprochant de l'objectif, ce qui ralentissait bas leurs algorithmes. Ont-ils discuté de cette observation intéressante? Non. Au final, le mieux qu'ils aient pu faire a été de faire voler l'hélicoptère directement au-dessus du véhicule terrestre, ce qui en faisait le mât de détection le plus cher au monde. Bien sûr, je suis mesquin. Mais c’est un gros problème dont personne ne veut parler - et ils devraient,

Il y a seulement une poignée de papiers qui en parlent, principalement par moi. Parmi les articles écrits par les auteurs ou les étudiants des auteurs des articles originaux énumérés dans cette question, je peux penser à un seul qui mentionne réellement ce problème. Likhachev et Ferguson suggèrent d'essayer d'estimer l'ampleur des mises à jour requises et de vider les informations stockées si la mise à jour incrémentielle prend plus de temps qu'un nouveau départ. Cette solution de contournement est assez judicieuse, mais il en existe d’autres également. Ma thèse de doctorat généralise une approche similaire pour un large éventail de problèmes informatiques et dépasse le cadre de cette question. Toutefois, vous trouverez peut-être les références utiles car elle offre une vue d'ensemble complète de la plupart de ces algorithmes et plus encore. Voir http://db.acfr.usyd.edu.au/download.php/Allen2011_Thesis.pdf?id=2364 pour plus de détails.

L'idée principale est d'utiliser un algorithme incrémental, capable de tirer parti des calculs précédents lorsque la route calculée initiale est bloquée. Ceci est souvent étudié dans le contexte des robots, de la navigation et de la planification.

Koenig & Likkachev, Replanification rapide pour la navigation en terrain inconnu, Transactions IEEE sur la robotique, vol. 21, n ° 3, juin 2005 présente D * Lite. Il semble prudent de dire que D * est obsolète en ce sens que D * Lite est toujours aussi rapide que D *. De plus, D * est complexe, difficile à comprendre, à analyser et à étendre. La figure 9 donne le pseudocode pour D * Lite et le tableau 1 montre les résultats expérimentaux avec D * Lite comparés à BFS, A vers l'arrière *, A * en aval, DynamicSWSF-P et D *.

Je ne connais pas les nouveaux algorithmes que vous avez énumérés (Anytime D *, Field D *, LEARCH). Récemment, j'ai vu un robot qui utilisait D * Lite pour la planification dans un environnement comportant des marcheurs aléatoires. En ce sens, je ne pense pas que D * Lite soit obsolète. Pour votre problème pratique, je suppose qu’il n’ya aucun mal à essayer la méthode d’ingénierie habituelle: adoptez une approche et, si elle ne correspond pas à vos besoins, essayez une autre solution (plus complexe).

J'aimerais ajouter quelque chose sur l'exploration rapide d'arbres randomisés, ou RRT. L’idée de base fait l’objet de bonnes discussions partout sur Internet, mais il est probablement prudent de commencer par les liens de la page Wikipedia et par les articles originaux de Kuffner et LaValle sur le sujet.

La caractéristique la plus importante des RRT est qu’ils peuvent gérer des espaces réels de très grande dimension sans être étouffés. Ils peuvent gérer la dynamique, ne sont pas optimaux mais sont probabilistes (garantis pour réussir si possible à mesure que le temps de calcul passe à l'infini), et sont capables de gérer des cibles en mouvement. Certaines extensions leur permettent de travailler dans des espaces non statiques, la meilleure de ces tâches étant le travail RRT multipartite que j'ai lié ci-dessous.

• 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

Les structures de données appelées oracles de distance traitent de tels problèmes. Cependant, la plupart des résultats de recherche ne concernent que les graphiques statiques .

Si les graphiques sont des grilles (et donc des surfaces planes), il existe des structures de données dynamiques (il est difficile de savoir si les constantes sont suffisamment petites pour l'application en question):

Les plus courts chemins exacts:

Jittat Fakcharoenphol, Satish Rao: Graphes plans, arêtes de pondération négatives, chemins les plus courts et temps quasi linéaire. J. Comput. Syst. Sci. 72 (5): 868-889 (2006)

Les plus courts chemins approximatifs:

Philip N. Klein, Sairam Subramanian: Schéma d’approximation entièrement dynamique pour les chemins les plus courts dans les graphes plans. Algorithmica 22 (3): 235-249 (1998)

Ittai Abraham, Shiri Chechik, Cyril Gavoille: Des oracles de distance approximatifs entièrement dynamiques pour les graphes plans via des étiquettes de distance interdites. STOC 2012: 1199-1218

À l'école, j'ai essayé l' optimisation de la colonie de fourmis . Dans certains textes, il a été présenté comme une solution permettant de modifier en permanence les graphiques, les réseaux de routage, etc. Il ne s’agit pas d’une solution technique, mais d’une adaptation de la façon dont les fourmis surmontent les obstacles en répandant des phéromones pour marquer les bons et les mauvais chemins. Je ne sais pas si cela fonctionne pour votre problème, mais je pense que c'est un point de vue intéressant.