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

Question

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 1

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, then 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 also be that you have faulty neighbor generation or cost calculator.

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