ROBOT MAZE

Robot & Maze:

Robot starts in the middle of a maze and can move N,S,E,W. Initially its facing N. IT can move a distance d forward, but will stop when it hits a wall.

a) Formulate the problem. How Large is the statespace?

I assume a grid like below were X = walls and # = tunnel and E = exit.

States: Each state is (i,j,d) where i and j is the position (where applicable) of the current location (i,j e 1..6) and where D = {N,S,E,W}.
Initial State = (3,3,N)
Actions:
a) Turn(d) where d is the new direction
b) Move(d) where d is the number of cells to traverse. D will always be Max(d, and available cells until we reach a wall)

Goal State = (1,5)
Transition Model: THis is the states, initial state (as defined above) and die successor function.
Successor Function can be 1 of two:
Successor(i,j,d) = Result(In(i,j,d), Turn(d)) = In(i2,j2,d2) where i2, j2 and d2 are the new values
OR Successor(i,j,d) = Result(In(i,j,d), Move(d)) = In(i2,j2,d2)
Path Cost: Cost is value of 1 per move/action
I dont think I should draw the state space unless asked.

E
xxxx#x
x####x
xx#xxx

How large is the state space? Well for each state we can move the direction (4 actions possible). Also for each state we can Move (1 action). Assuming we turn and then move which would be a good choice (because after we move we will have stopped somewhere, so we must turn), we will have a move action and then posisble 4 directions for each state. Also we must consider each possible state, that is Move(1), Move(2) etc in all directions.
Thus for each state we have a Move and Turn of 4 directions. Thus 5 actions for each state. I think Size = 4^n + n where n = number of states. (however on second thought the +n could greatly depend on the number of blocks available for each Mode(d) where d could be {1,2,3,4,5,max avail.}


Now we only need to turn at the intersection of 2 or more corridors. Update the above definitions and State space size.
States and Initial state stay the same. Actions are changed to MoveUntilWall in stead of Move(d). We still have Turn(d). There is no way of knowing if we are at an intersection (without trying to move and checking the result). Thus I say, Move until we stop and choose a direction. The size of the statespace will drastically diminish as we dont have each state to account for (but only the number of moves). THus still 4^n + n but here N is the number of MoveUntilWall actions.

C)From each point in maze we can move in any four directions until we hit a turning point. this is the only action we need to take.Reformulate and "How do we keep track of direction / orirentation"?
Now actions are just Move(d) where d is direction. We will move until we hit something (wall). 4^n only? where n is max number of levels in the tree until we reach a goal. Orientation? = The robots orientation will be whatever the last direction was in which we moved. If last action was Move(N), then the orientation will be N. If the move failed (ie. we could not move N) tyhen I assume we orientated N and stayed that way.

d) List three abstractions from the real world: 1) Robot doesn't have to worry about moving its legs, we abstracted the mechanical details, 2) Robot doesn't have to worry about breaking down (abstracted various external factors) 3. Robots doesnt have to worry about the maze changing

Danie van Eeden
------------------------