RFC: Spans-based Scheduling

[JoelCourtney]

RFC: Windows-Based Scheduling

This proposes changes to the Windows API and a redesign of the Scheduling API, which would use Windows as the primary way of determining how a Goal should behave. The two main reasons for these proposals are:

1. I believe this interface will be much simpler than the current Goal API in the long term.
2. We have to expand the Windows API to be more robust for Constraints anyway, so it makes sense to leverage that for Goals too.

These proposals use the ideas of "windows patterns" and "activity patterns". These are just collections of windows or activities that have relative positions but no absolute position. We won't need special classes to handle these objects though. A "windows pattern" is just a normal Windows object, but the function that uses it is allowed to move the absolute time anywhere it wants.

Updates to Windows API

Each item below is marked as whether it would be required in order to accomodate the proposed Scheduling redesign.

ForEachActivity produces Windows (required)

Change it to produce Windows instead of Constraint. This would require a refactor to the Windows Java object to keep metadata about the activities that generated it. New usage:

// Violate when starting an activity
export default (): Constraint => Windows.ForEachActivity(
    activityType,
    instance => instance.start()
).invert()

The new ForEachActivity would just perform a Union of the generated Windows. Also, given the pattern that a lack of window is a violation, we'll have to store the activity metadata in the gaps between windows when invert() is called.

ForbiddenActivityOverlap produces Windows (free)

Change it to a windows-producing ActivityOverlap. New usage:

export default (): Constraint => Windows.ActivityOverlap(activityType1, activityType2)
    .invert()

This would allow it to be used in scheduling too. This change would be free because the above change to ForEachActivity would make this happen naturally.

Manual Window Creation (required)

Ability to create windows separate from profiles. Usage:

// Instantaneous window at a given time
Windows.Instant(dateTime)

// Inclusive window between two times
Windows.Interval(dateTime, dateTime)

The case of creating a window with a start time and duration would be handled by Adrien's shiftBy operator: Windows.Instant(dateTime).shiftBy(0, duration)

Bound Inclusivity (optional)

Ability to toggle inclusivity of Windows bounds. Usage:

windows.setBoundTypes(BoundType.Inclusive, BoundType.Exclusive)

Repetition (required)

There are two kinds of repetition likely to be useful. Both use the concept of a "windows pattern", which is the relative positions and durations of a Windows set, without the absolute locations. This doesn't require a special class to represent it though.

Separation-based

We need to repeat based on a duration. I imagine that this operation would repeat a windows pattern both forward and backward to both horizons, and the user could then filter the result; but that is up for debate. Usage:

windows.repeatEvery(duration)

Number-based

We also need to repeat a fixed number of times in a range. This could be done in a number of ways.

