[ 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 applicable if there is at least one inconsistent Precondition Task that is not connected to the Task Constraint of S_Goals. The idea is to temporally shift a Precondition Task such that its inconsistency is decreased.

One of the SRC's inconsistent Precondition Tasks that are not connected to the Task Constraint of S_Goals is selected with a choice probability for a Precondition Task that is proportional to the inconsistency caused by the Precondition Task. If one of the Action Tasks that belong to the chosen Precondition Task's Task Constraint has already been executed or is currently under execution, the heuristic is stopped and a negative success value is returned.

The new places considered for the chosen Precondition Task p are in the predecessor interval i_p or successor interval i_s of p's interval i. The predecessor option is dropped if i is the first interval. The successor option is dropped if i is the last interval.

Each time the state-distance table provides the information that it is not possible to transform the state of i_p into the state requested by p, i_p is set to its predecessor interval. If i_p is the first interval and a state transition is still not possible, then the predecessor option is dropped.

Each time the state-distance table provides the information that it is not possible to transform the state of i_s into the state requested by p, i_s is set to its successor interval. If i_s is the last interval and a state transition is still not possible, then the successor option is dropped.

If p's inconsistency is not equal to the dead-end value, p's current interval i is also an option, i.e., no change will be made if i is chosen.

From all interval options, an interval is chosen with a choice probability for an interval that is proportional to , where d is the state distance from the interval's state to the state required by p. If there are no interval options for the choice, or if i is the chosen interval, the heuristic is stopped and a negative success value is returned.

If the chosen interval is the last interval, the Precondition Task p is moved to the interval's beginning. Otherwise, the Precondition Task p is moved to the middle of the chosen interval.

For questions, comments or suggestions, please contact us.

Last update:
May 20, 2001 by Alexander Nareyek