An Empirical Comparison of Any-Angle Path-Planning Algorithms
Tansel Uras, Sven Koenig
2021Proceedings of the International Symposium on Combinatorial Search48 citationsDOIOpen Access PDF
Abstract
We compare five any-angle path-planning algorithms, Theta*, Block A*, Field D*, ANYA, and Any-Angle Subgoal Graphs in terms of solution quality and runtime. Any-angle path-planning is a fairly new research area, and no direct comparison exists between these algorithms. We implement each algorithm from scratch and use similar implementations to provide a fair comparison.
Topics & Concepts
ImplementationBlock (permutation group theory)Path (computing)Motion planningAlgorithmComputer scienceField (mathematics)Quality (philosophy)MathematicsArtificial intelligenceGeometryPure mathematicsProgramming languageRobotPhilosophyEpistemologyRobotic Path Planning AlgorithmsSoftware Testing and Debugging TechniquesComputational Geometry and Mesh Generation