Discrete diffusion drops offline training: DMBD optimizes discrete variables directly and beats sampling baselines in 14 of 15 multi-robot task-allocation settings

Discrete decisions in combinatorial optimization can now be solved by diffusion-style sampling without training a neural network, with each decision variable treated as a categorical random variable and denoised step by step. Model-based diffusion previously denoised only in continuous space, so solutions had to be rounded, which degrades quality and can violate constraints; existing discrete diffusion solvers for combinatorial optimization instead learn the denoiser offline. Across 15 settings of a heterogeneous multi-robot coalition-formation and scheduling benchmark, DMBD reaches the lowest makespan among sampling-based methods in 14, trailing only on the smallest SS-BT instance; against all baselines it is lowest in 8 settings and second lowest in the other 7.

Each denoising step keeps the lowest-cost candidate, steering the search toward low-cost regions. The procedure follows the forward noising and reverse denoising structure of discrete diffusion D3PM, but the reverse transition distribution is approximated from samples weighted by the known target distribution, a Monte Carlo estimate, rather than learned. On generic unconstrained integer quadratic programs and polynomial optimization, DMBD achieves the lowest average cost among sampling-based methods in 17 of 18 settings, at about 0.6 s per problem, slightly more than the cross-entropy method and rounded MBD.

For multi-robot task allocation, candidate solutions are encoded as robot-task priorities and decoded into feasible coalitions and schedules. Sampling the original problem directly would make most samples violate constraints and waste the sampling budget, so a priority-based encoding makes every sample decode into a feasible solution. The encoding is evaluated on five configurations each of the SS-BT, SS-AT and MS-AT variants with 50 instances per setting, where a successful run returns a deadlock-free plan completing every task.

The evaluation is simulation-based: generic unconstrained integer quadratic programs and polynomial optimization at several sizes with 50 random instances each, plus 15 settings of heterogeneous multi-robot coalition formation and scheduling across three variants with 50 instances each, built on an existing benchmark environment; a successful run returns a deadlock-free plan completing every task. The method targets researchers and engineers who must solve discrete decisions within a seconds-scale time budget.

DMBD needs enough denoising steps to be competitive and may perform no better, or worse, than other methods with few steps; the convergence bound becomes loose as problem size grows. Like other sampling-based optimizers it loses sample efficiency on larger problems, and a reinforcement-learning policy performs better on larger multi-robot configurations. The method currently assumes a deterministic cost, and the priority encoding is neither injective nor surjective.