¿Cuáles son los algoritmos de última generación para encontrar caminos en un mapa continuo de la Tierra?

14

Supongamos que tengo un buque de superficie autónomo alimentado por energía solar en algún lugar de los fiordos de Noruega, provisto de un conjunto bastante reciente de mapas, un receptor GPS y ningún medio para descifrar comandos detallados de mi parte. Este barco tiene que llegar, digamos, a la isla de Hainan lo antes posible.

  • ¿Cuáles son los algoritmos deterministas para encontrar una ruta marítima en un globo terráqueo?
  • ¿Cuál es su complejidad de tiempo y memoria?

  • ¿Puedo, por ejemplo, usar A * después de transformar el mapa del globo en un diagrama con polígonos conectados (es decir, triangulación de Delaunay en una esfera / elipsoide) y cuáles son otros enfoques factibles?

Idealmente, las respuestas deberían proporcionar referencias a los documentos con la discusión de las preguntas mencionadas anteriormente.

Como señaló Rob Lang , los algoritmos deben cumplir con los criterios habituales: en ausencia de limitaciones de tiempo, conducir a la ruta más corta entre dos puntos en los océanos y mares de la Tierra, o indicar un fallo en la búsqueda de ruta de lo contrario.

Aquí hay subtemas interesantes (intercambio de tiempo / almacenamiento previo al cómputo para cómputos en línea, que proporciona rutas ligeramente subóptimas antes de que entre en vigencia una fecha límite, etc.), pero estos son auxiliares del problema principal.

Cazador de ciervos
fuente
1
@JDong: la navegación terrestre sigue rutas / caminos, en general, por lo tanto, A * es algo natural. Un gráfico preconstruido es lo que usaría.
Deer Hunter
1
Ah, me perdí la parte crítica de su pregunta: 'continuo'. En ese caso, quizás los campos vectoriales o potenciales podrían ser prometedores.
JDong
1
@RobLang - pregunta editada.
Deer Hunter
1
Para una ruta marítima, deberá tomar el nivel del mar, el viento y el flujo de agua en los cálculos. ¿De qué tipo de barco estamos hablando? OpenSeaMap proporciona algunas rutas de envío. Si pudieras usar esos A * funcionaría. También creo que esta pregunta es demasiado amplia para esta versión beta.
PiTheNumber
1
Creo que esta pregunta está bien si solo pide los mejores algoritmos dinámicos de búsqueda de rutas para espacios continuos de hoy. Podría intentar responder esto más tarde hoy después de un poco de investigación.
JDong

Respuestas:

7

El requisito determinista no es tan restrictivo. Eso solo implica que su vehículo está seguro del estado en que se encuentra. Dicho esto, probablemente querrá planificar caminos de una manera que le permita evitar obstáculos. La mejor forma en que he visto esto es con planificadores basados ​​en muestreo. Steven LaValle escribió el recurso académico central sobre este tema: Algoritmos de planificación .

El algoritmo RRT * se encuentra entre los planificadores que describe. Este algoritmo genera el árbol de espacio de estado con muestras aleatorias y algunas heurísticas para garantizar la viabilidad (por ejemplo, evitar obstáculos) y la optimización. Los detalles sobre RRT * se pueden encontrar en el libro de LaValle o en el sitio web de Sertac Karaman . El tiempo asintótico y las características de la memoria se describen como O (nlogn) para procesar y O (n) para consultas. El algoritmo es lineal, O (n), también en complejidad espacial.

jdmartin86
fuente
Votado a favor de los árbitros. Considerará aceptar al leer el libro de LaValle y revisar el material RRT *. ¡Gracias!
Deer Hunter
4

Para su consideración adicional, los campos potenciales son una opción interesante y de bajo costo para la búsqueda de caminos. Colocaría una carga fuerte en el destino y, finalmente, el agente llegaría a la carga. Un artículo más técnico de la Fundación Internacional para Agentes Autónomos y Sistemas Multiagente proporciona más información.

Los campos vectoriales también son una solución muy barata, pero se utilizan con mayor frecuencia para la búsqueda de rutas de múltiples agentes . Sin embargo, los campos vectoriales son muy buenos para áreas abiertas. Sin embargo, ninguno de los métodos anteriores garantiza el camino más corto, sacrificando la ruta óptima para una mejor respuesta dinámica.

Los enfoques combinados también son fuertes, como usar A * de antemano para generar puntos de ruta y usar campos vectoriales para ir a cada punto de ruta. Esto probablemente dará un comportamiento mucho más óptimo en una escala macro.

Tenga esto en cuenta en caso de que adquiera un ejército de robots nadadores.

JDong
fuente