Exhaustiveness Does Not Necessarily Mean Better: Selective Task Planning for Multi-robot Systems

摘要

The performance of multi-robot systems heavily relies on efficient task allocation and motion coordination. However, for a group of a large number of robots, finding the optimal solution is inevitably time-consuming and may become impossible. Recognizing that tasks vary in their impact on system performance, our main idea is to identify their critical subset that significantly influences the entire system, and enhance task allocation efficiency by optimally planning critical tasks while distributing the remaining tasks randomly or with simple strategies. We call this approach Selective Multi-robot Task Planning (SMTP), which contributes to significantly reducing the computational requirements and solution time, and in the meanwhile, maintaining the system performance. In addition, by implementing a filtering mechanism based on the conditional expectation to eliminate less essential tasks, SMTP shows high extendability, maximizes task allocation efficiency, and balances computational efficiency and solution quality. Massive simulation and real experiments demonstrate that our algorithm decreases the computation time and maintains the properties of the base system. Large-scale experiments show that our approach only takes 11% computation time to reach 80% optimization objective and 94.8% traffic balance performance.