betaFeedback

Reading v1View latest version

WorksComputer Science

Discrete Model-Based Diffusion for Combinatorial Optimization in Multi-Robot Task Allocation

Abstract

Decision making in multi-agent and multi-robot systems often involves discrete decision variables, leading to NP-hard combinatorial optimization problems that must be solved within seconds for near real-time implementation. Denoising diffusion has emerged as a powerful tool for such problems, but existing approaches face a trade-off: Model-Based Diffusion (MBD) incorporates diffusion in sampling-based optimization (SBO) without training but only over continuous spaces, while existing diffusion-based combinatorial solvers operate over discrete spaces but require offline training. To this end, we propose Discrete Model-Based Diffusion (Discrete MBD), a training-free SBO method that directly optimizes discrete variables by approximating categorical reverse transition distributions through Monte Carlo sampling. We establish a finite-step lower bound on the probability of finding a global minimizer and show that this bound converges to one as the number of denoising steps increases. Extensive experiments on generic integer programs and heterogeneous multi-robot coalition formation and scheduling demonstrate that Discrete MBD outperforms SBO baselines in nearly all settings while achieving solution quality competitive with that of mixed-integer programming and reinforcement learning methods at a fraction of their computational cost.

Introduction

Many decision-making problems in multi-robot and broadly multi-agent systems involve inherently discrete choices, such as assigning tasks to robots [11, 18, 35], selecting the modes of hybrid systems [14, 25], and avoiding obstacles [16, 19]. These decisions give rise to combinatorial optimization problems that are often NP-hard, with solution spaces growing exponentially with problem size, making high-quality solutions difficult to obtain within the tight time budgets of online operation.

A representative example, used throughout this paper, is the heterogeneous multi-robot task allocation (MRTA) problem, where robots with different skills, each at a different capability level, must complete spatially distributed tasks as quickly as possible [1, 9, 11] (Figure 1). Specifically, we consider joint coalition formation and scheduling, where each task requires tight coordination [31]: task execution begins only once a coalition with sufficient combined skill capabilities gathers at the task location. Robots must therefore jointly decide which robots serve each task (coalition formation) and when each robot executes its tasks (scheduling) to minimize makespan. This places the problem in the single-task robots, multi-robot tasks, time-extended assignment, cross-schedule dependencies (XD [ST-MR-TA]) category [18], with a combinatorial search space that grows rapidly with the numbers of robots and tasks, and complexity of the skill requirements. Since new tasks, robot dropouts, or travel delays may arise unexpectedly [9], robots must replan within seconds to dynamically adapt to such changing conditions.

Figure 1. Heterogeneous MRTA problem, which jointly addresses coalition formation and scheduling. Each robot has multiple skills at different capability levels (one block per level), and each task requires a minimum combined capability level for each specified skill. Robots must form coalitions and schedule routes to minimize the makespan. (a) Dashed curves show candidate routes. (b) Example coalition: R1 and R2 jointly meet T2’s requirement, so R1 waits for R2 to arrive before the task starts.

There exist numerous approaches to these combinatorial optimization problems. Exact methods formulate problems as optimization programs [8, 11] and employ techniques such as Branch-and-Bound and cutting-plane methods [27], but scale poorly and become computationally expensive for large problems. Metaheuristics, such as simulated annealing (SA) [5], genetic algorithms [4, 26], ant colony optimization [3], and large neighborhood search [30, 39], offer faster solutions but require problem-specific local search operators or heuristics. Learning-based methods [9, 17, 37, 38] enable fast inference but require offline training and may generalize poorly to problem structures unconsidered during the training.

Sampling-based optimization (SBO) offers an alternative. SBO methods iteratively sample candidate solutions from a probability distribution and refine the distribution to concentrate its search on promising regions, without problem-specific local search algorithms or offline training. While closely related methods are known as model-based search algorithms in combinatorial optimization [42], we follow the robotics and control literature [40, 41] and adopt the term SBO in this paper. Classical SBO methods for discrete problems include the cross-entropy method (CEM) [32] and sequential Monte Carlo (SMC) [10]. However, these methods struggle to explore large solution spaces with multimodal objective landscapes, i.e., objective functions with many local optima: CEM is prone to premature mode collapse, while SMC suffers from particle degeneracy that reduces sample diversity.

Meanwhile, Model-Based Diffusion (MBD) [29] has emerged as a promising SBO method that adapts the diffusion process of Denoising Diffusion Probabilistic Model (DDPM) [13] to optimization. MBD uses the known objective function to estimate the score function through Monte Carlo sampling, eliminating the need for offline neural network training. By gradually concentrating samples on low-cost regions through the diffusion process, MBD outperforms other SBO methods on nonconvex, non-differentiable problems [20, 29].

Diffusion-based search is also appealing for combinatorial optimization, where solution spaces are often large and highly multimodal [17, 37]. However, MBD denoises in a continuous space and thus cannot directly produce discrete decisions. Its solutions must be rounded, which degrades solution quality [37] and may lead to constraint violations. On the other hand, existing diffusion-based combinatorial optimization solvers [17, 21, 23, 34, 37] denoise directly over discrete variables using discrete diffusion models [2, 15]. However, they rely on a neural network to learn the denoising process offline.

To bridge this gap, we propose Discrete Model-Based Diffusion (Discrete MBD), a training-free SBO method that performs denoising diffusion directly over discrete decision variables, modeling each as a categorical random variable. At each denoising step, Discrete MBD approximates the categorical reverse transition distribution with samples weighted by the known problem formulation, progressively steering the search toward high-quality solutions. The contributions of this paper are as follows:

  • We propose Discrete MBD, an SBO method for combinatorial optimization that denoises directly over discrete decision variables by approximating the reverse transitions of discrete diffusion with Monte Carlo sampling.

  • We establish a finite-step probabilistic convergence guarantee for Discrete MBD (Theorem 1) that characterizes its exploration-exploitation trade-off and shows that the probability of finding a global minimizer approaches one as the number of denoising steps increases.

  • We present a priority-based encoding scheme, inspired by [4], that guarantees every sample decodes into a feasible solution for heterogeneous MRTA, improving sampling efficiency.

  • We evaluate Discrete MBD on numerous generic unconstrained integer programs and heterogeneous MRTA problems.

Preliminaries

We denote the kk-dimensional column vector of ones by 1k\mathbf{1}_k. For matrices AA and BB, let A⊙BA \odot B denote their elementwise product. For a matrix AA, we denote by AiA_i its ii-th row and by [A]ij[A]_{ij} the element in row ii and column jj. For a vector aa, [a]i[a]_i denotes its ii-th element. For vectors aa, bb of the same size, a⪰ba \succeq b means [a]i≥[b]i[a]_i \ge[b]_i for all ii. We denote the sets of positive and nonnegative integers by Z>0\mathbb{Z}_{>0} and Z≥0\mathbb{Z}_{\ge0}, respectively. For a set S\mathcal{S} and I1,I2∈Z≥0I_1,I_2 \in\mathbb{Z}_{\ge0}, SI1\mathcal{S}^{I_1} denotes the set of I1I_1-tuples with entries in S\mathcal{S}, and SI1×I2\mathcal{S}^{I_1\times I_2} the set of I1×I2I_1 \times I_2 matrices with entries in S\mathcal{S}.

We consider N∈Z≥0N \in\mathbb{Z}_{\ge0} discrete or categorical decision variables indexed by N={0,…,N−1}\mathcal{N} = \{0,\ldots,N-1\}, each taking one of K∈Z>0K \in\mathbb{Z}_{>0} categories in K={0,…,K−1}\mathcal{K} = \{0,\ldots,K-1\}. A solution can be represented by a categorical decision vector y∈KN\mathbf{y} \in\mathcal{K}^N, where yry_r denotes the category of variable rr. Equivalently, it can be represented by a one-hot matrix x\mathbf{x} in

XN,K={x∈{0,1}N×K∣x1K=1N},(1)\mathcal{X}_{N,K} = \left\{\mathbf{x} \in\{0,1\}^{N \times K} \mid\mathbf{x}\mathbf{1}_K = \mathbf{1}_N\right\}, \tag*{(1)}

where [x]rk=1[\mathbf{x}]_{rk}=1 if and only if yr=ky_r=k. The two representations are related by yr=∑k=0K−1k[x]rky_r=\sum_{k=0}^{K-1} k[\mathbf{x}]_{rk}. We can formulate an integer program with a cost function J:XN,K→RJ:\mathcal{X}_{N,K}\to\mathbb{R} and constraint functions gd:XN,K→Rg_d:\mathcal{X}_{N,K}\to\mathbb{R}, d=0,…,D−1d=0,\ldots,D-1:

X⋆:=argmin⁡x∈XN,KJ(x)(2)\mathcal{X}^{\star} := \underset{\mathbf{x}\in\mathcal{X}_{N,K}}{\operatorname{argmin}} J(\mathbf{x}) \tag*{(2)}
s.t. gd(x)≤0,d=0,…,D−1,(3)\text{s.t. } g_d(\mathbf{x})\le0,\quad d=0,\ldots,D-1, \tag*{(3)}

whose feasible set is

C={x∈XN,K∣[gd(x)≤0, ∀d∈{0,…,D−1}]}.(4)\mathcal{C}=\left\{\mathbf{x}\in\mathcal{X}_{N,K}\mid[g_d(\mathbf{x})\le0,\ \forall d\in\{0,\ldots,D-1\}]\right\}. \tag*{(4)}

Remark 1. Note that (2) covers a broad class of problems, since a category can encode any finite set of options available to a decision variable. For example, suppose each of NN robots must choose an order in which to perform TT tasks. Each category can then represent one of the K=T!K=T! permutations of the tasks. Under a fixed enumeration of these sequences, yr∈Ky_r\in\mathcal{K} indicates the specific task sequence performed by robot rr. With T=3T=3, we have K=6K=6 permutations: (0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0)(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0), which can be indexed by K={0,…,5}\mathcal{K}=\{0,\ldots,5\}, so yr=0y_r=0 means robot rr performs tasks 0, 1, and 2 in that order.

Sampling-Based Optimization

Solving (2) directly quickly becomes intractable as the problem size grows, since the solution space XN,K\mathcal{X}_{N,K} contains KNK^N elements and thus grows exponentially with NN. Sampling-based optimization (SBO) offers an alternative by recasting (2) as probabilistic inference over the target distribution

p0(x)∝pC(x) pJ(x)(5)p_0(\mathbf{x})\propto p_C(\mathbf{x})\,p_J(\mathbf{x}) \tag*{(5)}

