Disjoint pattern database heuristics

Disjoint pattern database heuristics

0.00 Avg rating0 Votes
Article ID: iaor20032931
Country: United States
Volume: 134
Issue: 1/2
Start Page Number: 9
End Page Number: 22
Publication Date: Jan 2002
Journal: Artificial Intelligence
Authors: ,
Keywords: heuristics, artificial intelligence
Abstract:

We describe a new technique for designing more accurate admissible heuristic evaluation functions, based on pattern databases. While many heuristics, such as Manhattan distance, compute the cost of solving individual subgoals independently, pattern databases consider the cost of solving multiple subgoals simultaneously. Existing work on pattern databases allows combining values from different pattern databases by taking their maximum. If the subgoals can be divided into disjoint subsets so that each operator only affects subgoals in one subset, then we can add the pattern-database values for each subset, resulting in a more accurate admissible heuristic function. We used this technique to improve performance on the Fifteen Puzzle by a factor of over 2000, and to find optimal solutions to 50 random instances of the Twenty-Four Puzzle.

Reviews

Required fields are marked *. Your email address will not be published.