Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Merge-and-shrink abstraction: a method for generating lower bounds in factored state spaces
Helmert M., Haslum P., Hoffmann J., Nissim R. Journal of the ACM61 (3):1-63,2014.Type:Article
Date Reviewed: Aug 6 2014

Pattern databases are heuristics used in search that rely on abstractions that aggregate states if they agree on a subset of the state variables. This paper considers a more general class of abstractions called merge-and-shrink abstractions. Shrinking projects the state space to be searched surjectively onto a reduced state space, merging involves creating an abstraction from two abstractions that involve disjoint variables on the state space. From these operations one constructs a tree of abstractions called a merge-and-shrink tree.

This paper provides a description of a generic merge-and-shrink algorithm. This abstracts away from the merging strategy and the shrinking strategy. Concrete construction of the tree requires choosing the strategies for merging and shrinking. The main tool used to make these choices is to relax bisimilarity of the representations.

Since many problems of interest are specified in terms of the allowable transitions between states, a major concern is that the total state space for the problem can be very large. The main results of this paper show that merge-and-shrink abstractions can be constructed in polynomial time. Furthermore, the resulting abstraction provides good lower bound estimates for reachability.

The authors identify the class of transition systems--factored ones--which allow these abstractions to be built in a practical, incremental way, without loss of information. For the purposes of exposition, the paper uses a simplified logistics planning problem involving a truck and two packages. The paper also includes the results of experiments on planning tasks using the authors’ merge-and-shrink approach, and compares the results to other planning techniques. While the paper is somewhat densely written, it provides full details for the reader.

Reviewer:  J. P. E. Hodgson Review #: CR142592 (1411-0991)
Bookmark and Share
  Featured Reviewer  
 
Graph And Tree Search Strategies (I.2.8 ... )
 
 
Heuristic Methods (I.2.8 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Graph And Tree Search Strategies": Date
How evenly should one divide to conquer quickly?
Walsh T. Information Processing Letters 19(4): 203-208, 1984. Type: Article
Oct 1 1985
Three approaches to heuristic search in networks
Bagchi A., Mahanti A. Journal of the ACM 32(1): 1-27, 1985. Type: Article
Sep 1 1986
AND/OR graph heuristic search methods
Mahanti A., Bagchi A. Journal of the ACM 32(1): 28-51, 1985. Type: Article
Feb 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy