Support: NSF grants IIS-0093581 and CCR-0330342

The approach in Task Switching in Mobile Wireless Sensor Networks had the problem that we were comparing functions, but not assigning agents to each task.

If we know the nature of the biochemical source, what defines how many agents can be taken away from coverage to work on sensing?

• The size of the region on which the agents have been deployed.
• The total number of agents in the formation.

The characteristics of the region can be defined for each agent before deployment.

The number of agents is dynamical and can change with time: more agents can be deployed, some robots can start to malfunction due to the environment, low battery, etc.

How to count, in a distributed way, how many robots are in the formation, in changes in the size of the network are possible?

• Consensus algorithms can be used.  Nonetheless, we discuss some of the drawbacks of such approach.

1. They require some knowledge (an upper bound) on the maximum network size in order to ensure stability.  This problem has been known before from researchers in the control community.
2. We present the problem of synchronism in the average-consensus algorithm, which had been overseen by the community on this area.

• As an alternative to such consensus algorithm, the aggregation algorithm (more recently known as part of the so-called gossip algorithms) is used.  A novel robust, fully-distributed algorithm that correctly estimates the number of robots in the network is thus presented.

Knowing both, the total number of robots in the network and the characteristics of the region, allows each agent to decide how many robots (but not which) can be taken from coverage and assigned to sensing.

The problem at this point becomes: how to choose such robots?

Under the assumption of a good estimator, it is shown that closest robots to the source would be the ones that switch to sensing.

A flag propagation algorithm allows to each agent, based only on the information gathered by some of its neighbors, to decide whether or not should it switch to sensing or stay doing coverage.

The algorithm is shown to lead the system to convergence towards an stable equilibrium point, to be fully distributed (thus scalable) and robust to changes in the network.

The algorithm is easily extendable to the situation when multiple sources appear in the formation.

It is assumed that there are enough agents to attend simultaneously all the source that can appear in the environment.

As in the single source case, each agent choses the source to which it might be assigned based on its relative distance to it.

Since the Voronoi regions induced by the sources define a partition of the space, at least one source has all the required agents in its induced region.

An inductive argument can thus be made to guarantee the convergence of the algorithm.

This generalization, as in the single source case, is shown to be robust, scalable, and to lead the network towards an stable equilibrium position on which each source has been attended.

Note: The simulations on this project have been based on the Mathematica code provided by the authors of  Coverage Control for Mobile Sensing Networks. IEEE Transactions on Robotics and Automation, 20(2):243--255, 2004.

The slides of the talk given in the 2007 IEEE ICRA Workshop on Collective Behaviors inspired by Biological and Biochemical Systems are here.

Back                        Home