OultimoCoder OultimoCoder - 4 days ago 5
Python Question

Why doesn't my a* algorithm take the shortest route?

My a* algorithm doesn't always take the shortest path.

In this image the robot has to traverse to the black squares, the river and trees are obstacles. The black line is the path it took, which is clearly not the shortest path as it should not have dipped.

http://imgur.com/GBoq9py

Here is my code for a* and the heuristic I am using:

def HeuristicCostEstimate(start, goal):
(x1, y1) = start
(x2, y2) = goal
return abs(x1 - x2) + abs(y1 - y2)

def AStar(grid, start, goal):
entry = 1
openSet = []
heappush(openSet,(1, entry, start))
cameFrom = {}
currentCost = {}
cameFrom[tuple(start)] = None
currentCost[tuple(start)] = 0
while not openSet == []:
current = heappop(openSet)[2]
print(current)
if current == goal:
break

for next in grid.Neighbours(current):
newCost = currentCost[tuple(current)] + grid.Cost(current, next)
if tuple(next) not in currentCost or newCost < currentCost[tuple(next)]:
currentCost[tuple(next)] = newCost
priority = newCost + HeuristicCostEstimate(goal, next)
entry +=1
heappush(openSet,(priority, entry, next))
cameFrom[tuple(next)] = current

return cameFrom, current


http://pastebin.com/bEw8x0Lx

Thanks for any help! And feel free to ask me to clarify anything.

Edit: removing the heuristic by returning 0 solves this problem. Which suggests the problem lies with my heuristic. Would anyone know what might be causing it?

Answer

A* is not always guaranteed to find a shortest path. While it is true that without a heuristic (h(n) = 0), the shortest path will be found (it becomes Dijkstra's algorithm), this does not mean that with any heuristic the shortest path will be found. The heuristic is added to speed up this search and the trade off is that in some cases you will not find the shortest path.

To understand whats going on, remember that the heuristic is an estimation of the actual distance to target. If the prediction is perfect, the graph is essentially pre-calculated. Consider the following cases.

  • If your heuristic is lower than the actual cost, the shortest path will be found.

  • If the heuristic is equal to the actual cost, all shortest paths are essentially pre-calculated, and the shortest path will be found without any unnecessary exploring.

  • If the heuristic is sometimes greater than the actual cost, than A* is not guaranteed to find the shortest path, but search time may be faster than if the heuristic made underestimations.

It seems that your heuristic is underestimating the cost. It could be you have faulty neighbor generation or cost calculator.

For further reading: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Comments