TY - GEN

T1 - Graph Searching with Predictions

AU - Banerjee, Siddhartha

AU - Cohen-Addad, Vincent

AU - Gupta, Anupam

AU - Li, Zhouzi

N1 - Publisher Copyright:
© Siddhartha Banerjee, Vincent Cohen-Addad, Anupam Gupta, and Zhouzi Li; licensed under Creative Commons License CC-BY 4.0.

PY - 2023/1/1

Y1 - 2023/1/1

N2 - Consider an agent 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. This setting with “help” often arises in exploring large search spaces (e.g., huge game trees) where we assume access to some score/quality function for each node, which we use to guide us towards the goal. In our case, we assume the help comes in the form of distance predictions: each node v provides a prediction f(v) of its distance to the goal vertex. Naturally if these predictions are correct, we can reach the goal along a shortest path. What if the predictions are unreliable and some of them are erroneous? Can we get an algorithm whose performance relates to the error of the predictions? In this work, we consider the problem on trees and give deterministic algorithms whose total movement cost is only O(OPT + ∆ · ERR), where OPT is the distance from the start to the goal vertex, ∆ the maximum degree, and the ERR is the total number of vertices whose predictions are erroneous. We show this guarantee is optimal. We then 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 devise a search strategy of low cost. For this planning version, we go beyond trees and give an algorithms which gets good performance on (weighted) graphs with bounded doubling dimension.

AB - Consider an agent 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. This setting with “help” often arises in exploring large search spaces (e.g., huge game trees) where we assume access to some score/quality function for each node, which we use to guide us towards the goal. In our case, we assume the help comes in the form of distance predictions: each node v provides a prediction f(v) of its distance to the goal vertex. Naturally if these predictions are correct, we can reach the goal along a shortest path. What if the predictions are unreliable and some of them are erroneous? Can we get an algorithm whose performance relates to the error of the predictions? In this work, we consider the problem on trees and give deterministic algorithms whose total movement cost is only O(OPT + ∆ · ERR), where OPT is the distance from the start to the goal vertex, ∆ the maximum degree, and the ERR is the total number of vertices whose predictions are erroneous. We show this guarantee is optimal. We then 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 devise a search strategy of low cost. For this planning version, we go beyond trees and give an algorithms which gets good performance on (weighted) graphs with bounded doubling dimension.

KW - Algorithms with predictions

KW - graph search

KW - network algorithms

UR - http://www.scopus.com/inward/record.url?scp=85147538104&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85147538104&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ITCS.2023.12

DO - 10.4230/LIPIcs.ITCS.2023.12

M3 - Conference contribution

AN - SCOPUS:85147538104

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023

A2 - Kalai, Yael Tauman

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 14th Innovations in Theoretical Computer Science Conference, ITCS 2023

Y2 - 10 January 2023 through 13 January 2023

ER -