1. List and define at list four properties of environments and how they impact problem-solving agents. {}
The book gives many properties of environments so any four of these and some general comment about the affect of the environment property on problem-solving. Below are some examples
Fully observable vs. partially observable – an environment is fully observable if an agent’s senses give it access to the complete state of the environment. Fully observable environments simplify problem solving by reducing the amount of unknown information. The agent is also not required to keep an internal model of the world.
Deterministic vs. stochastic – a deterministic environment allows the next state to be COMPLETELY determined by the current state of the environment and the actions of the agent. This simplifies problem-solving because nothing unexpected can happen while the agent is otherwise occupied. The agent does not need to deal with additional events.
Episodic vs. sequential – an environment is episodic if the agents experience is divided into periods of perceiving then acting and that the action only depends on the single episode not previous episodes. In this environment the agent does not need to think ahead.
Static vs. dynamic – an environment that can change while the agent is deliberating is called a dynamic environment. Static environments are easier because the agent does not have to worry that something may occur while it is processing.
Discrete vs. continuous – environments with a limited number of percepts and actions is discrete. This is easier to deal with than continuous information.
Single agent vs. multi-agent
A)
B)
C)
D)
2. Suggest heuristics that might be used to improve how choices are made to solve the following problem. {}
Given a database of flight information for all flights worldwide as follows:
Destination city Arrival Time Arr Date
Departure city Dep. Time Dep. Date
Airline Flight # Class Fare cost
for a desired destination city and not-later-than XX:XX arrival time and date from a given departure city and not-earlier-than YY:YY departure time and date:
A) Give at least two heuristics that would help find the lowest fare regardless of length of the trip
There is no single set of RIGHT answers here. See if the heurisitic makes sense to you or let me grade this question. =)
B) Give at least two heuristics that would help find the fastest trip regardless of cost of the fare.
Ditto
3. Give the book’s definition of an ideal rational agent. You can paraphrase and use your own words but capture the salient points from the book’s definition. {}
The book’s definition is: For each possible percept sequence, an ideal rational agent should do whatever action is expected to maximize its performance measure, on the basis of the evidence provided by the percept sequence and whatever built-in knowledge the agent has.
4. Match the terms below to the definitions for the problem types that follow: {}
A. Single-state B. Multiple-state C. Contingency D. Exploration
C The agent must use sensing during the execution phase
D The agent learns a map of its environment
B The agent must reason about the set of states it can get to
A The agent has exact information about the world
5. IndicateTrue (T) or False (F) for each of the following statements relating to resolution:
T Resolution is a generalization of Modus Ponens
F Resolution can be performed on sentences in either implicative normal form or
disjunctive normal form.
F The demodulation rule is for sentences containing an inequality
T Resolution with refutation is a complete inferencing procedure
T Skolemization is the process of removing existential quantifiers by elimination
T Reductio ad absurdum means that in order to prove P, we assert ¬P into the knowledge base and prove a contradiction
6. Represent the following problem knowledge as a set of first-order logic predicates and rules. Represent ONLY the facts and rules that would help answer the question at the end of the problem description. Indicate where your facts come from as either Problem (P) facts or Real-World knowledge (RW) facts. {}
Once upon a time there was a little red-headed girl named Sumitra. Sumitra had a puppy named Jake and a cat named Elwood and she loved both of them very much. When Sumitra comes home from school one day, she discovers that her new chartreuse knitted sweater has been torn up. Only Jake or Elwood could have done it. Sumitra knows that puppies like to tug on clothing and gnaw on things and that cats like to sharpen their claws and play with yarn. As Sumitra looks at her sweater she sees that in places the knitted yarn has been snagged and cut and then unraveled. Can she use logic to solve this puzzle and figure out whether Jake or Elwood tore up her sweater?
At a minimum they should have facts that indicate that
Jake is a puppy
Elwood is a cat
puppy implies tugclothing
puppy implies gnawing
cat implies sharpenclaws
cat implies yarnplay
sweater implies yarn
sharpenclaws implies sliced or cut or dug or snagged
yarnplay implies unraveled
yarnplay implies yarn
tugclothing implies pull
gnawing implies chewed
gnawing implies wet
sweater is dug or snagged or sliced or cut
sweater is unraveled
7. Given the map below, use the uniform cost search algorithm to search for the best path from Artemis to Zeus. Show the expansion trees generated at each step and the values for each leaf in the expansion trees.
 |
