Efficient algorithms for globally optimal trajectories

@article{citeulike:2795216, abstract = {We present serial and parallel algorithms for solving a system of equations that arises from the discretization of the Hamilton-Jacobi equation associated to a trajectory optimization problem of the following type. A vehicle starts at a prespecified point x_o and follows a unit speed trajectory x(t) inside a region in \ℛ^m until an unspecified time T that the region is exited. A trajectory minimizing a cost function of the form \∫₀^T r(x(t))dt+q(x(T)) is sought. The discretized Hamilton-Jacobi equation corresponding to this problem is usually solved using iterative methods. Nevertheless, assuming that the function r is positive, we are able to exploit the problem structure and develop one-pass algorithms for the discretized problem. The first algorithm resembles Dijkstra's shortest path algorithm and runs in time O(n log n), where n is the number of grid points. The second algorithm uses a somewhat different discretization and borrows some ideas from a variation of Dial's shortest path algorithm (1969) that we develop here; it runs in time O(n), which is the best possible, under some fairly mild assumptions. Finally, we show that the latter algorithm can be efficiently parallelized: for two-dimensional problems and with p processors, its running time becomes O(n/p), provided that p=O(\√n/log n)}, author = {Tsitsiklis, J. N. }, booktitle = {Automatic Control, IEEE Transactions on}, citeulike-article-id = {2795216}, doi = {10.1109/9.412624}, journal = {Automatic Control, IEEE Transactions on}, keywords = {dijkstra, distance, eikonal, fast, geodesic, marching, optimal, path}, number = {9}, pages = {1528--1538}, posted-at = {2008-05-13 15:48:34}, priority = {5}, title = {Efficient algorithms for globally optimal trajectories}, url = {http://dx.doi.org/10.1109/9.412624}, volume = {40}, year = {1995} }

TY - JOUR ID - citeulike:2795216 L3 - citeulike-article-id:2795216 TI - Efficient algorithms for globally optimal trajectories T2 - Automatic Control, IEEE Transactions on JF - Automatic Control, IEEE Transactions on VL - 40 IS - 9 SP - 1528 EP - 1538 N2 - We present serial and parallel algorithms for solving a system of equations that arises from the discretization of the Hamilton-Jacobi equation associated to a trajectory optimization problem of the following type. A vehicle starts at a prespecified point x_o and follows a unit speed trajectory x(t) inside a region in ℛ^m until an unspecified time T that the region is exited. A trajectory minimizing a cost function of the form ∫₀^T r(x(t))dt+q(x(T)) is sought. The discretized Hamilton-Jacobi equation corresponding to this problem is usually solved using iterative methods. Nevertheless, assuming that the function r is positive, we are able to exploit the problem structure and develop one-pass algorithms for the discretized problem. The first algorithm resembles Dijkstra's shortest path algorithm and runs in time O(n log n), where n is the number of grid points. The second algorithm uses a somewhat different discretization and borrows some ideas from a variation of Dial's shortest path algorithm (1969) that we develop here; it runs in time O(n), which is the best possible, under some fairly mild assumptions. Finally, we show that the latter algorithm can be efficiently parallelized: for two-dimensional problems and with p processors, its running time becomes O(n/p), provided that p=O(√n/log n) KW - dijkstra KW - distance KW - eikonal KW - fast KW - geodesic KW - marching KW - optimal KW - path AU - Tsitsiklis, JN PY - 1995/// UR - http://dx.doi.org/10.1109/9.412624 ER -