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.
See the DDR Setup Instructions for details on installing and testing 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
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
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
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 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-getfor 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
doneto represent the end of the sequence. You can use whatever you like. The analogy to
appendrules 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.
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.
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.
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:
name-task2.doc, where name is your last name.
Just send in the DDR patch file, not the entire DDR code.
Send the Zip file as an attachment in an email to
with the Subject line:
CS 348 Task 2.