Edge Partitioning in Parallel Structured Duplicate Detection

We show how edge partitioning, a technique originally developed for external-memory search, can be used to reduce the number of slow synchronization operations needed in parallel graph search. We show that edge partitioning improves on a previous technique called parallel structured duplicate detection by allowing a higher degree of concurrency, even for search problems with little or no inherent locality. For domain-independent graph search, we also show that edge partitioning significantly improves search speed by improving the efficiency of precondition checking. We demonstrate the effectiveness of this approach to parallel graph search for domain-independent STRIPS planning.

Authors

• Rong Zhou 0001
• Tim Schmidt
• Eric A. Hansen
• Minh Binh Do
• Serdar Uckun

Keywords

• parallel search
• heuristic search
• planning