A planning problem supplies an initial state, a goal and ground actions with preconditions and effects. PDDL2.1 enlarges this setting with durative actions, numerical quantities and plan metrics. A useful solution may therefore need more than logical correctness. It may have to finish early, consume little fuel, or balance several costs.

Forward state-space search represents a node by what is true after a prefix. LPG instead represents a node by a structured proposal for the whole plan. Some required facts may lack producers. Some actions may interfere. The proposal is still valuable because its defects point directly towards neighbouring proposals.

The underlying procedure, Walkplan, belongs to the family of stochastic local-search methods exemplified by Walksat. Choose an inconsistency in the current graph. Construct graph modifications that can resolve it. Usually take a minimum-evaluation modification; sometimes take a random one. Repeat until no inconsistency remains or a search bound triggers a restart.

This shift makes a powerful division of labour possible. Logical structure identifies what is broken. Reachability analysis estimates how hard each repair will be. Temporal propagation predicts when the altered plan will finish. A plan metric supplies the user’s notion of quality. Stochasticity helps the search leave local basins where greedy repair cycles.

The resulting planner is incremental and anytime. It can be configured to favour the first solution, as LPG-speed was, or continue after validity and seek lower-cost plans, as LPG-quality did. The first valid graph is not the end of deliberation; it becomes an incumbent against which later candidates are judged.

A planning graph contains fact levels and action levels. Preconditions connect facts to actions; add and delete edges connect actions to later facts. A no-op action carries a fact forward. Mutex relations mark action pairs that cannot coexist because they interfere, have inconsistent effects, or depend on mutually exclusive facts.

An action graph selects a subgraph. LPG’s linear variant permits at most one non-no-op action at each action level, while no-ops maintain facts across levels. “Linear” does not mean the final execution must be serial. It gives implementation and heuristic calculations a total level order; independent actions can later overlap when temporal constraints allow it.

The restriction simplifies propagation. At any level the planner can derive a definite logical state from earlier selected actions. It can find unsupported preconditions, maintain numerical values and trace which action supports which later need. Persistent mutex actions occupy different levels, eliminating ambiguity about their order.

An LA-graph is a solution graph when all preconditions of its actions and all goals at the final level are supported, and when the selected actions satisfy the relevant consistency conditions. Before that point, its unsupported fact nodes are the local-search inconsistencies. A dashed chain of no-ops can be blocked by an action that deletes the carried fact, turning a formerly supported precondition into a new flaw.

The graph may be longer than a more compact parallel action graph because each level holds only one ordinary action. The authors report that this representation size was not a problem in their tests. That observation is empirical, not a bound: domains with very long plans or enormous grounded action sets can still challenge memory and update cost.

The ordering set has two sources. A causal constraint a ≺_C b records that action a provides a fact consumed by b. An exclusion constraint a ≺_E b orders mutually exclusive actions. LPG directs a mutex ordering according to graph level: the action in the earlier level precedes the action in the later one.

For the paper’s main presentation, an ordering means that the first action ends before the second begins. A fact’s temporal value is the earliest time it becomes true, computed from its supporters. An action’s temporal value is its earliest completion: its duration plus the maximum among the times of supported preconditions and actions constrained to precede it.

Unsupported facts have undefined times. Once an insertion or removal changes the graph, LPG revises affected temporal values by forward propagation rather than recomputing everything blindly. The makespan of a valid temporal solution follows from the latest required completion time.

This representation separates two notions often collapsed in diagrams. Level order is a topological scaffold. Temporal order is a set of semantic constraints. Actions at different levels may overlap if neither causality nor exclusion forbids it. The competition version conservatively prevented any pair of mutex actions from overlapping; later work refined endpoint constraints and improved makespan by about ten per cent on reported Satellite SimpleTime tests.

PDDL2.1 also distinguishes conditions at start, over all and at end, and effects at start or end. The implementation adjusts temporal propagation for these endpoints. The paper explains the major cases while acknowledging that the competition treatment could over-constrain some overlaps. Soundness of an ordering does not guarantee temporal optimality.

Suppose precondition fact f of action b is unsupported at level k. An insertion neighbour adds an action a whose effect can support f at an admissible earlier level. No-op propagation connects the new effect to the need. The move may create fresh unsupported preconditions for a or introduce mutex interference, but it removes the selected defect.

