Question

1. Suppose that you want to program an AI agent to navigate out of a maze. The agent starts at the maze’s center facing the north direction. The agent can turn to face the south, north, east, or west. The agent can be directed to move forward for a certain distance but will stop before hitting a wall.

a) Formulate this as a search problem defining initial state, goal test, transition function, and cost function.

b) What can you tell about the size of the state space?

c) In maze navigation, it is only necessary to turn at the intersection of two or more corri-dors. Using this observation, reformulate the search problem. What can you say about the size of the state space now?

d) What simplifications or abstractions about the real world, actions, or details did we make in our problem formulation? List three of this simplifications and briefly discuss how realistic they are. For example, we assume that the agent can move as far as it can without battery charging.

Answer 1

a) Formulating this as a search problem. The goal is to get out of the maze.

Initial State: At (0,0) , Facing( (0,1) ).

Successor Function( At(x), Facing(y) ):

<Turn(North),{At(x),Facing( (0,1) )}>

<Turn(East),{At(x),Facing( (1,0) )}>

<Turn(West),{At(x),Facing( (-1,0) )}>

<Turn(South),{At(x),Facing( (0,-1) )}>

<Move(k blocks), {At(x+y min(k, D_max(x, y))), Facing(y)} > where D_max(x, y)is the maximum distance the robot can move in direction y from point x without hitting a wall.

Goal State: At(x),x∈G, where G is the set of locations outside the maze.

b) If the maze is comprised of S blocks, then the total number of states is 4S.

c) Given that, the only place we need to turn is at the intersection of two or more corridors. Now, let us re-formulate the problem. The successor remains same for the intersections and for the straight corridors,

Successor Function( At(x), Facing(y) ):

<Move(k blocks),{At(x+y min(k, D_max(x, y))), Facing(y)}>

The size of the state space decreases due to this observation. If there are I intersection blocks, the size of the state space now is 2S + 2I.

d) Three simplifications we made are

• The robot can see where the walls are perfectly.
• The robot can move only in one of four directions.
• The robot knows with certainty how far it has moved after attempting to move a certain distance.