betaFeedback

WorksComputer Science

Capability Composition in Heterogeneous Teams via Barrier-Guided Diffusion Sampling

Abstract

The agents in a heterogeneous team can cooperate to accomplish tasks that exceed their individual capabilities. The team trajectories for a cooperative task can be generated by a generative model, provided that the model has been trained on demonstrations of the agents cooperating. Yet, demonstrations of cooperation are costly and may not exist for tasks that the team has never performed. The conditions under which the agents can combine their capabilities, however, are physical properties of the team and are known before any demonstration is collected. We encode the conditions as constraints on the team trajectories, and we enforce the constraints while sampling from generative models trained on demonstrations of each agent alone. We prove that the proposed method can generate every team trajectory that satisfies the constraints, although the demonstrations contain no cooperation. Hence the constraints determine which team trajectories can be generated, and the demonstrations determine how likely each team trajectory is. Numerical results on two cooperative tasks show the effectiveness of the method, which generates cooperative team trajectories that satisfy the constraints and requires no retraining when agents join or leave the team. Finally, we implement the method on a multi-robot testbed.

Introduction

Cooperation allows the agents in a team to accomplish tasks that exceed their individual capabilities. Cooperation in multi-agent teams has long been studied, from the allocation and scheduling of tasks [1, 2] to the control of several robots acting on a common object [3, 4]. Existing methods assume that the capabilities of the team are specified in advance, together with the conditions under which each capability can be used. The capabilities that a task requires, however, depend on the environment where the agents are deployed, and the environment is often unknown when the agents are trained. The task may then require a capability that no agent has alone, and that the agents obtain only by combining their individual capabilities. Hence the required cooperation can be neither specified nor demonstrated in advance, and generating cooperative behaviors for the task remains a challenge.

Generative models, and diffusion models in particular, are effective methods to generate the trajectories of an agent [5, 6] or of a team [7, 8], provided that the demonstrations contain the desired behavior. To overcome this limitation, we observe that the conditions under which the agents can combine their capabilities follow from the physics of the team. Hence the conditions can be written as constraints on the team trajectories without any demonstration. We then sample the team trajectories from generative models trained on demonstrations of each agent alone, and we impose the constraints during sampling using a guidance method [5, 9]. This results in a method to sample cooperative team trajectories from models pre-trained on non-cooperative demonstrations.

Related work. Task allocation and scheduling decide which agent performs which task and when [1, 2], and a trajectory planner then realizes the decision. We sample the trajectories directly from diffusion models and read the pattern of cooperation off the result, with nothing computed in advance. One line of multi-agent diffusion planners trains on demonstrations of cooperation where they exist [7, 8], and reproduces only the cooperation those demonstrations contain. Another trains on single-robot data and reconciles the resulting plans by search [10] or by projection [11]. These approaches combine constraints by intersection, as for collision avoidance. We combine them by union, because cooperation admits configurations that no agent reaches alone. Cooperation is available only while the agents are physically arranged for it, and has to be encoded as a constraint that holds at every timestep of a trajectory. Control barrier functions [12] (barriers, for short) encode such constraints. A barrier keeps a trajectory inside the set it defines. Boolean combinations of barriers give intersections and unions of the admissible sets [13, 14]. On the generative side, barriers have been used to keep diffusion samples inside a safe set [15] and to guide sampling with a constricting condition that tightens as noise falls [16]. Barriers also make flow-matching samplers safe [17, 18]. In multi-agent systems, guidance can be distributed, so that each agent computes its own Lyapunov-based guidance input [19].

Contributions. Our contributions are as follows. First, we formulate cooperative trajectory generation without demonstrations of cooperation as barrier-guided diffusion sampling, with constraints that encode the individual capabilities of the agents and the cooperative ones. Second, we propose a scheme in which the scores trained independently for each agent are summed into a product prior, and we prove that the sum is the exact score of that product at every noise level, since the densities of different agents depend on disjoint sets of variables. Third, we prove that the sampler can generate every team trajectory satisfying the constraints with nonzero probability and, when its guidance succeeds at every step, no other. Thus, every pattern of cooperation the constraints permit can be generated, and none is specified or pre-computed. Fourth, we demonstrate the method on a river crossing task, in simulation and on the Robotarium. The generated trajectories cross the river cooperatively, while sampling the prior alone yields agents that ignore each other and fail the task. We also show that the sampler requires no retraining to generate trajectories when agents join or leave the team. Finally, we consider a task in which cooperation also has to be timed. The sampler generates such trajectories without demonstrations, but less often than in the river crossing. Most failures of the sampler are consistent with local maxima of the barrier.

Problem formulation

Consider a team of NN agents with states xi∈Rnix_i \in\mathbb{R}^{n_i} and inputs ui∈Rmiu_i \in\mathbb{R}^{m_i}, evolving in discrete time as

xi(t+1)=fi(xi(t),ui(t)),t=0,…,T−1.(1)x_i(t+1) = f_i(x_i(t),u_i(t)), \quad t=0,\ldots,T-1. \tag*{(1)}

Let x=(x1,…,xN)∈Rnx=(x_1,\ldots,x_N) \in\mathbb{R}^{n} be the team state and u=(u1,…,uN)∈Rmu=(u_1,\ldots,u_N) \in\mathbb{R}^{m} the team input, with n=∑inin=\sum_i n_i and m=∑imim=\sum_i m_i. A team trajectory is the matrix X=(x(0),…,x(T))∈Rn×(T+1)X=(x(0),\ldots,x(T)) \in\mathbb{R}^{n\times(T+1)}, whose row block Xi∈Rni×(T+1)X_i \in\mathbb{R}^{n_i\times(T+1)} corresponds to the trajectory of agent ii.

Without cooperation, agent ii is constrained to the states and controls satisfying ci(xi,ui)≥0c_i(x_i,u_i) \ge0, where ci:Rni×Rmi→Rc_i:\mathbb{R}^{n_i}\times\mathbb{R}^{m_i}\to\mathbb{R} is a problem-dependent constraint function. Cooperation enlarges this set. Let ccoup,i:Rn×Rm→Rc_{\mathrm{coup},i}:\mathbb{R}^{n}\times\mathbb{R}^{m}\to\mathbb{R} describe the allowable configurations while cooperating with the rest of the team, so that the constraint set of agent ii is

Ai={(x,u):ci(xi,ui)≥0}∪{(x,u):ccoup,i(x,u)≥0}.(2)\mathcal{A}_i = \{(x,u):c_i(x_i,u_i)\ge0\}\cup\{(x,u):c_{\mathrm{coup},i}(x,u)\ge0\}. \tag*{(2)}

A team trajectory is admissible when the pair (x(t),u(t))(x(t),u(t)) lies in Ai\mathcal{A}_i for every agent ii and at all times. Cooperation enlarges the set of admissible states and controls, while the dynamics (1) remain the same whether or not ccoup,i≥0c_{\mathrm{coup},i}\ge0. Combining constraint sets is standard in the safe control literature [13]. Multi-robot planning combines them by intersection, since collision avoidance asks that a plan satisfy every agent’s constraints, and the feasible set may shrink [10]. In (2), instead, the second set depends on the other agents, so Ai\mathcal{A}_i admits configurations that agent ii cannot reach alone.

