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
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
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?