Succinct Set-Encoding for State-Space Search

AAAI 2011 pp. 87-92

doi:10.1609/AAAI.V25I1.7818 /aaai/2011/schmidt2011aaai-succinct/

Abstract

We introduce the level-ordered edge sequence (LOES), a suc- cinct encoding for state-sets based on prefix-trees. For use in state-space search, we give algorithms for member testing and element hashing with runtime dependent only on state- size, as well as space and memory efficient construction of and iteration over such sets. Finally we compare LOES to binary decision diagrams (BDDs) and explicitly packed set- representation over a range of IPC planning problems. Our results show LOES produces succinct set-encodings for a wider range of planning problems than both BDDs and ex- plicit state representation, increasing the number of problems that can be solved cost-optimally.

PDF AAAI Semantic Scholar

Cite

Text

Schmidt and Zhou. "Succinct Set-Encoding for State-Space Search." AAAI Conference on Artificial Intelligence, 2011. doi:10.1609/AAAI.V25I1.7818

Markdown

[Schmidt and Zhou. "Succinct Set-Encoding for State-Space Search." AAAI Conference on Artificial Intelligence, 2011.](https://mlanthology.org/aaai/2011/schmidt2011aaai-succinct/) doi:10.1609/AAAI.V25I1.7818

BibTeX

@inproceedings{schmidt2011aaai-succinct,
  title     = {{Succinct Set-Encoding for State-Space Search}},
  author    = {Schmidt, Tim and Zhou, Rong},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2011},
  pages     = {87-92},
  doi       = {10.1609/AAAI.V25I1.7818},
  url       = {https://mlanthology.org/aaai/2011/schmidt2011aaai-succinct/}
}