Understanding A * heuristic for a single-purpose maze

Question

I have a maze as shown below:

|||||||||||||||||||||||||||||||||||| | P| | ||||||||||||||||||||||| |||||||| | | || | | ||||||| || | | || | | | | |||| ||||||||| || ||||| | || | | | | || || | | || | | | | | |||| ||| |||||| | | | | | | | || |||||||| | | || | | |||||||| || || ||||| | || | || ||||||||| || | | |||||| ||||||| || |||||| | |||||| | |||| || | | | |||||| ||||| | || || ||||| | |||||| | ||||| || | | |||||| ||||||||||| || || | |||||||||| |||||| | |+ |||||||||||||||| | |||||||||||||||||||||||||||||||||||| 

The goal is to find P + with subgoals

• The path to + is the lowest cost (1 hop = cost + 1)
• The number of cells found (nodes expanded) is minimized

I am trying to understand why my A * heuristic works much worse than the implementation that I have for Greedy Best First. Here are two bits of code for each:

 #Greedy Best First -- Manhattan Distance self.heuristic = abs(goalNodeXY[1] - self.xy[1]) + abs(goalNodeXY[0] - self.xy[0]) #A* -- Manhattan Distance + Path Cost from 'startNode' to 'currentNode' return abs(goalNodeXY[1] - self.xy[1]) + abs(goalNodeXY[0] - self.xy[0]) + self.costFromStart 

In both algorithms, I use heapq , a priority based on a heuristic value. The main search loop is the same for both:

 theFrontier = [] heapq.heappush(theFrontier, (stateNode.heuristic, stateNode)) #populate frontier with 'start copy' as only available Node #while !goal and frontier !empty while not GOAL_STATE and theFrontier: stateNode = heapq.heappop(theFrontier)[1] #heappop returns tuple of (weighted-idx, data) CHECKED_NODES.append(stateNode.xy) while stateNode.moves and not GOAL_STATE: EXPANDED_NODES += 1 moveDirection = heapq.heappop(stateNode.moves)[1] nextNode = Node() nextNode.setParent(stateNode) #this makes a call to setHeuristic nextNode.setLocation((stateNode.xy[0] + moveDirection[0], stateNode.xy[1] + moveDirection[1])) if nextNode.xy not in CHECKED_NODES and not isInFrontier(nextNode): if nextNode.checkGoal(): break nextNode.populateMoves() heapq.heappush(theFrontier, (nextNode.heuristic,nextNode)) 

So now we come to this problem. While A * finds the optimal path, it is quite expensive at the same time. To find the optimal cost:68 path, it expands (moves and searches) 452 nodes for this.

While the Greedy Best implementation, I found a sub-optimal path (cost: 74) in only 160 extensions.

I'm really trying to figure out where I am going wrong. I understand that the Greedy Best First algorithms can behave so naturally, but the gap in the node extensions is so wide that I feel that something is wrong here. Any help would be appreciated. I am happy to add details if what I inserted above is somewhat unclear.

Answer 1

A * provides an optimal answer to the problem, the greedy best first search provides any solution.

A * was expected to do more work.

If you need an A * option that is not optimal anymore, but returns a solution much faster, you can look at weighted A *. It simply consists in putting weight in a heuristic (weight> 1). In practice, this gives you a huge increase in productivity.

For example, you could try the following:

 return 2*(abs(goalNodeXY[1] - self.xy[1]) + abs(goalNodeXY[0] - self.xy[0])) + self.costFromStart 

Answer 2

A * search tries to find the best possible solution to the problem, and the greedy best-first just tries to find some solution at all. Task A * has a much more complicated task, and it should put a lot of effort into exploring every path that might be the best, while the greedy algorithm is best suited directly to the option that is closest to the target.

Answer 3

Since this was not allowed, and even if something wrong, the OP specified can be resolved with a Fezvez answer , I feel that I need to ask about it and maybe answer what is wrong and why the Fezvez answer can take care of this: have you checked the heuristic value of all your nodes with the A * algorithm and noticed something strange? Are they not equal? Because, although your heuristic is correct for the best first algorithm, it is not suitable for your A * algorithm. I made the project look like in java and I had this problem, so I ask here. For example, suppose you have these points of interest:

• Start (P) - (0,0)
• End (+) - (20.20)
• P1 - (2,2) → (your heuristic) + (path cost) = ((20-2) + (20-2)) + ((2-0) + (2-0)) = 40
• P2 - (4,3) → (your heuristic) + (path cost) = ((20-4) + (20-3)) + ((4-0) + (3-0)) = 40

Now, knowing that the A * algorithm is like a width algorithm with a heuristic , since your heuristic always gives you the same thing (F = h + g), it becomes actually a width algorithm, which also gives the best possible solution, but in practice it always slower than usual A *. Now, as Fesvez suggested, weighting your heuristic can simply mix the best of both worlds (first the first and second) and will look like the one above:

• Start (P) - (0,0)
• End (+) - (20.20)
• P1 - (2,2) → 2 * (your heuristic) + (path cost) = 2 * ((20-2) + (20-2)) + ((2-0) + (2-0)) = 76
• P2 - (4,3) → 2 * (your heuristic) + (path cost) = 2 * ((20-4) + (20-3)) + ((4-0) + (3-0)) = 73

Answer 4

I know this is an old post, but I recently worked on a similar problem, and I feel that the answers here are not good enough, maybe this can help others with similar doubts.

The reason your best first search works better than A * is probably due to your starting position, you start the node located on the opposite side of the node target. A * is expected to expand the nodes in relation to the position of the target (but this will greatly depend on the quality of your heuristic).

If you have much more search space or a starting position closer to the middle, you will probably notice that BFS will expand nodes in all directions until it reaches the goal, because it does not know which direction is preferred (t .e. in which direction is the goal). This is why A * is called informed search because it knows which nodes expand first (those that are directed toward the target).

Finally, if you have a cube that starts with 1 on top and should reach the goal with the same orientation (1 on top). Then the +1 heuristic is not good enough, because it will not fix the nature of the movements necessary to achieve the goal, it too underestimates the cost of the path. Ideally, you want the heuristic to be as accurate as possible to real value, but never overestimate the real value (i.e., the allowable heuristic).

It turns out that in order for the dice to play in the next slot with the same orientation (1 on top), it takes 3 steps, so you can do something like Manhattan Distance + 2 when Manhattan Distance> 1, and this will be do much better than BFS, as it will prefer nodes in the direction of the target. We called this heuristic U-Jump, and below is some comparison.

U-Jump Distance

Here is an illustration of this:

Number of nodes created

Number of nodes visited