A task is specified by a problem-dependent function ctask:Rn×(T+1)→Rc_{\mathrm{task}}:\mathbb{R}^{n\times(T+1)}\to\mathbb{R}, and a team trajectory successfully completes the task when ctask(X)≥0c_{\mathrm{task}}(X)\ge0. We are interested in tasks that no agent can complete alone and the team can complete together. This motivates the following assumption.

Assumption 2.1. (Cooperation is necessary and sufficient to complete the task) Every admissible team trajectory XX that completes the task also satisfies ci(xi(t),ui(t))<0≤ccoup,i(x(t),u(t))c_i(x_i(t),u_i(t))<0\le c_{\mathrm{coup},i}(x(t),u(t)) for some agent ii and some time tt. Moreover, at least one such trajectory exists.

Assumption 2.1 requires that, along every trajectory that completes the task, some agent at some timestep violates its own constraint cic_i and is admissible only through the coupling constraint ccoup,ic_{\mathrm{coup},i}. Hence no trajectory in which every agent always satisfies its own constraint completes the task, that is, cooperation is necessary. Cooperation is also sufficient, because at least one admissible trajectory completes the task.

Example 1. (Crossing a river) Consider a team of two agents, a ground vehicle and a vessel, operating in a unit square environment divided across the middle by a river of width ww. The task is for the vehicle to reach a location across the river. The vehicle cannot enter the water and the vessel cannot leave it, so the vehicle cannot satisfy the task alone.

Let xi=(zi,qi)x_i = (z_i, q_i) be the position of agent ii, with ziz_i and qiq_i as its horizontal and vertical coordinates, respectively. Agent i=1i = 1 is the vehicle and agent i=2i = 2 is the vessel, with dynamics fi(xi,ui)=xi+uif_i(x_i, u_i) = x_i + u_i. The constraint functions are

c1(x1,u1)=min⁡(∣q1−12∣−w2,vmax⁡−∥u1∥),c_1(x_1,u_1)=\min\left(\left|q_1-\frac{1}{2}\right|-\frac{w}{2},v^{\max}-\lVert u_1\rVert\right),
c2(x2,u2)=min⁡(w2−∣q2−12∣,vmax⁡−∥u2∥),c_2(x_2,u_2)=\min\left(\frac{w}{2}-\left|q_2-\frac{1}{2}\right|,v^{\max}-\lVert u_2\rVert\right),
ccoup,1(x,u)=min⁡(r−∥x1−x2∥,vmax⁡−∥u1−u2∥),c_{\mathrm{coup},1}(x,u)=\min\left(r-\lVert x_1-x_2\rVert,v^{\max}-\lVert u_1-u_2\rVert\right),

and ccoup,2<0c_{\mathrm{coup},2}<0 everywhere, since cooperation never lets the vessel leave the water. Hence c1≥0c_1\ge0 when the vehicle is on land and within its own speed limit, c2≥0c_2\ge0 when the vessel is on water and within its own, and ccoup,1≥0c_{\mathrm{coup},1}\ge0 when the two are within a tolerance radius rr and the vehicle moves within vmax⁡v^{\max} of the vessel. Figure 1 shows these sets (positions). The vehicle may therefore be in the water only while riding the vessel. While the vehicle is aboard, its speed limit applies relative to the vessel, so its velocity is the velocity of the vessel plus an input of norm at most vmax⁡v^{\max}. Since ccoup,2<0c_{\mathrm{coup},2}<0 leaves A2={(x,u):c2(x2,u2)≥0}A_2=\{(x,u):c_2(x_2,u_2)\ge0\}, the vessel is bound by ∥u2∥≤vmax⁡\lVert u_2\rVert\le v^{\max} at all times, and ∥u1∥≤2vmax⁡\lVert u_1\rVert\le2v^{\max} whenever the vehicle is within rr of the vessel. The vehicle starts at a given position x10x_1^0 on one side of the river, the vessel at a given position x20x_2^0 on the water, and the vehicle must reach a goal gg across the river:

ctask(X)=min⁡(δ−∥x1(0)−x10∥,δ−∥x2(0)−x20∥,δ−∥x1(T)−g∥),c_{\mathrm{task}}(X)=\min\left(\delta-\lVert x_1(0)-x_1^0\rVert,\delta-\lVert x_2(0)-x_2^0\rVert,\delta-\lVert x_1(T)-g\rVert\right),

where δ>0\delta>0 is the tolerance on each of the three positions.

Figure 1. Positions admitted by the vehicle’s constraint set A1A_1 in Example 1, for one position of the vessel (square): the land, by c1c_1 (left), within rr of the vessel, by ccoup,1c_{\mathrm{coup},1} (middle), and their union (right). The disc is narrower than the river, so it reaches land only when the vessel is near it. The vehicle (circle) is aboard the vessel when c1<0c_1 < 0 and ccoup,1≥0c_{\mathrm{coup},1} \ge0.

We study the following capability composition problem: given a task ctaskc_{\mathrm{task}} and a team of NN agents with constraint sets AiA_i, sample team trajectories XX with ctask(X)≥0c_{\mathrm{task}}(X)\ge0 and (x(t),u(t))∈Ai(x(t),u(t))\in A_i for every ii and every tt. We generate trajectories with a denoising diffusion model, a dynamical system that transports a Gaussian into the data distribution [20, 21]. A forward process adds noise to XX over diffusion time τ∈[0,1]\tau\in[0,1] as

dX=−12g2(τ)X dτ+g(τ) dw,(3)\mathrm{d}X=-\frac{1}{2}g^2(\tau)X\,\mathrm{d}\tau+g(\tau)\,\mathrm{d}w, \tag*{(3)}

where g>0g>0 is the noise schedule and ww is a Wiener process. We write pτp_\tau for the density of XX at time τ\tau, so that p0p_0 is the density of the demonstrations and p1p_1 close to the standard Gaussian N(0,I)\mathcal{N}(0,I). The coefficients of (3) are scalar, so noise enters each coordinate independently. Sampling reverses (3), running from τ=1\tau=1 back to τ=0\tau=0, according to

dX=fθ(X,τ) dτ+g(τ) dw,(4)\mathrm{d}X=f_\theta(X,\tau)\,\mathrm{d}\tau+g(\tau)\,\mathrm{d}w, \tag*{(4)}

with dw\mathrm{d}w now a reverse-time Wiener process and the drift fθf_\theta built from a score network trained to approximate the score ∇Xlog⁡pτ\nabla_X\log p_\tau. We assume that no demonstration of cooperation is available for training. Let Di\mathcal{D}_i be a set of demonstrations Xi∈Rni×(T+1)X_i\in\mathbb{R}^{n_i\times(T+1)} of agent ii alone, let pip^i be their density, and let sθis_{\theta_i} be a score network trained on Di\mathcal{D}_i. The team prior is the product p⊗=∏ipip^{\otimes}=\prod_i p^i of the per-agent densities. We assume that each Di\mathcal{D}_i is collected in an unconstrained environment, in which agent ii is free to occupy any state. The demonstrations are therefore reusable across tasks, while cic_i is task-specific and enforced at sampling time. In Example 1, D1\mathcal{D}_1 and D2\mathcal{D}_2 contain trajectories of the vehicle and the vessel.

