Download trackD.py from Nabidnur/RoboRACE-Net-M: direct link, hf CLI and curl.
- Browser
- Download file 20.4 kB
-
https://huggingface.co/Nabidnur/RoboRACE-Net-M/resolve/main/trackD.py
- Command line
-
hf download hf://Nabidnur/RoboRACE-Net-M/trackD.py
-
curl -L -o trackD.py https://huggingface.co/Nabidnur/RoboRACE-Net-M/resolve/main/trackD.py
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] | |