|
|
Straight line distance to Zeus |
|
|
|
Artemis |
210 |
|
|
Bacchus |
175 |
|
|
Cronus |
150 |
|
|
Demeter |
105 |
|
|
Eros |
185 |
|
|
Gaia |
80 |
|
|
Hesphestus |
70 |
|
|
Jove |
70 |
|
|
Mercury |
110 |
|
|
Neptune |
100 |
|
|
Persephone |
140 |
|
|
Saturn |
50 |
|
|
Uranus |
65 |
|
|
Venus |
60 |
|
|
Zeus |
0 |
8. For the tree below representing a min-max game use the minmax algorithm with alpha-beta (ab) pruning to determine the optimal moves to get the highest possible score if MAX and MIN make perfect moves. Show your work by labeling the nodes with the values of the selected moves. Use the notation <=X to indicate where branches were pruned after the X value was seen. Also cross out any pruned branches. When done, circle the set of moves that MAX and MIN make in this game.
Max
9. Write the necessary predicates and rules to solve the problem below and then APPLY the rules of first order logic and resolution to show the final solution. NOTE: You may reuse your solution from Question 6 (without rewriting anything) but make sure that you account for the slight variation in the problem below compared to Question 6. Retract any facts from your Q6 solution that are no longer true and assert additional facts to show the new world state. Mark the bold sentence below appropriately if you want to reuse your other solution.
Once upon a time there was a little red-headed girl named Sumitra. Sumitra had a puppy named Jake and a cat named Elwood and she loved both of them very much. When Sumitra comes home from school one day, she discovers that her new chartreuse knitted sweater has been torn up. Only Jake or Elwood could have done it. Sumitra knows that puppies like to tug on clothing and gnaw on things and that cats like to sharpen their claws and play with yarn. As Sumitra looks at her sweater she sees that in places the knitted yarn has been chewed and that those places are damp. Can she use logic to solve this puzzle and figure out whether Jake or Elwood tore up her sweater?
I am reusing the facts and rules from Question 6 without rewriting them. (Y/N)
(Below are any needed changes and additional rules and facts prior to the proof.) {}
sweater is wet new fact
sweater is chewed new fact
sweater is NOT dug or snagged or sliced or cut changed fact
sweater is NOT unraveled changed fact
Proof: (I will not count off if you just drop the quantifiers appropriately without stating it.)
(Should follow first order logic rules)
10. Given the map below, use the A* algorithm to search for the best path from Artemis to Zeus. Show the expansion trees generated by A* at each step and the values for each leaf in the expansion trees.
 |
|
|
Straight line distance to Zeus |
|
|
|
Artemis |
210 |
|
|
Bacchus |
175 |
|
|
Cronus |
150 |
|
|
Demeter |
105 |
|
|
Eros |
185 |
|
|
Gaia |
80 |
|
|
Hesphestus |
70 |
|
|
Jove |
70 |
|
|
Mercury |
110 |
|
|
Neptune |
100 |
|
|
Persephone |
140 |
|
|
Saturn |
50 |
|
|
Uranus |
65 |
|
|
Venus |
60 |
|
|
Zeus |
0 |
Extra Credit questions
XC1. List and give a one sentence description of at least three fields of study and how they have contributed to the creation and development of the field of AI. {5}
Philosophy
Mathematics
Psychology
Computer engineering
Linguistics
XC2. Describe the four categories of approaches to developing “intelligent” systems. {5}
Any of the four can be in any box
|
|
|
|
|
|
|
Systems that think like humans |
Systems that think rationally |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Systems that act like humans |
Systems that act rationally |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|