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 II

See http://www.columbia.edu/~cs4721/ 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):

• transitivity table (see link above)
• queue
• set (representing disjunction of temporal relationships, e.g., a bitstring of length at least 13)
• the network -- a fully connected graph. Parlez-vous 2D array?
• symbol table of variable names

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.

• 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. KR '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?
• Something of your choosing, e.g., 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.

Part III

• Aircraft scheduling system (Jeff'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 iteneraries 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.

  Since your system does not deal with constraints between interval durations, some constraints that are not handled by the temporal system must be checked after the temporal system has done its thang. For example, a plane can do no more than 3 flights per one third of a day. Also, at some airports, if you have more than one plane on the ground at once, a new interval must be asserted -- a time delay (equal to one flight) for food and fuel service) for one of the planes. If the resulting temporal constraints after propogation are not satisfactory, you system can iterate, adding constraints (e.g., for a service delay), or alleviating some constraints, e.g., some customers won't get the time of day they want. If a plane will deliver customers from city A to B, and then C to D, and if B doesn't equal C, then it must go from B to C in the middle -- add another interval to the network.

  Other constraints iteratively added to the temporal system include the fact that no two flights can take off simultaneously or land simultaneously at the same airport. Let me know if you think of a couple other such constraints.

  Optional: Deal dynamically with unpredictable flite delays.

  Note that you will need to generate output plans -- i.e., augment the basic reasoner so it can manifest a constraint network into a plausable sequence of events.

• Plan recognition or plan subsumption inference. The algorithm for this will be described in class, but not as extensively as the main temporal inference algorithm. Therefore, you can select this project if you are interested, but you will probably need to get a paper from me describing it (available on request). In addition to the constraint system from Part II above, you also need a small semantic hierarchy of primitive action types (domain-specific, but trivial). Input is two plans (i.e., temporal nets); output is whether one subsumes the other, and, if so, what the matching is between the plans.

  To decide if plan A subsumes plan B use backtracking search to see if each actions in plan A can be mapped to a distinct action in plan B such that every action in plan A subsumes the corresponding action in plan B, and the temporal constraints between actions in plan A subsume the corresponding constraints in plan A. Qualitative temporal constraint subsumption follows from set containment, e.g., "before, during, or after" subsumes "before or after".

  Create a toy example of the magnitude of that from Part II above to demonstrate this, e.g., cooking.

• A project of your choice. This project must either be similar to one of the two ideas mentioned above, or you must check it with the TA and instructor first. Talk to the TA first. Within this category would be a NLP system, e.g., to select the right verbs and connectives to describe a senario. 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.

email: evs at cs dot columbia dot edu