Online Task Planning With Collision Avoidance for Heterogeneous Mobile Robots

Recently, heterogeneous mobile robots (HMRs) have been widely implemented in warehouses or factories with limited space to improve efficiency. HMRs have different capabilities and sizes, which leads to two bottlenecks in the task planning for HMRs in an online environment. One is that it is hard to efficiently find high-quality task assignment results between heterogeneous tasks and HMRs because heterogeneous tasks need to be completed by HMRs of different capabilities. The other is that finding collision-free paths for HMRs of different sizes to complete assigned tasks is hard to satisfy the real-time demand. Existing works mainly consider solving these two bottlenecks separately while ignoring the mutual influence between the results of task assignment and collision-free path finding. To solve these issues, in this paper, we formally define the Online Task Planning with Collision Avoidance for HMRs (OTCH) problem, in which the platform aims to find the best task assignment and collision-free paths for HMRs to complete as many heterogeneous tasks as possible while minimizing the total cost containing the path cost and the delay cost. To solve the OTCH problem, we propose a novel task planning framework that considers task assignment and collision-free path finding simultaneously. Within this framework, we first present an aggregation algorithm to accelerate calculations. Then, we propose a network-flow-based task assignment algorithm to find a high-quality task assignment between heterogeneous tasks and HMRs in each batch. Finally, we propose a novel and efficient path finding algorithm to find collision-free paths for HMRs to complete assigned tasks while satisfying real-time demand. In addition, we not only analyze the complexity of the OTCH problem in detail but also give theoretical analysis for our proposed algorithms. Extensive experiments in a real-world dataset and two simulated datasets show that our proposed algorithms outperform the state-of-the-art while having the best scalability.