Evaluating centralised task-scheduling algorithms for multi-robot task-allocation problems

This project investigates the problem of task allocation with swarms of robots. Swarm robotics enables multiple robots to work together with the aim of accomplishing a particular task. In some cases, it might be beneficial to split a large task into smaller tasks. This project explores tasks that are sequentially interdependent, which means that before executing Task B, Task A would need to be executed first.

A foraging task, where robots must find food and return it to a nest, was used as an instance of the task-allocation problem. Foraging could be split into two tasks: harvesting and storing. Previous work in this area investigated the scenario where a harvester robot was to directly hand over the collected food item to a storing robot. In this project a cache with a finite capacity was used, thus enabling a harvester to place the food item within a temporary storage location. A storing robot would then collect the food item and take it to the nest.

The evaluation carried out in this project sought to determine whether a cache would result in a more efficient harvesting solution, and in which cases this might occur. Three algorithms were tested, namely: one where no cache was used (a robot performs both subtasks sequentially); one with fixed allocations; and another with a basic task-allocation algorithm that would depend on the cache status. From the results obtained, it was observed that for the experimental scenario in this project, the best results occurred when a cache was not used. This could prove to be interesting, as the generally held view is that addressing smaller subtasks would yield a better result. The outcome of this experiment suggests that there might be more efficient and more complex task-allocation algorithms, which were not explored in this project.