algoritmo ottimale per il percorso-scoperta in una matrice che non si adatta del tutto nella memoria

Question

Sto affrontando un problema difficile:

Immaginate ho una mappa di un paese intero, rappresentato da un enorme matrice di celle. Ogni cella rappresenta un metro quadrato di territorio. Ogni cella è rappresentata come valore double tra 0 e 1 che rappresenta il costo di attraversamento della cella.

La mappa ovviamente non è fissabile in memoria.

Sto cercando di racchiudere la mia mente attorno a un modo per calcolare il percorso ottimale per un robot, da un punto iniziale a una posizione finale. La prima idea che ho avuto è stata quella di creare una finestra mobile simile a TCP, con una minimappa della mappa reale attorno al robot in movimento, e l'esecuzione dell'algoritmo A * all'interno, ma sto affrontando alcuni problemi con le mappe con muri enormi, male pathfinding, ecc ...

Sto cercando la letteratura sugli algoritmi A * -like e non sono riuscito a visualizzare un'approssimazione di quale sarebbe stata una buona soluzione per questo problema.

Mi chiedo se qualcuno ha affrontato un problema simile o può aiutare con un'idea di una possibile soluzione!

Grazie in anticipo :)

Answer 1

Dal momento non so dati esatti, ecco alcune informazioni che potrebbero essere utili:

• Un percorso parziale di un percorso più breve è di per sé un percorso più breve. Cioè potresti dividere la tua matrice in sottomatrici e trovare (tutti) i percorsi più brevi. Tieni presente che non devi memorizzare tutti i risultati: ad es. può salvare la memoria non salvando un percorso completo ma solo le informazioni: il percorso passa da A a B. I nodi intermedi potrebbero essere calcolati di nuovo in seguito o memorizzati in un file per dopo. Potresti anche essere in grado di precomputare alcuni percorsi più brevi per determinate aree.

• Un altro approccio è che potresti essere in grado di comprimere la tua matrice in qualche modo. Cioè se disponi di aree grandi composte solo da uno stesso numero, potrebbe essere opportuno memorizzare solo quel numero e le dimensioni di quell'area.

• Un altro approccio (in relazione alla precompilazione di alcuni percorsi più brevi) consiste nel generare diversi livelli di dettaglio della mappa. Considerando una mappa degli Stati Uniti, questo potrebbe sembrare il seguente: Il livello di dettaglio più grossolano contiene solo le città di New York, Los Angeles, Chicago, Dallas, Filadelfia, Houston e Phoenix. Più i livelli sono alti, più città contengono, ma, d'altra parte, l'area più piccola dell'intera mappa viene mostrata da loro.

Answer 2

Il vostro problema ha alcuna struttura speciale, per esempio, fa la disuguaglianza triangolare stretta/si può garantire che il percorso più breve non jogging avanti e indietro? Vuoi eseguire la query molte volte? (In tal caso, è possibile eseguire una pre-elaborazione che si ammortizzerà su più query.) È necessaria la soluzione minima esatta o qualcosa all'interno di un fattore epsilon può essere OK?

Un pensiero era che si può grossolanamente la matrice - formare 100 metri per 100 metri quadrati e determinare le distanze del percorso più breve attraverso i 100 \ 100 volte quadrati. Ora ciò si adatta alla memoria (circa 1 Gigabyte), è possibile eseguire Dijkstra e quindi espandere ogni passaggio attraverso 100 \ 100 quadrati.

Inoltre, hai provato a eseguire una versione di backward dell'algoritmo di Dijkstra? Cioè, espandi dalla fonte e cerca il lavandino allo stesso tempo, e fermati quando c'è un'intersezione.

Per inciso, perché è necessario un livello così fine di granularità?

Answer 3

Ecco alcune idee che possono lavorare

è possibile modellare il vostro percorso come una curva lineare a tratti. Se hai 31 segmenti di linea, la tua curva è completamente descritta da 60 numeri. Ognuna delle possibili curve hanno un costo, quindi il costo è una funzione del seguente modulo

costo (x1, x2, x3 ..... x60)

Ora il problema è quello di trovare l'ottimo globale di una funzione di 60 variabili. Puoi usare metodi standard per farlo. Un'idea è usare gli algoritmi genetici. Un'altra idea è quella di utilizzare un metodo di Monte Carlo come parallelo rinvenimento

http://en.wikipedia.org/wiki/Parallel_tempering

Ogni volta che avete un percorso promettente quindi è possibile utilizzarlo come punto di partenza per trovare un minimo locale della funzione di costo. Forse puoi usare un'interpolazione per rendere la tua funzione di costo differenziabile. Quindi è possibile utilizzare il metodo Newton (o meglio BFGS) per trovare il mimima locale della funzione di costo.

http://en.wikipedia.org/wiki/Local_minimum

http://en.wikipedia.org/wiki/BFGS

il problema è in qualche modo simile al problema di trovare cammini di reazione in sistemi chimici. Forse puoi trovare qualche ispirazione nel libro "Energy Landscapes" di Davis Wales.

Ma ho anche alcune domande:

• E 'necessario per voi per trovare il percorso ottimale, o siete semplicemente alla ricerca di un percorso che è OK?
• Quanto tempo e potenza del computer avete a portata di mano?
• Il robot può compiere curve strette o è necessaria una modellazione fisica extra per migliorare la funzione di costo?