with

pC(x):=I{x∈C},pJ(x):=exp⁡(−J(x)λ),(6)p_C(\mathbf{x}) := \mathbb{I}\{\mathbf{x} \in\mathcal{C}\}, \qquad p_J(\mathbf{x}) := \exp\left(-\frac{J(\mathbf{x})}{\lambda}\right), \tag*{(6)}

where pCp_C enforces feasibility and pJp_J puts more mass on x\mathbf{x} with lower costs [29, 32].

Recently, MBD [29] adapted the denoising process of DDPM [13] to SBO in a training-free manner by exploiting the known target distribution (4). Starting from high-variance Gaussian distributions, MBD progressively concentrates on low-cost regions through a sequence of smoothed distributions defined by its noise schedule, which makes it effective on nonconvex, non-differentiable problems [29, 41].

While the same property is also promising for combinatorial optimizations like (2), the Gaussian structure of MBD is inherently tied to continuous variables and cannot directly accommodate discrete or categorical solution spaces. This structural limitation motivates a different approach: inspired by how MBD incorporates the Gaussian diffusion process of DDPM into training-free optimization with a known target distribution, we similarly adapt the categorical diffusion process of Discrete Denoising Diffusion Probabilistic Model (D3PM) [2], the discrete counterpart of DDPM, to training-free optimization by incorporating (4) (Figure 2). The resulting training-free SBO method progressively refines solutions within the discrete solution space.

Positioning of Discrete MBD

Figure 2. Positioning of Discrete MBD. MBD [29] incorporates the Gaussian diffusion of DDPM [13] into a training-free optimizer with a known target p0(x)p_0(\mathbf{x}). Extending MBD directly to discrete solution spaces is structurally challenging, since its Gaussian diffusion processes are tied to continuous x\mathbf{x} (red arrow). Instead, we start from D3PM [2], the categorical counterpart of DDPM, and make it training-free following the same principle as MBD.

Discrete Denoising Diffusion Probabilistic Model (D3PM)

D3PM [2] extends the Gaussian diffusion framework of DDPM [13] to categorical random variables. It defines a discrete-time Markov chain over a finite categorical state space and learns to reverse it.

To describe distributions over XN,K\mathcal{X}_{N,K}, let P∈[0,1]N×KP \in[0,1]^{N \times K} be a row-stochastic matrix with rows PrP_r. For x∈XN,K\mathbf{x} \in\mathcal{X}_{N,K}, let Cat⁡(xr;Pr)\operatorname{Cat}(\mathbf{x}_r; P_r) denote the probability mass of its rr-th row xr\mathbf{x}_r under the categorical distribution with probability row vector PrP_r. We consider distributions over XN,K\mathcal{X}_{N,K} that factorize over rows:

Cat⁡(x;P):=∏r=0N−1Cat⁡(xr;Pr).(7)\operatorname{Cat}(\mathbf{x}; P) := \prod_{r=0}^{N-1} \operatorname{Cat}(\mathbf{x}_r; P_r). \tag*{(7)}

D3PM consists of a forward and a reverse process, which we describe next.

Forward (noising) process: The forward process is a fixed Markov chain

q(x(1),…,x(M)∣x(0))=∏i=1Mq(x(i)∣x(i−1)),(8)q(\mathbf{x}^{(1)}, \ldots, \mathbf{x}^{(M)} \mid\mathbf{x}^{(0)}) = \prod_{i=1}^{M} q(\mathbf{x}^{(i)} \mid\mathbf{x}^{(i-1)}), \tag*{(8)}

that progressively corrupts x(0)∼p0\mathbf{x}^{(0)} \sim p_0 into categorical noise over MM noising steps. Let Qi∈[0,1]K×KQ_i \in[0,1]^{K \times K} be the row-stochastic transition matrix at step i∈{1,…,M}i \in\{1,\ldots,M\}, whose element [Qi]ab=q([x(i)]rb∣[x(i−1)]ra=1)[Q_i]_{ab} = q([\mathbf{x}^{(i)}]_r b \mid[\mathbf{x}^{(i-1)}]_r a = 1) is the probability that the categorical variable r∈Nr \in\mathcal{N} transitions from category aa to category bb. Then,

q(x(i)∣x(i−1))=Cat⁡(x(i);x(i−1)Qi),(9)q(\mathbf{x}^{(i)} \mid\mathbf{x}^{(i-1)}) = \operatorname{Cat}(\mathbf{x}^{(i)}; \mathbf{x}^{(i-1)}Q_i), \tag*{(9)}

applies the same transition to every row independently. Defining the cumulative transition matrix Q‾i:=Q1Q2⋯Qi\overline{Q}_i := Q_1Q_2 \cdots Q_i with Q‾0=I\overline{Q}_0 = I, the Markov property gives the ii-step marginal

q(x(i)∣x(0))=Cat⁡(x(i);x(0)Q‾i),(10)q(\mathbf{x}^{(i)} \mid\mathbf{x}^{(0)}) = \operatorname{Cat}(\mathbf{x}^{(i)}; \mathbf{x}^{(0)}\overline{Q}_i), \tag*{(10)}

which allows us to sample x(i)\mathbf{x}^{(i)} directly from x(0)\mathbf{x}^{(0)}.

In [2], the rows of Q‾i\overline{Q}_i are required to converge to a known stationary distribution as i→∞i \to\infty, for which sufficient conditions are given in [2 A.1]. In this work, we construct QiQ_i to satisfy the following assumption:

Assumption 1. The forward transition matrix is uniform, Qi=(1−βi)I+βiK1K1K⊤Q_i = (1-\beta_i)I + \frac{\beta_i}{K}\mathbf{1}_K\mathbf{1}_K^\top with βi∈[0,1]\beta_i \in[0,1]. Letting αi:=1−βi\alpha_i := 1-\beta_i and α‾i:=∏s=1iαs\overline{\alpha}_i := \prod_{s=1}^{i}\alpha_s, the cumulative matrix is Q‾i=α‾iI+1−α‾iK1K1K⊤\overline{Q}_i = \overline{\alpha}_i I + \frac{1-\overline{\alpha}_i}{K}\mathbf{1}_K\mathbf{1}_K^\top [2]. The schedule is given by α‾i=a(i/M)\overline{\alpha}_i = a(i/M), where a:[0,1]→(0,1]a:[0,1] \to(0,1] is nonincreasing and LL-Lipschitz, with a(0)=1a(0)=1 and a(τ)<1a(\tau)<1 for τ∈(0,1]\tau\in(0,1].

The uniform kernel [2, 15] in Assumption 1 is doubly stochastic, so the uniform distribution is stationary [2 A.1]. Using that, we define

pM(x(M)):=Cat⁡(x(M);1K1N1K⊤).(11)p_M(\mathbf{x}^{(M)}) := \operatorname{Cat}\left(\mathbf{x}^{(M)}; \frac{1}{K}\mathbf{1}_N\mathbf{1}_K^\top\right). \tag*{(11)}

Reverse (denoising) process: The reverse process starts from x(M)∼pM\mathbf{x}^{(M)} \sim p_M and aims to recover a low-cost solution. At each step i=M,…,1i=M,\ldots,1, x(i−1)\mathbf{x}^{(i-1)} is sampled from the learned reverse transition

pθ(x(i−1)∣x(i))=∑x~(0)q(x(i−1)∣x(i),x~(0))pθ(x~(0)∣x(i)),(12)p_\theta(\mathbf{x}^{(i-1)} \mid\mathbf{x}^{(i)}) = \sum_{\widetilde{\mathbf{x}}^{(0)}} q(\mathbf{x}^{(i-1)} \mid\mathbf{x}^{(i)}, \widetilde{\mathbf{x}}^{(0)})p_\theta(\widetilde{\mathbf{x}}^{(0)} \mid\mathbf{x}^{(i)}), \tag*{(12)}

with the posterior distribution

q(x(i−1)∣x(i),x(0))=q(x(i)∣x(i−1))q(x(i−1)∣x(0))q(x(i)∣x(0))(13)q(\mathbf{x}^{(i-1)} \mid\mathbf{x}^{(i)}, \mathbf{x}^{(0)}) = \frac{q(\mathbf{x}^{(i)} \mid\mathbf{x}^{(i-1)})q(\mathbf{x}^{(i-1)} \mid\mathbf{x}^{(0)})}{q(\mathbf{x}^{(i)} \mid\mathbf{x}^{(0)})} \tag*{(13)}
=∏r=0N−1Cat⁡(xr(i−1);xr(i)Qi⊤⊙xr(0)Q‾i−1xr(0)Q‾i(xr(i))⊤),(14)= \prod_{r=0}^{N-1} \operatorname{Cat}\left(\mathbf{x}^{(i-1)}_r; \frac{\mathbf{x}^{(i)}_r Q_i^\top\odot\mathbf{x}^{(0)}_r\overline{Q}_{i-1}}{\mathbf{x}^{(0)}_r\overline{Q}_i(\mathbf{x}^{(i)}_r)^\top}\right), \tag*{(14)}

which follows from Bayes’ theorem and the Markov property of the forward process.

Each factor in (12b) is the D3PM posterior [2 Eq. (3)] applied to row rr. Because this posterior is available in closed form, D3PM trains a neural network only to predict the clean-solution distribution pθ(x~(0)∣x(i))p_\theta(\tilde{\mathbf{x}}^{(0)} \mid\mathbf{x}^{(i)}). Then, (11) is used to sample x(i−1)\mathbf{x}^{(i-1)} for the next denoising step.

Discrete Model-Based Diffusion

We propose Discrete Model-Based Diffusion (Discrete MBD), which shares the forward and reverse processes of D3PM but performs denoising in a training-free manner. Discrete MBD differs from D3PM in two ways: (a) instead of learning the reverse transition p(x(i−1)∣x(i))p(\mathbf{x}^{(i-1)} \mid\mathbf{x}^{(i)}) (11) through offline training, it approximates it with the target distribution p0p_0 (4), and (b) it aims to find a minimum-cost solution of (2) rather than merely generate feasible solutions.

DMBD for Generic Optimization

We first present Discrete MBD for a generic combinatorial optimization problem. Its adaptation to heterogeneous MRTA problems is discussed in Section IV.

Discrete MBD’s reverse process starts with sampling x(M)∼pM\mathbf{x}^{(M)} \sim p_M (10). At each denoising step i=M,…,1i = M,\ldots,1, Discrete MBD (a) samples candidate solutions from a proposal, (b) uses them to approximate p(x(i−1)∣x(i))p(\mathbf{x}^{(i-1)} \mid\mathbf{x}^{(i)}), and (c) samples again from the approximated distribution and selects the best sample as x(i−1)\mathbf{x}^{(i-1)}.

