Discrete Model-Based Diffusion for Combinatorial Optimization in Multi-Robot Task Allocation
Organizations: Robotics Department, University of Michigan, Ann Arbor, MI, USA · Department of Mechanical Engineering, Oakland University, Rochester, MI, USA
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.
Figures & tables
| UIQP | UPO | ||||||||||||
| Method | 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 | 30 † | 30 † | |||||||
| 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 | |||||||
| 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 | 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 |
Combinatorial Optimization
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
See all 413 papers