A removal neighbour deletes b, the action that requires f. This also resolves the selected unsupported precondition because the requirement disappears. Removal can delete support needed by later actions and can therefore create different flaws. The search is allowed to exchange one set of inconsistencies for another when the evaluation predicts progress.

When a goal fact is unsupported, there is no consumer action to remove in the ordinary sense; insertion of a producer is the meaningful family. Candidate generation respects reachability and mutex information so that plainly impossible repairs can be excluded or penalised.

Walkplan selects an inconsistency, constructs the relevant neighbourhood and evaluates its members. A greedily best neighbour is chosen most of the time, with random tie-breaking among equally evaluated moves. With noise probability p, a stochastic choice supplies diversification. Search-step and restart limits prevent indefinite cycling.

The dynamic noise mechanism watches recent progress. In the reported experiments the initial p was 0.1. If the variance in the number of inconsistencies changed insufficiently over the previous fifty steps, noise was increased; otherwise it returned to its initial value. Stagnation therefore changes control rather than being mistaken for evidence that the current greedy basin is globally best.

The evaluation E combines three terms, written with coefficients α, β and γ in the paper’s general definition. SearchCost estimates how many additional actions are needed to repair new unsupported facts and threats. TemporalCost estimates the candidate’s effect on action completion times and plan makespan. ExecutionCost estimates the action-cost contribution derived from the problem’s metric. A later normalised form uses μ_E, μ_T, maxima over the neighbourhood and the current inconsistency count κ so that quality terms do not swamp progress towards validity.

Weights express the planning objective. In a pure speed-oriented phase, search cost matters heavily because reaching any solution quickly is the priority. When improving a valid plan, temporal and execution components can receive greater influence. The user’s PDDL metric helps set the relative temporal and execution weights.

The terms are estimates, not admissible lower bounds. A locally low score can still lead to a poor basin; a temporarily expensive edit can open a much better plan. LPG seeks effective guidance rather than optimality guarantees. Its stochastic choice and restarts are part of the answer to heuristic error.

For insertion, the evaluator builds a relaxed plan supporting the new action’s preconditions and considers actions that may be threatened by the insertion. For removal, it estimates how to re-support facts that depended on the deleted action. Reuse matters: actions already present in the graph should not be counted as if they must be bought again.

In reported default settings, μ_E was set to one and μ_T to the coefficient of total-time in a linear metric. When no metric was specified, μ_E was 0.5 and μ_T zero. These details keep a mathematical-looking score tied to implementation choices; changing scales or weights can change which neighbour wins.

A delete relaxation lets achieved facts persist, making support cheaper to calculate. For each fact, LPG’s reachability procedure records an estimated number of actions, execution cost, earliest time and a set of required actions. Those required-action sets help avoid simply adding independent fact estimates and double-counting shared support.

The forward computation applies each considered action at most once and excludes actions with mutex preconditions under its restricted scheme. This differs from classic h_max, h_add and FF-style extraction. LPG’s relaxed plans also account for threats when choosing supporting actions; a cheap supporter that damages the current graph may cease to look cheap.

RelaxedPlan assembles actions to support a set of facts relative to the current partial graph. Search cost is primarily the number of actions the repair appears to need, adjusted for reuse and interference. Execution and temporal costs of that relaxed support are then passed into the combined move evaluation.

Because deletes are relaxed, the forecast remains optimistic about some interactions. Because action availability is restricted and threats are considered, it is not the same optimism as FF’s heuristic. The result should be understood as engineered local guidance rather than a canonical distance.

This architecture is important: precomputed reachability supplies broad estimates, while the current action graph supplies context. A fact that is three actions from the initial state may be one action away when two supporters already sit in the candidate plan. Conversely, inserting an apparently direct producer can be expensive if it threatens a long no-op chain.

A numerical state pairs propositional facts with real-valued variables. Preconditions compare numerical expressions; effects assign, increase, decrease, multiply or divide variables. LPG propagates estimated values level by level in the linear graph so that it can identify unsupported numerical conditions and evaluate actions with state-dependent durations.

Action execution cost is derived from the plan metric while separating the temporal component already represented by duration. For a metric such as four times total time plus five times fuel used, LPG treats the fuel-changing effect as execution cost and handles total time through temporal evaluation. Static action costs are the main case in the paper; fully dynamic costs remain limited.

