Efficient algorithms for globally optimal trajectories

• Published in: IEEE transactions on automatic control 1995-09, Vol.40 (9), p.1528-1538
• Main Author: Tsitsiklis, J.N.
• Format: Article
• Language: English
• Subjects: Applied sciences; Computational complexity; Computer science; control theory; systems; Control theory. Systems; Cost function; Equations; Exact sciences and technology; Iterative algorithms; Iterative methods; Operations research; Optimal control; Optimization methods; Parallel algorithms; Vehicles
• ISSN: 0018-9286; 1558-2523
• DOI: 10.1109/9.412624

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/sub o/ and follows a unit speed trajectory x(t) inside a region in /spl Rscr//sup m/ until an unspecified time T that the region is exited. A trajectory minimizing a cost function of the form /spl int//sub 0//sup 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(/spl radic/n/log n).< >