AAAI Publications, Third Annual Symposium on Combinatorial Search

Font Size: 
Edge Partitioning in Parallel Structured Duplicate Detection
Rong Zhou, Tim Schmidt, Eric A. Hansen, Minh B. Do, Serdar Uckun

Last modified: 2010-08-25


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.


parallel search; heuristic search; planning

Full Text: PDF