A path from s to t on a polyhedral terrain is descending if the height of a point p never increases while we move p along the path from s to t. No ecient algorithm is known to find a shortest descending path (SDP) from s to t in a polyhedral terrain. We give a simple approximation algorithm that solves the SDP problem on general terrains. Our algorithm discretizes the terrain with O(n 2 X †) Steiner points so that after an O ‡ n 2 X † log i nX
One generalization of the Weighted Region Problem is finding a shortest aniso-tropic path @cite_18 , where the weight assigned to a region depends on the direction of travel. The weights in this problem capture, for example, the effect the gravity and friction on a vehicle moving on a slope. @cite_12 , Sun and Reif @cite_16 and Sun and Bu @cite_0 solved this problem by placing Steiner points along the edges.
@cite_0 @cite_18 @cite_16 @cite_12
2048876543 2050710547 2109032771 1480698831
The optimal path planning problems are very difficult in the case where the cost metric varies not only in different regions of the space, but also in different directions inside the same region. If the classic discretization approach is adopted to compute an @?-approximation of the optimal path, the size of the discretization (and thus the complexity of the approximation algorithm) is usually dictated by a number of geometric parameters and thus can be very large. In this paper we show a general method for choosing the variables of the discretization to maximally reduce the dependency of the size of the discretization on various geometric parameters. We use this method to improve the previously reported results on two optimal path problems with direction-dependent cost metrics. The authors address anisotropic friction and gravity effects as well as ranges of impermissible-traversal headings due to overturn danger or power limitations. The method does not require imposition of a uniform grid, nor does it average effects in different directions, but reasons about a polyhedral approximation of terrain. It reduces the problem to a finite but provably optimal set of possibilities and then uses A* search to find the cost-optimal path. However, the possibilities are not physical locations but path subspaces. The method also exploits the insight that there are only four ways to optimally traverse an anisotropic homogeneous region: (1) straight across without braking, which is the standard isotropic-weighted-region traversal; (2) straight across without braking but as close as possible to a desired impermissible heading; (3) making impermissibility-avoiding switchbacks on the path across a region; and (4) straight across with braking. The authors prove specific optimality criteria for transitions on the boundaries of regions for each combination of traversal types. > We discuss the problem of computing optimal paths on terrains for a mobile robot, where the cost of a path is defined to be the energy expended due to both friction and gravity. The physical model used by this problem allows for ranges of impermissible traversal directions caused by overturn danger or power limitations. The model is interesting and challenging, as it incorporates constraints found in realistic situations, and these constraints affect the computation of optimal paths. We give some upper- and lower-bound results on the combinatorial size of optimal paths on terrains under this model. With some additional assumptions, we present an efficient approximation algorithm that computes for two given points a path whose cost is within a user-defined relative error ratio. Compared with previous results using the same approach, this algorithm improves the time complexity by using 1) a discretization with reduced size, and 2) an improved discrete algorithm for finding optimal paths in the discretization. We present some experimental results to demonstrate the efficiency of our algorithm. We also provide a similar discretization for a more difficult variant of the problem due to less restricted assumptions. We discuss the problem of computing shortest anisotropic paths on terrains. Anisotropic path costs take into account the length of the path traveled, possibly weighted, and the direction of travel along the faces of the terrain. Considering faces to be weighted has added realism to the study of (pure) Euclidean shortest paths. Parameters such as the varied nature of the terrain, friction, or slope of each face, can be captured via face weights. Anisotropic paths add further realism by taking into consideration the direction of travel on each face thereby e.g., eliminating paths that are too steep for vehicles to travel and preventing the vehicles from turning over. Prior to this work an O(nn) time algorithm had been presented for computing anisotropic paths. Here we present the first polynomial time approximation algorithm for computing shortest anisotropic paths. Our algorithm is simple to implement and allows for the computation of shortest anisotropic paths within a desired accuracy. Our result addresses the corresponding problem posed in [12].