Pattern Database Sample Clauses

Pattern Database. ‌ Xxxxxxxxx and Xxxxxxxxx [21] extended the idea behind of abstraction heuristics to develop Pattern Databases, which proved to be the solution needed to find optimal solutions for the fifteen-puzzle [20]. In their solution, patterns were indicating which of the tiles could be abstracted away. This approach was then used by Xxxx to find optimal solutions for Rubik’s Cube [84]. PDBs were first used in the context of classical AI planning problems by Xxxxxxxx [29], which was done by projecting the state-space onto a memory limited abstract state space. This work was followed by extending the heuristic from explicit search to symbolic search [26], alleviating the memory demands of PDBs by leveraging a BDD description of the state-space. Xxxxx et al. [71] worked on methods to best use the memory available for creating PDBs, showing that creating several smaller PDBs and using the maximum value from all of them during search would get better results than generating only one. Research into this area has still not resulted into a definite answer, with methods on generating only one best PDB are still optimal on some domains, as showed by Xxxxxxxx and Xxxxxxx [82] with the Gamer approach. Also working with several PDBs, Xxxx and Felner [87] showed that, if the different goals can be divided into disjointed sets where actions in one would not affect another, then they could be all summed up and maintain the admissibility of the heuristic. This led to a greatly