Wireless Sensor and Actuator Networks: Algorithms and Protocols for Scalable Coordination and Data Communication

9.5 DYNAMIC TASK ASSIGNMENT

In some applications, the dynamic assignment of tasks among robots is required. For instance, in a search-and-rescue mission of 40 robots, a preferred task assignment might be 30 robots to explore the environment, 2 to mark resources, and 8 to maintain a communications network (Ogren et al., 2002). In general, assume that p_i robots need to be assigned to ith task, and that each robot can be assigned to only one task.

Four distributed algorithms were proposed by McLurkin and Yamins (2005) to assign swarms of homogenous robots to subgroups, each of which performs a different task to meet a specified global task distribution. In the simple Random-Choice algorithms, each robot chooses a given task with a probability proportional to the relative size of that task subgroup in the target distribution. In the above example, each node chooses tasks with probabilities 3/4, 1/20, 1/5, respectively. The Random-Choice algorithm does not require communication among robots and completes immediately. However, there is a high probability that it will fail to achieve acceptable target distribution if the size of swarms is small.

The next, the Extreme-Comm algorithm is another extreme for the communication overhead involved. In short, robots flood necessary information, including their IDs and task demands, until all robots learn all the information needed to make the same decision as a centralized algorithm. The tasks can be assigned in sorted order of robot IDs. More ...