cs.RONov 9, 2026

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

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

Explore similar work

CardsList
  1. Distributed Model-Based Diffusion For Scalable Multi-Robot Trajectory Optimization

    Jul 23, 2026Haejoon Lee, Xinyi Wang, Taekyung Kim +1Multi-Robot Motion PlanningDistributed Optimization

  2. Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching

    May 29, 2026Shengyu Feng, Tarun Suresh, Yiming YangAdjoint MethodNeural Combinatorial Optimization

  3. Parallel Tempering for Diffusion-Based Combinatorial Optimization

    Sep 29, 2026Arman Mielke, Uwe Bauknecht, Thilo Strauss +1Combinatorial OptimizationNeural Combinatorial Optimization