Assignment 3 Clarification

Russell and Norvig did not define the maze problem for Exercise 4.2d. Following is a definition of the problem so that you can design heuristics for it.

Maze problem:

In a maze problem, we want a "mouse" to move from a start state to a goal state in the fewest number of steps possible. We will abstract the maze into an n by m grid.

States: A state description specifies the placement of barriers as well as the current location of the "mouse". The "mouse" can see any barriers that are adjacent to its current square.

Operators: The "mouse" can move N, S, W, or E. If a barrier is encountered when executing an operator, the mouse will stay in its current square. (This shouldn't happen though, since the "mouse" can sense walls local to its current square.)

Goal test: Is the mouse in the final square?

Path cost: Each step through the maze costs 1. (In other words, the path cost will be equal to the number of operators executed to get from the start of the maze to the end of the maze.)