12:30–1:30 pm
Jones 303 5747 S. Ellis Avenue
Adela DePavia
Committee on Computational and Applied Mathematics
The University of Chicago
"Algorithms for Graph Searching Problems Based on work with Erasmo Tani and Ali Vakilian""
Abstract
When considering modern autonomous agents searching an unknown environment, a natural notion of algorithmic cost is total distance travelled by the searcher. However, classical algorithms focus on computational notions of cost, and do not provide optimality or efficiency guarantees in terms of distance travelled. In this talk we consider algorithms for search on graphs, which model broader applications. In graph searching problems, an agent starting at some vertex \(r\) has to traverse a (potentially unknown) graph \(G\) to find a hidden goal node \(g\) while minimizing the total distance travelled. We study a recently introduced setting in which at any node \(v\), the agent receives a noisy estimate of the distance from \(v\) to \(g\). We will discuss the first formal algorithmic guarantees for search on unknown weighted graphs, and consider lowerbounds that show these algorithms have optimal or nearly-optimal dependence on the prediction error.