Heuristic Search for Path Finding with Refuelling
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929727746342912 |
|---|---|
| author | Zhao, Shizhe Nandy, Anushtup Choset, Howie Rathinam, Sivakumar Ren, Zhongqiang |
| author_facet | Zhao, Shizhe Nandy, Anushtup Choset, Howie Rathinam, Sivakumar Ren, Zhongqiang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2309_10796 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Heuristic Search for Path Finding with Refuelling Zhao, Shizhe Nandy, Anushtup Choset, Howie Rathinam, Sivakumar Ren, Zhongqiang Robotics Artificial Intelligence 68T40 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. |
| title | Heuristic Search for Path Finding with Refuelling |
| topic | Robotics Artificial Intelligence 68T40 |
| url | https://arxiv.org/abs/2309.10796 |