Document Open Access Logo

Embeddings and Labeling Schemes for A*

Authors Talya Eden, Piotr Indyk, Haike Xu

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.62.pdf
  • Filesize: 0.72 MB
  • 19 pages

Document Identifiers

Author Details

Talya Eden
  • Massachusetts Institute of Technology, Cambridge, MA, USA
  • Boston University, MA, USA
Piotr Indyk
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Haike Xu
  • Tsinghua University, Beijing, China

Funding

  • Eden, Talya: Partially supported by the NSF Grant CCF-1740751, the Eric and Wendy Schmidt Fund, Ben-Gurion University, and the Computer Science Department at Boston University.
  • Indyk, Piotr: Partially supported by the NSF TRIPODS program (awards CCF-1740751 and DMS-2022448) and Simons Investigator Award.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.ITCS.2022.62

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • A* algorithm
  • path finding
  • graph search

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ittai Abraham, Amos Fiat, Andrew V Goldberg, and Renato F Werneck. Highway dimension, shortest paths, and provably efficient algorithms. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 782-793. SIAM, 2010. Google Scholar
  2. Noga Alon and Pavel Pudlák. Equilateral sets in l_pⁿ. Geometric & Functional Analysis GAFA, 13(3):467-482, 2003. Google Scholar
  3. Masataro Asai and Alex Fukunaga. Tiebreaking strategies for a* search: How to explore the final frontier. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016. Google Scholar
  4. Masataro Asai and Alex Fukunaga. Tie-breaking strategies for cost-optimal best first search. Journal of Artificial Intelligence Research, 58:67-121, 2017. Google Scholar
  5. Mohak Bhardwaj, Sanjiban Choudhury, and Sebastian Scherer. Learning heuristic search via imitation. In Conference on Robot Learning, pages 271-280. PMLR, 2017. Google Scholar
  6. Binghong Chen, Chengtao Li, Hanjun Dai, and Le Song. Retro*: learning retrosynthetic planning with neural guided a* search. In International Conference on Machine Learning, pages 1608-1616. PMLR, 2020. Google Scholar
  7. Xiao Cui and Hao Shi. A*-based pathfinding in modern computer games. International Journal of Computer Science and Network Security, 11(1):125-130, 2011. Google Scholar
  8. Talya Eden, Piotr Indyk, and Haike Xu. Embeddings and labeling schemes for a*, 2021. URL: http://arxiv.org/abs/2111.10041.
  9. Cyril Gavoille, David Peleg, Stéphane Pérennes, and Ran Raz. Distance labeling in graphs. Journal of Algorithms, 53(1):85-112, 2004. Google Scholar
  10. Andrew V Goldberg and Chris Harrelson. Computing the shortest path: A* search meets graph theory. In SODA, volume 5, pages 156-165, 2005. Google Scholar
  11. Richard K. Guy. An olla-podrida of open problems, often oddly posed. The American Mathematical Monthly, 90(3):196-200, 1983. URL: http://www.jstor.org/stable/2975549.
  12. Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100-107, 1968. URL: https://doi.org/10.1109/TSSC.1968.300136.
  13. Assaf Naor. Metric dimension reduction: a snapshot of the ribe program. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 759-837. World Scientific, 2018. Google Scholar
  14. Anup Rao and Amir Yehudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020. Google Scholar
  15. Thomas Rathfux, Hermann Kaindl, Ralph Hoch, and Franz Lukasch. Efficiently finding optimal solutions to easy problems in design space exploration: A* tie-breaking. In Proceedings of the 14th International Conference on Software Technologies, ICSOFT 2019, pages 595-604, Setubal, PRT, 2019. SCITEPRESS - Science and Technology Publications, Lda. URL: https://doi.org/10.5220/0008119405950604.
  16. Konrad J. Swanepoel and Amer Math Monthly. A problem of kusner on equilateral sets. Archiv der Mathematik, 2004. Google Scholar
  17. Ryo Yonetani, Tatsunori Taniai, Mohammadamin Barekatain, Mai Nishimura, and Asako Kanezaki. Path planning using neural A* search. In International Conference on Machine Learning, 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact