| Tesis Doctorales de la Universidad de Alcalá |
| SHORTEST PATH PROBLEMS IN WEIGHTED REGIONS | | Autor/a | Esteban Pascual, Guillermo | | Departamento | Física y Matemáticas | | Director/a | Orden Martín, David | | Directores/as | Silveira Isoba, Rodrigo Ignacio; Bose , Prosenjit | | Fecha de defensa | 10-05-2024 | | Calificación | Sobresaliente cum laude | | Programa | Ciencias (RD 99/2011) | | Mención internacional | Sí | | Resumen | La búsqueda de caminos mínimos es uno de los problemas más estudiados en el campo de la geometría computacional. En esta tesis nos hemos centrado en caminos mínimos en escenarios geométricos, un entorno que tiene muchas aplicaciones en robótica, computación gráfica y sistemas de información geográfica. Existen muchas variantes del problema en las que la viabilidad del camino viene determinada por ciertas propiedades del terreno. Una de esas variantes se denomina "Weighted Region Problem" (WRP), i.e., encontrar un camino mínimo cuando el dominio subyacente contiene pesos. El WRP es un problema geométrico muy conocido que, a pesar de haber sido muy estudiado, todavía está lejos de ser comprendido.
La dificultad a la hora de calcular caminos mínimos de forma exacta ha motivado el estudio de algoritmos aproximados para este problema. Una alternativa que podemos encontrar normalmente en ciertas aplicaciones gráficas es la de discretizar el espacio continuo bidimensional considerando una teselación a partir de celdas con pesos. A continuación, se pueden aproximar los caminos mínimos en esta subdivisión simplificada. Nosotros proporcionamos dos métodos que discretizan el espacio, basados en la utilización de puntos de Steiner en las celdas de una triangulación basada en triángulos equiláteros. Una vez tenemos esta discretización, se pueden utilizar algoritmos como el de Dijkstra para obtener caminos mínimos en grafos geométricos. Esto nos lleva a dos algoritmos aproximados para resolver el WRP.
Además, estudiamos cómo de bien una teselación regular con pesos aproxima el espacio, con respecto a los caminos mínimos. Consideramos un camino mínimo~$ \mathit{SP_w}(s,t) $ de~$ s $ a $ t $ en el espacio continuo bidimensional, un camino mínimo entre vertices~$ \mathit{SVP_w}(s,t) $ (o "any-angle path"), un camino mínimo cuyos vertices son, además, vertices de la malla, y un camino mínimo cuadrícula $ \mathit{SGP_w}(s,t) $, que es un camino mínimo en un grafo asociado a la malla con pesos. Proporcionamos cotas superiores e inferiores para las ratios $ \frac{\lVert \mathit{SGP_w}(s,t)\rVert}{\lVert \mathit{SP_w}(s,t)\rVert} $, $ \frac{\lVert \mathit{SVP_w}(s,t)\rVert}{\lVert \mathit{SP_w}(s,t)\rVert} $, $ \frac{\lVert \mathit{SGP_w}(s,t)\rVert}{\lVert \mathit{SVP_w}(s,t)\rVert} $ en teselaciones basadas en triángulos equilateros, cuadrados y hexágonos regulares. Estas ratios determinan la eficiencia de los algoritmos existentes para el cálculo de caminos mínimos en grafos que han sido obtenidos a partir de mallas.
Finalmente, estudiamos caminos mínimos de forma más aplicada dentro del marco de la geometría computacional aplicado a un problema de la robótica. Estudiamos el problema de determinar movimientos coordinados de longitud mínima para dos robots cuadrados con los ejes alineados que se trasladan en un plano libre de obstáculos: dadas unas posiciones iniciales y finales factibles, queremos encontrar un movimiento continuo para los dos cuadrados desde el inicio hasta el final, de manera que los movimientos sólo involucran a los robots sin que halla colisiones, y tal que la distancia euclidea total recorrida por los dos cuadrados sea mínima de entre todos los posibles movimientos. Esta contribución puede servir como una componente básica para la optimización de movimientos coordinados de dos robots a través de obstáculos, así como para \emph{planificación local} en algoritmos basados en muestreo, que son habitualmente usados en la práctica. |
|