(a) Sample. By Bayes’ theorem, we have p(x(0)∣x(i))∝q(x(i)∣x(0))p0(x(0))p(\mathbf{x}^{(0)} \mid\mathbf{x}^{(i)}) \propto q(\mathbf{x}^{(i)} \mid\mathbf{x}^{(0)})p_0(\mathbf{x}^{(0)}). However, since p0p_0 couples all rows of x(0)\mathbf{x}^{(0)}, sampling from the normalized posterior requires summing over all KNK^N elements of XN,K\mathcal{X}_{N,K}, which is intractable.

Instead, we construct a tractable proposal by examining the structure of the posterior. Note that (i) q(x(i)∣x(0))q(\mathbf{x}^{(i)} \mid\mathbf{x}^{(0)}) factorizes over rows (9), with q(xr(i)∣xr(0))=xr(0)(xr(i)QiT)T=xr(0)(x(i)QiT)Tq(\mathbf{x}^{(i)}_r \mid\mathbf{x}^{(0)}_r) = \mathbf{x}^{(0)}_r(\mathbf{x}^{(i)}_r\mathbf{Q}_i^\mathsf{T})^\mathsf{T} = \mathbf{x}^{(0)}_r(\mathbf{x}^{(i)}\mathbf{Q}_i^\mathsf{T})^\mathsf{T}, and (ii) Qi\mathbf{Q}_i is doubly stochastic by Assumption 1. By (i), the likelihood of each row xr(0)\mathbf{x}^{(0)}_r is given by xr(i)QiT\mathbf{x}^{(i)}_r\mathbf{Q}_i^\mathsf{T}, which by (ii) sums to one and thus defines a categorical distribution over xr(0)\mathbf{x}^{(0)}_r. Hence, our proposal is

ϕi(x(0)):=Cat⁡(x(0);x(i)QiT),(15)\phi_i(\mathbf{x}^{(0)}) := \operatorname{Cat}(\mathbf{x}^{(0)};\mathbf{x}^{(i)}\mathbf{Q}_i^\mathsf{T}), \tag*{(15)}

whose rows can be sampled independently. From the proposal ϕi\phi_i (13), we then draw a batch XS1\mathcal{X}_{S_1} of S1S_1 candidate solutions.

(b) Approximate. By construction, ϕi(x(0))=q(x(i)∣x(0))\phi_i(\mathbf{x}^{(0)}) = q(\mathbf{x}^{(i)} \mid\mathbf{x}^{(0)}) for all x(0)∈XN,K\mathbf{x}^{(0)} \in\mathcal{X}_{N,K}. Substituting this into Bayes’ theorem with the fact that ϕi\phi_i is normalized, we get

p(x(0)∣x(i))=q(x(i)∣x(0))p0(x(0))∑x∈XN,Kq(x(i)∣x)p0(x)(16)p(\mathbf{x}^{(0)} \mid\mathbf{x}^{(i)}) = \frac{q(\mathbf{x}^{(i)} \mid\mathbf{x}^{(0)})p_0(\mathbf{x}^{(0)})} {\sum_{\mathbf{x}\in\mathcal{X}_{N,K}}q(\mathbf{x}^{(i)}\mid\mathbf{x})p_0(\mathbf{x})} \tag*{(16)}
=ϕi(x(0))p0(x(0))Ex∼ϕi[p0(x)].(17)= \frac{\phi_i(\mathbf{x}^{(0)})p_0(\mathbf{x}^{(0)})} {\mathbb{E}_{\mathbf{x}\sim\phi_i}[p_0(\mathbf{x})]}. \tag*{(17)}
Algorithm 1: Discrete Model-Based Diffusion
(Discrete MBD) for Generic Optimization
Inputstemperature λ\lambda, denoising steps MM, sample counts S1S_1, S2S_2
OutputsFinal solution x(0)\mathbf{x}^{(0)}
1Initialize x(M)∼pM(x)=Cat⁡(⋅;1K1N1KT)\mathbf{x}^{(M)} \sim p_M(\mathbf{x}) = \operatorname{Cat}(\cdot; \frac{1}{K}\mathbf{1}_N\mathbf{1}_K^\mathsf{T})
2for i=M,…,1i=M,\ldots,1 do
3Sample XS1∼ϕi(⋅)=Cat⁡(⋅;x(i)QiT)\mathcal{X}_{S_1} \sim\phi_i(\cdot) = \operatorname{Cat}(\cdot;\mathbf{x}^{(i)}\mathbf{Q}_i^\mathsf{T})
4Update the distribution (15):
p^i(x(i−1)∣x(i))=∑xs∈XS1q(x(i−1)∣x(i),xs)p0(xs)∑xs∈XS1p0(xs)\hat{p}_i(\mathbf{x}^{(i-1)}\mid\mathbf{x}^{(i)}) = \frac{\sum_{\mathbf{x}_s\in\mathcal{X}_{S_1}}q(\mathbf{x}^{(i-1)}\mid\mathbf{x}^{(i)},\mathbf{x}_s)p_0(\mathbf{x}_s)}{\sum_{\mathbf{x}_s\in\mathcal{X}_{S_1}}p_0(\mathbf{x}_s)}
5
6Sample XS2∼p^i(⋅∣x(i))\mathcal{X}_{S_2} \sim\hat{p}_i(\cdot\mid\mathbf{x}^{(i)})
7Select x(i−1)∈arg⁡max⁡xs∈XS1∪XS2 p0(xs)\mathbf{x}^{(i-1)}\in\underset{\mathbf{x}_s\in\mathcal{X}_{S_1}\cup\mathcal{X}_{S_2}}{\arg\max}\ p_0(\mathbf{x}_s)
8return x(0)\mathbf{x}^{(0)}.

Table 1.

Substituting (14) into (11) in place of pθ(x~(0)∣x(i))p_\theta(\tilde{\mathbf{x}}^{(0)}\mid\mathbf{x}^{(i)}) gives

pi(x(i−1)∣x(i))=∑x(0)q(x(i−1)∣x(i),x~(0))p(x~(0)∣x(i))=∑x~(0)q(x(i−1)∣x(i),x~(0))ϕi(x~(0))p0(x~(0))Ex∼ϕi[p0(x)]=Ex∼ϕi[q(x(i−1)∣x(i),x)p0(x)]Ex∼ϕi[p0(x)],\begin{aligned} p_i(\mathbf{x}^{(i-1)}\mid\mathbf{x}^{(i)}) = \sum_{\mathbf{x}^{(0)}}q(\mathbf{x}^{(i-1)}\mid\mathbf{x}^{(i)},\tilde{\mathbf{x}}^{(0)})p(\tilde{\mathbf{x}}^{(0)}\mid\mathbf{x}^{(i)}) \\ &= \frac{\sum_{\tilde{\mathbf{x}}^{(0)}}q(\mathbf{x}^{(i-1)}\mid\mathbf{x}^{(i)},\tilde{\mathbf{x}}^{(0)})\phi_i(\tilde{\mathbf{x}}^{(0)})p_0(\tilde{\mathbf{x}}^{(0)})}{\mathbb{E}_{\mathbf{x}\sim\phi_i}[p_0(\mathbf{x})]} \\ &= \frac{\mathbb{E}_{\mathbf{x}\sim\phi_i}[q(\mathbf{x}^{(i-1)}\mid\mathbf{x}^{(i)},\mathbf{x})p_0(\mathbf{x})]}{\mathbb{E}_{\mathbf{x}\sim\phi_i}[p_0(\mathbf{x})]}, \end{aligned}

which we approximate using the samples XS1\mathcal{X}_{S_1} drawn from ϕi\phi_i:

pi(x(i−1)∣x(i))≈∑xs∈XS1q(x(i−1)∣x(i),xs)p0(xs)∑xs∈XS1p0(xs)=:p^i(x(i−1)∣x(i)).(18)p_i(\mathbf{x}^{(i-1)}\mid\mathbf{x}^{(i)}) \approx \frac{\sum_{\mathbf{x}_s\in\mathcal{X}_{S_1}}q(\mathbf{x}^{(i-1)}\mid\mathbf{x}^{(i)},\mathbf{x}_s)p_0(\mathbf{x}_s)} {\sum_{\mathbf{x}_s\in\mathcal{X}_{S_1}}p_0(\mathbf{x}_s)} =: \hat{p}_i(\mathbf{x}^{(i-1)}\mid\mathbf{x}^{(i)}). \tag*{(18)}

(c) Select. We draw S2S_2 candidate solutions XS2\mathcal{X}_{S_2} from p^i\hat{p}_i (15). Then we choose the lowest-cost candidate from XS:=XS1∪XS2\mathcal{X}_S := \mathcal{X}_{S_1}\cup\mathcal{X}_{S_2} to get x(i−1)∈arg⁡max⁡xs∈XS p0(xs)\mathbf{x}^{(i-1)} \in\underset{\mathbf{x}_s\in\mathcal{X}_S}{\arg\max}\ p_0(\mathbf{x}_s).

After MM denoising steps, Discrete MBD returns x(0)\mathbf{x}^{(0)} as its final solution. Algorithm 1 summarizes the procedure.

Similarity with MBD: Discrete MBD builds on the structure of D3PM in the same way that MBD [29] builds on DDPM. In particular, the proposal (13) is the categorical counterpart of [29, Eq. (8)}, and the approximation (15) parallels the Monte Carlo score estimate in [29, Eq. [9]].

Distinctions from D3PM: Compared to D3PM, our method has two key distinctions. First, rather than learning the reverse transition distribution, Discrete MBD approximates it with samples, whose costs are evaluated directly by (4). Many extensions of D3PM also exploit problem knowledge, but only on top of a learned denoiser, either as guidance [21, 22, 23] or as the training objective [33, 34].

Second, while D3PM produces a single intermediate solution x(i)\mathbf{x}^{(i)} at the end of each denoising step ii, Discrete MBD generates multiple candidate solutions and selects the lowest-cost one. This reflects their different goals: D3PM primarily focuses on the generative aspect of modeling the target distribution, whereas Discrete MBD wants to find an optimal solution. Accordingly, Discrete MBD greedily selects the best solution at each denoising step to steer the diffusion process toward low-cost regions. A similar selection appears in [22], but it again relies on a pretrained model and/or a learned or approximated value function.

