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 search task on unknown
graphs. We establish the first formal guarantees on unknown weighted graphs and
provide lower bounds showing that the algorithms we propose have optimal or
nearly-optimal dependence on the prediction error. Further, we perform
numerical experiments demonstrating that in addition to being robust to
adversarial error, our algorithms perform well in typical instances in which
the error is stochastic. Finally, we provide alternative simpler performance
bounds on the algorithms of Banerjee et al. (2022) for the case of searching on
a known graph, and establish new lower bounds for this setting.

在这篇研究论文中，我们考虑了最近由 Banerjee 等人（2022）提出的预测图搜索问题。我们设计了一种算法来应对未知图上的搜索任务，并且在预测误差上提供了最优或接近最优的算法依赖关系的保证。此外，我们还提出了 Banerjee 等人（2022）算法在已知图上的性能边界，并为该情景建立了新的下界。