1. A Mars rover has to leave the lander, collect rock samples from three places (in any order) and return to the lander every day. Assume that it has a navigation module that can take it directly to places of interest. So it has primitive actions go-to-lander, go-to-rock-1, go-to-rock-2, and go-to-rock-3.

We know the time it takes to traverse between each pair of special locations. Our goal is to find a sequence of actions that will perform this task in the shortest amount of time. (a) [3 pts] Formulate this problem as a problem-solving problem by specifying the search space, initial state, path-cost function, and goal test. Assume that the world dynamics are deterministic.

(b) [3 pts] Say what search technique would be most appropriate, and why. If your search technique requires a heuristic, give an appropriate one.

(c) [4 pts] Now assume that, in addition, the rover needs to be at a special communications location at 3PM. Any plan that misses a communications rendezvouz is unsatisfactory. So it now has primitive actions go-to-lander, go-to-comm-location, communicate, go-to-rock-1, go-to-rock-2, and go-to-rock-3. communicate can only be executed when the rover is at the communications location at 3 PM and executes a communications sequence that takes an hour. How would you modify the search space, path-cost function, and/or goal-test to handle this additional requirement?

3 4 5 6 7 8 9 10 Figure 5: Avg path cost v.s. N O QU C 3 4 5 6 7 8 9 10 Figure 6: Avg node generated v.s. N