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

Shuai D. Han, Jingjin Yu

Research output: Contribution to journalArticle

Abstract

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 solution quality close to the optimum.

Original languageEnglish (US)
Article number8962218
Pages (from-to)1350-1357
Number of pages8
JournalIEEE Robotics and Automation Letters
Volume5
Issue number2
DOIs
StatePublished - Apr 2020
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mechanical Engineering
  • Control and Optimization
  • Artificial Intelligence
  • Human-Computer Interaction
  • Control and Systems Engineering
  • Computer Vision and Pattern Recognition
  • Biomedical Engineering
  • Computer Science Applications

Keywords

  • Path planning for multiple mobile robots or agents
  • multi-robot systems
  • planning
  • scheduling and coordination

Fingerprint Dive into the research topics of 'DDM: Fast Near-Optimal Multi-Robot Path Planning Using Diversified-Path and Optimal Sub-Problem Solution Database Heuristics'. Together they form a unique fingerprint.

  • Cite this