Fast optimal and bounded suboptimal Euclidean pathfinding

DOI10.1016/J.ARTINT.2021.103624MaRDI QIDQ2060748zbMATH OpenOpenAlexWikidataFDO

Authors Bojie Shen, Muhammad Aamir Cheema, Daniel Damir Harabor, Peter J. Stuckey

Publication date 13 December 2021

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.artint.2021.103624

zbMATH Keywords

compressed path databasesEuclidean shortest path planningheuristic search

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Euclidean shortest paths. Exact or approximate algorithms.
• Application of the A^* algorithm to problems of the Euclidean shortest paths in the plane with polygonal obstacles
• SHORTEST PATHS AMONG OBSTACLES IN THE PLANE
• Approximate Euclidean Shortest Paths in 3-Space
• scientific article; zbMATH DE number 910885

Cites work

• Anytime heuristic search
• Compressing optimal paths with run length encoding
• Computing minimum length paths of a given homotopy class
• Constrained Delaunay triangulations
• Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks
• Field D^*: An interpolation-based path planner and replanner
• Optimal any-angle pathfinding in practice
• Optimal packing and covering in the plane are NP-complete

Cited in

(5)

• Subregion graph: a path planning acceleration structure for characters with various motion types in very large environments
• Optimal any-angle pathfinding in practice
• Optimal any-angle pathfinding on a sphere
• Regarding goal bounding and jump point search
• On approximating shortest paths in weighted triangular tessellations

This page was built for publication: Fast optimal and bounded suboptimal Euclidean pathfinding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2060748)