Part IThe shape of a completable mission

A plan often arrives as a sentence: collect the evidence, run the checks, obtain approval and release. The sentence sounds ordered, yet its conjunctions hide most of the engineering. Do the checks require the same frozen candidate? May security and functional evaluation run concurrently? Can an independent test replace a supplier attestation? Does approval expire if the candidate changes? What postcondition proves that release occurred?

Planning Before Action develops the earlier question of how preconditions, effects, partial order and decomposition turn an intention into a valid plan. Mission control starts one step later. Its narrower question is: after execution has begun, what representation lets the system know what remains possible and what must be repaired?

AND and OR are different causal claims

Classical AND/OR graphs distinguish two kinds of reduction. At an AND relation, every child obligation is needed. At an OR relation, any acceptable child can support the parent. Hierarchical task networks and partial-order planning add decomposition and ordering constraints, while workflow formalisms supply execution semantics and soundness checks. The useful inheritance is not a particular notation. It is the insistence that alternatives and prerequisites carry different logic.

For a task t, let its requirements be a set of clauses. Every clause must hold, and each clause contains one or more alternatives. A predecessor counts only when its outcome is verified. The task’s dependency condition can then be written:

This is an AND-of-OR form. The risk approval in the running case might require functional evidence and security evidence and residency evidence. The residency clause might accept a provider attestation or an independent probe. The distinction is operational. If the attestation fails, an OR alternative can preserve the mission. If security evidence fails, no amount of residency evidence should compensate for it.

An OR edge also needs a scope. Two artefacts may be interchangeable for one obligation and unequal for another. A provider attestation and an independent technical test might both satisfy a residency claim, while only the attestation satisfies a contractual notice clause. Treating “OR” as generic similarity lets a model silently weaken the mission. The graph therefore stores the obligation at the clause, not merely links among task names.

A task node must be more than a label

A useful node carries a typed input, expected output, precondition or dependency formula, owner, execution state, evidence requirement, validity interval, retry policy and recovery rule. It may also record cost, deadline and resource needs. These fields are not decorative metadata. They determine whether a scheduler may release the work and whether a later result can still support the goal.

A graph of labels is still a picture; a mission graph is an executable claim structure. Its edges say why one result supports another. Its receipts say what was observed. Its state machine says what transitions are legal. Its version says which structure governed the action. That is the minimum needed to ask a precise question after interruption: which part of the mission remains valid?

Part IIProgress is a remaining solution

A project dashboard usually compresses progress into a fraction: completed tasks divided by total tasks. The fraction is easy to calculate and often misleading. It gives equal weight to a decisive prerequisite and an optional document. It counts work on abandoned branches. It remains high when the only viable route disappears. It can even increase after the mission becomes impossible.

The verified frontier

Mission control needs a more local and more useful quantity: the set of tasks that may start now. Call it the verified frontier. A pending task belongs to the frontier when every AND clause has at least one verified alternative, its world-state guard still holds, and its authority preconditions can be checked before execution.

The frontier changes when evidence arrives, expires or is invalidated. It also changes when world state moves. A credit assessment prepared against one application version should leave the frontier after the application changes. A deployment step should leave it if the maintenance window closes. The graph supplies dependency logic, while guards bind that logic to current reality.

The smallest viable solution subgraph

A goal with alternatives usually has several possible supporting subgraphs. Let Ω(g) be the set of subgraphs that could still satisfy goal g from the current state. Each task has a remaining cost c_t, which may represent elapsed time, money, risk-weighted effort or a vector of several quantities. The cheapest current route is:

This does not demand that every mission optimise one scalar. A regulated process may compare routes lexicographically: first satisfy mandatory controls, then minimise irreversible exposure, then elapsed time, then cost. The important change is conceptual. Progress becomes the condition and cost of a viable remaining proof, not the proportion of coloured nodes.

A minimal worked example

Suppose a release needs three clauses: functional evidence, security evidence and residency evidence. Functional and security reports have valid receipts. Residency may be supported by a provider attestation or an independent probe. The provider route has failed, but the independent probe succeeded. The residency pack is therefore valid, and accountable approval enters the verified frontier.

The raw graph contains ten tasks. Five have verified receipts, so count progress is 50 per cent. The cheapest remaining solution contains only approval, canary deployment, postcondition readback and final release, with synthetic remaining cost 5.5. The failed attestation does not make the goal impossible because the OR clause is already shielded by another verified route.

