Planificación y Optimización de Rutas con Restricciones

Autor: Rocio Salinas Guerra
Coautor(es): Porfirio Toledo Hernández
Actualmente, los sistemas de posicionamiento son herramientas útiles cuando se requiere trazar una ruta de un punto a otro en cierto espacio y no se sabe la ubicación exacta, así como las trayectorias a seguir. Además, si se tienen restricciones en el espacio de búsqueda el problema se hace más complejo. Se considera el problema de llegar de un punto A a un punto B, en un espacio con obstáculos, restringido a una trayectoria dada por una función. Esta problemática se presenta en diversos casos, por ejemplo en la planificación de rutas para robots en un espacio continuo (en la practica discretizado) con obstáculos. En este trabajo se utilizó la teoría de grafos para modelar dicho problema, en donde la región del espacio navegable con obstáculos corresponde a un grafo no dirigido. En términos generales el problema se describe de la siguiente manera: se quiere llegar a un vértice B desde un vértice inicial A en un grafo dado, usualmente con una cantidad grande de nodos. Para identificar rutas factibles en la búsqueda de soluciones, se utiliza el algoritmo A*, el cual es un método que encuentra, sobre el grafo, la trayectoria más corta entre dos vértices de manera eficiente. Éste es una extensión del algoritmo de Dijkstra, el cual considera una función heurística h(A) para optimizar (computacionalmente) la búsqueda. La parte más importante para resolver el problema de interés, es la correcta elección de la heurística. Por lo que, para aplicar el algoritmo A*, es necesario proponer una heurística consistente. Además, h(A) debe considerar las restricciones dadas para obtener soluciones factibles. En el trabajo se presentan simulaciones numéricas, en las cuales se modela el espacio como una malla incompleta con obstáculos, en donde se asignan coordenadas en R^2 a cada vértice y las aristas se dotan con pesos. Luego se propone una función heurística consistente en la que se consideran las restricciones del problema. Finalmente, la restricción es dada por un polinomio. Los resultados obtenidos garantizarán la aplicabilidad de nuestra propuesta para la aplicación en planificación de rutas de robots.