Journal
IEEE ROBOTICS AND AUTOMATION LETTERS
Volume 5, Issue 2, Pages 1350-1357Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/LRA.2020.2967326
Keywords
Path planning for multiple mobile robots or agents; planning; scheduling and coordination; multi-robot systems
Categories
Funding
- National Science Foundation [IIS-1734419, IIS-1845888]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available