Dynamic state-space partitioning in external-memory graph search

The scalability of optimal sequential planning can be improved by using external-memory graph search. State-of-the-art external-memory graph search algorithms rely on a state-space projection function, or hash function, that partitions the stored nodes of the state-space search graph into groups of nodes that are stored as separate files on disk. Search performance depends on properties of the partition; whether the number of unique nodes in a file always fits in RAM, the number of files into which the nodes of the state-space graph are partitioned, and how well the partition captures local structure in the graph. Previous work relies on a static partition of the state space, but it can be difficult for a static partition to simultaneously satisfy all of these criteria. We introduce a method for dynamic partitioning and show that it leads to improved search performance in solving STRIPS planning problems.

Citation

Zhou, R.; Hansen, E. A. Dynamic state-space partitioning in external-memory graph search. ICAPS 2011.Twenty-First International Conference on Automated Planning and Scheduling (ICAPS-2011); 2011 June 11-16; Freiburg, Germany.