Succinct set-encoding for state-space search

• Twenty-Fifth AAAI Conference on Artificial Intelligence (AAAI-11)

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.

• go to publisher site »

read more

• download PDF (529K)

citation

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

Copyright © AAAI, 2011. All rights reserved; not for redistribution.