Algoritmi di pathfinding per mappe continue (es. poligoni)
Cerco di studiare diversi algoritmi per un breve percorso tra due punti in un piano con ostacoli poligonali. La stragrande maggioranza degli algoritmi che ho trovato utilizza mappe discrete (Grid Map, grafico di visibilità, Voronoi Roadmap, ecc.). Alcuni libri (come “Elements of Robotics” di Ben-Ari o “Introduction to Autonomous Robots” di Nikolaus Correll) menzionano mappe continue (es. dati poligonali grezzi), ma non spiegano gli algoritmi corrispondenti. Rivendicano vantaggi in termini di memoria o efficienza per pochi e semplici ostacoli, che potrebbero essere molto interessanti per me.
Credo che dovrebbe esserci un approccio intelligente utilizzando il calcolo geometrico (ad esempio il rilevamento dell'intersezione) e alcuni paradigmi algoritmici (ad esempio ramo e limite di costo minimo), ma non voglio reinventare male la ruota.
Esistono risorse per alcuni algoritmi di percorso breve (est) che utilizzano mappe continue o parole chiave utili da cercare?
Come suggerito, provo a specificare alcuni dei termini che ho usato:
Le mappe continue (vedi Fig. ) si riferiscono alla memorizzazione di valori numerici reali (continui) di forme geometriche. Ostacolo/Triangolo I. verrebbe memorizzato come: A = (3,2), B=(7,5), C=(7,2).
Le mappe discrete (vedi Fig. ) si riferiscono alla suddivisione in blocchi (discretizzazione, ad esempio come in una mappa a griglia). Ostacolo/Triangolo I. verrebbe ora memorizzato come indici di cella: (3,2), (4,2), (5,2), (6,2), (5,3), (6,3), ( 6,4) il pathfinding nelle mappe discrete è spesso realizzato da algoritmi basati su grafi come Dijkstra o A*.
Il calcolo geometrico è solo un termine vago che uso per operazioni di geometria computazionale che mi aspetterei in un algoritmo di ricerca di percorsi per mappe continue. (es. traslazione, distanza perpendicolare, rilevamento intersezione)
Risposte
Per le "mappe continue" come le hai chiamate, usa Dijkstra su tutti i tuoi vertici. L'unica differenza è che devi controllare il ritaglio quando calcoli la distanza tra i nodi.
Un altro termine, usato più spesso, per il mio problema sembra essere Euclidean Shortest Path(s) . La distinzione tra algoritmi per mappe continue e mappe discrete mi sembra un po' ambigua.
Tuttavia, la cosa più vicina che ho trovato a un algoritmo per una mappa continua è l'algoritmo di Mitchell per il problema continuo di Dijkstra (o metodo continuo di Dijkstra). Questo algoritmo utilizza wavelet che si diffondono uniformemente dal punto di partenza. Per "diffrazione" delle wavelet, raggiungono aree che non possono essere raggiunte direttamente. Questo crea una mappa del percorso più breve che può essere utilizzata per identificare il percorso più breve euclideo verso qualsiasi punto nello spazio di configurazione continuo.
Per ulteriori informazioni vedere:
- "Algoritmi euclidei dei cammini minimi esatti o approssimati" di F. Li e R. Klette
- bella ma un po' buggata l'animazione di Ivan Chen
- domanda di Anton Kovsharov
Si potrebbe obiettare che la mappa del percorso più breve creata è solo un'altra discretizzazione dello spazio di configurazione continuo. Tuttavia, immagino che la mappa del percorso più breve sia solo un risultato che può essere ottenuto, se l'algoritmo viene applicato all'intero spazio di configurazione. Se si desidera solo il percorso più breve tra due punti, l'algoritmo potrebbe arrestarsi dopo aver raggiunto il punto di destinazione. Non sono sicuro della classificazione di questi algoritmi, ma questo dovrebbe rispondere alla mia domanda.