RoboRACE-Net-M / trackD.py
Nabidnur's picture
RACE-Net-M weights, card and code
18ade57 verified
Raw History Blame Contribute Delete
20.4 kB
"""Track D — Byzantine cooperative maze exploration (mobile-robot swarm, numpy).
N robots must each reach a common goal in an unknown grid maze. A robot senses its 8
neighbouring cells exactly and broadcasts what it sensed; everybody fuses the broadcasts into
a belief map and re-plans every step (shortest path, unknown cells optimistically free).
F robots are Byzantine: they explore like everyone else but corrupt what they broadcast.
Fusion rules (per receiver; a robot's own direct observations always override peers)
solo ignore peers (single-robot exploration baseline)
trust_all naive map merging: the latest claim about a cell wins
majority per-cell majority vote over peers
wmsr_trim W-MSR-style trimming (LeBlanc et al. 2013): drop F 'wall' and F 'free' votes per cell (F known)
eigentrust EigenTrust (Kamvar et al. 2003): global trust from pairwise agreement, receiver pre-trusted
dawid_skene unanchored two-coin Dawid-Skene EM over the cells (1979)
reputation beta-reputation (Josang & Ismail 2002): weight each peer by log-odds of its
verified accuracy, clipped at 0 -> liars are DISCARDED
race_map receiver-anchored channel estimation (this repo): Bayesian model averaging over
each peer's two-coin channel, verified on the receiver's own cells; claims enter
as signed log-likelihood ratios -> a consistent liar is INVERTED and used, a
wall-inventor keeps only the weight of its 'free' claims, a random peer
contributes nothing; a Bayes-factor test separates a sleeper's two epochs
race_net_m RACE-Net-M (this repo): the same anchored channel estimation, LEARNED from simulated swarms
with random two-coin liars (robotics.swarm.racenet_m)
... + reach-repair planner variant: when the fused map says the goal is unreachable, un-believe only the
claimed walls that enclose the goal instead of dropping every peer
REF oracle knows who lies (reference, not ranked)
"Verified" = cells the receiver sensed itself that the peer also reported: the receiver's own
sensor is the anchor (RACE's "I know I am honest"), so no labels and no majority are needed.
Score = SPL (Success weighted by Path Length, Anderson et al. 2018), averaged over honest robots;
a robot fails if it needs more than 2.5x its optimal path length + 10 steps.
"""
from __future__ import annotations
from collections import deque
import numpy as np
RACE_TAU = 1.0 # log-odds needed before race_map blocks a cell (chosen on development mazes, seeds 0-7)
ATTACKS_D = ("none", "false_walls", "false_free", "invert", "random", "collude", "sleeper")
BASELINES_D = ("solo", "trust_all", "majority", "wmsr_trim", "eigentrust", "dawid_skene", "reputation")
MV = " + reach-repair"
OURS_D = ("race_map", "race_net_m", "race_map" + MV, "race_net_m" + MV)
ABLATION_D = ("reputation" + MV, "eigentrust" + MV, "majority" + MV) # the same planner fallback on baselines
METHODS_D = BASELINES_D + OURS_D + ABLATION_D + ("REF oracle",)
# Reachability repair (ours): the task guarantees that the goal can be reached. When the fused map says it cannot,
# some believed wall around the goal must be a lie. The standard planner then drops every peer and plans on the robot's
# own observations; the repair instead keeps the fused map and only un-believes the claimed walls that enclose the
# goal's reachable region, layer by layer (at most REPAIR_LAYERS), until the robot is connected to the goal.
# NET_TAU was chosen on development mazes (scripts/tune_trackD.py); the benchmark seeds were not used.
NET_TAU, REPAIR_LAYERS = 2.0, 6
NB8 = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 0), (0, 1), (1, -1), (1, 0), (1, 1)]
NB4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]
def make_maze(w=12, h=12, loops=0.08, seed=0):
"""Perfect maze by randomised DFS, then `loops` of the interior walls removed (alternative routes)."""
rng = np.random.default_rng(seed)
G = np.ones((2 * h + 1, 2 * w + 1), np.int8)
seen = np.zeros((h, w), bool)
stack = [(0, 0)]
seen[0, 0] = True
G[1, 1] = 0
while stack:
r, c = stack[-1]
nb = [(r + dr, c + dc) for dr, dc in NB4 if 0 <= r + dr < h and 0 <= c + dc < w and not seen[r + dr, c + dc]]
if not nb:
stack.pop()
continue
nr, nc = nb[rng.integers(len(nb))]
G[r + nr + 1, c + nc + 1] = 0
G[2 * nr + 1, 2 * nc + 1] = 0
seen[nr, nc] = True
stack.append((nr, nc))
inner = [(r, c) for r in range(1, 2 * h) for c in range(1, 2 * w) if G[r, c] == 1 and (r % 2) != (c % 2)]
for k in rng.choice(len(inner), int(loops * len(inner)), replace=False):
G[inner[k]] = 0
return G
def bfs(free, src):
"""Distance field from src over cells where free is True (4-connected)."""
H, W = free.shape
dist = np.full((H, W), -1, np.int32)
dist[src] = 0
q = deque([src])
while q:
r, c = q.popleft()
d = dist[r, c] + 1
for dr, dc in NB4:
rr, cc = r + dr, c + dc
if 0 <= rr < H and 0 <= cc < W and free[rr, cc] and dist[rr, cc] < 0:
dist[rr, cc] = d
q.append((rr, cc))
return dist
def _eigentrust(own, claims, i, alpha=0.15, iters=30):
"""EigenTrust (Kamvar, Schlosser & Garcia-Molina 2003). Local trust c[j,k] = max(sat - unsat, 0) over the cells
both j and k reported (the receiver uses its own sensed cells), row-normalised; the receiver is the only
pre-trusted peer. Returns the global trust vector (discard-only: trust is never negative)."""
n = len(claims)
V = claims.astype(np.int16).copy()
V[i] = own # the receiver rates others with what it sensed itself
C = np.zeros((n, n))
for j in range(n):
for k in range(n):
if j != k:
both = (V[j] >= 0) & (V[k] >= 0)
agree = int(np.sum(V[j][both] == V[k][both]))
C[j, k] = max(2 * agree - int(both.sum()), 0)
p = np.zeros(n)
p[i] = 1.0
rows = C.sum(1, keepdims=True)
C = np.where(rows > 0, C / np.maximum(rows, 1e-9), p[None])
t = p.copy()
for _ in range(iters):
t = (1 - alpha) * C.T @ t + alpha * p
t[i] = 0.0
return t / max(t.max(), 1e-9)
def _dawid_skene(own, claims, i, iters=25):
"""Unanchored two-coin Dawid-Skene EM over the map cells (Dawid & Skene 1979): every robot, the receiver
included, is one annotator; initialised with the majority vote. Returns per-cell log-odds of 'wall'."""
V = claims.astype(np.int16).copy()
V[i] = own
has = V >= 0
m = has.any(0)
if not m.any():
return np.zeros(own.shape)
X, Hm = (V[:, m] == 1).astype(float), has[:, m].astype(float) # [n, cells]
q = (X * Hm).sum(0) / np.maximum(Hm.sum(0), 1)
for _ in range(iters):
pi = np.clip(q.mean(), 0.05, 0.95)
t11 = np.clip(((X * Hm) @ q + 1) / (Hm @ q + 2), 0.02, 0.98) # P(says wall | wall)
t00 = np.clip((((1 - X) * Hm) @ (1 - q) + 1) / (Hm @ (1 - q) + 2), 0.02, 0.98) # P(says free | free)
ll = (np.log(pi / (1 - pi))
+ (Hm * (X * np.log(t11 / (1 - t00))[:, None] + (1 - X) * np.log((1 - t11) / t00)[:, None])).sum(0))
q = 1 / (1 + np.exp(-np.clip(ll, -30, 30)))
score = np.zeros(own.shape)
score[m] = np.clip(ll, -30, 30)
return score
def _acc_weights(own, claims, i, method, byz):
"""One weight per peer (majority / reputation / oracle)."""
n = len(claims)
lam = np.zeros(n)
for j in range(n):
if j == i:
continue
if method == "REF oracle":
lam[j] = 0.0 if byz[j] else 2.0
elif method == "majority":
lam[j] = 1.0
else: # beta reputation: verified accuracy, discard-only
both = (own >= 0) & (claims[j] >= 0)
a = int(np.sum(own[both] == claims[j][both]))
acc = (a + 1.2) / (int(both.sum()) + 2.0) # Beta prior: an unverified peer is mildly trusted
lam[j] = max(float(np.log(acc / (1 - acc))), 0.0)
return lam
# Channel prior: a peer's two-coin channel (t00 = P(says free | free), t11 = P(says wall | wall)) lies on a
# 7x7 grid; 60% prior mass on the honest type, the rest uniform. No attack-specific types.
_LEV = np.array([0.03, 0.2, 0.4, 0.5, 0.6, 0.8, 0.97])
_T00, _T11 = [x.ravel() for x in np.meshgrid(_LEV, _LEV, indexing="ij")]
_LOGPRIOR = np.log(np.where((_T00 == 0.97) & (_T11 == 0.97), 0.6, 0.4 / (len(_T00) - 1)))
def _posterior(n):
"""n[truth][claim] verified counts -> (posterior over channel types, log marginal likelihood)."""
ll = (_LOGPRIOR + n[0, 0] * np.log(_T00) + n[0, 1] * np.log1p(-_T00)
+ n[1, 1] * np.log(_T11) + n[1, 0] * np.log1p(-_T11))
m = ll.max()
w = np.exp(ll - m)
return w / w.sum(), m + np.log(w.sum())
def _llr(w):
"""Bayes-averaged evidence of a claim: [llr(claim free), llr(claim wall)] = log P(c | wall) / P(c | free)."""
p1w, p1f = float(w @ _T11), float(w @ (1 - _T00))
return np.array([np.log((1 - p1w) / (1 - p1f)), np.log(p1w / p1f)])
def _counts(own, claim, mask):
n = np.zeros((2, 2))
if mask.any():
np.add.at(n, (own[mask], claim[mask]), 1.0)
return n
def _race_score(own, claims, stamp, i, t, window):
"""Receiver-anchored channel estimation on a map. For every peer, the receiver compares the peer's
broadcasts with the cells it sensed ITSELF (its anchor) and infers the peer's two-coin channel by
Bayesian model averaging. Each claim then enters as a signed log-likelihood ratio: an inverter's
claims are flipped and used, a wall-inventor keeps only the weight of its 'free' claims, a random
peer averages out to zero evidence. Sleepers: if a Bayes-factor test says the recent `window` steps
follow a different channel than the past, the two epochs are scored with separate channels."""
score = np.zeros(own.shape)
seen = own >= 0
for j in range(len(claims)):
if j == i:
continue
has = claims[j] >= 0
rec = has & (stamp[j] >= t - window)
old = has & ~rec
n_rec, n_old = _counts(own, claims[j], rec & seen), _counts(own, claims[j], old & seen)
w_all, m_all = _posterior(n_rec + n_old)
w_rec, m_rec = _posterior(n_rec)
w_old, m_old = _posterior(n_old)
if m_rec + m_old - m_all > 3.0: # log Bayes factor for "the channel changed"
score[rec] += _llr(w_rec)[claims[j][rec]]
score[old] += _llr(w_old)[claims[j][old]]
else:
score[has] += _llr(w_all)[claims[j][has]]
return score
def wall_logodds(own, claims, stamp, i, method, byz, t=0, window=30):
"""Per-cell log-odds that a cell is a wall, from the peers' broadcasts (methods that produce evidence)."""
if method == "race_map":
return _race_score(own, claims, stamp, i, t, window)
if method == "race_net_m":
from robotics.swarm import racenet_m
return racenet_m.wall_logodds(own, claims, stamp, i, t, window)
raise ValueError(method)
def scores(own, claims, stamp, i, method, byz, t=0, window=30):
"""(per-cell evidence that the cell is a wall, threshold) for every fusion rule except solo / trust_all."""
n = len(claims)
vote = (claims == 1).astype(float) - (claims == 0).astype(float)
if method in ("race_map", "race_net_m"):
return wall_logodds(own, claims, stamp, i, method, byz, t, window), (RACE_TAU if method == "race_map" else NET_TAU)
if method == "wmsr_trim":
# W-MSR-style trimming (LeBlanc et al. 2013) per cell: drop up to F 'wall' and up to F 'free' votes
F = int(byz.sum()) # the number of Byzantine robots is assumed known
peers = np.arange(n) != i
nw, nf = (claims[peers] == 1).sum(0), (claims[peers] == 0).sum(0)
return np.maximum(nw - F, 0) - np.maximum(nf - F, 0).astype(float), 0.4
if method == "eigentrust":
return np.tensordot(_eigentrust(own, claims, i), vote, 1), 0.4
if method == "dawid_skene":
return _dawid_skene(own, claims, i), RACE_TAU
return np.tensordot(_acc_weights(own, claims, i, method, byz), vote, 1), 0.4
def belief(own, claims, stamp, i, method, byz, t=0, window=30, return_score=False):
"""Receiver i's map: -1 unknown, 0 free, 1 wall. Planning is optimistic (anything not believed 'wall' is
traversable), so only the wall threshold matters; race scores are log-likelihood ratios and need posterior
odds of about 3:1 before a cell is blocked."""
if method == "solo":
return (own, None) if return_score else own
n = len(claims)
if method == "trust_all":
st = np.where(np.arange(n)[:, None, None] == i, -1, stamp)
j = st.argmax(0)
B = np.take_along_axis(claims, j[None], 0)[0]
B = np.where(st.max(0) >= 0, B, -1)
score = None
else:
score, tau = scores(own, claims, stamp, i, method, byz, t, window)
B = np.where(score > tau, 1, np.where(score < -tau, 0, -1)).astype(np.int8)
B = np.where(own >= 0, own, B)
return (B, score) if return_score else B
def repair_field(own, B, goal, start, layers=None):
"""Distance-to-goal on the fused map after un-believing the claimed walls that enclose the goal (never walls the
robot sensed itself). Returns None if the robot is still disconnected after `layers` rounds."""
B = B.copy()
for _ in range(REPAIR_LAYERS if layers is None else layers):
d = bfs(B != 1, goal)
if d[start] >= 0:
return d
comp = d >= 0
edge = np.zeros_like(comp)
edge[1:, :] |= comp[:-1, :]
edge[:-1, :] |= comp[1:, :]
edge[:, 1:] |= comp[:, :-1]
edge[:, :-1] |= comp[:, 1:]
peel = edge & (B == 1) & (own != 1)
if not peel.any():
return None
B[peel] = -1
d = bfs(B != 1, goal)
return d if d[start] >= 0 else None
def episode(seed, attack="none", F=0, method="race_map", n=6, w=12, h=12, trace=None, sleeper_T=40,
channels=None, snaps=None, snap_p=0.0):
"""channels: optional {robot: (t00, t11, t_change)} parametric two-coin liars (used to train RACE-Net-M; then
`attack` is ignored for those robots). snaps: list that receives (own, claims, stamp, i, t) snapshots."""
mv = method.endswith(MV)
fuse = method.replace(MV, "")
rng = np.random.default_rng(seed)
srng = np.random.default_rng(seed + 7_000_003) if snaps is not None else None
G = make_maze(w, h, seed=seed)
H, W = G.shape
free_cells = np.argwhere(G == 0)
goal = tuple(free_cells[rng.integers(len(free_cells))])
dgoal = bfs(G == 0, goal)
far = free_cells[dgoal[free_cells[:, 0], free_cells[:, 1]] >= np.percentile(dgoal[G == 0], 55)]
pos = [tuple(far[k]) for k in rng.choice(len(far), n, replace=False)]
byz = np.zeros(n, bool)
byz[rng.choice(n, F, replace=False)] = True
if channels is not None:
byz[:] = False
byz[list(channels)] = True
opt = np.array([dgoal[p] for p in pos])
budget = (2.5 * opt + 10).astype(int) # per-robot deadline: 2.5x its optimal path + 10 steps
T = int(budget.max())
own = np.full((n, H, W), -1, np.int8) # each robot's direct observations
claims = np.full((n, H, W), -1, np.int8) # latest broadcast of each robot about each cell
stamp = np.full((n, H, W), -1, np.int32)
steps = np.zeros(n, int)
done = np.zeros(n, bool)
wander = [None] * n
ring = [(goal[0] + dr, goal[1] + dc) for dr, dc in NB4 if G[goal[0] + dr, goal[1] + dc] == 0]
for t in range(T):
# ---- sense + broadcast
for i in range(n):
for dr, dc in NB8:
r, c = pos[i][0] + dr, pos[i][1] + dc
v = G[r, c]
own[i, r, c] = v
say = v
if byz[i] and channels is not None:
t00, t11, t_change = channels[i]
if t >= t_change and rng.random() > (t11 if v == 1 else t00):
say = 1 - v
elif byz[i]:
a = attack
if a == "sleeper":
a = "none" if t < sleeper_T else "invert"
if a == "invert":
say = 1 - v
elif a == "false_walls" and v == 0 and rng.random() < 0.6:
say = 1
elif a == "false_free" and v == 1 and rng.random() < 0.6:
say = 0
elif a == "random":
say = int(rng.integers(2))
claims[i, r, c] = say
stamp[i, r, c] = t
if byz[i] and attack == "collude": # the bloc walls off the goal, consistently and every step
for r, c in ring:
claims[i, r, c] = 1
stamp[i, r, c] = t
# ---- move
beliefs = {}
for i in range(n):
if byz[i]: # liars keep exploring (random reachable targets)
if wander[i] is None or pos[i] == wander[i]:
wander[i] = tuple(free_cells[rng.integers(len(free_cells))])
d = bfs(G == 0, wander[i])
else:
if done[i] or steps[i] >= budget[i]:
continue
if snaps is not None and srng.random() < snap_p:
snaps.append((own[i].copy(), claims.copy(), stamp.copy(), i, t))
B, score = belief(own[i], claims, stamp, i, fuse, byz, t, return_score=True)
beliefs[i] = B
d = bfs(B != 1, goal)
if d[pos[i]] < 0: # the fused map says the goal is unreachable
d = repair_field(own[i], B, goal, pos[i]) if mv else None
if d is None: # standard: fall back to the robot's own observations
d = bfs(own[i] != 1, goal)
r, c = pos[i]
best = min(((d[r + dr, c + dc], (r + dr, c + dc)) for dr, dc in NB4
if G[r + dr, c + dc] == 0 and d[r + dr, c + dc] >= 0), default=None)
if best is not None and best[0] < d[r, c] or (best is not None and d[r, c] < 0):
pos[i] = best[1]
if not byz[i]:
steps[i] += 1
elif not byz[i]:
steps[i] += 1 # waiting also costs time
if not byz[i] and pos[i] == goal:
done[i] = True
if trace is not None:
trace.append({"pos": list(pos), "done": done.copy(), "beliefs": {k: v.copy() for k, v in beliefs.items()}})
if (done | (steps >= budget))[~byz].all():
break
honest = ~byz
spl = np.where(done, opt / np.maximum(steps, np.maximum(opt, 1)), 0.0)[honest]
return {"spl": float(spl.mean()), "success": float(done[honest].mean()),
"ratio": float(np.mean((steps / np.maximum(opt, 1))[honest & done])) if (honest & done).any() else float("nan"),
"G": G, "goal": goal, "byz": byz}
def _cell(args):
seed, attack, F, method = args
r = episode(seed, attack, F, method)
return {"track": "D", "attack": attack, "liars": F, "f": round(F / 6, 2), "subset": seed, "method": method,
"acc": r["spl"], "success": r["success"], "ratio": r["ratio"]}
def available_methods():
from robotics.swarm import racenet_m
return tuple(m for m in METHODS_D if "race_net_m" not in m or racenet_m.available())
def run(n_mazes=20, Fs=(1, 2, 3, 4), attacks=ATTACKS_D, procs=2, only=None, first_seed=1000):
"""only: optional set of method names (cells are deterministic, so new methods can be added to saved rows)."""
jobs = [(first_seed + s, a, F, m) for a in attacks for F in ((0,) if a == "none" else Fs)
for s in range(n_mazes) for m in available_methods() if only is None or m in only]
if procs > 1:
from multiprocessing import Pool
with Pool(procs) as p:
return p.map(_cell, jobs, chunksize=8)
return [_cell(j) for j in jobs]