Key result
Safe-triangle path planning lowers computational complexity compared to quadtree-based mapping in simulated workspaces.
Why the study?
The computational complexity of path planning algorithms using safe triangles versus quadtree workspace representations was not well characterized.
This study compares the computational complexity of safe triangles versus quadtree approaches for 2D path planning.
Simulation comparison informs path planning design; leaves open real-world validation in dynamic or clinical settings.
Computational complexity of two path planning approaches for a two-dimensional (2D) work space is considered: The approach using safe triangles and the approach based on quadtree. The average cost of establishing work space representation, i.e. of building the safe triangles and the quadtree respectively, are estimated. Both approaches are simulated to plan paths for numerous work spaces with obstacles which are generated at random. The results of the simulation are summarized to show the expected behavior of each approach. Comparison based on analyses and simulation is presented.
No takes yet. Share an insight, caveat, or question.
A 1991 study studied this question. Path planning approach using safe triangles vs. Path planning approach based on quadtree was evaluated on Computational complexity and average cost of establishing work space representation. A path planning approach using safe triangles was compared to a quadtree-based approach for computational complexity in simulated 2D workspaces with randomly generated obstacles.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: