WorksComputer Science
Discrete Model-Based Diffusion for Combinatorial Optimization in Multi-Robot Task Allocation
Abstract
Decision making in 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 robotic systems involve inherently discrete choices, such as assigning tasks to robots [11, 35, 39], selecting 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, 40], 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
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 [43], we follow the robotics and control literature [41, 42] 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 our method on numerous generic unconstrained integer programs and heterogeneous MRTA problems.
Preliminaries
We denote the -dimensional column vector of ones by . For matrices and , let denote their elementwise product. For a matrix , we denote by its -th row and by the element in row and column . For a vector , denotes its -th element. For vectors , of the same size, means for all . We denote the sets of positive and nonnegative integers by and , respectively. For a set and , denotes the set of -tuples with entries in , and the set of matrices with entries in .
We consider discrete or categorical decision variables indexed by , each taking one of categories in . A solution can be represented by a categorical decision vector , where denotes the category of variable . Equivalently, it can be represented by a one-hot matrix in
where if and only if . The two representations are related by . Then we can formulate an integer program with a cost function and constraint functions , :
whose feasible set is
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 robots must choose an order in which to perform tasks. Each category can then represent one of the permutations of the tasks. Under a fixed enumeration of these sequences, indicates the specific task sequence performed by robot . With , we have permutations: , , , , , and , which can be indexed by , so means robot 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 contains elements and thus grows exponentially with . Sampling-based optimization (SBO) offers an alternative by recasting (2) as probabilistic inference over the target distribution
with
where enforces feasibility and puts more mass on 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, 42].
While the same property is also promising for combinatorial optimization problems 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.
Figure 2. Positioning of Discrete MBD. MBD [29] incorporates the Gaussian diffusion of DDPM [13] into a training-free optimizer with a known target . Extending MBD directly to discrete solution spaces is structurally challenging, since its Gaussian diffusion processes are tied to continuous (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 , let be a row-stochastic matrix with rows . For , let denote the probability mass of its -th row under the categorical distribution with probability row vector . We consider distributions over that factorize over rows:
D3PM consists of a forward and a reverse process, which we describe next.
Forward (noising) process: The forward process is a fixed Markov chain
that progressively corrupts into categorical noise over noising steps. Let be the row-stochastic transition matrix at step , whose element is the probability that the categorical variable transitions from category to category . Then,
applies the same transition to every row independently. Defining the cumulative transition matrix with , the Markov property gives the -step marginal
which allows us to sample directly from .
In [2], the rows of are required to converge to a known stationary distribution as , for which sufficient conditions are given in [2 A.1]. In this work, we construct to satisfy the following assumption:
Assumption 1. The forward transition matrix is uniform, with . Letting and , the cumulative matrix is [2]. The schedule is given by , where is nonincreasing and -Lipschitz, with and for .
The uniform kernel [2, 15] in Assumption 1 is doubly stochastic, so the uniform distribution is stationary [2 A.1]. Using that, we define
Reverse (denoising) process: The reverse process starts from and aims to recover a low-cost solution. At each step , is sampled from the learned reverse transition
with the posterior distribution
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 . Because this posterior is available in closed form, D3PM trains a neural network only to predict the clean-solution distribution . Then, (11) is used to sample 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 (11) through offline training, it approximates it with the target distribution (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 § 4.
Discrete MBD’s reverse process starts with sampling (10). At each denoising step , Discrete MBD (a) samples candidate solutions from a proposal, (b) uses them to approximate , and (c) samples again from the approximated distribution and selects the best sample as .
(a) Sample. By Bayes’ theorem, we have . However, since couples all rows of , sampling from the normalized posterior requires summing over all elements of , which is intractable.
Instead, we construct a tractable proposal by examining the structure of the posterior. Note that (i) factorizes over rows (9), with , and (ii) is doubly stochastic by Assumption 1. By (i), the likelihood of each row is given by , which by (ii) sums to one and thus defines a categorical distribution over . Hence, our proposal is
whose rows can be sampled independently. From the proposal (13), we then draw a batch of candidate solutions.
(b) Approximate. By construction, for all . Substituting this into Bayes’ theorem with the fact that is normalized, we get
Algorithm 1: Discrete Model-Based Diffusion (Discrete MBD) for Generic Optimization
Inputs: temperature , denoising steps , sample counts ,
Outputs: Final solution
Initialize
for do
Sample
Update the distribution (15):
Sample
Select
return .
Substituting (14) into (11) in place of gives
which we approximate using the samples drawn from :
(c) Select. We draw candidate solutions from (15). Then we choose the lowest-cost candidate from to get .
After denoising steps, Discrete MBD returns 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 at the end of each denoising step , 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 aims 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.

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 : Similar to D3PM, the transition matrices govern how Discrete MBD explores . Under Assumption 1, each row of stays the same with probability , and otherwise switches to one of the other categories uniformly at random. In the early stage of the algorithm (large ), remains relatively small, making closer to uniform and inducing exploration. As decreases, and places more probability mass around , performing local refinement. The schedule 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 .
Theorem 1. Let Assumption 1 hold, , and . Define , , where , and . Then, for every and ,
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 at least once, and the second term lower-bounds the probability of remaining in until the end of the algorithm. Together, they characterize the exploration-exploitation trade-off. A faster-decaying noise schedule keeps the noise level high for longer, which increases and the first term. This matches the intuition that higher noise makes closer to uniform and promotes exploration.
At the same time, it requires a larger , which increases 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 [42].
Effects of sample sizes and diffusion steps: Based on Theorem 1, increasing the sample sizes and or the number of denoising steps raises the guaranteed probability of finding an optimal solution whenever the bound is nontrivial, i.e., . More importantly, as , this lower bound monotonically increases for any and . 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 heterogeneous robots and spatially distributed tasks in the domain , with skill types . We adopt the species-traits model [9, 11], where each robot belongs to one of the species, each with a unique set of skills. Robot has a capability vector , whose th entry is its capability level in skill , a depot , and a speed , so that it travels between in time . Task has a location , a duration , and a nonzero combined capability requirement vector for skills , whose th entry is the required minimum combined capability in skill .
A solution consists of a coalition and a start time for each task , and a route for each robot , which lists the tasks assigned to robot in visiting order, starting and ending at its depot . Under tight coordination, task starts only once all members of have arrived, and all members remain at until . Minimizing the makespan , i.e., the time at which the last robot returns to its depot, yields
s.t.
We assume problem (17) itself is feasible, i.e., for all .
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., has exactly one nonzero entry, whereas in MS (multi-skill agents), robots may have several skills. In BT (binary tasks), , so one capable robot per required skill satisfies (21). 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 , where each row indexed by specifies the priority level robot assigns to task . The entry indicates priority level , with smaller denoting higher priority. We evaluate each candidate by decoding it into a solution as follows.
Decoding: Given , let denote the priority level that robot assigns to task , i.e., . We then evaluate on (17) as follows.
(a) Coalition formation. For each task , visit the robots from highest to lowest priority for task (i.e., increasing , breaking ties by robot index). Add robot to only if doing so reduces the unmet requirement .
(b) Coalition pruning (only for MS-AT). Since robots may possess several skills in MS-AT, can contain a larger team than necessary. For each task , visit the members of from lowest to highest priority (breaking ties by robot index) and remove robot whenever the remaining coalition still meets the requirement, i.e., .
(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, , from highest to lowest priority (i.e., ascending ), 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 .
These steps decode every into a feasible solution of (17). Steps (a)-(b) select coalitions that satisfy (21). Step (c) prevents cyclic waiting among coalitions, satisfying the routing constraints (22)–(24). Hence, Discrete MBD applies directly with .
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 sampling-based 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 and the uniform transition matrix [2, 15] with the modified cosine schedule:
where and , thereby satisfying Assumption 1. At each denoising step, we allocate 75% of the samples to and the remaining 25% to .
Unconstrained Problems
Settings: We consider two classes of unconstrained problems over variables with categories each. Both are written in terms of the integer vector , with . For each problem class and pair , we evaluate methods on 50 random instances.
Unconstrained Integer Quadratic Program (UIQP):
where is symmetric and indefinite and . For , (25) reduces to quadratic unconstrained binary optimization (QUBO), which is equivalent to an Ising problem [24]. We set with i.i.d., and .
Unconstrained Polynomial Optimization (UPO):
where monomial has coefficient and index set . For , (26) is a pseudo-Boolean optimization problem [6]. We use monomials, each over 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 on the relaxation 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 iterations with 2048 samples per iteration.
Results (Q1): Table 1 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 (), where it is still within 0.1% of the best. Discrete MBD takes about 0.6 s per problem, slightly more
| Method | \multicolumn{6}{c}{UIQP} | \multicolumn{6}{c}{UPO} | ||||||||||
| \multicolumn{2}{c}{} | \multicolumn{2}{c}{} | \multicolumn{2}{c}{} | \multicolumn{2}{c}{} | \multicolumn{2}{c}{} | \multicolumn{2}{c}{} | |||||||
| Cost | Time (s) | Cost | Time (s) | Cost | Time (s) | Cost | Time (s) | Cost | Time (s) | Cost | Time (s) | |
| Gurobi (30 s) | 0.11 | 0.19 | 0.51 | 22.16 | ||||||||
| CEM | 0.47 | 0.47 | 0.47 | 0.48 | 0.48 | 0.49 | ||||||
| SMC | 0.86 | 0.86 | 0.86 | 0.86 | 0.86 | 0.86 | ||||||
| Rounded MBD | 0.47 | 0.47 | 0.56 | 0.47 | 0.46 | 0.56 | ||||||
| Discrete MBD (ours) | 0.56 | 0.58 | 0.61 | 0.57 | 0.58 | 0.61 | ||||||
| Scale | – | – | – | – | – | – | ||||||
| Gurobi (30 s) | 27.24 | |||||||||||
| CEM | 0.47 | 0.48 | 0.49 | 0.48 | 0.49 | 0.50 | ||||||
| SMC | 0.87 | 0.87 | 0.87 | 0.86 | 0.86 | 0.86 | ||||||
| Rounded MBD | 0.45 | 0.48 | 0.44 | 0.45 | 0.48 | 0.44 | ||||||
| Discrete MBD (ours) | 0.60 | 0.59 | 0.60 | 0.60 | 0.59 | 0.60 | ||||||
| Scale | – | – | – | – | – | – | ||||||
| Gurobi (30 s) | ||||||||||||
| CEM | 0.47 | 0.49 | 0.50 | 0.48 | 0.51 | 0.52 | ||||||
| SMC | 0.92 | 0.93 | 0.93 | 0.92 | 0.93 | 0.93 | ||||||
| Rounded MBD | 0.45 | 0.44 | 0.47 | 0.45 | 0.44 | 0.47 | ||||||
| Discrete MBD (ours) | 0.59 | 0.58 | 0.58 | 0.59 | 0.58 | 0.58 | ||||||
| Scale | – | – | – | – | – | – |
Table 1. 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 (: Gurobi hit its 30 s time limit).
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 (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) [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 -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 iterations, with 2048 samples per iteration.
| Method | , , Makespan ↓ | , , Time (s) ↓ | , , Makespan ↓ | , , Time (s) ↓ | , , Makespan ↓ | , , Time (s) ↓ | , , Makespan ↓ | , , Time (s) ↓ | , , Makespan ↓ | , , Time (s) ↓ |
| SS-BT | ||||||||||
| CTAS-D (30 s) | 31.39 61% | 30 | 40.74 36% | 30 | 23.31 98% | 30 | – | 30 | 104.15 < 1% | 30 |
| LNS | 24.94 | 0.29 | 25.85 | 0.32 | 18.69 | 0.35 | 51.04 | 0.66 | 30.73 | 1.49 |
| SA | 26.21 | 0.09 | 28.08 | 0.11 | 21.22 | 0.13 | 53.54 | 0.42 | 36.32 | 0.91 |
| RL(s.10) | 27.30 | 1.61 | 26.93 | 2.58 | 19.96 | 3.22 | 35.44 | 7.08 | 22.91 | 9.95 |
| CEM | 26.82 | 0.08 | 27.76 | 0.11 | 20.32 | 0.12 | 44.95 | 0.50 | 27.48 | 1.09 |
| SMC | 24.64 | 0.34 | <u>25.51</u> | 0.37 | <u>18.48</u> | 0.40 | 50.84 | 0.72 | 30.65 | 1.56 |
| Rounded MBD | 27.53 | 0.28 | 29.88 | 0.19 | 21.79 | 0.29 | 60.67 | 1.44 | 37.52 | 3.10 |
| Discrete MBD (ours) | <u>24.88</u> | 0.15 | 25.25 | 0.17 | 17.95 | 0.20 | <u>37.16</u> | 0.86 | 22.03 | 1.70 |
| SS-AT | ||||||||||
| CTAS-D (30 s) | – | 30 | – | 30 | – | 30 | – | 30 | – | 30 |
| LNS | 44.97 | 0.29 | 54.51 | 0.32 | 40.98 | 0.35 | 130.86 | 0.66 | 83.28 | 1.49 |
| SA | 46.01 | 0.09 | 55.44 | 0.11 | 41.99 | 0.13 | 115.03 | 0.42 | 80.02 | 0.90 |
| RL(s.10) | 50.46 | 2.53 | 57.55 | 4.26 | 33.59 | 5.19 | 70.95 | 12.45 | 37.70 | 16.08 |
| CEM | 46.87 | 0.08 | 54.31 | 0.11 | 38.97 | 0.12 | 99.39 | 0.50 | 60.80 | 1.09 |
| SMC | <u>44.34</u> | 0.34 | <u>53.96</u> | 0.37 | 40.10 | 0.40 | 130.57 | 0.72 | 82.84 | 1.56 |
| Rounded MBD | 50.49 | 0.28 | 61.52 | 0.19 | 47.47 | 0.29 | 143.52 | 1.44 | 93.82 | 3.11 |
| Discrete MBD (ours) | 44.02 | 0.16 | 50.79 | 0.17 | <u>34.23</u> | 0.20 | <u>83.25</u> | 0.86 | <u>47.65</u> | 1.69 |
| MS-AT | ||||||||||
| CTAS-D (30 s) | 62.29 24% | 30 | 80.36 10% | 30 | 39.51 19% | 30 | 126.54 < 1% | 30 | 67.60 3% | 30 |
| LNS | 36.32 | 0.46 | 32.72 | 0.56 | 22.51 | 0.71 | 68.91 | 1.52 | 40.66 | 3.31 |
| SA | 39.30 | 0.17 | 36.61 | 0.26 | 26.96 | 0.40 | 74.28 | 1.19 | 48.28 | 2.52 |
| RL(s.10) | 41.44 | 2.21 | 35.21 | 3.16 | 23.80 | 3.87 | 47.15 | 8.93 | 27.92 | 12.27 |
| CEM | 36.22 | 0.17 | 32.28 | 0.26 | 22.36 | 0.40 | 52.18 | 1.31 | 31.16 | 2.77 |
| SMC | 35.49 | 0.49 | <u>32.19</u> | 0.60 | <u>22.12</u> | 0.75 | 68.53 | 1.57 | 40.32 | 3.38 |
| Rounded MBD | 40.85 | 0.38 | 37.87 | 0.36 | 26.86 | 0.57 | 82.20 | 2.17 | 49.61 | 4.47 |
| Discrete MBD (ours) | <u>35.67</u> | 0.26 | 31.68 | 0.35 | 21.30 | 0.65 | <u>49.67</u> | 1.82 | <u>28.36</u> | 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.
Results (Q1 & Q2): As shown in Table II, Discrete MBD achieves the lowest makespan among the SBO methods in 13 out of 15 configurations, lagging behind only on the smallest instances (). In fact, its performance advantage also widens as the problem size grows. Against all baselines, Discrete MBD achieves the lowest makespan in 7 of 15 settings and the second lowest in the remaining 8. 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 outperforms all baselines or closely approaches the strongest baseline in every setting while remaining training-free and fast enough for online use.
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 . 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 be the solution at diffusion step . Then, we have (A) for all and (B) .
Proof. By Assumption 1, we have . Hence, under (13), each row independently selects the same category with probability , which proves (B). It selects each other category with probability , which proves (A).
Lemma 2. Let Assumption 1 hold, and let be the solution at diffusion step . For any set of samples and temperature , from (15) satisfies
Proof. Fix and a row , and let and be defined such that and . By (12), under , row takes a category with a probability
since, by Assumption 1, for , , and . Since the rows of are independent by (12) and ,
by Bernoulli’s inequality. This holds for every , and is a convex combination of these components, so the bound also holds for .
Now we provide the proof for Theorem 1:
Proof. Let , and let be the -algebra generated by and all samples drawn at steps . Then, is -measurable. Since every element of attains the maximum of over and no other element does, the selection step of Algorithm 1 (line 7) gives if and only if . We now proceed in three steps.
(Step 1) Let . We have two cases. First consider . Given , the samples in are i.i.d. from the proposal (13). Thus, for any optimal solution , by Lemma 1(A), we have
On the event , Lemma 1(B) gives , and given , the samples in are i.i.d. from with by Lemma 2. Note that
Combining the above with (a) and (b) by Assumption 1, we get
With (23) and (24), we get
where . Taking expectations in (25),
(Step 2) Since , we can get
Since the right-hand side of (27) is nondecreasing in , with a lower bound on , we can also lower bound . Let , with . We show by induction on . The case holds since . If it holds for , then by (27),
and thus the induction holds on .
(Step 3) Using the result from Step 2, with , we get
Finally, we bound in (29):
Since is concave and decreasing in , Jensen’s inequality gives
Since is nondecreasing with respect to by Assumption 1, we get . Then using the additivity of the integral, we know . Therefore,
By Bernoulli’s inequality, since and . Together with and , this gives . Substituting this and (42) into (41) completes the proof.
References
- [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]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]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]James C Bean. Genetic algorithms and random keys for sequencing and optimization. ORSA journal on computing, 6(2):154–160, 1994.DOI
- [5]Dimitris Bertsimas and John Tsitsiklis. Simulated annealing. Statistical science, 8(1):10–15, 1993.
- [6]Endre Boros and Peter L. Hammer. Pseudo-boolean optimization. Discrete Applied Mathematics, 123(1):155–225, 2002. ISSN 0166-218X.DOI
- [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]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]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]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]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]Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2026. URL https://www.gurobi.com.
- [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]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]Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling. Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in neural information processing systems, 34:12454–12465, 2021.
- [16]Daniel Ioan, 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]Armin Khosravi, Ali Ghasemzadeh, Erfan Babakhani, Amirhossein Kazerouni, Yong-Hong Kuo, Philip Torr, and Seyedali Mirjalili. Diffusion models for combinatorial optimization: A survey. SSRN Electronic Journal, 2026. doi: 10.2139/ssrn.7128558.DOI
- [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]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]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]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]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]Yang Li, Jiping Guo, Runzhong Wang, Hongyuan Zha, and Junchi Yan. Fast t2t: Optimization consistency speeds up diffusion-based training-to-testing solving for combinatorial optimization. Advances in Neural Information Processing Systems, 37:30179–30206, 2024.arxiv.org/abs/2502.02941
- [24]Andrew Lucas. Using formulations of many np problems. Frontiers in Physics, Volume 2 - 2014, 2014. ISSN 2296-424X. doi: 10.3389/fphy.2014.00005.DOI
- [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.arxiv.org/abs/1910.08251
- [26]Seyedali Mirjalili. Genetic algorithm. In Evolutionary algorithms and neural networks: theory and applications, pages 43–55. Springer, 2018.
- [27]George L. Nemhauser and Laurence A Wolsey. Integer and combinatorial optimization, volume 18. Wiley, New York, 1988.
- [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]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]David Pisinger and Stefan Ropke. Large neighborhood search. In Handbook of metaheuristics, pages 99–127. Springer, 2018.
- [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]Reuven Rubinstein. The cross-entropy method for combinatorial and continuous optimization. Methodology and computing in applied probability, 1(2):127–190, 1999.DOI
- [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]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]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]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]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]Zheyuan 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]Isaac E Weintraub, Alexander Von Moll, David W Casbeer, and Satyanarayana G Manyam. Virtual target selection for a multiple-pursuer–multiple-evader scenario. Journal of Aerospace Information Systems, 22(5):391–400, 2025.
- [40]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
- [41]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
- [42]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
- [43]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.

