I'm taking an AI class and working through some offered practice midterms in order to both understand the material better and help prepare for the initial exam. I feel like I understand search pretty well, and I understand admissibility well, but not consistency, which I understand is a trouble spot for many people. I've looked at a lot of answers on here and frankly, they haven't helped that much in really nailing down the intuitive piece of it. So my larger question is to ask for an explanation on consistency itself, but I also have a small example from one of these midterms I don't understand to help anchor the explanation.
Now for this problem, in the third maze, the practice midterm tells me that the minimum of the distances of Pacman to each box, minus 1, is consistent. I can't really figure out why this is. (Attached the image of the direct question below for clarity).
The question, choice 4 is the puzzling choice
Here's my thought process on this. Consistency means that as we search through the tree, we never overestimate the cost of going to any particular node, as well as not overestimating the cost of going to the solution itself from any node. My take is that if we take the minimum of the distance from Pacman to the boxes, then when we push one box onto the button, Pacman has to move in a direction away from the box that is now on the button, towards one of the other boxes. Since Pacman is closest to the box that is now on the button, the heuristic function will tell us that the cost is increasing as we move away initially, even though this is not actually the case. So the heuristic does in fact overestimate the cost to a node in some cases, right? Either I don't understand consistency or I don't understand this example, or of course possibly both. So my questions are:
A consistent heuristic means that you cannot find a lower estimate of the total cost by walking to neighboring nodes. Specifically, if you can get from a->b at cost c, then you need h(a) <= h(b)+c. This transitively guarantees that no path from a, including a cyclic path, could provide a lower total cost estimate.
To evaluate heuristics given in the problem, consider that the cost to get from any node a to any of its neighbors b is 1. Therefore, the heuristic is consistent if we always have h(a) <= h(b)+1, given that h(goal)=0.
Since pac man can only move one space, and can only move 1 box 1 space, all of the options given metrics can change by at most 1, and would be consistent, except for the cases that are adjacent to the goal state. Both of the max options can suddenly jump from a high value to 0 when the goal is reached in maze 3. Both of the min options are consistent.