algoritmo óptimo para la trayectoria de investigación en una matriz que no encaja completamente en la memoria

Question

estoy frente a un problema difícil:

Imagínese Tengo un mapa de todo un país, representado por una enorme matriz de celdas. Cada celda representa un 1 metro cuadrado de territorio. Cada celda se representa como un valor double entre 0 y 1 que representa el costo de atravesar la celda.

El mapa obviamente no se puede montar en la memoria.

Estoy tratando de enfocar mi mente alrededor de una manera de calcular la ruta óptima para un robot, desde un punto de partida hasta una posición final. La primera idea que tuve fue hacer una ventana móvil similar a TCP, con un minimapa del mapa real alrededor del robot en movimiento, y ejecutar el algoritmo A * allí, pero estoy enfrentando algunos problemas con mapas con paredes enormes, mal pathfinding, etc ...

Estoy buscando en la literatura sobre algoritmos tipo A * y no pude visualizar una aproximación de lo que sería una buena solución para este problema.

Me pregunto si alguien se ha enfrentado a un problema similar o puede ayudar con una idea de una posible solución.

Gracias de antemano :)

Answer 1

Ya que no conocen datos exactos, aquí hay alguna información que podría ser útil:

• Un camino parcial de un camino más corto es en sí mismo un camino más corto. Es decir. puedes dividir tu matriz en submatrices y encontrar (todos) los caminos más cortos allí. Tenga en cuenta que no tiene que almacenar todos los resultados de: por ejemplo, puede ahorrar memoria al no guardar una ruta completa sino solo la información: La ruta va desde A hasta B. Los nodos intermedios pueden calcularse más tarde nuevamente o almacenarse en un archivo para más adelante. Incluso es posible que pueda calcular previamente algunas rutas más cortas para ciertas áreas.

• Otro enfoque es que puede ser capaz de comprimir su matriz de alguna manera. Es decir. si tiene áreas grandes que constan de un solo y el mismo número, podría ser bueno almacenar solo ese número y las dimensiones de esa área.

• Otro enfoque (en relación con la precomputación de algunas rutas más cortas) es generar diferentes niveles de detalle de su mapa. Teniendo en cuenta un mapa de los EE. UU., Esto podría verse de la siguiente manera: el nivel de detalle más grueso contiene solo las ciudades de Nueva York, Los Ángeles, Chicago, Dallas, Filadelfia, Houston y Phoenix. Cuanto más fino sea el nivel, más ciudades contendrá, pero, por otro lado, mostrará el área más pequeña de todo el mapa.

Answer 2

¿Su problema tiene ninguna estructura especial, por ejemplo, ¿el triángulo de la desigualdad de retención/se puede garantizar que el camino más corto no refrescar un lado a otro? ¿Desea realizar la consulta muchas veces? (De ser así, puede hacer un procesamiento previo que se amortizará en múltiples consultas). ¿Necesita la solución mínima exacta, o algo dentro de un factor épsilon estará bien?

Se pensó que se podía engrosar la matriz: formar cuadrados de 100 metros por 100 metros y determinar las distancias de trayectoria más cortas a través de 100 \ multiplicado por 100 cuadrados. Ahora esto cabe en la memoria (alrededor de 1 Gigabyte), puede ejecutar Dijkstra, y luego expandir cada paso a través de los 100 \ times 100 cuadrados.

Además, ¿ha intentado ejecutar una versión hacia adelante y hacia atrás del algoritmo de Dijkstra? Es decir., amplía desde la fuente y busca el receptor al mismo tiempo, y detente cuando haya una intersección.

Por cierto, ¿por qué necesita un nivel tan fino de granularidad?

Answer 3

Aquí están algunas ideas que pueden funcionar

puede modelar su trayectoria como una curva lineal por tramos. Si tiene 31 segmentos de línea, su curva se describe por completo con 60 números. Cada una de las posibles curvas tienen un costo, por lo que el costo es una función de la forma siguiente

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

Ahora su problema es encontrar el óptimo global de una función de 60 variables. Puede usar métodos estándar para hacer esto. Una idea es usar algoritmos genéticos. Otra idea es utilizar un método de Monte Carlo como el templado paralelo

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

Cada vez que haya un camino prometedor continuación, se puede usar como punto de partida para encontrar un mínimo local de la función de coste. Tal vez pueda usar alguna interpolación para hacer que su función de costo sea diferenciable. Entonces puede usar el método de Newton (o más bien BFGS) para encontrar el mimima local de la función de costo.

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

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

su problema es algo similar al problema de encontrar caminos de reacción en sistemas químicos. Quizás puedas encontrar algo de inspiración en el libro "Energy Landscapes" de Davis Wales.

Pero también tengo algunas preguntas:

• ¿Es necesario para que usted pueda encontrar el camino óptimo, o simplemente estás buscando un camino que está bien?
• ¿Cuánta potencia de computadora y tiempo tienes a mano?
• ¿Puede el robot realizar giros bruscos o necesita un modelo de física adicional para mejorar la función de costos?