Visualization of denoising process in Discrete Model-Based Diffusion

Figure 3. Visualization of denoising process in Discrete Model-Based Diffusion (Discrete MBD) in the heterogeneous MRTA problem from Figure 1. By performing diffusion directly over the discrete solution space of coalition formations and routes, the reverse transition distribution progressively concentrates its probability mass in solutions with shorter makespans, steering the search toward high-quality solutions.

**Role of QiQ_i: ** Similar to D3PM, the transition matrices QiQ_i govern how Discrete MBD explores XN,K\mathcal{X}_{N,K}. Under Assumption 1, each row of x′∼ϕix' \sim\phi_i stays the same with probability αˉi+(1−αˉi)/K\bar{\alpha}_i + (1-\bar{\alpha}_i)/K, and otherwise switches to one of the other categories uniformly at random. In the early stage of the algorithm (large ii), αˉi\bar{\alpha}_i remains relatively small, making ϕi\phi_i closer to uniform and inducing exploration. As ii decreases, αˉi→1\bar{\alpha}_i \to1 and ϕi\phi_i places more probability mass around x(i)x^{(i)}, performing local refinement. The schedule aa thus controls the exploration-exploitation trade-off, which we analyze formally in the next subsection.

Theoretical Analysis

Here we establish a probabilistic convergence guarantee for our method toward the set of global minimizers X⋆⊆C\mathcal{X}^{\star} \subseteq\mathcal{C}.

Theorem 1. Let Assumption 1 hold, C≠∅\mathcal{C} \ne\emptyset, and S1≥S2≥1S_1 \ge S_2 \ge1. Define γN:=∫01(1−a(τ))N dτ\gamma_N := \int_0^1 (1-a(\tau))^N \, \mathrm{d}\tau, ρ:=N2L/amin⁡\rho:= N^2L/a_{\min}, where amin⁡:=a(1)a_{\min} := a(1), and [ ⋅ ]+:=max⁡{0,⋅}[\,\cdot\,]_+ := \max\{0,\cdot\}. Then, for every M∈Z>0M \in\mathbb{Z}_{>0}, and λ>0\lambda> 0,

Pr⁡(x(0)∈X⋆)≥(1−(1−γNKN)S1M)[1−ρS2MS2−1]+(19)\Pr\left(x^{(0)} \in\mathcal{X}^{\star}\right) \ge\left(1-\left(1-\frac{\gamma_N}{K^N}\right)^{S_1M}\right)\left[1-\frac{\rho^{S_2}}{M^{S_2-1}}\right]_+ \tag*{(19)}

Proof. The proof is given in Section VII. ■

Exploration-exploitation trade-off: The first term on the right-hand side of (16) lower-bounds the probability of sampling a minimizer in X⋆\mathcal{X}^{\star} at least once, and the second term lower-bounds the probability of remaining in X⋆\mathcal{X}^{\star} until the end of the algorithm. Together, they characterize the exploration-exploitation trade-off. A faster-decaying noise schedule aa keeps the noise level 1−αˉi1-\bar{\alpha}_i high for longer, which increases γN\gamma_N and the first term. This matches the intuition that higher noise makes ϕi\phi_i closer to uniform and promotes exploration.

At the same time, it requires a larger LL, which increases ρ\rho and shrinks the second term, consistent with the intuition that more exploration weakens exploitation. A similar trade-off for diffusion-based methods is discussed in [41].

Effects of sample sizes and diffusion steps: Based on Theorem 1, increasing the sample sizes S1S_1 and S2S_2 or the number of denoising steps MM raises the guaranteed probability of finding an optimal solution whenever the bound is nontrivial, i.e., MS2−1>ρS2M^{S_2-1} > \rho^{S_2}. More importantly, as M→∞M \to\infty, this lower bound monotonically increases for any S1≥S2≥2S_1 \ge S_2 \ge2 and λ>0\lambda> 0. This is consistent with the empirical results from [33, 37], where more denoising steps yield better solutions.

DMBD for Heterogeneous MRTA

Problem setup: We now apply Discrete MBD to the heterogeneous MRTA problem of Section I and Figure 1, an XD [ST-MR-TA] instance in the taxonomy of [18]. Consider a team of RR heterogeneous robots R={0,…,R−1}\mathcal{R}=\{0,\ldots,R-1\} and TT spatially distributed tasks T={0,…,T−1}\mathcal{T}=\{0,\ldots,T-1\} in the domain D:=[0,1]2\mathcal{D}:=[0,1]^2, with BB skill types B={0,…,B−1}\mathcal{B}=\{0,\ldots,B-1\}. We adopt the species-traits model [9, 11], where each robot belongs to one of the SS species, each with a unique set of skills. Robot rr has a capability vector cr∈Z≥0B\mathbf{c}_r \in\mathbb{Z}_{\ge0}^{B}, whose bbth entry is its capability level in skill bb, a depot or∈Do_r \in\mathcal{D}, and a speed vr>0v_r > 0, so that it travels between z,z′∈Dz,z' \in\mathcal{D} in time Δr(z,z′):=∥z−z′∥2/vr\Delta_r(z,z') := \lVert z-z' \rVert_2/v_r. Task jj has a location pj∈Dp_j \in\mathcal{D}, a duration δj>0\delta_j > 0, and a nonzero combined capability requirement vector for skills wj∈Z≥0Bw_j \in\mathbb{Z}_{\ge0}^{B}, whose bbth entry is the required minimum combined capability in skill bb.

A solution consists of a coalition Lj⊆R\mathcal{L}_j \subseteq\mathcal{R} and a start time tj≥0t_j \ge0 for each task jj, and a route πr=(πr,0,…,πr,mr−1)\pi_r=(\pi_{r,0},\ldots,\pi_{r,m_r-1}) for each robot rr, which lists the mrm_r tasks {j∈T:r∈Lj}\{j \in\mathcal{T}:r \in\mathcal{L}_j\} assigned to robot rr in visiting order, starting and ending at its depot oro_r. Under tight coordination, task jj starts only once all members of Lj\mathcal{L}_j have arrived, and all members remain at pjp_j until tj+δjt_j+\delta_j. Minimizing the makespan Cmax⁡C_{\max}, i.e., the time at which the last robot returns to its depot, yields

min⁡{Lj},{πr},{tj},Cmax⁡Cmax⁡s.t.∑r∈Ljcr⪰wj,∀j∈T,tπr,0≥Δr(or,pπr,0),∀r∈R:mr>0,tπr,ℓ+1≥tπr,ℓ+δπr,ℓ+Δr(pπr,ℓ,pπr,ℓ+1),∀r∈R, ℓ=0,…,mr−2,Cmax⁡≥tπr,mr−1+δπr,mr−1+Δr(pπr,mr−1,or),∀r∈R:mr>0.(20)\begin{aligned} \min_{\{L_j\},\{\pi_r\},\{t_j\},C_{\max}}\quad& C_{\max}\\ \text{s.t.}\quad& \sum_{r\in L_j} c_r \succeq w_j,\quad\forall j\in\mathcal{T},\\ & t_{\pi_{r,0}} \ge\Delta_r(o_r,p_{\pi_{r,0}}),\quad\forall r\in\mathcal{R}:m_r>0,\\ & t_{\pi_{r,\ell+1}} \ge t_{\pi_{r,\ell}}+\delta_{\pi_{r,\ell}}+\Delta_r(p_{\pi_{r,\ell}},p_{\pi_{r,\ell+1}}),\quad\forall r\in\mathcal{R},\ \ell=0,\ldots,m_r-2,\\ & C_{\max}\ge t_{\pi_{r,m_r-1}}+\delta_{\pi_{r,m_r-1}}+\Delta_r(p_{\pi_{r,m_r-1}},o_r),\quad\forall r\in\mathcal{R}:m_r>0. \tag*{(20)} \end{aligned}

We assume problem (17) itself is feasible, i.e., ∑r∈Rcr⪰wj\sum_{r\in\mathcal{R}}c_r\succeq w_j for all j∈Tj\in\mathcal{T}.

We study three variants, SS-BT, SS-AT, and MS-AT, which differ in robot skills and task requirements. In SS (single-skill agents), robots have one skill, i.e., crc_r has exactly one nonzero entry, whereas in MS (multi-skill agents), robots may have several skills. In BT (binary tasks), wj∈{0,1}Bw_j\in\{0,1\}^{B}, so one capable robot per required skill satisfies (17b). In AT (additive tasks), requirements are general nonnegative integers that the coalition must meet through its combined capabilities.

Priority-based encoding: Discrete MBD could be directly applied to (17), but most of its samples would violate the constraints, severely reducing sample efficiency. Thus, following [4, 36], we instead represent candidate solutions as robot-task priorities that can be decoded into feasible solutions for (17). The decision variable is x∈XRT,Tx\in\mathcal{X}_{RT,T}, where each row indexed by (r,j)∈R×T(r,j)\in\mathcal{R}\times\mathcal{T} specifies the priority level robot rr assigns to task jj. The entry [x](r,j)k=1[x]_{(r,j)k}=1 indicates priority level kk, with smaller kk denoting higher priority. We evaluate each candidate xx by decoding it into a solution as follows.

Decoding: Given x∈XRT,Tx\in\mathcal{X}_{RT,T}, let κrj(x)∈{0,…,T−1}\kappa_{rj}(x)\in\{0,\ldots,T-1\} denote the priority level that robot rr assigns to task jj, i.e., [x](r,j)κrj(x)=1[x]_{(r,j)\kappa_{rj}(x)}=1. We then evaluate xx on (17) as follows.

(a) Coalition formation. For each task j∈Tj\in\mathcal{T}, visit the robots from highest to lowest priority for task jj (i.e., increasing κrj(x)\kappa_{rj}(x), breaking ties by robot index). Add robot rr to Lj(x)L_j(x) only if doing so reduces the unmet requirement ∑b∈Bmax⁡{[wj]b−∑r′∈Lj(x)[cr′]b,0}\sum_{b\in\mathcal{B}}\max\{[w_j]_b-\sum_{r'\in L_j(x)}[c_{r'}]_b,0\}.

(b) Coalition pruning (only for MS-AT). Since robots may possess several skills in MS-AT, Lj(x)L_j(x) can contain a larger team than necessary. For each task j∈Tj\in\mathcal{T}, visit the members of Lj(x)L_j(x) from lowest to highest priority (breaking ties by robot index) and remove robot rr whenever the remaining coalition still meets the requirement, i.e., ∑r′∈Lj(x)∖{r}cr′⪰wj\sum_{r'\in L_j(x)\setminus\{r\}}c_{r'}\succeq w_j.

