Procedural Constraints + Scheduling in Typescript

[JoelCourtney]

@adrienmaillard @jmdelfa @mattdailis @camargo I summon thee.

Intro

In the effort to address Aerie’s scheduler expressiveness problems, a year ago I proposed “spans-based scheduling”. Ultimately we threw it out for a couple reasons:

• While the proposal was more expressive than what we have currently, it still had the same fundamental problem, which was that if an operation was not supported, the users had to wait for us to implement it, rather than making it themselves. The old proposal essentially provided a new (very general) operation, but it wasn’t general enough.
• Procedural scheduling does solve the expressiveness problem. Even though it might be hard to use, we decided to pursue it because spans-based scheduling only kicks the expressiveness can down the road, whereas procedural scheduling actually solves the problem.

I think that might have been a bit premature though, because we misunderstood the limitations of spans-based scheduling. The idea was to allow you to place an activity anywhere you could create a span, and to chain steps of activity creation together to enable activity groups and anchors. The limitation that killed that proposal wasn’t inherent inexpressiveness in spans-based goals, but the inexpressiveness of the constraints package in our ability to create spans.

On the other hand, spans-based scheduling had one massive advantage over procedural scheduling: ease of implementation. It seemed like our two main options for procedural scheduling were both terrible:

• Expose the backend to the user. This would require a new (and complicated) execution pipeline that might have to interleave with the old pipeline. And would require cleaning up the scheduler and constraints data structures in major ways to make them user-friendly.
• Re-implement the scheduler backend (and constraints backend) in typescript. Absolutely not going to happen.

But I present the following Math^TM:

procedural constraints + spans based scheduling = procedural scheduling

I’ll try to justify that in a bit. The point is that we can implement truly procedural scheduling - in typescript, to maintain integration with the eDSL - without re-implementing the scheduler itself. We need to re-implement “only” the constraints package in typescript, which is not a small task, but is orders of magnitude simpler.

Procedural Constraints

Procedural Constraints are actually a separate problem that we will need to solve at some point anyway. Constraints have the exact same expressiveness problem as the scheduler; we regularly get requests for help with constraints that are either impossible or ludicrously complicated to implement in the current system, and they have to wait for us to make the necessary updates every time.

It is also a requirement for every design we have for procedural scheduling. So to me it seems just as important as the scheduler; we just don’t focus on it because Clipper has much more complex and pressing needs for the scheduler. So let’s just focus on constraints for a minute.

It would be the easiest transition for the user if they could take their existing profiles and spans objects in the eDSL and just pull out the segments so they could do their own operations on them, and not have to change their constraints at all during the migration. Here’s what that would look like:

1. Refactor the existing eDSL classes (Windows, Real, Discrete, Spans, ActivityInstance) to actually contain their data, and perform the operations on it instead of generating an AST. This would require translating all the procedural operations from the backend into the eDSL. (Fair amount of work, but none of it is particularly difficult. I’ve been prototyping this, and did about half of it in the last week.)
2. Have the [profile].Resource(…) functions actually query the profiles directly from the database. Same deal for activity instances.
3. Return the concrete violations to merlin, and forward that response to the UI.
4. All constraint files would be loaded and executed together; this is to allow the database adapter to cache resources for reuse between constraints, and brings us one step closer to code sharing between constraints.
5. Provide a .collect() function on the profiles/spans objects which produces the segments or spans for the author to use. Expose the lower-level .map, .map2, and .filter functions we already have to allow custom operations without even unwrapping the data.
6. The only things the user would do to migrate are make their constraint function async and add an import statement, which are pretty brainless changes. Everything else is drop-in.

Long term, there are some operations that only exist because of the declarative context, and could slowly be deprecated and replaced with more idiomatic procedural operations (looking at you, ForEachActivity).

Example

Let’s look at a simple operation that doesn’t exist in the eDSL: squaring a piece-wise constant real resource. Currently, the only way you can do that is by squaring it in the mission model and emitting a second resource just for your constraint. The constraint would look like this:

export default (): Constraint => {
	return Real.Resource(“custom squared resource”).lessThan(someOtherProfile);
}

If we implemented procedural constraints in typescript, they would have two options for how to do this:

import * from “aerie-timeline”;

// Helper functions

