Proceedings of the AAAI Conference on Artificial Intelligence · 2011 · 41 citations · 18 references
ComputingComputer ScienceAlgorithmsMotion PlanningOptimizationHeuristic SearchRobot Motion PlanningShortest Path AlgorithmsTrajectory OptimizationMultiple Sequence AlignmentPath OptimizationShortest Path OptimizationShortest Path PlanningTrajectory PlanningUpper Bound ComputationUpper Bound Performance
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 "epsilon" to rapidly find an initial suboptimal path and then reduces "epsilon" to improve path quality over time. In ARA*, "epsilon" 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 varepsilon 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
1990 · 3.1K 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