A repair cone is not automatically every descendant. Consider a downstream report whose postcondition was independently re-observed after its inputs changed. That report may remain valid if its evidence contract says the observation supersedes derivation. Conversely, a copied summary can become invalid even when its text looks plausible. Provenance and evidence semantics determine propagation. The graph supplies reachability; the receipt contract decides whether support was actually lost.

flowchart LR
  A["Eleven green ticks, zero<br/>releasable outcome"] --> B["Part I The shape of a<br/>completable mission"]
  B --> C["Part II Progress is a<br/>remaining solution"]
  C --> D["Part III Mission control is a<br/>runtime, not a diagram"]
  D -. "re-test" .-> A
  classDef first fill:#0a1424,stroke:#7B4CD8,stroke-width:2px,color:#e6f3ff
  classDef step fill:#0a1424,stroke:#3f7da0,stroke-width:1px,color:#e6f3ff
  class A first
  class B,C,D step

Part IIIMission control is a runtime, not a diagram

The word “graph” invites a design-tool interpretation. Teams draw dependencies, export an image and then execute through chat, tickets and scripts. The picture soon diverges from the mission. Runtime mission control needs the graph itself to own legal state transitions, scheduling decisions and evidence links. A drawing may be generated from that state, but it cannot be the source of execution truth.

Give uncertainty a first-class state

A minimal lifecycle includes pending, ready, running, succeeded, failed, unknown and skipped. “Ready” may be computed rather than stored. “Unknown” deserves special treatment. It means a command was accepted or sent, yet the controller cannot establish whether the intended effect happened. A timeout after a canary-deployment request is the classic case.

Calling unknown a failure invites blind retry and duplicate effect. Calling it success advances dependants without proof. The only safe next step is an outcome-observation task: query the target system, reconcile identifiers, inspect an effect receipt or escalate to an operator. Unknown outcome is a branch in the mission, not an error message to hide inside a retry loop.

Keep five kinds of state separate

Mission control often fails because every persistent object is called memory. The graph’s node statuses are workflow state. The current release version, deployment state and maintenance window are world state. Prior conversations are episodic memory. Policies and manuals are enterprise knowledge. Receipts linking claims to observations form an evidence ledger. They have different owners, update rates and trust rules.

A restart should reconstruct workflow state from durable events, refresh world state from authoritative systems, compile only relevant knowledge into context, and preserve evidence provenance. It should not ask a model to infer all five from a transcript. Durable workflow systems illustrate the value of replaying persisted event histories after failure, while W3C PROV-O supplies a vocabulary for linking entities, activities, derivations and responsible agents. Neither product nor standard, by itself, defines the mission’s business truth.

The mission graph routes work; it does not grant power. A model may propose a node or suggest an alternative decomposition. A deterministic validator checks types, acyclicity, allowed task classes and evidence contracts. A policy layer binds actor, subject, purpose and current permission. A typed action contract limits parameters. Only then can an executor act. Afterward, readback decides whether the graph may advance.

A production-shaped worked scenario

A candidate package is frozen and assigned a digest. Functional evaluation and security evaluation run in parallel against that digest. Residency evidence accepts either a supplier attestation or an independent probe. Accountable approval requires all three evidence clauses. Canary deployment requires that approval, a valid maintenance window and a scoped release capability. Final release requires canary readback, not merely a successful API response.

The supplier attestation fails. The independent probe succeeds, so the residency pack remains supported. Mission control places risk approval on the verified frontier and marks the supplier branch non-selected. After approval, the deployment worker sends the canary command. The network times out before a response arrives. Mission control records an unknown outcome and schedules a readback query. It does not rerun deployment. Readback finds the canary active under the expected digest, emits an effect receipt, and makes observation of service health ready.

Several boundaries remain visible. The language model can help decompose the goal, draft test plans and explain blockers. The mission controller computes readiness from typed state. The policy system decides whether the scoped capability may be used. The deployment platform produces the effect. Observability establishes the postcondition. The accountable person owns approval. Collapsing these roles into one “agent status” would destroy the evidence chain.

Long-lived transactions offer another useful precedent. Sagas divide work into steps and define compensating transactions when a partial execution must be amended. Compensation is recovery, not time reversal. A notification may be withdrawn but still have been read; a market order may be offset but not erased. The mission graph should therefore attach compensation and escalation to nodes while preserving the original effect receipt.

Part IVWhat the evidence supports, and what it does not

The case for explicit dependency control does not begin with language models. AND/OR search formalised problem reduction decades ago. Partial-order planners represented only necessary ordering commitments. Hierarchical task networks analysed how tasks decompose into constrained networks. Workflow-net research developed structural notions of completion and detected deadlocks or livelocks under defined formalisms. These traditions establish that dependency structure changes what can be planned and verified.

