An efficient artificial-intelligence-type algorithm for the propagation of temporal constraints has been devised for incorporation into software that performs scheduling and planning of tasks in real time. This algorithm checks for temporal consistency and computes time windows of time points within temporal-constraint networks, which are often used in scheduling and planning. A C++-language computer program that implements the algorithm has been devised for incorporation into the control software of the Mission Data System of NASA’s Jet Propulsion Laboratory. The algorithm and program could also be applied to industrial planning and scheduling problems.
For the purpose of this discussion, “time point” signifies the nominal or planned time of occurrence of a specified event in, or state of, the system (e.g., a spacecraft or a production line) that is the subject of the planning and scheduling effort. A temporal-constraint network is equivalent to a graph, the nodes of which represent time points and the lines of which represent temporal constraints. The simplest such network (see figure) contains one predecessor and one successor time point that are required to be separated by a time interval of not less than a and not more than b. In forward propagation in this network, one would endeavor to update the time window of the successor point to be consistent with the time constraint and the time window of the predecessor point; similarly, in backward propagation in this network, one would endeavor to update the time window of the predecessor point to be consistent with the time constraint and the time window of the successor point.
The present algorithm involves iterations of forward and backward propagation; each iteration consists of a forward sweep followed by a backward sweep. Each sweep starts the propagation of temporal constraints from a subset of time points. During the propagation, the algorithm updates the time window at each time point by use of all its incoming temporal constraints in a forward sweep or all of its outgoing temporal constraints in a backward sweep. A data structure denoted a propagation queue is used to store time points, the successors or predecessors of which are to be updated next in a forward or backward sweep, respectively. Once the time window of a time point has been updated and all its incoming (or outgoing) temporal constraints have been used, that time point is placed in the propagation queue.
A forward sweep starts from a set of time points that have no predecessors. These time points are put in the propagation queue, then the sweep proceeds until the queue is empty. The backward sweep starts from a set of time points that have no successors, and then proceeds similarly to the forward sweep. It is assumed that there are no cycles (time-constraint paths that begin and end at the same time point) so that the algorithm will not enter an infinite loop during a sweep. The algorithm performs as many iterations as are needed until either (1) there is no window left to be updated or (2) a window of negative length is created. In case (1), the final windows of all time points are considered to have been computed and the network is considered temporally consistent. In case (2), the algorithm returns the message to the effect that the network is temporally inconsistent.
The great advantage of this algorithm, relative to a prior temporal-constraint-propagation algorithm, is its computational efficiency and thus computational speed, and storage saving. The prior algorithm requires O(N3) number of arithmetic operations and O(N2) amount of memory [where O(x) signifies proportionality to a quantity of the order of x and N is the number of time points in a temporal- constraint network]. In contrast, the present algorithm requires only O(N) number of arithmetic operations and O(N) amount of memory.
This work was done by John Z. Lou of Caltech for NASA’s Jet Propulsion Laboratory. Under the Information Sciences category. NPO-21098