// OPTION 1: Manually transforming an array of segments
export async function square(real: Real, bounds: Interval): Real {
	let segments = await real.collect(bounds); // Segment<LinearEquation>[]
	let squared = segments.map(segment => {
		let interval = segment.interval;
		let eq = segment.value;
		if (eq.rate !== 0) throw new Error(“cannot square a non-constant linear equation”);
		return new Segment(interval, new LinearEquation(eq.initialTime, eq.initialValue ** 2, 0));
	};
	return new Real(bound(squared));
}

// OPTION 2: Use the provided mapValues function
// Note the bounds aren’t required for this option.
export function square(real: Real): Real {
	return real.mapValues(segment => {
		let eq = segment.value;
		if (eq.rate !== 0) throw new Error(“cannot square a non-constant linear equation”);
		return new LinearEquation(eq.initialTime, eq.initialValue ** 2, 0);
	}
}

// Main constraint function

export default async (bounds: Interval): Constraint => {

	// USING OPTION 1
	let squared = await square(Real.Resource(“original resource”), bounds);

	// USING OPTION 2
	let squared = square(Real.Resource(“original resource”));

	return squared.lessThan(someOtherProfile);
}

I exported the square function. That’s because all these constraints would be loaded and executed in the same workspace; if we add the ability to set file names, we could let other constraints import this function and use it. (This is already the case, but if they start implementing truly novel operators the demand for the feature will increase.) Theoretically they could even workaround the current lack of code-sharing by extending the Real class prototype, but uhh….let’s not encourage that.

Again, for constraints that work good enough in the current system and don’t have a use for procedural constraints, the only necessary changes are that the import statement and the async keyword, which are both brainless changes. The bounds argument in the function signature is optional; they don’t have to add it if they don’t need it.

Spans-based scheduling is just procedural scheduling with a fake mustache

In my old proposal I came up with a callback-chaining design I called "spans-based scheduling". I've realized that it is actually equivalent to procedural scheduling, so I'm going to stop using that old name. It was intended to allow this pattern:

1. Calculate a set of spans with the constraints package, using simulation data as input
2. Require the existence of a particular activity in each span
3. Some activities will be created
4. Receive references to either the new-created activities, or to all relevant activities including pre-existing ones that satisfied the condition
5. Provide a callback that recurses back to step 1, using the provided activities as additional input.

That looks a lot like procedural scheduling. It didn’t look very procedural at first, because the original proposal used a very declarative-looking syntax and relied on declarative constraints. But if we modernize that algorithm a little bit to have the goal operate on missing activity instance conflicts instead of spans, then I’d argue it actually is procedural scheduling. And if we modernize the interface to be defined by a generator, I think it’s undeniable. Here’s an example with a hypothetical syntax:

import * from ‘aerie-timeline’;

// the * in the signature makes this function a generator
export default async function* (bounds: Interval) {

	// STEP 1
	// We have access to all sim results due to procedural constraints.
	// Create some conflicts however you want.
	// They don’t have to all be the same activity type
	let myConflicts = /* some calculation using resources, activity instances, etc. */;
	
	// STEP 2
	yield* myConflicts;

	// STEPS 3 AND 4
	// yielding a `Schedule` object cedes control to the scheduler.
	// `Schedule.Created` indicates to only return created activities. (Alternatively `Schedule.All`)
	// `Schedule.Instances` indicates to resimulate and return the instances, instead of directives. This invalidates cached resources in the worker. (Alternatively `Schedule.Directives`)
	let newActivityInstances = yield new Schedule(Schedule.Created, Schedule.Instances);

	// STEP 5 - Generators are a way to flatten callbacks into a single function.
	// Do it again!
	let someMoreConflicts = /* calculate whatever */;

	yield* someMoreConflicts;

	newActivityInstances = yield new Schedule(…);

	// etc

	// the last batch of activities will be scheduled by the driver automatically when the generator exits.
}

This solution would be tricky, but small:

1. The eDSL main would need to detect if the goal function is a generator and hand it off to a procedural goal driver.
2. The driver would return an AST node containing an ID unique to the driver, and remain waiting.
3. Tricky part! A ProceduralGoal type in the scheduler backend would need to be able to cede control back and forth with node, provide multiple sets of conflicts to the solver, and request resimulations. From the user perspective, the yield new Schedule(...) would look like an RPC.

As an aside, I think it would be good to create a fourth goal type, SimpleGoal or BasicGoal or something like that, which is just a container for conflicts to be passed to the scheduler. The user would create the conflicts themselves, and the scheduler would solve them. Even if we never implement the full procedural scheduling design above, this could be a big improvement in expressiveness when combined with procedural constraints.

With SimpleGoal in mind, the exact role of the procedural goal driver becomes more clear: the yielding of concrete conflicts is just syntactic sugar for aggregation into a SimpleGoal, and the driver only serves as an iteration tool that delegates to other goals. So lets define the driver's purpose as such:

1. delegate to another goal - any of the 4 eDSL goals
2. evaluate it and get the new activities
3. repeat

Application to current scheduler problems

Activity Groups:

Procedural goals don’t need to produce activities of all the same type, and by allowing the goal to resume after the schedule request and produce more activities, it can produce a structure of related activities.

Anchoring:

Anchoring is not fully addressed by this proposal, but it gets us halfway there: with access to the concrete activity instances in the plan, all we need to do is extend the conflicts to allow anchoring.

Advanced Linkage:

This is where goal delegation comes in. If the above example code essentially delegates to a SimpleGoal, why not delegate to a more complex goal? To take the linkage example from Juan's presentation, the procedure could look like this:

import * from ‘aerie-timeline’;

export default async function* () {
        // Delegate!
	yield new CardinalityGoal(…);

        // Get the new activity directives created by the cardinality goal
	let newActivities = yield new Schedule(Schedule.Created, Schedule.Directive);

	let specificGnc = /* pick the desired instance out of newActivities */;

	let solarArrayFix = new MissingActivityInstanceConflict(/* new activity anchored to specificGnc */);
	
	yield solarArrayFix;
}

Proposed implementation plan

1. Temporarily disconnect the constraints and scheduler typescript packages. (Hard copy the constraints eDSL as-is into the scheduler, so the constraints package can be changed independently.)
2. Implement procedural constraints in typescript, without touching the portion of scheduling that delegates to constraints.
3. Update the scheduler eDSL to work with procedural constraints and re-merge the packages.
4. Implement SimpleGoal.
5. Implement the procedural driver.

Pros of this approach

• This constraints design is a near drop-in replacement only requiring a couple minor changes.
• This constraints design does not require two evaluation pipelines for declarative / procedural constraints, because it secretly converts all constraints to procedural.
• Allows us to completely nuke the constraints AST system in step 3 - massive reduction in complexity.
• Allows us to distribute the constraints package as a legit NPM package, which would let customers use the machinery we’ve made for operating on profiles in other contexts.
• Removing the split between eDSL and backend for constraints provides a clean pathway for users’ custom operators to be adopted into the package: if they get a lot of use out of a well-written custom operator, we can just assimilate their code as-is.
• I think the generator workflow for this procedural goal design is intuitive and clean. Generators are dope.
• Solves activity groups with no additional work. Anchoring and linkage are on the horizon.
• Don’t have to refactor the scheduler backend to make it more user-friendly.

Cons of this approach

• Reimplementing the constraints package (for the nth time) in typescript (but not an overwhelming amount of work; I’ve already prototyped a good chunk).
• We could only delete the constraints eDSL and backend AST/parsers, not the backend Profiles classes themselves. This is because a) the scheduling goals often perform windows operations internally and b) we still need a container to represent the results returned from typescript.
• Procedural goal driver control flow would be tricky.
• No custom scheduler solvers (but I’d argue that was feature creep anyway).
• I’m not sure if the iterative nature of the procedural goal could integrate well with a satisficing scheduler.

