# DDM: Fast Near-Optimal Multi-Robot Path Planning using Diversified-Path and Optimal Sub-Problem Solution Database Heuristics

arXiv: https://arxiv.org/abs/1904.02598 · HTML: https://mlsanity.com/paper/1904.02598/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Apr 2019.

## Built on by (most cited first, 3 of 3)

- [Why Solving Multi-agent Path Finding with Large Language Model has not Succeeded Yet](https://mlsanity.com/paper/2401.03630/) (2024)
- [Enhancing Lifelong Multi-Agent Path-finding by Using Artificial Potential Fields](https://mlsanity.com/paper/2505.22753/) (2025)
- [Quantum Grid Path Planning Using Parallel QAOA Circuits Based on Minimum Energy Principle](https://mlsanity.com/paper/2510.07413/) (2025)

## Abstract (arXiv)

We propose a novel centralized and decoupled algorithm, DDM, for solving multi-robot path planning problems in grid graphs, targeting on-demand and automated warehouse-like settings. Two settings are studied: a traditional one whose objective is to move a set of robots from their respective initial vertices to the goal vertices as quickly as possible, and a dynamic one which requires frequent re-planning to accommodate for goal configuration adjustments. Among other techniques, DDM is mainly enabled through exploiting two innovative heuristics: path diversification and optimal sub-problem solution databases. The two heuristics attack two distinct phases of a decoupling-based planner: while path diversification allows the more effective use of the entire workspace for robot travel, optimal sub-problem solution databases facilitate the fast resolution of local path conflicts. Extensive evaluation demonstrates that DDM achieves high levels of scalability and high levels of solution optimality.