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.
fuente
Respuestas:
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.
fuente
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.
fuente