Scalable Multi-Robot Path Planning via Quadratic Unconstrained Binary Optimization

• URL: http://arxiv.org/abs/2602.14799v1
• Date: Mon, 16 Feb 2026 14:50:04 GMT
• Title: Scalable Multi-Robot Path Planning via Quadratic Unconstrained Binary Optimization
• Authors: Javier González Villasmil,
• Abstract summary: Multi-Agent Path Finding (MAPF) remains a fundamental challenge in robotics.<n>This paper investigates Quadratic Unconstrained Binary Optimization (QUBO) as a structurally scalable alternative for simultaneous multi-robot path planning.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-Agent Path Finding (MAPF) remains a fundamental challenge in robotics, where classical centralized approaches exhibit exponential growth in joint-state complexity as the number of agents increases. This paper investigates Quadratic Unconstrained Binary Optimization (QUBO) as a structurally scalable alternative for simultaneous multi-robot path planning. This approach is a robotics-oriented QUBO formulation incorporating BFS-based logical pre-processing (achieving over 95% variable reduction), adaptive penalty design for collision and constraint enforcement, and a time-windowed decomposition strategy that enables execution within current hardware limitations. An experimental evaluation in grid environments with up to four robots demonstrated near-optimal solutions in dense scenarios and favorable scaling behavior compared to sequential classical planning. These results establish a practical and reproducible baseline for future quantum and quantum-inspired multi-robot coordinations.

Related papers

• Discrete-Guided Diffusion for Scalable and Safe Multi-Robot Motion Planning [56.240199425429445]
  Multi-Robot Motion Planning (MPMP) involves generating trajectories for multiple robots operating in a shared continuous workspace.<n>While discrete multi-agent finding (MAPF) methods are broadly adopted due to their scalability, their coarse discretization trajectory quality.<n>This paper tackles limitations of two approaches by introducing discrete MAPF solvers with constrained generative diffusion models.
  arXiv  Detail & Related papers  (2025-08-27T17:59:36Z)
• Automatic Operator-level Parallelism Planning for Distributed Deep Learning -- A Mixed-Integer Programming Approach [6.449961842220686]
  We propose a bi-level solution framework balancing optimality with computational efficiency.<n>Our framework achieves comparable or superior performance, reducing computational bubbles by half under the same memory constraints.<n>Such capabilities position our solution as both a valuable research tool for exploring optimal parallelization strategies and a practical industrial solution for large-scale AI deployment.
  arXiv  Detail & Related papers  (2025-03-12T13:00:29Z)
• Simultaneous Multi-Robot Motion Planning with Projected Diffusion Models [57.45019514036948]
  Simultaneous MRMP Diffusion (SMD) is a novel approach integrating constrained optimization into the diffusion sampling process to produce collision-free, kinematically feasible trajectories.<n>The paper introduces a comprehensive MRMP benchmark to evaluate trajectory planning algorithms across scenarios with varying robot densities, obstacle complexities, and motion constraints.
  arXiv  Detail & Related papers  (2025-02-05T20:51:28Z)
• Self-Supervised Learning-Based Path Planning and Obstacle Avoidance Using PPO and B-Splines in Unknown Environments [0.0]
  Smart BSP is an advanced self-supervised learning framework for real-time path planning and obstacle avoidance in autonomous robotics.<n>The proposed system integrates Proximal Policy Optimization (PPO) with Convolutional Neural Networks (CNN) and Actor-Critic architecture.<n>During the training process a nuanced cost function is minimized that accounts for path curvature, endpoint proximity, and obstacle avoidance.
  arXiv  Detail & Related papers  (2024-12-03T05:20:29Z)
• A Hybrid Evolutionary Approach for Multi Robot Coordinated Planning at Intersections [0.0]
  Coordinated multi-robot motion planning at intersections is key for safe mobility in roads, factories and warehouses.<n>We propose a new evolutionary-based algorithm using a parametric lattice-based configuration and the discrete-based RRT for collision-free multi-robot planning at intersections.
  arXiv  Detail & Related papers  (2024-12-02T03:40:04Z)
• Intelligent Trajectory Design for RIS-NOMA aided Multi-robot Communications [59.34642007625687]
  The goal is to maximize the sum-rate of whole trajectories for multi-robot system by jointly optimizing trajectories and NOMA decoding orders of robots. An integrated machine learning (ML) scheme is proposed, which combines long short-term memory (LSTM)-autoregressive integrated moving average (ARIMA) model and dueling double deep Q-network (D$3$QN) algorithm.
  arXiv  Detail & Related papers  (2022-05-03T17:14:47Z)
• Robust Topology Optimization Using Multi-Fidelity Variational Autoencoders [1.0124625066746595]
  A robust topology optimization (RTO) problem identifies a design with the best average performance. A neural network method is proposed that offers computational efficiency. Numerical application of the method is shown on the robust design of L-bracket structure with single point load as well as multiple point loads.
  arXiv  Detail & Related papers  (2021-07-19T20:40:51Z)
• Machine Learning Framework for Quantum Sampling of Highly-Constrained, Continuous Optimization Problems [101.18253437732933]
  We develop a generic, machine learning-based framework for mapping continuous-space inverse design problems into surrogate unconstrained binary optimization problems. We showcase the framework's performance on two inverse design problems by optimizing thermal emitter topologies for thermophotovoltaic applications and (ii) diffractive meta-gratings for highly efficient beam steering.
  arXiv  Detail & Related papers  (2021-05-06T02:22:23Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• First Steps: Latent-Space Control with Semantic Constraints for Quadruped Locomotion [73.37945453998134]
  Traditional approaches to quadruped control employ simplified, hand-derived models. This significantly reduces the capability of the robot since its effective kinematic range is curtailed. In this work, these challenges are addressed by framing quadruped control as optimisation in a structured latent space. A deep generative model captures a statistical representation of feasible joint configurations, whilst complex dynamic and terminal constraints are expressed via high-level, semantic indicators. We validate the feasibility of locomotion trajectories optimised using our approach both in simulation and on a real-worldmal quadruped.
  arXiv  Detail & Related papers  (2020-07-03T07:04:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.