Latency-Aware Task Assignment and Scheduling in Collaborative Cloud Robotic Systems

摘要

Traditional robotic systems are often incapable of handling complex tasks due to hardware constraints, such as computing ability, storage space, and battery capacity. Cloud robotic systems, characterized by allowing multi-robot systems to access the powerful cloud infrastructures, is a promising solution to fulfill complex tasks, such as disaster management, real-time object recognition, 3D Simultaneous Localization And Mapping (SLAM). However, the destabilizing factors of network could lead to high latency of data transmission in cloud robotic systems, which have made great challenges to the fields that have high real-time requirements. What's more, the existence of heterogeneity of robots further complicates cloud robotics cooperation. In order to minimize the average response time in latency-aware scenarios, we jointly investigate task assignment and scheduling in Collaborative Cloud Robotic Systems (CCRS). We first formulate the problem into a Mixed-Integer Non-Linear Programming (MINLP) and then linearize it into an Integer Linear Programming (ILP) using discrete time structure. To meet the extensibility requirement, we further propose a partitioning-based algorithm to deal with large-scale task graphs. The results show that our two approaches outperform the existing genetic algorithm and greedy algorithm.