(c) Global task ordering. To enforce a global order over tasks, each robot visits its assigned tasks in order of their coalition’s average priority, sj(x):=1∣Lj(x)∣∑r∈Lj(x)κrj(x)s_j(x):=\frac{1}{|L_j(x)|}\sum_{r\in L_j(x)}\kappa_{rj}(x), from highest to lowest priority (i.e., ascending sjs_j), breaking ties by task index.

(d) Scheduling. Simulate the resulting routes, starting each task as soon as all coalition members arrive. This yields the start and end times of all tasks and the makespan as J(x)=Cmax⁡J(x)=C_{\max}.

These steps decode every x∈XRT,Tx\in\mathcal{X}_{RT,T} into a feasible solution of (17). Steps (a)-(b) select coalitions that satisfy (17b). Step (c) prevents cyclic waiting among coalitions, satisfying the routing constraints (17c)–(17e). Hence, Discrete MBD applies directly with p0(x)∝exp⁡(−J(x)/λ)p_0(x)\propto\exp(-J(x)/\lambda).

Remark 2. Our priority-based encoding improves the sample efficiency of Discrete MBD by ensuring that every sample decodes into a feasible solution. However, the encoding is neither injective nor surjective: different priority assignments may be decoded to the same plan, and some solutions of (17) may not be representable. A common alternative is penalty-based constraint handling, which penalizes infeasible solutions. More general approaches to constraint handling while maintaining sample efficiency for Discrete MBD remain future work.

Simulation Results

We evaluate Discrete MBD on generic, unconstrained integer programs and on heterogeneous MRTA, addressing two questions: Q1. How does Discrete MBD compare with other SBO methods in solution quality and computation time? Q2. How does it compare with exact, metaheuristic, and learning-based methods?

Experimental Setup

Metrics: We report the mean objective value (cost for generic integer programs, makespan for MRTA) and the computation time per instance, averaged over 5 solver seeds and all problem instances. Computation times exclude one-time JIT compilation. Averages include only runs in which the solver returns a feasible solution.

Implementation: All methods are implemented in Python using JAX [7], with sample evaluations parallelized on an NVIDIA RTX 3080 Ti GPU, while Gurobi [12] runs on the CPU. All experiments are conducted on a computer equipped with an Intel Core i9-12900KF CPU and 64 GB of RAM. For Discrete MBD, we use temperature λ=10−5\lambda=10^{-5} and the uniform transition matrix with the cosine schedule of [2, 15]. At each denoising step, we allocate 75% of the samples to S1S_1 and the remaining 25% to S2S_2.

Unconstrained Problems

Settings: We consider two classes of unconstrained problems over NN variables with KK categories each. Both are written in terms of the integer vector y∈{0,…,K−1}N\mathbf{y}\in\{0,\ldots,K-1\}^{N}, with [y]r:=∑k=0K−1[x]rk[y]_r:=\sum_{k=0}^{K-1}[x]_{rk}. For each problem class and pair N,K∈{10,50,100}N,K\in\{10,50,100\}, we evaluate methods on 50 random instances.

Unconstrained Integer Quadratic Program (UIQP):

min⁡y∈{0,…,K−1}NyTRy+hTy,(21)\min_{\mathbf{y}\in\{0,\ldots,K-1\}^{N}}\quad\mathbf{y}^{\mathsf{T}}\mathbf{R}\mathbf{y}+\mathbf{h}^{\mathsf{T}}\mathbf{y}, \tag*{(21)}

