2011 · 36 citations · 18 references
ComputingComputer ScienceAlgorithmsMotion PlanningOptimizationHeuristic SearchRobot Motion PlanningShortest Path AlgorithmsTrajectory OptimizationMultiple Sequence AlignmentPath OptimizationShortest Path OptimizationShortest Path PlanningTrajectory PlanningUpper Bound Computation
Anytime variants of Dijkstra’s and A * shortest path algorithms quickly produce a suboptimal solution and then improve it over time. For example, ARA * introduces a weighting value (ε) to rapidly find an initial suboptimal path and then reduces ε to improve path quality over time. In ARA*, ε is based on a linear trajectory with ad-hoc parameters chosen by each user. We propose a new Anytime A * algorithm, Anytime Nonparametric A * (ANA*), that does not require ad-hoc parameters, and adaptively reduces ε to expand the most promising node per iteration, adapting the greediness of the search as path quality improves. We prove that each node expanded by ANA * provides an upper bound on the suboptimality of the current-best solution. We evaluate the performance of ANA * with experiments in the domains of robot motion planning, gridworld planning, and multiple sequence alignment. The results suggest that ANA * is as efficient as ARA * and in most cases: (1) ANA * finds an initial solution faster, (2) ANA * spends less time between solution improvements, (3) ANA * decreases the suboptimality bound of the current-best solution more gradually, and (4) ANA * finds the optimal solution faster. ANA * is freely available from Maxim Likhachev’s Search-based Planning Library (SBPL).
18
A note on two problems in connexion with graphs
E. Dijkstra · Numerische Mathematik · 1959 · 23.8K citations
Adhi Harmoko S, M.Komp, Joseph Marie Jacquard et al. · 2005 · 18.4K citations
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
Generalized best-first search strategies and the optimality of A*
Rina Dechter, Judea Pearl · Journal of the ACM · 1985 · 1.1K citations · Full text