Skip to content

Pursuit 3-Agent Shield Infeasibility

The 3-agent Pursuit shield can be infeasible even after the safety label was relaxed to require both intruders to be in the goal region at the same time.

Observation

For the saved 3-agent learned shield bundle at exports/gridworlds/pursuit/3/shield/transition_shield_bundle.pkl, the reset state has:

  • guard at (5, 4), intruders at (1, 2) and (1, 6)
  • immediate unsafe probability 0.0 for every guard action
  • eventual unsafe demand 1.0 for every guard action at every OM level
  • no missing transition coverage and no partial state-action coverage
  • no almost-sure safe states in the induced MDP

So the failure is not caused by the label accidentally marking a single intruder in goal as unsafe. The label is doing the intended "both intruders in goal" check.

Why This Happens

TransitionShield constrains the probability of eventually reaching an unsafe state, not the one-step probability of entering unsafe on the next transition.

In default 3-agent Pursuit, the guard can influence positions for one step, but the environment does not give the guard a durable capture/blocking mechanism:

  • collisions do not remove or freeze intruders
  • agents may share cells after simultaneous movement
  • the public state has no captured/dead intruder state
  • the default experiment uses time-free shield semantics, so the hidden episode cap is not part of the reachability calculation

Under an opponent model with positive support for intruder actions, the intruders retain positive probability of continuing to move toward the two goal entries. On an infinite-horizon reachability objective, repeated positive chances to eventually put both intruders in the goal region drive the full-breach probability to 1.0. The one-step event can be blocked at reset, while the eventual event remains unavoidable.

This is the same broad distinction documented in budget-augmented-shielding.md: max_risk is an eventual unsafe budget, not an immediate hazard threshold.

Implications

Lowering the hard label from "any intruder reaches goal" to "all intruders reach goal simultaneously" makes the immediate objective less strict, but it does not create an almost-sure safe recurrent region. With the current dynamics, a max_risk=0.2 reset budget is structurally infeasible because the best eventual risk is 1.0.

Repair Options

The clean repair depends on the intended interpretation of Pursuit:

  • If Pursuit should model durable pursuit/capture, add public capture state and transition dynamics that remove, freeze, or otherwise neutralize intruders after guard collision. Then the guard can create a closed safe region.
  • If the intended shield is only a local "do not allow both intruders to enter now" filter, add an immediate-risk shield mode for this environment instead of using eventual reachability VI.
  • If the intended objective is finite-horizon safety, build a time-augmented or remaining-budget graph for Pursuit. Hidden max_steps cannot affect the current time-free shield calculation.
  • If the current time-free dynamics are intentional, max_risk must be near 1.0 for 3-agent Pursuit; this weakens shielding and mostly removes the intended training constraint.

Capture-Terminal Dynamics Follow-Up

If the intended Pursuit dynamics are "agents cannot share cells" and "guard capture terminates the episode", modifying only one saved graph is not enough. The shield can be sound only when the runtime environment, legal/WM graph, true transition graph, and cached shield bundles all use the same transition semantics.

Pursuit now defaults terminates_after_collision=True, and the pursuit WM, OM, experiment, and exact-dynamics notebooks pass the flag explicitly. This is the minimal runtime switch for making same-cell collisions terminal in the current implementation. It is enough only if every graph/bundle artifact used by training is regenerated from env factories with the same flag. Old wm/env_transition_graph.pkl, wm/legal_joint_graph.pkl, true_shield/true_transition_graph.pkl, and shield/transition_shield_bundle.pkl artifacts still encode the previous non-terminal collision semantics until rebuilt.

Important implementation details:

  • A capture transition should lead to a represented safe terminal state, usually as a self-looping terminal graph node. TransitionShield.step(...) still inspects the post-step state before returning, even if the base environment emitted termination flags.
  • If the terminal observation does not contain a distinct terminal/captured state, the graph and environment must still agree exactly on the observation returned after capture. Otherwise the shield may see missing coverage or an infeasible normal state after a terminal transition.
  • Simply deleting same-cell nodes changes the dynamics only if simultaneous collisions are redirected to the same terminal outcome that the environment returns. If the graph instead bounces or drops those transitions, it is no longer modelling capture termination.

With capture-terminal dynamics, infinite-horizon feasibility is plausible for both 2-agent and 3-agent Pursuit because repeated play no longer gives intruders unbounded chances after a capture. It is not a proof of feasibility at a chosen budget, though:

  • For 2 agents, feasibility should hold from the default start if every unsafe goal entry can either be blocked or captured before/at entry under the shield's opponent model.
  • For 3 agents, feasibility depends on whether one guard can keep the probability of simultaneous dual-goal entry below max_risk before either intruder is captured. The two-gap layout can still make low budgets infeasible under some opponent policies, even with terminal capture.