סמינר מכון AI תאריך 25.5.26 יום ב'

Speaker: Lior Siag Supervisor: Prof. Ariel Felner and Dr. Shahaf Shperberg Date: Monday, 25/5, talk starts at 12:05 Place: Building 37, room 202 Talk title: New Directions in Bidirectional Search Abstract: Heuristic search uses heuristic functions to efficiently explore complex search spaces. Bidirectional heuristic search (BiHS) extends this paradigm by simultaneously searching from the start and goal states to reduce overall search effort. This work expands on both the theoretical foundations and practical capabilities of BiHS, aiming to clarify when bidirectional search is effective and how it can be made scalable in practice. It presents a unifying theoretical perspective on BiHS with front-to-end (F2E) heuristics and shows empirically that modern algorithms often operate close to known theoretical lower bounds on the number of node expansions. It further analyzes front-to-front (F2F) heuristics, highlighting the tradeoff between their ability to reduce node expansions and their additional computational overhead. Beyond theoretical insights, this work addresses scalability through parallelization and external-memory search, introducing a general framework that enables different BiHS algorithms to efficiently exploit multicore architectures and external storage, allowing them to solve substantially larger problem instances. Finally, it extends BiHS to the bounded-suboptimal setting, designing algorithms that maintain provable solution quality guarantees while further improving search efficiency. Collectively, these contributions provide a more unified, scalable, and general understanding of bidirectional heuristic search