Shortest path problems in weighted regions

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 metodos que discretizan el espacio, basados en la utilización de puntos de Steiner en las celdas de una triangulación basada en triángulos equilateros. 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 SPw(s, t) de s a t en el espacio continuo bidimensional, un camino mínimo entre vertices SVPw(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 SGPw(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 ?SGPw(s,t)?/?SPw(s,t)?, ?SVPw(s,t)?/?SPw(s,t)?, ?SGPw(s,t)?/?SVPw(s,t)? 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 geometria 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 traves de obstáculos, así como para planificación local en algoritmos basados en muestreo, que son habitualmente usados en la práctica.