where R∈RN×N\mathbf{R}\in\mathbb{R}^{N\times N} is symmetric and indefinite and h∈RN\mathbf{h}\in\mathbb{R}^{N}. For K=2K=2, (18) reduces to quadratic unconstrained binary optimization (QUBO), which is equivalent to an Ising problem [24]. We set R:=12(R′+(R′)T)\mathbf{R}:=\frac{1}{2}(\mathbf{R}'+(\mathbf{R}')^{\mathsf{T}}) with [R′]ij∼N(0,1)[\mathbf{R}']_{ij}\sim\mathcal{N}(0,1) i.i.d., and h∼N(0,I)\mathbf{h}\sim\mathcal{N}(0,\mathbf{I}).

Method\multicolumn{6}{c}{UIQP}\multicolumn{6}{c}{UPO}
\multicolumn{2}{c}{K=10K=10}\multicolumn{2}{c}{K=50K=50}\multicolumn{2}{c}{K=100K=100}\multicolumn{2}{c}{K=10K=10}\multicolumn{2}{c}{K=50K=50}\multicolumn{2}{c}{K=100K=100}
Cost ↓\downarrowTime (s) ↓\downarrowCost ↓\downarrowTime (s) ↓\downarrowCost ↓\downarrowTime (s) ↓\downarrowCost ↓\downarrowTime (s) ↓\downarrowCost ↓\downarrowTime (s) ↓\downarrowCost ↓\downarrowTime (s) ↓\downarrow
\multicolumn{13}{c}{N=10N=10}
Gurobi (30 s)−10.01-10.010.11−2.95-2.950.19−1.20-1.200.51−10.01-10.0122.16−4.72-4.7230†30^{\dagger}−1.57-1.5730†30^{\dagger}
CEM−9.78-9.780.47−2.79-2.790.47−1.13-1.130.47−9.71‾\underline{-9.71}0.48−4.37-4.370.48−1.45-1.450.49
SMC−9.85‾\underline{-9.85}0.86−2.89‾\underline{-2.89}0.86−1.18-1.180.86−9.59‾\underline{-9.59}0.86−4.61‾\underline{-4.61}0.86−1.55‾\underline{-1.55}0.86
Rounded MBD−9.75-9.750.47−2.49‾\underline{-2.49}0.47−0.93‾\underline{-0.93}0.56−9.22-9.220.47−2.98-2.980.46−0.80-0.800.56
Discrete MBD (ours)−9.84\mathbf{-9.84}0.56−2.90\mathbf{-2.90}0.58−1.18\mathbf{-1.18}0.61−9.81\mathbf{-9.81}0.57−4.69\mathbf{-4.69}0.58−1.57\mathbf{-1.57}0.61
Scale10210^2–10410^4–10510^5–10510^5–10910^9–101110^{11}–
\multicolumn{13}{c}{N=50N=50}
Gurobi (30 s)−1.17-1.1727.24−3.46-3.4630†30^{\dagger}−1.41-1.4130†30^{\dagger}−2.28-2.2830†30^{\dagger}−1.08-1.0830†30^{\dagger}−3.69-3.6930†30^{\dagger}
CEM−1.14-1.140.47−3.16-3.160.48−1.28-1.280.49−2.14-2.140.48−0.90-0.900.49−2.95-2.950.50
SMC−1.18‾\underline{-1.18}0.87−3.27‾\underline{-3.27}0.87−1.32‾\underline{-1.32}0.87−2.28‾\underline{-2.28}0.86−0.96‾\underline{-0.96}0.86−3.14‾\underline{-3.14}0.86
Rounded MBD−0.82-0.820.45−1.65-1.650.48−0.52-0.520.44−1.10-1.100.45−0.23-0.230.48−0.38-0.380.44
Discrete MBD (ours)−1.20\mathbf{-1.20}0.60−3.54\mathbf{-3.54}0.59−1.43\mathbf{-1.43}0.60−2.35\mathbf{-2.35}0.60−1.12\mathbf{-1.12}0.59−3.70\mathbf{-3.70}0.60
Scale10410^4–10510^5–10610^6–10610^6–101010^{10}–101110^{11}–
\multicolumn{13}{c}{N=100N=100}
Gurobi (30 s)−3.30-3.3030†30^{\dagger}−0.98-0.9830†30^{\dagger}−4.00-4.0030†30^{\dagger}−3.24-3.2430†30^{\dagger}−1.56-1.5630†30^{\dagger}−5.22-5.2230†30^{\dagger}
CEM−3.04-3.040.47−0.83‾\underline{-0.83}0.49−3.35‾\underline{-3.35}0.50−2.68‾\underline{-2.68}0.48−1.11‾\underline{-1.11}0.51−3.61‾\underline{-3.61}0.52
SMC−2.80-2.800.92−0.75-0.750.93−3.05-3.050.93−2.37-2.370.92−0.95-0.950.93−3.14-3.140.93
Rounded MBD−1.75-1.750.45−0.32-0.320.44−0.98-0.980.47−0.99-0.990.45−0.19-0.190.44−0.31-0.310.47
Discrete MBD (ours)−3.33\mathbf{-3.33}0.59−0.93\mathbf{-0.93}0.58−3.76\mathbf{-3.76}0.58−3.22\mathbf{-3.22}0.59−1.39\mathbf{-1.39}0.58−4.58\mathbf{-4.58}0.58
Scale10410^4–10610^6–10610^6–10610^6–101010^{10}–101110^{11}–

Table 1 (PDF p. 7). MEAN COST AND RUNTIME (S) ON UNCONSTRAINED UIQP AND UPO OVER 50 INSTANCES ACROSS 5 SOLVER SEEDS. COSTS SHARE THE SCALE FACTOR SHOWN; BOLD/UNDERLINE MARK THE BEST/SECOND-BEST METHOD BESIDES GUROBI WITH 30 S LIMIT (†\dagger: GUROBI HIT ITS 30 S TIME LIMIT).

Unconstrained Polynomial Optimization (UPO)

min⁡y∈{0,…,K−1}N∑u=1Uμu∏r∈Puyr(22)\min_{y\in\{0,\ldots,K-1\}^{N}} \sum_{u=1}^{U}\mu_u\prod_{r\in\mathcal{P}_u}y_r \tag*{(22)}

where monomial uu has coefficient μu∈R\mu_u\in\mathbb{R} and index set Pu⊆{0,…,N−1}\mathcal{P}_u\subseteq\{0,\ldots,N-1\}. For K=2K=2, (19) is a pseudo-Boolean optimization problem [6]. We use U=250U=250 monomials, each over ∣Pu∣=5|\mathcal{P}_u|=5 distinct variables chosen uniformly at random, which keeps the objective magnitude moderate and ensures numerical stability.

Baselines: We consider three SBO methods: the cross-entropy method (CEM) [32] with an elite fraction of 1%; sequential Monte Carlo (SMC) [10], which mutates each particle by resampling 10% of its variables; and Rounded MBD, which runs MBD with temperature λ=10−5\lambda=10^{-5} on the relaxation [−1,1]N×K[-1,1]^{N\times K} with the cosine noise schedule [28], and rounds each sample to a one-hot form via a row-wise argmax, as in [37]. For reference on solution quality only, we also report Gurobi [12] with a 30 s time limit, averaged over 5 initial states. All methods, including Discrete MBD, run for M=100M=100 iterations with 2048 samples per iteration.

Results (Q1): Table I shows that Discrete MBD achieves the lowest average cost among the SBO methods in 17 out of 18 settings. The only exception is the smallest size (N=K=10N=K=10), where it is still within 0.1% of the best. Discrete MBD takes about 0.6 s per problem, slightly more than CEM and Rounded MBD. Overall, Discrete MBD offers the best solution quality among SBO methods at comparable computational cost.

Multi-Robot Coalition and Scheduling

Settings: We now consider the heterogeneous MRTA problem (17), using the benchmark environment and test sets of [9]. Following [9], we consider five configurations of (R,S,T,B)(R,S,T,B) (Table II) for each of the three variants SS-BT, SS-AT, and MS-AT (called SA-BT, SA-AT, and MA-AT therein), giving 15 settings with 50 instances each. A run is successful if it returns a deadlock-free plan that completes every task.

Baselines: We group the baselines into four categories. (i) MILP-based: CTAS-D [11], which solves a mixed-integer linear program with Gurobi [12] to optimize the flow of each species over the tasks, then rounds the flows to integers to obtain robot routes. We use a 30 s time limit per instance. (ii) Learning-based: RL(s.10) [9], a reinforcement-learning policy trained on MS-AT instances. It runs each instance 10 times with Boltzmann action selection and returns the plan with the lowest makespan. (iii) Metaheuristics: large neighborhood search (LNS) [30], which destroys 10% of the variables and repairs them with kk-exchange neighborhoods, and simulated annealing (SA) [5] with initial temperature 1.0 and cooling factor 0.95. (iv) SBO: CEM, SMC, and Rounded MBD from Section V-B, with the same hyperparameters. All sampling-based baselines (metaheuristics and SBO) and Discrete MBD use the encoding scheme described in Section IV and are run for M=350M=350 iterations, with 2048 samples per iteration.

Results (Q1 & Q2): As shown in Table II, Discrete MBD achieves the lowest makespan among the SBO methods in 14 out of 15 configurations, lagging behind only on the smallest SS-BT instance (R=9R=9). In fact, its performance advantage also widens as the problem size grows. Against all baselines, Discrete MBD achieves the lowest makespan in 8 of 15 settings and the second lowest in the remaining 7. RL(s.10) performs better on larger configurations, where Discrete MBD, like other sampling-based methods, suffers from lower sample efficiency. Unlike RL(s.10), however, Discrete MBD is training-free while still finding competitive solutions within 3.7 s. CTAS-D fails to find feasible solutions within 30 s on many instances (as shown in the superscripts indicating the success rates), making it unsuitable for online planning. Overall, Discrete MBD matches or closely approaches the strongest baseline in every setting while remaining training-free and fast enough for online use.

MethodR=9, S=3R=9,\ S=3 T=20, B=3T=20,\ B=3 Makespan ↓Time (s) ↓R=15, S=5R=15,\ S=5 T=20, B=5T=20,\ B=5 Makespan ↓Time (s) ↓R=25, S=5R=25,\ S=5 T=20, B=5T=20,\ B=5 Makespan ↓Time (s) ↓R=25, S=5R=25,\ S=5 T=50, B=5T=50,\ B=5 Makespan ↓Time (s) ↓R=50, S=5R=50,\ S=5 T=50, B=5T=50,\ B=5 Makespan ↓Time (s) ↓
SS-BT
CTAS-D (30 s)31.3961%3040.7436%3023.3198%30–30104.15< 1%30
LNS24.940.2925.850.3218.690.3551.040.6630.731.49
SA26.210.0928.080.1121.220.1353.540.4236.320.91
RL(s.10)27.301.6126.932.5819.963.2235.447.0822.919.95
CEM26.820.0827.760.1120.320.1244.950.5027.481.09
SMC24.640.34_25.51_0.37_18.48_0.4050.840.7230.651.56
Rounded MBD27.570.28_29.86_0.1921.750.2960.861.4437.373.10
Discrete MBD (ours)_24.94_0.1525.210.1718.010.20_37.30_0.8622.061.70
SS-AT
CTAS-D (30 s)–30–30–30–30–30
LNS44.970.2954.510.3240.980.35130.860.6683.281.49
SA46.010.0955.440.1141.990.13115.030.4280.020.90
RL(s.10)50.462.5357.554.2633.595.1970.9512.4537.7016.08
CEM46.870.0854.310.1138.970.1299.390.5060.801.09
SMC_44.34_0.34_53.96_0.3740.100.40130.570.7282.841.56
Rounded MBD50.480.2861.480.1947.600.29143.571.4493.503.11
Discrete MBD (ours)44.230.1651.370.17_34.52_0.20_83.46_0.86_47.61_1.69
MS-AT
CTAS-D (30 s)62.2924%3080.3610%3039.5119%30126.54< 1%3067.603%30
LNS36.320.4632.720.5622.510.7168.911.5240.663.31
SA39.300.1736.610.2626.960.4074.281.1948.282.52
RL(s.10)41.442.2135.213.1623.803.8747.158.9327.9212.27
CEM36.220.1732.280.2622.360.4052.181.3131.162.77
SMC_35.49_0.49_32.19_0.60_22.12_0.7568.531.5740.323.38
Rounded MBD40.880.3838.120.3627.010.5782.452.1749.634.47
Discrete MBD (ours)35.450.2631.550.3521.260.65_49.81_1.82_28.35_3.65

Table 2. Mean makespan and computation time on heterogeneous MRTA problem (17) over 50 problem instances across 5 solver seeds. CTAS-D superscripts indicate success rates. Bold/underline indicate best/second-best makespan, respectively.

Conclusions

In this paper, we proposed Discrete Model-Based Diffusion (Discrete MBD), a training-free sampling-based optimization (SBO) method that replaces the learned denoiser of discrete diffusion with a Monte Carlo approximation and guarantees asymptotic convergence to the global optimum. We also presented a priority-based encoding for heterogeneous MRTA that guarantees feasible samples and thus improves sample efficiency. Discrete MBD outperforms SBO and metaheuristic baselines in nearly all settings and matches mixed-integer linear program-based and learning-based methods at a fraction of their computational cost.

Several directions remain for future work. First, Discrete MBD needs enough denoising steps to be competitive; with few steps, it may perform no better, or even worse, than other methods. Our convergence bound characterizes the role of the number of steps but becomes loose as the problem size grows. Using adaptive noise schedules to reduce the number of denoising steps would be an interesting direction. Second, like other SBO methods, Discrete MBD loses sample efficiency on larger problems. For heterogeneous MRTA, extending Discrete MBD to a distributed setting, as in [20], is a promising direction. Lastly, we assume a deterministic cost JJ. Extending Discrete MBD to stochastic objectives would allow our MRTA formulation to capture uncertain skill requirements and travel times.

Appendix

Before the proof for Theorem 1, we first provide two supporting lemmas.

Lemma 1. *Let Assumption 1 hold, and let x(i)∈XN,Kx^{(i)} \in\mathcal{X}_{N,K} be

the solution at diffusion step 1≤i≤M1 \le i \le M. Then, we have (A) ϕi(x)≥(1−αˉiK)N\phi_i(\mathbf{x}) \ge\left(\frac{1-\bar{\alpha}_i}{K}\right)^N for all x∈XN,K\mathbf{x} \in\mathcal{X}_{N,K} and (B) ϕi(x(i))≥αˉiN\phi_i(\mathbf{x}^{(i)}) \ge\bar{\alpha}_i^N.

Proof: By Assumption 1, we have Q‾i=αˉiI+(1−αˉi)1K1K1K⊤\overline{Q}_i=\bar{\alpha}_i I+(1-\bar{\alpha}_i)\frac{1}{K}\mathbf{1}_K\mathbf{1}_K^\top. Hence, under ϕi(⋅)\phi_i(\cdot) (13), each row independently selects the same category xr(i)x_r^{(i)} with probability αˉi+1−αˉiK≥αˉi\bar{\alpha}_i+\frac{1-\bar{\alpha}_i}{K}\ge\bar{\alpha}_i, which proves (B). It selects each other category with probability 1−αˉiK\frac{1-\bar{\alpha}_i}{K}, which proves (A).

Lemma 2. Let Assumption 1 hold, and let x(i)∈XN,K\mathbf{x}^{(i)}\in\mathcal{X}_{N,K} be the solution at diffusion step 1≤i≤M1\le i\le M. For any set of samples XS1\mathcal{X}_{S_1} and temperature λ>0\lambda>0, p^i\hat{p}_i from (15) satisfies

p^i(x(i)∣x(i))≥1−Nβi1−αˉi.(23)\hat{p}_i(\mathbf{x}^{(i)}\mid\mathbf{x}^{(i)})\ge1-\frac{N\beta_i}{1-\bar{\alpha}_i}. \tag*{(23)}

Proof: Fix xs∈XS1\mathbf{x}_s\in\mathcal{X}_{S_1} and a row rr, and let kk and k′k' be defined such that [x(i)]rk=1[\mathbf{x}^{(i)}]_{rk}=1 and [xs]rk′=1[\mathbf{x}_s]_{rk'}=1. By (12), under q(⋅∣x(i),xs)q(\cdot\mid\mathbf{x}^{(i)},\mathbf{x}_s), row rr takes a category j≠kj\ne k with a probability

∑j≠k[Q‾i−1]k′j[Q‾i]jk[Q‾i]k′k≤βi/K(1−αˉi)/K=βi1−αˉi,(24)\sum_{j\ne k}\frac{[\overline{Q}_{i-1}]_{k'j}[\overline{Q}_i]_{jk}}{[\overline{Q}_i]_{k'k}} \le\frac{\beta_i/K}{(1-\bar{\alpha}_i)/K} =\frac{\beta_i}{1-\bar{\alpha}_i}, \tag*{(24)}

since, by Assumption 1, [Q‾i]jk=βi/K[\overline{Q}_i]_{jk}=\beta_i/K for j≠kj\ne k, ∑j≠k[Q‾i−1]k′j≤1\sum_{j\ne k}[\overline{Q}_{i-1}]_{k'j}\le1, and [Q‾i]k′k≥(1−αˉi)/K[\overline{Q}_i]_{k'k}\ge(1-\bar{\alpha}_i)/K. Since the rows of q(⋅∣x(i),xs)q(\cdot\mid\mathbf{x}^{(i)},\mathbf{x}_s) are independent by (12) and βi/(1−αˉi)≤1\beta_i/(1-\bar{\alpha}_i)\le1,

