A hybrid optimal-approximate path planning algorithm

Path planning is the problem of finding the lowest-cost path between two endpoints in a weighted graph. An optimal algorithm, such as A*, is guaranteed to return the lowest-cost path. However, the computational expense of A* is high on a class of graphs called terrains, motivating the development of approximate algorithms such as HTAP (the hierarchical terrain representation for approximate paths). HTAP has computational cost linear in path length, rather than A*´s quadratic complexity, but does not guarantee the lowest cost path. However, HTAP´s overhead means that very short paths are disproportionately costly to find. In this paper, we propose a hybrid algorithm which uses HTAP for long paths and A* for short paths. We empirically compare the hybrid algorithm to the HTAP algorithm on the basis of computational cost. The hybrid algorithm has a significant performance advantage over HTAP in the case of very short paths, and is the same as HTAP for long paths. We report results for a number of terrains, giving performance profiles with respect to path length