Imagine four blocks sitting in a row on a slippery table, joined to each other by springs, with the two end blocks also attached by springs to walls. Give one a poke and the whole chain starts jiggling back and forth. Now add three little motors, one between each neighbouring pair of blocks, that can push them apart or pull them together. And just to make life interesting, every so often a random shove knocks the blocks around.
Your job is to keep the chain calm, and keep every block within a safe zone around its resting spot.
Now imagine doing that for a thousand chains at once.
The jiggling-blocks system
This setup comes from a well-known 2010 research paper by Yang Wang and Stephen Boyd, and it’s become a standard test for control methods. The rules are:
- Each motor has a strength limit. It can only push or pull so hard.
- Each block should stay within a safe zone around its resting position.
- We want the blocks to settle down without the motors working harder than necessary.
Thinking ahead: model predictive control
How do you decide what the motors should do? One of the most powerful approaches is called model predictive control, or MPC.
MPC works a lot like a good chess player:
- Look at the board. Measure where every block is and how fast it’s moving.
- Think several moves ahead. Using a model of how springs and blocks behave, plan the best sequence of motor pushes for the next 15 steps (about seven and a half seconds).
- Make only the first move. Apply the first push in the plan.
- Look again and re-plan. The world never goes exactly as predicted (those random shoves!), so throw the old plan away and make a fresh one from the new position.
This loop of plan, act, re-plan makes MPC both clever and adaptable. It’s used in self-driving cars, chemical plants, robots, drones and even some heating systems.
Each plan is a small optimisation puzzle called a quadratic program, with 105 numbers to choose and 120 rules to obey.
Soft walls instead of hard ones
There’s a subtle problem. Sometimes a random shove knocks a block so hard that no plan, however clever, can keep it inside its safe zone. If the rules said “the block must stay inside, no exceptions”, the puzzle would have no solution and the controller would be stuck.
So the safe zones are made soft. A block is allowed to stray outside, but the plan pays a hefty fine for every bit it goes over. The fine is large enough that whenever staying inside is possible, the plan does exactly that. It’s only when there’s no other choice that a block is allowed to go a little over, and even then the plan does its best to bring it back.
The motor limits, on the other hand, stay hard. A motor physically can’t push harder than its maximum, so the plan is never allowed to ask it to.
One at a time versus all together
A single one of these puzzles is tiny. A good solver running on an ordinary computer processor (CPU) can crack one in well under a thousandth of a second. That’s very hard to beat.
But we don’t have one system. We have a thousand, each starting from its own random position and getting its own random shoves. At every step, we need a thousand fresh plans.
Here’s where the two approaches differ:
- The one-at-a-time approach solves the thousand puzzles one after another, using a well-known solver called SCS. It’s a bit like a single brilliant runner delivering a thousand letters, one trip at a time.
- The all-together approach uses Jaddle on a graphics card (GPU). All thousand chains have the same springs, motors and rules; only their positions differ. So Jaddle solves all thousand puzzles side by side, in lockstep, like a marching band where every musician takes the same step at the same time.
Both approaches use a warm start: each new plan begins from the previous step’s plan, shifted forward by one step. Since the world hasn’t changed much in half a second, the old plan is usually a great starting guess.
And the winner is…
It depends on how many systems you have, which is the most interesting part of the whole example.
- One system: the one-at-a-time solver wins. A single tiny puzzle leaves a GPU almost entirely idle; it spends most of its time just getting started.
- Tens of systems: the batched approach catches up.
- A thousand systems: the batched approach on a laptop GPU spends about one-fortieth as long per puzzle as the one-at-a-time solver, and its plans are slightly more accurate too. Even running the batched approach on an ordinary CPU, it’s about three times faster than looping.
- Ten thousand systems: something new happens…
The slowest member of the band
Remember the marching band? The band only finishes when its slowest member finishes. In a fleet of ten thousand, there are always a few chains in a tricky spot, perhaps just shoved past the edge of their safe zone, and their puzzles take longer to solve. Everyone else ends up waiting for them.
The fix is something every real controller needs anyway: a deadline. We give the solver a fixed amount of effort per step. Any system that hasn’t fully finished by then simply uses the best plan it has so far. Because Jaddle always keeps its answers within the motor limits as it works, even an unfinished plan never asks a motor to do the impossible.
With a deadline in place, the time per puzzle for ten thousand systems drops back down near its best.
Do they agree?
Speed is no use if the answers are wrong. So we check both approaches against a reference answer solved to extremely high accuracy. Both are close, and over the whole run, the two fleets end up with nearly identical total costs. The blocks stay calm, the motors stay within their limits, and the chains settle down in both cases.
The takeaway
This example isn’t saying “always use a GPU”. If you’re controlling one robot and need an answer within a strict fraction of a millisecond, a traditional CPU solver is still the right tool.
But a surprising number of real problems involve lots of similar decisions at once: a fleet of delivery robots, a wind farm full of turbines, or testing one controller against thousands of possible futures to see how it copes. In those cases, it’s worth asking the marching-band question: could all of these take the same step together? When the answer is yes, solving them side by side can be dramatically faster than solving them one at a time.