Assignment 1

Due Thursday, April 1st in class.

1. For the problem posed below, write the problem components you would use in constructing a search procedure. Explain your reasoning.
2. Describe the search algorithm you would use to solve the problem (you needn't give the pseudocode for the algorithm, but you must describe how the algorithm works). Justify your choice of algorithm.
3. Suppose that one of the physicians-to-be argues that the matching process is flawed, and doesn't believe that the final result is best possible matching and insists that you produce not only the final match, but also all the tentative match attempts. Does this change your answer to part a? Why or why not? Does this change your answer to part b? Why or why not?

Every year, thousands of medical school graduates head off to residency programs to earn their stripes. Graduates are assigned to residencies through a national matching program which works as follows (with a few liberties in the accuracy of the description). Each graduate applies to various residency programs at hospitals throughout the country. The programs (generally in large teaching hospitals) invite the most promising candidates to come for a visit and interview. After all the interviews have concluded the residency programs and the graduating students rank each other. For example, Janet Tibia might rank her choices (in a Rank Order List, as it's called) as follows:

1. Brigham and Women's Hospital
2. University of California, Los Angeles
3. University of California, San Francisco

Meanwhile, the residency programs rank their choices as well, also in a Rank Order List. For example, the soon-to-be Dr. Tibia might be ranked 39th at Brigham and Women's, 4th at University of Virginia and 6th at University of California, San Francisco. The national matching program then considers all the graduates and all the programs and assigns residents-to-be to programs.

The process starts off with an attempt to place an applicant into the program indicated as most preferred on that applicant's list. If the applicant cannot be matched to this first choice program, an attempt is then made to place the applicant into the second choice program, and so on, until the applicant obtains a tentative match, or all the applicant's choices have been exhausted.

An applicant can be tentatively matched to a program in this process if the program also ranks the applicant on its Rank Order List, and either:

• The program has an unfilled position, or
• The program does not have an unfilled position, but the applicant is more attractive to the program than another applicant who is already tentatively matched to the program. In this case, the applicant who is the least preferred current match in the program is removed from the program, to make room for a tentative match with the more preferred applicant.

When an applicant is removed from a previously made tentative match, an attempt is made to re-match this applicant, starting from the top of his/her list. This process is carried out for all applicants, until each applicant has either been tentatively matched to the most preferred choice possible, or all choices submitted by the applicant have been exhausted. When all applicants have been considered, the match is complete and all tentative matches become final.

In 1998, the match enrolled 3,814 programs, which altogether offered 22,451 positions. A total of 35,823 applicants participated in the match.

Suppose we have a 5x5 Wumpus world with the usual rules, as shown below in Figures 1 and 2 (on the next page).

1. Represent both worlds in a set of sentences in propositional logic, as what the agent can perceive and describe the inference procedure you would use. Be sure that your representation is consistent with your inference procedure.
2. Use your inferencing procedure and representation to derive the next move by a very conservative agent.
3. Could the agent in the example be a reflex agent? Why or why not?

a) Write a representation for the following story. Your representation should include the background knowledge, as well as the specifics of the story. For each of the questions below (and answers), show how your inferencing procedure and representation would generate the appropriate answers.

Questions:

1. Is Billy a child or an adult? [Child]
2. Does Billy need to be at day care at 8a.m., or 8p.m.? [8 a.m.]
3. Is AAA a repair service? [Yes]

b) Suppose we now we add the sentence:

Describe the mechanism for representing this new sentence, and apply it.

c) Suppose the next sentence read:

How would your representation change? Would your answers to questions 1-3 change?

Wile E. Coyote is hungry, and would very much like to dine on freshly grilled roadrunner. Wile E. only lives near one roadrunner, The Roadrunner. Roadrunners are too fast for coyotes to catch without help. The Acme Corporation make several roadrunner-catching devices. No Acme product works as intended.

1. Represent the above facts as Horn clauses in first-order logic.
2. Describe Generalized Modus Ponens and demonstrate its application with an inference from the knowledge base you created in part a.
3. Describe forward and backward chaining, and use either one to prove that Wile E. Coyote will never catch The Roadrunner.
4. Describe one disadvantage of forward chaining, and explain why you might use it anyway.

1. Represent each of the above facts in first-order logic.
2. Convert each of the above facts to implicative normal form. Show the conversion from standard FOL to INF for the statement:

Either Ms. Scarlett or someone in the library poisoned Prince Horatio.

3. Use resolution to answer the question: Did Ms. Scarlett kill the prince? Be sure to include the binding lists you use, and name the resolution strategy you choose for your proof.

Suppose we wish to represent the categories of exotic birds in a semantic network. We might have a top-level category for birds, and then distinguish exotic birds from others.

a) Create a graphical, frame-based version of the relationships suggested in the figure below.

b) Suppose that parrots can talk — how would this be represented in your frame–based system?

c) Next, suppose that Toucan Sam (the Froot Loops mascot), who is a toucan, can talk. Furthermore, Toucan Sam is the only toucan who can talk. Represent this in your frame-based knowledge base.

d) How would you conclude that Molly can’t talk? Show the reasoning using the representation from your frame-based knowledge base?