They do not prove that every agent system needs a graph. Nor do they prove that a generated graph is correct. Modern evidence is narrower. A NeurIPS 2023 study reported that its best evaluated model achieved roughly 12 per cent average success when generating executable plans autonomously across the tested classical-style domains, while model outputs were more useful as heuristic guidance for sound planners. The result concerns those domains and model versions; it should not be treated as a universal ceiling.

A 2026 Atomic Task Graph preprint provides more direct, though still provisional, evidence for local repair. It represents tool-use tasks as a directed graph, executes independent branches and repairs a minimal affected subgraph. In the authors’ ablation on Mistral-7B, removing local repair reduced reported performance by 7.72 points on ALFWorld and 6.48 points on ScienceWorld. The study also reports important limits: decomposition depends on the backbone model, failure localisation is difficult with noisy observations or long-range dependencies, evaluation is text-based, and simple tasks incur overhead.

These results support a bounded conclusion. Explicit dependency control can improve scheduling, localisation and recovery in selected long-horizon environments. They do not establish that a graph alone causes reliable agency, that benchmark gains transfer to regulated operations, or that an LLM should be trusted to author its own executable dependencies without validation.

The strongest competing explanation

A credible alternative says the apparent benefit comes from extra computation and scaffolding, rather than graph structure. Give a stronger model a larger context, a better prompt, tool feedback and repeated replanning, and it may reconstruct dependencies when needed. A graph can then become duplicated state, expensive to maintain and another place for errors.

This objection should shape the experiment. Compare a graph controller against a linear state machine and a transcript-based replanner under the same model, tools, budgets and failure injections. Measure goal success, duplicate effects, time to identify a blocker, unaffected work preserved after failure, human interventions and total execution cost. If explicit dependencies do not reduce propagation or recovery cost under matched disturbances, the graph has not earned its complexity.

A discriminating failure-injection experiment

A useful evaluation would hold the model, tools, prompts, task instances, action budget and human escalation policy constant. Only the control representation would change. Controller A receives the full transcript and replans after each observation. Controller B uses a conventional linear or branching workflow. Controller C uses the evidence-backed AND/OR graph described here. Each controller should face the same clean runs and the same seeded disturbances.

The disturbances should vary one causal feature at a time: expire a decisive receipt; fail one member of a valid OR clause; fail every member of that clause; return an unknown outcome after an external command; change world state after a node becomes ready; and corrupt a completed artefact that supports two downstream branches. The test set should include simple linear missions so that overhead has a fair chance to appear.

Primary outcomes are verified goal success and duplicate external effects. Mechanism-level outcomes are time to locate the violated clause, unaffected work preserved, size of the reopened region, wasted model and tool calls, stale actions released, operator interventions and wall-clock recovery time. Graph-authoring errors must count against Controller C. Replanning tokens and validator work must count in total cost.

The thesis predicts little or no advantage on clean linear tasks, then increasing advantage as alternatives, concurrency and selective recovery become important. It would be weakened if Controller C merely shifted errors into graph construction, if its repair cones were no smaller than global replanning, or if matched transcript replanning preserved unaffected work at the same cost. That outcome would favour a simpler controller and a better state summary rather than a mission graph.

The negative control

Consider a nightly file transfer with one legal sequence: close the source, compute a checksum, copy, verify checksum, open the destination. Each step has a deterministic postcondition. There are no alternatives, no useful concurrency and no reason to preserve work after a branch failure. A five-state workflow or checklist provides the same decision information with less machinery. This is the negative control that prevents “graph” from becoming a prestige synonym for workflow.

Even inside its useful range, the graph may be wrong. A model can omit a prerequisite, invent a false alternative or assign an invalid postcondition. Organisational actors can game evidence receipts. World state can change between readiness and release. A malicious tool can return a syntactically valid lie. The response is layered control: graph validation, pre-effect freshness, independent readback, provenance, failure injection and human accountability where consequence demands it.

Formal workflow verification also has limits. Soundness properties can expose certain structural anomalies without domain knowledge, but extensions such as cancellation and priorities change what is decidable. Mission control should therefore use formal checks where the model permits them and avoid implying complete verification of an open, changing world.

Part VA decision instrument and an executable planner

The design decision should follow the structure of the work. A mission graph is warranted when the controller must reason about alternatives, parallel prerequisites, interruption or selective recovery. Consequence raises the evidence standard, but consequence alone does not create graph complexity. A simple irreversible action may need strong authority and readback while still using a linear workflow.

The seven-question gate

