Artificial Intelligence (W4701)

Homework 2:

Knowledge Representation: What and When

Due Date: Tuesday, October 26.


Part 0: Written Work on Knowledge Representation

  1. Exercise 6.1 (about 2 sentences only, please)
  2. Use a truth table to show p->q <--> q V ~p. (Also, think about what that means a little...)
  3. Exercise 6.5
  4. Exercise 6.7
  5. Exercise 6.12. Your knowledge base should start with sentences directly from the first paragraph of this exercise. Inferences are then done only by applying the rules from Fig. 6.13.
  6. Exercise 6.15 a and b, only -- no implementation.
  7. Exercise 7.3 a, b, c, d, e, f (only).
  8. Exercise 7.5
  9. Exercise 8.8
  10. Take (a small version of) a temporal network you devised for Part I below (at least 4 nodes, i.e., intervals) and represent it in first-order logic. Then, also represent 3 entries (i.e., boxes with a set of relations) of your choosing from the transitivity table in the paper by Allen and represent them in first-order logic. In one or two sentences, do you think a general-purpose first-order logic inference engine would be as efficient as the algorithm in the Allen paper? Why or why not?

Part I: Temporal constraints applied

Get the system from

Compile and run To compile it, type "javac". To run it, type "java part2". This will give you a ">" prompt, at which you enter a constraint between two intervals.

The system (implemented in Java by Jeff Sherwin) implements the following simple text-based I/O format: "INTERVAL-VARIABLE (CONSTRAINTS) INTERVAL-VARIABLE". For example, given "x (> m) y" and "y (>) z", one of the things it will output is "x (>) z".

When you type return with no input, it shows you the final network.

Note: If you try to use more than 20 nodes in your network, change, where this is hardcoded ("AdjMatrix graph = new AdjMatrix(20);") to a bigger number (Thanks to Haoqiang Zheng), or else you will get an "overflow" error spit out at you.

Select one of the following example toy problems to represent as temporal constraints, and use the system to infer maximal constraints.

You can make slight variations to the example you choose, or expand it if you like. If so, be sure to explain how you varied it in terms of the English description.

Draw two graphical depictions of your input: one in terms of time intervals and how they overlap, and one as a temporal network. Then show your on-line encoding of the temporal network (trivial transformation). Show the system working on the example. Make two or three variations, showing the differences in results for each variation. Draw the resulting temporal networks.

Read through all of these examples, not only to select one, but to learn a range of examples.

At first, do one with only a small number of intervals -- try it by hand to compare to the system. This will also help you prepare for the midterm.

You may work in small teams of 2 or 3 people on the construction of such example inputs. If so, make this clear on your hand-in.

Part II: Evaluating Temporal Constraint Propagation

Design and execute a series of experiments to see how much information a temporal network can maintain. Specifically, your system will randomly create a series of time intervals in one dimension (time -- isn't it the fourth dimension?), and feed constraints into the network until the network has completely figured out all temporal relationships (i.e., no disjunction, i.e., exactly one relation per arc).

For example, if there are 5 intervals, and I know all (5*4) of their relationships (established randomly for this experiment), I can give the temporal network one relationship at a time, keeping track of average set-size per arc. Do this kind of thing repeatedly, make a table of the results, and write a paragraph describing the tables contents, and another making any conclusions you can.

The random intervals can be established by picking random endpoints. If the endpoints are numbers between 1 and 5, many will start or end at the same point. If they are between 1 and 100, this is less likely. Pick a pragmatically sensible range for the purposes of this experiment. This method ensures that the set of temporal relationships are possible, and so the system should never detect an inconsistency (if it does, it will give an error saying there is a null arc -- no items on an arc, i.e., no possible relationships left).

The experiments must be generated by a computer program. If you write it in Java, you can connect it directly to our implementation. If you want to do it in LISP, ask me (Eric) -- I think I can point you towards an implementation.

email: evs at cs dot columbia dot edu