In this page
Scenario Search
A single scenario answers what if?. Many scenarios answer what is best?. Because an overlay world is created instantly and stores only what it changes, a server can fork a world for every candidate solution, evaluate all of them in parallel with the real models on the real data, and keep only the good ones. Worlds become the base of a search engine.
┌──────────── generation g ────────────┐
plans ──►│ fork 1 world per plan (overlay) │
│ evaluate each plan in its world │──► scores
│ (spawn, Job.world, in parallel) │
└──────────────────────────────────────┘
│
Pareto front of all scores
│ │
keep its worlds remove the others
│
mutate the front ──► plans of generation g+1
At the end, the worlds left are the Pareto front: the candidates that no other candidate beats on every objective. Each of them is a complete scenario that users can open, explore and diff against reality.
The orchestrator can be any algorithm: a grid over a few parameters, random sampling, a genetic algorithm, a Bayesian optimiser. The example below is a small genetic algorithm.
Candidates and scores
A candidate is the set of parameters the search changes. Here, a fishing trip plan for the vessel of the running example: the transit speed to the fishing zone, and the hours of trawling once there. Two objectives: burn less fuel, catch more fish.
/// One candidate plan: the genome the search mutates.
type Plan {
/// transit speed to the fishing zone, knots
speed: float;
/// hours of trawling once there
trawl: float;
}
/// What a plan achieves, computed in its world.
type Score {
world: String;
plan: Plan;
/// litres burnt over the horizon
fuel: float;
/// tonnes caught
catch: float;
}
Evaluating a candidate in its world
evaluate runs in the candidate’s world. It writes the 12 hours the plan predicts into the vessel’s series, then scores them. In a real project this is where the models run (see Simulation):
/// Runs in the candidate's world: writes the 12 hours the plan predicts, then scores them.
fn evaluate(p: Plan): Score {
var v = vessels.get("trawler")!!;
var now = v.speed.lastTime()!!;
var transit = 40.0 / p.speed; // hours to reach the zone, 40 nm away
var fuel = 0.0;
var trawled = 0.0;
for (var h = 1; h <= 12; h++) {
var speed = 0.0;
var rate = 40.0; // idle
if (h <= transit) {
speed = p.speed;
rate = 300.0 * (speed / 10.0) * (speed / 10.0);
} else if (trawled < p.trawl) {
speed = 3.5;
rate = 260.0;
trawled = trawled + 1.0;
}
v.speed.setAt(now + h * 1hour, speed);
v.fuel_rate.setAt(now + h * 1hour, rate);
fuel = fuel + rate;
}
return Score { world: World::current(), plan: p, fuel: fuel, catch: trawled * 0.8 };
}
Collecting the results
The orchestrator runs in main. It forks one overlay world per plan and spawns evaluate in each with Job.world. A task cannot read another world, and await jobs all run in the awaiting task’s world, so the orchestrator waits for the spawned tasks and reads what they returned. The result of a spawned task is stored in files/<user>/tasks/<task_id>/result.gcb:
/// Forks one overlay world per plan, evaluates every plan in its own world in parallel, and returns the scores.
fn evaluate_all(plans: Array<Plan>, generation: int): Array<Score> {
var ids = Array<int> {};
for (i, p in plans) {
var name = "gen${generation}-${i}";
World::create(name, WorldMode::overlay, "main");
ids.add(spawn(Job { function: evaluate, arguments: [p], world: name }));
}
for (_, id in ids) {
while (Task::is_running(id)) {
Runtime::sleep(10ms);
}
}
var scores = Array<Score> {};
for (_, t in Task::tasks(ids)) {
var result = GcbReader<Score> { path: "files/${t!!.user_name}/tasks/${t!!.task_id}/result.gcb" };
scores.add(result.read());
}
return scores;
}
The evaluations run in parallel on the worker pool. The orchestrator itself holds a worker while it waits: size the pool (--workers, --workers_large) so that evaluations still have workers to run on, and choose the class each evaluation runs in with Job.task_class.
Keeping the Pareto front
A score dominates another when it is no worse on every objective and better on one. The front is the set of scores no other score dominates. To keep the number of kept worlds bounded, the function keeps at most max of them, spread along the front:
/// `a` is no worse than `b` on both objectives, and better on one.
fn dominates(a: Score, b: Score): bool {
return a.fuel <= b.fuel && a.catch >= b.catch && (a.fuel < b.fuel || a.catch > b.catch);
}
/// The scores no other score dominates, at most `max` of them, spread along the front.
fn pareto(scores: Array<Score>, max: int): Array<Score> {
var front = Array<Score> {};
for (_, s in scores) {
var dominated = false;
for (_, o in scores) {
if (dominates(o, s)) {
dominated = true;
break;
}
}
if (!dominated) {
front.add(s);
}
}
front.sort_by(Score::fuel, SortOrder::asc);
if (front.size() <= max) {
return front;
}
var spread = Array<Score> {};
for (var i = 0; i < max; i++) {
spread.add(front.get(i * (front.size() - 1) / (max - 1)));
}
return spread;
}
The genetic loop
Each generation evaluates new plans, merges their scores with the current front, keeps the new front and removes the worlds of every other candidate. The next generation mutates plans of the front:
fn mutate(p: Plan, rnd: Random): Plan {
return Plan {
speed: max(6.0, min(13.0, p.speed + rnd.normal(0.0, 1.0))),
trawl: max(0.0, min(10.0, p.trawl + rnd.normal(0.0, 1.5))),
};
}
@expose
fn search(): Array<Score> {
var rnd = Random { seed: 42 };
var plans = Array<Plan> {};
for (var i = 0; i < 16; i++) {
plans.add(Plan { speed: rnd.uniformf(6.0, 13.0), trawl: rnd.uniformf(0.0, 10.0) });
}
var front = Array<Score> {};
for (var g = 0; g < 5; g++) {
var all = evaluate_all(plans, g);
all.add_all(front);
var next = pareto(all, 5);
var kept = Map<String, bool> {};
for (_, s in next) {
kept.set(s.world, true);
}
for (_, s in all) {
if (kept.get(s.world) == null) {
World::remove(s.world);
}
}
front = next;
plans = Array<Plan> {};
for (var i = 0; i < 16; i++) {
plans.add(mutate(front.get(rnd.uniform(0, front.size())).plan, rnd));
}
}
return front;
}
After 5 generations of 16 candidates, 80 worlds were created and evaluated, and only the 5 worlds of the front remain:
curl -X POST -d '[]' http://localhost:8080/project::search
# [{"world":"gen4-0", "plan":{"speed":6.0,"trawl":0.0}, "fuel":888.0, "catch":0.0},
# {"world":"gen4-12","plan":{"speed":6.0,"trawl":0.01}, "fuel":1108.0,"catch":0.8},
# {"world":"gen2-14","plan":{"speed":6.0,"trawl":1.02}, "fuel":1328.0,"catch":1.6},
# {"world":"gen2-11","plan":{"speed":6.0,"trawl":3.45}, "fuel":1768.0,"catch":3.2},
# {"world":"gen2-6", "plan":{"speed":10.64,"trawl":10.0},"fuel":3359.7,"catch":7.2}]
curl -X POST -d '[]' http://localhost:8080/runtime::World::list
# gen2-6, gen2-11, gen2-14, gen4-0, gen4-12
Each kept world holds the complete predicted trip of its plan. A user opens gen2-11 with the world: gen2-11 header and sees the vessel’s predicted speed and fuel curves in the usual dashboards, and the World Diff tells exactly what this candidate changes compared with the real data.
Search in practice
- Remove what you do not keep. A search creates many worlds. Remove the losers as soon as they are scored, and the front of the previous run before the next one, or
World::reseta fixed pool of worlds instead of creating new ones. - Fork from a stable base. Candidates are forked from main, or from one snapshot taken when the search starts, so that every candidate starts from the same state.
- Constraints. A candidate that breaks a hard limit (a stability margin, a quota, an arrival time) gets a score that is dominated by everything, or is removed before the front is computed.
- Diversity. A front can hold many nearly identical candidates. Keep the ones that differ the most, as
paretodoes by spreading along the fuel axis, so that users get real alternatives. - Budget. The number of worlds per generation and the number of generations follow from the time one evaluation takes and the number of workers. Measure one evaluation first.
- Periodic search. Schedule the search with
Scheduler::addto re-run it as new data arrives, every 15 minutes for instance.