1. spacedInstants: produces a set of N equally-spaced instantaneous windows for each window of the this Windows object. (I think of this like MATLAB or numpy's linspace.)

   // N must be >= 2
   windows.spacedInstants(N)

2. split: splits each window into N equally-sized windows by removing N-1 instants in the middle.

   // N must be >= 1, but N=1 does nothing
   windows.split(N)

3. repeatInside: essentially performs spacedInstants but with a custom windows pattern. Aligns the start of the first pattern instance with the start of the window, and the end of the last pattern instance with the end of the window. Ensures equal spacing in between pattern instances.

   // N must be >= 2
   windowsPattern.repeatInside(parentWindows, N)

   If the repeated windows patterns are too long to fit inside the parent windows back-to-back, then a naive implementation of this method would produce overlapping windows. Personally I think that's OK as long as the user is aware of that behavior.

repeatInside is a more general version of spacedInstants, because: windows.spacedInstants(N) == Windows.Instant(0).repeatInside(windows, N). Personally, I think implementing both repeatInside and split would be ideal.

Starts and Ends (useful, maybe not required)

Ability to replace windows with their start or end points. Useful for making windows on directional transitions in Real profiles. Example usage:

Real.Resource("state of charge").lessThan(0.3).starts()

Unlike Real.Resource("soc").equal(0.3), this produces an instantaneous window only when state of charge drops below 30%, not when it rises above 30%.

This particular example could also be achieved with a transition operator on the Real class: Real.Resource("soc").crossesFromAbove(0.3), but the starts() operation is more general.

Windows-Based Scheduling

The concept is that all scheduling boils down to a set of windows that need an activity pattern, and a process for adding those activities if they are not present. I believe that only the following are required for a fully functional Scheduling API:

• The above Windows API
• An activity instance builder API, with the ability to create the following:
  • Individual activity instances:
    • Inputs:
      • Activity Type (duh)
      • Either the start time or end time, not both (default start = 0)
      • Parameter values, using the existing Real and Discrete classes from the Constraints API, possibly referencing Resource values.
    • Example:

      let activity = ActivityBuilder.For(ActivityType.PeelBanana)
          
          // This object would be type-checked for the specific activity type. 
          .parameters({ peelDirection: "fromTip" })
          
          // This argument only matters when multiple activities are in a pattern.
          // Default is 0 if not called.
          .start(startTime)
      
          // Alternatively provide an endTime (mutually exclusive with `start()`)
          // .end(endTime)

  • A pattern of activity instances:
    • Example:

      let activityPattern = ActivityBuilder.Pattern(
          activity1, activity2 // ... (varargs)
      )

• Some parameterization to tell the goal where to attempt to place the activity pattern.
  • This might be like Matt's PR [AERIE-1835] Start and End TimingConstraints in CoexistenceGoal #214, or just use it directly.
  • For the sake of simplicity in this RFC I just use a Placement enum, but it can be easily replaced with something more flexible.

    enum Placement {
      NearStart, // start activity as close to the window start as possible
      NearEnd // end activity as close to the window end as possible
    }

The algorithm for applying a Goal will be much simpler than before:

1. For each window, check if the activity pattern exists (we may need some tolerance in timing to account for floating-point slop)
2. If not, create a conflict for it using the placement parameter.
3. Using the same activity metadata mentioned in ForEachActivity, create MissingAssociationConflicts when appropriate.

I argue that with liberal use of the .split() operation, there should be no need to ever place more than one activity pattern in a window. Please try to think of counter-examples though, because this proposal will lose a lot of simplicity if that's not true.

Examples

Expand

Place a BiteBanana within 10 seconds of every PeelBanana:

export default (): Goal => {
    let windows = Windows.ForEachActivity(
        ActivityType.PeelBanana,
        peel => peel.end().shiftBy(0, 10)
    );
    let activity = ActivityBuilder.For(ActivityType.BiteBanana)
        .parameters({ biteSize: 1 });
    
    return Goal.From(
        windows,
        activity,
        Placement.NearStart
    )
}

Place two GrowBanana activities in every day of the "Banana Season" mission phase:

export default (): Goal => {
    let windows = Windows.All(
        Discrete.Resource("mission phase").equal("Banana Season"),
        Windows.Instant(0).repeatEvery(86400).invert().split(2)
    );
    let grow = ActivityBuilder.For(ActivityType.GrowBanana)
        .parameters({
          quantity: 1,
          growingDuration: 86400/2
        });
    
    return Goal.From(
        windows,
        grow,
        Placement.NearStart
    )
}

Place a pattern of 2 ThrowBananas after every PickBanana with quantity > 2:

export default (): Goal => {
    let windows = Windows.ForEachActivity(
        ActivityType.PickBanana,
        // This line assumes the separately-proposed change that makes parameters undefined outside of the activity bounds,
        // but not the proposed change that makes comparisons with undefined profiles return true.
        // I now think that second change was a little hasty.
        pick => pick.parameters.quantity.greaterThan(2).ends().shiftBy(0, 10)
    );
    let activityPattern = ActivityBuilder
        .Pattern(
            ActivityBuilder.For(ActivityType.ThrowBanana)
                .parameters({ speed: 10 })
                .start(0), // The absolute time doesn't matter...
            ActivityBuilder.For(ActivityType.ThrowBanana)
                .parameters({ speed: 15 })
                .start(3) // ... only that the second activity comes 3 seconds later
        );
    
    return Goal.From(
        windows,
        activityPattern,
        Placement.NearStart
    )
}

After every PickBanana, place both a ThrowBanana and a PeelBanana in one operation, but without a rigid relative time specified by a pattern.

function goalHelper(activity: ActivityBuilder): Goal {
    let windows = Windows.ForEachActivity(
        ActivityType.PickBanana,
        pick => pick.end().shiftBy(0, 10)
    );
    return Goal.From(
        windows,
        activity,
        Placement.NearStart
    );
}
export default (): Goal => {
    return Goal.All(
        goalHelper(
            ActivityBuilder.For(ActivityType.ThrowBanana)
                .parameters({ speed: 10 })
        ),
        goalHelper(
            ActivityBuilder.For(ActivityType.PeelBanana)
                .parameters({ peelDirection: "fromTip" })
        )
    );
}

Limitations

1. In a coexistence-type goal, I can't think of a clean way to allow the created activity's parameters to depend on the parameters of the existing activity that caused it.
2. In a coexistence-type goal, if you produce two non-instantaneous windows that overlap, they will be merged into one window. Then the scheduler will place only one activity, which is probably not the desired behavior.
   • great conversation about that happening here

[dyst5422]

I 100% thought this was how it worked based on our discussions. So I am 100% in agreement with making it align with this proposal as it makes the most sense to me.

Personally, fewer special concepts applied more often > more special concepts applied less often. That is, having to combine the simple concepts of windows in more complex ways is better than managing more conceptual ideas. We are essentially creating an algebra for these things and reducing it down to the simplest axiom building blocks provides for the easiest understanding of it.

[Twisol]

One of my concerns around Windows is that, originally, it was meant to capture the concept of "when is a complex condition true", not "what spans of time are available for use". The concepts separate when you consider the union of two Windows objects -- you may end up with fewer spans, because overlapping spans are coalesced. If your scheduling rules depend on spans having an identity, such as for adding an activity for each of a set of spans (even if they overlap), this coalescing is likely not what you wanted.

Conditions really "want" to have the first interpretation; a condition is all about deciding, for each time, whether the state of the world meets our condition. Whole spans don't really have an identity at this point, and the coalescing behavior is what we want.

On the other hand, typical scheduling rules seem to work in terms of spans with identity. We often want to take some action for each activity of a given type (a set of spans which may overlap!) in the same way that we often want to take some action for each contiguous span of time over which a condition is true.

While I agree with Dylan that fewer general-purpose concepts are better, I struggled (and still struggle) to see how these two interpretations can be unified while addressing all use-cases. Originally, I had hoped that a coercion (ideally implicit) would lift a condition's Windows to the collection of Spans that a scheduling rule naturally wants to operate over in general.

This would require a refactor to the Windows Java object to keep metadata about the activities that generated it.

As I recall, Windows is used by clients other than the scheduler (namely, constraints/conditions), for which this information isn't necessary. Aside from my concerns about the concept unification, can we motivate why Windows (which is already rather complex) should be expanded to include this data centrally? Would it be sufficient to define a type that contains both Windows and this activity provenance information, which is used by the scheduler only?

[JoelCourtney]

I think it could be done if we expose this difference to the author through Windows and Spans classes in the API, and allow explicitly converting between them with windows.spans() and spans.windows(). (And require that a Goal takes Spans as input.) But, this could place a lot of cognitive load on the author and it would essentially boil down to the same process, but more explicitly; and it would double the maintenance associated with operations that are valid on both Spans and Windows.

So, as an alternative to the metadata idea, here's a revision that might be less finicky:

1. Turn off coalescing for every operation except invert.
2. Add an explicit windows.coalesce() operation.
3. shorterThan/longerThan operate on non-coalesced windows, unless the author uses windows.coalesce().shortThan(...)
4. ViolationsOf automatically coalescing before producing violations.

[Twisol]

I think we've reached a point where we're both ostensibly speaking on behalf of customers. It may be good to reach out to an actual expert customer to get some ground truth on the matter.

[JoelCourtney]

Fair enough

[JoelCourtney]

To clarify though, by "hidden from the author" I didn't mean that the author should be unaware there is a difference, just that they use the same Windows object for both use cases. The Windows object itself doesn't know whether it should coalesce because it doesn't know whether it will be passed as argument to a Constraint or Goal.

[Twisol]

To clarify though, by "hidden from the author" I didn't mean that the author should be unaware there is a difference, just that they use the same Windows object for both use cases.

Fair. I'm still concerned about the cognitive overloading of using the same type for purposes that I think are quite distinct from a user's perspective.

The Windows object itself doesn't know whether it should coalesce because it doesn't know whether it will be passed as argument to a Constraint or Goal.

My position is that users always want to coalesce when describing states of affairs, and never want to coalesce when they're describing when to do what due to those states of affairs. Assigning distinct types to these distinct user activities (no relation to simulated activities 😅) assures that there is a consistent and clear divide that users can learn and rely on in general.

I want to understand what user expectations your proposed approach validates. Unfortunately, I'm somewhat lacking in imagination: it's hard for me to discount the feedback we got from customers when we originally developed conditions. Coalescing was quite important -- for instance, Clipper was working at some point on a formalization of many if not most of their flight rules in first-order logic, which entails the coalescing understanding of operations.

[JoelCourtney]

As I recall, Windows is used by clients other than the scheduler (namely, constraints/conditions), for which this information isn't necessary.

The primary motivation for attaching activity metadata to Windows is actually for constraints. Currently Constraint.ForEachActivity attaches that same metadata to Violations, so the UI can associate a violation when the activity that caused it.

[adrienmaillard]

Great work. I have a first set of questions/remarks:

• For what it’s worth, we have been facing this coalescing/non-coalescing matter when we were developing the prototype and the introduction of the non-coalescing mode made things unclear even at the code level. I’d be in favor of a different Spans structure (and their own internal consistency -> avoid two branches+set of assumptions for every operation) and an API that allows to go from one to the other explicitly.

• Your proposed changes would replace CoexistenceGoal and RecurrenceGoal quite nicely. Actually, with only the proposed changes in the Windows API, CoexistenceGoal can replace RecurrenceGoal.

• I think the activity pattern would cover the occurrence part of the CardinalityGoal as you could have some some kind of
  activityPattern.repeat(N) to repeat the same pattern and let the scheduler figure out when to schedule these. Here, I am guessing that in absence of temporal constraint, it is expected for the scheduler to look at other constraints/already present activities (etc..) and figure out how to schedule the set of activities. However, I cannot see how the duration specification of the CardinalityGoal would be covered. How would you address it ?

• About temporal constraints, you say that there should be only one per activity template. But it happens that sometimes we want the activity to start and end at specific times with regard to the reference window. And I do not see why you introduce this limitation. Could you elaborate ?

• The current ActivityExpression is kind of implementing operations from an Allen interval algebra (https://www.wikiwand.com/en/Allen%27s_interval_algebra), I think we would need that for the activity pattern.

• How is Windows.Interval() different from Windows.between() ?

[JoelCourtney]

About temporal constraints, you say that there should be only one per activity template

If it has a fixed duration or a parameterized duration, it doesn't make sense to fix both endpoints because it almost certainly can't be satisfied, right? If it has uncontrollable duration, it also seems like two endpoints could not be satisfied. In what contexts could the scheduler actually meet the demand that an activity start and end at specific times, when the duration is already determined?

Allen interval algebra

no objections from me

How is Windows.Interval() different from Windows.between() ?

It's probably not, but it needs to exist in the windows API, which it currently doesn't.

I cannot see how the duration specification of the CardinalityGoal would be covered.

I haven't had much time to think about this today, but I'll get back to you on it.

[JoelCourtney]

I can't find a Windows.between() function anywhere, so I'm not sure what you're talking about.

[Twisol]

At least on the Java side of things, that would most likely be Window.between() rather than Windows.between(). Also, I think your Windows.Instant is similar to the existing Window.at(), which gives you a one-point interval.

You still have to use new Windows(...) to wrap such an interval into the right Windows type, so even if the capability already exists in Java, there's probably value in providing more compact forms in the TypeScript DSL.

[JoelCourtney]

Revision

We had a meeting with some customers in Clipper. Problems and missing features that this RFC needs to address:

• coalescing windows as talked about above
• creating multiple instances of an activity without specifying a temporal relationship between them (i.e. in parallel not in series, so .split(n) will not be sufficient)
• specifying an activity duration requirement instead of instance existence
• only placing an activity when a certain condition is true (this is essentially the opposite problem of coalescing; if a window is split because the author doesn't want an activity placed when a certain condition is true, an extra activity will be placed.)

Coalescing Windows

The folks at clipper were supportive of the idea of separating Windows and Spans into two different objects. I didn't present my own solution of a .coalesce() operation because I didn't get around to it during the meeting, but I suppose this design decision doesn't matter to me that much, so I won't keep pushing it.

Given this decision, the ForEachActivity function should operate on Spans not Windows.

Implementation

The eDSL should have two separate classes, Windows and Spans. These two objects are easily confused because they have many similar behaviors, so it should be explicit which object is in use at all times. Constraints will be based on Windows and Goals will be based on Spans.

• Windows will have an explicit windows.spans() method, and Spans will have an explicit spans.windows() method, to convert between them.
• invert will only exist on Windows
• The Windows.All and Windows.Any functions do not translate well to spans, so I propose just having a similar Spans.Union function that does not transform the spans at all, but just combines them. Additionally, intersect does not make much sense between two Spans objects, but spans.intersect(windows) does.

Activity Builder / Pattern changes

The other three problems I think are best solved by expanding how activity patterns are constructed. The ActivityBuilder class would include the following methods:

• .For(ActivityType): constructor, must be called first
• parameters(...): specify activity parameters
• placeWhen(Windows): only place the activity during certain windows
• duration(Duration): specify a duration requirement instead of requiring a single instance
• Allen interval algebra relations:
  • e.g. .precededBy(spans) or .during(spans)
  • One and only one of these methods is required to be called.
  • specifies when to place the activity
• .then(spans => ActivityBuilder): allows a subsequent activity to be placed based on the spans of this activity
  • Can be called any number of times
  • This is essentially ForEachActivity, but for goals
  • The argument is a function because the next activity in the chain should be placed based on the spans corresponding to the current activity. Of course, the author can transform the input spans however they want.

Example

export default (): Goal => {
    let pickSpans = Spans.ForEachActivity(
        ActivityType.PickBanana,
        pick => pick.span()
    );

    // Create the goal
    return Goal.From(pickSpans)
        .then(spans => ActivityBuilder.For(ActivityType.PeelBanana)
            .parameters({/* ... */})
            .precededBy(spans)
        );
}

After each pick activity, place a peel activity and then two bite activities when the peel ends

export default (): Goal => {
    let pickSpans = Spans.ForEachActivity(
        ActivityType.PickBanana,
        pick => pick.span()
    );

    let windowsWithoutBiteBanana = Spans.ForEachActivity( // Make sure the bites are not placed at the same time
            ActivityType.BiteBanana
            bite => bite.span()
        ).windows().invert();

    // Prepare the function that generates bite banana activities, because it is reused.
    let biteActivities = peelSpans => ActivityBuilder.For(ActivityType.BiteBanana)
        .parameters({/* ... */})
        .precededBy(peelSpans)
        .placeWhen(windowsWithoutBiteBanana);

    // Create the goal
    return Goal.From(pickSpans)
        .then(spans => ActivityBuilder.For(ActivityType.PeelBanana)
            .parameters({/* ... */})
            .precededBy(spans)
            .then(biteActivities)

            // The placeWhen from above will kick in here to ensure that the second bite is placed after the first
            .then(biteActivities)
        );
}

How .then works

Unlike the original proposal, I think this revision might require changes to the solver. Once spans are calculated and its time to place activities, the scheduler will need to check which activities already exist based on the interval relations.

• activities that don't exist are created
• activities that do already exist are recorded, and should only be associated with one span

Then the scheduler will need to collect the spans associated with those activities and use them to evaluate the .then(...) method call.

This would require creating a new CreateActivitiesSpans expression node in the Windows API that is lazily evaluated with the relevant activity spans after the above steps. I think this can be accomplished similarly to how activity instance aliases are handled in the current constraints API.

Extra benefit

Adrien exposed a few unsoundness problems with scheduling in #244. One of them is that later goals in the priority order can invalidate the results of earlier goals, at best making scheduling not idempotent. Compared to other types of goals, Spans-based goals can more easily detect this behavior, because the Spans and Windows objects given to the placement relation methods and the placeWhen method can be used to determine if the goal's results did not change. Those Spans and Windows can be recomputed at the end of scheduling and compared to the Spans and Windows used to evaluate the goal. If they did not change, the goal's results would be the same.

Unfortunately, that is no longer true if the scheduler needs to automatically respect constraints.

[JoelCourtney]

Tasks

The checkboxes represent the smallest indivisible pieces of work. The top-level bullet points represent tickets.

---

• Basic Spans container
  • support for adding, removing, and flatMapping
  • support for converting to and from Windows

---

• Starts and Ends operations
  • For windows
  • For spans
• Split operation
  • For windows
  • For spans
• Spans.ForEachActivity
  • implement
• Manual creation
  • For windows
  • For spans
• LazyComputedSpans AST node (used by .then)
  • implement

---

• Preliminary ActivityBuilder implementation
  • allen interval algebra relations
  • parameters
• BasicGoal representation
  • TS API
  • JSON parsing
  • Backend class (getConflicts does nothing)

---

• BasicGoal implementation

---

• ActivityBuilder duration requirement
• ActivityBuilder placeWhen restriction