DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2022.62

Embeddings and Labeling Schemes for A*

Authors: Talya Eden, Piotr Indyk, and Haike Xu

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract

A* is a classic and popular method for graphs search and path finding. It assumes the existence of a heuristic function h(u,t) that estimates the shortest distance from any input node u to the destination t. Traditionally, heuristics have been handcrafted by domain experts. However, over the last few years, there has been a growing interest in learning heuristic functions. Such learned heuristics estimate the distance between given nodes based on "features" of those nodes. In this paper we formalize and initiate the study of such feature-based heuristics. In particular, we consider heuristics induced by norm embeddings and distance labeling schemes, and provide lower bounds for the tradeoffs between the number of dimensions or bits used to represent each graph node, and the running time of the A* algorithm. We also show that, under natural assumptions, our lower bounds are almost optimal.

Cite as

Talya Eden, Piotr Indyk, and Haike Xu. Embeddings and Labeling Schemes for A*. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 62:1-62:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{eden_et_al:LIPIcs.ITCS.2022.62,
  author =	{Eden, Talya and Indyk, Piotr and Xu, Haike},
  title =	{{Embeddings and Labeling Schemes for A*}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{62:1--62:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.62},
  URN =		{urn:nbn:de:0030-drops-156585},
  doi =		{10.4230/LIPIcs.ITCS.2022.62},
  annote =	{Keywords: A* algorithm, path finding, graph search}
}

Search Results

Documents authored by Xu, Haike

Embeddings and Labeling Schemes for A*

Abstract

Cite as

Thanks for your feedback!

Could not send message