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.

https://i.sstatic.net/0ws5E.jpg

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?

Disulfiram

Paste your code into your question. To make it a code block, highlight it and press Ctrl+k. – Aboutship

Thanks guys I have now edited with the relevant code. – Disulfiram

I don't get why this wouldn't be the shortest path if it had to go on the black square – Sawfish

If your heuristic can ever overestimate the cost, then it is "inadmissible" and may cause A* not to find the shortest path. Try building a test fixture that computes the actual shortest path, and compares it to your heuristic. – Ozell

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

Tort

Thank you. I figured it was to do with my heuristic not accounting for obstacles. I will see if there is a better heuristic out there. – Disulfiram

In addition to the reading I outlined in my answer, I recommend reading the discussion on following question. There are multiple good links in different answers. #29657432 – Tort

I thought my heuristic always underestimates though, because it finds the shortest distance and returns that. Is that not what it does? – Disulfiram

Your wording for A* disadvantages is not 100% correct. And your link proves it. A* is not guaranteed to find ALL pathes (which Dijkstra or BFS do at expense of search time). But A* DOES guarantee to find a single shortest path if heuristic is never larger than the true distance. And this condition is essential part of the algorithm. Otherwise it is not A* (or is its wrong implementation). Do a coding mistake in Dijkstra and it also does not guarantee to find any paths. It's like saying a modern car is not guaranteed to drive without an engine. Of course it doesn't, because it's not a car... – Gildus

And underestimating heuristic is not a problem at all as Euclidian distance is always shorter than the final path. It's overestimating which is a problem. I upvote because this is still a good unswer overall. – Gildus

Answer 2

Change your heuristic to (x1-x2)^2 + (y1-y2)^2 and you should find it generates a more accurate path.

Madame