代做600.435 Artificial Intelligence Spring 2017 Final Exam调试数据库编程

Final Exam

600.435 Artificial Intelligence

Spring 2017

Intelligent Agents                                                                                         13 points

1. (8 points) Consider a self-driving caras an intelligent agent. Name two items for each of the PEAS elements.

• Performance measures:

• Environment: 

• Actuators: 

• Sensors:

2. (5 points) Consider a computer program that is playing online poker. Is the environment of this intelligent agent ...

• Fully observable?

• Deterministic?

• Static?

• Discrete?

In which of these categories is a Go playing program different?

Just provide a yes/no answer to each of these questions.

Basic Search                                                                                                 10 points

In the following grid, we want to find the fastest path from A to G.

We may move from every cell to each directly neighboring cell (up, down, left, right). The cell in the center of the grid is unreachable.

A	b	c
d		e
f	G	h

3. (7 points) Draw the full search tree of breadth-first search that explores this grid.

• Note that search may return to already visited cells.

• The search graph must include all leaf nodes at maximum depth.

4. (3 points) If we use depth-first search and move

• up, whenever possible

• right, whenever possible (and up is not possible)

• down, whenever possible (and up and right is not possible)

• left, otherwise

Again, search may return to already visited cells.

Will depth-first succeed? If yes, in how many steps? If no, why not?

Informed Search                                                                                    10 points

Consider the search space below, where S is the start node and G1 and G2 satisfy the goal test. Arcs are labeled with the cost of traversing them and the heuristic cost to a goal is reported inside nodes (so lower scores are better).

5. (10 points) For A* search, indicate which goal state is reached at what cost and list, in order, all the states popped o『 of the OPEN list. You use a search graph to show your work.

Note: When all else is equal, nodes should be removed from OPEN in alphabetical order.

Path to goal (cost):

States popped off of OPEN:

Game Playing                                                  12 points

Apply the mini-max algorithm to the partial game tree below, where it is the minimizer’s turn to play and the game does not involve randomness. The values estimated by the static-board evaluator (SBE) are indicated in the leaf nodes (higher scores are better for the maximizer).

Process this game tree working left-to-right.

6. (5 points) Write the estimated values of the intermediate nodes inside their circles.

7. (2 points) Indicate the proper move of the minimizer by circling one of the root’s outgoing arcs.

8. (5 points) Circle each leaf node (if any) whose SBE score does not need to be consulted. Briefly explain why:

First Order Logic                                                                                          15 points

9. (5 points) Convert the following sentence into first-order predicate calculus logic:

There is a lacrosse player who has played in every game this season.

10. (10 points) Given the following propositional-logic clauses, show E must be true by adding ¬E and using only the resolution inference rule to derive a contradiction.

Use the notation presented in class (and in the book) where the resulting clause is connected by lines to the two clauses resolved.

• A ∨ ¬C

• B ∨ ¬A

• B ∨ ¬D

• E ∨ ¬A ∨ ¬B

• C

• ¬D

Probabilistic Reasoning                                                                               10 points

11. (5 points) Suppose we roll a die 2 times. What is the probability that the sum of the numbers is 3?

12. (5 points) In the general population, 0.1% have the disease X.

Doctors developed a test with the following properties:

• If a person has the disease, the test detects it 90% of the time, and fails to detect it in 10% of the time.

• If a person does not have the disease, the test gives false positive indication 10% of the time, and a correct negative indication 90% of the time.

What is the probability that a random person who receives a positive test result, does indeed have the disease (round numbers when appropriate)?

Bayesian Networks                                                                                       15 points

Consider the following Bayesian Network, where variables A–D are all Boolean valued (when answering the questions be sure to show your work, if a computation gets too convoluted it’s fine just state terms with numbers):

13. (5 points) What is the probability that all four of these Boolean variables are false?

14. (5 points) What is the probability that A is true, C is true and D is false?

15. (5 points) What is the probability that A is true given that C is true and D is false?

Reinforcement Learning                                                                              15 points

Consider the deterministic reinforcement environment drawn below, where the current state of the Q table is indicated on the arcs. Let γ = 1. Immediate rewards are indicated inside nodes. Once the agent reaches the end state the current episode ends.

16. (5 points) Assuming our RL agent exploits its policy (with learning turned o『), what is the path it will take from start to end? Briefly explain your answer.

17. (5 points) Assuming the RL agent is using one-step Q learning and moves from node start to node b. Report below the changes to the graph above (only display what changes).  Assume a learning rate of α = 1. Show your work.

18. (5 points) Show the final state of the Q table after a very large number of training episodes (i.e., show the Q table where the Bellman Equation is satisfied everywhere). No need to show your work nor explain your answer.