Optimality of A* algorithm

Question

In the book Artificial Intelligence a Modern Approach 4th edition, the author claims that the A* algorithm is cost-optimal if the heuristic function is admissible (never overestimates the remaining true cost).

Additionally, if the heuristic is consistent (obeying the triangle inequality by using a neighboring node), the first time we reach the goal state, will be the optimal solution. Consistency can be best described by a triangle inequiality: h(n) < c(n, a, n') + h(n'), the heuristic of going from n to the goal h(n) is less than the sum of the actual cost of going from n to n' c(n, a, n'), and the heuristic of going from n' to the goal h(n'), where "a" denotes some action that takes the agent from n to n'.

My problem statement is to find the shortest path in terms of Euclidian distances on a 2-D grid with obstacles where the agent can move to any of the 8 available adjacent cells.

My algorithm is rather straightforward:

Create an object `Point` to denote a path
- It contains information such as:        
    1. current location
    2. list of past moves
    3. sum of total distance travelled (g)
    4. estimated future distance (h), which is the Euclidian distance between current location and the goal.
    5. f = g + h, the function to minimize, which is also what the priority queue compares Points on

Create a priority queue and put Point into it - the queue holds the best Point we have so far in terms g + h

Create a set of tuple of (row, column) pairs to mark grids as visited

In a while loop:

 - Get a Point curr from the priority queue

 - If curr is on the goal, return its path

Otherwise for all curr's successors:
- if the successor's current location hasn't been visited:
  - put the location tuple into the visited set, and put the successor into the priority queue

Here is an example of a path:

Clearly, this is not the optimal solution, as the path is longer than necessary. But why?

My heuristic seems standard, but it is not finding the optimal solution, let alone have the first arrival be optimal.

While debugging, I noticed that the reason it was not finding the optimal path was because the points on the optimal path were visited by "suboptimal" paths (paths that head toward the lower right before finding a way to cross the obstacle first). And this is difficult to avoid since the Euclidian distance will guide the search toward the lower right, right out the gate, which is a suboptimal path.

Euclidian distance obviously does not overestimate the cost, hence it satisfies the definition of admissibility.

Furthermore, I believe the heuristic is also consistent, as going to any neighboring point that is not on the straight line between the current point and the goal, will form a triangle, and will obey the triangle inequality. (Perhaps consistency needs to be satisfied when n' is on the straight line between n and the goal? In that case I believe it fails because h(n) = c(n, a, n') + h(n'))

I modified the algorithm by changing the visited set into a map where the keys are location tuples (r, c), and values are current f values, and I will let a successor that is on a visited cell enter the queue only if it has a lower f value than the previous f value on the cell, and update the f value to be the current lower f value.

The algorithm successfully finds the path for this problem.

However, this algorithm fails for another puzzle where we're moving elements in an array based on some rules. As a result, I don't believe my understanding of A* algorithm is correct.

Could you let me know if my heuristic of Euclidian distance is admissible or consistent, and point out any other flaws that plague my reasoning?

Answer 1

what is your formula for g? From your result it looks like amount of nodes visited.

That cost function will result in more extraneous diagonals. Because going diagonally down left followed by diagonally down right has the exact same cost as going down twice.

in particular at that turnaround assuming the node just before has cumulative cost of $g$ then the square just below has cost $g+1$ the node just down right has cost $g+1.4$, when both have explored their neighbors they both touch the square under the first one. The path going straight down will have cumulative cost $g + 2$ while the path with the bent will have cost $g + 2 * 1.4$. So after updating the path straight down should be the one preserved.

However if instead you scale de diagonal distance by (some approximation of) the square root of 2 compared to the orthogonal path. Then paths that avoid the zigzag diagonal will be more favorable.