Spatial Allocation in Swarm Robotics

From AIRWiki
Jump to: navigation, search

Spatial Allocation in Swarm Robotics.
Short Description: Methods for the allocation of an autonomous swarm of robots to spatially distributed activities.
Coordinator: AndreaBonarini (
Tutor: AndreaBonarini (
Students: JacopoDeStefani (
Research Area: Robotics
Research Topic: Exploration Strategies
Start: 2012/09/01
End: 2015/03/29
Status: Closed
Level: Ms
Type: Thesis


The thesis is publicly available on Politesi (here), the digital archive of PhD and Post-graduate theses of Politecnico di Milano. The work discussed in Milan consists of an extension of the Master's Thesis developed at the IRIDIA laboratory of the ULB, in Brussels, and discussed in September 2013.


This thesis proposes three distributed methods to achieve the allocation of a homogeneous swarm of robots to spatially distributed collective activities. Such tasks require the simultaneous presence of multiple robots to be successfully performed.

Several approaches to solve the problem have been proposed in the scientific literature, both centralized and decentralized (relying either on implicit or explicit coordination), but, to the best of our knowledge, none of these works has focused on an instance of the problem with a scarce number of agents (i.e. inferior to the number of available task), using robots and tasks both embodied.

The problem has first been formally analyzed and specified, using a novel approach based on UML diagrams. Then, the methods have been developed in the form of probabilistic finite state machines (PFSM), a microscopic level, behavior-based approach in swarm robotics. The first method (Naive) simply consists of a greedy allocation of the robots to available tasks in the environment, as soon as they have been localized. The second one (Probabilistic) improves the Naive one with probabilistic rules to avoid allocation conflicts and achieve a more uniform allocation. The third (Informed) is built upon the Probabilistic one, using odometry to avoid the redundant exploration of already visited clusters. The methods have been simulated on three different scenarios: Uniform, Biased and Corridor. We characterize the methods according to their allocation uniformity and allocation speed.

We show that there exists a trade-off between uniformity and speed for the developed methods. We also find that the positioning of the clusters has a strong impact on the performances of the methods. We conclude that the Informed method has the best performances on the proposed scenarios.

Keywords: Swarm robotics, Task allocation, Decentralized control, Coalition formation.