ARA*: Anytime A* with Provable Bounds on Sub-Optimality

By Maxim Likhachev, Geoffrey J. Gordon, Sebastian Thrun. Neural Information Processing Systems, 2003

883 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/9dfd9554e948b95cc92a64f4d16c3369cdde82de

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Sergey Levine
2. Pieter Abbeel
3. J. Bagnell
4. Chelsea Finn
5. Yoshua Bengio
6. Mrinal Kalakrishnan
7. Trevor Darrell
8. Abhinav Kumar Gupta

Citations in the corpus

• Minimum snap trajectory generation and control for quadrotors (2011, methodology): “Exploring the full state space using reachability algorithms [6], incremental search techniques [7] or LQR-tree-based searches [8] is impractical for a dynamic system with six degrees of freedom.”
• Search-based planning for manipulation with motion primitives (2010, methodology): “To this end, we employ an anytime heuristic search, ARA* [12], that finds solutions with provable bounds on suboptimality and improves these solutions until allotted time for planning expires.”
• E-Graphs: Bootstrapping Planning with Experience Graphs (2012, background): “ThecomputePathfunction (shown below) runs weighted A* without re-expansions [13].”
• Learning, planning, and control for quadruped locomotion over challenging terrain (2011, methodology): “When faced with such terrain, we use the Anytime Repairing A* (ARA*) algorithm (Likhachev et al. 2003) to find a plan that maximizes the sum of foothold rewards from the start to the goal.”
• Posterior Sampling for Anytime Motion Planning on Graphs with Expensive-to-Evaluate Edges (2020, background): “Anytime variants of A* [4, 25] efficiently run a succession of weighted A* searches with decreasing inflation.”
• Learning from Multiple Heuristics (2008, background): “Examples of these domains include pathfinding in computer games (Sturtevant and Buro 2005), robotic navigation (Likhachev, Gordon, and Thrun 2003), and planning (IPC 2008).”
• CHOMP: Covariant Hamiltonian optimization for motion planning (2013, methodology): “Likhachev et al. (2004) present a framework for efficiently updating an A* search while smoothly reducing heuristic inflation, allowing resolution complete search in an anytime fashion on a broader variety of problems than previously computable.”
• Research Advances and Challenges of Autonomous and Connected Ground Vehicles (2019, background): “Then, the anytime variants of A ∗ search is developed to handle the limited planning-cycle time [392], [393].”
• Using interpolation to improve path planning: The Field D* algorithm (2006, methodology): “Likhachev et al. 2003, 2005 present an approach that uses the cost-to-goal value function of the global planner to focus an anytime global 4D trajectory planner.”
• Construction and optimal search of interpolated motion graphs (2007, methodology): “Search Method: We use A∗ search [Pearl 1984], and in particular its anytime extension ARA∗ [Likhachev et al. 2003], to find the paths through the motion graph and interpolation weights so that the interpolated path will satisfy the constraints and provide the optimal solution.”
• Trajectory generation and control for precise aggressive maneuvers with quadrotors (2012, methodology): “We depart from the optimization-based methods described by Gillula et al. (2009, 2010) and Tedrake (2009) and incremental search techniques (Likhachev et al. 2003) because these methods do not appear to scale to 12 dimensions.”
• Anytime Dynamic A*: An Anytime, Replanning Algorithm (2005, methodology): “It has been used to guide Segbots and ATRV vehicles in urban terrain (Likhachev 2003).”
• Distillation-Based Training for Multi-Exit Architectures (2019, background): “In [6], anytime algorithms are defined for the first time, and they become widely popular in planning and control [8, 29, 49].”
• Planning Long Dynamically Feasible Maneuvers for Autonomous Vehicles (2008, background): “Recognizing this mismatch, other researchers have concentrated on improving the quality of global planning, so that a global path can be easily tracked by the vehicle [13, 14, 15, 16, 17].”