Representing Pattern Databases with Succinct Data Structures

In this paper we describe novel representations for precomputed heuristics based on Level-Ordered Edge Sequence (LOES) encodings. We introduce compressed LOES, an extension to LOES that enables more aggressive compression of the state-set representation. We evaluate the novel repre- sentations against the respective perfect-hash and binary decision diagram (BDD) representations of pattern databases in a variety of STRIPS domains.

AI-based Problem Solving and Planning Formal Methods in Verification Logic, Reasoning, and Knowledge

View graph Source

Paper

The full text of this publication is not hosted on 44B due to licensing.

Read it at OpenAlex

Similar papers

Succinct Set-Encoding for State-Space SearchTim-Christian Schmidt, R. Zhou2011 · AAAI Conference on Artificial Intelligence · 4 citations In Library

Lossy Compression of Pattern Databases Using Acyclic Random HypergraphsM. Sadeqi, Howard J. Hamilton2017 · International Joint Conference on Artificial Intelligence · 0 citations In Library

Value Compression of Pattern DatabasesNathan R Sturtevant, Ariel Felner, M. Helmert2017 · AAAI Conference on Artificial Intelligence · 6 citations In Library

On Variable Dependencies and Compressed Pattern DatabasesMalte Helmert, Nathan Sturtevant, Ariel Felner2021 · Proceedings of the International Symposium on Combinatorial Search In Library

Additive Pattern Databases for Decoupled SearchSilvan Sievers, Daniel Gnad, Álvaro Torralba2022 · Proceedings of the International Symposium on Combinatorial Search In Library

Symbolic A* Search with Pattern Databases and the Merge-and-Shrink AbstractionS. Edelkamp, Peter Kissmann, Á. Torralba2012 · European Conference on Artificial Intelligence · 21 citations In Library

SuccinctEdgeWeiqin Xu, Olivier Curé, Philippe Calvez2020 · Proceedings of the VLDB Endowment In Library

Repetition- and Linearity-Aware Rank/Select DictionariesPaolo Ferragina, Giovanni Manzini, Giorgio Vinciguerra2021 · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) In Library

On Creating Complementary Pattern DatabasesSantiago Franco, Á. Torralba, Levi H. S. Lelis et al.2017 · International Joint Conference on Artificial Intelligence · 41 citations In Library

Below the Surface: Summarizing Event Sequences with Generalized Sequential PatternsJoscha Cüppers, Jilles Vreeken2023 · Knowledge Discovery and Data Mining · 4 citations In Library

Source of record

OpenAlex

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal