Rush Hour Puzzle
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.
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.
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.
Author
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
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
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
