| Date and Venue | Paper | Authors | Presentations | Abstract |
|---|---|---|---|---|
| SoCS '11 | Deadline-Aware Search Using On-line Measures of Behavior | Austin Dionne Jordan Thayer Wheeler Ruml |
Poster Poster Ad | In many applications of heuristic search, insufficient time is available to find provably optimal solutions. We consider the contract search problem: finding the best solution possible within a given time limit. The conventional approach to this problem is to use an interruptible anytime algorithm. Such algorithms return a sequence of improving solutions until interrupted and do not consider the approaching deadline during the course of the search. We propose a new approach, Deadline Aware Search, that explicitly takes the deadline into account and attempts to use all available time to find a single high-quality solution. This algorithm is simple and fully general: it modifies best-first search with on-line pruning. Empirical results on variants of gridworld navigation, the sliding tile puzzle, and dynamic robot navigation show that our method can surpass the leading anytime algorithms across a wide variety of deadlines. |
| IJCAI '11 | Bounded Suboptimal Search: A Direct Approach Using Inadmissible Estimates |
Jordan Thayer Wheeler Ruml |
Poster Slides My Talk (39:30) Whole Session | Bounded suboptimal search algorithms offer shorter solving times by sacrificing optimality and instead guaranteeing solution costs within a desired factor of optimal. Typically these algorithms use a single admissible heuristic both for guiding search and bounding solution cost. In this paper, we present a new approach to bounded suboptimal search, Explicit Estimation Search, that separates these roles, consulting potentially inadmissible information to determine search order and using admissible information to guarantee the cost bound. Unlike previous proposals, it successfully combines estimates of solution length and solution cost to predict which node will lead most quickly to a solution within the suboptimality bound. An empirical evaluation across six diverse benchmark domains shows that Explicit Estimation Search is competitive with the previous state of the art in domains with unit-cost actions and substantially outperforms previously proposed techniques for domains in which solution cost and length can differ. |
| ICAPS '11 | A Survey of Suboptimal Search Algorithms |
Jordan Thayer Wheeler Ruml | Slides | This tutorial provides a survey of heuristic search algorithms, focusing on algorithms that find suboptimal solutions. We will cover algorithms that provide quality bounds, beam search algorithms, and anytime search algorithms. The commonality between these families of algorithms is that they all sacrifice finding optimal solutions in order to find solutions faster. The goal will be to develop an understanding of when the searches are likely to perform well and when they are likely to perform poorly. |
| ICAPS '11 | Using Solution Length Estimates in Heuristic Search |
Jordan Thayer Wheeler Ruml | Slides | Handling g-value plateaus is an open and challenging problem for domain independent planning. One promising approach for dealing with these plateaus is to search on multiple objectives, hoping that the guidance of one cost metric will pull the search out of plateaus in another. For cost based planning, plan length is a natural candidate for this additional guidance. This tutorial examines how the field of heuristic search has been tackling the problem of using both solution cost and solution length within a single algorithm, with a special focus on how algorithms can incorporate solution length without abandoning guarantees on solution quality. |
| ICAPS '11 | Learning Inadmissible Heuristics During Search |
Jordan Thayer Austin Dionne Wheeler Ruml |
Slides Talk | Suboptimal search algorithms offer shorter solving times by sacrificing guaranteed solution optimality. While optimal search algorithms like A* and IDA* require admissible heuristics, suboptimal search algorithms need not constrain their guidance in this way. Previous work has explored using off-line training to transform admissible heuristics into more effective inadmissible ones. In this paper we demonstrate that this transformation can be performed on-line, during search. In addition to not requiring training instances and extensive pre-computation, an on-line approach allows the learned heuristic to be tailored to a specific problem instance. We evaluate our techniques in four different benchmark domains using both greedy best-first search and bounded suboptimal search. We find that heuristics learned on-line result in both faster search and better solutions while relying only on information readily available in any best-first search. |
| SoCS '10 | Finding Acceptable Solutions Faster Using Inadmissible Information |
Jordan Thayer Wheeler Ruml | SoCS Slides | Bounded suboptimal search algorithms attempt to find a solution quickly while guaranteeing that the cost does not exceed optimal by more than a desired factor. These algorithms generally use a single admissible heuristic both for guidance and guaranteeing solution quality. We present a new approach to bounded suboptimal search that separates these roles, consulting multiple sources of potentially inadmissible information to determine search order and using admissible information to guarantee quality. An empirical evaluation across six benchmark domains shows the new approach has better overall performance. |
| SoCS '10 | Anytime Heuristic Search: Frameworks and Algorithms |
Jordan Thayer Wheeler Ruml | SoCS Poster | Anytime search is a pragmatic approach for trading solution cost and solving time. It can also be used for solving problems within a time bound. Three frameworks for constructing anytime algorithms from bounded suboptimal search have been proposed: continuing search, repairing search, and restarting search, but what combination of suboptimal search and anytime framework performs best? An extensive empirical evaluation results in several novel algorithms and reveals that the relative performance of frameworks is essentially fixed, with the repairing framework having the strongest overall performance. As part of our study, we present two enhancements to Anytime Window A* that allow it to solve a wider range of problems and hastens its convergence on optimal solutions. |
| SoCS '10 | A Comparison of Greedy Search Algorithms |
Christopher Wilt
Jordan Thayer Wheeler Ruml | We discuss the relationships between three approaches to greedy heuristic search: best-first, hill-climbing, and beam search. We consider the design decisions within each family and point out their oft-overlooked similarities. We consider the following best-first searches: weighted A*, greedy search, A* epsilon, window A* and multi-state commitment k-weighted A*. For hill climbing algorithms, we consider enforced hill climbing and LSS-LRTA*. We also consider a variety of beam searches, including BULB. We show how to best configure beam search in order to maximize robustness. An empirical analysis on six standard benchmarks reveals that beam search and best-first search have remarkably similar performance, and outperform hill-climbing approaches in terms of both time to solution and solution quality. Of these, beam search is preferable for very large problems and best first search is better on problems where the goal cannot be reached from all states. | |
| UNH Tech. Report 10-01 | Finding Acceptable Solutions Faster Using Inadmissible Information | Jordan Thayer Wheeler Ruml | Bounded suboptimal search algorithms attempt to find a solution quickly while guaranteeing that its cost does not exceed optimal by more than a desired factor. Typically these algorithms use a single admissible heuristic evaluation function for both guiding search and bounding solution quality. In this paper, we present a new approach to bounded suboptimal search that separates these roles, consulting inadmissible information to determine search order and using admissible information to guarantee quality. Unlike previous proposals, it explicitly estimates expected solution cost and search distance in an attempt to reach a solution within the suboptimality bound as quickly as possible. We show how to construct these estimates during search using information that is readily available yet often overlooked. In an empirical evaluation across six diverse benchmark domains, the new techniques have better overall performance than previous approaches, including weighted A* and optimistic search. | |
| ICAPS '10 | The Joy of Forgetting: Faster Anytime Search via Restarting | Silvia Richter
Jordan Thayer Wheeler Ruml | ICAPS 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 an initial solution quickly, they are typically greedy with respect to the heuristic cost-to-go estimate h. In this paper, we show that this low-h bias can cause poor performance if the heuristic has systematic errors. Building on this observation, we 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, and show that it is particularly useful for problems where the greedy solution makes early mistakes. |
| ICAPS '09 | Using Distance Estimates in Heuristic Search |
Jordan Thayer Wheeler Ruml | ICAPS Poster | 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. |
| SoCS '09 | The Joy of Forgetting: Faster Anytime Search via Restarting |
Silvia Richter
Jordan Thayer Wheeler Ruml | 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. |
| SoCS '09 | Using Distance Estimates in Search: A Re-evaluation |
Jordan Thayer Wheeler Ruml Jeff Kreis | SoCS Poster | 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. |
| 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. |
| 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. |