q(x(i)∣x(i),xs)≥(1−βi1−αˉi)N≥1−Nβi1−αˉi(25)q(\mathbf{x}^{(i)}\mid\mathbf{x}^{(i)},\mathbf{x}_s)\ge\left(1-\frac{\beta_i}{1-\bar{\alpha}_i}\right)^N\ge1-\frac{N\beta_i}{1-\bar{\alpha}_i} \tag*{(25)}

by Bernoulli’s inequality. This holds for every xs\mathbf{x}_s, and p^i\hat{p}_i is a convex combination of these components, so the bound also holds for p^i\hat{p}_i.

Now we provide the proof for Theorem 1:

Proof: Let pi⋆:=Pr⁡(x(i)∈X⋆)p_i^\star:=\Pr(\mathbf{x}^{(i)}\in\mathcal{X}^\star), and let Fi\mathcal{F}_i be the σ\sigma-algebra generated by x(M)\mathbf{x}^{(M)} and all samples drawn at steps M,…,i+1M,\ldots,i+1. Then, x(i)\mathbf{x}^{(i)} is Fi\mathcal{F}_i-measurable. Since every element of X⋆\mathcal{X}^\star attains the maximum of p0p_0 over XN,K\mathcal{X}_{N,K} and no other element does, the selection step of Algorithm 1 (line 7) gives x(i−1)∈X⋆\mathbf{x}^{(i-1)}\in\mathcal{X}^\star if and only if X⋆∩(XS1∪XS2)≠∅\mathcal{X}^\star\cap(\mathcal{X}_{S_1}\cup\mathcal{X}_{S_2})\ne\varnothing. We now proceed in three steps.

(Step 1) Let hi:=((1−αˉi)/K)Nh_i:=((1-\bar{\alpha}_i)/K)^N. We have two cases. First consider {x(i)∉X⋆}∈Fi\{\mathbf{x}^{(i)}\notin\mathcal{X}^\star\}\in\mathcal{F}_i. Given Fi\mathcal{F}_i, the samples in XS1\mathcal{X}_{S_1} are i.i.d. from the proposal ϕi\phi_i (13). Thus, for any optimal solution x⋆∈X⋆\mathbf{x}^\star\in\mathcal{X}^\star, by Lemma 1(A), we have

Pr⁡(x(i−1)∉X⋆∣Fi)≤(1−ϕi(x⋆))S1≤(1−hi)S1=:bi.(26)\Pr(\mathbf{x}^{(i-1)}\notin\mathcal{X}^\star\mid\mathcal{F}_i)\le(1-\phi_i(\mathbf{x}^\star))^{S_1}\le(1-h_i)^{S_1}=:b_i. \tag*{(26)}

On the event {x(i)∈X⋆}∈Fi\{\mathbf{x}^{(i)}\in\mathcal{X}^\star\}\in\mathcal{F}_i, Lemma 1(B) gives ϕi(x(i))≥αˉiN\phi_i(\mathbf{x}^{(i)})\ge\bar{\alpha}_i^N, and given (Fi,XS1)(\mathcal{F}_i,\mathcal{X}_{S_1}), the samples in XS2\mathcal{X}_{S_2} are i.i.d. from p^i(⋅∣x(i))\hat{p}_i(\cdot\mid\mathbf{x}^{(i)}) with 1−p^i(X⋆)≤1−p^i(x(i)∣x(i))≤Nβi/(1−αˉi)1-\hat{p}_i(\mathcal{X}^\star)\le1-\hat{p}_i(\mathbf{x}^{(i)}\mid\mathbf{x}^{(i)})\le N\beta_i/(1-\bar{\alpha}_i) by Lemma 2. Note that

1−αˉiN=(1−αˉi)(1+αˉi+αˉi2+⋯+αˉiN−1)≤N(1−αˉi).1-\bar{\alpha}_i^N=(1-\bar{\alpha}_i)(1+\bar{\alpha}_i+\bar{\alpha}_i^2+\cdots+\bar{\alpha}_i^{N-1})\le N(1-\bar{\alpha}_i).

Combining the above with (a) S1≥S2S_1\ge S_2 and (b) βi=(αˉi−1−αˉi)/αˉi−1≤L/(Mamin⁡)\beta_i=(\bar{\alpha}_{i-1}-\bar{\alpha}_i)/\bar{\alpha}_{i-1}\le L/(M a_{\min}) by Assumption 1, we get

Pr⁡(x(i−1)∉X⋆∣Fi)≤(1−αˉiN)S1(Nβi1−αˉi)S2(27)\Pr(\mathbf{x}^{(i-1)}\notin\mathcal{X}^\star\mid\mathcal{F}_i) \le(1-\bar{\alpha}_i^N)^{S_1}\left(\frac{N\beta_i}{1-\bar{\alpha}_i}\right)^{S_2} \tag*{(27)}
≤(N2βi)S2≤(ρ/M)S2.(28)\le(N^2\beta_i)^{S_2}\le(\rho/M)^{S_2}. \tag*{(28)}

With (23) and (24), we get

Pr⁡(x(i−1)∈X⋆∣Fi)≥(1−bi)I{x(i)∉X⋆}(29)\Pr(\mathbf{x}^{(i-1)}\in\mathcal{X}^\star\mid\mathcal{F}_i) \ge(1-b_i)\mathbb{I}\{\mathbf{x}^{(i)}\notin\mathcal{X}^\star\} \tag*{(29)}
+(1−ℓ)I{x(i)∈X⋆},(30)+(1-\ell)\mathbb{I}\{\mathbf{x}^{(i)}\in\mathcal{X}^\star\}, \tag*{(30)}

where 1−ℓ=[1−(ρ/M)S2]+1-\ell=[1-(\rho/M)^{S_2}]_+. Taking expectations in (25),

pi−1⋆≥(1−bi)(1−pi⋆)+(1−ℓ)pi⋆.(31)p_{i-1}^\star\ge(1-b_i)(1-p_i^\star)+(1-\ell)p_i^\star. \tag*{(31)}

(Step 2) Since 0≤1−ℓ≤10\le1-\ell\le1, we can get

pi−1⋆≥(1−ℓ)(1−bi)(1−pi⋆)+(1−ℓ)pi⋆(32)p_{i-1}^\star\ge(1-\ell)(1-b_i)(1-p_i^\star)+(1-\ell)p_i^\star \tag*{(32)}
=(1−ℓ)(1−bi(1−pi⋆)).(33)=(1-\ell)(1-b_i(1-p_i^\star)). \tag*{(33)}

Since the right-hand side of (27) is nondecreasing in pi⋆p_i^\star, with a lower bound on pi⋆p_i^\star, we can also lower bound pi−1⋆p_{i-1}^\star. Let Bi:=∏j=i+1MbjB_i:=\prod_{j=i+1}^M b_j, with BM:=1B_M:=1. We show pi⋆≥(1−Bi)(1−ℓ)M−ip_i^\star\ge(1-B_i)(1-\ell)^{M-i} by induction on i=M,M−1,…,0i=M,M-1,\ldots,0. The case i=Mi=M holds since pM⋆≥0p_M^\star\ge0. If it holds for ii, then by (27),

pi−1⋆≥(1−ℓ)(1−bi+bi(1−Bi)(1−ℓ)M−i)(34)p_{i-1}^\star\ge(1-\ell)(1-b_i+b_i(1-B_i)(1-\ell)^{M-i}) \tag*{(34)}
≥(1−ℓ)(1−biBi)(1−ℓ)M−i(35)\ge(1-\ell)(1-b_iB_i)(1-\ell)^{M-i} \tag*{(35)}
=(1−Bi−1)(1−ℓ)M−i+1,(36)=(1-B_{i-1})(1-\ell)^{M-i+1}, \tag*{(36)}

and thus the induction holds on i=M,M−1,…,0i=M,M-1,\ldots,0.

(Step 3) Using the result from Step 2, with I={1,…,M}\mathcal{I}=\{1,\ldots,M\}, we get

Pr⁡(x(0)∈X⋆)=p0⋆≥(1−∏i∈Ibi)(1−ℓ)M.(37)\Pr(\mathbf{x}^{(0)}\in\mathcal{X}^\star)=p_0^\star\ge\left(1-\prod_{i\in\mathcal{I}}b_i\right)(1-\ell)^M. \tag*{(37)}

Finally, we bound (1−∏i∈Ibi)(1-\prod_{i\in\mathcal{I}}b_i) in (29):

∏i∈Ibi=∏i∈Iexp⁡(S1ln⁡(1−hi))=exp⁡(S1∑i∈Iln⁡(1−hi)).\begin{aligned} \prod_{i\in\mathcal{I}}b_i=\prod_{i\in\mathcal{I}}\exp(S_1\ln(1-h_i)) \\ &=\exp\left(S_1\sum_{i\in\mathcal{I}}\ln(1-h_i)\right). \end{aligned}

Since ln⁡(1−h)\ln(1-h) is concave and decreasing in hh, Jensen’s inequality gives

∏i∈Ibi=exp⁡(S1M⋅1M∑i∈Iln⁡(1−hi))≤exp⁡(S1Mln⁡(1−1M∑i∈Ihi)).\begin{aligned} \prod_{i\in\mathcal{I}}b_i =\exp\left(S_1M\cdot\frac{1}{M}\sum_{i\in\mathcal{I}}\ln(1-h_i)\right) \\ &\le\exp\left(S_1M\ln\left(1-\frac{1}{M}\sum_{i\in\mathcal{I}}h_i\right)\right). \end{aligned}

Since (1−a(i/M))N(1-a(i/M))^N is nondecreasing with respect to i∈Ii\in\mathcal{I} by Assumption 1, we get (1−a(i/M))N≥M∫(i−1)/Mi/M(1−a(τ))N dτ(1-a(i/M))^N\ge M\int_{(i-1)/M}^{i/M}(1-a(\tau))^N\,d\tau. Then using the additivity of the integral, we know ∑i∈Ihi≥MγN/KN\sum_{i\in\mathcal{I}}h_i\ge M\gamma_N/K^N. Therefore,

∏i∈Ibi≤(1−1M∑i∈Ihi)S1M≤(1−γNKN)S1M.(38)\prod_{i\in\mathcal{I}}b_i\le\left(1-\frac{1}{M}\sum_{i\in\mathcal{I}}h_i\right)^{S_1M}\le\left(1-\frac{\gamma_N}{K^N}\right)^{S_1M}. \tag*{(38)}

