Reading:

• Russell and Norvig, Chapter 6.
• Russell and Norvig, Chapter 7 (7.2 is optional).
• Russell and Norvig, Chapter 8. For this chapter, you are only responsible for the general concepts, not the full technical content. Sections 8.3 and 8.5 are optional.
• "Maintaining Knowledge about Temporal Intervals" by J.F. Allen. The algorithm in Section 4 can be difficult to understand at first. We will go over it in class. Basically, it just propagates transitivity through a network until there is nothing new to propagate. Perhaps it is elusive to understand because it is expressed recursively. If an exam question deals with this algorithm in detail, you will be allowed to look at the paper during the exam. 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?

  There are a couple errors in the constraint propagation algorithm in this paper (but these have been written in if you got the hardcopy we photocopied for class). 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 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

Compile and run part2.java. To compile it, type "javac part2.java". 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 AdjMatrix.java, 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.

• The Optimal Picnic. You need to plan which order to eat your food that you brought with you for a picnic. There are several constraints that interact. I give a few here, and ask you to come up with a few more. The apple turns brown after you begin to eat it. You want to finish eating it before it has become brown. The dessert should be eaten after the main course, or it should be eaten first, before anything else (if you are having a rebellious day). The ants start to come after you have opened the can of tuna fish, or after you have opened the dessert. You must leave before the ants come. You must wash down your main course with a fluid. You start to sweat and ruin your tuxedo when the sun comes out. The sun comes out after the wind blows. The wind blows after you call your friend in Taiwan on your cell phone, who tells you he sees a butterfly flap it's wings. You need to call this friend, but you can't make the call while you are eating the main course.

  Woody Allen stated the following observation regarding humanity. "Why does man kill? He kills for food. But not only food. Often, there must be a beverage." In total there are at least the following foods to be eaten: apple, beverage, tuna, main course, and dessert. Take note, there are other intervals in this problem other than the eating of each food item.

• Uncle Albert. This one comes from the literature, but was intended to test a system that handles both qualitative and quantitative constraints. Since your system only handles the former, you probably want to make some alterations. The conference on Knowledge Representation '91 is on the 22nd-25th. You need to schedule a two day workshop immediately before or after the conference. You also want to spend either the day before or the day after the conference sightseeing with your Uncle Albert. You can't sightsee on the days of the workshop. The room for the workshop must be reserved two weeks in advance, and it's already the 7th. When should you tell Uncle Albert to expect you?
• The aircraft incident that may result when a certain set of events take place, e.g., unauthorized slats deployment, altitude over some threshold, speed over some threshold, slats disagree indicator illuminates, manual deployment of slats, aircraft nose increases, automatic engagement of autopilot, autopilot over-ride, pilot fatigue, pilot error, galley coffee maker failure, aircraft incident.
• Aircraft scheduling system (Jeff Sherwin's idea). A small corporate jet company (that we will all use someday) has a limited number of planes and very demanding clients. Since flights are based on the times that meetings finish and start, there are no time points specified for flights. Devise a method to coordinate multiple flights for for multiple clients given a specified small number of plans. Assume there are are only a small number of cities with varying distances (and therefor flight times) where these planes can land. Complicated examples that the computer can solve and verify that the companies flight plan will work will earn the higher grades.

  Assume there are, e.g., 3 planes and 5 cities. The system's is to compute the itineraries of the planes for a given day. The input is the customer requests pertaining to that day. Each customer request indicates where to and from, and requests which part of the day: early, mid or late. The customer understands that they may not get their first choice on time of day. Assume that the flight of one plane between two cities serves exactly one customer request (i.e., you can't fit more than one customer into the plane), or assume the alternative possibility; make your assumption explicit.

  Your system needs to find a mapping of planes to requests, and the day's itinerary of each plane. Note that once you have mapped planes to requests, this manifests as a series of temporal constraints, e.g., early-day flights must come before mid-day flights.

  Hint: Have early-day, mid-day and late-day be temporal intervals.

• Something of your choosing. This project must either be similar to one of the two ideas mentioned above, or you must check it with a TA or the instructor first. Talk to the TA first. Note that some problems are not appropriate for this kind of qualitative reasoning. For example, planning the courses to take over 4 years for a computer science major involves temporal constraints, but in this domain there are only 5 (vs. 13) possible qualitative temporal relationships between any two events (i.e., courses): before, meets, equals, before-inverse and meets-inverse.

Part II: Evaluating Temporal Constraint Propagation

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