After finding a valid plan, LPG records its quality as a bound. It then modifies the graph and searches for another valid solution whose metric improves the incumbent. Repeated restarts and changed evaluation emphasis yield a sequence of solutions. The user can stop at any time and retain the best one seen.

This explains the distinction between LPG-speed and LPG-quality. They are not unrelated planners. One reports the quick-solution operating point; the other allows up to five CPU minutes in the paper’s comparison to improve plan quality. Intermediate plans trace a speed–quality frontier that a first-versus-last table can hide.

Anytime does not mean quality improves at every search step. Most intermediate graphs are invalid, and even valid plans can be worse than the incumbent. The guarantee is operational: once a solution exists, the system preserves its best known answer while continuing to seek a better one.

The benchmark families include Depots, DriverLog, Rovers, Satellite and ZenoTravel across STRIPS, SimpleTime, Time, Numeric, Complex and HardNumeric variants. LPG used the same default search settings across attempted problems. Median results over five runs reduce: but do not eliminate: the variability of stochastic search.

In post-competition tests, LPG attempted 468 of 508 fully automated problems and solved 94.4 per cent of those attempted. The competition figures had been lower: 428 attempted and an 87 per cent success ratio. The authors attribute much of the improvement to corrected parser behaviour and an extended version, so the two figures must not be silently merged.

The detailed comparison against a constructed “SuperPlanner” takes the best result among the other fully automated planners for each problem. LPG-speed’s aggregate solved rate in the reported comparison was 94.6 per cent, versus 80.3 per cent for the SuperPlanner. In Time variants, LPG solved 95.1 per cent versus 77.4 per cent; it was faster on 81.4 per cent and at least an order of magnitude faster on 25.5 per cent of compared cases.

The pattern is not uniform. FF was faster on average for smaller DriverLog STRIPS cases. In ZenoTravel SimpleTime LPG was roughly an order of magnitude faster in the authors’ account. Numeric Satellite exposed limitations, while temporal and complex variants often favoured LPG. Plan quality also depends on allowing the anytime process to run rather than stopping at its first solution.

“SuperPlanner” is a demanding per-instance envelope, but it is not an executable single system with common overhead. IPC-era CPU times, parsers and benchmark encodings also limit modern generalisation. The evidence strongly establishes that temporal action-graph local search was competitive and often excellent on IPC-3; it does not establish superiority for every planner, domain or hardware generation.

Stochastic local search is incomplete under finite restart and step limits. Failure to find a plan does not prove unsolvability. Nor does finding a plan prove optimality. The graph representation and evaluation are built to discover good solutions quickly, not certify that no better solution exists.

Delete relaxation and local move scoring can misrank repairs. A supporter may look cheap while creating distant interference; removal may look costly while unlocking a different structure. Adaptive noise reduces entrapment but does not convert heuristic search into exhaustive search.

The competition system did not handle universally quantified effects in Settlers Numeric and did not properly handle the maximise-data metric in Satellite HardNumeric. It used best-first search rather than local search for FreeCell. Those exclusions matter when interpreting broad “domain-independent” language.

Temporal handling was sound but sometimes conservative. Always ordering mutex actions end-to-start can forgo legal overlaps between compatible endpoints. Dynamic action durations were supported through estimated numerical state, whereas dynamic execution costs were not treated with the same generality.

Grounding, mutex precomputation and representation size can become bottlenecks outside the tested scale. The study reports excellent IPC-3 behaviour, not a complexity escape. Modern reproduction should publish preprocessing, grounding and memory costs beside search time.

The numerical estimates are explanatory, not measurements copied from the paper. Each candidate declares SearchCost, TemporalCost and ExecutionCost. The profile supplies weights, and the displayed score is their exact weighted sum.

Unsupported power compares inserting a switch-on action, reusing a slower powered instrument, or removing the photograph. Mutex overlap compares ordering, replacing or removing an interfering action. Insufficient fuel compares refuelling, rerouting or dropping a flight.

All candidates resolve the selected flaw, satisfying the neighbourhood contract. They differ in collateral work. A speed profile weights search most; a quality profile weights execution cost most. The chosen minimum can therefore change without any arithmetic or logical disagreement.

The paper’s stochastic branch is represented conceptually rather than randomly fired, so the demonstration remains deterministic and exactly testable. In LPG a noise event can choose a non-minimum neighbour to diversify search. Here the preferred move is the greedy baseline against which that exploration would be defined.

