W-restrained Bidirectional Bounded-Suboptimal Heuristic Search

Authors

  • Dor Atzmon Royal Holloway, University of London
  • Shahaf S. Shperberg Ben-Gurion University
  • Netanel Sabah Ben-Gurion University
  • Ariel Felner Ben-Gurion University
  • Nathan R. Sturtevant University of Alberta

DOI:

https://doi.org/10.1609/icaps.v33i1.27175

Keywords:

Heuristic search

Abstract

In this paper, we develop theoretical foundations for bidirectional bounded-suboptimal search (BiBSS) based on recent advancements in optimal bidirectional search. In addition, we introduce a BiBSS variant of the prominent meet-in-the-middle (MM) algorithm, called Weighted MM (WMM). We show that WMM has an interesting property of being W-restrained, and study it empirically.
ICAPS-23 Proceedings Cover

Downloads

Published

2023-07-01

How to Cite

Atzmon, D., Shperberg, S. S., Sabah, N., Felner, A., & Sturtevant, N. R. (2023). W-restrained Bidirectional Bounded-Suboptimal Heuristic Search. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1), 26-30. https://doi.org/10.1609/icaps.v33i1.27175

Issue

Vol. 33 (2023): Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling

Section

Main Track