A passage time–cost optimal A* algorithm for cross-country path planning

Abstract

Path planning plays a crucial role in various domains, such as autonomous driving, robot navigation, logistics and emergency rescue. In applications such as logistics distribution and emergency rescue, the passage time cost is often a key factor. Traditional path planning algorithms prioritize the shortest or cost-optimal paths while overlooking passage time efficiency. This paper proposes an improved A* algorithm for the optimal passage time cost. First, we used the analytic hierarchy process method to establish the passage time cost based on multiple topographic and geological factors. Then, we improved the heuristic function in the A* algorithm by taking the time cost as the evaluation index. Finally, the performance of the improved A* algorithm was validated under rectangular and hexagonal grid settings and compared to that of the classical A* and Dijkstra algorithms. The experimental results show that the path passage time planned with the proposed time–cost optimal A* algorithm is reduced by 20.21% and 20.08% on average compared with that of the path shortest A* algorithm under rectangular and hexagonal grids, respectively. The proposed time–cost optimal A* algorithm saves computing time by 9.08% and 44.56% under rectangular and hexagonal grids, respectively, compared to Dijkstra. The passage time costs of the paths planned by the proposed A* algorithm under hexagonal grids are reduced by 5.99%-13.98% compared to those under rectangular grids, indicating that hexagonal grids are more suitable than rectangular grids for path planning. The proposed method reduces the response time, enhances the life-saving efficiency, and minimizes casualties and property damage when determining the fastest rescue route for emergency scenarios.

Keywords

• Passage time-cost optimal path planning
• Analytic hierarchy process
• Hexagonal grid
• A* algorithm
• Dijkstra’s algorithm