HW1
[15 points] Answer the following questions briefly but precisely, explaining your reasoning:
Why performance measures for an agent should be designed according to the effects in the environment instead of the behaviors of the agent?
Why it is important to know if an agent’s environment is fully observable or if it is partially observable?
Can an agent that keeps no history of its percept sequence be rational?
[20 points] Winter is coming and you need to figure out how to remove snow from your driveway. Assume the driveway is divided into squares, with the squares lined up in one line, and there is a collection place at the end of the driveway where the snow can be collected. The snow can be removed from a square by pushing it to a neighbor square if a person with a shovel is in the square. Your goal is to have all the snow in the collection place. Formulate the problem using a state-space search representation. You start with a person with a shovel in a square. When the person moves the snow to an adjacent square, the person with the shovel also moves to the next square.
Describe precisely:
how you would represent the states (i.e., what information needs to be included in any state to make sure the state describes all the information you need to apply the actions);
what is the initial state (it is up to you to specify what you want for the initial state)
what goal test you would use;
what are the actions;
Is the state-space a tree or a graph? Please justify your answer.
[20 points] This question is on properties of search algorithms. Considering the uninformed search algorithms covered in Chapter 3, answer the following questions. Do not simply write the name of one algorithm, explain what algorithms you could use and, most importantly, why.
if you have limited memory, which search algorithm(s) would you use and why?
if you have an estimate of the length of the solution (i.e., the number of links to traverse to reach the goal node from the initial one), which algorithm(s) would you choose and why?
if you want the minimum cost solution and all the actions have the same cost, which algorithm(s) would you choose and why?
if you want to minimize the length of the solution (i.e., the solution with the smallest number of steps) and do not want to use a lot of memory, which algorithm(s) would you choose and why?
if you have a state space where parts of the state space graph have only a few links that connect one part of the search space to another, what algorithm(s) would you use and why?
[20 points] Suppose you search a graph and do not keep track of the nodes that have been explored.
If the graph is acyclic and you use the uniform cost search algorithm, will the algorithm find the cost-optimal solution or not? Will your algorithm take longer than the standard uniform cost algorithm to find the solution? Does the answer depends on the search space being a-cyclic or not?
If the graph has loops and you use depth-first search, what can you guarantee?