Dr. Susan Imberman Sample Midterm CSC 480

Name________________________

For all questions write the answers inside the blue books. Any answers written on the question papers will not be accepted.

1. Hamlet the hamster has a deluxe, two room cage. There is an opening between the two sections of the cage.

State 1 State 2

State 3 State 4

State 5 State 6

· Hamlet can move right, move left, and eat.

· When Hamlet eats, he doesn’t stop until all the food is gone.

· If movement can bring him to the next room, it does so.

· Food can only be in one section of the cage

· Hamlet's goal is to find and eat all the food. Therefore the goal states are States 5 and 6.

a) (10 points)Assume Hamlet's world is accessible. This means he knows his current state, if he is in a goal state, and what each action does. If Hamlet is in State 3, find the shortest path to a goal state. Hamlet can check for repeated states, therefore any state that is repeated is not expanded further.

a) (2 points) What search method guarantees that Hamlet will find an optimal solution?

b) (10 points) Assume the world is no longer accessible since Hamlet has gotten old and lost all of his perceptual abilities (he can't hear, see, or smell!). We now have a multistate problem. If we are given a set of initial states (State 1, State 2, State3, State 4) find a path Hamlet can take that will always guarantee he reaches his goal (State 5 or State 6 or both). Hamlet can check for repeated states, therefore any state that is repeated is not expanded further.

For example:

For each of the following multiple-choice questions select that answer that BEST completes the statement. (20 points)

2. A light switch is an agent that can transmit current at will. It transmits current when it believes that is what we want. By flicking the switch we communicate to the agent our desire to have the current on or off. This description of an intelligent agent is consistent with a) intentional stance b) possible worlds theory c) omniscience d) Professor Imberman’s insanity e) veracity

3. A maze-navigating agent is “happy” when it has reached the end of the maze. This type of agent can best be described as a) utility based b) simple reflex c) intentional d) goal based e) nondeterministic

4. A sequence of actions causing you to move from one state to another is called a(n) a) problem formulation b) contingency problem c) path d) depth first search e) cost limited search.

5. The goal of a Turing test is to a) identify "thing A" as a computer or a human b)classify "Computer A" as being a computer as many times as "Human B" is classified as being a computer c) identify males and females d)see if Professor Imberman is intelligent e) identify a computer with 100% accuracy

6. George Boole’s contribution to the field of Artificial Intelligence was a) deriving a set of syllogisms b) building the Ars Magnus c) developing the foundations of propositional logic d) defining rational agents e) developing a universal algebra

7. A search algorithm that is complete a) searches the entire search space b) finds an optimal solution c) finds a solution d) has low search cost e) has no initial state

8. The person who gave the field of Artificial Intelligence its name was a) John McCarthy b) Aristotle c) Kurt Goedel d) Stephen Kleene e) Professor Imberman

9. When the cost function in a cost limited search equals the depth of the search, cost limited search becomes equivalent to a)breadth first search b) A^* search c) iterative deepening d)greedy search e) heuristic search

10. Which of the following is not true of a simple lookup table agent? a) the number of percept sequences may be large b)tables can always be built within a small time period c)these agents are not autonomous d) they are effective for domains with a small number of percept sequences e) they can be implemented in simple reflex agents

11. As we know, this semester Jack Bauer faces his fifth bad day. It is up to you to help him through his current crisis. A canister of Syntox ^Ò nerve gas has been released inside CTU headquarters killing 40% of CTU personnel. Jack holds his breath and crawls through the air ducts in order to grab the canister and disarm it. Chloe (computer geek extraordinaire) can't determine from the floor schematics if Jack will end up in the room with the canister, the hallway, or the gas mask storage closet. Therefore Jack can find himself in any of the following initial states, State 1, State 2, or State3.

	State 1			State 2
	State 3

· Jack can move right, move left, and grab.

· If movement can bring him to the next room, it does so

· When Jack grabs, he either puts on a gas mask or deactivates the canister. (State 7 shows Jack in goal wearing his gas mask!!)

· Jack's goal is to find and grab the canister, thus deactivating it. Therefore his goal states are State 7 and State 8.

· He can also find himself in intermediate states, State 4, State 5 and State 6.

	State 4			State 5
	State 6

State 7 State 8

c) (4 points) Jack's world is accessible. Jack knows his current state, if he is in a goal state, and what each action does. Create a lookup table that lists Jack's perception as his current state and gives the action sequence that will lead Jack to a goal state, or if he is already in a goal state, the table indicates this.

d) (10 points) Terrorists have shut all the lights. Jack's world is no longer accessible. We now have a multistate problem. If we are given a set of initial states (State 1, State 2, State3), using depth first search find a path Jack can take that will always guarantee he reaches his goal (State 7 or State 8 or both). Jack can check for repeated states, therefore any state that is repeated is not expanded further. Solve this problem by expanding the tree below. Apply the operators in the order given.

e) (2 points) Is Jack guaranteed that the solution you found in part b was optimal? Why or why not?

12. a) (6 points) A softbot intelligent agent is designed to search the internet for the best priced digital camera. In class we discussed five different ways to describe an intelligent agent’s environment. Discuss the softbot’s environment using only three of these.

b) (8 points) Dr. Frankenimbermanstein has created an intelligent agent. The agent's job is to write computer programs, hence it is a computer programmer agent. Write a PEAS description for the computer programmer agent.

13. The following is a map of The Interesting College of the University of California (ICUC). The numbers represent the distances that students walk to get from building to building.

a) (10 points) Joe Thestudent wishes to walk from building A to building G. Since Joe is a freshman, he has no idea how to get there. He decides to use a uniform cost search taught to him by his brilliant, modest, computer science professor. Show how uniform cost search finds a solution for Joe. ( In order to get full credit SHOW ALL WORK!!)

b) (10 points) You are given that the straight line distance between each building and goal G is as follows:

Straight Line Distance

A to G = 8

B to G = 3

C to G = 2

D to G = 3

Show how greedy search finds a solution for Joe. ( In order to get full credit SHOW ALL WORK!!)

c) (3 points) Does greedy search guarantee an optimal solution? Why?

d) (4 point) How does greedy search differ from A^* search?

14. (10 points) In the 4 queens problem, the idea is to place 4 queens on a 4 X 4 chessboard so that no queen attacks another queen.

For the 4 queens problem, compare breadth first search to depth first for each of the following criteria:

• Memory usage (3 points)
• Execution Time (2 points)
• Optimal solution? (3 points)
• Complete? (2 points)

15. (9 points) Given the following search space:

a) Which goal state would be found using depth first search from left to right?

b) Which goal state would be found using iterative deepening?

c) Which goal state would be found using breadth first search?

d) Which states are on the fringe?