1. Your goal is to navigate a robot out of a maze. The robot starts in the cente

Question

1. Your goal is to navigate a robot out of a maze. The robot starts in the center of the maze facing north. You can turn the robot to face north, east, south, or west. You can direct the robot to move forward a certain distance, although it will stop before hitting a wall.

a. Formulate this problem. How large is the state space?

b. In navigating a maze, the only place we need to turn is at the intersection of two or more corridors. Reformulate this problem using this observation. How large is the state space now?

2. Discuss how well the standard approach to game playing would apply to games such as tennis, pool, and croquet, which take place in a continuous physical state space.

3. Prove the following assertion: For every game tree, the utility obtained by MAX using minimax decisions against a suboptimal MIN will never be lower than the utility obtained playing against an optimal MIN. Can you come up with a game tree in which MAX can do still better using a suboptimal strategy against a suboptimal MIN?

Explanation / Answer

a) 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(South), {At(x),Facing( (0,-1) )} >

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

                     <Move( k blocks), {At(x + y min(k, Dmax(x, y))), Facing(y)}> where Dmax(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.If the maze is comprized of S blocks, then the total number of states is 4S.

b)

The successor function remains the same for intersections,and for locations x which are straight corridors:

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

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

Thus if the maze has I intersection blocks then the size of the state space is 4I + 2(S I).

2)

Without modification the standard approach wouldn't work well. You would probably need to break time/space into tiles, or include a physic engine of some sort in the operator to get an idea of the results of an action. Continuous space makes search much more challenging.

3)

MIN playing suboptimally means, by definition, that MIN selects a move with minimax utility greater than or equal to the move predicted by minimax. Since MAX maxes over these decisions, then the minimax utility against a suboptimal is greater than or equal to the minimax utility against an optimal min. the optimal move for MAX is to select the move that leads to the leaf with utility 2. But if MAX knows MIN will play suboptimally, MAX can select the other option, which would get him utility 1 against an optimal MIN, but will get him utility 10 against a suboptimal MIN.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.