3.2) Your goal is to navigate a robot out of a maze. The robot starts in the cen

Question

3.2) 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?
c. From each point in the maze, we can move in any of the four directions until we reach a turning
point, and this is the only action we need to do. Reformulate the problem using these actions.
Do we need to keep track of the robot’s orientation now?

Explanation / Answer

Function( At(x), 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 2 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) 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? The successor function remains the same for intersections, and for locations x which are straight corridors: Successor Function( At(x), Facing(y) ): Thus if the maze has I intersection blocks then the size of the state space is 4I + 2(S ? I). 3 HW 1 - Solutions cs171 (c) From each point in the maze, we can move in any of the four directions until we reach a turning point, and this is the only action we need to do. Reformulate the problem using these actions. Do we need to keep track of the robot

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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