Task 2

The goal of this task is to investigate the CS 348 Deductive Data Retriever (DDR), make some improvements to it, apply it to a toy problem, and apply it to a practical problem of your own choosing. You'l need to run some comparative experiments, showing how the Retriever works on different problems, with and without your improvements, and submit a report on what you did and the experimental results.

Set Up

See the DDR Setup Instructions for details on installing and testing the Retriever.

Improving the Retriever

The Retriever returns all possible answers. This is bad for two reasons. First, it's inefficient if you want just one answer. Second, and more importantly, it means it can't handle problems with infinite search spaces, even if there are finite answers. Infinite search spaces can arise very easily if functional terms are generated.

Change DDR so that it returns one answer, but can be called again to get the next answer, if any.

More specifically, at the user level, (ask pattern) should retrieve the first answer for pattern, as usual. (ask) however should now search for another answer, starting from where the search left off.

Study the code and think first! This will involve changing how the code works in a number of places. Currently it just appends the results of going down the lists of alternatives that get generated during backward chaining. Those appends have to turn into some kind of queuing of possibilities, which the internal code can then use when one branch fails, or the top level ask can use to say "find another."

Do this as cleanly as possible, i.e., minimize global variables.

For those who want to be "lazy," (pun intended as you'll see), check out generated lists. They're one way to do this without changing too much code. Think carefully about which lists need to be generated and which should not be. Generated lists is only a suggestion -- not a requirement.

Do not change ddr.lisp. Create a patch file with the code you need to extend and redefine ddr.lisp.

Toy Problem

Do the Monkey and Bananas problem using your new Retriever. Monkey and Bananas is a classic problem from early AI.

A bunch of bananas are hanging from the ceiling in the center of the room. There's a box by the window, and a monkey by the door. To get the bananas, the monkey must move the box to the center of the room and climb on it to reach the bananas. Use DDR to show that the monkey can get the bananas.

The predicate of interest is can-get:

(can-get state)

which means "in state the monkey can get the bananas." A state is an object representing the state of the world. A state has structure, so you need to represent it with a functional term. For example, you might use

(state mloc bloc on)

where mloc and bloc are the location (door, window, center) of the monkey and box respectively, and on is what the monkey is standing on (floor, box). The initial state has the monkey with no bananas, on the floor, at door, and the box at window. Note that state here is a function, not a predicate.

You have to give rules that say whether can-get is true for a given state. can-get is clearly true for the state where the monkey is on the box and the box is in the center of the room.

can-get is also true for any state that can lead to a state where can-get is true. A state can lead to another state if there's an action the monkey can do in the first state that results in the second state. For this you need to define rules about the predicate can-lead-to

(can-lead-to state1 action state2)

where actions are structured objects, e.g.,

(walk loc1 loc2)

could be the action "monkey walks from loc1 to loc2." For example, one rule you need for can-lead-to is "if the monkey is at location P1 and walks to location P2, the monkey will be at location P2." You also need rules for moving objects, like the box, and so on.

If you have the correct rules, can-get of the initial state described above should be true. If you remove the box from the room, however, it should be false. Test this.

Extension: It can be kind of unsatisfying to ask "can the monkey get the bananas" and only get the answer yes or no. More interesting is to get "how" the monkey gets the bananas. To do this, add an argument to can-get for a sequence of actions that lead to the solution state, e.g.,

(DO (WALK DOOR WINDOW)
  (DO (PUSH-BOX WINDOW CENTER)
    (DO CLIMB-BOX DONE)))

which is one possible sequence of steps that will get the monkey the bananas. I used (do action sequence) to represent "do action before the actions in sequence and done to represent the end of the sequence. You can use whatever you like. The analogy to cons and nil in the append rules is intentional.

You will need to figure out what you need to change in your rules to construct the sequences.

Do this extension only after you have the simpler rules working.

A Real Problem

Puzzles are fine for testing and exploring, but in real life we need programs to solve real problems, like assigning resources to tasks, choosing parts for computers, and so on. Find a real world task that seems appropriate for deductive retrieval, represent it with a set of predicates and results and possibly functions, and apply the Retriever to it. Any interesting domain should be at least as complex as Monkeys and Bananas.

Experiments

Gather data on how both versions of the Deductive Data Retriever runs for map coloring, Monkey and Bananas (M&B), and your own real problems. In particular,

When showing numeric data, tables and charts/graphs help a lot.

The Report

Put your report in a Word document (or RTF file if you use something other than Word). Separate the document into clearly labeled sections based on the above, i.e., a section on how you changed the Retriever, a section on how you implemented the cryptarithmetic problem, a section on the experiments and results, and so on.

Create the following files:

Just send in the DDR patch file, not the entire DDR code.

Send the Zip file as an attachment in an email to c-riesbeck@northwestern.edu, with the Subject line: CS 348 Task 2.


Comments? comment image Send mail to Chris Riesbeck.