A practical rule follows. Use a mission graph when at least two structural signals are present and local recovery has material value. Use it sooner when a failed branch can waste hours of expensive work or expose an irreversible effect. Avoid it when the final question has no observable completion contract. In that case, the graph can organise inquiry but should not certify success.

The dependency planner

The accompanying Python artefact encodes the minimal mechanism. Each task contains an AND-of-OR clause tuple, status, synthetic cost and evidence receipts. The validator rejects missing references, empty clauses, cycles and success without evidence. The planner computes the verified frontier, enumerates non-dominated remaining solution subgraphs for a small DAG, refuses unknown outcomes and estimates a repair cone after evidence invalidation.

The positive case starts with a failed provider attestation and a verified independent test. Approval is ready and the release remains viable. Failure injection invalidates the only successful alternative; the residency pack reopens and downstream nodes become impossible. The negative case marks approval successful without a receipt and is rejected. A separate unknown-outcome case blocks a blind canary retry.

#!/usr/bin/env python3
"""A small evidence-aware AND/OR dependency planner.

The planner uses synthetic data only and the Python standard library.
A task's ``clauses`` are interpreted as AND-of-OR requirements:

    (("a", "b"), ("c",))  means  (a OR b) AND c

A predecessor counts as satisfied only when it is marked ``succeeded`` and
has at least one evidence receipt. Unknown outcomes are deliberately not
retried or treated as failures: they require reconciliation first.
"""

from __future__ import annotations

import argparse
import copy
import math
import unittest
from dataclasses import dataclass, field
from enum import Enum
from itertools import product
from typing import Iterable, Mapping, Sequence


class MissionError(ValueError):
    """Raised when a mission graph violates an executable invariant."""


class Status(str, Enum):
    PENDING = "pending"
    RUNNING = "running"
    SUCCEEDED = "succeeded"
    FAILED = "failed"
    UNKNOWN = "unknown"
    SKIPPED = "skipped"


@dataclass
class Task:
    """One typed node in an AND/OR dependency graph.

    ``clauses`` is a tuple of requirement clauses. Every clause must be
    satisfied, while any one alternative inside a clause is sufficient.
    ``evidence`` contains synthetic receipt identifiers, not payloads.
    """

    task_id: str
    label: str
    clauses: tuple[tuple[str, ...], ...] = ()
    cost: float = 1.0
    status: Status = Status.PENDING
    evidence: tuple[str, ...] = ()
    owner: str = "mission-control"


@dataclass(frozen=True)
class Plan:
    task_ids: frozenset[str]
    remaining_cost: float


@dataclass(frozen=True)
class RepairReport:
    invalidated: str
    reopened_verified_nodes: tuple[str, ...]
    newly_impossible_nodes: tuple[str, ...]
    still_viable_goal: bool


@dataclass
class Mission:
    tasks: dict[str, Task]

    def validate(self) -> None:
        """Check references, evidence invariants and acyclicity."""
        if not self.tasks:
            raise MissionError("A mission must contain at least one task.")

        for key, task in self.tasks.items():
            if key != task.task_id:
                raise MissionError(f"Task map key {key!r} does not match task_id {task.task_id!r}.")
            if task.cost < 0 or not math.isfinite(task.cost):
                raise MissionError(f"Task {key!r} has an invalid cost: {task.cost!r}.")
            if task.status is Status.SUCCEEDED and not task.evidence:
                raise MissionError(
                    f"Task {key!r} claims success without an evidence receipt."
                )
            for clause in task.clauses:
                if not clause:
                    raise MissionError(f"Task {key!r} contains an empty OR clause.")
                for dependency in clause:
                    if dependency == key:
                        raise MissionError(f"Task {key!r} depends on itself.")
                    if dependency not in self.tasks:
                        raise MissionError(
                            f"Task {key!r} references unknown dependency {dependency!r}."
                        )

        visiting: set[str] = set()
        visited: set[str] = set()

        def visit(task_id: str) -> None:
            if task_id in visiting:
                raise MissionError(f"Dependency cycle detected at {task_id!r}.")
            if task_id in visited:
                return
            visiting.add(task_id)
            for clause in self.tasks[task_id].clauses:
                for dependency in clause:
                    visit(dependency)
            visiting.remove(task_id)
            visited.add(task_id)

        for task_id in self.tasks:
            visit(task_id)

    def clone(self) -> "Mission":
        return Mission(copy.deepcopy(self.tasks))

    def is_verified(self, task_id: str) -> bool:
        task = self.tasks[task_id]
        return task.status is Status.SUCCEEDED and bool(task.evidence)

    def formula_satisfied(self, task_id: str) -> bool:
        """Return whether every requirement clause has a verified alternative."""
        task = self.tasks[task_id]
        return all(any(self.is_verified(dep) for dep in clause) for clause in task.clauses)

    def ready(self) -> tuple[str, ...]:
        """Return the verified frontier: pending tasks whose clauses all hold."""
        return tuple(
            task_id
            for task_id, task in self.tasks.items()
            if task.status is Status.PENDING and self.formula_satisfied(task_id)
        )

    def blocked_reasons(self, task_id: str) -> tuple[str, ...]:
        task = self.tasks[task_id]
        if task.status is not Status.PENDING:
            return (f"status is {task.status.value}",)
        reasons: list[str] = []
        for index, clause in enumerate(task.clauses, start=1):
            if any(self.is_verified(dep) for dep in clause):
                continue
            states = ", ".join(
                f"{dep}={self.tasks[dep].status.value}" for dep in clause
            )
            reasons.append(f"clause {index} needs one of [{states}]")
        return tuple(reasons)

    def set_status(
        self,
        task_id: str,
        status: Status,
        evidence: Sequence[str] = (),
    ) -> None:
        if task_id not in self.tasks:
            raise MissionError(f"Unknown task {task_id!r}.")
        task = self.tasks[task_id]
        if status is Status.RUNNING and task.status is Status.PENDING:
            if not self.formula_satisfied(task_id):
                detail = "; ".join(self.blocked_reasons(task_id))
                raise MissionError(f"Task {task_id!r} is not ready: {detail}")
        if status is Status.SUCCEEDED and not evidence:
            raise MissionError(
                f"Task {task_id!r} cannot succeed without an evidence receipt."
            )
        if task.status is Status.UNKNOWN and status is Status.RUNNING:
            raise MissionError(
                f"Task {task_id!r} has an unknown outcome; reconcile before retrying."
            )
        task.status = status
        task.evidence = tuple(evidence)

    def unknown_outcomes(self) -> tuple[str, ...]:
        return tuple(
            task_id
            for task_id, task in self.tasks.items()
            if task.status is Status.UNKNOWN
        )

    def candidate_plans(self, goal_id: str) -> tuple[Plan, ...]:
        """Enumerate non-dominated remaining solution subgraphs for a small DAG.

        Failed, skipped and unknown nodes cannot currently support a plan. A
        running or pending node contributes its remaining cost. Shared
        dependencies are counted once because each candidate is a set.
        """
        if goal_id not in self.tasks:
            raise MissionError(f"Unknown goal {goal_id!r}.")

        memo: dict[str, tuple[frozenset[str], ...]] = {}

        def plans_for(task_id: str) -> tuple[frozenset[str], ...]:
            if task_id in memo:
                return memo[task_id]
            task = self.tasks[task_id]
            if self.is_verified(task_id):
                memo[task_id] = (frozenset(),)
                return memo[task_id]
            if task.status in {Status.FAILED, Status.UNKNOWN, Status.SKIPPED}:
                memo[task_id] = ()
                return memo[task_id]

            candidates: list[frozenset[str]] = [frozenset({task_id})]
            for clause in task.clauses:
                alternatives: list[frozenset[str]] = []
                for dependency in clause:
                    alternatives.extend(plans_for(dependency))
                if not alternatives:
                    memo[task_id] = ()
                    return memo[task_id]
                candidates = [
                    left | right
                    for left, right in product(candidates, alternatives)
                ]
                candidates = self._prune_plan_sets(candidates)

            memo[task_id] = tuple(self._prune_plan_sets(candidates))
            return memo[task_id]

        plans = []
        for task_ids in plans_for(goal_id):
            cost = sum(self.tasks[task_id].cost for task_id in task_ids)
            plans.append(Plan(task_ids=task_ids, remaining_cost=cost))
        plans.sort(key=lambda plan: (plan.remaining_cost, len(plan.task_ids), sorted(plan.task_ids)))
        return tuple(plans)

    def _prune_plan_sets(
        self, candidates: Iterable[frozenset[str]]
    ) -> list[frozenset[str]]:
        unique = sorted(
            set(candidates),
            key=lambda ids: (
                sum(self.tasks[task_id].cost for task_id in ids),
                len(ids),
                sorted(ids),
            ),
        )
        kept: list[frozenset[str]] = []
        for candidate in unique:
            candidate_cost = sum(self.tasks[task_id].cost for task_id in candidate)
            dominated = False
            for other in kept:
                other_cost = sum(self.tasks[task_id].cost for task_id in other)
                if other.issubset(candidate) and other_cost <= candidate_cost:
                    dominated = True
                    break
            if not dominated:
                kept.append(candidate)
        return kept

    def cheapest_plan(self, goal_id: str) -> Plan | None:
        plans = self.candidate_plans(goal_id)
        return plans[0] if plans else None

    def completion_ratio(self) -> float:
        succeeded = sum(1 for task_id in self.tasks if self.is_verified(task_id))
        return succeeded / len(self.tasks)

    def repair_cone(self, invalidated_id: str, goal_id: str) -> RepairReport:
        """Estimate the smallest provenance-sensitive region affected by invalidation.

        A verified consumer is reopened only when one of its AND clauses loses
        every verified alternative. Pending descendants are marked newly
        impossible only when all remaining solution subgraphs disappear.
        """
        if invalidated_id not in self.tasks:
            raise MissionError(f"Unknown task {invalidated_id!r}.")
        before = self.clone()
        after = self.clone()
        after.tasks[invalidated_id].status = Status.FAILED
        after.tasks[invalidated_id].evidence = ()

        reopened: set[str] = {invalidated_id}
        changed = True
        while changed:
            changed = False
            for task_id, task in after.tasks.items():
                if task_id in reopened or task.status is not Status.SUCCEEDED:
                    continue
                before_ok = before.formula_satisfied(task_id)
                after_ok = after.formula_satisfied(task_id)
                if before_ok and not after_ok:
                    task.status = Status.PENDING
                    task.evidence = ()
                    reopened.add(task_id)
                    changed = True

        newly_impossible: list[str] = []
        for task_id, task in before.tasks.items():
            if task.status is Status.SUCCEEDED:
                continue
            if before.cheapest_plan(task_id) is not None and after.cheapest_plan(task_id) is None:
                newly_impossible.append(task_id)

        return RepairReport(
            invalidated=invalidated_id,
            reopened_verified_nodes=tuple(sorted(reopened)),
            newly_impossible_nodes=tuple(sorted(newly_impossible)),
            still_viable_goal=after.cheapest_plan(goal_id) is not None,
        )


def build_release_mission() -> Mission:
    """Synthetic worked scenario used by the article and tests."""
    rows = [
        Task(
            "freeze_candidate",
            "Freeze candidate package",
            cost=0.5,
            status=Status.SUCCEEDED,
            evidence=("receipt:sha256:7f3a",),
            owner="release-engineering",
        ),
        Task(
            "functional_eval",
            "Run functional evaluation",
            clauses=(("freeze_candidate",),),
            cost=2.0,
            status=Status.SUCCEEDED,
            evidence=("report:functional:184",),
            owner="evaluation",
        ),
        Task(
            "security_eval",
            "Run security evaluation",
            clauses=(("freeze_candidate",),),
            cost=3.0,
            status=Status.SUCCEEDED,
            evidence=("report:security:91",),
            owner="security",
        ),
        Task(
            "provider_attestation",
            "Obtain provider residency attestation",
            clauses=(("freeze_candidate",),),
            cost=1.0,
            status=Status.FAILED,
            owner="supplier-management",
        ),
        Task(
            "independent_test",
            "Run independent residency test",
            clauses=(("freeze_candidate",),),
            cost=2.5,
            status=Status.SUCCEEDED,
            evidence=("report:residency-probe:22",),
            owner="platform-assurance",
        ),
        Task(
            "residency_evidence",
            "Assemble acceptable residency evidence",
            clauses=(("provider_attestation", "independent_test"),),
            cost=0.5,
            status=Status.SUCCEEDED,
            evidence=("evidence-pack:residency:12",),
            owner="risk-office",
        ),
        Task(
            "risk_approval",
            "Record accountable risk approval",
            clauses=(("functional_eval",), ("security_eval",), ("residency_evidence",)),
            cost=1.0,
            owner="accountable-executive",
        ),
        Task(
            "deploy_canary",
            "Deploy bounded canary",
            clauses=(("risk_approval",),),
            cost=2.0,
            owner="release-engineering",
        ),
        Task(
            "observe_readback",
            "Verify canary postconditions",
            clauses=(("deploy_canary",),),
            cost=2.0,
            owner="operations",
        ),
        Task(
            "release",
            "Release candidate",
            clauses=(("observe_readback",),),
            cost=0.5,
            owner="release-authority",
        ),
    ]
    mission = Mission({task.task_id: task for task in rows})
    mission.validate()
    return mission


def run_demo() -> None:
    mission = build_release_mission()
    plan = mission.cheapest_plan("release")
    print("POSITIVE CASE: failed primary evidence path, viable alternative")
    print(f"verified completion ratio: {mission.completion_ratio():.0%}")
    print(f"verified frontier: {', '.join(mission.ready())}")
    if plan is None:
        print("goal is not currently viable")
    else:
        ordered = ", ".join(sorted(plan.task_ids))
        print(f"cheapest remaining solution cost: {plan.remaining_cost:.1f}")
        print(f"remaining solution subgraph: {ordered}")

    report = mission.repair_cone("independent_test", "release")
    print("\nFAILURE INJECTION: invalidate the only successful OR alternative")
    print(f"reopened verified nodes: {', '.join(report.reopened_verified_nodes)}")
    print(f"newly impossible nodes: {', '.join(report.newly_impossible_nodes)}")
    print(f"release still viable: {report.still_viable_goal}")

    print("\nNEGATIVE CASE: success without evidence is rejected")
    try:
        invalid = build_release_mission()
        invalid.tasks["risk_approval"].status = Status.SUCCEEDED
        invalid.validate()
    except MissionError as exc:
        print(f"rejected: {exc}")

    print("\nUNKNOWN OUTCOME CASE: reconcile before retry")
    uncertain = build_release_mission()
    uncertain.set_status(
        "risk_approval", Status.SUCCEEDED, evidence=("decision:risk:44",)
    )
    uncertain.set_status("deploy_canary", Status.RUNNING)
    uncertain.set_status("deploy_canary", Status.UNKNOWN)
    print(f"unknown outcomes: {', '.join(uncertain.unknown_outcomes())}")
    try:
        uncertain.set_status("deploy_canary", Status.RUNNING)
    except MissionError as exc:
        print(f"retry blocked: {exc}")


class MissionPlannerTests(unittest.TestCase):
    def test_or_alternative_keeps_goal_viable(self) -> None:
        mission = build_release_mission()
        self.assertEqual(mission.ready(), ("risk_approval",))
        plan = mission.cheapest_plan("release")
        self.assertIsNotNone(plan)
        assert plan is not None
        self.assertNotIn("provider_attestation", plan.task_ids)
        self.assertNotIn("independent_test", plan.task_ids)  # already verified

    def test_success_requires_evidence(self) -> None:
        mission = build_release_mission()
        with self.assertRaisesRegex(MissionError, "without an evidence receipt"):
            mission.set_status("risk_approval", Status.SUCCEEDED)

    def test_unknown_outcome_blocks_blind_retry(self) -> None:
        mission = build_release_mission()
        mission.set_status(
            "risk_approval", Status.SUCCEEDED, evidence=("decision:risk:44",)
        )
        mission.set_status("deploy_canary", Status.RUNNING)
        mission.set_status("deploy_canary", Status.UNKNOWN)
        with self.assertRaisesRegex(MissionError, "reconcile before retrying"):
            mission.set_status("deploy_canary", Status.RUNNING)

    def test_repair_cone_crosses_unshielded_or_clause(self) -> None:
        mission = build_release_mission()
        report = mission.repair_cone("independent_test", "release")
        self.assertIn("residency_evidence", report.reopened_verified_nodes)
        self.assertIn("release", report.newly_impossible_nodes)
        self.assertFalse(report.still_viable_goal)

    def test_repair_cone_stops_at_verified_alternative(self) -> None:
        mission = build_release_mission()
        mission.tasks["provider_attestation"].status = Status.SUCCEEDED
        mission.tasks["provider_attestation"].evidence = ("attestation:provider:8",)
        mission.validate()
        report = mission.repair_cone("independent_test", "release")
        self.assertNotIn("residency_evidence", report.reopened_verified_nodes)
        self.assertTrue(report.still_viable_goal)

    def test_cycle_is_rejected(self) -> None:
        mission = Mission(
            {
                "a": Task("a", "A", clauses=(("b",),)),
                "b": Task("b", "B", clauses=(("a",),)),
            }
        )
        with self.assertRaisesRegex(MissionError, "cycle"):
            mission.validate()


def main() -> None:
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument(
        "--test", action="store_true", help="run the built-in unit tests"
    )
    args = parser.parse_args()
    if args.test:
        suite = unittest.defaultTestLoader.loadTestsFromTestCase(MissionPlannerTests)
        result = unittest.TextTestRunner(verbosity=2).run(suite)
        raise SystemExit(0 if result.wasSuccessful() else 1)
    run_demo()


if __name__ == "__main__":
    main()

POSITIVE CASE: failed primary evidence path, viable alternative
verified completion ratio: 50%
verified frontier: risk_approval
cheapest remaining solution cost: 5.5
remaining solution subgraph: deploy_canary, observe_readback, release, risk_approval

FAILURE INJECTION: invalidate the only successful OR alternative
reopened verified nodes: independent_test, residency_evidence
newly impossible nodes: deploy_canary, observe_readback, release, risk_approval
release still viable: False

NEGATIVE CASE: success without evidence is rejected
rejected: Task 'risk_approval' claims success without an evidence receipt.

UNKNOWN OUTCOME CASE: reconcile before retry
unknown outcomes: deploy_canary
retry blocked: Task 'deploy_canary' has an unknown outcome; reconcile before retrying.

What to measure in operation

Once the graph is executable, record metrics that correspond to its mechanism: size and age of the verified frontier; time each clause remains blocked; number and cost of viable solution subgraphs; work completed outside the selected solution; evidence-expiry events; unknown-outcome age; repair-cone size; duplicate-effect attempts prevented; and human decisions needed to restore viability. Report denominators and graph versions.

Failure injection should target structure, not only model answers. Expire one evidence receipt. Remove one OR alternative. Corrupt a dependency reference. Delay a readback. Return a valid-looking receipt for the wrong candidate digest. Revoke authority after readiness but before action. The expected result is not merely an exception. The controller should expose the exact blocked clause, freeze unaffected evidence, withdraw invalid frontier nodes and create a bounded recovery route.

Version the proof, not only the code

Mission structure changes during real work. An assessor may demand another test. A supplier route may become unacceptable. A new observation may reveal that two tasks share a hidden prerequisite. Those changes should create a new graph version with an explicit reason and impact analysis. They should never rewrite the historical graph under which earlier actions were released.

Receipts therefore refer to the task version, candidate version, dependency clause and evidence policy that made them valid. A graph migration can carry a receipt forward only when a deterministic rule proves compatibility. Otherwise, the affected node re-enters review. This prevents a new edge from silently laundering old completion into a stricter mission.

Route selection also deserves a receipt. Choosing the cheapest OR branch can be inappropriate when it creates concentration risk, crosses a sovereignty boundary or consumes scarce human authority. Store the alternatives considered, the selection policy and the reason the chosen subgraph was admissible. The planner may optimise within those constraints, but it should not invent them.

The release gate is behavioural: the system must demonstrate that it can lose support without losing the mission. That is a stronger requirement than successfully completing a clean-path demo. It makes recoverability observable before a costly real interruption.

stateDiagram-v2
  [*] --> Claim
  state "AND and OR are different<br/>causal claims" as Claim
  state "A task node must be more than<br/>a label" as Test
  state "The verified frontier" as Revision
  Claim --> Test: expose mechanism
  Test --> Decision: evidence survives
  Test --> Revision: rival survives
  Revision --> Claim: narrow or rebuild
  Decision --> [*]

Compact glossary

Verified frontier

Pending nodes whose dependency clauses and current guards are satisfied, making them candidates for scheduling.

Solution subgraph

A set of nodes sufficient to support the goal under the current AND/OR structure.

Repair cone

The smallest provenance-sensitive region that must reopen or reroute after support is invalidated.

Evidence receipt

A durable reference connecting a completion claim to an observed, typed postcondition.

Unknown outcome

A state in which an action may have produced an effect, but the controller cannot yet prove or disprove it.

Mission control

The deterministic runtime that validates graph state, computes readiness, schedules bounded work and directs recovery.

Operate the frontier, not the story

Long-horizon work becomes fragile when its state lives mainly in prose. A transcript can explain what agents said. A checklist can record which boxes were touched. A progress bar can count them. None of those representations, alone, tells the controller whether the goal still has a valid route.

Represent the mission as evidence-backed AND/OR obligations when alternatives, concurrency, interruption and selective recovery materially affect the outcome. Let models propose decompositions and local actions, then validate the graph mechanically. Compute the verified frontier from current world state. Treat completion as a receipt-backed claim. Give unknown outcomes a reconciliation branch. After failure, preserve supported regions and reopen only the repair cone.

The architecture decision is therefore conditional, not universal. Keep a checklist for a simple one-path procedure. Use a workflow state machine when branching is bounded and recovery is local. Adopt a dependency mission graph when the system must choose among routes and retain progress under disturbance. Add stronger simulation or human control when effects are consequential or goals resist formal completion.

The practical replacement for “79 per cent complete” is a more demanding operational statement: the goal remains viable, these nodes are ready, this evidence supports them, this route is selected, and this bounded region will reopen if support fails. That is progress a machine, an operator and an auditor can act on.