Mejora de la optimización de la ruta de JPS para robots móviles basada en el algoritmo Theta* de propagación de ángulo
Autores: Luo, Yuan; Lu, Jiakai; Qin, Qiong; Liu, Yanyu
Idioma: Inglés
Editor: MDPI
Año: 2022
Acceso abierto
Artículo científico
2022
Mejora de la optimización de la ruta de JPS para robots móviles basada en el algoritmo Theta* de propagación de ángulo
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Algoritmo
Caminos
Optimización
ángulo visible
Búsqueda de camino de cualquier ángulo
Experimentos de simulación
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 30
Citaciones: Sin citaciones
El algoritmo Jump Point Search (JPS) ignora la posibilidad de caminar en cualquier ángulo, por lo que los caminos encontrados por el algoritmo JPS en el mapa de rejilla discreta todavía tienen una brecha con los caminos reales. Para abordar los problemas anteriores, este documento mejora la estrategia de optimización de caminos del algoritmo JPS combinando el ángulo visible del algoritmo Angle-Propagation Theta* (AP Theta*), y propone el algoritmo AP-JPS basado en una estrategia de búsqueda de caminos en cualquier ángulo. Primero, basándose en el algoritmo JPS, este documento propone un método de juicio de triángulo de visión para optimizar el camino generado seleccionando el punto de búsqueda sucesor. En segundo lugar, se introduce la idea del ángulo visible del nodo en el algoritmo AP Theta* para modificar la detección de alcance de línea de visión (LOS) entre dos nodos. Finalmente, los caminos se optimizan utilizando un polinomio de séptimo orden basado en mínimo snap, de modo que el algoritmo AP-JPS genere caminos que se ajusten mejor al movimiento real del robot. La viabilidad y efectividad de este método se demuestran mediante experimentos de simulación y comparación con otros algoritmos. Los resultados muestran que el algoritmo de planificación de caminos en este documento obtiene caminos con buena suavidad en entornos con diferentes densidades de obstáculos y diferentes tamaños de mapa. En los experimentos de comparación de algoritmos, se puede ver que el algoritmo AP-JPS reduce el camino en un 1.61-4.68% y el ángulo de giro total del camino en un 58.71-84.67% en comparación con el algoritmo JPS. El algoritmo AP-JPS reduce el tiempo de cálculo en un 98.59-99.22% en comparación con el algoritmo AP-Theta*.
Descripción
El algoritmo Jump Point Search (JPS) ignora la posibilidad de caminar en cualquier ángulo, por lo que los caminos encontrados por el algoritmo JPS en el mapa de rejilla discreta todavía tienen una brecha con los caminos reales. Para abordar los problemas anteriores, este documento mejora la estrategia de optimización de caminos del algoritmo JPS combinando el ángulo visible del algoritmo Angle-Propagation Theta* (AP Theta*), y propone el algoritmo AP-JPS basado en una estrategia de búsqueda de caminos en cualquier ángulo. Primero, basándose en el algoritmo JPS, este documento propone un método de juicio de triángulo de visión para optimizar el camino generado seleccionando el punto de búsqueda sucesor. En segundo lugar, se introduce la idea del ángulo visible del nodo en el algoritmo AP Theta* para modificar la detección de alcance de línea de visión (LOS) entre dos nodos. Finalmente, los caminos se optimizan utilizando un polinomio de séptimo orden basado en mínimo snap, de modo que el algoritmo AP-JPS genere caminos que se ajusten mejor al movimiento real del robot. La viabilidad y efectividad de este método se demuestran mediante experimentos de simulación y comparación con otros algoritmos. Los resultados muestran que el algoritmo de planificación de caminos en este documento obtiene caminos con buena suavidad en entornos con diferentes densidades de obstáculos y diferentes tamaños de mapa. En los experimentos de comparación de algoritmos, se puede ver que el algoritmo AP-JPS reduce el camino en un 1.61-4.68% y el ángulo de giro total del camino en un 58.71-84.67% en comparación con el algoritmo JPS. El algoritmo AP-JPS reduce el tiempo de cálculo en un 98.59-99.22% en comparación con el algoritmo AP-Theta*.