Learning-Based Algorithms for Graph Searching Problems

arXiv:2402.17736v1 Announce Type: cross
Abstract: We consider the problem of graph searching with prediction recently introduced by Banerjee et al. (2022). In this problem, 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 setting in which at any node $v$, the agent receives a noisy estimate of the distance from $v$ to $g$. We design algorithms for this …

abstract agent algorithms arxiv cs.ai cs.ds cs.lg graph hidden node prediction searching study total type vertex