Euclidean pathfinding with compressed path databases

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

We consider optimal and anytime algorithms for the Euclidean Shortest Path Problem (ESPP) in two dimensions. Our approach leverages ideas from two recent works: Polyanya, a mesh-based ESPP planner which we use to represent and reason about the environment, and Compressed Path Databases, a speedup technique for pathfinding on grids and spatial networks, which we exploit to compute fast candidate paths. In a range of experiments and empirical comparisons we show that: (i) the auxiliary data structures required by the new method are cheap to build and store; (ii) for optimal search, the new algorithm is faster than a range of recent ESPP planners, with speedups ranging from several factors to over one order of magnitude; (iii) for anytime search, where feasible solutions are needed fast, we report even better runtimes.

Original languageEnglish
Title of host publicationProceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
EditorsChristian Bessiere
Place of PublicationMarina del Rey CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages4229-4235
Number of pages7
ISBN (Electronic)9780999241165
DOIs
Publication statusPublished - 2020
EventInternational Joint Conference on Artificial Intelligence-Pacific Rim International Conference on Artificial Intelligence 2020 - Yokohama, Japan
Duration: 7 Jan 202115 Jan 2021
Conference number: 29th/17th
https://www.ijcai.org/Proceedings/2020/ (Proceedings)
https://ijcai20.org (Website)

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Volume2021-January
ISSN (Print)1045-0823

Conference

ConferenceInternational Joint Conference on Artificial Intelligence-Pacific Rim International Conference on Artificial Intelligence 2020
Abbreviated titleIJCAI-PRICAI 2020
Country/TerritoryJapan
CityYokohama
Period7/01/2115/01/21
OtherIJCAI-PRICAI 2020, the 29th International Joint Conference on Artificial Intelligence and the 17th Pacific Rim International Conference on Artificial Intelligence!IJCAI-PRICAI2020 will take place January 7-15, 2021 online in a virtual reality in Japanese Standard Time (JST) zone.
Internet address

Keywords

  • Robotics
  • Motion and Path Planning
  • Heuristic Search and Game Playing
  • Heuristic Search

Cite this