Improved A* algorithm applied in dynamic environment for pathfinding

摘要

Pathfinding is widely applied when encountering autonomous driving, mobile robot pathfinding, and so on. Traditional pathfinding algorithms have certain limitations such as high computational cost, overly dependent on the design of heuristics, and unable to focus on muti-objective. This research deals with the comparison of three algorithms applied in the same pathfinding situation. A delivery robot is taken as the object of study, and the simulation of the same map and obstacle design ensures three algorithms are tested under the same circumstances. To improve the A star algorithm, enhancements are applied, such as real-time heuristic adjustments, adaptive cost functions, and dynamic re-planning techniques. These modifications allow the algorithm to efficiently re-evaluate paths as environmental conditions evolve, ensuring timely and optimal decision-making. After using Python coding to manipulate the simulation of A star, Dijkstra, and rapidly exploring random tree (RRT) algorithms, A star algorithm performs best in the pathfinding problems. Research in the A star algorithm enables significant improvement in the calculation efficiency by enhancing the flexibility of the heuristic function used in A star while cutting back on search space and computation time spent which leads to a great improvement in pathfinding tasks.