Zero-Aware Pattern Databases with 1-Bit Compression for Sliding Tile Puzzles
| العنوان: | Zero-Aware Pattern Databases with 1-Bit Compression for Sliding Tile Puzzles |
|---|---|
| المؤلفون: | Robert Clausecker, Alexander Reinefeld |
| المصدر: | Proceedings of the International Symposium on Combinatorial Search. 10:35-43 |
| بيانات النشر: | Association for the Advancement of Artificial Intelligence (AAAI), 2021. |
| سنة النشر: | 2021 |
| الوصف: | A pattern database (PDB) is a pre-computed lookup table storing shortest distances from abstract states to abstract goal states. PDBs are key components in heuristic search as their entries are used to prune paths that cannot lead to an optimal solution. With the sliding-tile puzzle as an exemplary application domain, we present methods to improve the precision and size of PDBs by improving additive pattern databases to zero-aware additive pattern databases (ZPDBs), reducing the compression rate from previously 1.6 bit to 1 bit per entry, generating optimal additive pattern partitionings, and building effective collections of pattern databases. With these enhancements, we achieve an overall 8.59-fold performance gain on the 24-puzzle compared to the previously best set of 6-tile PDBs. |
| تدمد: | 2832-9163 2832-9171 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_________::e71cb19d26de5c93dbdea4dba3448b12 https://doi.org/10.1609/socs.v10i1.18500 |
| رقم الأكسشن: | edsair.doi...........e71cb19d26de5c93dbdea4dba3448b12 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 28329163 28329171 |
|---|