Main results

Generating a team trajectory through (4) requires the team score at every diffusion time, and § 2 leaves us with one score per agent. Let pτ⊗p_\tau^{\otimes} denote the density at time τ\tau of the forward process (3) started from p⊗p^{\otimes}. The separately trained per-agent scores yield the team score exactly, as we show next.

Proposition 3.1. (Agent scores form the team score) Let pτip_\tau^i be the density of XiX_i at time τ\tau. Then the rows of the team score for agent ii are its own score: for every τ\tau and ii,

∇Xilog⁡pτ⊗(X)=∇Xilog⁡pτi(Xi).(5)\nabla_{X_i}\log p_\tau^{\otimes}(X)=\nabla_{X_i}\log p_\tau^i(X_i). \tag*{(5)}

Proof. Let kτ(X∣X0)k_\tau(X\mid X_0) be the density of XX at time τ\tau when the forward process starts from the trajectory X0X_0. It factorizes across coordinates, so pτ⊗(X)=∏i∫pi(Yi)kτ(Xi∣Yi) dYip_\tau^{\otimes}(X)=\prod_i\int p^i(Y_i)k_\tau(X_i\mid Y_i)\,\mathrm{d}Y_i, and the logarithm turns the product into a sum whose ii-th term depends on XiX_i alone.

The identity (5) holds whenever the densities in the product depend on disjoint sets of variables. The forward process adds noise to each coordinate independently, so it smooths each variable separately. When the densities are over the same variable, as in a product of experts, smoothing the product is not the same as multiplying the smoothed densities, and the identity holds only approximately [22].

Sampling (4) with this score returns team trajectories drawn from p⊗p^{\otimes}, and there is no reason for them to be admissible or to complete the task: the per-agent densities were trained on demonstrations and carry no information about Ai\mathcal{A}_i or ctaskc_{\mathrm{task}}. The constraints must therefore be imposed while the trajectory is generated. Following [16], we add a control uu to (4),

dX=[fθ(X,τ)+u]dτ+g(τ) dw,(6)\mathrm{d}X=\left[f_\theta(X,\tau)+u\right]\mathrm{d}\tau+g(\tau)\,\mathrm{d}w, \tag*{(6)}

and choose uu at each step so that a scalar barrier stays non-negative along the sampled trajectory. The barrier encodes all the constraints specified in § 2. The sampler generates state trajectories only, while the constraint functions depend also on the inputs. We therefore assume that, for every agent ii and state xix_i, the map ui↦fi(xi,ui)u_i\mapsto f_i(x_i,u_i) in (1) is injective, so that ui(t)u_i(t) is the unique input taking xi(t)x_i(t) to xi(t+1)x_i(t+1). In Example 1, ui(t)=xi(t+1)−xi(t)u_i(t)=x_i(t+1)-x_i(t). Hence the constraints along a trajectory are functions of XX only. Admissibility is an intersection over agents and times, and (2) is a union:

min⁡i,tmax⁡{ci(xi(t),ui(t)),ccoup,i(x(t),u(t))},(7)\min_{i,t}\max\left\{c_i(x_i(t),u_i(t)),c_{\mathrm{coup},i}(x(t),u(t))\right\}, \tag*{(7)}

so that hcomp≥0h_{\mathrm{comp}}\geq0 when the trajectory is admissible. The actuation limits do not need a term of their own, since (2) already carries each agent’s actuation limit in cic_i and the coupled regime’s in ccoup,ic_{\mathrm{coup},i}. The barrier then becomes

h(X)=min⁡{hcomp(X),ctask(X)},h(X)=\min\{h_{\mathrm{comp}}(X),c_{\mathrm{task}}(X)\},

and the set C={X:h(X)≥0}\mathcal{C}=\{X:h(X)\geq0\} contains exactly the admissible team trajectories that complete the task.

The sampler of [16] simulates (6) on a grid τK>⋯>τ0=0\tau_K>\cdots>\tau_0=0 with steps Δτk=τk−τk−1\Delta\tau_k=\tau_k-\tau_{k-1},

Xk−1=Xk−[fθ(Xk,τk)+uk]Δτk+g(τk)Δτk ζk,(8)X_{k-1}=X_k-\left[f_\theta(X_k,\tau_k)+u_k\right]\Delta\tau_k+g(\tau_k)\sqrt{\Delta\tau_k}\,\zeta_k, \tag*{(8)}

from XK∼N(0,I)X_K\sim\mathcal{N}(0,I) to the returned trajectory X∗=X0X^*=X_0, where the ζk\zeta_k are independent Gaussian increments. The control uses the relaxed barrier h~(X,τ)=h(X)+ϵ(XK,τ)\widetilde{h}(X,\tau)=h(X)+\epsilon(X_K,\tau), whose margin is continuous, nondecreasing in τ\tau, vanishes at τ0\tau_0, and equals max⁡{0,−h(XK)}\max\{0,-h(X_K)\} at τK\tau_K, so that h~(XK,τK)≥0\widetilde{h}(X_K,\tau_K)\geq0. At each step ζk\zeta_k is drawn first, then uku_k is chosen so that

h~(Xk−1,τk−1)≥(1−αΔτk)h~(Xk,τk),(9)\widetilde{h}(X_{k-1},\tau_{k-1})\geq(1-\alpha\Delta\tau_k)\widetilde{h}(X_k,\tau_k), \tag*{(9)}

with α>0\alpha>0 and αΔτk≤1\alpha\Delta\tau_k\leq1. If (9) holds at every step, then h~\widetilde{h} stays non-negative and h(X∗)≥0h(X^*)\geq0 for every realization of the noise [16]. In that case X∗X^* is admissible and completes the task, and, by Assumption 2.1, at some timestep some agent violates its own constraint cic_i and is admissible only through its coupling constraint ccoup,ic_{\mathrm{coup},i}. Let Xk−1(u)X_{k-1}(u) denote the state that (8) gives with uk=uu_k = u and the noise ζk\zeta_k already drawn, so that (9) depends on uku_k through h~(Xk−1(uk),τk−1)\tilde{h}(X_{k-1}(u_k), \tau_{k-1}). Linearizing h~(⋅,τk−1)\tilde{h}(\cdot, \tau_{k-1}) at a point X‾\overline{X} gives the condition

h~(X‾,τk−1)+⟨∇h~(X‾,τk−1),Xk−1(u)−X‾⟩≥(1−αΔτk)h~(Xk,τk),(10)\tilde{h}(\overline{X},\tau_{k-1})+\left\langle\nabla\tilde{h}(\overline{X},\tau_{k-1}),X_{k-1}(u)-\overline{X}\right\rangle\geq(1-\alpha\Delta\tau_k)\tilde{h}(X_k,\tau_k), \tag*{(10)}

