# Buffered Voronoi Safety Projection

- ID: 746
- Canonical URL: https://synthcore.org/idea/746/buffered-voronoi-safety-projection
- API JSON: https://synthcore.org/api/idea/746.json
- API Markdown: https://synthcore.org/api/idea/746.md
- Verification status: unverified
- Source: [arXiv:2607.11403](https://arxiv.org/abs/2607.11403)
- Category: dynamics
- Solves: stability, accuracy, scalability
- ML areas: rl, graph-nn, world-model, training-dynamics
- Math tags: control-theory, optimization, geometry, dynamical-systems, linear-algebra
- Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10

## Idea description

Add a decentralized safety layer to a multi-agent neural policy or learned world model. Each agent first predicts an action or short trajectory, then projects its proposal into a half-space defined by each neighbor's announced trajectory and a positive buffer, avoiding a centralized nonconvex collision solve. Use Jacobi or Gauss-Seidel iterations when agents mutually revise their predicted trajectories.

## Mathematical statement

Let agent i have predicted position p_i in R^d and neighbor j announce position p_j^a. Define the separation vector q_{ij}=p_i^a-p_j^a, its unit normal n_{ij}=q_{ij}/(||q_{ij}||_2+epsilon), and required clearance r_{ij}>0. A buffered Voronoi half-space is n_{ij}^T(p_i-p_j^a)>=r_{ij}, equivalently n_{ij}^T p_i>=n_{ij}^T p_j^a+r_{ij}. The agent's neural proposal z_i is projected onto all local half-spaces by solving min_p 1/2||p-z_i||_2^2 subject to these inequalities. For a horizon H, impose the inequality at every predicted time t. Let F be the map from announced peer trajectories to the next local solutions; decentralized iteration converges locally when the induced cross-agent Jacobian G=partial F/partial p^a satisfies rho(G)<1, where rho denotes spectral radius. Jacobi uses all old announcements, while Gauss-Seidel substitutes newly computed trajectories immediately.

## Key formulas

- $$q_{ij}^{k}=p_i^{a,k}-p_j^{a,k},\qquad n_{ij}^{k}=\frac{q_{ij}^{k}}{\|q_{ij}^{k}\|_2+\varepsilon},\qquad (n_{ij}^{k})^\top(p_i^{k+1}-p_j^{a,k})\ge r_{ij}.$$
- $$p_i^{k+1}=\arg\min_{p}\frac{1}{2}\|p-z_i\|_2^2\quad\text{s.t.}\quad (n_{ij}^{k})^\top p\ge (n_{ij}^{k})^\top p_j^{a,k}+r_{ij},\ \forall j\in\mathcal T_i.$$
- $$p^{a,k+1}=F(p^{a,k}),\qquad \|p^{a,k+1}-p^\star\|\le \|G\|\,\|p^{a,k}-p^\star\|,\qquad \rho(G)<1\ \Rightarrow\ \text{local convergence}.$$
- $$r_{ij}=d_{\mathrm{safe}}+v_{\mathrm{rel},ij}\tau+\beta\sigma_{ij}.$$

## Implementation notes

1) Integration point: use this as an action shield after a decentralized graph policy. Each agent i receives its local observation and neighbor predictions, produces a nominal velocity or displacement z_i with a GNN or MLP, rolls it forward for H steps, and applies the projection independently at each time step. The announced trajectory is the previous iteration's trajectory; the projected trajectory is broadcast to neighbors. 2) Pseudocode: initialize all announced trajectories p_i^a from the policy; for k=0,...,K-1, compute q_ij and n_ij for every local threat edge, construct the half-space right-hand side n_ij^T p_j^a+r_ij, solve the small Euclidean projection QP for each agent, and replace p_i^a by the result. In Jacobi mode all agents use iteration-k announcements; in Gauss-Seidel mode process agents in a fixed order and immediately broadcast each new result. Execute only the first action, then replan. 3) Computed from the mechanism: half-space normals, local projection QPs, and the safety buffer. Estimate empirically: the Jacobian G by finite differences of the decentralized update map, its spectral radius, and prediction uncertainty sigma_ij from an ensemble or recent residuals. 4) First cheap experiment: train five agents with a two-layer graph policy on 2-D particle navigation, comparing no shield, centralized pairwise projection, buffered Jacobi, and buffered Gauss-Seidel. Sweep K and r. The quantitative prediction is a sharp practical transition: for fixed coupling, violation probability should fall to approximately zero once r exceeds the maximum unmodeled relative displacement, while iteration residuals should decay geometrically when the estimated rho(G)<1 and fail to decay when rho(G)>1. Measure whether the observed convergence boundary agrees with rho(G)=1 within 20%.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.