Artificial Intelligence

Algorithms for optimal and near-optimal bidirectional search

Friday, March 16, 2018, 11:00am PDTiCal
6th floor large conference room
This event is open to the public.
AI Seminar
Nathan Sturtevant, University of Denver

Bidirectional search has been studied in many contexts for over 50 years. Despite the potential of exponential gain, bidirectional search algorithms have not been widely used in practice because they are often outperformed by unidirectional search. This has variously been attributed to the search frontiers missing each other, passing through each other, or the long time taken to prove the optimal solution. This talk will build on recent theoretical foundations to develop two new algorithms for bidirectional search. The first, fractional MM, can solve bidirectional search problems using the minimum possible number of necessary node expansions, however it requires a priori knowledge of the correct parameters for each problem instance in order to do so. The second, Near-Optimal Bidirectional Search (NBS), is guaranteed to expand no more than two times the necessary node expansions; we prove that no admissible algorithm can have better worst case performance. These algorithms give us new insights and tools to understand and use bidirectional search in practice.


Nathan Sturtevant is an Associate Professor in the Computer Science Department at the University of Denver. His scientific research focuses on search in Artificial Intelligence. This includes work on heuristic and combinatorial search for single and multiple agents, including bidirectional search, automated abstraction, heuristics, refinement search, search for game design, heuristic learning, inconsistent heuristics, cooperative search, large-scale and parallel search. Particular applications include pathfinding and planning in memory-constrained real-time environments (e.g. commercial video games) as well as algorithms for building and using memory-based heuristics via large-scale search. Other work considers theoretical and practical issues in games with more than two players, including opponent modeling, learning, and imperfect information.

« Return to Events