Optimization of Task Allocation for Resource-Constrained Swarm Robots

While task allocation of swarm robots has been extensively researched, resource constraints of robots are rarely considered. In this work, we propose two novel task allocation methods robust to robot failures while considering the resource constraint, limited communication range, and deadline constraint of tasks. The first method, STA (static task allocation) method, finds an optimal task allocation solution at compile-time in terms of the minimum expected finish time, using answer set programming. On the other hand, the DTA (dynamic task allocation) method determines the task candidates for each robot at compile-time considering the resource constraint. It lets each robot select a task autonomously at run-time iteratively by exchanging the task allocation information with its neighbor robots. We assess the efficacy of our methods across three distinct environments: a numerical simulation, a swarm robotics simulation, and real robots. Experimental results show that the proposed methods can effectively tolerate robot failures, and the DTA method is superior to the STA method as the probability of robot failure increases. However, the STA method also exhibits consistent performance and superiority when faced with limitations in inter-robot communication. Additionally, we validate the feasibility of our method in a real-world context by conducting experiments with actual robots.
Note to Practitioners
—The motivation of this work is to explore how to allocate tasks efficiently to swarm robots to ensure timely completion despite occasional robot failures. In search-and-rescue scenarios, such as in the aftermath of a disaster, the effective use of swarm robots is vital, and the time taken to search is crucial to rescuing individuals within a critical time. Various approaches have been proposed to tackle this problem, taking into account time constraints. However, few studies have considered the impact of hardware constraints on robots. To address this issue, this paper proposes two new strategies to find an optimal allocation: the Static Task Allocation (STA) method and the Dynamic Task Allocation (DTA) method. Our methods are evaluated both on real robots and in simulation environments, demonstrating their suitability for practical application.