IMPLEMENTATION OF EFFICIENT ALGORITHMS FOR GLOBALLY OPTIMAL TRAJECTORIES

We consider a continuous-space shortest path problem in a two-dimensio nal plane. This is the problem of finding a trajectory that starts at a given point, ends at the boundary of a compact set of R-2, and minim izes a cost function of the form integral(0)(T) r(chi(t)) dt + q(chi(T )). For a discretized version of this problem, a Dijkstra-like method that requires one iteration per discretization point has been develope d by Tsitsiklis [10]. Here we develop some new label correcting-like m ethods based on the Small Label First methods of Bertsekas [2] and Ber tsekas et al. [6]. We prove the finite termination of these methods, a nd we present computational results showing that they are competitive and often superior to the Dijkstra-like method and are also much faste r than the traditional Jacobi and Gauss-Seidel methods.