Sign in to follow this  
STRIKE82

Rush Hour Puzzle

Recommended Posts

STRIKE82    100
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

Share this post


Link to post
Share on other sites
alvaro    21246
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.

Share this post


Link to post
Share on other sites
STRIKE82    100
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?

Share this post


Link to post
Share on other sites
STRIKE82    100
@ 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

Share this post


Link to post
Share on other sites
alvaro    21246
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.

Share this post


Link to post
Share on other sites
alvaro    21246
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.

Share this post


Link to post
Share on other sites
STRIKE82    100
@ 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?

Share this post


Link to post
Share on other sites
alvaro    21246
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?

Share this post


Link to post
Share on other sites
STRIKE82    100
@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?

Share this post


Link to post
Share on other sites
STRIKE82    100
@InnocuosFox

Yes but is very low...

Your question is tricky :)

If i say yes to you then also 2 and 3 in this example never overestimate the distance to the goal considering the other cars.

O no?



Share this post


Link to post
Share on other sites
alvaro    21246
Quote:
Original post by STRIKE82
@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.


You have to learn to be precise. "The cars blocking the path represent the minimum number of moves to clear the path" is not true. You probably have the right intuition for it, but that doesn't cut it.

Quote:
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.

Then why are you tempted to say "yes"?

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

No, it doesn't mean anything of that type, and you seem to be forgetting what the question is. The only question you have to answer is this: Is the statement "The distance to the solution is always at least 1" true or false? That's all that matters.

Share this post


Link to post
Share on other sites
STRIKE82    100
@Alvaro

OK

So to be precise then we can say that only H1 is true because in the easiest of the possibilities, or when the path is clear then it never overestimates the distance to the goal.

H2 i was tempted to say yes in relation to this example, because the number of the other cars is the same as the number of moves required to exit, but i think is not precise to say this. So H2 is false.

H3 again is false because there could be other cars blocking the cars that directly block the path of the red car.

As you said i have guessed and that is not precise and can not be accepted.
But i can only guess if i don't have the tools to evaluate each heuristic.

I mean i don't know how to precisely evaluate each of the given heuristic.

Am i right this time about H1, H2, and H3?

What you think?

Share this post


Link to post
Share on other sites
alvaro    21246
I don't know if you are getting any closer. If you say a heuristic is admissible, you need to provide proof that it never overshoots. If you say it isn't admissible, you can for instance show a situation where the heuristic overestimates the number of moves.

Share this post


Link to post
Share on other sites
STRIKE82    100
H1 then can never overshoot because the solution can never be less than 1. It must be at least 1.

H2 can overshoot because there could be as in this case 5 cars beside the red car in other locations that would require the solution to be less than 5.

H3 can overshoot everytime there is more than one car directly blocking the way.

Is this ok as proof?

What you say?

Share this post


Link to post
Share on other sites
alvaro    21246
Quote:
Original post by STRIKE82
H1 then can never overshoot because the solution can never be less than 1. It must be at least 1.

Yup, it's as easy as that. [EDIT: Actually, your wording is not quite right. You can say that the *distance to the goal* can never be less than 1, or that the solution can never be shorter than 1 move. The solution is not a number.]

Quote:
H2 can overshoot because there could be as in this case 5 cars beside the red car in other locations that would require the solution to be less than 5.

That didn't make sense. If you think it can overshoot, just describe one example where it does overshoot. A diagram would do.

Quote:
H3 can overshoot everytime there is more than one car directly blocking the way.

That doesn't sound right. I don't think you have thought this one through.

[Edited by - alvaro on November 12, 2009 1:27:10 PM]

Share this post


Link to post
Share on other sites
IADaveMark    3731
I think throughout this whole thread you are getting two ideas confused. Remember, you are not trying to solve the path. You are not even trying to come up with an estimation formula based on other inputs for how many moves it might take. What you are supposed to be doing is, essentially, calibrating your measuring device in such a way that every possible path that you evaluate can be compared to it in a reasonable fashion. To continue the metaphor, you don't calibrate your scale with something sitting on it.

In normal A*, the typical heuristic is a straight line. Never mind the complications - if they even exist. That's what A* is supposed to handle. In this case, the 2nd and 3rd options address ONLY the complications - not the simplest, most vanilla case. The 1st option is, essentially, the scale with nothing on it. No complications; no weights.

A variation on option 1 would be the minimum distance that the car would have to travel if there were no other obstacles. In fact, that would be the idea heuristic. However, that would have been too easy and they wanted to make you think.

Share this post


Link to post
Share on other sites
sebbit    224
Quote:
Original post by InnocuousFox
I think throughout this whole thread you are getting two ideas confused. Remember, you are not trying to solve the path. You are not even trying to


Uhm, are you sure about that? Maybee I got that wrong, too. But isn't the question actually to find the best set of moves (of all cars) that solves the puzzle?

In that case wouldn't the vanilla heuristic have to at least take the number cars into account, that have to be moved (at least once)?

Share this post


Link to post
Share on other sites
IADaveMark    3731
Mostly just that they are mixing terms. We seem to be flowing between distance, moves of obstacles, number of cars, etc. It kinda obfuscates what a heuristic is in a way. Sure, the solution to this puzzle is not in terms of distance (entirely) but rather in terms of atomic actions... that is the movement of A car - not just our own. But returning the number of cars in the puzzle? That's silly talk.

Share this post


Link to post
Share on other sites
alvaro    21246
Oh, I see. In the context of finding solutions to puzzles (in which I have done a fair bit of work), the language feels completely normal. You think of a graph where configurations are nodes, moves are edges, and then the distance between two configurations is the number of moves it takes to get from one to the other.

If you are thinking about A* in the context of an agent in a game trying to go somewhere, I can see how this usage of the terms might be confusing.

Share this post


Link to post
Share on other sites
STRIKE82    100
Thank you for your support

I have submitted the test and answered in the following way:

a. Heuristic 1 can not be considered to be admissible because it returns always 1 in any state. For example if we are in a goal state we know that an admissible heuristic requires to have the value 0, or greater than 0 otherwise.

b. Similarly Heuristic 2 can not be considered to be admissible because as it constantly returns the number of cars beside the black car, is in contradiction with the statement of admissible heuristic. As we are reaching the goal, state by state we know that the admissible heuristic value should decrease towards the value 0 or the goal. So again in a goal state this heuristic would return 5 and not 0.

c. Heuristic 3 is the only one to be admissible because as it returns the number of cars directly blocking the black car at any given state, implicitly means that to reach the goal or the exit, the number of cars directly blocking the black car needs to decrease or go toward the value of 0. This Heuristic will never overestimate the cost of reaching the goal, so it is in harmony with Heuristic Admissible Statement.


Keep in touch for the next post

Best regards

STRIKE82

Share this post


Link to post
Share on other sites
alvaro    21246
Your explanations are a bit hand-wavy, but I think you mostly understand the situation and what was asked of you.

I think the first heuristic is admissible because the heuristic is only evaluated at nodes that are not solutions.

The second heuristic is not admissible if there is a solution and there are at least two other cars, because the situation just before the solution will be at a distance of 1 to the goal, but the heuristic would have a value of at least 2.

The third heuristic is admissible because any solution must include moves to clear the way, and each car in the way requires at least one move.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this