2019/04/04 by Shuai D. Han, Han, Shuai D., Jingjin Yu +1 · 2 citations
Computer Science · #AI-based Problem Solving and Planning #FOS: Computer and information sciences #Optimization and Search Problems #Robotic Path Planning Algorithms #Robotics (cs.RO)
paper · pdf · doi:10.48550/arxiv.1904.02598
openalex publication_date 2019/04/04 · openalex created_date 2019/04/11 · openalex updated_date 2026/07/28
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.