which is linear in uu, so the control of minimum norm that satisfies (10) is in closed form. The sampler of [16] takes the minimum-norm control with X‾=Xk\overline{X}=X_k. As noted in [16], the linearization error is quadratic in the displacement Xk−1−XkX_{k-1}-X_k, which is dominated by the noise term g(τk)Δτk ζkg(\tau_k)\sqrt{\Delta\tau_k}\,\zeta_k. The error is therefore of order g(τk)2Δτkg(\tau_k)^2\Delta\tau_k, the same order as the decrease that (9) allows. Hence a control that satisfies (10) at X‾=Xk\overline{X}=X_k can violate (9), and the guarantee is then lost.

To overcome this limitation, we use the sampler of [16] with three modifications. First, the relaxed barrier is evaluated on an estimate of the trajectory being formed rather than on the iterate itself, which for most of the reverse process is dominated by noise and carries little information about the trajectory the sampler returns. The estimate is the best affine estimate of X0X_0 from XτX_\tau, given in Lemma 3.2 below. Second, the control is uk=0u_k=0 whenever the unguided update satisfies (9), instead of its linearization as in [16 Remark 2]. Third, when the unguided update violates (9), we search for uku_k locally. We first set uku_k to the control of minimum norm that satisfies (10) with X‾=Xk\overline{X}=X_k, as in [16]. While (9) fails, we set X‾=Xk−1(uk)\overline{X}=X_{k-1}(u_k), the state reached with the current control, and recompute uku_k from (10). If no control satisfying (9) is found within jmax⁡j_{\max} iterations, as happens near a local maximum of h~\tilde{h}, where the gradient vanishes, we take the step with the last control. The guarantee is then lost, but the returned trajectory may still lie in CC, because later steps can increase h~\tilde{h} again. For this reason, Algorithm 1 returns h(X⋆)h(X^\star) together with X⋆X^\star.

Lemma 3.2. (Affine estimate of the returned trajectory) Let X0∈Rn×(T+1)X_0\in\mathbb{R}^{n\times(T+1)} be a random variable with mean μ\mu and covariance Σ>0\Sigma>0. Let XτX_\tau evolve from X0X_0 according to (3), and let aτ=exp⁡(−12∫0τg2(s) ds)a_\tau=\exp\left(-\frac{1}{2}\int_0^\tau g^2(s)\,\mathrm{d}s\right) and στ2=1−aτ2\sigma_\tau^2=1-a_\tau^2. Then

(Aτ,bτ)=arg min⁡A,b E∥X0−AXτ−b∥2(A_\tau,b_\tau)=\underset{A,b}{\operatorname{arg\,min}}\ \mathbb{E}\left\|X_0-AX_\tau-b\right\|^2

is given by Aτ=aτΣ(aτ2Σ+στ2I)−1A_\tau=a_\tau\Sigma\left(a_\tau^2\Sigma+\sigma_\tau^2I\right)^{-1} and bτ=(I−aτAτ)μb_\tau=(I-a_\tau A_\tau)\mu, so that MτX=AτX+bτM_\tau X=A_\tau X+b_\tau satisfies

MτX=μ+Aτ(X−aτμ).(11)M_\tau X=\mu+A_\tau(X-a_\tau\mu). \tag*{(11)}

Moreover, MτM_\tau is invertible for every τ∈[0,1]\tau\in[0,1], M0=IM_0=I, and MτX=E[X0∣Xτ=X]M_\tau X=\mathbb{E}[X_0\mid X_\tau=X] when X0X_0 is Gaussian.

Proof. (3) is linear with scalar coefficients, so Xτ=aτX0+στξX_\tau=a_\tau X_0+\sigma_\tau\xi, where ξ∼N(0,I)\xi\sim\mathcal{N}(0,I) is independent of X0X_0 and στ2=aτ2∫0τg2(s)/as2 ds=1−aτ2\sigma_\tau^2=a_\tau^2\int_0^\tau g^2(s)/a_s^2\,\mathrm{d}s=1-a_\tau^2. Hence XτX_\tau has mean aτμa_\tau\mu and covariance aτ2Σ+στ2Ia_\tau^2\Sigma+\sigma_\tau^2I, and its cross-covariance with X0X_0 is aτΣa_\tau\Sigma. The minimizer is Aτ=Cov⁡(X0,Xτ)Cov⁡(Xτ)−1A_\tau=\operatorname{Cov}(X_0,X_\tau)\operatorname{Cov}(X_\tau)^{-1} and bτ=E[X0]−AτE[Xτ]b_\tau=\mathbb{E}[X_0]-A_\tau\mathbb{E}[X_\tau], which gives the expressions above. The eigenvalues λj\lambda_j of Σ\Sigma are positive, and AτA_\tau has the same eigenvectors and the eigenvalues aτλj/(aτ2λj+στ2)>0a_\tau\lambda_j/(a_\tau^2\lambda_j+\sigma_\tau^2)>0, so MτM_\tau is invertible. Since a0=1a_0=1 and σ0=0\sigma_0=0, A0=IA_0=I and b0=0b_0=0. When X0X_0 is Gaussian, (X0,Xτ)(X_0,X_\tau) is jointly Gaussian, and its conditional mean is affine and equal to (11). □

Lemma 3.2 uses only the mean and the covariance of X0X_0, so MτM_\tau is computed in closed form and does not need to be learned. During sampling, XτX_\tau is the current iterate, and MτXM_\tau X is the best affine estimate of the trajectory being formed. We therefore let μ\mu and Σ\Sigma be the mean and covariance of the product prior p⊗p^\otimes, estimated from the training sets Di\mathcal{D}_i, and evaluate the relaxed barrier on this estimate, that is, h~(X,τ)=h(MτX)+ϵ(XK,τ)\tilde{h}(X,\tau)=h(M_\tau X)+\epsilon(X_K,\tau), with margin ϵ(XK,τ)=max⁡{0,−h(MτKXK)}\epsilon(X_K,\tau)=\max\{0,-h(M_{\tau_K}X_K)\}. Theorem 4.2 of [16] is stated for the barrier h(X)+ϵ(XK,τ)h(X)+\epsilon(X_K,\tau), and it extends to the modified h~\tilde{h} above with the same proof. The margin gives h~(XK,τK)≥0\tilde{h}(X_K,\tau_K)\geq0, and if (9) holds at every step, then h~(Xk−1,τk−1)≥(1−αΔτk)h~(Xk,τk)≥0\tilde{h}(X_{k-1},\tau_{k-1})\geq(1-\alpha\Delta\tau_k)\tilde{h}(X_k,\tau_k)\geq0 for every kk, by induction. As ϵ\epsilon vanishes at τ0\tau_0 and M0=IM_0=I, h(X⋆)=h~(X0,τ0)≥0h(X^\star)=\tilde{h}(X_0,\tau_0)\geq0, so X⋆∈CX^\star\in C. In our implementation, the right-hand side of (9) is replaced by its minimum with 0.15+ϵ(XK,τK−1)0.15+\epsilon(X_K,\tau_{K-1}), so that the guidance stops acting once a trajectory is well inside CC. The right-hand side remains non-negative, and the argument above still applies.

