"""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]