[JoelCourtney]

@mattdailis There's no mention of profile streaming in procedural constraints because I dropped that feature from my prototype. It is still possible though.

[JoelCourtney]

I edited the main post to include goal delegation (enabling linkage) as part of the MVP.

[jmdelfa]

I think the procedural scheduling proposal is parallel in nature to Clipper requests as they address different aspects. Procedural scheduling is a generic instrument to allow the users to do what vanilla Aerie cannot do, at least in an easy way. On the other hand, the different features discussed with Clipper team such as grouping, advanced anchoring and activity linkage, are fundamental capabilities (to any mission, not only for Clipper) that should be inherent to Aerie and easy to model (this point was emphasized a number of times by Clipper team).

I would suggest to start designing/implementing these capabilities (Clipper highlighted them as high priority). That will benefit not only Clipper, but can also be used by procedural constraints/scheduling.

[jmdelfa]

Very positive conversation with Joel. I recap below the main outcome:

• We agreed on proceeding forward with the implementation of anchoring, grouping and linkage as discussed in the Scheduling TODO's presentation. There will be a design phase for each of these topics. Besides sw engineering, ease of use should be a key point when designing the different capabilities. In the particular case of grouping, which is probably the most complex feature, the proposed way forward (pending discussion during design phase) is to implement them using HTN (Hierarchical Task Networks) which provides the user with so-called methods to define complex goals in terms of other complex goals and primitive activities plus (partial) relations (temporal or parametric) among them. The main benefit of HTNs is that they allow to handle complexity and allow reuse methods as templates to achieve complex goals.
• Another important point touched is the role of procedural scheduling. We share the view that Aerie should sustain a continuous effort to improve/increase expressiveness in the built-in scheduler for those functionalities that represent core building blocks for any mission (e.g. grouping). At the same time, procedural scheduling is a fundamental capability that should be farther developed to enable the user to model any custom mission-need that vanilla Aerie cannot model, at least in an easy way.
• I will proceed to schedule the first meeting to start discussing anchoring at the earliest available window