algorithmartificial-intelligencea-starheuristics

Intuition behind heuristic functions plus example


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.

Problem Description

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:

  1. Why is this heuristic actually consistent?
  2. Why is my reasoning flawed?
  3. What is actual solid intuition for consistency? What does it "actually" mean to be consistent? Admissibility is easy to have intuition for - it means that we never wrongly think we're farther from the goal than we actually are. For example, if I'm trying to walk from Houston to Dallas, at no point do I wrongly think Dallas is farther away than it actually is, although I'm allowed to think that its closer than it actually is. What is consistency in intuitive terms like that? I know the triangle inequality, but if someone said to me "explain this to me like I'm five years old (so not capable of mathematical abstractions) and trying to walk from Houston to Dallas", I'd be unable to for consistency, but perfectly able to for admissibility. That bothers me. I'd like the "for the five year old who can't do math" answer, not the "for the confused computer science student" answer.

Solution

  • 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.