On Swarm Optimality in Dynamic and Symmetric Environments

摘要

The field of multi agents and multi robotics has become increasingly popular during the last two decades. The motivation behind multi agents based systems is that many tasks can be rather efficiently completed by using multiple simple autonomous agents (robots, software agents, etc.) instead of a single sophisticated one. Such systems are usually also more adaptive, scalable and robust than those based on a single, highly capable, unit. However, when examining such systems, one may be concerned of the price tag attached to the decentralized nature of swarm based approaches. Meaning, while we simplify designs and control mechanisms in order to save costs and computation resources, how far do our systems drift from optimality ? This work examines this issue by constructing an optimal algorithm for the Dynamic Cooperative Cleaners problem (presented and analyzed in [2]). The performance of the SWEEP protocol of [2] is compared to this of the optimal algorithm. The results of this comparison show that as the problem gets harder, the performance of the SWEEP protocol gets closer to those of the optimal algorithm. The work also presents insightful results concerning optimal swarms in symmetric environments.