Graph Searching with Predictions

Anupam Gupta
Siddhartha Banerjee
Zhouzi Li
ITCS'23(2023) (to appear)
Google Scholar


Consider an agent (say a robot) exploring an unknown graph in search of some goal state. As it walks around the graph, it learns the nodes and their neighbors. The agent only knows where the goal state is when it reaches it. How do we reach this goal while moving only a small distance? This problem seems hopeless, even on trees of bounded degree, unless we give the agent some help. In our case, this help comes in the form of *predictions*: each node $v$ provides a prediction $f(v)$ of its distance to the goal vertex. Naturally if the predictions are correct, we can reach the goal quickly. What if some of the predictions are erroneous? This naturally models graph search problems where we are given some quality function to guide us towards the goal: in our framework the quality is given by the distance predictions. In this work, we initiate a study of this problem with predictions. We consider the problem on trees (where the problem is already non-trivial) and give deterministic realgorithms whose movement cost is only $O(OPT + ERR)$, where $OPT$ is the distance from the start to the goal vertex, and the $ERR$ is the total number of vertices whose predictions are erroneous. We also consider a ``planning'' version of the problem where the graph and predictions are known at the beginning, so the agent can use this global information to quickly reach the goal. For the planning version, we give a different algorithm for trees, and then an algorithm for all (weighted) graphs with bounded doubling dimension.