License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.12
URN: urn:nbn:de:0030-drops-175158
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17515/
Banerjee, Siddhartha ;
Cohen-Addad, Vincent ;
Gupta, Anupam ;
Li, Zhouzi
Graph Searching with Predictions
Abstract
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.
BibTeX - Entry
@InProceedings{banerjee_et_al:LIPIcs.ITCS.2023.12,
author = {Banerjee, Siddhartha and Cohen-Addad, Vincent and Gupta, Anupam and Li, Zhouzi},
title = {{Graph Searching with Predictions}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {12:1--12:24},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-263-1},
ISSN = {1868-8969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17515},
URN = {urn:nbn:de:0030-drops-175158},
doi = {10.4230/LIPIcs.ITCS.2023.12},
annote = {Keywords: Algorithms with predictions, network algorithms, graph search}
}
|
Keywords: |
|
Algorithms with predictions, network algorithms, graph search |
|
Collection: |
|
14th Innovations in Theoretical Computer Science Conference (ITCS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
01.02.2023 |
