Anytime Heuristic Search

Abstract

We describe how to convert the heuristic search algorithm A* into an anytime algorithm that finds a sequence of improved solutions and eventually converges to an optimal solution. The approach we adopt uses weighted heuristic search to find an approximate solution quickly, and then continues the weighted search to find improved solutions as well as to improve a bound on the suboptimality of the current solution. When the time available to solve a search problem is limited or uncertain, this creates an anytime heuristic search algorithm that allows a flexible tradeoff between search time and solution quality. We analyze the properties of the resulting Anytime A* algorithm, and consider its performance in three domains; sliding-tile puzzles, STRIPS planning, and multiple sequence alignment. To illustrate the generality of this approach, we also describe how to transform the memory-efficient search algorithm Recursive Best-First Search (RBFS) into an anytime algorithm.

References in corpus (2)

• The 3rd International Planning Competition: Results and Analysis
• Multiple-Goal Heuristic Search

Cited by in corpus (19)

• Best-First Heuristic Search for Multicore Machines
• Interleaving Graph Search and Trajectory Optimization for Aggressive Quadrotor Flight
• Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits
• RBF-HS: Recursive Best-First Hitting Set Search
• Evaluating Anytime Algorithms for Learning Optimal Bayesian Networks
• Helpfulness as a Key Metric of Human-Robot Collaboration
• Neural Weighted A*: Learning Graph Costs and Heuristics with Differentiable Anytime A*
• Algorithms for Generating Ordered Solutions for Explicit AND/OR Structures
• Action Selection for MDPs: Anytime AO* vs. UCT
• Direct Policy Gradients: Direct Optimization of Policies in Discrete Action Spaces
• Constant-time Motion Planning with Anytime Refinement for Manipulation
• Search-based Motion Planning for Aggressive Flight in SE(3)
• T*$\epsilon$ -- Bounded-Suboptimal Efficient Motion Planning for Minimum-Time Planar Curvature-Constrained Systems
• A Survey of Motion Planning and Control Techniques for Self-driving Urban Vehicles
• A Classification of Configuration Spaces of Planar Robot Arms with Application to a Continuous Inverse Kinematics Problem
• Best-first Search Algorithm for Non-convex Sparse Minimization
• Local Trajectory Planning For UAV Autonomous Landing
• A Mathematical Negotiation Mechanism for Distributed Procurement Problems and a Hybrid Algorithm for its Solution
• A Search Algorithm for Simplicial Complexes