Root finding for the common case of uncontrollable, but secretly fixed or parametric duration activities

[mattdailis]

When the scheduler does not know the expected duration of an activity, and yet it needs to schedule it with certain temporal constraints, it performs root finding (for an illustration see the last few slides of this presentation).

We have a @FixedDuration annotation that allows a mission modeler to declare that their activity has a known duration, and we also have an @ParametricDuration annotation that declares that the activity's duration can be computed as a function of its parameters.

This discussion pertains to activities that have fixed or parametric duration, but have not been annotated as such. Would it be worthwhile to tweak the root finding algorithm to find solutions for these sooner?

Root finding starts with two guesses - one at the extreme minimum start time (could be the beginning of the plan), and one at the extreme maximum start time (the start time that would be valid if the activity duration was zero). It then uses the slope of the function to determine the best third guess. If the activity's duration is secretly fixed or parametric, this third guess should always succeed.

The suggestion is to make the optimistic assumption that the activity's duration will remain the same across guesses. After the first guess, the second guess could place the activity in the most likely correct location, rather than placing it at the maximum start time.

Open questions are:

• We would expect this case to be common, but have not actually measured this.
• The case of "schedule a slew to end before time t" does not fall into this case. However, if the variation in slew duration is not large, it may be "close enough" to a constant duration, such that the second guess will still succeed
• Is it important to "bracket" the solution? Or are two guesses on the same side of the solution still useable for the secant method?

[adrienmaillard]

We do not do bracketing because bracketing requires x1 and x2 such that f(x1) has a different sign than f(x2). Then, these methods rely on the intermediate value theorem (IVT) to ensure the root is found.

So we cannot use a bracketing method as a default because it would require search for these x1 x2 before doing any rootfinding. But in the secant method we compute some x1 and x2 (bounds of the start interval). If we detect the condition, we could switch to another method to ensure that a root is found.

The secant method has no guaranteed convergence. The bounds we compute in the beginning could bracket the solution but the secant makes no use of this information and could diverge depending on the shape of the function.

I guess we could use a best guess as our x2 and see what happens.

I have just gave a quick try at this and I have one test failing. Not the most difficult time-dependant non-linear stuff but a rather simple case. I'll look at it more closely when I'll have some time.