Succinct set-encoding for state-space search
We introduce the Level-Ordered-Edge-Sequence (LOES), a succinct 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 explicit 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 explicit state representation, increasing the number of problems that can be solved cost-optimally.
- download PDF (529K)
Schmidt, T.; Zhou, R. Succinct set-encoding for state-space search. Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI-11); 2011 August 7-11, San Francisco, CA.
Copyright © AAAI, 2011. All rights reserved; not for redistribution.