[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publication: [PUBLink])

This heuristic is always applicable. The idea is to introduce an event that changes the SRC's state in such a way that a Precondition Task becomes less inconsistent.

One of the SRC's inconsistent Precondition Tasks that is after the current time c is selected with a choice probability for a Precondition Task that is proportional to the inconsistency caused by the Precondition Task.

An interval i is to be chosen, in which an event will be added to reduce the inconsistency of the chosen Precondition Task p. Initially, i is set to the interval of p. If p is at the very start of i, the heuristic is stopped and a negative success value is returned, because this means that there is no room to include an event without its overlapping with the interval's event.

Each time the state-distance table provides the information that it is not possible to transform the state of i into the state requested by p, i is set to its predecessor interval. If i is the first interval and a state transition is still not possible, the heuristic is stopped and a negative success value is returned. This is also done if a state transition from i's state to p's requested state is possible but i is not long enough for an event to be inserted without causing an overlap with the event of i.

The event is to be placed at a time point t, which is to be between two previously computed time points t₁ and t₂. The idea of this balanced placement is to ensure a maximal space with respect to other tasks that interact with the event and with further events that would need to be inserted to achieve full satisfaction of p.

If i is still the interval of p, t₁ is computed by setting it to the same time point as the interval's last Precondition Task before or at the same time point of p. If i has no Precondition Tasks or all other Precondition Tasks of i come after p, t₁ is set to the interval's begin. If t₁ is before c, t₁ is set to c.

If i is before the interval of p, t₁ is computed by setting it to the same time point as i's last Precondition Task. If i has no Precondition Tasks, t₁ is set to the i's begin.

t₂ is set to the same time point as p. If i is before the interval of p, t₂ is set to the last time point of i. To place t at a time point such that there is enough room for further events that would have to be inserted to achieve full satisfaction of p, t is computed as:

There is a possibility of t₁'s being set to an interval's begin. This placement would be unfavorable because a new State Task at this time point may interact with the interval's State Tasks. Thus, if t is equal to t₁, t is set to t + 1. If t is now higher than t₂, t is set back to t₂. If t is before c, the heuristic is stopped and a negative success value is returned.

One state is chosen from among all the states that can be derived by a state transition from i's state, a choice probability for a state being proportional to , where d is the state's state-distance to the state required by p. The event that causes the selected state is the event to be added.

If multiple different sets of Contributions can cause the event, one of the sets is chosen at random. The addition of a new action (i.e., of a Task Constraint) described below is done for every Contribution of the selected set.

There may be numerous different ActionTypes for Task Constraints that imply a State Task with the required Contribution. To choose from among them, the insertion of each relevant type of Task Constraint (together with its tasks) is simulated, the change in overall inconsistency being recorded. The tasks of an action are inserted at time points such that the required Contribution occurs at time point t, and the temporal relations of the Task Constraint are ensured by a process similar to that described in Section [Aggressive Heuristics].

The choice between the ActionTypes is made in such a way that the choice probability is dependent on the inconsistency change. The chosen action is inserted as in the simulation.

For questions, comments or suggestions, please contact us.

Last update:
May 20, 2001 by Alexander Nareyek