By Bernoulli’s inequality, (1−ℓ)M≥1−Mℓ(1-\ell)^M\ge1-M\ell since $0\le\ell\le1 and M≥1M \ge1. Together with (1−ℓ)M≥0(1-\ell)^M \ge0 and ℓ≤(ρ/M)S2\ell\le(\rho/M)^{S_2} this gives (1−ℓ)M≥[1−ρ(ρ/M)S2−1]+(1-\ell)^M \ge[1-\rho(\rho/M)^{S_2-1}]_+. Substituting this and (30) into (29) completes the proof.

References

  1. [1]Ashay Aswale and Carlo Pinciroli. Heterogeneous coalition formation and scheduling with multi-skilled robots. In 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 5402–5409. IEEE, 2023.arxiv.org/abs/2306.11936
  2. [2]Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg. Structured denoising diffusion models in discrete state-spaces. Advances in neural information processing systems, 34:17981–17993, 2021.arxiv.org/abs/2107.03006
  3. [3]William Babincsak, Ashay Aswale, and Carlo Pinciroli. Ant colony optimization for heterogeneous coalition formation and scheduling with multi-skilled robots. In 2023 International Symposium on Multi-Robot and Multi-Agent Systems (MRS), pages 121–127, 2023. doi: 10.1109/MRS60187.2023.10416771.DOI
  4. [4]James C Bean. Genetic algorithms and random keys for sequencing and optimization. ORSA journal on computing, 6(2):154–160, 1994.DOI
  5. [5]Dimitris Bertsimas and John Tsitsiklis. Simulated annealing. Statistical science, 8(1):10–15, 1993.
  6. [6]Endre Boros and Peter L. Hammer. Pseudo-boolean optimization. Discrete Applied Mathematics, 123(1):155–225, 2002. ISSN 0166-218X.DOI
  7. [7]James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Yash Katariya, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018.
  8. [8]Yuxiao Chen, Anubhav Singh, Ryo Kuroiwa, and J Christopher Beck. New exact methods for solving quadratic traveling salesman problem. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 35, pages 325–333, 2025.DOI
  9. [9]Weiheng Dai, Utkarsh Rai, Jimmy Chiun, Yuhong Cao, and Guillaume Sartoretti. Heterogeneous Multi-robot Task Allocation and Scheduling via Reinforcement Learning. IEEE Robotics and Automation Letters, 10 (3):2654–2661, March 2025. ISSN 2377-3766. doi: 10.1109/LRA.2025.3534682.DOI
  10. [10]Pierre Del Moral, Arnaud Doucet, and Ajay Jasra. Sequential monte carlo samplers. Journal of the Royal Statistical Society Series B: Statistical Methodology, 68 (3):411–436, 2006.
  11. [11]Bo Fu, William Smith, Denise M. Rizzo, Matthew Castanier, Maani Ghaffari, and Kira Barton. Robust task scheduling for heterogeneous robot teams under capability uncertainty. IEEE Transactions on Robotics, 39(2):1087–1105, 2023. doi: 10.1109/TRO.2022.3216068.DOI
  12. [12]Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2026. URL https://www.gurobi.com.
  13. [13]Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840–6851, 2020.arxiv.org/abs/2006.11239
  14. [14]Francois R Hogan and Alberto Rodriguez. Reactive planar non-prehensile manipulation with hybrid model predictive control. The International Journal of Robotics Research, 39(7):755–773, 2020. doi: 10.1177/0278364920913938.DOI
  15. [15]Emil Hoogeboom, Didrik Nielsen, Priyank Jain, Patrick Forré, and Max Welling. Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in neural information processing systems, 34:12454–12465, 2021.
  16. [16]Daniel Iouan, Ionela Prodan, Sorin Olaru, Florin Stoican, and Silviu-Iulian Niculescu. Mixed-integer programming in motion planning. Annual Reviews in Control, 51:65–87, 2021. ISSN 1367-5788.
  17. [17]Armin Khosravi, Ali Ghasemzadeh, Erfan Babakhani, Amirhossein Kazerouni, Yong-Hong Kuo, Philip Torr, and Seyedali Mirjalili. Diffusion models for combinatorial optimization: A survey. 2026.DOI
  18. [18]G Ayorkor Korsah, Anthony Stentz, and M Bernardine Dias. A comprehensive taxonomy for multi-robot task allocation. The International journal of robotics research, 32(12):1495–1512, 2013.DOI
  19. [19]Vince Kurtz and Hai Lin. Temporal logic motion planning with convex optimization via graphs of convex sets. IEEE Transactions on Robotics, 39(5):3791–3804, 2023.arxiv.org/abs/2301.07773
  20. [20]Haejoon Lee, Xinyi Wang, Taekyung Kim, and Dimitra Panagou. Distributed model-based diffusion for scalable multi-robot trajectory optimization. arXiv preprint arXiv:2607.20992, 2026.arxiv.org/abs/2607.20992
  21. [21]Haoyu Lei, Kaiwen Zhou, Yinchuan Li, Zhitang Chen, and Farzan Farnia. Boosting cross-problem generalization in diffusion-based neural combinatorial solver via inference time adaptation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, pages 36289–36297, 2026.arxiv.org/abs/2502.12188
  22. [22]Xiner Li, Yulai Zhao, Chenyu Wang, Gabriele Scalia, Gokcen Eraslan, Surag Nair, Tommaso Biancalani, Shuiwang Ji, Aviv Regev, Sergey Levine, and Masatoshi Uehara. Derivative-free guidance in continuous and discrete diffusion models with soft value-based decoding. In Advances in Neural Information Processing Systems, volume 38, pages 105884–105922, 2025.arxiv.org/abs/2408.08252
  23. [23]Yang Li, Jinpei Guo, Runzhong Wang, Hongyuan Zha, and Yanchi Yan. Fast 2t: Optimization consistency speeds up diffusion-based training-to-testing solving for combinatorial optimization. Advances in Neural Information Processing Systems, 37:30179–30206, 2024.DOI
  24. [24]Andrew Lucas. Ising formulations of many np problems. Frontiers in Physics, Volume 2 - 2014, 2014. ISSN 2296-424X. doi: 10.3389/fphy.2014.00005.DOI
  25. [25]Tobia Marcucci and Russ Tedrake. Warm start of mixed- integer programs for model predictive control of hybrid systems. IEEE Transactions on Automatic Control, 66(6):2433–2448, 2020.
  26. [26]Seyedali Mirjalili. Genetic algorithm. In Evolutionary algorithms and neural networks: theory and applications, pages 43–55. Springer, 2018.
  27. [27]George L Nemhauser and Laurence A Wolsey. Integer and combinatorial optimization, volume 18. Wiley, New York, 1988.
  28. [28]Alexander Quinn Nichol and Prafulla Dhariwal. Improved denoising diffusion probabilistic models. In International conference on machine learning, pages 8162–8171. PmLR, 2021.arxiv.org/abs/2102.09672
  29. [29]Chaoyi Pan, Zeji Yi, Guanya Shi, and Guannan Qu. Model-based diffusion for trajectory optimization. Advances in Neural Information Processing Systems, 37:57914–57943, 2024.arxiv.org/abs/2407.01573
  30. [30]David Pisinger and Stefan Ropke. Large neighborhood search. In Handbook of metaheuristics, pages 99–127. Springer, 2018.
  31. [31]Yara Rizk, Mariette Awad, and Edward W Tunstel. Cooperative heterogeneous multi-robot systems: A survey. ACM Computing Surveys (CSUR), 52(2):1–31, 2019.DOI
  32. [32]Reuven Rubinstein. The cross-entropy method for combinatorial and continuous optimization. Methodology and computing in applied probability, 1(2):127–190, 1999.DOI
  33. [33]Sebastian Sanokowski, Sepp Hochreiter, and Sebastian Lehner. A diffusion model framework for unsupervised neural combinatorial optimization. arXiv preprint arXiv:2406.01661, 2024.arxiv.org/abs/2406.01661
  34. [34]Sebastian Sanokowski, Wilhelm Berghammer, Haoyu Wang, Martin Ennemoser, Sepp Hochreiter, and Sebastian Lehner. Scalable discrete diffusion samplers: Combinatorial optimization and statistical physics. In International Conference on Learning Representations, volume 2025, pages 87053–87082, 2025.arxiv.org/abs/2502.08696
  35. [35]Philipp Schillinger, Mathias Bürger, and Dimos V Dimarogonas. Simultaneous task allocation and planning for temporal logic goals in heterogeneous multi-robot systems. The international journal of robotics research, 37(7):818–838, 2018.DOI
  36. [36]Robert H Storer, S David Wu, and Renzo Vaccari. New search spaces for sequencing problems with application to job shop scheduling. Management science, 38(10):1495–1509, 1992.DOI
  37. [37]Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. Advances in neural information processing systems, 36:3706–3731, 2023.arxiv.org/abs/2302.08224
  38. [38]Zhe yuan Wang and Matthew Gombolay. Heterogeneous Graph Attention Networks for Scalable Multi-Robot Scheduling with Temporospatial Constraints. In Proceedings of Robotics: Science and Systems, Corvalis, Oregon, USA, July 2020. doi: 10.15607/RSS.2020.XVI.094.
  39. [39]Nils Wilde and Javier Alonso-Mora. Designing heterogeneous robot fleets for task allocation and sequencing. In 2023 International Symposium on Multi-Robot and Multi-Agent Systems (MRS), pages 156–162. IEEE, 2023.arxiv.org/abs/2312.07234
  40. [40]Grady Williams, Paul Drews, Brian Goldfain, James M Rehg, and Evangelos A Theodorou. Information-theoretic model predictive control: Theory and applications to autonomous driving. IEEE Transactions on Robotics, 34(6):1603–1622, 2018.arxiv.org/abs/1707.02342
  41. [41]Zeji Yi, Chaoyi Pan, Guanya Shi, and Guannan Qu. Global convergence of sampling-based nonconvex optimization through diffusion-style smoothing. arXiv preprint arXiv:2605.16520, 2026.arxiv.org/abs/2605.16520
  42. [42]Mark Zlochin, Mauro Birattari, Nicolas Meuleau, and Marco Dorigo. Model-based search for combinatorial optimization: A critical survey. Annals of Operations Research, 131(1):373–395, 2004.

Paper details

vlnc:W_234s7wf8
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents