Epistemic Coverage Scan

When to Use

• Any multi-agent graph-traversal system where isolated or low-degree nodes risk being permanently skipped because no pheromone gradient points toward them.
• When EFE-driven (or any gradient-following) agents have converged locally and you need a backstop guarantee that the entire node set is eventually visited.
• When audit completeness matters — code review, security scans, dependency graphs — and a missed node is a missed vulnerability.

NOT for:

• Single-agent systems where the agent already maintains an explicit "to-visit" queue (a BFS/DFS frontier achieves the same guarantee deterministically).
• Dense, fully-connected graphs where every node is reachable via gradient within a few hops and isolation is structurally impossible.
• Real-time systems where a sudden long-range teleport disrupts locality assumptions in the surrounding architecture.

Core Concepts

Unseen set — {n : visit_counts[n] == 0 and n != current_position}. Maintained implicitly via GenerativeModel.visit_counts, a dict that is incremented in update_belief() on every observation. An agent's unseen set is agent-local; with social learning, multiple agents collectively saturate coverage faster but each tracks its own frontier.

Self-annealing scan probability — P_scan = |unseen| / |all_nodes|. No decay schedule parameter required. At initialization every node is unseen so P_scan ≈ 1.0 (minus the agent's starting position). As visits accumulate the probability falls monotonically. Once all nodes have been visited, |unseen| = 0 and the mechanism costs exactly zero probability mass per step.

Warm-up gate — scan is suppressed for total_steps <= 3. This prevents premature teleportation before EFE has had enough observations to form meaningful beliefs; the first few steps are spent seeding local beliefs via normal gradient following.

Innate vs adaptive layering — The scan fires before the EFE action is returned but after EFE has computed a local candidate. Priority order in _select_action():

1. Adaptive: epistemic teleport (EFE below teleport_threshold, global uncertainty dominates local max by factor 1.5x).
2. Innate: epistemic scan (unseen nodes exist, random draw beats P_scan, teleport to highest-uncertainty unseen node).
3. Adaptive: EFE softmax over local neighbors (default path).

Target selection within unseen set — max(unseen, key=lambda n: model.get_belief(n).uncertainty). All unseen nodes share the same prior Beta(1,1) so their uncertainty values are identical at first. Once social learning has pushed pheromone signals into some priors, the argmax selects the structurally most-uncertain candidate even before direct visit.

Implementation Pattern

# Inside ActiveInferenceAgent._select_action(medium) — after EFE candidate
# is computed, before returning:

WARM_UP_STEPS = 3

if agent.total_steps > WARM_UP_STEPS:
    all_nodes  = list(medium.graph.nodes())
    unseen     = [n for n in all_nodes
                  if model.visit_counts.get(n, 0) == 0
                  and n != agent.position]

    if unseen:
        scan_prob = len(unseen) / max(len(all_nodes), 1)   # self-annealing
        if rng.random() < scan_prob:
            # Among unseen, prefer highest posterior uncertainty
            target = max(unseen, key=lambda n: model.get_belief(n).uncertainty)
            return target, "epistemic_scan"

# Fall through to EFE-selected candidate
return efe_candidate, "efe_<action_type>"

Exact source location: soma/active_inference_agent.py lines 203-214, method ActiveInferenceAgent._select_action(self, medium: Medium).

Key invariants to preserve when porting:

• The unseen filter must exclude agent.position (the agent is already there).
• visit_counts must be updated in update_belief(), not in step(), so social-learning pheromone updates do not increment counts.
• The max(len(all_nodes), 1) guard prevents ZeroDivisionError on empty graphs.
• Action label "epistemic_scan" is distinct from "epistemic_teleport" so callers can log and instrument the two paths separately.

Supporting signatures from GenerativeModel (soma/generative_model.py):

# Belief retrieval — returns Beta(1,1) prior for unseen nodes
model.get_belief(node_id: str) -> NodeBelief
    # NodeBelief.uncertainty == Var[Beta(α,β)] = αβ / ((α+β)²(α+β+1))

# Visit tracking — called automatically inside update_belief()
model.visit_counts: Dict[str, int]   # {node_id: number_of_direct_observations}

# Novelty score (not used in scan target selection, used in EFE)
model.novelty(node_id: str) -> float  # 1 / (1 + visits)

# Global highest-uncertainty node (used by epistemic_teleport, not scan)
model.highest_uncertainty_node(exclude: Optional[set]) -> Optional[str]

Key References

• Friston, K. (2010). The free-energy principle: a unified brain theory? Nature Reviews Neuroscience, 11(2), 127-138. — Foundational paper establishing epistemic foraging as free-energy minimization.

• Parr, T., & Friston, K. J. (2019). Generalised free energy and active inference. Biological Cybernetics, 113(5), 495-513. — Formalizes the innate vs adaptive distinction in active inference agents; epistemic scan maps to the "prior preference for information gain" term.

• Hansen, J. L., & Ghrist, R. (2021). Opinion dynamics on discourse sheaves. SIAM Journal on Applied Mathematics, 81(5), 2033-2060. — Convergence proof for sheaf Laplacian diffusion on graphs; establishes why gradient-following alone fails on disconnected components (motivates innate scan).

• SOMA soma/active_inference_agent.py — Reference implementation. ActiveInferenceAgent._select_action() lines 203-214; GenerativeModel (soma/generative_model.py) for visit_counts, get_belief(), novelty().