We have a robot trapped in a maze of size $M \times N$ but we don't know what is its position initially. We want the robot to exit the maze but each time we move it we cannot be sure if it did move effectively into the direction we told it to move or if it hit a wall and remained in the same place it was.
¿What's the size of the space of states for this search problem?
I know the answer is $2^{MN}$ but I don't see how this is shown. The exit we are looking for is just a position of the maze.