Issues on the correctness of the scheduling engine

[adrienmaillard]

I have found two issues affecting the correctness of the scheduling engine. Basically, we are underestimating how flexible the behavior of an activity can be.

(1)

We go through each goal only once. Let's say G1 is a goal that has been evaluated on an empty plan and produced 2 conflicts. G1 has scheduled activity A1 that was successfully simulated. A1 starts at time 10. But G1 is not completely satisfied, it required another activity that could not be scheduled.

Then we go to goal G2 that requires us to schedule activity A2 starting at time 2. When we simulate the activity, we use incremental scheduling and stop it at the end of the last activity of the plan, that is the end of A1.

But A2 could modify the resources in a way that A1 does not execute in the same way/has its duration changed which might invalidate the satisfaction of G1 by A1. If for example, A1 was supposed to end at a specific time.

Rather than just checking if simulation executes without error, we should check that previously inserted activities (that are scheduled after the lastly inserted activity) are not impacted by the last activity we inserted. If some activities have been impacted (their parameters and/or end time have changed), we should check whether their associated goal is still satisfied and if not, reject the last insertion.

But there is a difficulty. Let’s say that A1 has its parameters or end date changed and that it indeed invalidates G1. Simply re-evaluating conflicts for G1 will not be satisfying as G1 ended up not being completely satisfied at the first iteration. When finding there are two conflicts, we will have no way of attributing the conflicts to the insertion of A2 because we do not record which conflicts were initially produced and with what activity insertions they were solved.

TODO:

• Record solving steps to be able to check against potential changes (this is going to also help in the future if we do backtracking)
• Check for plan changes whenever a new activity is simulated before the latest activity in the plan.

(2) Edit: as of june 7 2023, the following has been fixed

There is also an oversight of the scheduling engine, the possibility that an activity spawns other activities. When simulating an activity, we do not check/record whether other sub-activities have spawned or not. In the best case, these activities might help satisfy goals. In the worst case, they might violate global constraints.

TODO:

• The scheduling engine should record these spawned activities and use them for satisfying goals/checking global constraints.

[pranav-super]

For (1), could we implement some sort of fixed point iteration that in determining when to stop implements some sort of prioritization based on goal satisfiedness?
For example, say we iterate a bunch of times on the goals and it happens that G1 is not satisfied but every time we iterated, G2 was satisfied, then we drop the priority of G1, or raise the priority of G2, and then end execution as all higher priority goals (like G2) have been satisfied?
Or we could not do any sort of prioritization and after a fixed point is reached (whether or not goals are satisfied) we end execution and report back to users which goals were and weren't satisfied?

[adrienmaillard]

We can't change the priorities of goals. If there is any chance to satisfy G1, we must do it before satisfying G2. But the kind of moves you describe can probably be used in an explainability step to explain why G2 cannot be satisfied. And provide an advice to the user saying how he could arrange priorities better. But we are far from that moment. What I am proposing is barely maintaining consistency/correctness from one goal to another, making sure we are not invalidating previously satisfied goals.

[adrienmaillard]

(The idea of perturbating the priorities is generally a good one when trying to optimizing such problems. Several metaheuristics could be put on top of a greedy algorithm (such as genetic algorithms or large neighbourhood search...) but your comment made me think of Squeaky Wheel Optimization that tries to shuffle the priorities according to some analysis of current flaws. If you are interested, here is the paper: https://jair.org/index.php/jair/article/view/10231/24345)

[pranav-super]

Also, this is separate from the two concerns you voiced but might be relevant to overall scheduling fixes, and that's that I believe activities without a controllable duration behave somewhat unpredictably - this was something encountered when implementing AERIE-1880; not sure if that is of similar priority to what you've suggested here, though.

[adrienmaillard]

You're right. Some changes in #234 are trying to address this.

[adrienmaillard]

Writing as an occurrence of the first issue I wrote about almost a year ago happened in Clipper:

• We have act A, B and C.
• And two goals G1 and G2.
• G1: schedule B for each C, ends at start of anchor.
• G2: schedule A for each B, ends at start of anchor.
• C is already in the plan.
• A and B are both GNC activities that modifies the same state.

G1 is solved first, it successfully schedules a B ending at the start of C.
Then G2 is processed, and outputs an A. But because A modifies the same states as B, B takes longer to finish and ends after the start of C, violating the satisfaction of G1.