Heuristic Search for Path Finding with Refuelling
This addresses the problem of efficiently computing optimal refueling paths for robots or vehicles with limited fuel and stops, though it is incremental as it builds on existing heuristic search methods.
The paper tackles the Gas Station Problem (GSP), a path-finding challenge with refueling constraints, by developing the Refuel A* (RF-A*) algorithm, which finds optimal solutions and runs 2 to 8 times faster than existing methods on large city maps with hundreds of gas stations.
This paper considers a generalization of the Path Finding (PF) problem with refuelling constraints referred to as the Gas Station Problem (GSP). Similar to PF, given a graph where vertices are gas stations with known fuel prices, and edge costs are the gas consumption between the two vertices, GSP seeks a minimum-cost path from the start to the goal vertex for a robot with a limited gas tank and a limited number of refuelling stops. While GSP is polynomial-time solvable, it remains a challenge to quickly compute an optimal solution in practice since it requires simultaneously determine the path, where to make the stops, and the amount to refuel at each stop. This paper develops a heuristic search algorithm called Refuel A$^*$ (RF-A$^*$) that iteratively constructs partial solution paths from the start to the goal guided by a heuristic while leveraging dominance rules for pruning during planning. RF-A$^*$ is guaranteed to find an optimal solution and often runs 2 to 8 times faster than the existing approaches in large city maps with several hundreds of gas stations.