Generalizable Multi‑Agent Planning from Signal Temporal Logic Specifications via Diffusion

Notation. We consider valid trajectories as polylines $\tau_{s_i}=\{\mathbf{x}^{(i)}_t\}_{t=0}^{T-1}\subset\mathbb{R}^2$ for $M$ successful agents over $T$ steps.

Path Overlap (↓)

Occupancy grid. Overlay a uniform grid of resolution $r_{\text{grid}}=0.3\,\mathrm{m}$ on the workspace $[x_{\min},x_{\max}]\times[y_{\min},y_{\max}]$ (e.g., $x_{\max}=y_{\max}=6$, $x_{\min}=y_{\min}=-0.5$). For agent $i$, the binary occupancy mask is \[ O^{(i)}_{u,v}=\mathbf{1}\!\left[(u,v)\in \text{cells}\bigl(\tau_{s_i}\bigr)\right]. \] The (normalised) overlap among $M$ agents is \[ \text{Overlap} \;=\; \frac{\displaystyle\sum_{u,v}\Bigl(\bigwedge_{i=1}^{M}O^{(i)}_{u,v}\Bigr)} {\displaystyle\sum_{u,v}\Bigl(\bigvee_{i=1}^{M}O^{(i)}_{u,v}\Bigr) + \varepsilon}, \qquad \varepsilon=10^{-6}, \] where $\wedge$/$\vee$ denote logical AND/OR over agents. $\text{Overlap}\!\approx\!1$ means identical footprints; $\approx\!0$ means disjoint footprints.

Path Entropy (↑)

From $O^{(i)}_{u,v}$ build the cumulative grid \[ \mathrm{occ}_{u,v}=\sum_{i=1}^{M}\sum_{t=0}^{T-1}\mathbf{1}\!\left[(u,v)\in \text{cell}(\mathbf{x}^{(i)}_t)\right], \] and the visited set $\mathcal V=\{(u,v)\mid \mathrm{occ}_{u,v}>0\}$ with $V=|\mathcal V|$. Define \[ p_{u,v}=\frac{\mathrm{occ}_{u,v}}{\sum_{(a,b)\in\mathcal V}\mathrm{occ}_{a,b}},\quad (u,v)\in\mathcal V, \] and report the normalised Shannon entropy \[ \hat H \;=\; -\frac{1}{\log V}\sum_{(u,v)\in\mathcal V} p_{u,v}\log p_{u,v}. \]

Pairwise Distance & Cluster Statistics

Distances. For each pair $(i,j)$, compute the discrete Fréchet distance $D_{ij}=d_F\!\bigl(\tau_{s_i},\tau_{s_j}\bigr)$, forming a symmetric matrix $D\in\mathbb{R}^{M\times M}$. The mean pairwise distance (reported as “Mean Pairwise Dist. (↑)”) is \[ \overline{D} \;=\; \frac{1}{M^2}\sum_{i=1}^{M}\sum_{j=1}^{M} D_{ij}, \] where higher values indicate more separation among successful plans.

Graph & clusters. Build an undirected graph $G=(V,E)$ with $V=\{1,\ldots,M\}$ and \[ (i,j)\in E \;\Longleftrightarrow\; 0 < D_{ij}\le \Delta\tau,\quad \Delta\tau = 1\,\mathrm{m}. \] Let $\text{ConnComp}(G)$ be the connected components, $k=|\text{ConnComp}(G)|$, and $C_c$ a component. We report:

• Num. Clusters (↑): $k$ (larger $\Rightarrow$ more distinct route groups).
• Max Cluster Fraction (↓): $\displaystyle\max_c |C_c|/M$ (smaller $\Rightarrow$ no single dominant route).
• Agents per Cluster (↓): $\displaystyle \frac{1}{k}\sum_c |C_c|$ (smaller $\Rightarrow$ more evenly split).

Legend: “↑” higher is better; “↓” lower is better. These metrics complement success/safety to characterise diversity.