Resumen de Shortest path problems in weighted regions
- español
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.
- English
Finding a shortest path is one of the most studied problems in computational geometry. In this thesis we focus on shortest paths in geometric settings, which has many applications in robotics, computer graphics and geographic information systems. There are many variants of the problem in which the feasibility of a path is determined by some geometric property of the terrain. One such variant is the Weighted Region Problem (WRP), i.e., finding a shortest path when the underlying domain is weighted. The WRP is a well-known geometric problem that, despite having been studied extensively, is still far from being well understood.
The difficulty of finding exact weighted shortest paths motivates the study of approximation algorithms for the problem. One alternative that is often encountered in many graphic applications is to discretize the continuous 2-dimensional space by considering a mesh of weighted cells. Then, optimal shortest paths in this simpler subdivision are approximated. We present two methods that discretize the space based on the placement of Steiner points in the cells of an equilateral-triangle tessellation. Using such a discretization, we can use standard algorithms for shortest paths in graphs for computing a shortest path in the geometric graph obtained. This will lead us to two approximation algorithms for solving the WRP.
In addition, we study how well a weighted regular mesh approximates the space, with respect to shortest paths. We consider a shortest path SPw(s, t) from s to t in the continuous 2-dimensional space, a shortest vertex path SVPw(s, t) (or any-angle path), which is a shortest path where the vertices of the path are vertices of the mesh, and a shortest grid path SGPw(s, t), which is a shortest path in a graph associated to the weighted mesh. We provide upper and lower bounds on the ratios ∥SGPw(s,t)∥/∥SPw(s,t)∥,, ∥SVPw(s,t)∥/∥SPw(s,t)∥, ∥SGPw(s,t)∥/∥SVPw(s,t)∥ in equilateral-triangle, square and regular-hexagon meshes.
These ratios determine the effectiveness of existing algorithms that compute shortest paths on the graphs obtained from the grids.
Finally, we explore an application of shortest paths inside the frame of computational geometry applied to a robotics problem. We study the problem of determining minimum-length coordinated motions for two axis-aligned square robots translating in an obstacle-free plane: Given feasible start and goal configurations, find a continuous motion for the two squares from start to goal, comprising only robot-robot collision-free configurations, such that the total Euclidean distance traveled by the two squares is minimal among all possible such motions. Our contribution can serve as a basic component in optimizing the coordinated motion of two squares among obstacles, as well as for local planning in sampling-based algorithms, which are often used in practice, in the same setting.
