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/log n).
展开▼
机译：我们提出用于求解方程组的串行和并行算法，该方程组是由与以下类型的轨迹优化问题相关的汉密尔顿-雅各比方程的离散化引起的。车辆从预定点x / sub o /开始，并沿/ spl Rscr // sup m /中的区域内部的单位速度轨迹x（t）直到该区域离开的未指定时间T。寻求使形式为/ spl int // sub 0 // sup T / r（x（t））dt + q（x（T））的成本函数最小的轨迹。通常使用迭代方法求解对应于该问题的离散汉密尔顿-雅各比方程。尽管如此，假设函数r为正，我们就能够利用问题结构并开发离散算法的一遍算法。第一种算法类似于Dijkstra的最短路径算法，并在时间O（n log n）中运行，其中n是网格点的数量。第二种算法使用了稍微不同的离散化方法，并借鉴了我们在此处开发的Dial最短路径算法（1969）的一种变体。在一些相当温和的假设下，它的运行时间为O（n），这是最好的。最后，我们证明了后一种算法可以有效地并行化：对于二维问题，使用p个处理器，只要p = O（/ s p radic / n / log n），其运行时间就变为O（n / p）。
展开▼
