| Date and Venue | Paper | Authors | Presentations | Abstract |
|---|---|---|---|---|
| STAIR '08 | Fast and Loose in Suboptimal Heuristic Search |
Jordan Thayer Wheeler Ruml Ephrat Bitton | STAIR '08 Presentation | Applications often demand we tackle problems that are too large to solve optimally. In this paper, our aim is to solve shortest-path problems as quickly as possible while guaranteeing that solution costs are bounded within a specified factor of optimal. We explore two approaches. First, we extend the approach taken by weighted A*, in which all expanded nodes are guaranteed to remain within the bound. We prove that a looser bound than weighted A*'s can be used and show how an arbitrary inadmissible heuristic can be employed. As an example, we show how temporal difference learning can learn a heuristic on-line. Second, we show how an optimistic search that expands nodes potentially outside the bound can be modified to ensure bounded solution quality. We test these methods on grid-world path-finding and temporal planning benchmarks, showing that these methods can surpass weighted A*'s performance. |
| ICAPS '08 | Faster Than Weighted A*: An Optimistic Approach to Bounded Suboptimal Search |
Jordan Thayer Wheeler Ruml | ICAPS '08 Presentation | Planning, scheduling, and other applications of heuristic search often demand we tackle problems that are too large to solve optimally. In this paper, we address the problem of solving shortest-path problems as quickly as possible while guaranteeing that solution costs are bounded within a specified factor of optimal. 38 years after its publication, weighted A* remains the best-performing algorithm for general-purpose bounded suboptimal search. However, it typically returns solutions that are better than a given bound requires. We show how to take advantage of this behavior to speed up search while retaining bounded suboptimality. We present an optimistic algorithm that uses a weight higher than the user's bound and then attempts to prove that the resulting solution adheres to the bound. While simple, we demonstrate that this algorithm consistently surpasses weighted A* in four different benchmark domains including temporal planning and gridworld pathfinding. |
| SoCS '09 | Using Distance Estimates in Search: A Re-evaluation |
Jordan Thayer Wheeler Ruml Jeff Kreis | Traditionally, heuristic search algorithms have relied on an estimate of the cost-to-go to speed up problem-solving. In many domains, operators have different costs and estimated cost-to-go is not the same as estimated search-distance-to-go. We investigate further accelerating search by using a distance-to-go function. We evaluate two previous proposals: Dynamically weighted A$^*$ and A* epsilon. We present a revision to dynamically weighted A* which improves its performance substantially in domains where solutions are not at fixed depths. We show how to incorporate search distance to go estimates into weighted A* in order to improve its performance in pathfinding problems. We present a proof showing that weighted A* can ignore duplicate states, leading to large improvements in performance for pathfinding problems. | |
| SoCS '09 | The Joy of Forgetting: Faster Anytime Search via Restarting | Jordan Thayer Wheeler Ruml Silvia Richter | SoCS Presentation | Anytime search algorithms solve optimisation problems by quickly finding a usually suboptimal solution and then finding improved solutions when given additional time. To deliver a solution quickly, they are typically greedy with respect to the heuristic cost-to-go estimate h. In this paper, we first show that this low-h bias can cause poor performance if the heuristic is inaccurate. Building on this observation, we then present a new anytime approach that restarts the search from the initial state every time a new solution is found. We demonstrate the utility of our method via experiments in PDDL planning as well as other domains. We show that it is particularly useful for hard optimisation problems like planning where heuristic may be quite inaccurate and inadmissible, and where the greedy solution makes early mistakes. |
| ICAPS '09 | Using Distance Estimates in Heuristic Search |
Jordan Thayer Wheeler Ruml | This paper explores the use of an oft-ignored information source in heuristic search: a search-distance-to-go estimate. Operators frequently have different costs and cost-to-go is not the same as search-distance-to-go. We evaluate two previous proposals: dynamically weighted A* and A* epsilon. We present a revision to dynamically weighted A* that improves its performance substantially in domains where the search does not progress uniformly towards solutions, and particularly in certain temporal planning problems. We show how to incorporate distance estimates into weighted A$^*$ and improve its performance in several domains. Both approaches lead to dramatic performance increases in popular benchmark domains. |