In DiTops we have operations that represent activities. These operations have sets of values that define temporal events of interest. An operation can also have constraints that define the acceptable values for the temporal events. A constraint defines a relationship between the values in one operation and either an absolute value, or the values in a different operation. The propagator traverses the graph of operations and constraints and either creates for each operation a set of acceptable values consistent with the constraints, or detects that for some operations no values are consistent with the constraints. This page describes the set of constraints that apply to the start and completion time bounds for the activity represented by an operation. The propagator uses these constraints to create an arcconsistent set of values for the start/completion times.
The constraints on the start and completion times can be broken into two sets. The first set represents relationships of the constrained time to some user specified absolute time. I call these Absolute Constraints. The second set of constraints represent a binary relationship between two operations. I call these Relative Constraints.
All of these constraints are defined as constraints on a particular timebound of an operation.
The set of Absolute Constraints currently in use are given in the following table:
Name  Constrained Value  Parameters  Semantics 

Earliest Start (EST)  Start time  time value Maximum Deviation 
Operation must not begin before EST. 
Earliest Arrival (EAD)  Finish time  time value Maximum Deviation 
Operation must not end before EAD. 
Due Date (DD)  Finish time  time value Maximum Deviation 
Operation must end before DD. 
The obvious hole in the set of Absolute constraints is a Latest Start constraint. That constraint does not currently exist mainly because no application has required it. DiTops can relax these absolute constraints to find a feasible solution to some scheduling problem. Currently DiTops allows the Due Date and EAD to be relaxed. These are the correct constraints to relax for some domains. However, if one is attempting to fire a rocket and only have a short window in which firing is possible, then holding the Due Date as unmovable and relaxing the Earliest Start Time is correct. The "Maximum Deviation" parameter in the above table is intended to allow a partial relaxation of a constraint. The intent is to allow users the ability to specify that these constraints can be relaxed a little if necessary. Allowing a constraint to be Completely relaxed is controlled by other means.
The set of Relative Constraints is given in the following table:
RELATIONSHIP NAME  Parameters  Semantics  

Before  Minimum Offset Maximum Offset 
Operation 1 must end before Operation 2 starts. "Sue must get to the airport before boarding the plane." 

Startsbefore  Minimum Offset Maximum Offset 
Operation 1 must start before Operation 2 starts. "While Sue mows the grass, I'll rake the clippings." 

Endsbefore  Minimum Offset Maximum Offset 
Operation 1 must end before Operation 2 ends. "The airport must be cleared before the plane's flight can end." 

Samestart  Window Size  Operation 1 and Operation 2 must start within window time of each other.
Order of starting is unimportant. "The two nuts, on each side of the rod, should be tightened from both sides to keep the rod from overturning." 

Sameend  Window Size  Operation 1 and Operation 2 must end within a defined time of each
other. Order of completion is unimportant. "Loading the fuel, and loading the cargo should be done about the same time." 
An obvious lack is a windowed relation from the end time of OP1 to the start time of OP2 (a windowed "Before"). The semantics of this relation would be that OP1 should end about the time OP2 starts. As with the other "windowed" relationships, OP2 could start before OP1. OP2 just can't start too soon before OP1.
In the Relative Constraints table, the pictures on the right show how a constraint relates the two activities (OP1 and OP2). For both activities the start time is represented by the left arrow, and the end time the right arrow. Within the small square the area with slashes () represents the minimum time interval which is the minimum amount the arrows should be separated. The arrows can not be inside the minimum separation area without violating the constraint. In the diagrams with a minimum constraint, the two activities are shown as being as closely aligned as possible. However, the two activities could be separated by more time, up to the maximum separation value, and still not be violating the constraint.
Allen has described a set of relations between time intervals that can be implemented via the relations above. The mapping between Allen's relations and the set of DiTops relations is given in the table below.
Allen's Relations  DiTops Relations 

Before(OP1,OP2)  Before(OP1,OP2,Finitetime,Infinity) 
Meets(OP1,OP2)  Before(OP1,OP2,0,0) 
Overlaps(OP1,OP2)  StartsBefore(OP1,OP2,Finitetime < Duration(OP1),Duration(OP1)) 
Starts(OP1,OP2)  StartsBefore(OP1,OP2,0,0) 
During(OP1,OP2)  StartsBefore(OP2,OP1,Finitetime,Infinity) EndsBefore(OP1,OP2,Finitetime,Infinity) 
Finishes(OP1,OP2)  EndsBefore(OP1,OP2,0,0) 
Equal(OP1,OP2)  StartsBefore(OP1,OP2,0,0) EndsBefore(OP1,OP2,0,0) 
The main difference between Allen's interval relations and DiTops's interval relations, is the ability in DiTops to specify an approximate relationship between two intervals. In Allen's interval relations, specific points in time (perhaps with unknown values) are related. DiTop's relations include a range of values either from min to max or within a window and these ranges allow for some uncertainty to be represented. In creating his temporal relations, Allen was setting up an interval temporal logic system, where he could classify all relationships between intervals uniquely. In Allen's temporal logic, he can describe exactly how a specific action will change the world over a period of time. To describe how the world changes over a period of time, Allen invokes the standard closedworld assumption. In contrast, DiTops relationships are intended to model real world activities where all the changes to the world are not fore known and the resultant uncertainties abound.
The desired functionality is different too. Allen wants to model causeeffect where both cause and effect occur over some temporal interval. In this mode, it is computationally cheaper to model relations as between time points. In contrast, DiTops wants to optimize resource utilization or due date satisfaction when scheduling multiple plans. For DiTops, it is computationally cheaper to model relations with some slack. The existence of some slack can help limit the propagation of small changes.
gap+@cs.cmu.edu