Parallel AND/OR Search for Marginal MAP


  • Radu Marinescu IBM Research
  • Akihiro Kishimoto IBM Research
  • Adi Botea Eaton



Marginal MAP is a difficult mixed inference task for graphical models. Existing state-of-the-art algorithms for solving exactly this task are based on either depth-first or best-first sequential search over an AND/OR search space. In this paper, we explore and evaluate for the first time the power of parallel search for exact Marginal MAP inference. We introduce a new parallel shared-memory recursive best-first AND/OR search algorithm that explores the search space in a best-first manner while operating with limited memory. Subsequently, we develop a complete parallel search scheme that only parallelizes the conditional likelihood computations. We also extend the proposed algorithms into depth-first parallel search schemes. Our experiments on difficult benchmarks demonstrate the effectiveness of the parallel search algorithms against current sequential methods for solving Marginal MAP exactly.




How to Cite

Marinescu, R., Kishimoto, A., & Botea, A. (2020). Parallel AND/OR Search for Marginal MAP. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06), 10226-10234.



AAAI Technical Track: Reasoning under Uncertainty