Approximate Path Planning

HTAP (download 780 KB)

Path planning is the problem of finding the least-cost path through a weighted graph. The above images show the amount of the graph searched (nodes marked in white) by A*, on the left, and by the HTAP algorithm, on the right. As is typical for a path of this length, A* had to search nearly the entire graph. The HTAP algorithm returns an approximately optimal path, orders of magnitude faster.