Discrete Model-Based Diffusion for Combinatorial Optimization in Multi-Robot Task Allocation
Authors: Haejoon Lee, Thomas Marshall Vielmetti, Xinyi Wang, Dimitra Panagou
Organizations: Robotics Department, University of Michigan, Ann Arbor, MI, USA · Department of Mechanical Engineering, Oakland University, Rochester, MI, USA
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.
Figures & tables
Fig. 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.
Fig. 2: Positioning of DMBD . MBD [ 29 ] incorporates the Gaussian diffusion of DDPM [ 13 ] into a training-free optimizer with a known target p0(x) . Extending MBD directly to discrete solution spaces is structurally challenging, since its Gaussian diffusion processes are tied to continuous 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 .
Fig. 3: Visualization of denoising process in DMBD ( DMBD ) 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.
Algorithm 1 DMBD ( DMBD ) for Generic Optimization
UIQP
UPO
K=10
K=50
K=100
K=10
K=50
K=100
Method
Cost ↓
Time (s) ↓
Cost ↓
Time (s) ↓
Cost ↓
Time (s) ↓
Cost ↓
Time (s) ↓
Cost ↓
Time (s) ↓
Cost ↓
Time (s) ↓
N=10
Gurobi (30 s)
−10.01
0.11
−2.95
0.19
−1.20
0.51
−10.01
22.16
−4.72
30 †
−1.57
30 †
CEM
−9.78
0.47
−2.79
0.47
−1.13
0.47
−9.71
0.48
−4.37
0.48
−1.45
0.49
SMC
−9.85
0.86
−2.89
0.86
−1.18
0.86
−9.59
0.86
−4.61
0.86
−1.55
0.86
Rounded MBD
−9.73
0.47
−2.48
0.47
−0.93
0.56
−9.22
0.47
−3.03
0.46
−0.81
0.56
TABLE I: 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).
R=9,S=3
R=15,S=5
R=25,S=5
R=25,S=5
R=50,S=5
T=20,B=3
T=20,B=5
T=20,B=5
T=50,B=5
T=50,B=5
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
TABLE II: 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.
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
Trajectory optimization for multi-robot systems remains a critical challenge, particularly when navigating highly non-convex, non-linear, and non-differentiable environments. While Model-Based Diffusion (MBD) has recently emerged as a promising sampling-based optimization paradigm for single-robot trajectory generation, extending it to multi-robot systems results in a centralized, high-dimensional inference problem that (i) suffers from poor sample efficiency due to the curse of dimensionality and (ii) requires global access to all robots' dynamics, constraints, and objectives. To address this, we propose Distributed Model-Based Diffusion (DMBD), a distributed server-robot method that decomposes the reverse diffusion process into local conditional reverse diffusion processes. This decomposition enables each robot to iteratively perform denoising independently within its own control subspace while conditioning on the current trajectory estimates of the other robots that are aggregated and broadcast by the server. Extensive simulations in goal swapping, multi-floor coverage, parking, and rush-hour scenarios demonstrate that DMBD achieves strong scalability, solving many challenging coordination tasks with sub-second computation time and outperforming existing baselines.
Haejoon Lee, Xinyi Wang, Taekyung Kim +1
Robotics Department, University of Michigan, Ann Arbor, MI, USA
Diffusion-based neural solvers have shown strong promise for combinatorial optimization (CO), but existing methods typically rely on supervised training with large collections of near-optimal solutions. In this work, we extend adjoint-based trajectory optimization methods to discrete combinatorial domains. We formulate diffusion-based CO as a stochastic control problem over Continuous-Time Markov Chains and introduce discrete adjoint dynamics for propagating optimization signals through discrete generative trajectories. Building on this formulation, we propose Combinatorial Adjoint Matching (CAM), an unsupervised training framework for discrete diffusion solvers with structured and low-variance trajectory-level optimization signals. Empirically, CAM consistently outperforms existing unsupervised diffusion baselines and achieves performance competitive with strong supervised diffusion solvers and even traditional solvers across diverse combinatorial optimization problems. Our code is available at https://github.com/Shengyu-Feng/CAM.
Shengyu Feng, Tarun Suresh, Yiming Yang
Language Technologies Institute, Carnegie Mellon University · University of Illinois Urbana-Champaign
Discrete diffusion models have emerged as a powerful paradigm for solving combinatorial optimization (CO) problems on graphs by learning to sample high-quality solutions. A common inference-time approach is to generate multiple candidate solutions independently and return the best-performing sample, improving solution quality at the expense of an increase in computational cost. In this work, we introduce PT-Denoise, an inference-time procedure that allows these concurrent denoising trajectories to interact through parallel tempering, without requiring retraining or fine-tuning of the underlying denoiser. Our method assigns a temperature to each diffusion process and allows processes to swap temperatures based on their relative performance. This dynamically reallocates promising, low-energy trajectories to colder, more concentrated sampling regimes while allowing higher-energy states to escape local minima through randomized exploration. Experiments on canonical graph-structured CO problems show that our approach consistently improves the quality of the best solution found, while only adding minimal computational overhead.
Arman Mielke, Uwe Bauknecht, Thilo Strauss +1
ETAS Research · University of Stuttgart · Max Planck Research School for Intelligent Systems (IMPRS-IS) +2