Shortest path problems in weighted regions

Abstract

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.