Advanced Intelligent Systems (W4721)

Homework 1: Temporal Inference

Due Date: Tuesday, February 16, 1999.

Reading: Chapter 8 from Russel and Norvig. For this chapter, you are only responsible for the concepts, not the technical content. Sections 8.3 and 8.5 are optional.

"Maintaining Knowledge about Temporal Intervals" by J.F. Allen. Section 5 is optional, but why not at least read the first paragraph since that section does something pretty clever? Also, Section 7 is optional, but why not skim it; it can give you ideas for part III below. There are a couple errors in the constraint propogation algorithm in this paper. In, "If R(k,i) is a proper subset of N(k,i) then add to ToDo;" all i's should be j's. And, in, "If R(i,k) is a proper subset of N(k,i)" the N(k,i) should be N(i,k). Also, in the lightswitch example, there is a mistake when the second sentence is incorporated -- there is an extraneous relation on one of the arcs.

Part I

Part I is TBA. It will have a little reading and a hand-written question about basic ideas of planning.

Part II

Implement Allen's temporal contraint propogation algorithm. You must work alone on part II. You are expected to do this in one week.

See for the transitivity table in Java, or email Jeff for it in another programming language.

Your system should implement 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". You can have a menu mode in which you keep adding new constraints and can ask it to spill its guts whenever it wants, and/or you can have a command-line mode where it takes a set of constraints as standard input and then dumps the resulting network. Actually, you can provide the 2D adjacency matrix or an adjacency list as a more concise form of output.

You'll need at least the following data structures (or classes):

Select one of the following toy problems to represent as temporal constraints, and use it to test your system. You can make slight variations to the one you choose, or expand it if you like. Show your system working on the example, and also provide the semantics between each inputted constraint, and your semantic interpretation of the resulting inferences. Actually, you may work together on the construction of such example inputs, and you may share them across the class.

Part III

This is the larger part of the homework. You can pair up and work with a partner for this part. You are to build on top of your system one of the following. Pick something that interests you. Keep in mind that you can build further on what you do here for the final project of the course. In terms of magnitude, note that your grade for this assignment will rely twice as much on Part III as on Part II, but do not get too ambitious -- you should select a 2 week project here that will not burn you out. You must supply a 1-2 page writeup describing your project, the choices you made, the rationale for these choices, and the results. You also must supply a transcript of its operation. Put it in html (and link to an applet demo?) if you'd like it to be part of the growing archives of our course web page.

email: evs at cs dot columbia dot edu