Shortest path in multi-source single-goal scenarios: an A* algorithm with distance transform approach
Loading...
Date
2024-11-01
Authors
Suthakar, S.
Sinthumathy, S.
Anoja, R.
Journal Title
Journal ISSN
Volume Title
Publisher
Postgraduate Institute of Science (PGIS), University of Peradeniya, Sri Lanka
Abstract
Finding the shortest path in multi-source, single-goal scenarios remains a crucial challenge in various applications, such as robotics, drone navigation, and network routing. This study proposed a novel method combining the A* algorithm with Distance Transformation to compute the shortest path efficiently. While the traditional A* algorithm uses heuristic values and movement costs to determine the optimal path, it can be computationally intensive in environments with numerous obstacles. By incorporating Distance Transformation, the proposed algorithm refines heuristic calculations, which improves the accuracy by accounting for obstacle distribution and proximity, leading to more precise path estimation and faster convergence. The experimental results demonstrated that the combined approach significantly reduces computational time and memory usage while maintaining the accuracy of the pathfinding process. This method can be applied to a variety of spatial graphs, making it well-suited for real-world applications requiring efficient and fast pathfinding.
Description
Keywords
A* algorithm , Distance transformation , Heuristic calculation , Multi-source single-goal , Shortest path
Citation
Proceedings of the Postgraduate Institute of Science Research Congress (RESCON) -2024, University of Peradeniya, P 97