Implementation of efficient algorithms for globally optimal trajectories
- 1 January 1998
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 43 (2), 278-283
- https://doi.org/10.1109/9.661081
Abstract
We consider a continuous space shortest path problem in a two-dimensional plane. This is the problem of finding a trajectory that starts at a given point, ends at the boundary of a compact set of /spl Rfr//sup 2/, and minimizes a cost function of the form /spl int//sub O//sup T/ r(x(t)) dt+q(x(T)). For a discretized version of this problem, a Dijkstra-like method that requires one iteration per discretization point has been developed by Tsitsiklis (1995). Here we develop some new label correcting-like methods based on the small label first methods of Bertsekas (1993) and Bertsekas et al. (1996). We prove the finite termination of these methods, and present computational results showing that they are competitive and often superior to the Dijkstra-like method and are also much faster than the traditional Jacobi and Gauss-Seidel methods.Keywords
This publication has 6 references indexed in Scilit:
- Sequential and Parallel Path-Relinking Algorithms for the Quadratic Assignment ProblemIEEE Intelligent Systems, 2005
- Efficient algorithms for globally optimal trajectoriesIEEE Transactions on Automatic Control, 1995
- A simple and fast label correcting algorithm for shortest pathsNetworks, 1993
- Numerical Methods for Stochastic Control Problems in Continuous TimePublished by Springer Science and Business Media LLC ,1992
- An Analysis of Stochastic Shortest Path ProblemsMathematics of Operations Research, 1991
- Shortest path algorithmsAnnals of Operations Research, 1988