The three tests verify that every shown score equals the declared weighted sum, the chosen move has the global minimum score with stable lexical tie-breaking, and every candidate advertises resolution of the selected inconsistency. Changing a control reruns all three tests.

Begin with the public IPC-3 PDDL2.1 tasks and identify exactly which parser and semantic subset is supported. Record grounding counts, persistent mutex computation, LA-graph size, preprocessing time and memory. Preserve original domain variants rather than silently translating temporal or numerical constructs into easier forms.

Implement causal and exclusion constraints separately. Unit-test earliest-time propagation after insertion and removal, including start, overall and end conditions. Verify that graph levels never introduce an unintended precedence. Test conservative mutex ordering and an endpoint-aware refinement on the same plans.

For local search, publish inconsistency-selection rules, candidate neighbourhoods, relaxed-plan contents, component scales, weights, noise updates, restart bounds and random seeds. Run enough seeds to report distributions rather than only medians. Include time to first solution, success probability, quality-over-time area, final metric, actions, makespan and resource use.

Recreate LPG-speed and LPG-quality as operating points on the same improvement trajectory. Compare with individual planners as well as a virtual best envelope. A virtual best system answers “was anyone better?”; a deployable portfolio answers “could one controller obtain those results?”

Extensions can test learned move ranking, large-neighbourhood repairs, incremental temporal networks and modern temporal planners. Keep ablations causal: remove threat accounting, required-action reuse, adaptive noise or temporal cost one at a time. The goal is to learn which component earns which advantage, not merely to produce a faster descendant.

Review one: scholarly fidelity and teaching. The reconstruction was checked against the 52-page primary article and indexed in-body passages. It preserves the distinction between planning graphs, LA-graphs and TA-graphs; unsupported preconditions as inconsistencies; insertion and removal neighbourhoods; causal and exclusion constraints; temporal-value propagation; three-part evaluation; restricted relaxed plans; numerical state; adaptive noise; and incremental plan improvement.

The main teaching hazard was treating a graph level as time. The page states repeatedly that levels form a topological scaffold while Ω and durations determine the schedule. A second hazard was presenting every intermediate candidate as executable. The repair account makes invalid but explicitly flawed graphs central.

Review two: evidence fairness, language and accessibility. The journal date (2003) is separated from the canon’s 2011 archival deposit. Competition and post-competition attempt/success figures are not conflated. The SuperPlanner is identified as a virtual per-problem envelope. Strong temporal results are shown beside weaker or unsupported regions, and no completeness or optimality guarantee is implied.

The ten figures have unique titles, descriptions and captions. Animation is decorative, pauses under reduced-motion preference and does not carry exclusive meaning. Controls have visible labels, outputs update as text, and the laboratory exposes three exact tests. British spelling is used; source reconstructions are distinguished from synthetic explanatory numbers.

Both works reject a single fixed control rule. Moreno-Scott and colleagues choose among heuristics by problem region. Gerevini, Saetti and Serina balance search, time and execution costs and inject noise when progress stalls. In each case control depends on a description of the current problem, not only on logical validity.

LPG also reconnects to earlier planning papers in the collection. Planning graphs provide reachability and mutex structure; relaxed planning supplies estimates; temporal constraints turn partial-order relations into earliest times. The distinctive contribution is to make these structures the substrate of stochastic local repair and anytime improvement.

Canon 0091 moves from planning control to logical control with Keith Clark’s “Negation as Failure”. The transition is apt: an automated system’s behaviour depends not only on what follows from explicit facts, but on what it is licensed to do when proof or support is absent.

An unsupported precondition is simultaneously a logical failure and a generator of alternatives. Causal links say which past commitments matter. Mutexes say which coexistences are impossible. Temporal values say how local changes propagate into schedule quality. A relaxed plan forecasts what the change is likely to demand next.

This architecture turns evaluation into a conversation among representations. The logical graph does not decide quality. The metric does not decide feasibility. The stochastic controller does not invent repairs. Each contributes a bounded kind of information, and the search step exists where those boundaries meet.

The same pattern appears in agency more broadly: maintain a provisional course, identify a concrete discrepancy, estimate remedies, sometimes explore against the current estimate, and preserve the best achieved outcome. LPG is valuable precisely because this pattern is operational rather than metaphorical. Every part has a data structure, update rule and failure mode.