Computer Science – Artificial Intelligence
Scientific paper
2011-06-30
Journal Of Artificial Intelligence Research, Volume 22, pages 279-318, 2004
Computer Science
Artificial Intelligence
Scientific paper
10.1613/jair.1480
We explore a method for computing admissible heuristic evaluation functions for search problems. It utilizes pattern databases, which are precomputed tables of the exact cost of solving various subproblems of an existing problem. Unlike standard pattern database heuristics, however, we partition our problems into disjoint subproblems, so that the costs of solving the different subproblems can be added together without overestimating the cost of solving the original problem. Previously, we showed how to statically partition the sliding-tile puzzles into disjoint groups of tiles to compute an admissible heuristic, using the same partition for each state and problem instance. Here we extend the method and show that it applies to other domains as well. We also present another method for additive heuristics which we call dynamically partitioned pattern databases. Here we partition the problem into disjoint subproblems for each state of the search dynamically. We discuss the pros and cons of each of these methods and apply both methods to three different problem domains: the sliding-tile puzzles, the 4-peg Towers of Hanoi problem, and finding an optimal vertex cover of a graph. We find that in some problem domains, static partitioning is most effective, while in others dynamic partitioning is a better choice. In each of these problem domains, either statically partitioned or dynamically partitioned pattern database heuristics are the best known heuristics for the problem.
Felner Ariel
Hanan S.
Korf R. E.
No associations
LandOfFree
Additive Pattern Database Heuristics does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Additive Pattern Database Heuristics, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Additive Pattern Database Heuristics will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-480031