Hello all I am new to the forum and also to AI. I am a student and i have been giving an assignment to solve about the rush hour puzzle. The grif is a 6 X 6. This is the url to see the whole picture : http://www.cs.princeton.edu/courses/archive/fall07/cos402/assignments/rushhour/example.gif The question is as follow: In Rush Hour puzzles (see Figure 1 for an example), the black car is trying to escape traffc by moving out of the exit. Cars can be moved up and down or left and right (depending on which direction they are facing). The goal is to clear a path for the black car and move the black car out through the exit. This should be done in the fewest possible moves. Assuming you want to solve this puzzle with the help of an A* search algorithm, which of the following heuristics are admissible? Briefly explain your answer. Heuristic 1: always return 1. Heuristic 2: return the number of other cars (besides the red car). In the example above, this would be 5. Heuristic 3: return the number of cars directly blocking the path of the black car to the exit. In the example above, this would be 2. How would you tackle this question? I know that f(n) = g(n) + h(n), where g(n) is the cost so far to reach n, and h(n) is the estimated cost from goal to n. h(n) needs to be admissible or lower than or equal to the cost of moving from n to the goal. I have seen few admissible heuristics as staright line distance, Manhattan distance, misplaced tiles. My problem is that i don't know where to start from to tackle the problem, or which heuristics should i take and evaluate against the given question. I would appriciate if you could help me to understand the problem. Thank you STRIKE82

A heuristic is admissible if and only if it never overestimates the distance to the goal. With that definition (which I don't think was completely clear to you), you should be able to answer the question.

I know that h(n) is admissible if it never overestimates the distance to the goal.

But given the question i have to take three good candidates heuristic functions to tackle the problem, evaluate them and explain whether they are admissible.

Which heuristics should i take in consideration for the rush hour puzzles?

@ Alvaro

just spoke with my tutor.

The heuristics to evaluate are those stated in the question, and there is no need to search for other heuristics.

Regards

Quote: Original post by STRIKE82
I know that h(n) is admissible if it never overestimates the distance to the goal.

But given the question i have to take three good candidates heuristic functions to tackle the problem, evaluate them and explain whether they are admissible.

Which heuristics should i take in consideration for the rush hour puzzles?

I thought you were asking about those 3 specific heuristics you listed on your first post, for which it's pretty easy to determine whether they are admissible or not.

For coming up with your own heuristics, think of some quantity whose admissibility would be easy to prove. For instance, distance between the black car and the exit plus the number of vehicles blocking the way. You could even count a blocking car twice if it is itself blocked.

Quote: Original post by STRIKE82
@ Alvaro

just spoke with my tutor.

The heuristics to evaluate are those stated in the question, and there is no need to search for other heuristics.

Regards

Oh, OK. That should be easy. With a bit of practice you'll be able to come up with your own heuristics with no problem.

@ Alvaro

Could you please help me in giving me some examples on how to start to practice and evaluate those functions?

The deadline is by tomorrow buti have 5 extra days to go, cause my tutor said so.

I don't want you to give me the solution.

I prefer to understand what i have to do my self to answer correctly.

From the given example i figured out that the cheapest solution costs 5, or 4 moves for other cars to make the path clear and 1 move for the red car to exist.

Given this is correct how do i evaluate those three heuristics?

So if f(n) = g(n) + h(n) do i have to substitute the values?

Ignore `f(n) = g(n) + h(n)' for now. A heuristic is just a function that gives you an idea of how close to the goal you are. Intuitively, the closer the black car is to the exit, the closer the solution might be; and the more obstacles there are in the way, the farther away we are from the solution.

Anyway, for your specific assignment, consider the statements:
(1) "The distance to the solution is always at least 1".
(2) "The distance to the solution is always at least the number of other cars".
(3) "The distance to the solution is always at least the number of cars directly blocking the path of the black car to the exit".

Which of those statements seem true to you?

@Alvaro

Thanks. Your statement makes things very clear.

So considering the situation i would say that Heuristic 3 is admissible, because the cars blocking the path represent the minimum number of moves to clear the path, abstracting other cars or without considering them.

I am tempted to say yes to heuristic 2 in this example, but i think is not admissible because there could be cars in other examples that don't necessarily block the way to the red car.

For the first heuristic I would say no, because if it always return 1 then it means that the path is always clear.

How was that?

What you think?

Number 1 doesn't over-estimate the distance to the goal, right? ;-)