Home    |    Research    |    Publications    |    People    |    Private
Overview    |    Methodology    |    Case Studies    |    Links

Task partitioning & Task allocation

Task partitioning in swarm robotics systems

Task partitioning is the process by which a task is decomposed into less-complex sub-tasks, that can be tackled separately. The advantages of task partitioning are many: reduction of physical interference between workers, higher exploitation of specialization, increased efficiency, and higher parallelism. Task partitioning also entails overhead costs, that are due to the higher coordination required within the swarm. The balance between benefits and costs depends on the way a task is partitioned into sub-tasks. Swarms in which the robots are capable of autonomously defining sub-tasks of a given task would be extremely flexible. In fact, the way tasks are partitioned (and therefore performed) could be adapted to specific environments and to the goals to be reached. To date, very few research works are dedicated to the topic of task partitioning. Moreover, all the proposed methods are designed for the tasks at hand and are highly dependent on the specific context. Our research aims at building a general task partitioning framework, which can be utilized in several context and to tackle many different tasks, without the need for implementing ad-hoc solutions for each specific situation.

Task allocation in swarm robotics systems

Task allocation refers to the process by which specific individuals are allocated to specific tasks. The process is individual-centric as it makes decisions about which individual performs which task. Task allocation overlaps with many other fields, for example scheduling, task partitioning and decision making. In swarms, task allocation is usually performed in a self-organized manner, that is, individuals make decisions on what task to perform depending on information obtained by local sensing and local communication. The global allocation emerges over time from the decisions of the individuals. Self-organized task allocation differs in several ways from processes found in other fields such as distributed systems, operations research or scheduling. First, decisions are individual-centric and made by the individuals themselves. Second, decisions are instantaneous, that is, the time-horizon is limited and there is no long-term planning involved. Third, the process is decentralized, that is, there is no controller that plans or allocates tasks centrally. Fourth, self-organized task allocation does not employ sophisticated negotiation schemes and therefore require no (or only simple) communication capabilities. These advantages have, of course, also certain drawbacks. Most notably, due to their stochastic nature, self-organized task allocation strategies are not exact in their allocation. As a result, the strategies are unable to guarantee strict task requirements such as task completion deadlines. Our research aims at developing strategies for self-organized task allocation that allow a swarm of robots to tackle complex tasks.