Los vehículos híbridos aéreo-submarinos (HAUV) son una nueva frontera para los vehículos. Pueden operar tanto bajo el agua como en el aire, proporcionando un enorme potencial para una amplia gama de exploraciones científicas. La planificación de rutas informativas es esencial para la autonomía del vehículo. Sin embargo, cubrir toda una región de misión es un desafío para los HAUV debido a la posibilidad de un entorno multidominio. Este documento presenta un marco de planificación de trayectorias informativas para planificar caminos y generar trayectorias para HAUV que realizan misiones multidominio en entornos dinámicos. Introducimos el novedoso algoritmo heurístico de búsqueda de vecindario extenso generalizado GLNS-k-means que utiliza k-means para agrupar información en varios conjuntos; luego, a través del algoritmo heurístico GLNS, busca el mejor camino para visitar estos puntos, sujeto a diversas restricciones relacionadas con los presupuestos de ruta y las capacidades de movimiento del HAUV. Con este enfoque, el HAUV es capaz de muestrear y centrarse en regiones de interés. Nuestro método proporciona una trayectoria significativamente más óptima (que permite la recolección de más información) que las soluciones de optimización por colonia de hormigas (ACO). Además, introducimos un esquema de replanteamiento en línea eficiente para adaptar la trayectoria según los obstáculos dinámicos durante la misión. El esquema de replanteamiento propuesto basado en el árbol KD permite tiempos computacionales significativamente más cortos que los métodos de árbol chivo expiatorio.