Metodología
Esta sección describe cómo se modelan en el planificador el movimiento del robot, el entorno y la restricción de covarianza. También explica cómo implementar un EKF para los nodos discretizados de A* como un sistema dependiente del tiempo continuo.
Métrica de incertidumbre
Para cuantificar la incertidumbre de localización, puede utilizarse cualquier métrica escalar derivada de la covarianza del EKF. Utilizamos la traza de la covarianza de posición.
Se utiliza la traza de la matriz de covarianza porque la matriz es simétrica y semidefinida positiva. Por lo tanto, todas las entradas diagonales son no negativas y dan como resultado una cantidad escalar positiva.
La restricción de incertidumbre es:
La traza de la covarianza de posición debe mantenerse por debajo de un umbral definido por el usuario.
Cualquier segmento de trayectoria entre dos nodos que incumpla esta restricción se considera inviable.
Evaluación de aristas teniendo en cuenta la incertidumbre
Una vez creado un segmento con el Algoritmo 1, cada segmento de trayectoria candidato se evalúa mediante la función de comprobación de incertidumbre, resumida en el Algoritmo 2. El movimiento del robot y la propagación del EKF se simulan simultáneamente, mientras se supervisa la métrica de incertidumbre durante toda la ejecución. Se descarta cualquier nodo que no cumpla la restricción.
Análisis teórico
Esta sección ofrece una garantía teórica sobre la optimalidad del planificador A* propuesto con restricciones de incertidumbre. El problema se formula como una búsqueda en un grafo, donde la validez de las aristas queda determinada estrictamente por el límite de covarianza del EKF.
Formulación del grafo
El coste de una arista es la longitud de arco de la trayectoria generada por el controlador de seguimiento del punto objetivo.
Experimentos y resultados
Esta sección presenta resultados de simulación que evalúan el planificador propuesto con restricciones de incertidumbre en entornos sin GPS. Los experimentos muestran cómo imponer un límite a la incertidumbre de localización afecta a la viabilidad de las rutas, la precisión de la estimación y la calidad de las rutas de distintos planificadores.
Efecto de la densidad de hitos
El efecto de la densidad de hitos se evalúa modificando el porcentaje de hitos y manteniendo fijas la densidad de obstáculos y el umbral de incertidumbre. Para cada caso, se presentan la tasa de éxito, la longitud de la ruta y el tiempo de cálculo como promedios de las ejecuciones exitosas de todos los planificadores. Se sigue el mismo procedimiento para evaluar los efectos de la densidad de obstáculos y del umbral de incertidumbre.
En cuanto a la longitud de las rutas, A genera sistemáticamente las rutas más cortas para todas las densidades de hitos. Sus rutas se mantienen cerca del límite inferior euclidiano, lo que refleja la optimalidad garantizada por su heurística admisible. PRM y RRT generan rutas notablemente más largas debido a la exploración aleatoria y a la conectividad subóptima del mapa de rutas. El aumento de la densidad de hitos reduce la variabilidad de la longitud de las rutas de todos los planificadores, pero A* sigue siendo el más eficiente en términos de distancia recorrida.
A tiene el menor tiempo de cálculo en general, seguido de PRM y, después, de RRT. Al aumentar la densidad de hitos, aumenta el tiempo de cálculo de todos los planificadores.
Efecto de la densidad de obstáculos
Para todas las densidades de obstáculos, A genera sistemáticamente las rutas más cortas, lo que demuestra la solidez de sus garantías de optimalidad incluso en entornos congestionados. PRM y RRT generan rutas más largas debido a los desvíos causados por el muestreo aleatorio y la conectividad local limitada. A medida que aumenta la densidad de obstáculos, la longitud de las rutas aumenta ligeramente para todos los planificadores, pero el orden relativo no cambia.
A tiene el menor tiempo de cálculo para todas las densidades de obstáculos, seguido de PRM y, después, de RRT. Esto refleja el mayor número de expansiones de nodos que necesitan los planificadores basados en muestreo en entornos congestionados.
Efecto del umbral de incertidumbre
El umbral de incertidumbre se evalúa con la densidad de hitos fijada en 10% y la densidad de obstáculos fijada en 5%.
Conclusiones
Este artículo presenta la planificación de rutas en entornos sin GPS, donde la incertidumbre de localización aumenta debido a la navegación por estima. A* con restricciones de incertidumbre conserva sus garantías de optimalidad y devuelve la ruta más corta entre todas las trayectorias factibles que cumplen la restricción de incertidumbre, además de mantener un tiempo de cálculo bajo en general.
Los resultados experimentales muestran que, aunque las rutas óptimas desde el punto de vista geométrico a menudo no son válidas bajo las restricciones de incertidumbre, el método identifica correctamente desvíos factibles que atraviesan zonas con abundantes hitos. Sin embargo, el enfoque presupone que se conocen el entorno y la ubicación de los hitos, algo que no siempre se cumple en situaciones reales sin GPS. El trabajo futuro se centrará en relajar estos supuestos, gestionar obstáculos dinámicos y explorar filtros de creencias entre agentes para la navegación de múltiples robots en condiciones de incertidumbre.
Preguntas frecuentes
¿Cómo mide el planificador la incertidumbre de localización? Utiliza la traza de la covarianza de posición derivada del EKF.
¿Cuándo se considera inviable un segmento de trayectoria? Un segmento es inviable si incumple el umbral de incertidumbre definido por el usuario entre dos nodos.
¿Cómo se define el coste de una arista? Es la longitud de arco de la trayectoria generada por el controlador de seguimiento del punto objetivo.
¿Qué supuestos plantea el enfoque? Presupone que se conocen el entorno y la ubicación de los hitos.