The A* algorithm is a widely used pathfinding and graph traversal algorithm known for its efficiency in finding the shortest path between two points. It combines the strengths of Dijkstra’s Algorithm and Greedy Best-First Search by using both the actual distance traveled from the start point and an estimated distance to the goal, which makes it optimal and complete. A* is commonly applied in robotics, video games, and navigation systems due to its ability to find the most efficient route. Its performance depends heavily on the heuristic used, and while it is generally fast, it can be computationally expensive for large or complex maps. The drawback of the A* algorithm is that it examines each traversed point, resulting in low speed and high data storage requirements. This paper introduces an improved A* algorithm, which combines three techniques: expansion distance, reducing redundant points, and smoothing the path planning.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Optimizing the Path Planning by the Improved A* Algorithm

  • Tien Dung Vu,
  • Vu Toan Thang,
  • Quang Hung Tran,
  • Han Quang Vu Ngo,
  • Doan Thanh Xuan

摘要

The A* algorithm is a widely used pathfinding and graph traversal algorithm known for its efficiency in finding the shortest path between two points. It combines the strengths of Dijkstra’s Algorithm and Greedy Best-First Search by using both the actual distance traveled from the start point and an estimated distance to the goal, which makes it optimal and complete. A* is commonly applied in robotics, video games, and navigation systems due to its ability to find the most efficient route. Its performance depends heavily on the heuristic used, and while it is generally fast, it can be computationally expensive for large or complex maps. The drawback of the A* algorithm is that it examines each traversed point, resulting in low speed and high data storage requirements. This paper introduces an improved A* algorithm, which combines three techniques: expansion distance, reducing redundant points, and smoothing the path planning.