computer science//algorithms//anytime algorithm
An anytime algorithm is an algorithm that has a valid answer very early and keeps improving it for as long as it is given time, so it can be stopped at any moment and still return something usable; it is what a planner or a dispatcher runs when the deadline is set by the world rather than by the computation. Weighted A* search with a shrinking inflation factor, RRT* in motion planning, Monte Carlo tree search and a local search polishing a greedy assignment are all anytime.
An anytime algorithm is an algorithm that has a valid answer very early and keeps improving it for as long as it is given time, so it can be stopped at any moment and still return something usable; it is what a planner or a dispatcher runs when the deadline is set by the world rather than by the computation. Weighted A* search with a shrinking inflation factor, RRT* in motion planning, Monte Carlo tree search and a local search polishing a greedy assignment are all anytime.
Its quality against time is usually a concave curve: most of the improvement arrives early, and each extra second buys less. That shape gives a clean rule for when to stop. If the plan's quality grows as U(t)U(t)U(t) and every second of waiting costs ccc, because the target moves or the fire spreads, keep thinking while
dUdt>c,\frac{dU}{dt} > c,dtdU>c,
and act as soon as the marginal improvement drops below the cost of waiting. A rescue drone replanning over a flood zone stops refining its route the moment the minutes saved per second of thought fall below what the water costs per second.
A decision that arrives late is the right decision for a world that no longer exists.
An anytime method turns that into a design parameter: the answer's quality is whatever the time budget allows, and the budget is always met.
Decision runs in layers, each with its own deadline in real-time computing terms: a drone's attitude control at 1 kHz on the microcontroller, a robot's local planner at 10 to 20 Hz on its onboard computer, the global planner at about 1 Hz, the fleet's task assignment every few seconds on a server (hierarchical control). Each layer must answer within its period in the worst case, and an anytime method is how the slower layers guarantee it.
The default answer matters as much as the algorithm. If the planner has not finished, the controller keeps the last valid plan or falls back to a safe manoeuvre (stop, hold position), and designing that fallback is part of the design.
Boyd's OODA loop states the same rule for whole systems: whoever closes observe, orient, decide and act with sufficient quality faster than the environment changes wins, and the decision stage gets what is left of the budget (delay as the enemy).