We next characterize the type of trajectories that the diffusion sampler can generate. In particular, we prove that any admissible team trajectory solving the task can be generated with arbitrary accuracy and nonzero probability, even when the training set does not contain such trajectories. To this end, we make the following technical assumption.

Assumption 3.3. (Monotone reachability) For every X∈CX\in C and s≤0s\leq0, there exists X′ ⁣X'\! with h(X′)=sh(X')=s and a continuous path from X′X' to XX along which hh is nondecreasing.

Assumption 3.3 asks that every trajectory in CC be reachable from below without lowering hh. It fails when a trajectory in CC lies in a region enclosed by higher values of hh, so that hh first increases and then decreases along every path that reaches it from a lower level set. It involves only hh, and neither the prior nor the data. For X∈Rn×(T+1)X\in\mathbb{R}^{n\times(T+1)} and ρ>0\rho>0, B(X,ρ)B(X,\rho) denotes the open ball of radius ρ\rho centered at XX in the Frobenius norm, and supp⁡(μ)\operatorname{supp}(\mu) denotes the support of a distribution μ\mu, that is, the smallest closed set of probability one.

Algorithm 1 Barrier-guided sampling, modified from [16]

Require: per-agent scores sθis_{\theta_i}, relaxed barrier h~\tilde{h}, grid {τk}\{\tau_k\}, gain α\alpha, iteration limit jmax⁡j_{\max}

Draw XK∼N(0,I)X_K \sim\mathcal{N}(0,I) and set the margin ϵ(XK,⋅)\epsilon(X_K,\cdot)

for k=K,…,1k=K,\ldots,1 do

&nbsp;&nbsp;&nbsp;&nbsp;Draw ζk∼N(0,I)\zeta_k \sim\mathcal{N}(0,I) and set uk←0u_k \leftarrow0

&nbsp;&nbsp;&nbsp;&nbsp;if Xk−1(0)X_{k-1}(0) violates (9) then

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;uk←arg⁡min⁡{∥u∥:(10), Xˉ=Xk}u_k \leftarrow\arg\min\{\lVert u\rVert:(10),\ \bar{X}=X_k\} [16]

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for j=1,…,jmax⁡j=1,\ldots,j_{\max}, while (9) fails at Xk−1(uk)X_{k-1}(u_k) do

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;uk←arg⁡min⁡{∥u∥:(10), Xˉ=Xk−1(uk)}u_k \leftarrow\arg\min\{\lVert u\rVert:(10),\ \bar{X}=X_{k-1}(u_k)\}

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end for

&nbsp;&nbsp;&nbsp;&nbsp;end if

&nbsp;&nbsp;&nbsp;&nbsp;Xk−1←Xk−1(uk)X_{k-1}\leftarrow X_{k-1}(u_k)

end for

return X⋆=X0X^\star=X_0 and h(X⋆)h(X^\star)

Theorem 3.4. (Every trajectory in CC can be generated) Let Assumption 3.3 hold, let fθf_\theta and hh be continuous, with CC the closure of {X:h(X)>0}\{X:h(X)>0\}, and let μ\mu be the distribution of the trajectory X⋆X^\star returned by Algorithm 1. Then μ(B(Xˉ,ρ)∩C)>0\mu(B(\bar{X},\rho)\cap C)>0 for every Xˉ∈C\bar{X}\in C and every ρ>0\rho>0. If, in addition, (9) holds at every step, then supp⁡(μ)=C\operatorname{supp}(\mu)=C.

Proof. Fix Xˉ\bar{X} with h(Xˉ)>0h(\bar{X})>0 and ρ>0\rho>0, and let ρ′∈(0,ρ]\rho'\in(0,\rho] be such that h>0h>0 on B(Xˉ,ρ′)B(\bar{X},\rho'), which exists because hh is continuous. Assumption 3.3 with any s<0s<0 gives a trajectory Y^K\hat{Y}_K with h(Y^K)=sh(\hat{Y}_K)=s and a continuous path from Y^K\hat{Y}_K to Xˉ\bar{X} along which hh is nondecreasing. Let X^K=MτK−1Y^K\hat{X}_K=M_{\tau_K}^{-1}\hat{Y}_K. At X^K\hat{X}_K the margin is ϵ(X^K,τK)=−s\epsilon(\hat{X}_K,\tau_K)=-s, so h~(X^K,τK)=0\tilde{h}(\hat{X}_K,\tau_K)=0, and as ϵ\epsilon vanishes at τ0\tau_0 and h(Xˉ)>0h(\bar{X})>0,

∑k=1K[ϵ(τk)−ϵ(τk−1)]=−s<h(Xˉ)−h(Y^K),\sum_{k=1}^{K}\left[\epsilon(\tau_k)-\epsilon(\tau_{k-1})\right]=-s<h(\bar{X})-h(\hat{Y}_K),

so the path has points Y^K,…,Y^0=Xˉ\hat{Y}_K,\ldots,\hat{Y}_0=\bar{X} with

h(Y^k−1)−h(Y^k)>ϵ(τk)−ϵ(τk−1).(12)h(\hat{Y}_{k-1})-h(\hat{Y}_k)>\epsilon(\tau_k)-\epsilon(\tau_{k-1}). \tag*{(12)}

Let X^k=Mτk−1Y^k\hat{X}_k=M_{\tau_k}^{-1}\hat{Y}_k, so that X^0=Xˉ\hat{X}_0=\bar{X} as M0=IM_0=I, and h~(X^k,τk)=h(Y^k)+ϵ(τk)\tilde{h}(\hat{X}_k,\tau_k)=h(\hat{Y}_k)+\epsilon(\tau_k) increases strictly as kk decreases.

Since h~\tilde{h} vanishes at X^K\hat{X}_K it is non-negative at every step, and by (12) it increases strictly. Hence the unguided update from X^k\hat{X}_k to X^k−1\hat{X}_{k-1} satisfies (9) with strict inequality, and Algorithm 1 sets uk=0u_k=0 there. The recursion (8) adds g(τk)Δτk ζkg(\tau_k)\sqrt{\Delta\tau_k}\,\zeta_k to a term set by XkX_k and uku_k, and g(τk)>0g(\tau_k)>0, so exactly one increment ζk⋆\zeta_k^\star carries X^k\hat{X}_k to X^k−1\hat{X}_{k-1} and (X^K,ζ1:K⋆)(\hat{X}_K,\zeta_{1:K}^\star) returns Xˉ\bar{X}.

