Timezone: »
Poster
Parallel Recursive Best-First AND/OR Search for Exact MAP Inference in Graphical Models
Akihiro Kishimoto · Radu Marinescu · Adi Botea
The paper presents and evaluates the power of parallel search for exact MAP inference in graphical models. We introduce a new parallel shared-memory recursive best-first AND/OR search algorithm, called SPRBFAOO, that explores the search space in a best-first manner while operating with restricted memory. Our experiments show that SPRBFAOO is often superior to the current state-of-the-art sequential AND/OR search approaches, leading to considerable speed-ups (up to 7-fold with 12 threads), especially on hard problem instances.
Author Information
Akihiro Kishimoto (IBM Research)
Radu Marinescu (IBM Research, Ireland)
Adi Botea (IBM Research)
More from the Same Authors
-
2019 Poster: Depth-First Proof-Number Search with Heuristic Edge Cost and Application to Chemical Synthesis Planning »
Akihiro Kishimoto · Beat Buesser · Bei Chen · Adi Botea -
2019 Poster: Counting the Optimal Solutions in Graphical Models »
Radu Marinescu · Rina Dechter -
2019 Spotlight: Counting the Optimal Solutions in Graphical Models »
Radu Marinescu · Rina Dechter -
2018 Poster: From Stochastic Planning to Marginal MAP »
Hao(Jackson) Cui · Radu Marinescu · Roni Khardon