Algorithmes de recherche de chemin pour les cartes continues (par exemple, les polygones)
J'essaie d'étudier différents algorithmes pour un court chemin entre deux points dans un plan avec des obstacles polygonaux. La grande majorité des algorithmes que j'ai trouvés utilisent des cartes discrètes (Grid Map, graphe de visibilité, Voronoi Roadmap, etc.). Certains livres (comme « Elements of Robotics » de Ben-Ari ou « Introduction to Autonomous Robots » de Nikolaus Correll) mentionnent des cartes continues (par exemple, des données polygonales brutes), mais n'expliquent pas les algorithmes correspondants. Ils revendiquent des avantages de mémoire ou d'efficacité pour des obstacles peu nombreux et simples, ce qui pourrait être très intéressant pour moi.
Je crois qu'il devrait y avoir une approche intelligente utilisant le calcul géométrique (par exemple la détection d'intersection) et un paradigme algorithmique (par exemple la branche et la liaison au moindre coût), mais je ne veux pas mal réinventer la roue.
Existe-t-il des ressources pour certains algorithmes de chemin court (le plus court) utilisant des cartes continues ou des mots-clés utiles à rechercher ?
Comme suggéré, j'essaie de spécifier certains des termes que j'ai utilisés :
Les cartes continues (voir Fig. ) font référence au stockage de valeurs numériques réelles (continues) de formes géométriques. Obstacle/Triangle I. serait stocké comme suit : A = (3,2), B=(7,5), C=(7,2).
Les cartes discrètes (voir Fig. ) font référence à la subdivision en morceaux (discrétisation, par exemple comme dans une carte en grille). Obstacle/Triangle I. serait maintenant stocké sous forme d'indices de cellule : (3,2), (4,2), (5,2), (6,2), (5,3), (6,3), ( 6,4) la recherche de chemin dans les cartes discrètes est souvent accomplie par des algorithmes basés sur des graphes comme Dijkstra ou A*.
Le calcul géométrique n'est qu'un terme vague que j'utilise pour les opérations de géométrie computationnelle auxquelles je m'attendrais dans un algorithme de recherche de chemin pour les cartes continues. (par exemple translation, distance perpendiculaire, détection d'intersection)
Réponses
Pour les "cartes continues" comme vous l'appelez, utilisez simplement Dijkstra sur tous vos sommets. La seule différence est que vous devez vérifier l'écrêtage lors du calcul de la distance entre les nœuds.
Un autre terme, plus souvent utilisé, pour mon problème semble être le(s) chemin(s) le plus court(s) euclidien(s) . La distinction entre les algorithmes pour les cartes continues et les cartes discrètes me semble un peu ambiguë.
Cependant, la chose la plus proche que j'ai trouvée à un algorithme pour une carte continue est l'algorithme de Mitchell pour le problème continu de Dijkstra (ou la méthode continue de Dijkstra). Cet algorithme utilise des ondelettes qui se propagent uniformément à partir du point de départ. Par « diffraction » des ondelettes, elles atteignent des zones inaccessibles directement. Cela crée une carte du plus court chemin qui peut être utilisée pour identifier le plus court chemin euclidien vers n'importe quel point de l'espace de configuration continu.
Pour plus voir:
- "Euclidean Shortest Paths Exact or Approximate Algorithms" par F. Li et R. Klette
- animation sympa mais un peu buggée par Ivan Chen
- demande d'Anton Kovsharov
On peut soutenir que la carte du plus court chemin créée n'est qu'une autre discrétisation de l'espace de configuration continu. Cependant, je suppose que la carte du chemin le plus court n'est qu'un résultat qui peut être obtenu si l'algorithme est appliqué à l'ensemble de l'espace de configuration. Si seul le chemin le plus court entre deux points est recherché, l'algorithme pourrait s'arrêter après avoir atteint le point cible. Je reste incertain quant à la classification de ces algorithmes mais cela devrait répondre à ma question.