Past talk · AI/ML Seminar Series
Policy and Heuristic-Guided Tree Search Algorithms
Assistant Professor, Department of Computer Science, University of Alberta
- Date & time
- Monday, May 3, 2021 · 1:00 PM
- Location
- Online (live stream)
Abstract
In this talk I describe two tree search algorithms that use a policy to guide the search. I start with Levin tree search (LTS), a best-first search algorithm with guarantees on the number of nodes it needs to expand, based on the quality of the policy it employs. I then describe Policy-Guided Heuristic Search (PHS), which uses both a policy and a heuristic function to guide the search, with guarantees based on the quality of both. Empirical results show that LTS and PHS compare favorably with A*, Weighted A*, Greedy Best-First Search, and PUCT on single-agent shortest-path problems.
About the speaker
Levi Lelis is an Assistant Professor at the University of Alberta, Canada, and a Professor on leave from Universidade Federal de Viçosa, Brazil. He is interested in heuristic search, machine learning, and program synthesis.