The barrier h~\tilde{h} is continuous and (12) is strict, so induction on kk gives uk=0u_k=0 at every step on a neighborhood of (X^K,ζ1:K⋆)(\hat{X}_K,\zeta_{1:K}^\star). The recursion is the unguided one there, hence continuous, and a smaller neighborhood is carried into B(Xˉ,ρ′)B(\bar{X},\rho'). That neighborhood has positive probability under the Gaussian initialization and increments, so μ(B(Xˉ,ρ)∩C)≥μ(B(Xˉ,ρ′))>0\mu(B(\bar{X},\rho)\cap C)\geq\mu(B(\bar{X},\rho'))>0. If instead h(Xˉ)=0h(\bar{X})=0, then B(Xˉ,ρ/2)B(\bar{X},\rho/2) contains a trajectory X′X' with h(X′)>0h(X')>0, because CC is the closure of {h>0}\{h>0\}, and the claim follows from B(X′,ρ/2)⊆B(Xˉ,ρ)B(X',\rho/2)\subseteq B(\bar{X},\rho). Finally, we prove the second claim. If (9) holds at every step, then h(X0)≥0h(X_0)\geq0 for every realization of the noise, by the extension of [16 Theorem 4.2] given after Lemma 3.2, so that μ(C)=1\mu(C)=1. Since hh is continuous, CC is closed, and hence supp⁡(μ)⊆C\operatorname{supp}(\mu)\subseteq C. The reverse inclusion C⊆supp⁡(μ)C\subseteq\operatorname{supp}(\mu) is the first claim, since every ball around a point of CC has positive probability. □\square

We next ask which agents cooperate, and when. Let the times at which agent ii is admissible only through its coupling constraint be

Si(X)={t:ci(xi(t),ui(t))<0≤ccoup,i(x(t),u(t))},(13)S_i(X)=\{t:c_i(x_i(t),u_i(t))<0\leq c_{\mathrm{coup},i}(x(t),u(t))\}, \tag*{(13)}

and we call S(X)=(S1(X),…,SN(X))S(X)=(S_1(X),\ldots,S_N(X)) the coupling pattern of XX. The trajectories in CC with pattern SS form the set CS={X∈C:S(X)=S}C_S=\{X\in C:S(X)=S\}, and these sets partition CC. The sampler returns, with nonzero probability, the coupling pattern of every trajectory that satisfies the constraints strictly.

Corollary 3.5. (Every coupling pattern can occur) Let the hypotheses of Theorem 3.4 hold and let XX satisfy h(X)>0h(X)>0 and, for every tt and ii, either ci(xi(t),ui(t))>0c_i(x_i(t),u_i(t))>0 or ci(xi(t),ui(t))<0<ccoup,i(x(t),u(t))c_i(x_i(t),u_i(t))<0<c_{\mathrm{coup},i}(x(t),u(t)). Then the sampler returns a trajectory in CC with the coupling pattern of XX with nonzero probability, that is, μ(CS(X))>0\mu(C_{S(X)})>0.

Proof. The inequalities in the hypothesis are strict and cic_i, ccoup,ic_{\mathrm{coup},i} and hh are continuous, so there is a ρ>0\rho>0 such that every trajectory in B(X,ρ)B(X,\rho) satisfies them and has h>0h>0. By (13) the coupling pattern is S(X)S(X) throughout B(X,ρ)B(X,\rho), and Theorem 3.4 gives μ(CS(X))≥μ(B(X,ρ)∩C)>0\mu(C_{S(X)})\geq\mu(B(X,\rho)\cap C)>0. □\square

The constraint functions cic_i, ccoup,ic_{\mathrm{coup},i} and ctaskc_{\mathrm{task}} determine CC. By Theorem 3.4, the sampler can return every trajectory in CC, with probabilities determined by the demonstrations. The constraints do not prescribe a coupling pattern, because (x(t),u(t))(x(t),u(t)) lies in AiA_i whenever ci≥0c_i \ge0 or ccoup,i≥0c_{\mathrm{coup},i} \ge0. Hence CC contains trajectories with different coupling patterns, and Corollary 3.5 gives each of them a positive probability of being sampled. Finally, by Proposition 3.1, each agent contributes its own score to the product prior, while the constraints enter only through the guidance. Adding or removing an agent therefore changes only the constraint functions and the set of scores in the product, and no network needs to be retrained.

The probability that the sampler returns a trajectory in CC depends on whether (9) can be satisfied at every step, because (9) at every step guarantees that the returned trajectory lies in CC. Algorithm 1 searches for such a step locally, along gradients of h~\tilde{h}. Because hcomph_{\mathrm{comp}} in (7) is a maximum over the two sets of each union, hh can have local maxima at which h<0h < 0, and a search that reaches one may find no step satisfying (9) even when CC is nonempty. Controllers based on control barrier functions have the same limitation, since their quadratic programs can stall at points other than the intended ones [23]. The maxima that encode unions of sets [13] add such points.

Numerical results

We consider Example 1 over 50 timesteps, with w=0.16w = 0.16, vmax⁡=0.045v^{\max} = 0.045, r=0.05r = 0.05 and δ=0.06\delta= 0.06. The training sets D1D_1 and D2D_2 contain 2000 single-agent trajectories each, recorded in an environment of the same dimensions without the river. Hence the demonstrations describe how each agent moves, and contain neither the constraints nor any cooperation.1 To compute the guidance from the gradient of hh, we replace the min and max in hh by the smooth surrogates

smin⁡κ(a)=−1κlog⁡∑je−κaj,\operatorname{smin}_{\kappa}(a) = -\frac{1}{\kappa}\log\sum_j e^{-\kappa a_j},
smax⁡κ(a)=1κlog⁡∑jeκaj−1κlog⁡M,\operatorname{smax}_{\kappa}(a) = \frac{1}{\kappa}\log\sum_j e^{\kappa a_j} - \frac{1}{\kappa}\log M,

over the MM entries of aa, with κ=25\kappa= 25. Both surrogates are bounded above by the exact minimum and maximum, so the smoothed barrier is non-negative only on trajectories in CC.

The sampler generates cooperative trajectories, although neither training set contains one. No trajectory drawn from the team prior lies in CC (Table 1). Guided by ctaskc_{\mathrm{task}} alone, all 500 generated trajectories reach the goal, but in every one of them the vehicle enters the water without the vessel. Guided by hh, all 500 lie in CC. Figure 2 shows one trajectory of each kind. In the trajectory guided by hh, the vessel meets the vehicle at the river, the two cross together, and the vehicle continues to the goal. This sequence appears in neither training set.

Figure 2. River crossing of Example 1: a trajectory sampled from the prior alone, one guided by the task constraint ctaskc_{\mathrm{task}} only, and one guided by all constraints hh (Algorithm 1). The band is the river, open circles mark initial positions and the disc around ⋆\star is the goal. The vehicle’s path in the river is green where the vessel is within rr and amber where it is not. Right: vehicle-vessel distance along the trajectory guided by hh, shaded while the vessel carries the vehicle.

river crossingescape roomRobotarium
Algorithm 110030100
per-step projection1003699
penalty guidance16014
projection after sampling44254
rejection000

Table 1. Percentage of the generated trajectories that are admissible and complete the task, averaged over five seeds.

The constraints require the two agents to cross together, and the learned prior determines where and when they do. To separate the two contributions, we replace the learned prior by a Gaussian of matched moments and keep the barrier. For each of the 500 trajectories guided by hh, we record the coordinate z1z_1 and the timestep tt at which the two agents come closest (Figure 3). With the Gaussian prior all trajectories also lie in CC, and the crossings concentrate near the point where the straight line from x10x_1^0 to gg meets the river. With the learned prior, the trajectories inherit the turns and pauses of the demonstrations, which are walks through two or three random waypoints at constant speed, and their crossings spread over most of the region that the horizon allows. The number of timesteps on which the two agents are within rr of each other varies in the same way, from 4 to 27. The constraints require only two such timesteps, so the longer couplings come from the prior.

Figure 3. 500 trajectories from the learned prior and 500 from a Gaussian prior of matched moments, both guided by hh. The shading counts the trajectories that cross at the coordinate z1z_1 and the timestep tt at which the two agents come closest. The red curves bound the crossings that allow reaching the goal by TT. The learned prior spreads its crossings over that region, and the Gaussian concentrates them near the middle.

The sampler requires no retraining when the team changes. We add a second vessel that can also carry the vehicle, so that A1\mathcal{A}_1 in (2) gains a third set. Both vessels use the same score, and ctaskc_{\mathrm{task}} fixes the initial position of each, the new vessel starting on the water at distance 0.2 from x20x_2^0. All 500 trajectories generated for this team lie in C\mathcal{C}, and in 127 of them the vehicle passes from one vessel to the other. With three vehicles and three vessels, all 500 trajectories lie in C\mathcal{C}. They show 144 different coupling patterns, against 12 in 100 solutions of trajectory optimization without the prior. Removing agents works in the same way, unless the remaining team cannot complete the task. With no vessel, for example, Assumption 2.1 fails and no trajectory lies in C\mathcal{C}.

We implement the river crossing on the Robotarium [24], a testbed of unicycle robots in an arena of 3.2 m by 2 m. The unit square of Example 1 is mapped to a square of side 2 m in the arena, and each timestep of a trajectory is executed in 1.2 s. The robots have a physical size, so we change the constraint functions and keep the networks and the sampler. The river widens to 80 cm and rr grows to 32 cm, so that two robots fit within rr of each other, while 2r<w2r < w still forces the vessel to carry the vehicle. We also add two constraints that the simulation does not need. The first requires every pair of robots to stay at least 20 cm apart, so that the robots do not collide. The second requires every robot to stay inside the arena. Finally, a constraint that holds at every timestep can still be violated between two consecutive timesteps, so we impose every constraint on the whole segment between them. We call this the Robotarium setting. Algorithm 1 places every trajectory in C\mathcal{C}, with one vessel and with two. Each robot tracks its sampled positions through the Robotarium’s map from single-integrator to unicycle inputs, so the nonholonomic constraint appears only as tracking error. We execute the first 15 trajectories with one vessel and the first 5 with two. All 20 runs satisfy the constraints up to the tracking error, which stays below 5 cm. Figure 4 shows a run with two vessels, in which one vessel hands the vehicle to the other.

Figure 4. A Robotarium run with two vessels. (a) Camera frame at the handover, with executed paths of the vehicle (blue), vessel 1 (red) and vessel 2 (purple). Dashed lines are the riverbanks. (b) Distance from the vehicle to each vessel, with the time in the river shaded and the time of (a) dotted.

In the second task, an escape room, cooperation also has to be timed. Two agents start on one side of a wall with a doorway, and both have to reach an exit on the other side by the end of the horizon. The door is open at time tt when, at t−1t-1, some agent was on a pad placed before the wall, or in the doorway. The state of agent ii consists of its current and previous positions, pip_i and pi−p_i^-, because the door depends on the previous step. Let WW be the wall with the door shut, Ws⊂WW_s \subset W its solid part, so that W∖WsW \setminus W_s is the doorway, PP the pad, and dSd_S the signed distance to SS, positive outside SS. Then

ci(xi,ui)=min⁡{dW(pi),vmax⁡−∥ui∥},ccoup,i(x,u)=min⁡{dWs(pi),o(x),vmax⁡−∥ui∥},o(x)=max⁡jω(pj−),ω(p)=max⁡{−dP(p),min⁡{dWs(p),−dW(p)}}.\begin{aligned} c_i(x_i,u_i) &= \min\left\{d_W(p_i),v^{\max}-\lVert u_i\rVert\right\},\\ c_{\mathrm{coup},i}(x,u) &= \min\left\{d_{W_s}(p_i),o(x),v^{\max}-\lVert u_i\rVert\right\},\\ o(x) &= \max_j \omega(p_j^-),\\ \omega(p) &= \max\left\{-d_P(p),\min\left\{d_{W_s}(p),-d_W(p)\right\}\right\}. \end{aligned}

where ω(p)≥0\omega(p) \ge0 when pp is on the pad or in the doorway, so that o(x)≥0o(x) \ge0 when the door is open. The task function ctaskc_{\mathrm{task}} asks each agent to start within δ\delta of its initial position and to end within δ\delta of the exit. The wall is thicker than one step and the pad is more than one step from the doorway, so an agent alone cannot pass. Two agents can, one on the pad while the other enters the doorway and then holds the door. Both agents use the same score network, trained on 4000 single-agent trajectories recorded in the room without the wall.

Cooperation that has to be timed is harder to generate. In the escape room, about 30% of the trajectories generated by Algorithm 1 lie in CC, and in each of them one agent stands on the pad while the other enters the doorway (Figure 5). Without the local search, as in [16], no trajectory lies in CC. Most failures leave an agent at the shut door, which is consistent with the local maxima of hh discussed in § 3.

Figure 5. A trajectory of the escape room in CC, at four timesteps (top) and over the horizon (bottom). Dots are the agents and faint lines their last five steps. The doorway is dark when the door is shut, the disc is the pad, and the dotted line is the exit. Agent 2 is on the pad from t=11t = 11 to t=15t = 15, so the door is open from t=12t = 12, agent 1 enters the doorway at t=16t = 16 and holds the door, and agent 2 enters at t=19t = 19. Bottom: timesteps on the pad (yellow), in the doorway (agent colour), and with the door open (shaded).

In all three settings, Algorithm 1 and per-step projection place far more trajectories in CC than the other three methods in Table 1. All methods use the same prior, barrier and noise. Per-step projection [11, 25] moves the sample toward {h≥0.02}\{h \ge0.02\} after every reverse step with a few Newton steps, on XτX_\tau or on MτXτM_{\tau}X_\tau, and the table reports the better of the two. Penalty guidance [5] adds to the score the gradient of a penalty on constraint violation, with a weight chosen per task. Projection after sampling moves each sample of the prior onto CC once sampling ends. Rejection keeps the samples of the prior that lie in CC. These last three methods place at most about half of the trajectories in CC, and almost none in the escape room. Per-step projection comes with no guarantee that the returned trajectory lies in CC, while Algorithm 1 has one whenever (9) holds at every step. In the river crossing and in the Robotarium setting, both methods place almost every trajectory in CC, and projection is faster. In the escape room, projection places 36% of the trajectories in C\mathcal{C}, against 30%. It moves the samples about 400 times more than Algorithm 1, as measured by the control energy of [16], and its trajectories end farther from the prior, as measured by the maximum mean discrepancy [26]. In the river crossing, projection moves the samples about 50 times more, and its trajectories are as close to the prior as those of Algorithm 1. On images, the larger correction of per-step projection visibly degrades the samples [16].

Conclusion

In this paper we study how to generate trajectories for a team of agents, without demonstrations of cooperation, when the task requires a capability that no agent has alone. We encode the capability as constraints on the team trajectory, and guide the sampling from diffusion models trained on each agent alone with a barrier function built from the constraints. The resulting sampler can provably generate every team trajectory that satisfies the constraints. Our numerical results show that the sampler generates cooperative trajectories that satisfy the constraints, and that it requires no retraining when agents join or leave the team. On the Robotarium, the generated trajectories satisfy the constraints also when unicycle robots execute them, up to the tracking error. Existing guidance methods, however, can fail when the constraint sets are complex, for example when cooperation also has to be timed. Future work includes the design of guidance methods for complex constraint sets, and learning the coupling constraints from demonstrations of interacting agents.

Acknowledgments

This work was supported in part by NSF under award CMMI-2622263.

References

  1. [1]B. P. Gerkey and M. J. Matarić, “A formal analysis and taxonomy of task allocation in multi-robot systems,” International Journal of Robotics Research, vol. 23, no. 9, pp. 939–954, 2004.DOI
  2. [2]G. A. Korsah, A. Stentz, and M. B. Dias, “A comprehensive taxonomy for multi-robot task allocation,” International Journal of Robotics Research, vol. 32, no. 12, pp. 1495–1512, 2013.DOI
  3. [3]E. Tuci, M. H. M. Alkilabi, and O. Akanyeti, “Cooperative object transport in multi-robot systems: A review of the state-of-the-art,” Frontiers in Robotics and AI, vol. 5, p. 59, 2018.DOI
  4. [4]H. Farivarnejad and S. Berman, “Multirobot control strategies for collective transport,” Annual Review of Control, Robotics, and Autonomous Systems, vol. 5, pp. 205–219, 2022.
  5. [5]M. Janner, Y. Du, J. B. Tenenbaum, and S. Levine, “Planning with diffusion for flexible behavior synthesis,” in International Conference on Machine Learning, ser. PMLR, vol. 162, 2022.arxiv.org/abs/2205.09991
  6. [6]C. Chi, Z. Xu, S. Feng, E. Cousineau, Y. Du, B. Burchfiel, R. Tedrake, and S. Song, “Diffusion policy: Visuo-motor policy learning via action diffusion,” in Robotics: Science and Systems, 2023.
  7. [7]Z. Zhu, M. Liu, L. Mao, B. Kang, M. Xu, Y. Yu, S. Ermon, and W. Zhang, “MADiff: Offline multi-agent learning with diffusion models,” in Advances in Neural Information Processing Systems, 2024.arxiv.org/abs/2305.17330
  8. [8]D. Lee, D. Lee, and A. Zhang, “Multi-agent coordination via flow matching,” in International Conference on Learning Representations, 2026.arxiv.org/abs/2511.05005
  9. [9]P. Dhariwal and A. Nichol, “Diffusion models beat GANs on image synthesis,” in Advances in Neural Information Processing Systems, vol. 34, 2021.
  10. [10]Y. Shaoul, I. Mishani, S. Vats, J. Li, and M. Likhachev, “Multi-robot motion planning with diffusion models,” in International Conference on Learning Representations, 2025.arxiv.org/abs/2410.03072
  11. [11]J. Liang, J. K. Christopher, S. Koenig, and F. Fioretto, “Simultaneous multi-robot motion planning with projected diffusion models,” arXiv preprint arXiv:2502.03607, 2025.arxiv.org/abs/2502.03607
  12. [12]A. D. Ames, X. Xu, J. W. Grizzle, and P. Tabuada, “Control barrier function based quadratic programs for safety critical systems,” IEEE Transactions on Automatic Control, vol. 62, no. 8, pp. 3861–3876, 2017.DOI
  13. [13]P. Glotfelter, J. Cortés, and M. Egerstedt, “A nonsmooth approach to controller synthesis for Boolean specifications,” IEEE Transactions on Automatic Control, vol. 66, no. 11, pp. 5160–5174, 2020.DOI
  14. [14]R. Lin and M. Egerstedt, ““Hierarchy of needs” for robots: Control synthesis for compositions of hierarchical, complex objectives,” in 2025 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 2025, pp. 7682–7688.DOI
  15. [15]W. Xiao, T.-H. Wang, C. Gan, and D. Rus, “SafeDiffuser: Safe planning with diffusion probabilistic models,” in International Conference on Learning Representations, 2025.
  16. [16]D. Gadginmath, A. Allibhoy, and F. PasqualeLtti, “Provably safe generative sampling with constricting barrier functions,” Transactions on Machine Learning Research, 2026.arxiv.org/abs/2602.21429
  17. [17]X. Dai, Z. Yang, D. Yu, F. Liu, H. Sadeghian, S. Haddadin, and S. Hirche, “SafeFlow: Safe robot motion planning with flow matching via control barrier functions,” arXiv preprint arXiv:2504.08661, 2025.arxiv.org/abs/2504.08661
  18. [18]J. Yang, S. Jang, and S. Han, “SafeFlowMatcher: Safe and fast planning using flow matching with control barrier functions,” in International Conference on Learning Representations, 2026.arxiv.org/abs/2509.24243
  19. [19]R. Lin, M. Egerstedt, and F. PasqualeLtti, “Multi-agent flow matching with decoupled generative guidance,” arXiv preprint arXiv:2609.38133, 2026.arxiv.org/abs/2609.38133
  20. [20]J. Ho, A. Jain, and P. Abbeel, “Denoising diffusion probabilistic models,” in Advances in Neural Information Processing Systems, vol. 33, 2020.arxiv.org/abs/2006.11239
  21. [21]Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole, “Score-based generative modeling through stochastic differential equations,” in International Conference on Learning Representations, 2021.
  22. [22]Y. Du, C. Durkan, R. Strudel, J. B. Tenenbaum, S. Dieleman, R. Fergus, J. Sohl-Dickstein, A. Doucet, and W. Grathwohl, “Reduce, reuse, recycle: Compositional generation with energy-based diffusion models and MCMC,” in International Conference on Machine Learning, ser. PMLR, vol. 202, 2023, pp. 8489–8510.arxiv.org/abs/2302.11552
  23. [23]M. F. Reis, A. P. Aguiar, and P. Tabuada, “Control barrier function-based quadratic programs introduce undesirable asymptotically stable equilibria,” IEEE Control Systems Letters, vol. 5, no. 2, pp. 731–736, 2021.DOI
  24. [24]S. Wilson, P. Glotfelter, L. Wang, S. Mayya, G. Notomista, M. Mote, and M. Egerstedt, “The Robotarium: Globally impactful opportunities, challenges, and lessons learned in remote-access, distributed control of multirobot systems,” IEEE Control Systems Magazine, vol. 40, no. 1, pp. 26–44, 2020.DOI
  25. [25]S. Zampini, J. K. Christopher, L. Oneto, D. Anguita, and F. Fioretto, “Training-free constrained generation with stable diffusion models,” arXiv preprint arXiv:2502.05625, 2025.arxiv.org/abs/2502.05625
  26. [26]A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, and A. Smola, “A kernel two-sample test,” Journal of Machine Learning Research, vol. 13, no. 25, pp. 723–773, 2012.DOI

Paper details

vlnc:W_wny8nbsa
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents