A planner is only as good as its picture of the world, and the picture arrives as telemetry: an obstacle moved, a task finished, latency climbed. These figures compute the four pieces of the problem: keeping a route current as the map changes, sharing a space between agents, ordering dependent work, and deciding from the numbers when a plan has gone stale.
A* orders its open list by
f(n) = g(n) + h(n)where g is the cost from the start and h an estimate of the cost to the goal. On a 4-connected grid with unit steps the Manhattan distance
h(n) = |x_n - x_g| + |y_n - y_g|never overestimates, so the first path found is optimal; it is also consistent, h(n) \le c(n, n') + h(n'), so no node is expanded twice. With h = 0 the same loop is Dijkstra's algorithm and expands far more. The cost of A* is that each map change throws all of that work away.
D* Lite (Koenig & Likhachev 2002) searches from the goal and keeps two values per cell: g, the cost-to-goal it has committed to, and a one-step lookahead
\mathrm{rhs}(s) = \min_{s' \in \mathrm{Succ}(s)} \big( c(s, s') + g(s') \big)A cell is consistent when the two agree. The queue is ordered by the key
k(s) = \big[\, \min(g, \mathrm{rhs}) + h(s_{\text{start}}, s) + k_m,\;\; \min(g, \mathrm{rhs}) \,\big]and when the map changes only the cells whose edge costs changed are made inconsistent and re-queued; the search repairs the cost field outward from them and stops as soon as the start is consistent. The term k_m accumulates the heuristic drift as the agent moves so old keys stay valid. The figure's expansion counts are this economy measured.
Cooperative A* (Silver 2005) plans each agent in turn over states (x, y, t) with the moves of the grid plus a wait, unit cost per step, and a reservation table that earlier agents have filled:
\mathrm{Succ}(x, y, t) = \{ (x', y', t+1) : (x', y') \in N(x, y) \cup \{(x, y)\},\; (x', y', t+1) \notin \mathcal{R},\; (x', y') \to (x, y) \text{ at } t \notin \mathcal{R} \}The second exclusion is the swap: two agents may not cross the same edge in opposite directions in the same step. The heuristic is the true grid distance to the goal from a breadth-first pass, which ignores other agents and is therefore admissible.
Later agents plan around earlier ones, so the sum of costs is at least the sum of the independent shortest paths, and the difference is the price of coordination, paid mostly in wait steps. The figure counts both.
The order in which agents plan changes the result; a fixed order can leave a late agent with no feasible path within the horizon. Conflict-based search (Sharon et al. 2015) removes the dependence on order at a higher computational cost, and priority schemes in between are an active area. Switching Reservations off in the figure shows the alternative: independent shortest paths and the collisions they produce.
Repeatedly take a task with no unplaced predecessors, place it, and decrement the in-degree of its successors. Every task is placed exactly once and every edge is examined exactly once, so the running time is
O(|V| + |E|)If the queue empties before every task is placed, the remaining tasks lie on or downstream of a cycle, and no order exists. The figure reports exactly those tasks. The layer of a task, the length of the longest chain of predecessors above it, gives the column layout.
With durations d_v, a forward pass over the topological order gives the earliest times,
\mathrm{ES}(v) = \max_{u \to v} \mathrm{EF}(u), \qquad \mathrm{EF}(v) = \mathrm{ES}(v) + d_vand a backward pass the latest times and the slack,
\mathrm{LF}(v) = \min_{v \to w} \mathrm{LS}(w), \qquad \text{slack}(v) = \mathrm{LS}(v) - \mathrm{ES}(v)Zero-slack tasks form the critical path; its length is the makespan with unlimited workers, and no schedule beats it. With W workers the figure's list scheduler comes within a factor of 2 - 1/W of optimal (Graham 1969); the gap between its makespan and the critical-path bound is visible in the Gantt strip.
e_t = \lambda x_t + (1 - \lambda)\, e_{t-1}A one-pole low-pass filter with memory of about 1/\lambda samples. It tracks the level with almost no state, which is why it is the default in telemetry pipelines, and why on its own it cannot say whether a rise is noise or a shift: it only follows.
Page's cumulative sum (1954) accumulates standardised excursions on each side of the baseline, minus an allowance k:
S^+_t = \max\big(0,\; S^+_{t-1} + z_t - k\big), \qquad S^-_t = \max\big(0,\; S^-_{t-1} - z_t - k\big), \qquad z_t = \frac{x_t - \mu_0}{\sigma}An alarm fires when either sum crosses h. Because the figure's latency is autocorrelated, it feeds the sums the one-step AR(1) prediction residuals rather than the raw deviations; a CUSUM on correlated samples alarms far too often, and the residuals are white under the baseline model (Alwan & Roberts 1988). With k set to half the shift one wants to catch, in units of \sigma, the detector is the likelihood-ratio test for that shift, and h sets the trade between false alarms and detection delay: the average run length to a false alarm grows roughly as e^{2kh} while the delay after a true shift grows only linearly in h. The figure lets the reader move both and watch the delay it measures.
The Constellation router is the part of the platform that does dispatch: six registered lanes, planner, critic, retriever, executor, memory and verifier, contribute to arbiter rounds, and a depth ladder raises the consensus floor as a round escalates. It is described, with figures that run the deployed escalation and release rules, at /research/constillation.
The lab's own work queue is a ticket backlog on the live feed, created and updated by the agents and closed by an administrator. Neither system runs a grid search; what they share with this page is the shape of the problem: work arriving as events, dependencies between tasks, several agents on shared resources, and the question of when a plan should be redone.
The figures are the planning primitives in isolation, each with its cost measured. Incremental repair is the D* Lite lesson: recompute only what an update invalidated. Reservations are the cooperative-A* lesson: agents that publish their intended use of a shared resource do not collide on it. Kahn's ordering and the critical path are how a dependent workload gets its schedule and its bound. The CUSUM is the smallest detector that tells drift from a shift.
Carrying them into the router means replacing grid cells with lanes and model calls, and path cost with latency and token spend. The mathematics does not change.
A grid with four moves has no turning radius, no velocity and no smoothness. Lattice planners with motion primitives and sampling planners such as RRT* handle those; D* Lite carries over to any graph, but the graph is then far larger.
The figure's obstacles are known exactly once reported. Real telemetry is late and noisy, so the cost of a cell is a distribution and the planner should weigh the risk of a blocked route against its length. Planning in occupancy probabilities rather than binary cells is the usual compromise.
Cooperative A* is complete only for a given priority order. When it fails for one agent the fix is to reorder, or to move to conflict-based search, whose worst case is exponential in the number of conflicts.
The CUSUM assumes a known \mu_0 and \sigma. Services have daily cycles and slow trends, so both must be estimated on a moving window, and a detector re-baselined after every alarm will follow a slow enough drift without ever alarming. Seasonal models or a second, slower CUSUM are the standard answers.