Succinct Set-Encoding for State-Space Search

Authors

  • Tim Schmidt Palo Alto Research Center, Inc. and Technische Universität München
  • Rong Zhou Palo Alto Research Center, Inc.

DOI:

https://doi.org/10.1609/aaai.v25i1.7818

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.

Downloads

Published

2011-08-04

How to Cite

Schmidt, T., & Zhou, R. (2011). Succinct Set-Encoding for State-Space Search. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 87-92. https://doi.org/10.1609/aaai.v25i1.7818

Issue

Section

Constraints, Satisfiability, and Search